algorithm - Fortune算法中的断点收敛

Question

我正在实现 Fortune 的扫掠线算法来计算 Voronoi 图。我的主要引用资料是 de Berg 等人的“计算几何:算法和应用”，虽然他们对该主题的介绍非常清楚，但他们忽略了一些我自己一直难以解决的小而重要的细节。我在网上搜索了帮助，但其他网站要么提供了比教科书更高的概述，要么提供了与本书提供的完全相同的伪代码。

我需要一种方法来确定由海滩线上的三重弧确定的一对断点是收敛还是发散，以便检测即将发生的圆圈事件。似乎要做出决定，我需要了解 Voronoi 单元边缘的形状，随着 Fortune 算法的进展，断点会追踪到这些边缘。例如，如果我能找到由断点追踪的边缘的斜率，我可以计算由断点和它们各自的斜率形成的两条线相交的位置，并根据该结果决定它们是否收敛。但是，我不知道如何获取斜坡上的信息，只知道断点的当前位置。

我唯一需要处理的信息是三个站点的 x、y 位置和扫掠线的当前 y 坐标(我使用的是水平扫掠线)。

其实，我确实有一个确定收敛的想法。给定两个站点，它们定义的海滩线的两个部分之间的断点仅由扫描线的当前位置控制。想着把两个断点的位置记录下来，把扫描线暂时往前推一点，记录下它们的新位置。因为普通 Voronoi 图的边不弯曲，如果新断点对之间的距离小于旧对断点之间的距离，则断点收敛；否则，他们就会分歧。但这看起来既危险(我不知道它是否总是有效)又丑陋。肯定有更好的方法。

我们将不胜感激任何想法，尤其是伪代码(如果可能，使用类似 C# 的语法)。我还知道可以使用计算几何库来获取 Voronoi 图，但这是个人学习练习，所以我想自己实现算法的所有部分。

Answer 1

所以这很尴尬，但在沉迷于这个问题之后，答案似乎显而易见。我写这篇文章是希望能帮助将来遇到与我相同问题的学生。

两个站点之间的 Voronoi 边垂直平分连接站点的(假想)线段。您可以通过取连接线段斜率的垂线，然后在两条边上进行直线相交测试来得出边的斜率，但还有更简单的方法。

只要三个站点都是not collinear , 那么垂直平分站点之间的线段的边缘也与边缘包含所有三个站点的圆相切。因此，如果由三个 Voronoi 站点定义的圆心位于中间 站点的前面，则由三重 Voronoi 站点定义的断点会收敛，其中“前面”和“后面”取决于坐标您选择的系统和扫掠线对齐。

在我的例子中，我有一条从最小 y 移动到最大 y 的水平扫掠线，因此如果圆心的 y 坐标大于中间站点的 y 坐标，则断点会收敛，否则发散。

编辑:Kristian D'Amato 正确地指出上述算法遗漏了一些收敛情况。我最终使用的最终算法如下。当然，我不确定它是否 100% 正确，但它似乎适用于我尝试过的所有情况。

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0