我在 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?
Cheers.
发布评论
评论（8）
不要忘记，您不需要费心计算平方根。
如果您只想找到最近的一个（而不是实际距离），只需使用 dx^2 + dy^2 即可，这将为您提供每个项目的距离平方，这同样有用。
如果您没有包含此像素列表的数据结构，则只需对所有像素进行测试。
如果您有一定的灵活性，那么有很多减少工作量的好方法。制作一个 四叉树，或保留像素的排序列表（按 x 排序并按 y 排序）以更快地缩小搜索范围。
Don't forget that you don't need to bother with the square root.
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.
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.
我必须同意 jk 和 Ewan 的意见，制作一个 Voronoi 图。这会将空间划分为多边形。 K 中的每个点都有一个多边形来描述最接近它的所有点。
现在，当您查询一个点时，您需要找到它位于哪个多边形中。这个问题称为点位置，可以通过构造梯形地图。
jk 已经链接到使用 Voronoi 图 .wikipedia.org/wiki/Fortune's_algorithm" rel="noreferrer">Fortune 算法 需要 O(n log n) 计算步骤并消耗 O(n) 空间。
此网站向您展示如何制作梯形地图和怎么查询呢。您还可以在那里找到一些界限：
预期创建时间：O(n log n)
预期空间复杂度：O(n)
但最重要的是，预期查询时间：O(log n)。这（理论上）比 kD 树的 O(√n) 更好。
我的来源（除了上面的链接）是： ，第六章和第七章。
在那里您将找到有关这两种数据结构的详细信息（包括详细证明）。 Google 图书版本仅包含您需要的部分内容，但其他链接应该足以满足您的目的。如果你对这类事情感兴趣就买这本书（这是一本好书）。
I will have to agree with jk and Ewan with making a Voronoi Diagram. This will partition the space in polygons. Every point in K will have a polygon describing all points that are closest to it.
Now when you get a query of a point, you need to find in which polygon it lies. This problem is called Point Location and can be solved by constructing a Trapezoidal Map.
jk already linked to the creation of the Voronoi Diagram using Fortune's algorithm which takes O(n log n) computational steps and costs O(n) space.
This website shows you how to make a trapezoidal map and how to query it. You can also find some bounds there:
Expected creation time: O(n log n)
Expected space complexity: O(n)
But most importantly, expected query time: O(log n). This is (theoretically) better than O(√n) of the kD-tree.
My source(other than the links above) is: Computational Geometry: algorithms and applications, chapters six and seven.
There you will find detailed information about the two data structures (including detailed proofs). The Google books version only has a part of what you need, but the other links should be sufficient for your purpose. Just buy the book if you are interested in that sort of thing (it's a good book).
这称为最近邻搜索。唐纳德·高德纳 (Donald Knuth) 将其称为“邮局问题”。
有多种解决方案：线性搜索、局部敏感散列、向量近似文件和空间分区。
谷歌搜索这些应该有帮助。
This is called the nearest neighbor search. Donald Knuth called it the post-office problem.
There are a number of solutions: linear search, locality sensitive hashing, vector approximation files and space partitioning.
Googling those should help.
将这些点放入 KD 树中，之后可以非常快地找到最近邻居。有关详细信息，请参阅维基百科上的这篇文章。
Put the points in a KD tree, after this it's very fast to find the nearest neighbor. See this article on wikipedia for details.
Voronoi 图的构建是计算几何。 Delaunay 三角剖分的构造也涉及类似的考虑。您可以调整以下Delaunay 算法之一来满足您的需求。
The construction of Voronoi Diagrams is a branch of Computational Geometry. The construction of Delaunay Triangulations involves similar considerations. You may be able to adapt one of the following Delaunay algorithms to suit your needs.
你想要做的是构造一个 voronoi 图 这可以在 O(n log n ）使用平面扫描
what you are trying to do is construct a voronoi diagram this can be done in O(n log n) using a plane sweep
另一个提示：距离始终大于或等于每个坐标差，并且始终小于或等于它们的总和，即
这可能会帮助您更有效地进行排序。
Another hint: The distance is always greater than or equal to each coordinate difference, and always less than or equal to their sum, i.e.
This might help you doing the sorting more efficiently.
根据该图形填充像素的密度，您最好从原始像素向外搜索。
我为图形终端仿真编写了类似的代码。我最终做的是编写一个从中心点开始生长的方边螺旋形状的搜索模式，然后让它不断生长，直到它碰到某个东西。即使在旧的 CPU 上，这也足够快了。
Depending on how densely this graphic is filled with pixels, you might be better off just searching outward from your pixel of origin.
I programmed something like this for a graphic terminal emulation. What I ended up doing was programming a search pattern in the shape of a square-sided spiral that grew out from the center point, and I let it grow until it hit something. That was sufficiently fast for the purpose, even on an old CPU.