最近邻区域可视化

Question

我正在编写一个应用程序，它使用k-d树在二维空间中查找点。在开发过程中，能够“看到”每一个点周围最近的邻居区域是很好的。

在所附的图像中，红色点是k-d树中的点，围绕每个点的蓝线是最近邻搜索返回包含点的区域。

这个图像是这样创建的：

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

该算法有两个问题：

• 更重要的是，它在我的(相当快的核心i7)计算机上是缓慢的。
• (不太重要)这是草率的，你可以从不同宽度的蓝线中看到。

所谓的一组点的“可视化”是什么？

创建这样一个可视化的好算法是什么？

​

​

Answer 1

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

希望这能有所帮助！

Answer 2

雅各布

嘿，你找到了一种有趣的方法来生成Voronoi图，尽管它不是很有效。

第一个不太重要的问题是:你得到的不同厚度的边界，那些蝴蝶形状，实际上是双曲线的两个分支之间的区域。精确的双曲线由方程_~_

更重要的问题是:构造一组点的Voronoi图有两种著名的有效解决方案：“财富”的扫描算法(如Templatety胡枝子所提到的)和制剂和Shamos的Divide & Conquer解。这两种方法都在最佳时间O(N.Lg(N))中对N个点运行，但不太容易实现。

这些算法将Voronoi图构造成一组线段和半直线.检查图解。

本文“用于操作一般细分和计算Voronoi的基元”使用一个较高层次的框架描述了这两种算法，关注所有的实现细节；这篇文章很难，但算法是可实现的。

您也可以看看“平面Voronoi图的直接迭代算法”，这是我从未尝试过的。

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

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

Answer 3

从个人经验来看：“财富”的算法很难实现。Guibas和Stolfi提出的分而治之算法还不错，它们提供了详细的伪代码，很容易转换成过程编程语言。如果你有几乎退化的输入并且使用浮点，两者都会爆炸，但是由于原语是二次型的，如果你可以用32位整数表示坐标，那么你可以用64位来执行行列式计算。

一旦你开始工作，你可能会考虑用平面细分算法代替kd-树算法，它的最坏情况是Theta(√n)。