如何查询Voronoi图？ [英] How to query a Voronoi diagram?

问题描述

我正在使用boost计算二维中一组点的Voronoi图，非常简单；

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

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

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

Voronoi

问题&推荐答案属于哪个站点？只是nearest neighbor search问题的另一种表述方式：相关的Voronoi多边形与生成Voronoi图的集合中最近的点相关联。不幸的是，

• 没有解决这个问题的固定时间算法，
• Voronoi图没有提供比O(N)搜索更快的解决问题的方法。

如果您需要在Voronoi图中定位许多点，您可以构建一棵搜索树，通常得到O(LogN)的性能。this question上的答案在构建一个k-d tree来执行查询时是这样做的。在Boost中，您可以使用现有的R-tree用于此目的。

有一种方法可以基于Voronoi图(Delaunay hierarchy)构建搜索树。如果您也使用它来构建Voronoi图，它可能会提供一些minor benefits。但没有像通用搜索问题那样容易获得的优化库。

这篇关于如何查询Voronoi图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！