9

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

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

我必须使用的唯一信息是三个站点的 x、y 位置和扫描线的当前 y 坐标（我使用的是水平扫描线）。

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

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

4

3 回答 3

7

所以这很尴尬，但是在解决这个问题之后，答案似乎很明显。我写这篇文章是为了希望能帮助将来有和我一样的问题的学生。

两个站点之间的 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
于 2012-03-08T16:11:29.953 回答
2

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

说：

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.

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

无论如何，我在算法的其他地方发现了浮点精度错误的严重问题。绝对没有我最初想的那么简单。

于 2013-06-17T08:51:27.653 回答
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 ;
于 2015-01-10T23:03:25.230 回答