将点插入到与现有点的最大距离的有限二维区域中
我在有限的 2D 空间区域内有一组 2D 点（为了让事情简单起见，假设有一个与世界对齐的矩形）。将一个新点插入到与其新的最近邻居有相对较大距离的集合中的极其有效的方法是什么？
我可以慢慢地构建一个 Delaunay 三角剖分，并将我的搜索限制为最大的三角形，但我希望有人有不同的（更好的）想法。
善意， 大卫
编辑：
忘了提及，我需要这样做数千次，每次都考虑到前面的所有要点。我正在寻找一种算法，它不会随着我的点集的增长而减慢速度。
I have a set of 2D points inside a finite 2D region of space (let's say a world-aligned rectangle to keep things simple for now). What would be an exceedingly efficient way to insert a new point into the set that has a relatively large distance to its new closest neighbour?
I could slowly build a Delaunay triangulation and limit my search to the largest triangles only, but I was hoping someone has a different (better) idea.
Goodwill,
David
Edit:
Forgot to mention that I need to do this thousands of times, every time taking all the previous points into account. I'm looking for an algorithm that doesn't slow down to a crawl as my point set grows.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
使用 Bowyer-Watson 或其他增量算法来维护 Voronoi 图。 Voronoi 图的顶点是候选点，将所有候选点按照到源点的距离排序保留在优先级队列中。这应该是非常快的，并且是最优的（至少在每一步都是最优的）。
您是否在寻找更快但不太理想的东西？
Use the Bowyer-Watson or other incremental algorithm to maintain the Voronoi diagram. The vertexes of the Voronoi diagram are candidate points, keep all the candidate points in a priority queue ordered by distance to the source points. That should be pretty fast, and optimal (at least, optimal at each step).
Were you looking for something faster and less optimal?