Fortune 的算法和圆圈作为扫描线
Fortune's algorithm and circle as sweep line
我认为可以制定类似财富的算法，但使用圆而不是直线作为扫描线。
也就是说，“圈子事件”仍然是“圈子事件”，点事件定义会略有变化。
二叉树的实现也发生了变化，但变化很小。某种意义上变成了“二叉树mod2*pi”
原始算法措辞中的抛物线是椭圆，其中两个焦点之一从其准线移动到无穷大，依此类推。
根据圆和极坐标重新制定算法定义是否有任何障碍？它可以推广到更高的维度吗？
N.B.: 度量为 sqrt(x * x + y * y).
附加：
我试图从圆和位于圆内的点推断出等距点的方程。对于点 (a, 0) 和圆 center = (0, 0), radius = r，公式为 rho = (r * r - a * a) / (2 * (r - a * cos(theta)))。根据Wikipedia's article about ellipse，该推导方程的形式与相对于焦点的极坐标中的椭圆方程的形式相匹配。情节（略微扭曲）直观地证明了我的结论的正确性：
对于a == r（点位于海滩线上），此椭圆变成（退化为）线段或半径，类似于来自原始 Fortune 算法措辞的“点事件”的相应射线。
据我所知，有两篇论文描述了一种计算二维 Voronoi 图的扫描圆方法。第二个 "Parallel computing 2D VD..." 也显示了其实施的基准测试结果。不幸的是，如果您正在寻找类似这样的东西，则没有提供源代码 link。
我认为可以制定类似财富的算法，但使用圆而不是直线作为扫描线。
也就是说，“圈子事件”仍然是“圈子事件”，点事件定义会略有变化。
二叉树的实现也发生了变化，但变化很小。某种意义上变成了“二叉树mod2*pi”
原始算法措辞中的抛物线是椭圆，其中两个焦点之一从其准线移动到无穷大，依此类推。
根据圆和极坐标重新制定算法定义是否有任何障碍？它可以推广到更高的维度吗？
N.B.: 度量为 sqrt(x * x + y * y).
附加：
我试图从圆和位于圆内的点推断出等距点的方程。对于点 (a, 0) 和圆 center = (0, 0), radius = r，公式为 rho = (r * r - a * a) / (2 * (r - a * cos(theta)))。根据Wikipedia's article about ellipse，该推导方程的形式与相对于焦点的极坐标中的椭圆方程的形式相匹配。情节（略微扭曲）直观地证明了我的结论的正确性：
对于a == r（点位于海滩线上），此椭圆变成（退化为）线段或半径，类似于来自原始 Fortune 算法措辞的“点事件”的相应射线。
据我所知，有两篇论文描述了一种计算二维 Voronoi 图的扫描圆方法。第二个 "Parallel computing 2D VD..." 也显示了其实施的基准测试结果。不幸的是，如果您正在寻找类似这样的东西，则没有提供源代码 link。