平面点集Delaunay三角剖分的分治算法

2012-07-25 11:06:22谢增广
计算机工程与设计 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查看全文