最接近给定点

Question

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

干杯.

Answer 1

不要忘记你不需要打扰平方根.

如果你只是想找到最近的一个(而不是它的实际距离),只需使用dx^2 + dy^2,这将给你每个项目的距离平方,这同样有用.

如果没有包含此像素列表的数据结构,则需要对它们进行全部测试.

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

Answer 2

我将不得不同意jk和Ewan制作Voronoi图表.这将分割多边形中的空间.K中的每个点都有一个多边形,描述最接近它的所有点.现在当你得到一个点的查询时,你需要找到它所在的多边形.这个问题称为点位置,可以通过构造梯形图来解决.

jk已经使用Fortune的算法链接到Voronoi图的创建,该算法采用O(n log n)计算步骤并且花费O(n)空间. 本网站向您展示如何制作梯形地图以及如何查询它.您还可以在那里找到一些边界:
预期创建时间:O(n log n)
预期空间复杂度:O(n)

但最重要的是,预期查询时间:O(log n).这(理论上)优于kD树的O(√n).

我的来源(上面的链接除外)是:计算几何:算法和应用程序,第六章和第七章.

在那里,您将找到有关这两种数据结构的详细信息(包括详细的证明).Google图书版仅包含您需要的部分内容,但其他链接应足以满足您的需求.如果你对这类东西感兴趣,那就买这本书(这是一本好书).

Answer 3

Voronoi Diagrams的构建是计算几何的一个分支.Delaunay三角测量的构造涉及类似的考虑.您可以调整以下Delaunay算法之一以满足您的需求.

• 翻转算法
• 增加的
• 分而治之
• 扫掠迹线

Answer 4

将点放在KD树中,在此之后找到最近的邻居非常快.有关详细信息,请参阅维基百科上的这篇文章

Answer 5

这称为最近邻搜索.唐纳德克努特称之为邮局问题.

有许多解决方案:线性搜索,局部敏感散列,矢量近似文件和空间分区.

谷歌搜索那些应该有所帮助.

Answer 6

你要做的是构造一个voronoi图,这可以使用平面扫描在O(n log n)中完成