总第
２６１期２０１１年第
７期计算机与数字工程
Ｃｏｍ
ｐｕｔｅｒ
＆Ｄｉ
ｇｉｔａｌ
Ｅｎ
ｇｉｎｅｅｒｉｎ
ｇＶｏｌ．３９Ｎｏ．７
５７
基于格网划分的
Ｄｅｌａｕｎａ
ｙ三角剖分算法研究＊
李小丽
陈花竹
（
河南大学软件学院
郑州
４５００００）
摘
要
为了提高海量数据的
Ｄｅｌａｕｎａ
ｙ三角网的构网速度，
本文采用格网划分的三角剖分方法，
首先将数据按照线性
四叉树方式划分为若干格网块，
构建块内子三角网，
然后按照自下而上的合并方式对块进行合并，
形成全局
Ｄｅｌａｕｎａ
ｙ三角
网。
在此基础上，
为了避免出现过小锐角的情况，
通过加入约束角来对三角格网进行优化。
关键词
Ｄｅｌａｕｎａ
ｙ；
格网划分；
约束角
中图分类号
ＴＰ３０１．６
Ｓｔｕｄ
ｙｏｆ
Ｍａｓｓｉｖｅ
Ｄａｔａ
Ｄｅｌａｕｎａ
ｙＴｒｉａｎ
ｇｕｌａｔｉｏｎ
Ｂａｓｅｄ
ｏｎ
Ｇｒｉｄ
Ｐａｒｔｉｔｉｏｎ
Ｍｅｔｈｏｄ
Ｌｉ
Ｘｉａｏｌｉ
Ｃｈｅｎ
Ｈｕａｚｈｕ
（
Ｓｏｆｔｗａｒｅ
Ｃｏｌｌｅ
ｇｅ，
Ｈｅｎａｎ
Ｕｎｉｖｅｒｓｉｔ
ｙ，
Ｚｈｅｎ
ｇｚｈｏｕ
４５００００）
Ａｂｓｔｒａｃｔ
Ｔｏ
ｒａｉｓｅ
ｔｈｅ
ｓ
ｐｅｅｄ
ｏｆ
ｔｈｅ
ｃｏｎｓｔｒｕｃｔｉｏｎ
ｏｆ
Ｄｅｌａｕｎａ
ｙ
ｔｒｉａｎ
ｇｕｌａｔｉｏｎ
ｏｒｉｅｎｔｅｄ
ｍａｓｓｉｖｅ
ｄａｔａ，
ｔｈｉｓ
ｔｈｅｓｉｓ
ｕｓｅｓ
ｔｈｅ
ｇｒｉｄ
ｐａｒｔｉｔｉｏｎ
ｍｅｔｈｏｄ．Ａｔ
ｆｉｒｓｔ，
ｉｔ
ｄｉｖｉｄｅｓ
ｔｈｅ
ｄａｔａ
ｉｎｔｏ
ｃｅｒｔａｉｎ
ｇｒｉｄ
ｔｉｌｅｓ
ｂ
ｙ
ｑｕａｄｔｒｅｅ
ｍｅｔｈｏｄ，
ｃｏｎｓｔｒｕｃｔｓ
ｓｕｂ
Ｄｅｌａｕｎａ
ｙ
ｔｒｉａｎ
－
ｇｕｌａｔｉｏｎ．Ｔｈｅｎ，
ｉｔ
ｍｅｒ
ｇｅｓ
ｔｗｏ
ｔｒｉａｎ
ｇｕｌａｔｉｏｎｓ
ｆｒｏｍ
ｂｏｔｔｏｍ
ｕ
ｐ
ｔｏ
ｆｏｒｍ
ｔｈｅ
ｗｈｏｌｅ
Ｄｅｌａｕｎａ
ｙ
ｔｒｉａｎ
ｇｕｌａｔｉｏｎ．Ｏｎ
ｔｈｅ
ｂａｓｉｓ
ｏｆ
ｔｈａｔ，
ｔｏ
ａｖｏｉｄ
ｐｒｏｄｕｃｉｎ
ｇ
ｔｏｏ
ａｃｕｔｅ
ａｎ
ｇｌｅｓ，
ｗｅ
ｇｉｖｅ
ａ
ｔｈｒｅｓｈｏｌｄ
ａｎ
ｇｌｅ
ｔｏ
ｉｍ
ｐｒｏｖｅ
ｔｈｅ
ａｎ
ｇｌｅｓ
ｏｆ
ｔｈｅ
ｔｒｉａｎ
ｇｕｌａｔｉｏｎ．
Ｋｅ
ｙ
Ｗｏｒｄｓ
Ｄｅｌａｕｎａ
ｙ，
ｇｒｉｄ
ｐａｒｔｉｔｉｏｎ，
ｔｈｒｅｓｈｏｌｄ
ａｎ
ｇｌｅ
Ｃｌａｓｓ
Ｎｕｍｂｅｒ
ＴＰ３０１．６
１
引言
Ｄｅｌａｕｎａ
ｙ三角网在地形拟合、
三维建模、
有限
元分析等方面应用广泛。
并且它具有空外接圆、
最
小内角最大以及唯一性等重要性质，
Ｄｅｌａｕｎａ
ｙ三
角网一直被公认为是优的三角剖分。
经过长期的
研究，
国内外出现了大量算法，
主要归纳为三类：
逐
点插入算法、
三角网生长算法和分治算法。
近年来
随着
Ｄｅｌａｕｎａ
ｙ三角网在应用领域的不断拓展以及
应用需求的不断深入，
特别是对海量数据的管理和
分析，
已成为
Ｄｅｌａｕｎａ
ｙ三角剖分的一大研究热点，
并出现了格网划分的的三角剖分思想［
１］。
本文在
点插入算法和分治算法的基础上，
采用格网划分的
思想，
对海量数据进行分块管理和构建，
希望获得较高的算法效率。
并对加入了约束角的三角格网
如何优化进行了分析。
２
基于格网划分的
Ｄｅｌａｕｎａ
ｙ三角剖
分算法
随着科学技术的不断发展，
海量数据的廉价获
取已成为可能，
而且目前人们在可视化方面的要求
也越来越高，
那么针对海量数据的管理和分析也越
来越普遍。
但是普通计算机仍无法满足对海量数
据处理的要求，
即便是硬件配置较高的计算机，
当
数据量达到一定程度后仍无法正常处理。
怎么在
普通计算机上进行海量数据的
Ｄｅｌａｕｎａ
ｙ三角网构
建是一个亟待解决的问题［
１］。
本文采用基于格网
划分的海量数据
Ｄｅｌａｕｎａ
ｙ三角剖分算法，
通过分
＊收稿日期：２０１１年
１月
９日，
修回日期：
２０１１年
２月
１７日作者简介：李小丽，
女，
硕士研究生，
助教，
研究方向：
地理信息系统。
陈花竹，
女，
硕士研究生，
助教，
研究方向：
偏微分
方程的图像处理。５８
李小丽等：
基于格网划分的
Ｄｅｌａｕｎａ
ｙ三角剖分算法研究第
３９卷
块的方式来对海量数据进行管理［
２～３］。
当在三角
网中进行点的插入删除操作时，
可以快速定位其所
在的块并确定影响区域，
进而提高了构网速度，
降
低了对计算机硬件的要求较低，
便于对三角网进行
更新维护。
２．１
格网划分
首先计算区域内的最大点密度，
根据此点密
度，
确定正方形格网的行列宽，
保证每个网格中点
的数目在一定范围之内。
通过线性四叉树分割方
式对区域进行格网划分，
并对每块进行四叉树编
码。
为了解决块内点数目不均的状况，
当块内点数
过小时，
根据线性四叉树编码方式对块自下而上进
行合并。
２．２
块内构建
Ｄｅｌａｕｎａ
ｙ三角网
在格网块内通过逐点插入算法构建
Ｄｅｌａｕｎａ
ｙ
三角网，
逐点插入算法的基本步骤是：
１）
定义一个
包含所有数据点的初始凸多边形；
２）
对初始凸多
边形通过环切边界法进行初始三角剖分，
然后重复
３）、
４）
步，
直至所有数据点被处理完毕；
３）
插入新
数据点
Ｐ，
首先找出所有其外接圆包含
Ｐ点的三角
形，
并删除离
Ｐ点最近的边，
形成一个
Ｄｅｌａｕｎａ
ｙ空
腔，
然后连接点
Ｐ与空腔的每一个顶点；
４）
以
ＬＯＰ算法优化三角网［
４］。
本文将块内的
Ｄｅｌａｕｎａ
ｙ
三角网的三角形分为如下四类：
形状可能改变的三
角形，
拓扑关系可能改变的三角形、
第二类三角形
的邻接三角形、
除上述之外的三角形［
１］。
当块内
Ｄｅｌａｕｎａ
ｙ三角网构建完毕之后，
将当前块的
Ｄｅｌａｕｎａ
ｙ三角网的结果存入空间数据库或其它数
据文件，
而仅将受邻接格网内的点影响的边界三角
形及其邻近三角形驻入内存（
第一类、
二类、
三类三
角形）。
２．３
格网块
Ｄｅｌａｕｎａ
ｙ三角网合并
块内三角形构建完毕之后，
按照四叉树编码的
逆序，
自下而上的进行格网块间的合并［
３］。
对两
Ｄｅｌａｕｎａ
ｙ子三角网的合并首先找到两个子三角网
合并的顶线和底线，
从底线开始构建三角形，
在此
过程中伴随删除非
Ｄｅｌａｕｎａ
ｙ三角形，
直到顶线结
束。
由于位置的不同，
相邻两
Ｄｅｌａｕｎａ
ｙ子三角网
合并可分为左右和上下两种合并情况。
格网块
Ｄｅｌａｕｎａ
ｙ三角网合并的方式与上述
Ｄｅｌａｕｎａ
ｙ子三角网合并的方式相同，
首先找出两
Ｄｅｌａｕｎａ
ｙ三角网合并的顶线与底线，
然后从顶线开始到底线结束，
该过程伴随着非
Ｄｅｌａｕｎａ
ｙ三角
形的删除和新
Ｄｅｌａｕｎａ
ｙ三角形的生成。
根据分析可知当两块进行合并时，
第一类和第二类三角形将
受到影响，
第三类和第四类不会受到影响。
这两个格网块的并集形成一个新格网块，
对该
格网块重新选择其第一、
二、
三类三角形（
只需把两
个格网块相邻的三角形进行判断），
把第三、
四类三
角形存入空间数据库或其它数据文件，
释放第四类
三角形占用的内存，
这样只有新格网块的第一、
二、
三类三角形驻入内存，
为后续格网块的网合并做好
准备。
按照线性四叉树编码，
自下而上的方式进行
两
Ｄｅｌａｕｎａ
ｙ三角网合并，
重复上述步骤，
直至所有
格网块都处理完毕，
再把驻入内存的三角形存入空
间数据库或其它数据文件，
释放内存，
整个构网结
束。
３
算法流程
在分块的过程中，
为了提高分块的效率和便于
合并，
我们对块采用线性四叉树编码方式，
并且使
用自下而上的合并方式对块进行合并。
第一步：
划分格网块
为了避免出现块内点数目过大的情况，
我们首
先找出区域内点的最大密度，
根据此密度，
按照线
性四叉树划分方式确定初始格网，
并对每块进行编
码。
在为每个点确定格网块时，
记录每块内的点
数。
然后根据块内点数情况，
如果点数过小则按照
自下而上的方式合并块。
第二步：
块内建立子三角网［
５～６］
１）
建立初始凸多边形
２）
采用环切法建立初始三角形网
３）
采用点插入法插入剩余点。
从而建立了子
三角形网。
第三步：
合并块
图
１
两子网合并现有两个凸
壳
ＨＬ、
ＨＲ，
寻找
连接
ＨＬ、
ＨＲ的
顶线和底线过程
如下：
找到
ＨＬ
最右边的点
Ｘ和
ＨＲ最左边的点
Ｙ，
从连接
Ｘ、
Ｙ点的线段
ＸＹ开
始，
如果
ＨＲ上
Ｙ的逆时针方向相邻点
Ｚ位于线
段
ＸＹ的下侧，
则用
Ｚ替换
Ｙ，
直到
ＨＲ上的所有
点都位于
ＸＹ之上。
然后考察
ＨＬ，
如果
ＨＬ上
Ｘ
的顺时针方向上相邻的点
Ｋ位于
ＸＹ的下侧，
则用
Ｚ替换
Ｘ，
直到
ＨＬ上的所有点都位于
ＸＹ之上。
最终形成的线段
ａｂ就是连接
ＨＬ、
ＨＲ的底线。
同