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