1

我在有限的 2D 空间区域内有一组 2D 点（假设是一个世界对齐的矩形，以保持现在的简单）。将一个新点插入到与其新的最近邻居距离相对较大的集合中，什么是一种非常有效的方法？

我可以慢慢建立一个 Delaunay 三角剖分并将我的搜索限制在最大的三角形上，但我希望有人有不同的（更好的）想法。

善意，大卫

编辑：

忘了提到我需要这样做数千次，每次都要考虑到前面的所有要点。我正在寻找一种不会随着我的点集增长而减速到爬行的算法。

4

1 回答 1

3

使用 Bowyer-Watson 或其他增量算法来维护 Voronoi 图。Voronoi 图的顶点是候选点，将所有候选点按到源点的距离排序在一个优先级队列中。这应该非常快，并且是最佳的（至少在每一步都是最佳的）。

您是否正在寻找更快且不太理想的东西？

于 2009-11-09T01:09:14.563 回答