利用类Delaunay三角剖分实现Voronio图

1 引言计算几何在计算机辅助设计、计算机图形学(特别是三维图形生成技术)及机器人等领域是非常重要的。特别在近年来,受到了学术界的极大关注。Voronoi图是计算几何的一个重要分支。在气象、生态、空中交通管制、城市规划等领域都得到广泛应用。至今已发展了大量的实现Voronoi图的方法,发表了很多文章,基本上是基于连续域计算几何出发进行的,其计算方法主要分成两个类型:一个是增量算法,通过每次增加一个点来计算Voronoi图;另一种是分合算法,通过将点划分成两部分,递归计算每一部分点的Voronoi图,然后再将它们合并。