Delaunay三角网的生成算法研究
第28卷 第1期测 绘 学 报
V o l
.28,N o .1 1999年2月
A CTA GEODA ET I CA et CA R TO GRA PH I CA S I N I CA
Feb .,1999
3收稿日期:1998203218,截稿日期:1998210221。武晓波,男,33岁,硕士,助研。主要从事遥感、G IS 研究。
D elaunay 三角网的生成算法研究
3
武晓波 王世新 肖春生
(中国科学院遥感应用研究所,北京,100101)
A new study of D elaunay tr i angulation creation
W u X iaobo ,W ang Sh ix ing ,X iao Chun sheng
(Institu te of R e m ote S ensing A pp lica tions ,Ch inese A cad e m y of S ciences ,B eij ing ,100101)
Abstract A s one of the mo st i m po rtan t D TM model ,D elaunay triangu lati on is w idely app lied in m an ifo ld
fields .T h is paper in troduces b riefly its defin iti on and sign ifican t p roperties .A fter review ed and assessed si m 2p ly to its p revalen t generati on algo rithm s —divide 2conquer ,increm en tal in serti on ,triangu lati on grow th ,th is article p rovides a new upgrade algo rithm —compound algo rithm .T he new algo rithm takes advan tages of di 2vide 2conquer and increm en tal in serti on algo rithm .It u ses compu ter resou rces of ti m e and space mo re reason 2ab ly .T h rough test w ith realD E M data ,its runn ing speed p roves far faster than that of increm en tal in serti on and m atches to divide 2conquer in average case .In better case ,faster than divide 2conquer .
Keywords D TM ,D elaunay triangu lati on ,Generati on algo rithm ,Compound algo rithm
摘 要 D elaunay 三角网作为一种主要的D TM 表示法,具有极其广泛的用途。经过二十多年来的研究,它的生成算法已趋于成熟。本文简要介绍了D elaunay 三角网的定义及其特性,在简单回顾和评价了分割2归并法,逐点插入法,三角网生长法等三类主流算法的基础上,提出了一个融以上算法优点于一体,兼顾空间与时间性能的合成算法。经测试,一般情况下它的运算速度远快于逐点插入法,与分割2归并法相当,较好的情况下快于分割2归并法。关键词 D TM D elaunay 三角网 生成算法 合成算法分类号 T P 309
1 前言
在地学领域,经常需要处理大量分布于地域
内的离散数据。由于这些数据分布的不均匀性,就产生了一个如何合理有效地使用这些宝贵数据的问题。1908年,G .V o rono i 首先在数学上限定了每个离散点数据的有效作用范围,即其有效反映区域信息的范围,并定义了二维平面上的
V o rono i 图[1]
(以下称为V 2图)。1911年,A .H .T h iessen 应用V 2图进行了大区域内的平均降水
量研究[2]。1934年,B .D elaunay 由V 2图演化出了更易于分析应用的D elaunay 三角网[3](以下称为D 2三角网)。从此,V 2图和D 2三角网就成了被普遍接受和广泛采用的分析研究区域离散数据的有力工具。当然,它的应用不仅适用于地学,而且活跃于所有与2.5维分析有关的领域。
在G IS 中,2.5维的分析处理由D TM (数字地形模型)模型进行。D TM 主要由栅格与T I N (不规则三角网)两种数据格式来表示[4,5],而以后者更为重要。前者的优点是,充分表现了高程的细
节变化,拓扑关系简单,算法实现容易,某些空间操纵及存储方便;它的不足之处是,占用巨大的存储空间,不规则的地面特征与规则的数据表示之间的不协调。后者的优点是,高效率的存储,数据结构简单,与不规则的地面特征和谐一致,可以表示线性特征和迭加任意形状的区域边界,易于更新,可适应各种分布密度的数据等;它的局限性是,算法实现比较复杂和困难。在现今的G IS系统中,基本上均支持以上两种数据格式,以T I N 为主,栅格为辅,并提供相互转换功能。
历经二十余年的不懈努力,T I N的许多算法难关已被攻克。T I N的生成算法中,最终有三种为普遍接受和采用,它们是分割2归并法、逐点插入法和逐步生长法,而又以前二者更为流行。分割2归并法时间效率高,但占用内存空间较多。逐点插入法时间效率较差,占用内存空间较少。本文在此二者基础上,提出了一种综合性能的算法——合成算法。它的时性能优于以上两种算法。
2 D elaunay三角网的定义及其特性
D elaunay三角网是V2图(也称为T h iessen 图,D irich let图,V igner2Seithz图)的伴生图形。对它的研究是从对V2图的研究开始的。V2图定义是:
假设V={v1,v2,...,v N},N≥3是欧几里德平面上的一个点集,并且这些点不共线,四点不共圆。用d(v i,v j)表示点v i,v j间的欧几里德距离。设x为平面上的点,则区域V(i)={x∈E2 d(x,v i)≤d(x,v j),j=1,2,...,N,j≠I}称为V o rono i多边形(V2多边形)。各点的V2多边形共同组成V2图。
平面上的V2图可以看作是点集V中的每个点作为生长核,以相同的速率向外扩张,直到彼此相遇为止而在平面上形成的图形。除最外层的点形成开放的区域外,其余每个点都形成一个凸多边形。
D2三角网的定义是:
有公共边的V2多边形称为相邻的V2多边形。连接所有相邻的V2多边形的生长中心所形成的三角网称为D2三角网。
D2三角网的外边界是一个凸多边形,它由连接V中的凸集形成,通常称为凸壳。D2三角网具有两个非常重要的性质。
?空外接圆性质:在由点集V所形成的D2三角网中,其每个三角形的外接圆均不包含点集
V中的其他任意点;
?最大的最小角度性质:在由点集V所能形
成的三角网中,D2三角网中三角形的最小角度是
最大的。
由于这两个性质,决定了D2三角网具有极大
的应用价值。同时,它也是二维平面三角网中唯一
的、最好的。M iles证明D2三角网是“好的”三角
网[6];Sib son认定“在一个有限点集中,只存在一个局部等角的三角网,这就是D2三角网”[7];L in2 gas进一步论证了“在一般情况下,D2三角网是最优的”[8];T sai认为,“在不多于3个相邻点共圆的欧几里德平面中,D2三角网是唯一的”[9]。
3 D-三角网生成算法回顾
T sai根据实现过程,把生成D2三角网的各种算法分为三类:分治算法;逐点插入法;三角网生长法[7]。
3.1 分治算法
Sham o s和Hoey提出了分治算法思想[10],并给出了一个生成V2图的分治算法。L ew is和Rob in son将分治算法思想应用于生成D2三角网[11]。他们给出了一个“问题简化”算法,递归地分割点集,直至子集中只包含三个点而形成三角形,然后自下而上地逐级合并生成最终的三角网。以后L ee和Schach ter又改进和完善了L ew is和Rob in son的算法[12]。
L ee和Schach ter算法的基本步骤是:
把点集V以横坐标为主,纵坐标为辅按升序排序,然后递归地执行以下步骤:
把点集V分为近似相等的两个子集V L和V R;
在V L和V R中生成三角网;
用L aw son提出的局部优化算法LO P[12]优化所生成的三角网,使之成为D2三角网;
找出连接V L和V R中两个凸壳的底线和顶线;
由底线至顶线合并V L和V R中两个三角网。
以上步骤显示,分治算法的基本思路是使问题简化,把点集划分到足够小,使其易于生成三角网,然后把子集中的三角网合并生成最终的三角网,用LO P算法保证其成为D2三角网。不同的实现方法可有不同的点集划分法、子三角网生成法及合并法。
92
第1期 武晓波等:D elaunay三角网的生成算法研究
3.2 逐点插入法
L aw son提出了用逐点插入法建立D2三角网的算法思想[11]。L ee和Schach ter,Bow yer,W at2
son,Sloan,M acedon i o和Paresch i,F lo rian i和Puppo,T sai先后进行了发展和完善[9,13～18]。
逐点插入算法的基本步骤是:
定义一个包含所有数据点的初始多边形;
在初始多边形中建立初始三角网,然后迭代以下步骤,直至所有数据点都被处理;
插入一个数据点P,在三角网中找出包含P 的三角形t,把P与t的三个顶点相连,生成三个新的三角形;
用LO P算法优化三角网。
从上述步骤可以看出,逐点插入算法的思路非常简单,先在包含所有数据点的一个多边形中建立初始三角网,然后将余下的点逐一插入,用LO P算法确保其成为D2三角网。各种实现方法的差别在于其初始多边形的不同以及建立初始三角网的方法不同。
3.3 三角网生长法
Green和Sib son首次实现了一个生成
D irich let多边形图的生长算法[19]。B rassel和R eif 稍后也发表了类似的算法[20]。M cCu llagh和Ro ss 通过把点集分块和排序改进了点搜索方法,减少了搜索时间[21]。M au s也给出了一个非常相似的算法[22]。
三角网生长算法的基本步骤是:
以任一点为起始点;
找出与起始点最近的数据点相互连接形成
D2三角形的一条边作为基线,按D2三角网的判别法则(即它的两个基本性质),找出与基线构成D2三角形的第三点;
基线的两个端点与第三点相连,成为新的基线;
迭代以上两步直至所有基线都被处理。
上述过程表明,三角网生长算法的思路是,先找出点集中相距最短的两点连接成为一条D e2 launay边,然后按D2三角网的判别法则找出包含此边的D2三角形的另一端点,依次处理所有新生成的边,直至最终完成。各种不同的实现方法多在搜寻“第三点”上做文章。
T sai为比较算法性能,给出了一张各种算法的时间复杂度对照表[9]。如表1所示。
表1 几种D elaunay三角网生成算法的时间复杂度
Tab.1 Run-ti m e co m plex ities for severa l D elaunay
tr i angula tion a lgor ith m s
算法一般情况最坏情况
L a w son(1977)2O(N4 3)O(N2)
Green和Sibson(1978)3O(N3 2)O(N2)
L e w is和and Robinson(1978)1O(N l og N)O(N2)
B rassel和R eif(1979)3O(N3 2)O(N2)
M aCullagh和Ro ss(1980)3O(N3 2)O(N2)
L ee和Schach lter(1980)1O(N l og N)O(N l og N)
L ee和Schach lter(1980)2O(N3 2)O(N2)
Bow yer(1981)2O(N3 2)O(N2)
W atson(1981)2O(N3 2)O(N2)
M irante和W eigarten(1982)3O(N3 2)O(N2)
Sl oan(1987)2O(N5 4)O(N2)
Dw yer(1987)1O(N l ogl og N)O(N l og N)
Che w(1989)1O(N l og N)O(N l og N)
M acedoni o和Paresch i(1991)2O(N3 2)O(N2)
上标说明:1.分割2归并法;2.逐点插入法;3.三角网生长法。
表中,N为数据点数。O(f(N))表示算法的时间复杂度,它以算法中频度最大的语句频度f(N)来度量。
4 合成算法介绍
上述三类算法中,三角网生长法在80年代中期以后的文献中已很少见,较多的是分治算法和逐点插入法。而后两类算法又各有其长处及短处。逐点插入法虽然实现比较简单,占用内存较小,但它的时间复杂度差,即运行速度慢。Sham o s和Hoey已证明在N个数据点中建立任何三角网至少需要8(N log N)时间[10]。所以从时间复杂度方面看,分治算法最好。但由于递归执行,它需要较大内存空间。在较低档的计算机平台上,速度慢和占用大空间都是令人难以接受的。这里,我们提出并实现了一种合成算法,它把逐点插入法植入到了分治算法中,互相取长补短,体现了它们的综合优势,从而达到了较好的时空性能。
4.1 基本步骤
合成算法的基本步骤是:
begin
把点集V以横坐标为主,纵坐标为辅按升序排序,然后递归地执行以下步骤:
if V中数据量大于一给定值,把V分为近似相等的两个子集V L和V R;
在V L和V R中用合成算法生成三角网;
找出连接V L和V R中两个凸壳的底线和顶线;
由底线至顶线合并V L和V R中两个三角网;
03测 绘 学 报 第28卷
生成基本三角网;end
4.2 基本三角网生成过程
基本三角网的生成分两步完成,第一步生成初始三角网,第二步在初始三角网中插入剩余点。此处使用了M acedon i o 和Paresch i 改进了的逐点插入算法。它使用凸壳作为初始多边形来生成初始三角网,然后将其余点逐一插入。在生成初始三角网和插入两个步骤中,均采用LO P 过程进行优化,保证所形成的三角网是D 2三角网。4.2.1 生成凸壳过程
这里使用L ark in 改进和完善了的凸壳生成算法[23]。根据Sedgew ick 的结论[24],它把具有x ,y ,x +y ,x -y 的极大值和极小值的点相连作为初始凸壳,然后用一个递归过程convex (I ,J )把位于其中相邻两点间凸壳上的其余点找出来。为提高搜索效率,先把数据分块。convex (I ,J )搜索包含线段—→IJ
(从I 到J 逆时针方向)的矩形内的
数据块,找出位于—→IJ
右侧与—→IJ
距离最大的点。
该点就是要找的凸壳上的点。如果最大距离为零,则要判断它是否位于I ,J 之间。如是,它也是凸壳上的点。
begin
将V 分块,如图1所示;
?
?
?
??????
?????
??
?
??
??
?
??
?
?
??图1
D E
F
G
H A C
B
找出V 中具有x -y ,x ,x +y ,y 的最大值和
最小值的点A ,B ,C ,D ,E ,F ,G ,H (如有相同点则取其一),相连成为初始凸壳L (图中A 2H 点只表示位于L 上);
rep eat
convex (I ,J ); I 、J 是L 上相邻两点
un til L 上的点全被处理end
函数convex (I ,J )begin
在—→IJ
右侧的数据块中,找出与—→IJ
距离
d 最大的点K 。K 位于—
→IJ
右 侧,d 为正,位于—→IJ
左侧,d 为负。
if d >0
将K 插入I 、J 间; convex (I ,K ); convex (K ,J );else if d ==0
if K 位于I 、J 间 将K 插入I 、J 间; convex (I ,K ); convex (K ,J ); else retu rn ;else
retu rn ;end
4.2.2 初始三角网生成过程
begin
读入凸壳点,按逆时针方向顺序存入链表cvxh ;
A =cvxh 中横坐标值最小的点;
A 与cvxh 中其后的两点
B ,
C 连接形成初始
三角形;
rep eat
连接A 与cvxh 中C 的后续点,每次一点,生成新三角形;
用LO P 过程优化三角网;un til 遇到A 4.2.3 点插入过程
rep eat
找出包含p 的三角形t ; 连接p 与t 的三个顶点; 用LO P 过程优化三角网;un til p 为空end
4.2.4 局部优化过程
L aw son 提出的局部优化过程LO P (L ocal O p ti m izati on P rocedu re )是所有生成D 2三角网算
法都要用到的关键过程。理论上说,不论用何种方法生成的三角网,只要用LO P 过程进行处理,就能使它变为D 2三角网。这样一个重要的过程其实非常简单,它就是运用D 2三角网的性质对由两个有公共边的三角形组成的四边形进行判断。如果
1
3第1期 武晓波等:D elaunay 三角网的生成算法研究
其中一个三角形的外接圆包含第四个顶点,则将这个四边形的对角线交换,如图2所示
。
图2
A
B
D
C 优化后
优化前
C D B
A
4.3 寻找连接两个凸壳的底线过程HULL
L ee 和Schach lter 提出的分治算法分两步进
行,首先找出连接左右两个凸外界的顶线和底线,
然后由底至顶合并两个子三角网。这两个过程都要用到函数p red (v i ,v j )和succ (v i ,v j )。函数p red (v i ,v j )找出在以v i 为共同端点的一簇线段中,与v i v j 顺时针方向相邻线段的另一端点,succ (v i ,v j )找出与v i v j 逆时针方向相邻线段的另一端点。点拓扑关系示意如图3中,p red (0,1)是7,succ (0,1)是2。
图3
5
04321
76
设H L ,H R 为V L ,V R 中的左右两个凸壳,寻找连接H L ,H
R
的底线过程HU LL 从连接H L 中
最右边的点X 和H R
中最左边的点Y 的线段—→
X Y
开始,迭代进行。如果H
R
上Y 的逆时针方向相邻
点Z 位于—→X Y
的右侧,则用Z 替换Y ,直至H
R
上
的所有点都在—→X Y
之右。接着考查H L ,如果H L 上X 顺时针方向的点Z ″位于—→X Y
的右侧,则用Z ″
替换X ,直至H L 上的所有点都在—→X Y
之右。最终
形成的—→X Y
就是连接H L ,H
R
的底线。用相似方
法可以找到连接H L ,H
R
的顶线(图4)。
begin
X =H L 中最右边的点;Y =H R 中最左边的点;
Z =H
R 中Y 逆时针方向相邻点;
Z ′
=H L
中X 逆时针方向相邻点;
Z ″=p red (X ,Z ′);rep eat
if (Z is 2righ t 2of —→X Y ) T =Z
Z =succ (Z ,Y ) Y =T else
if (Z ″is 2righ t 2of —
→X Y
) T =Z ″ Z ″=p red (Z ″,X ) X =T else
retu rn —→
XY
end if end if end rep eat end
按类似方法可找出顶线。
图4
底线
顶线
4.4 子三角网归并过程M ERGE
子三角网的合并过程也是一个迭代过程,它从连接H L ,H R 的底线开始,在两个子三角网T L ,T R 中寻找与底线组成D 2三角形的第三点L 1,R 1,选其中外接圆半径小的一个插入到最终的三角网中。新生成的连接左右两个子三角网的边成为新的底线,逐步上推直到顶线结束,如图5所示
。
图5
R 1
L 1
L R
R
L
begin
B T =连接H L ,H
R
的底线
U T =连接H L ,H R 的顶线L =B T 的左端点R =B T 的右端点rep eat
A =
B =false
R 1=p red (R ,L ) if (R 1位于—→L R
左侧)
R 2=p red (R ,R 1)
23测 绘 学 报 第28卷
w h ile(四边形R1,L,R,R2符合D elaunay三角网的条件)
删除边—→
R R1
T=R1
R1=R2
R2=p red(R,T)
end w h ile
else
A=true
endif
L1=succ(L,R)
if(L1位于—→
L R
左侧)
L1=succ(L,L1)
w h ile(四边形L,R,L1,L2符合D elaunay三角网的条件)
删除边—→
L L1
T=L1
L1=L2
L2=succ(L,T)
end w h ile
else
B=true
end if
if(A=true)
插入边—→
RL
1
L=L1
else
if(B=true)
插入边—→
R1L
R=R1
else
if(四边形L,R,R1,L1符合D elaunay三角网的条件)
插入边—→
R1L
R=R1
else
插入边—→
RL1
L=L1
endif
endif
endif
B T=—→
L R
un til(B T=U T)
end
4.5 数据结构
我们用M SC实现了合成算法,其中数据结构参考了L aw son提出的标准三角网数据结构和P rep arata与Sham o s提出的DCEL(双向链接边)数据结构[25]。在边结构中,增加了两个边指针fp red和tp red,分别指向起点顺时针方向的邻边与终点顺时针方向的邻边。它们在寻找两个子三角网的顶线与底线以及合并过程中带来很多方便。合成算法中所采用的点、边、三角形数据结构如下:
typ edef struct vertex{ data po in ts
doub le x,y,z; X&Y coo rdinates
and its heigh t struct vertex3pp tr,3hp tr; N ex t
PO I N T in cell and po in ter to nex t hu ll po in t
}V ER T EX;
typ edef struct edge{ Edges in TR I AN2
GL E struct vertex3vf,3vt; F rom-
node and to-node struct triangle3lt,3rt; L eft and
R igh t TR I AN GL E struct edge3fp red,3fsucc,3tp red,
3tsucc; fou r con tacted edges.
}ED GE;
typ edef struct triangle{ D elaunay
triangles struct edge3ed[3]; bounded
ED GE s’s indices struct triangle3at[3]; A djacen t
TR I AN GL E s’s indices struct vertex3vt[3]; vertices’s
indices doub le xc,yc; X&Y of circum2
cen ter o r cen tro id doub le r2; Square of circum ra2
diu s }TR I AN GL E;
5 实例测试
为了考察合成算法的实际运行效果,我们在586 90微机平台上,用一个有9652个数据点的
33
第1期 武晓波等:D elaunay三角网的生成算法研究
真实数据集作了测试。对应于子集分割阈值由小到大的变化,进行了多次运行,结果如表2所示。分割阈值最小取12是因为当取更小的值时,有子集中的点共线的现象。我们预想,当子集分割阈值取最小值时,算法接近于分割2归并法,应具有最好的执行效率;当子集分割阈值超过数据总数时,算法变为逐点插入法,应具有最差的执行效率。即算法的执行效率应与分割阈值呈负相关关系。测试结果表明并不完全如此。逐点插入法用时最多,表现最差在意料之中。出乎意料的是,分割2归并法的表现并不是最好,算法的执行效率并不像估计的那样与分割阈值呈严格的负相关关系,而是在分割阈值由小到大的变化的初始阶段呈正相关,达到一最高点后转呈负相关。
表2 合成算法在不同分割阈值下运行所需时间
Tab.2 Co m pound A lgor ith m’s perfor mance under
var ious split threshold
分割阈值运行时间 s
12182(分割2归并法)
200150
500140
1000137
2000148
4000190
6000307
10000570(逐点插入法)
测试结果说明,不能仅仅从理论时间复杂度来评价一个算法的实际表现,对时间与空间的合理综合利用才是决定一个算法优劣的关键。
6 总结与讨论
D2三角网由于其独特的数学性质,是进行2.5维分析的一个有力工具,是G IS中D TM模型的一个重要表示方法和分析处理手段。在已有的由离散数据建立D2三角网的算法中,经过二十多年来的研究与实践,分治算法与逐点插入法被普遍接受和采用。这两类算法虽然各自具有明显的优势,但也同时具有其固有的缺点。分治算法具有时间优势,但却付出了高昂的空间代价。逐点插入法具有空间优势,但时间效率极低。我们对这两类算法进行了揉合,取其长补其短,给出了一个新的算法,目的是更好地合理利用计算机资源,提高执行速度,增强平台适应性。经实例测试它达到了这一目的。
本文所讨论的算法都是针对一般D2三角网的,可用于不带方向性的2.5维分析或对精度要求不高的D TM分析。在精度要求较高的D TM 分析中,必须使用能够表示地形结构线(山脊线、谷地线)的约束D2三角网[26～27]。这方面的研究工作也已有很长的历史,我们正在进行它的算法研究及编程。有兴趣的读者可参阅文献[18,26～27],并欢迎与我们联系讨论。
致谢阎守邕研究员全面指导了这项研究,对本文的段落安排及文字运用等方面提出了许多珍贵建议并作了修改。在此谨向他表示诚挚的敬意和感谢。赵健、崔景年、田青、周艺、王涛等同仁在研究过程中给予了大力帮助,在此也向他们表示衷心感谢。
7 参考文献
1 V o rono i G.N ouvelles A pp licati on s des Param eters Con tinu s,a la T heo rie des Fo rm es Q uadratiques,
D eux iem e M emo rie:R echerches su r les Parrallelloe2
dres P ri m itifs,Jounal fu r die R eine und A ngew andte M athem atik,1908(134):198～287
2 T h iessen A H.P reci p itati on A verages fo r L arge A r2 eas,M on th ly W eather R eview,1911(39):1082～1084
3 D elaunay B.Su r la Sphere V ide.Bu lletin of the
A cadem y of Sciences of the U SSR,C lasse des Sci2
encesM athem atiques et N atu relles,1934(8):793～
800
4 毋河海.地图数据库系统.北京:测绘出版社,1991
5 柯正谊,何建邦,池天河.数字地面模型.北京:中国科学技术出版社,1993
6 M iles R E.So lu ti on to P rob lem67215(P robab ility
D istribu ti on of a N etw o rk of T riangles).S I AM,
1969(11):399～402
7 Sib son R.L ocally Equ iangu lar T riangu lati on https://www.docsj.com/doc/e913969486.html,2 pu ter Jou rnal,1978,21(3):243～245
8 L ingas A.T he Greedy and D elaunay T riangu lati on s are no t Bad in the A verage https://www.docsj.com/doc/e913969486.html, rm ati on P ro2 cessing L etters,1986(22):25～31
9 T sai V J D.D elaunay T riangu lati on s in T I N C re2 ati on:an O verview and a L inear2ti m e A lgo rithm.
In t.J.of G IS,1993,7(6):501～524
10 Shamo s M I.and Hoey D.C lo sest2po in t P rob lem s, In:P roceedings of the16th A nnual Sympo sium on
the Foundati on s of Compu ter Science,1975.151～
162
11 L ew is B A.and Rob in son J S.T riangu lati on of P la2 nar R egi on s w ith A pp licati on s,T he Compu ter Jou r2
43测 绘 学 报 第28卷
nal,1978,21(4):324～332
12 L ee D T.and Schach ter B J.Tw o A lgo rithm s fo r Con structing a D elaunay T riangu lati on,In t.J.of Compu ter and Info rm ati on Sciences,1980,9(3)
13 L aw son C L.Softw are fo r C’Su rface In terpo lati on.
M athem atical Softw are III.J.R ice,Ed.N ew Yo rk:A cadem ic P ress,1977
14 Bow yer https://www.docsj.com/doc/e913969486.html,pu ting D irich let T esselati on s,Com2 pu ter Jou rnal,1981(24):162～166
15 W atson D https://www.docsj.com/doc/e913969486.html,pu ting the n2di m en si on D elaunay T esselati on w ith A pp licati on to V o rono i Po lytopes.
Compu ter Jou rnal,1981(24):167～172
16 Sloan S W.A fast A lgo rithm fo r Con structing D e2 launay T riangu lati on s in the P lane.A ndvanced En2 gineering Softw are,1987(9):34～55
17 M acedon ia G and Paresch iM T.A n A lgo rithm fo r the T riangu lati on of A rb itrarily D istribu ted Po in ts:
A pp licati on s to V o lum e E sti m ate and T errain F it2
ting,Compu ters&Geo sciences,1991(17):859～
874
18 D e F lo rian i L and Puppo E.A n on2line A lgo rithm fo r Con strained D elaunay T riangu lati on,CV G IP:
Graph ical M odels and I m age P rocessing,1992,54
(3):290～300
19 Green P J.and Sib son https://www.docsj.com/doc/e913969486.html,pu ting D irich let T es2 selati on s in the P lane.T he Compu ter Jou rnal, 1978,21(2):168～17320 B rassel K E.and R eif D.P rocedu re to Generate T h iessen Po lygon s.Geophysical A nalysis,1979
(11):289～303
21 M cCau llagh M T.and Ro ss C G.D elaunay T riangu2 lati on of a R andom D ata Set Fo r Iirarithm ic M ap2 p ing.T he Cartograph ic Jou rnal,1980(17):93～99 22 M au s A.D elaunay T riangu lati on and the Convex
H u ll of n Po in ts in Expected L inear T i m e.B IT,
1984(24):151～163
23 L ark in B J.A n AN S I C P rogram to D eterm ine in Expected L inear T i m e the V ertices of the Convex
H u ll of a Set of P lanar Po in https://www.docsj.com/doc/e913969486.html,pu ters&Geo2
sciences,1991,17(3):431～443
24 Sedgew ick R.A lgo rithm s.N ew Yo rk:A ddison2 W esley,1988
25 P reparata F P and Shamo s M https://www.docsj.com/doc/e913969486.html,pu tati onal Ge2 om etry:A n In troducti on,N ew Yo rk Berlin: Sp ringer2V erlag,1985
26 Chew L P.Con strained D elaunay T riangu lati on s.
A lgo rithm ica,1989,4:97～108
27 V o igtm ann A,Becker L and H in rich s K.H ierach ical Su rface R ep resen tati on sU sing Con strained D elaunay T riangu lati on s,A dvances in G IS R esearch.In:P ro2 ceedings of the six th In ternati onal Sympo sium on Spatial D ata H andling.T aylo r&F rancis,Ed.
W augh T C&H ealey R G,1994.848～867
53
第1期 武晓波等:D elaunay三角网的生成算法研究
不规则三角网的算法设计与实现10页word文档
1 引言 地球表面高低起伏，呈现一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法——数字高程模型的方法，这种方法已经被普遍广泛采用。数字高程模型即DEM （Digital Elevation Model），是以数字形式按一定结构组织在一起，表示实际地形特征空间分布的模型，也是地形形状大小和起伏的数字描述。 由于地理信息系统的普及，DEM作为数字地形模拟的重要成果已经成为国家空间数据基础设施（NSDI）的基本内容之一，并被纳入数字化空间框架（DGDF）进行规模化生产，已经成为独立的标准基础产品[5]。DEM有三种主要的表示模型：规则格网模型，等高线模型和不规则三角网。格网（即GRID）DEM在地形平坦的地方，存在大量的数据冗余，在不改变格网大小情况下，难以表达复杂地形的突变现象，在某些计算，如通视问题，过分强调网格的轴方向。不规则三角网（简称TIN，即Triangulated Irregular Network）是另外一种表示数字高程模型的的方法（Peuker等，1978），它既减少了规则格网带来的数据冗余，同时在计算（如坡度）效率方面又优于纯粹基于等高线的方法。不规则三角网能随地形起伏变化的复杂性而改变采样点的密度和决定采样点的位置，因而它能够避免地形起伏平坦时的数据冗余，又能按地形特征点如山脊，山谷线，地形变化线等表示数字高程特征。
基于三角形的表面建模可适合所有的数据结构，且三角形在形状和大小方面有很大灵活性，能很容易地融合断裂线，生成线或其他任何数据，因此基于三角形的方法在地形表面建模中得到了越来越多的注意，已经成为表面建模的主要方法之一。VB语言简洁易学，对于学习GIS的学生来说无疑是接受很容易而且较快的一门计算机编程和开发语言，也是大多数学生最熟悉和了解的语言。正是基于对生成不规则三角网算法的研究和满足学GIS的学生对VB语言的喜爱和熟悉的情况下，本文就主要介绍用三角网生长算法生成不规则三角网及其在VB6.0环境下的实现。 2 TIN的算法种类及各算法特点 在介绍构成TIN各种算法之前我们要来了解认识一下一个重要法则——Delaunay三角网法则。通常构建三角网并不考虑地性线（山脊线，山谷线）的骨架作用，但是，由于用等高线数据构建三角网时，由于地形的复杂多样，有的地区存在因地形突变而形成的断裂线等特殊地貌。另外一些地区存在大面积水域等内部不需要构网的区域，因此，在精度要求较高的TIN中，必须考虑以上问题。因此此时应顾及地性线，断裂线，水域线等特殊情况，也就是应构建约束—Delaunay三角网。约束法是基于约束图计算约束D—三角剖分[1,9]（简称CDT，即Constrained Delaunay Triangulation）构造算法[8]，这种Delaunay三角网满足这样的法则：Delaunay三角网为相互邻接且互不重叠的三角形的集合，每一个三角形的外接圆内不包含其他点。Delaunay三角网由对应Voronoi多边形的点连接而成。Delaunay三角形有三个相邻点连接而成，这三个相邻顶点对应的
Delaunay三角形构网的分治扫描线算法
第36卷 第3期测 绘 学 报 Vol.36,No.3 2007年8月 ACTA GEODAETICA et CARTO GRAPHICA SINICA Aug ,2007 文章编号:100121595(2007)0320358205中图分类号:P208 文献标识码:A Delaunay 三角形构网的分治扫描线算法 芮一康,王结臣 (南京大学地理信息科学系,江苏南京210093) A N e w Study of Compound Algorithm B ased on Sw eepline and Divide 2and 2conquer Algorithms for Constructing Delaunay T riangulation RU I Y i 2kang ,WAN G Jie 2chen (Depart ment of Geographic Inf ormation Science ,N anji ng U niversity ,N anji ng 210093,Chi na ) Abstract :As one of the most important DTM model ,Delaunay triangulation is widely applied in manifold fields.A wide variety of algorithms have been proposed to construct Delaunay triangulation ,such as divide 2and 2conquer ,in 2cremental insertion ,trangulation growth ,and so on.The compound algorithm is also researched to construct Delau 2nay triangulation ,and prevalently it is mainly based on divide 2and 2conquer and incremental insertion algorithms.This paper simply reviews and assesses sweepline and divide 2and 2conquer algorithms ,based on which a new com 2pound algorithm is provided after studying the sweepline algorithm seriously.To start with ,this new compound al 2gorithm divides a set of points into several grid tiles with different dividing methods by divide 2and 2conquer algo 2rithm ,and then constructs subnet in each grid tile by sweepline algorithm.Finally these subnets are recursively merged into a whole Delaunay triangulation with a simplified efficient LOP algorithm.For topological structure is im 2portant to temporal and spatial efficiency of this algorithm ,we only store data about vertex and triangle ,thus edge is impliedly expressed by two adjacent triangles.In order to fit two subnets merging better ,we optimize some data structure of sweepline algorithm.For instance ,frontline and baseline of triangulation are combined to one line ,and four pointers point to where maximum and minimum of x axis and y axis are in this outline.The test shows that this new compound algorithm has better efficiency ,stability and robustness than divide 2and 2conquer and sweepline algo 2rithms.Especially if we find the right dividing method reply to different circumstance ,its superiority is remarkable.K ey w ords :Delaunay triangulation ;compound algorithm ;sweepline algorithm ;divide 2and 2conquer algorithm 摘 要:Delaunay 三角网作为一种主要的DTM 表示法,具有极其广泛的用途。基于分治算法和逐点插入法的合成算法是目前研究较多的用于生成Delaunay 三角网的合成算法。简要介绍和评价扫描线算法和分治算法后,提出一种新的基于这两种算法的合成算法。该方法兼顾空间与时间性能,稳定性较高,分别较扫描线算法和分治算法,运行效率和鲁棒性更优。 收稿日期:2006206221;修回日期:2007202206 基金项目:国家自然科学基金(40401046) 作者简介:芮一康(19832),男,江苏溧阳人,研究生,主要从事地理信息系统理论与应用研究。 关键词:Delaunay 三角网;合成算法;扫描线算法;分治算法 1 引 言 2维平面域内任意离散点集的不规则三角网(TIN 2Triangular Irregular Network )的构建是GIS 数据表达、管理、集成和可视化的一项重要内 容,也是地学分析、计算机视觉、表面目标重构、有限元分析、道路CAD 等领域的一项重要的应用技 术。在所有生成TIN 的方法中,Delaunay 三角网 最优,它尽可能避免了病态三角形的出现,常常被用来生成TIN 。Delaunay 三角网是Voronoi 图的直线对偶图,即是连接所有相邻的Voronoi 多边形的生长中心所形成的三角网。它有以下两条重要性质[1]:空外接圆性质,即由点集所形成的三角网中,每个三角形的外接圆均不包含点集中的
一种基于TDOA与三角形加权质心定位的混合算法
邮局订阅号：82-946120元/年技术创新 软件时空 《PLC 技术应用200例》 您的论文得到两院院士关注 一种基于TDOA 与三角形加权质心定位的混合算法 A Hybrid Algorithm Based On TDOA And Triangle Weighted Centroid Localization (1.兰州大学;2.总参谋部通信训练基地) 傅涛 1,2 杨凌 1 李晓燕 1 闫胜武 1 FU Tao YANG Ling LI Xiao-yan YAN Sheng-wu 摘要:提出一种基于TDOA 与三角形加权质心定位的混合算法,该算法仅采用三个信标节点,充分利用节点的数据处理单元和通信单元,通过三角形加权质心定位算法得到一个定位信息,同时待定节点充分利用接收信号进行相关运算,求时差得到另一个定位信息。对两组定位信息比较、取均值,得到相对稳定的定位信息,实验证明该算法不仅减小了定位误差,提高了定位精度,而且解决了TDOA 的模糊定位问题。 关键词:TDOA;信标节点;三角形加权质心定位;混合定位 中图分类号:TP393 文献标识码:A Abstract:A hybrid algorithm based on TDOA and triangle weighted centroid localization was proposed.This algorithm only used three beacon nodes,make full use of the data processing unit and node communication unit,We can get a location information through the triangle weighted centroid localization algorithm,and at the same time,an Unknown node make full use of accept signal related calculation,for time to get another location information.For both groups positioning information comparison,Calculate average and get a relatively stable location information,the experiment shows that this algorithm not only improve location accuracy,reducing the positioning error,and solve the problem of the fuzzy TDOA localization. Key words:TDOA;Beacon nodes;Triangle weighted centroid localization;Hybrid localization 文章编号:1008-0570(2012)10-0395-02 1引言 在无线传感器网络(WSN)中,没有位置信息的监测消息是毫无意义的,因而节点定位技术成为无线传感器网络中的一项关键支撑技术。依据定位过程中是否需要测量实际节点间的距离,可将WSN 定位算法分为基于测距定位算法(Range-Based)和基于非测距定位算法(Range-Free)。前者包括:到达时间法 (TOA)、 到达时间差法(TDOA)、到达角度法(AOA)、信号强度法(RSSI)等。后者包括:质心算法、DV-HOP 算法、Amorphous 算法和APIT 算法等。事实上,每种定位算法都有其适用范围和局限性,因而本文提出一种基于TDOA 与三角形加权质心定位的混合算法。 2TDOA 双曲线定位算法 WSN 中传统的TDOA 测距技术是利用两种不同信号(一般是射频信号和超声波)到达同一节点所产生的时间差来确定节点间的距离,不仅增加了硬件成本和体积,而且应用规模受限,不符合本文要求,而移动通信系统中的TDOA 作为一种双曲线定位技术,可以很好的移植到WSN 当中,在不增加节点硬件成本的情况下完成节点定位功能。 2.1TDOA 定位算法原理如图1所示,假设A(x A ,y A )、B(x B ,y B )、C(x C ,y C )是三个信标节点,O(x,y)点是待定节点,T ij 表示信号从i 点到待定节点所用时间与信号从j 点到待定节点所用时间差,v 表示信号传播速度,d ij 表示待定节点到信标节点i 和j 点的距离差,解以下双曲线方程组即可得出未知节点的坐标,但此种方法存在模糊定位问题,可能存在双解两交点的情况,需要优化。 2.2TDOA 互相关方法数学模型 TDOA 算法关键在于得到两个信标节点到待定节点的时间差T 。直接计算TOA 需要节点达到严格同步,会大幅度增加节点的成本和能量消耗,实现起来困难,所以本文采用互相关技术求解时间差T,从而达到不增加节点硬件成本的效果。 如图1所示,当待定节点发起请求定位信号时,信标节点A 和B 发射的连续波信号为s(t),经传输后受到噪声干扰,待定节点O 接收到信号分别为x 1(t)、x 2(t): 由(2)式化简可得(3)式: 式中:T 是传输时延,T=d 1-d 2;A 为幅度比,A=A 1/A 2,则待定节点接收到信号的互相关函数为: 根据自相关函数的性质,,可以用互相关函数达到极大值来估计时延差T 。当取极大值时,τ就是我们需要测算的到达时间差T 的值,将T 代入公式,得解。 3基于RSSI 的定位算法 3.1基于RSSI 的三角形质心定位算法 傅涛:讲师硕士研究生 395--
三角网算法
三角网算法 (2010-11-15 10:54:01) 原作：Paul Bourke / 1989.1 翻译：robter_x 原文出处： https://www.docsj.com/doc/e913969486.html,.au/~pbourke/terrain/triangulate/ 这是一个适用于地形模型的三角网算法。 摘要（略） 介绍 有很多技术能够应用于表面插值，也就是说，已知一些采样点高度，求与这些采样点接近的某点的高度。一些常用的方法是邻接插值，表面补丁，二次曲面，多边形插值，样条插值和下面将要描述的丹尼三角网（Delauney Triangulation）。一些插值方法经常应用于经验数据的显示，例如，地形模型中的原始数据来源于调查，气象中心的气象分析数据，或有限元分析筛选出的数据等。 这篇文章讨论的技术不仅适用于地形模型，而且适用于其它方面，这个技术具有下列特点 有一些地方的采样点密度高，而另一些地方的采样点密度低。例如，在地形模型中，一般水边界的内部的采样点呈低密度分布，而在一些较复杂的地方，采样点呈高密度分布。 由于地形表面的不连续，导致采样平面上的采样点较密集。这些可能是自然情况，如，悬岩和河岸，也可能是人工制造的不连续，如围墙。很多平滑方法不能很好的处理这种情况，特别是那些基于多边形的函数将导致表面尖突，摆动和不稳定。 采样点经常沿着等值线分布，这是由于采样点的来源可能是等值线图或者地质调查组的实际勘探。这是导致采样点密度不一致的另一个原因。沿着采样点曲线有较高的采样点密度，而与采样点曲线垂直的路径，除非遇到另一条采样点曲线，否则，没有采样点。 经常需有处理大量的采样点。对一个适用的技术来说，随着采样点数量的增加，处理采样所需的时间应该适度的增加。典型的采样点数量一般是100～100000，对于一个自动化的取样方法来说，通常会有这么大数量的采样点。 获得的采样点一般是逐步增多的。最初获得的采样点被分析，对于感兴趣的地方可能会增加采样密度。很显然，在分析结果上增加一些新的采样点来进一步分析比对所有的采样点重新分析要有利。
三角剖分
Delaunay三角剖分算法 默认分类2009-12-16 11:41:23 阅读33 评论0 字号：大中小订阅 转载：https://www.docsj.com/doc/e913969486.html,/renliqq/archive/2008/02/06/1065399.html 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格，这就是散点集的三角剖分问题，散点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。该问题图示如下： 1.1.三角剖分定义 【定义】三角剖分：假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件： 1.除了端点，平面图中的边不包含点集中的任何点。 2.没有相交边。 3.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。 1.2. Delaunay三角剖分的定义 在实际中运用的最多的三角剖分是Delaunay三角剖分，它是一种特殊的三角剖分。先从Delaunay边说起： 【定义】Delaunay边：假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。 【定义】Delaunay三角剖分：如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。 1.3.Delaunay三角剖分的准则 要满足Delaunay三角剖分的定义，必须符合两个重要的准则：
delaunay三角网生长准则及算法
Delaunay 三角网是Voronoi(或称thiessen多边形,V 图)图的伴生图形 ◆Delaunay 三角网的定义: 由一系列相连的但不重叠的三角形的集合, 而且这些 三角形的外接圆不包含这个面域的其他任何点。 ◆Voronoi图的定义： Voronoi图把平面分成N 个区，每一个区包括一个点， 该点所在的区域是距离该点最近的点的集合。 ◆Delaunay三角网的特性： ◆不存在四点共圆； ◆每个三角形对应于一个Voronoi图顶点； ◆每个三角形边对应于一个Voronoi图边； ◆每个结点对应于一个Voronoi图区域； ◆Delaunay图的边界是一个凸壳； ◆三角网中三角形的最小角最大。 空外接圆准则最大最小角准则最短距离和准则 在TIN中，过每个三角形的外接圆均不包含点集的其余任何点在TIN中的两相邻三角形形成 的凸四边形中，这两三角形 中的最小内角一定大于交换 凸四边形对角线后所形成的 两三角形的最小内角 一点到基边的两端的距离 和为最小 Delaunay三角剖分的重要的准则
张角最大准则面积比准则对角线准则 一点到基边的张角为最大三角形内切圆面积与三角形 面积或三角形面积与周长平 方之比最小 两三角形组成的凸四边形 的两条对角线之比。这一 准则的比值限定值，须给 定，即当计算值超过限定 值才进行优化 Delaunay三角剖分的重要的准则 不规则三角网(TIN)的建立 ●三角网生长算法就是从一个“源”开始，逐步形成覆盖整个数据区域的三角网。 ●从生长过程角度，三角网生长算法分为收缩生长算法和扩张生长算法两类。 方法说明方法实例 收缩生长算法先形成整个数据域的数据边界（凸壳）， 并以此作为源头，逐步缩小以形成整个三 角网 分割合并算法 逐点插入算法 扩张生长算法从一个三角形开始向外层层扩展，形成覆 盖整个区域的三角网 递归生长算法
delaunay算法简介
三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。 然后有两个问题要解决：
1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”； 大概的道理我们是懂了，但是给你任意一些点，你采用什么思路
基于delaunay三角剖分的三维地形生成
基于delaunay三角剖分的三维地形生成 1、问题背景 地图是几个世纪以来最重要的空间信息表达的载体“近年来随着高技术 的发展特别是基于计算机平台GIS的发展,地理信息系统得到日益广泛的应用。 地形与人类的生产生活息息相关,在城市规划、路径选取、资源调查与分配、工程勘查与设计、项目选址、环境监测、灾害预测与预报、军事、游戏娱乐等领域有广泛的应用,因此人们一直关心如何真实地表达自然界的地形,以满足人们生活的需要。目前,随着计算机技术的进一步发展,计算能力的不断提高,使用计算机进行地的三维表达成为目前研究的热点,这种地形的表达方式,不但感觉直观、真实性好、而且具有二维电子地图的其它优点,例如分层显示!位置顶点查找等。二维地形生成技术是当今社会的热门技术,正在被越来越多的人所重视和研究。 2、算法描述 Lawson提出了用逐点插入法建立D-三角网的算法思想［11］。Lee和Schachter，Bowyer，Watson，Sloan，Macedonio和Pareschi，Floriani和Puppo，Tsai先后进行了发展和完善。 本次实验算法为delaunay三角剖分的逐点插入法，算法步骤如下： 1、创建一个最大的三角形包含所有离散的数据点，构成初始的三角网。 2、遍历各点（p） (1)、在三角网查找包含p的三角形t。 (2)、若p在三角形内：p与三角形t的三个顶点相连构成三个三角形。加 入三角网中。如下图：
若p 在三角形边上：找出边所对应的另一个三角形的顶点，并与当前的三角形的顶点构成四个顶点，加入三角形网中。如下图： (3)、移除三角形t 。 (4)、用LOP 算法对各个三角形进行优化处理。 3、移除外围三角形。 LOP 算法 在相邻的两个三角形( abd 和bcd) 所组成的四边形中，如果对角线交换所得的两个新三角形ABC 和ABD( 如下图) 比原来的两个三角形更优，则用新的两个三角形替代原来的两个三角形。更优的标准之一是最小角度最大原则: 调整前的二个三角形共六个内角中的最小角和调整后的六个角中的最小角相比较，若前者小于后者则调整，否则不调整; 标准之二是空外接圆性质: 在由点集V 所形成。D-三角网中，其每个三角形的外接圆均不包含点集V 中的其他任意点。结合本文定义的数据结构，本文采取了以相邻三角形作为优化着眼点的处理算法。根据Delaunay 三角网空外接圆性质有以下判断: 当sin( ∠C + ∠D) ≤0， 不进行优化，p
word版本hslogic_Delaunay三角剖分算法应用
本课题的研究方法 三角网格化主要有两种准则:一种称为Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质（空外接圆性质和最大最小角度性质）以及Delaunay三角网的基本原理为基础，参照传统算法思路，在构建三角网的过程中，改进算法的实现方法，数据结构，以达到提高效率的目的。 Delaunay的重要性质 空外接圆性质：在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。λ 最大最小角度性质：在由点集V生成的Delaunay三角网中，所有三角形中的最小角度是最大的，即在生成的三角形网格中,各三角形的最小内角和为最大。λ唯一性：不论从区域何处开始构网，最终都将得到一致的结果。λ 由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网；Lingas进一步论证了“在一般情况下，Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要算法依据。 3.3 详细算法描述 算法基于上述的传统构建算法，但仅有两步： 第一步： （1）在离散点集中寻找一纵坐标最小的点A。 （2）以点A为起点，寻找两个点B、D，使得向量AB与横坐标轴夹角最小，向量AD与横坐标轴夹角最大。若点A、B、D共线，将原B点标记为A，寻找点D，使得向量AD与直线AB夹角最大；寻找点C使得向量BC与线段AB夹角最小。否则，若A、B、D不共线，则寻找点C使得向量BC与线段AB夹角最小。这样，所有点都在逆时针旋转的折线DABC的左侧。 （3）上面一步生成的点C、D如果为同一点，则△ABC（或△ABD）即为包含所有不规则点的Delaunay三角形，生成凸包的过程结束跳过一下各步；否
有限元分析中的二维Delaunay三角网格剖分代码实现
有限元分析中的二维Delaunay三角网格剖分代码实现 //二维平面点集的Delaunay三角剖分 #include "stdafx.h" #include
delaunay算法简介.(优选.)
最新文件---- 仅供参考------已改成word文本------ 方便更改 三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。 首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。
然后有两个问题要解决： 1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典---Delaunay 三角剖分。 Delaunay三角剖分具有四个特有的性质： （1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准； （2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。 （3）Delaunay三角网是唯一的。 （4）三角网的外边界构成了点集的凸多边形“外壳”；
基于MATLAB实现二维delaunay三角剖分
34 基于MATLAB 实现二维delaunay 三角剖分 刘锋涛 凡友华 （哈尔滨工业大学深圳研究生院 深圳 518055） 【摘要】在已知凸多边形的顶点坐标的前提情况下，利用MATLAB 中的meshgrid 函数产生多边 形附近矩形区域内的网格点的坐标，然后再利用inpolygon 函数判断哪些点位于多边形内和哪 些点位于多边形的边界上。在此基础上利用delaunay 函数来完成delaunay 三角剖分。 【关键词】delaunay 三角剖分；MATLAB 网格划分是有限元分析前处理中的关键步骤，网格划分的密度以及质量对有限元计算的精度、效率以及收敛性有着重要的影响作用。自20世纪70年代开始，关于有限元网格生成方法的研究已经取得了许多重要成果，提出许多有效的算法。Ho-Le 对网格生成方法进行了系统的分类[1]。许多学者也对网格生成的方法进行了综述，如我国的学者胡恩球等[2]、关振群等[3]。 Delaunay 三角剖分(简称DT)是目前最流行的通用的全自动网格生成方法之一。DT 有两个重要特性：最大-最小角特性和空外接圆特性。DT 的最大-最小角特性使它在二维情况下自动地避免了生成小内角的长薄单元。因此特别适用于有限元网格生成。大体上可将DT 算法分为三大类：分治算法，逐点插入法和三角网生长法。经典DT 技术已经相当成熟，近年来的研究重点是约束DT 的边界恢复算法，以及如何克服算法退化现象所产生的薄元(sliver element)问题[3]。 然而，实现DT 有限元网格生成，对于非计算机图形学专业的工程师来说还是很复杂的。在处理一些对有限元网格划分质量不过的问题时，如极限分析的有限元方法，可以采用一些更为简单的方法来实现。在Matlab 计算软件中，已有一个成熟的函数delaunay 可以实现对一系列点的DT 划分。因此，本文基于Matlab 的delaunay 等一些函数来完成一个凸多边形的DT 网格划分。 1 MATLAB 中的函数 1.1 delaunay 函数 delaunay 函数可以按照DT 网格划分的要求将一个点集中的点划归某一个有限网格所有。它在Matlab 中的用法如下： =delaunay(,) or, =delaunay(,,)TRI x y TRI x y options 其输入为点集中所有点的横、纵坐标向量x 和y ，返回值为一个3m ×的矩阵，矩阵中每一行表示DT 网格中一个三角形网格的三个顶点。 1.2 meshgird 函数 为了在任意凸多边形内产生一个点集，可以利用Matlab 中的meshgrid 命令。其用法如下： [,] = meshgrid(,)X Y x y
Delaunay三角网表示点和删除算法
0引言 对于静态数据三角化(数据点不能动态插入与删除)，有许多D-三角网构建算法[1-5]；对于动态的点插入，使用逐点插入的方法进行动态局部更新；对于动态的点删除，使用的方法有两种，一是基于凸耳权值的点删除方法[6-7]，二是基于空外接圆准则和凸耳性质的点删除方法[8-9]，上述两种方法都是基于凸耳删除的方法，存在难以理解或算法效率差的缺点。本文提出了一种数据结构来存储D-三角网和表现其拓扑关系，对其中的点删除算法进行了改进，可实现D-三角网中数据点的快速删除操作。 1存储结构 对于三角格网的存储结构，本文设计了点、有向边的存储 表示，三角形的信息在有向边的遍历中隐含，其C++实现如下： Class Point2d {double x,y;} Class Edge { Public:Int num;Edge* next;Edge* prev; Point2d*data;Edge (){data =0;} Edge*Sym (){return (num<1)?this+1:this-1;}Edge*Onext (){return next;}Edge*Oprev (){return prev;} void EndPoints (Point2d*or,Point2d*de ){data =or;Sym ()->data =de;} TwinEdge*Tedge (){return (TwinEdge *)(this -num );}}; Class TwinEdge {Private:Edge e [2];Public:TwinEdge (){ e [0].num =0;e [0].next =&(e [0]);e [1].num =1;e [1].next =&(e [1]); 收稿日期：2007-03-01E-mail ：mengl@https://www.docsj.com/doc/e913969486.html, 基金项目：国家863高技术研究发展计划基金项目(2002AA114020、2001AA135210)；中国科学院知识创新基金项目(20036020)。 作者简介：孟亮(1968－)，男，山西临汾人，博士研究生，研究方向为GIS 、计算机图形学；方金云(1968－)，男，山东青岛人，博士，副研究员，研究方向为海量空间数据处理关键支撑技术、网格GIS 等；唐志敏(1966－)，男，江苏江阴人，研究员，博士生导师，研究方向为计算机系统结构、网络并行处理。 Delaunay 三角网表示和点删除方法 孟 亮，方金云，唐志敏 (中国科学院计算技术研究所，北京100080) 摘 要：对于三角网的表示方法，提出了一种双循环链表结构，这种结构能够方便的表示三角网的边拓扑和面拓扑信息，以及多边形结构。基于这种结构，对三角网点删除算法进行了改进。以前的点删除算法是基于连续的凸耳删除，提出的方法是基于多边形边的构建方法，利用D-三角网的空外接圆属性。与其它方法相比，这种方法具有容易理解，效率高的优点。关键词：Delaunay 三角网;凸耳;点删除;拓扑结构;双循环链表中图法分类号：TP391;P208 文献标识码：A 文章编号：1000-7024(2008)03-0738-03 Delaunay TIN expression and point deletion method MENG Liang, FANG Jin-yun, TANG Zhi-min (Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100080,China ) Abstract ：As to representation of triangulated irregular network (TIN ),a dual-circulation linked list structure is proposed,this structure can conveniently express edge and plane topology information of triangulated irregular network,and polygon structure.Based on this structure,improvements are achieved about TIN point deletion algorithm.Previous point deletion algorithm is based on continuous ears deletion,the methods proposed is based on edge construction method of polygon,using Delaunay TIN circumcircle https://www.docsj.com/doc/e913969486.html,pared with other methods,this method has the advantage of easy understanding,higher efficiency. Key words ：Delaunay triangulated irregular network;ears;point deletion;topology structure;dual-circulation linked list 2008年2月计算机工程与设计 Feb.2008 第29卷第3期Vol.29 No.3 Computer Engineering and Design
平面点线集三角剖分的扫描算法
第24卷 第2期2004年2月北京理工大学学报 T r ansactions of Beijing Instit ute o f T echnolog y V ol.24 N o.2F eb.2004 文章编号:1001-0645(2004)02-0129-04 平面点线集三角剖分的扫描算法 周培德 (北京理工大学信息科学技术学院计算机科学工程系,北京 100081) 摘 要:提出计算平面点线集三角剖分的一种算法.该算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分.当扫描线达到最左边的事件点时,处理该事件点,就完成了平面点线集的三角剖分.证明了算法的时间复杂性为O (N lb N ),其中N 是点线集中点的数目与线段端点数之和. 关键词:散乱点线集;三角剖分;平面扫描;算法;时间复杂性中图分类号:T P 301.6 文献标识码:A Sweeping Algorithm for Triangulation of Plane Point -Line Set ZHOU Pei-de (Depar tment of Co mputer Science and Engineer ing ,School o f Infor matio n Science and T echno lo gy ,Beijing Instit ut e of T echno lo gy ,Beijing 100081,China) Abstract :Sw eeping alg orithm is presented fo r the tr iangulation of plane point -line set .T he algor ithm m akes use of the idea of plane sw eeping .When the sw eep -line reaches it ,the event -po int w ill be dealt w ith,viz.,the event-point is connected w ith so me points sw ept and thus the sw ept regions are triang ulated.When the sw eep-line r eaches the leftmost event-point,the point w ill be dealt w ith ,and the triang ulation of the plane point -line set is accom plished .It is prov ed in detail that the time co mplex ities o f the alg orithm is O (N lb N ),w here N is the sum of the num ber of points and the num ber of line-seg ment endpoints w ithin the point-line set. Key words :debunching point-line set;triang ulation;plane sw eep;alg orithm;tim e co mplex ity 收稿日期:20030321 作者简介:周培德(1941-),男,教授. 平面点集三角剖分问题是计算几何中的一个重要问题,它是从许多实际问题中提出来的,至今,人们已研究了求解该问题的许多算法,其中以Delaunay 算法最为著名.将平面点集中的某些点组成点对并满足某些特殊关系,比如它们为平面线段的两个端点,而另外一些点仍为孤立点,这样便构成点线集.平面点集三角剖分问题可以转换为平面点线集的三角剖分问题,并且它们具有相同的时间复杂性下界.平面点线集三角剖分问题要求三角形的三条边或为点线集中的线段,或为点线集中不同线段端点的连线,或为点线集中点与线段端点的连线, 或为点线集中点与点的连线.三角形的顶点为点线集中的点或线段端点.另外还要求连线与连线,连线与点线集中线段均不相交.给定的平面点线集中线段互不相交(线段端点处相交除外).不难看出,平面散乱点线集三角剖分问题是平面点集三角剖分问题的一个特殊情况.按照常规,求解平面点集三角剖分的算法(比如Delaunay 三角剖分算法)可以用于平面散乱点线集的三角剖分.但在平面点集三角剖分的算法中如何保证点线集中的线段必是三角形的一条边,以及连线与点线集中线段不相交.只要解决这个问题就可以实现点线集的三角剖分.目前解决这
- 三角网算法
- 、不规则三角网生成的算法
- 三角网构造原理
- 生成Delaunay三角网的合成算法-Read
- 不规则三角网(TIN)生成的算法
- 不规则三角网的算法设计与实现
- DELAUNAY三角网的算法
- aunay三角网合成算法
- Delaunay三角网算法
- 实体建模三角网相交算法及应用研究
- 不规则三角网的算法设计与实现10页word文档
- 生成Del aunay三角网合成算法
- 几种三角网生成算法的探讨
- 快速构建Delaunay三角网算法研究及OpenGL下三维可视化
- 基于不规则三角网构建的网格生长算法
- 生成Delaunay三角网的合成算法
- delaunay三角网生长准则及算法
- 不规则三角网的算法设计与实现