如何从图表中获取Voronoi网站点

Question

假设我们从某处获得了一个沃罗诺伊图，但没有点。

像这样，但没有红色点： 我们只有边界。

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

并且如果我们有无限延伸的沃罗诺伊图。我们能够计算至少一个点吗？或者是否有任何启发式算法？

- Johnson

---

欢迎来到StackOverflow。然而，您的问题并没有遵循我们关于如何提出一个好问题的指南。首先，问题不够清晰。图表是如何给出的？请展示一个包含Voronoi图的数据结构的示例。其次，您没有展示自己的工作，看起来像是在把作业丢给我们。请告诉我们您在解决这个问题时所做的一些工作，最好包括代码，并告诉我们您卡在哪里了。 - Rory Daulton

https://mathoverflow.net/questions/257100/algorithm-for-reconstructing-point-sites-from-a-voronoi-diagram - RaffleBuffle

Rory Daulton所说的数据结构并不重要。问题是关于算法而不是实现等方面的。其次，谁倾倒什么？这是与学校无关的问题。我之前没有做任何事情，因为我不是数学家或类似的人。 - Johnson

SirRaffleBuffle 非常感谢你！ - Johnson

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个站点，那么你只能有一个沃罗诺伊交点。在这种情况下，你将无法确定你的站点 - 只能确定它们相对于交点的角度。

在所有其他一般情况下，你可以按照上述描述找到至少一个站点；通过沃罗诺伊边的反射，可以确定所有其他站点的位置，包括只有一个沃罗诺伊交点的极端单元格。

- comingstorm

Answer 2

这个问题由Ash和Bolker在1985年进行了调查并解决了一半。对于一个现代版本，它完善了早期的工作，可以参考这篇文章：

Biedl、Therese、Martin Held和Stefan Huber。"Recognizing straight skeletons and Voronoi diagrams and reconstructing their input." 在Voronoi Diagrams in Science and Engineering (ISVD) ，2013第10届国际研讨会上，第37-46页。 IEEE，2013。

(IEEE链接。)

---

         
          ^{(图片来自Stefan Huber。)}

---

- Joseph O'Rourke