最近邻区域可视化

Question

我正在编写一个使用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)计算机速度很慢.
• (不太重要)它很草率,正如你可以看到蓝线的不同宽度.

什么是一组点的"可视化"？

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

Answer 1

这被称为Voronoi图,并且有许多优秀的算法可以有效地生成它们.我最常听到的是Fortune的算法,该算法在时间O(n log n)内运行,尽管存在其他算法用于此问题.

希望这可以帮助!