如何从图中获取 Voronoi 站点点

Question

假设我们从某处获得了一张 Voronoi 图，但没有点。

像这样但没有红点：

我们只有边界。

有什么算法可以帮助检索积分吗？

---

如果我们有无限延伸的 Voronoi 图怎么办？我们可以至少计算一个点吗？或者是否有任何启发式算法？

Answer 1

对于 Voronoi 图的单个交集，通常有 3 条边，边之间有 3 个扇区。将这些扇区（及其角度）称为A、B、 和C。另外，将扇区之间的边A和B边称为 ，边和ab也同样如此。bcca

每个扇区内都应该有一个原始站点点；设站点a为扇区中的站点A、b扇区中的站点B和c扇区中的站点C。 请注意，扇区边界两侧站点的角度必须相等，因为从 Voronoi 边到每个站点的距离必须相等。例如，从站点a到边缘的角度必须与从边缘到站点的ab角度相同；称这个角为。同样，让角度为从站点到边缘以及从站点到站点的角度；以及从到和从到 的角度abbXYbbcbccZccacaa。

这给出了方程：

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 交叉点的极值单元。