沃罗诺伊图的逆

Question

3

我从事地理信息系统方面的工作。我有一组多边形。我想编写一个算法，首先检查该多边形集是否是一个有效的Voronoi图。如果是，则返回可以生成相同Voronoi图的点集。

请问有谁能帮我实现吗？

谢谢。

- Shiva

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- S. Huber · Accepted Answer

这篇SO答案简要介绍了Thiessen多边形的概念，而不是Voronoi图：

Biedl等人在2013年的ISVD会议上发表了一篇文章Recognizing Straight Skeletons and Voronoi Diagrams and Reconstructing Their Input，解决了这个问题。

对于某些特殊情况，这个问题比较简单，但对于一般输入则并非易事。请注意，对于某些输入可能存在无限多个解，即具有相同Voronoi图的点集：

Many solutions

Biedl等人的论文介绍了一种算法，它能够（i）检查多边形镶嵌是否为Voronoi图，并且（ii）确定所有可能的点集，其Voronoi图等于该镶嵌。

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

更多细节请参见其他SO answer。