幸运算法中的断点收敛

Question

我正在实现Fortune的扫描线算法来计算Voronoi图。我主要参考了de Berg等人的《计算几何：算法与应用》，虽然他们对这个主题的覆盖非常清晰，但是他们忽略了一些小但重要的细节，这让我自己很难解决。我已经在网上寻求帮助，但其他网站要么比教科书提供的概述更高，要么给出与书本相同的伪代码。

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

我唯一可以使用的信息是三个点的x、y坐标和扫描线的当前y坐标（我正在使用水平扫描线）。

实际上，我对于确定收敛有一个想法。给定两个点，它们定义的海滩线之间的断点仅由扫描线的当前位置控制。我考虑记录两个断点的位置，暂时将扫描线向前移动一小段距离，并记录它们的新位置。因为正常Voronoi图中的边不会弯曲，所以如果新的一对断点之间的距离小于旧的一对断点之间的距离，则断点收敛；否则，它们发散。但这似乎既危险（我不知道它是否总是有效），又很丑陋。肯定有更好的方法。

任何想法都将不胜感激，尤其是伪代码（如果可能的话使用类似C#的语法）。我也意识到，有计算几何库可以用来获取Voronoi图，但这是个人的学习练习，所以我想自己实现算法的所有部分。

- Drake

---

你解决了Delaunay三角剖分问题吗？ - Micromega

不，这是我第一次尝试计算几何。我知道它们是对偶的，但我想先实现直接的Fortune算法。 - Drake

Answer 1

这有点尴尬，但问题在我睡觉后似乎变得很明显。我写这篇文章的目的是希望能够帮助未来遇到同样问题的学生。

两个站点之间的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

- Drake

---

我也有点烦恼，似乎没有人提供一种快速简便的检查收敛性的方法。你的问题（和答案）是一个很好的发现。但我认为有些情况是收敛的，而你描述的算法却无法捕捉到这些情况。这些情况是断点实际上向后移动（按照你定义的意义；与扫描线运动相反）。当三个站点从左到右排列，并且它们的抛物线弧以与之相反的方式出现时，就会发生这种情况；断点仍将在未来收敛，在海滩线下方。 - Kristian D'Amato

@KristianD'Amato感谢提醒我在这里的回答，我已经在帖子底部更新了我认为是正确的改进算法。 - Drake

基于KristianD'Amato的完整答案，我应该澄清一下，我的IsRightOfLine函数是针对特定坐标系和扫描线方向（具体来说，扫描线从大y到小y）而选择的，如果您为自己的实现调整该函数，您应该检查以确保它适用于您的坐标设置。 - Drake

Answer 2

如果网站围绕圆心按顺时针顺序排列，则弧收敛。如果它们围绕圆心按逆时针顺序排列，则弧发散。（或者反之，这取决于你的实现）。测试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 ;

- Brian Upton

---

这是唯一正确的答案。其他所有答案都只提供了太绕弯的解决方案。有了行列式值，我们还可以检测共线点的情况，这会导致平行边。 - Tomilov Anatoliy

@Orient 我对这背后的直觉感到困惑，可能是因为我还没有完全了解使用行列式方法计算外接圆的直觉。你能否解释一下？特别是，我不太确定顺时针和逆时针究竟意味着什么，并且有一些例子我不确定如何分类。 - mnoronha

@mnoronha 我吗？那是Brian Upton的回答。 - Tomilov Anatoliy

@Orient 好的。我之所以联系你是因为原作者不活跃了，而你在评论中似乎表明你理解了答案。 - mnoronha

@mnoronha，我觉得我无法比维基更好地解释。这里是我实现Fortune算法的代码。 - Tomilov Anatoliy

@Orient 不用担心。感谢您包含您的工作链接！ - mnoronha

Answer 3

欢迎，Drake。我通过检查断点是否在“虚构”的扫描线位置上物理收敛于圆心来实现它。但事实上，这会有点复杂，因为在某些情况下，圆心几乎或准确地位于扫描线位置，因此扫描线增量需要与您建议的当前扫描线位置和圆心之间的差成比例关系。

例如：

1. 当前扫描线Y值为1.0f；圆心Y值为0.5f（向下移动，即向减小的y方向移动）。

2. 设置sweepYIncrement =（circleCenterY-currentSweepLineY）/ 10.0f （10.0f除数是任意选择的）。

3. 在新的扫描线位置检查新的断点位置。

4. 检查到圆心的距离。

5. 如果两个距离都小于当前距离，则断点收敛。

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

不管怎样，在算法的其他部分，我发现了严重的浮点精度错误。显然不像我最初想象的那么简单。

- Kristian D'Amato

---

非常有趣。这更像是一种逻辑而非数学的方法，但仔细考虑后似乎应该可以实现。我认为算法的这一部分是单元测试的最佳选择。 - Drake