polygon - 如何查询 Voronoi 图？

Question

我boost用来计算二维中一组点的 voronoi 图，非常简单；

std::vector<Point> points;
...
voronoi_diagram<double> vd;
construct_voronoi(points.begin(), points.end(), &vd);

是否有一种算法来处理生成的多边形，以便查询“给定点属于哪个站点？” 可以在恒定时间内回答吗？换句话说，给定点位于一组多边形中的哪个多边形中？

当然，可以计算并比较给定点与现有点的距离，但这将花费 O(n) 时间并且不利用 Voronoi 图中编码的信息。

标签： polygonvoronoiboost-polygon

Answer 1

问题“给定点属于哪个站点？” 只是说明最近邻搜索问题的另一种方式：相关的 Voronoi 多边形是与生成 Voronoi 图的集合中的最近点相关联的多边形。很遗憾，

• 没有任何恒定时间算法可以解决这个问题，并且
• Voronoi 图没有比 O(N) 搜索更快地解决问题。

如果需要在 Voronoi 图中定位很多点，可以构建搜索树，通常可以获得 O(log N) 的性能。这个问题的答案是在 python 中构建一个kd 树来进行查询。在 boost 中，您可以为此目的使用现有的R-tree 。

有一种方法可以基于 Voronoi 图（Delaunay 层次结构）构建搜索树。如果您也使用它来构建 Voronoi 图，它可能会提供一些小好处。但是没有像通用搜索问题那样容易获得的优化库。