computational-geometry - voronoi 图的倒数

Question

我在 GIS 工作。我有一组多边形。我想做一个算法，首先检查多边形集是否是有效的 Voronoi 图。如果是，则返回可以生成相同 voronoi 图的点集。

任何人都可以帮助我如何去做

谢谢

Answer 1

这个SO 答案的简短摘要，它使用术语泰森多边形而不是 Voronoi 图：

Biedl 等人已经解决了这个问题， Recogning Straight Skeletons and Voronoi Diagrams and Reconstructing their Input，ISVD 2013。

对于某些特殊情况，这个问题更简单，但对于一般输入来说并不是那么微不足道。请注意，对于某些输入，可能有无限多个解，即具有相同 Voronoi 图的点集：

Biedl 等人的论文。提出了一种算法，该算法 (i) 检查多边形镶嵌是否是 Voronoi 图，并且 (ii) 确定 Voronoi 图等于镶嵌的所有可能点集。

基本思想如下：考虑 Voronoi 图的对偶的有根生成树，并不断将 Voronoi 节点处的局部限制传播到根 Voronoi 区域。这种限制的交集给出了所有可能的解决方案。

在其他SO 答案中查看更多详细信息。