有了最终的泰森多边形，是否有可能找到初始点集？
Having the final Thiessen polygons, is it possible to find the initial set of points?
我正在寻找一种方法来反转 Voronoi 算法。
基本上，有一些主要由三角形和正方形组成的连接形状，我试图找到一组点，通过使用 Voronoi 算法可以重新创建初始形状。
找到每个三角形的质心不会给你一个根据定义尽可能远离其他点的点。
简介。
在 1985 年 Ash 和 Boker 的部分解决方案之后，Biedl et al. 在 2013 年的一篇论文中解决了这个问题。如果您的 Voronoi 节点都是奇数度，那么 Ash 和 Bolker 的算法适用于您。
首先请注意，可能没有 the 点集，但 many 点集都具有您要求的相同 Voronoi 图.例如，考虑这张图片
取自this website. The red point set and the blue point set give you the same black Voronoi diagram. (And, by the way, the straight skeletons的红色和蓝色多边形也与点集的Voronoi图一致。）
算法概述。
大致思路如下。假设神谕告诉您 Voronoi 单元中的一个候选点。然后你可以通过相邻单元之间的公共边将这个点镜像到相邻的Voronoi单元，并继续传播。
但可能会有麻烦：镜像点可能位于相邻单元格之外。此外，如果您考虑一个 Voronoi 节点和入射单元，那么您可以通过入射 Voronoi 边缘围绕一个周期继续传播该点，但您可能不会再次到达原始点。
所以论文的内容如下：
给出了你的输入形成Voronoi图的充分必要条件
它告诉你如何选择一个有效的起始点（如果存在这样的点）。实际上，它为您提供了一组所有可能的起点。
第二部分的工作原理大致如下：对于每个 Voronoi 单元，可以通过调查单元的 Voronoi 节点知道 "region" 点所在的位置。然后取Voronoi图的对偶图的生成树并选择任意根。对于每个单元格，您都有一个唯一的 "mirroring path" 到 "root cell"。应用上述区域的镜像序列并将镜像相交。
交点是所有可能起点的集合。如果它是空的，那么你的输入不是 Voronoi 图。
进一步简化。
如果您的 Voronoi 节点的度数为奇数，那么问题就简单多了。考虑 Biedl 等人的论文中的图 4。为每个节点找出点必须位于的线。如果 Voronoi 单元有两个奇数节点，那么您可以将这些线相交并获得单个可能的候选点。您可以对每个 Voronoi 单元执行此操作。
我正在寻找一种方法来反转 Voronoi 算法。
基本上，有一些主要由三角形和正方形组成的连接形状，我试图找到一组点，通过使用 Voronoi 算法可以重新创建初始形状。
找到每个三角形的质心不会给你一个根据定义尽可能远离其他点的点。
简介。 在 1985 年 Ash 和 Boker 的部分解决方案之后，Biedl et al. 在 2013 年的一篇论文中解决了这个问题。如果您的 Voronoi 节点都是奇数度，那么 Ash 和 Bolker 的算法适用于您。
首先请注意，可能没有 the 点集，但 many 点集都具有您要求的相同 Voronoi 图.例如，考虑这张图片
取自this website. The red point set and the blue point set give you the same black Voronoi diagram. (And, by the way, the straight skeletons的红色和蓝色多边形也与点集的Voronoi图一致。）
算法概述。 大致思路如下。假设神谕告诉您 Voronoi 单元中的一个候选点。然后你可以通过相邻单元之间的公共边将这个点镜像到相邻的Voronoi单元，并继续传播。
但可能会有麻烦：镜像点可能位于相邻单元格之外。此外，如果您考虑一个 Voronoi 节点和入射单元，那么您可以通过入射 Voronoi 边缘围绕一个周期继续传播该点，但您可能不会再次到达原始点。
所以论文的内容如下：
给出了你的输入形成Voronoi图的充分必要条件
它告诉你如何选择一个有效的起始点（如果存在这样的点）。实际上，它为您提供了一组所有可能的起点。
第二部分的工作原理大致如下：对于每个 Voronoi 单元，可以通过调查单元的 Voronoi 节点知道 "region" 点所在的位置。然后取Voronoi图的对偶图的生成树并选择任意根。对于每个单元格，您都有一个唯一的 "mirroring path" 到 "root cell"。应用上述区域的镜像序列并将镜像相交。
交点是所有可能起点的集合。如果它是空的，那么你的输入不是 Voronoi 图。
进一步简化。 如果您的 Voronoi 节点的度数为奇数，那么问题就简单多了。考虑 Biedl 等人的论文中的图 4。为每个节点找出点必须位于的线。如果 Voronoi 单元有两个奇数节点，那么您可以将这些线相交并获得单个可能的候选点。您可以对每个 Voronoi 单元执行此操作。