22
我在2D图像中随机选择了一组像素。对于图像中的每个其他像素，我需要找出集合K中的哪个像素最接近它（使用标准的sqrt（dx^2 + dy^2）度量距离）。我知道每个像素可能有多个解决方案。显然，它可以通过强制对抗集合中的每个像素来完成，但是我宁愿避免这一点，因为它效率不高。任何其他好建议？给定点的最近点
干杯。
Q
给定点的最近点
A
回答
31
不要忘记，你不需要打扰平方根。
如果你只是想找到最近的一个（而不是实际距离），只需使用dx^2 + dy^2，它会给你每个项目的距离平方，这是一样有用。
如果你没有数据结构包装这个像素列表，你只需要对它们进行测试。
如果您有一定的灵活性，有许多减少工作量的好方法。制作一个Quadtree，或保留像素的排序列表（按x排序并按y排序），以便更快地缩小搜索范围。
5
这被称为最近邻搜索。唐纳德克努特称之为邮局问题。
有许多解决方案：线性搜索，局部敏感哈希，矢量近似文件和空间分区。
谷歌搜索这些应该帮助。
1
取决于此图形填充像素的密度如何，最好从原始像素向外搜索。
我编写了类似于图形终端仿真的东西。我最终做的是编制一个从中心点出现的方形螺旋形状的搜索模式，然后让它增长直到碰到什么东西。即使在旧的CPU上，这也足够快。
+0
对于单点来说，我的算法“足够好”。对于整个队伍来说，Voronoi听起来像是一个赢家。我会收回我的答案，除了一些未来的读者可能有单点要求。 – 2009-12-14 17:47:19
4
另一个提示：距离总是大于或等于每一个坐标差，始终小于或等于它们的总和，即
d >= dx, d >= dy, d <= dx + dy.
这可以帮助你做的排序效率更高。
5
你正在试图做的是建立一个voronoi diagram这可以在O进行使用plane sweep
7
（N日志N）的Voronoi Diagrams建设是Computational Geometry一个分支。 Delaunay Triangulations的构建涉及类似的考虑。您可以根据需要调整以下Delaunay algorithms之一。
- 翻转算法
- 增量
- 分而治之
- 扫掠迹线
6
把点的KD树，这是非常快的找到最近的邻居后。有关详细信息，请参阅维基百科上的this文章。
14
我将不得不同意jk和Ewan制作Voronoi Diagram。这将分割多边形中的空间。 K中的每个点都有一个多边形，描述了与其最接近的所有点。 现在当你得到一个点的查询时，你需要找到它所在的多边形。这个问题被称为Point Location，可以通过构建一个Trapezoidal Map来解决。
jk已经链接到使用Fortune's algorithm的Voronoi Diagram的创建，这需要O（n log n）个计算步骤和成本O（n）空间。 This website向您显示如何制作梯形图以及如何查询它。您还可以找到一些界限有：
预计创建时间：为O（n log n）的
预期的空间复杂度：O（n）的
但最重要的，预计查询时间：O（log n）的。这（理论上）比kD树的O（√n）更好。
我的来源（除了上面的链接）是：Computational Geometry: algorithms and applications，第六和第七章。
在那里你会找到关于两个数据结构的详细信息（包括详细的证明）。 Google图书版本只包含您需要的部分内容，但其他链接应该足以满足您的需求。如果你对这样的事情感兴趣，就买这本书吧（这本书是一本好书）。
好想法！对于大型数据集，这会极大地减少运行时间。 – 2009-12-14 14:18:28
既然你在处理像素，这也意味着你可以下降到整数数学，这是另一个巨大的速度奖金 – 2009-12-14 14:21:53
@rikh即使你确实需要距离，一旦你知道哪个点是最近的。 – 2009-12-14 14:22:17