Voronoi:使用Fortune算法计算voronoi图的Swift框架-源码

沃罗诺伊 使用Fortune算法计算voronoi图的Swift框架。 使用VoronoiDiagram类可计算voronoi图的像元。 Voronoi图是将给定点之间的线一分为二的边。 单元中的每个点比任何其他voronoi点都更靠近该单元的voronoi点。 位于两个像元边缘的点与两个voronoi点等距。 财富算法 财富算法是一种在O(n log(n))时间内求解voronoi图的方法。 它只需要在每个voronoi点处以及在三个voronoi点所形成的可能圆上发生事件（发生在O(n)时间），并且还需要在每个站点事件（发生在O(log(n))时间。 Fortune的算法使用海滩线（由给定x坐标处的抛物线的最小值形成的分段曲线）和扫掠线（与抛物线的方向线相对应的水平线）。 每个voronoi点对应于抛物线的焦点，扫掠线对应于准线。 抛物线可以定义为焦点（点）和方向（线）。 抛物线