平面点集Delaunay三角剖分的分治算法
2012-07-25谢增广
计算机工程与设计 2012年7期
谢增广
(华北计算技术研究所,北京100083)
0 引 言
三角剖分是计算几何中领域的重要课题之一。平面点集Delaunay三角剖分与该点集的Voronoi图是对偶图,具有许多优良性质,在图形网格化技术领域有着广泛应用。三角剖分算法理论研究已经相当成熟,已经能够证明算法时间复杂度的上界和下界[1],然而由于区域拓扑划分问题,算法在实际工程中应用的难易程度有所不同。根据实现过程,Delaunay三角剖分的算法可以分为逐点插入法、三角网生长法,分治算法等,其中分治算法最适合实际工程应用。
论文引入了一种数据结构——双链接边表 (doublyconnected edge list,DCEL),利用该数据结构可以方便地对平面区域进行划分;引入了3个工具算法,简化了Delaunay三角剖分算法分治的实现过程;另外对特殊退化情况进行分类处理,增强了该算法的实用性。
1 算法设计与实现
1.1 数据结构
双链接 边 表 (doubly-connected edge,DCEL)[4-5]是 用来表示平面图拓扑信息的一种数据结构,如图1所示。
在DCEL中,将每条边的两端分别作为一条半边。半边有方向性,由起点出发,指向另一个端点。一条边的两条半边互为孪生半边。
DCEL由三组记录构成,分别存储顶点、面、半边的信息。
(1)在顶点V的记录中,除了存储点的坐标信息,还有一个指向半边的指针,指向以V为起点的某一条半边。
(2)在面f的记录中,只存储了一个指向半边的指针,指向该面边界上的某一条半边。

图1 DCEL数据结构
(3)在半边edge的记录中,存储了半边的起点,一个半边的指针指向其孪生半边,一个面指针指向位于半边左侧的面face。……
登录APP查看全文
