Fortune算法中断点融合

StackOverflow https://stackoverflow.com//questions/9612065

题

我正在实施计算voronoi图的财富的Sweepline算法。我的主要参考是De Berg等人的“计算几何：算法和应用程序”，虽然他们对这个话题的覆盖率非常清楚，但他们通过了几个小但重要的细节，我一直遇到自己遇到麻烦。我已经搜索了Web寻求帮助，但其他网站要么提供比教科书更高的概述，或者给出了书提供的完全相同的伪代码。

我需要一种方法来确定一对断点是否由海滩线上的三个弧度决定，以便检测即将到来的圆事件。似乎是决定我需要了解voronoi细胞边的形状，即断点追踪作为财富的算法的进展。例如，如果我能找到由断点追踪的边缘的斜率，我可以计算出由断点和它们各自的斜率相交的两条线的位置，并决定它们是否基于该结果收敛。但是，我不知道如何在斜坡上获取信息，只有断点的当前位置。

我必须使用的唯一信息是三个站点的x，y位置和sweebline的当前y坐标（我正在使用水平的sweebline）。

实际上，我确实有一个确定收敛的想法。考虑到两个站点，它们定义的海滩线的两部分之间的断点仅受扫描线的当前位置的控制。我考虑过录制两个断点的位置，暂时推进扫描线少量，并记录其新位置。因为普通voronoi图中的边缘不曲线，因为新的一对断点之间的距离小于旧对之间的距离，则断点会聚;否则，他们分歧。但这似乎危险（我不知道它是否总是有效）和丑陋。当然必须有更好的方法。

任何想法都可以理解，并且伪代码（如果可能的C＃-like语法中）尤其如此。此外，我也知道，我可以使用的计算几何库来获取voronoi图表，但这是一个个人学习练习，所以我想自己实现算法的所有部分。

有帮助吗？

解决方案

欢迎德雷克。我通过检查断点是否物理地收敛于圆形中心的“虚拟”递增的SWEEPLINE位置。这实际上使自己复杂一些比特，因为在某些情况下，圆形中心几乎或精确地在Sweepline位置，因此SWEEPLE的增量需要与当前SWEEPLINE位置和根据您推荐时产生的圆中心之间的差异成比例。

说：

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。

我知道这可能是非常昂贵的，因为你必须多次计算断点位置，但我有信心照顾所有可能的情况。

无论如何，我在算法中其他地方的浮点精度错误找到了严重问题。绝对不像我最初的想法那么简单。

其他提示

所以这是相当尴尬的，但在睡觉之后答案答案似乎很明显。我正在写这一点，希望将来有着同样的问题。

两个站点之间的voronoi边缘垂直分二出来的（假想）线段连接站点。通过取垂直的连接线段的垂直垂直，可以通过垂直导出边缘的斜率，然后在两个边缘执行线路交叉测试，但是有甚至有更简单的方式。

只要三个站点是> Conlinear ，然后将垂直分化的边缘与位点之间的段分开的边缘也与边缘包含所有三个位点的圆圈相切。因此，如果三个站点定义的圆的中心位于中间站点前面的圆的中心，则由voronoi站点的三倍定义的断点会聚，其中“前面”和“后面”取决于坐标系统和Sweebline对齐您选择。

在我的情况下，我有一个水平的sweebline，我从最小y移动到最大y，因此如果圆的中心的Y坐标大于中间站点的Y坐标，则断点会聚，否则分歧。

编辑：克里斯蒂安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
.

如果站点围绕圆的中心顺时针排序，则电弧会聚。如果它们围绕圆的中心逆时针排序，则电弧会发散。（或反之亦然，具体取决于您的实现）。用于CW或CCW的测试从您用来找到圆的中心的代码中掉出来。

这是C＃代码的片段，用于计算点A，B，C：的Ciffenter D. 

        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 ;
.

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top