如何查询Voronoi图？

Question

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

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

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

当然，我们可以计算和比较给定点到现有点的距离，但这需要O(n)时间，而不使用Voronoi图中编码的信息。

Answer 1

“给定的点属于哪个站点？”是描述最近邻搜索问题的另一种方法:相关的Voronoi多边形是与生成Voronoi图的最近点相关联的多边形。不幸的是，

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

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

有一种方法可以构建基于Voronoi图( Delaunay层次结构)的搜索树。如果您还使用它来构建Voronoi图，它可能会提供一些次要福利。但是，没有像一般搜索问题那样容易获得的优化库。