6

我正在编写一个使用kd 树在二维空间中查找点的应用程序。在开发过程中，如果能够“看到”每个点周围的最近邻区，那就太好了。

在附图中，红点是 kd 树中的点，围绕每个点的蓝线界定了最近邻搜索将返回包含点的区域。

图像是这样创建的：

for each point in the space:
  da = distance to nearest neighbor
  db = distance to second-nearest neighbor
  if absolute_value(da - db) < 4:
    draw blue pixel

这个算法有两个问题：

  • （更重要的是）我的（相当快的Core i7）计算机上它很慢。
  • （不太重要）它很草率，你可以从不同宽度的蓝线看出。

一组点的这种“可视化”叫什么？

有哪些好的算法可以创建这样的可视化？

分区

4

4 回答 4

7

这被称为Voronoi 图，有许多优秀的算法可以有效地生成它们。我听说最多的是Fortune 的算法，它在 O(n log n) 时间内运行，尽管存在其他算法来解决这个问题。

希望这可以帮助！

于 2012-02-15T06:39:02.150 回答
4

雅各布，

嘿，您发现了一种有趣的方式来生成这个 Voronoi 图，尽管它不是那么有效。

首先是不太重要的问题：你得到的不同厚度的边界，那些蝴蝶形状，实际上是双曲线的两个分支之间的区域。正是方程 |da - db| 给出的双曲线 = 4. 要获得一条粗线，您必须修改此标准并将其替换为到两个最近邻居的平分线的距离，让 A 和 B；使用向量微积分，| PA.AB/||AB|| - ||AB||/2 | < 4。

更重要的问题：构建一组点的 Voronoi 图有两种众所周知的有效解决方案：Fortune 的扫描算法（如 templatetypedef 所述）和 Preparata & Shamos 的分治解决方案。两者都在 N 个点的最佳时间 O(N.Lg(N)) 中运行，但实现起来并不容易。

这些算法将 Voronoi 图构建为一组线段和半线。检查http://en.wikipedia.org/wiki/Voronoi_diagram。

这篇论文“Primitives for the operation of general subdivisions and the computing of Voronoi”描述了这两种算法，使用了一个有点高级的框架，关心所有的实现细节；这篇文章很难，但算法是可以实现的。

您还可以查看我从未尝试过的“平面 Voronoi 图的简单迭代算法”。

一种完全不同的方法是直接从给定点构建距离图，例如通过 Dijkstra 算法：从给定点开始，在距每个点的给定距离内增长区域的边界，当两个边界时停止增长遇见。[需要更多解释。] 请参阅http://1.bp.blogspot.com/-O6rXggLa9fE/TnAwz4f9hXI/AAAAAAAAAPk/0vrqEKRPVIw/s1600/distmap-20-seed4-fin.jpg

另一个好的起点（用于有效计算距离图）可以是“用于计算线性时间距离变换的通用算法”。

于 2012-02-15T08:16:47.340 回答
2

从个人经验来看：Fortune 的算法实施起来很痛苦。Guibas 和 Stolfi 提出的分治算法还不错。他们提供了详细的伪代码，这些伪代码很容易转录成过程编程语言。如果您有几乎退化的输入并使用浮点，两者都会爆炸，但由于基元是二次的，如果您可以将坐标表示为 32 位整数，那么您可以使用 64 位来执行行列式计算。

一旦你让它工作，你可能会考虑用在平面细分上工作的算法替换你的 kd-tree 算法，它有一个 Theta(√n) 最坏的情况。

于 2012-02-15T12:54:10.187 回答
1

你可以在 D3.js 库中找到一个很好的实现：http: //mbostock.github.com/d3/ex/voronoi.html

于 2012-02-15T18:27:14.233 回答