到给定点的最近点 [英] Closest point to a given point

问题描述

我在 2D 图像中有一组随机选择的像素 K.对于图像中的每个其他像素，我需要找出集合 K 中的哪个像素最接近它(使用标准 sqrt(dx^2 + dy^2) 距离度量).我知道每个像素可能有多个解决方案.显然，它可以通过对集合中的每个像素进行蛮力来完成，但我宁愿避免这种情况，因为它效率不高.还有什么好的建议吗?

I have a set K of randomly selected pixels in a 2D image. For every other pixel in the image I need to find out which pixel in set K is closest to it (using the standard sqrt(dx^2 + dy^2) measure of distance). I am aware that there may be more than one solution for each pixel. Obviously it can be done by brute force against every pixel in the set, but I'd rather avoid this as it's not efficient. Any other good suggestions?

干杯.

推荐答案

不要忘记你不需要为平方根烦恼.

Don't forget that you don't need to bother with the square root.

如果您只想找到最近的(而不是实际距离)，只需使用 dx^2 + dy^2，这将为您提供到每个项目的平方距离，即一样有用.

If you just want to find the nearest one (and not it's actual distance) just use dx^2 + dy^2, which will give you the distance squared to the each item, which is just as useful.

如果您没有包含此像素列表的数据结构，则只需对它们进行测试即可.

If you have no data structure wrapping this list of pixels up, you will need to just test against them all.

如果您有一定的灵活性，有很多好方法可以减少工作量.制作一个 四叉树，或保留像素的排序列表(按 x 排序并按 y 排序)以更快地缩小搜索范围.

If you have some flexibility, there are loads of good ways to reducing the workload. Make a Quadtree, or keep sorted list of the pixels (sorted by x and sorted by y) to narrow your search more quickly.

这篇关于到给定点的最近点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！