我在 2D 图像中有一组随机选择的像素 K。对于图像中的每个其他像素，我需要找出 K 集中的哪个像素最接近它（使用标准的 sqrt(dx^2 + dy^2) 距离度量）。我知道每个像素可能有多个解决方案。显然，它可以通过对集合中的每个像素的蛮力来完成，但我宁愿避免这样做，因为它效率不高。还有什么好的建议吗？
干杯。
问问题
32762 次
8 回答
40
不要忘记您不需要为平方根而烦恼。
如果您只想找到最近的一个（而不是实际距离），只需使用dx^2 + dy^2，这将为您提供与每个项目的距离平方，这同样有用。
如果您没有将这个像素列表包装起来的数据结构，您将只需要针对它们进行测试。
如果你有一定的灵活性，有很多很好的方法可以减少工作量。制作四叉树，或保留像素的排序列表（按 x 排序并按 y 排序）以更快地缩小搜索范围。
于 2009-12-14T14:15:39.563 回答
21
我将不得不同意 jk 和 Ewan 制作Voronoi 图。这会将空间划分为多边形。K 中的每个点都会有一个多边形来描述最接近它的所有点。现在，当您查询某个点时，您需要找到它位于哪个多边形中。这个问题称为点定位，可以通过构建梯形图来解决。
jk 已经与使用Fortune 算法创建Voronoi 图相关联，该算法采用 O(n log n) 计算步骤并花费 O(n) 空间。
本网站向您展示如何制作梯形地图以及如何查询。您还可以在那里找到一些界限：
预期创建时间：O(n log n)
预期空间复杂度：O(n)
但最重要的是，预期的查询时间：O(log n)。这（理论上）比 kD-tree 的 O(√n) 更好。
我的来源（除了上面的链接）是：计算几何：算法和应用，第六章和第七章。
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).
于 2009-12-14T16:21:38.420 回答
7
Voronoi 图的构建是计算几何的一个分支。Delaunay三角剖分的构建涉及类似的考虑。您可以调整以下Delaunay 算法之一以满足您的需求。
- 翻转算法
- 增加的
- 分而治之
- 扫描线
于 2009-12-14T14:24:18.207 回答
7
将这些点放在KD树中，在此之后找到最近的邻居非常快。有关详细信息，请参阅维基百科上的这篇文章。
于 2009-12-14T14:24:52.137 回答
6
这称为最近邻搜索。Donald Knuth 称之为邮局问题。
有许多解决方案：线性搜索、局部敏感散列、向量近似文件和空间分区。
谷歌搜索这些应该会有所帮助。
于 2009-12-14T14:15:37.677 回答
5
您要做的是构建一个voronoi 图，这可以使用平面扫描在 O(n log n) 中完成
于 2009-12-14T14:16:43.057 回答
4
另一个提示：距离总是大于等于每个坐标差，并且总是小于等于它们的和，即
d >= dx, d >= dy, d <= dx + dy.
这可能会帮助您更有效地进行排序。
于 2009-12-14T14:16:32.483 回答
2
根据该图形填充像素的密集程度，您最好从原始像素向外搜索。
我为图形终端仿真编写了类似的程序。我最终做的是编写一个从中心点长出来的方形螺旋形状的搜索模式，我让它一直增长直到它碰到什么东西。即使在旧 CPU 上，这也足够快。
于 2009-12-14T14:16:01.767 回答