第3 4卷第 1期 2 0 1 4年 0 1月
西
安
科
技
大学学
报
Vo 1 . 3 4 No .1
J OU R NA L O F X I’ AN UN I V ER S I T Y O F S C I E NC E A ND T E C H NO L O G Y
J a n . 2 0 1 4
文章编号: 1 6 7 2— 9 3 1 5 ( 2 0 1 4 ) 0 1— 0 0 5 2—0 5
带断层约束的 D e l a u n a y三角剖分混合算法 张群会,解子毅 (西安科技大学计算机科学与技术学院,陕西西安 7 1 0 0 5 4 )
摘
要:三角剖分是构建高精度数字高程模型( D E M)的基础,在各个领域都有广泛的应用。特别
是在约束数据域下的 D e l a u n a y三角剖分更具有重大的研究价值,前人已经做了大量的工作,并提出了一系列经典的剖分算法。在对传统算法进行研究与分析后,总结了传统算法的优缺点,结合 了逐点插入法、三角网生长法以及分治法的思想,提出了一种高效的、带断层约束的 D e l a u n a y三
角剖分混合算法。该算法在建立无约束的 D T ( D e l a u n a y T r i a n g u l a t i o n, D T )网格的基础上通过嵌入 加密后的断层数据来实现带断层约束的 C D T( C o n s t r a i n e d D e l a u n a y T r i a n g u l a t i o n, C D T)网格。通
过实例比较,说明了混合算法在构网质量和时间效率上都优于传统算法。 关键词: D e l a u n a y三角剖分;混合算法;加密;断层约束 中图分类号: T P 3 9 0 文献标志码:A
Mi x e d a l g o r i t h m o f d e l a u n a y t r i a n g u l a r s u b d i v i s i o n wi t h f a u l t c o ns t r a i n t
Z H A N G Q u n— h u i, X I E Z i— y i ( C o l l e g e o fC o m p u t e r S c i e n c e a n d T e c h n o l o g y, X i’ a n U n i v e r s i t y o fS c i e ce n a n d T e c h ol n o g y, X i’ a n 7 1 0 0 5 4, C h i n a )
Ab s t r a c t: T i r a n ul g a t i o n i s
t h e b a s i s o f b u i l d i n g a h i g h - p r e c i s i o n d i g i t a l e l e v a t i o n m o d e l( D E M) .I t h a s b e e n wi d e l y a p p l i e d i n v a i r o u s i f e l d s .E s p e c i a l l y,t i r a n g u l a t i o n i n c o n s t r a i n e d d a t a u n d e r t h e d o ma i n
D e l a u n a y h a s mo r e s i g n i i f c a n t r e s e a r c h v a l u e .Ma n y s c h o l a r s h a v e d o n e a g r e a t j o b, a n d p u t f o r w a r d a s e ie r s o f c l a s s i c t ia r n ul g a t i o n a l g o r i t h ms .Af te r r e s e a r c h i n g a n d a n a l y z i n g t h e t r a d i t i o n a l a l g o it r h ms,t h e
a d v a n t a g e s a n d d i s a d v a n t a g e s o f t r a d i t i o n l a lg a o i r t h ms a r e s u mme d u p .C o mb i n e d w i t h i n c r e me n t l a i n— s e r t i o n a l g o i r t h m,t r i a n g u l a t i o n ro g w t h a l g o i r t h m a s we l l a s t h e i d e o l o g i c a l d i v i d e a n d c o n q u e r a l g o i r t h m,
a h i g h l y e f f i c i e n t mi x e d lg a o i r t h m o f De l a u n a y t i r a n g u l a r s u b d i v i s i o n w i t h f a u l t c o n s t r a i n t i s p r e s e n t e d .
O n t h e b a s i s o f e s t a b l i s h i n g u n c o n s t r a i n e d D e l a u n a y t r i a n g u l a t i o n( D
T ), t h i s mi x e d lg a o i r t h m g e n e r a t e s c o n s t r a i n e d D e l a u n a y t i r a n ul g a t i o n( C D T )b y e m b e d d i n g t h e e n c r y p t e d f a u l t d a t a .I t i s i l l u s t r a t e d w i t h e x pe r i me n t t h a t t h i s mi x e d a l g o it r h m i s be t t e r t h a n t h e t r a d i t i o n a l a l g o it r h ms i n n e t wo r k q u a l i t y a n d t i me e f ic f i e nc y.
Ke y wo r d s: d e l a u n a y t r i a n ul g a r s u b d i v i s i o n; mi x e d lg a o r i t h m; e n c r y p t; f a u l t c o n s t r a i n t
言 目前比较流行的构建数据高程模型( D E M)的
兰 四边形 ( G R I D )网格法。和 G R I D相比, T I N能够
收稿日期: 2 0 1 3—1 1— 0 1 通讯作者:张群会 ( 1 9 5 6一),男,陕西咸阳人,教授, E - ma i l: 3 7 0 1 6 1 5 7 6@q q . c o r n

带断层地震数据的Delaunay三角剖分算法_专业资料。数据网格化是三维地质建模的常用方法。断层是普遍的地质现象,带断层的海量数据三角剖分在建模中较为复杂。提出了...
带断层的海量数据三角剖分在建模中较为复杂.提出一种简单的可以解决带断层Delaunay三角剖分有效算法.该算法首先对数据边界进行初始Delaunay三角剖分,然后将其变......
2008 文章编号: 1001-1986(2008)06-0070-03 带断层地震数据的 Delaunay 三角剖分算法刘少兵 (西安科技大学计算机科学与技术学院,陕西 西安 710054) 摘要:数据...
带约束折线的平面散点集Delaunay三角剖分_专业资料。首先将原始散点与约束点...该算法思路简捷,易于编程,生成的三角网形态优良。第3 4卷第1期 2 1年2月 ...
该算法首先 要 将带岛屿多边形的所有顶点统一构建基于多边形边约束的 Delaunay 不规则三角网 ( CD2 TIN ) ; 基于三角形顶 点绕向 ,提出了多边形域外三角形的...
带岛区约束数据域的Delaunay三角剖分通用算法研究_专业资料。文章提出了一种可解决带岛区约束数据域的三角剖分通用算法,通过对岛区制图边界拓扑结构建立与分析,...
Delaunay三角剖分插值算... 54人阅读 4页 2.00 带断层海量数据的De...约束Delaunay三角剖分...
带内外边界约束的平面点集Delaunay三角剖分_专业资料。算法首先将离散点与约束边界点一起进行Delaunay三角剖分,形成初始Delaunay三角网,然后将约束边界上的各条约束...
约束生长算法是生长算法的一个扩展.将两者结合可实现任意数据域的Delaunay三角剖分。提出了一种简单多边形三角剖分的约束生长算法。该算法的思想是基于生长算法.基...
约束数据域的Delaunay三角剖分与修改算法_电力/水利_工程科技_专业资料。第 ... 带断层约束的Delaunay三... 暂无评价 5页 3.00 基于边界特征点提取的...
热门文档