如何从图表中获取Voronoi站点

Question

假设我们从某个地方得到了Voronoi图，但没有分数。

像这样但没有红点：

我们只有边界。

是否有任何算法可以帮助检索点？

---

如果我们拥有无限长的Voronoi图，那该怎么办？我们可以计算至少一个点还是有任何启发式算法？

Answer 1

对于Voronoi图的单个交叉点，通常在边缘之间有3个边和3个扇区。称行业（及其角度）A，B和C。此外，调用扇区A和B边缘ab之间的边缘，同样对边缘bc和ca。

每个部门都应该有一个原始站点;让网站a成为A部门的网站，b部门的B网站以及c部门的网站C。 请注意，扇区边界两侧的站点角度必须相等，因为从Voronoi边缘到每个站点的距离必须相等。例如，从位置a到边缘ab的角度必须与从边缘ab到位置b的角度相同;把这个角度称为X。同样地，让角度Y成为从b位置到bc边缘以及从bc到c位置的角度;和Z从c到ca，从ca到a的角度。

这给你方程式：

A = Z + X
B = X + Y
C = Y + Z

随着解决方案（简化因为A + B + C == 2 * pi）：

X = (A + B - C)/2 = pi - C
Y = (B + C - A)/2 = pi - A
Z = (C + A - B)/2 = pi - B

这将为您提供从任何Voronoi交叉口到其3个站点中的每个站点的光线。从邻近的Voronoi交叉路口到同一个小区站点的光线的交叉点将为您提供该站点的位置。

---

并且，回答你的第二个问题：如果你只有3个站点，那么你只能有一个Voronoi交叉口。在这种情况下，您将无法确定您的站点 - 只是它们与交叉点的角度。

在所有其他一般情况下，您可以找到至少一个如上所述的网站;然后，Voronoi边缘的反射应该确定所有其他站点的位置，包括只有一个Voronoi交叉点的极值单元。

Answer 2

Ash和Bolker在1985年对这个问题进行了调查和解决。对于完成早期工作的更现代的版本，请看：

Biedl，Therese，Martin Held和Stefan Huber。 “识别直骨架和Voronoi图并重建它们的输入。”在Voronoi Diagrams in Science and Engineering（ISVD），2013年第10届国际研讨会，第37-46页。 IEEE，2013。（IEEE link。）

---

         
          ^{(Image from Stefan Huber.)}

---