基于合成算法的Delaunay三角网生成改进算法
2011-02-10潘丽丽孙玉秋
长江大学学报(自科版) 2011年1期
潘丽丽,孙玉秋
(长江大学信息与数学学院,湖北荆州434023)
不规则三角网能够精确的表示复杂的地形。Delaunay三角网因其在所有可能的三角网中表现最为出色而被用于不规则三角网的生成。被人们广泛采用的Delaunay三角网生成算法有分治法与逐点插入法,这2种算法各有优劣,随之出现了综合2种算法的合成算法。合成算法虽然提高了执行效率,但并没有很好的解决其中的一些 “瓶颈”问题。因此,如何改进现有算法从而提高算法的执行效率成为必须要解决的另一个问题。为此,笔者基于合成算法对子模块中的关键步骤进行改进,提高算法的性能,简化算法的实现。
1 基本概念及性质
Voronoi图 (以下简称V图),又叫泰森多边形或Dirichlet图,它是由一组连接两邻点直线的垂直平分线组成的连续多边形。N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角网是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Voronoi三角网是Delaunay图的偶图。
性质1(空外接圆性质) 在由点集V生成的Delaunay三角网中,每个三角网的外接圆均不包含该点集的其他任意点。
性质2(最大最小角度性质) 在由点集V生成的Delaunay三角网中,所有三角形中的最小角度是最大的,即在生成的三角形网格中,各三角形的最小内角和为最大。
性质3(唯一性) 不论从区域何处开始构网,最终都将得到一致的结果。
