Fortune算法中的断点收敛

Question

我正在实现计算Voronoi图的Fortune的甜线算法。我的主要参考文献是de Berg等人的“计算几何:算法和应用”，虽然他们对这个主题的覆盖非常清楚，但他们忽略了我自己一直难以解决的几个小但重要的细节。我在网上搜索过帮助，但其他网站要么给出了比教科书更高的概述，要么给出了书中提供的完全相同的伪代码。

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

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

实际上，我确实有一个确定收敛性的想法。给定两个站点，它们定义的海滩线的两个部分之间的断点仅由扫描线的当前位置控制。我想记录两个断点的位置，暂时将扫描线向前推进一点，然后记录它们的新位置。由于正常Voronoi图中的边不会弯曲，因此如果新断点对之间的距离小于旧断点对之间的距离，则断点收敛；否则，它们会发散。但这似乎既危险(我不知道它是否总是有效)，也很丑陋。当然，一定有更好的方法。

任何想法都会受到赞赏，尤其是伪代码(如果可能的话，使用类似C#的语法)。我还意识到有一些计算几何库可以用来获得Voronoi图，但这是一个个人学习练习，所以我想自己实现算法的所有部分。

Answer 1

欢迎德雷克。我通过检查断点是否在物理上收敛于圆的圆心，在一个“虚构的”甜线位置的增量上实现了它。这实际上有点复杂，因为在某些情况下，圆的中心可能几乎或精确地位于轮廓线位置，因此轮廓线的增量需要与当前轮廓线位置与您建议生成的圆中心之间的差成比例。

可以这样说：

1. currentSweeplineY = 1.0f；circleCenterY = 0.5f (我们正在向下移动，即沿y方向递减)。

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (可以任意选择10.0f除数)。

3. Check new breakpoint positions at new sweepline position。

4. Check distance to circle center。

5. If both distances are less than current distances, the breakpoints converge。

我知道这可能非常昂贵，因为您必须多次计算断点位置，但我相信它可以处理所有可能的情况。

无论如何，我在算法的其他地方发现了浮点精度错误的严重问题。绝对不像我一开始想的那么简单。

Answer 2

因此，这是相当尴尬的，但在考虑这个问题之后，答案似乎是显而易见的。我写这篇文章是希望对将来和我有同样问题的学生有所帮助。

两个站点之间的Voronoi边垂直等分连接两个站点的(虚构的)线段。您可以通过取连接线段的坡度的垂直度，然后在两条边上执行线相交测试来得出边的坡度，但还有一种更简单的方法。

只要有三个点是not collinear，那么将两个点之间的线段垂直平分的边也与包含这三个点的边的圆相切。因此，如果由三个站点定义的圆的中心位于中间站点的前面，则由三个Voronoi站点定义的断点会聚在一起，其中“前面”和“后面”取决于您选择的坐标系和轮廓线对齐。

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

编辑:克里斯蒂安·达马托正确地指出，上述算法遗漏了一些收敛情况。我最终使用的最终算法如下。当然，我不确定它是否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

Answer 3

如果这些点是围绕圆的中心顺时针排列的，则圆弧正在收敛。如果它们是围绕圆的中心逆时针排列的，那么圆弧是发散的。(反之亦然，具体取决于您的实现)。cw或ccw的测试不属于您用来查找圆心的代码。

以下是用于计算点a，b，c的外圆中心d的C#代码片段：

        Vector2 ba = b - a;
        Vector2 ca = c - a;     
        float baLength = (ba.x * ba.x) + (ba.y * ba.y);
        float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
        float denominator = 2f * (ba.x * ca.y - ba.y * ca.x);   
        if (denominator <= 0f ) { // Equals 0 for colinear points.  Less than zero if points are ccw and arc is diverging.
            return false;  // Don't use this circle event!
        };
        d.x = a.x + (ca.y * baLength - ba.y * caLength) / denominator ;
        d.y = a.y + (ba.x * caLength - ca.x * baLength) / denominator ;