我有一个在2D图像中随机选择的像素集合K。对于图像中的每个其他像素，我需要找出离它最近的集合K中的像素（使用标准的sqrt(dx^2 + dy^2)距离测量）。我知道对于每个像素可能会有多个解。显然可以通过对集合中的每个像素进行暴力搜索来完成，但我更愿意避免这种方式，因为效率不高。有什么好的建议吗？
谢谢。
8个回答
43
不要忘记，您无需费心计算平方根。
如果您只想找到最近的一个（而不是它的实际距离），只需使用dx^2 + dy^2，这将给出到每个项目的距离的平方，这同样有用。
如果您没有数据结构包裹这个像素列表，您需要对它们进行全部测试。
如果您有一些灵活性，有很多好方法可以减少工作量。制作一个四叉树，或者保持像素的排序列表（按x排序和按y排序）以更快地缩小搜索范围。
- Rik Heywood
4
好想法！对于大型数据集，这将极大地减少运行时间。 - San Jacinto
2由于您正在处理像素，这也意味着您可以转换为整数运算，这是另一个巨大的速度优势。 - Rik Heywood
11即使你需要计算距离，也可以在确定最近的点之后使用“sqrt”。 - Andreas Brinck
将四叉树推广到 n 维向量上进行搜索是一个好主意吗？ - Shashwat
21
我同意 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图书版本仅有部分您需要的信息，但其他链接应该足以满足您的目的。如果您对此类事情感兴趣，就买本书吧（这是一本好书）。
- Matthijs Wessels
7
这被称为最近邻搜索。Donald Knuth 称之为邮局问题。
有许多解决方案：线性搜索、局部敏感哈希、向量逼近文件和空间划分。
通过谷歌搜索这些内容应该会有所帮助。
- Paul
4
另一个提示：距离始终大于或等于每个坐标差，且始终小于或等于它们的总和，即
d >= dx, d >= dy, d <= dx + dy.
这可能有助于您更有效地进行排序。
- balpha
3
根据图形像素的密度，您可能最好从起始像素向外搜索。
我曾为一个图形终端仿真编写过类似的程序。我最终编写了一个以正方形螺旋形状为搜索模式的算法，从中心点开始扩展，并让它不断扩大，直到碰到障碍物为止。即使在旧CPU上，这种方法也足够快速地实现了目的。
- Carl Smotricz
1
1对于单个点，我的算法“足够好”。对于一堆点，Voronoi听起来像是一个赢家。我会撤回我的答案，但一些未来的读者可能有单个点的要求。 - Carl Smotricz
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接