论文部分内容阅读
Voronoi图是计算几何中的一种重要几何结构,也是计算几何的重要研究内容之一,如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法,但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法,时间复杂度为O(nlogn),但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图,提出了一种改进的Voronoi图增量构造算法,该算法是通过对已有的生成Voronoi图的增量法进行分析,并结合它们的优点,采用扫描线的方式,通过右