Dra*_*ake 9 algorithm voronoi breakpoints computational-geometry
我正在实施Fortune的扫描线算法来计算Voronoi图.我的主要参考文献是de Berg等人的"计算几何:算法和应用",虽然他们对这个主题的报道非常清楚,但他们传递了一些我自己一直无法解决的小而重要的细节.我在网上寻求帮助,但其他网站要么比教科书提供更高的概述,要么提供本书提供的完全相同的伪代码.
我需要一种方法来确定由海滩线上的三个弧确定的一对断点是否收敛或发散,以便检测即将到来的圆周事件.似乎要做出决定,我需要了解Voronoi单元边缘的形状,断点随着Fortune算法的进展而逐渐显现出来.例如,如果我能找到断点跟踪的边的斜率,我可以计算断点形成的两条线的位置和它们各自的斜率相交,并根据该结果确定它们是否收敛.但是,我不知道如何获得斜坡上的信息,只知道断点的当前位置.
我必须处理的唯一信息是三个站点的x,y位置和扫描线的当前y坐标(我使用的是水平扫描线).
实际上,我确实有一个确定收敛的想法.给定两个站点,他们定义的海滩线的两个部分之间的断点仅由扫描线的当前位置控制.我考虑记录两个断点的位置,暂时推进扫描线少量,并记录他们的新位置.因为正常Voronoi图中的边不会弯曲,如果新断点之间的距离小于旧对之间的距离,则断点会聚; 否则,他们分歧.但这似乎既危险(我不知道它是否总是有效)和丑陋.当然必须有更好的方法.
任何想法都会受到赞赏,并且伪代码(如果可能的话,使用类似C#的语法)尤其如此.另外我知道有一些计算几何库可以用来获取Voronoi图,但这是一个个人学习练习,所以我想自己实现算法的所有部分.
所以这是相当令人尴尬的,但在解决问题后,答案似乎很明显.我写这篇文章是为了希望将来能像我一样帮助学生.
两个站点之间的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
欢迎德雷克。我通过检查断点是否以扫掠线位置的“虚拟”增量物理地收敛于圆心来实现它。这实际上有点复杂，因为在某些情况下，圆心可以几乎或精确地位于扫描线位置，因此扫描线增量需要与当前扫描线位置和按照您建议生成的圆心之间的差值成正比。
说：
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。
我知道这可能非常昂贵，因为您必须多次计算断点位置，但我相信它会处理所有可能的情况。
不管怎样，我在算法的其他地方发现了浮点精度误差的严重问题。绝对不像我最初想象的那么简单。