3, :Delaunay DEM 45 0 (DEM), Delaunay [123 ], Delaunay DEM, [ 4210 ],,, ;, ;,,,,,,,, 1, Delaunay,, 4, (LOP) : ;,, ; P, P t, P t 3, ; LOP ; 2 TIN ( ),,

Size: px

Start display at page:

Download "3, :Delaunay DEM 45 0 (DEM), Delaunay [123 ], Delaunay DEM, [ 4210 ],,, ;, ;,,,,,,,, 1, Delaunay,, 4, (LOP) : ;,, ; P, P t, P t 3, ; LOP ; 2 TIN ( ),,"

垒齐
5 years ago
Views:

1 ( ) Journal of Changπan University (Natural Science Edition) Vol. 28 No. 3 May 2008 : (2008) Delaunay D EM 1, 1,2 (1., ; 2., ) : D EM ( ),, Delaunay,, DEM, DEM, :,, DEM : ; ; ;Delaunay ; :U :A Entire optimized triangulation algorithm of Delaunay triangle net work for DEM construction MA Zhi2min 1, L UO Bin 1,2 (1. School of Earth Sciences and Resources, Changπan University, Xiπan , Shaanxi, China ; 2. Institute of Geography Science and Natural Resources, Chinese Academy of Science, Beijing , China) Abstract : Aiming at t he poor efficiency, slow speed, poor shape properties of t he triangulation and the low accuracy in existing DEM construction methodologies for road determining systems, t his paper st udied t he factors which influence t he efficiency of Delaunay t riangulatio n of constrained data set after t he analysis of extant algorit hm, proposed an entire optimized algorit hm based o n Delaunay t riangulatio n of co nst rained data set. The met ho d and p rocedure are discussed, as well as how to merge t he highway designed surface mo del into t he D EM. Meanwhile, the optimized algorithm was applied in t he highway locating as a case study. The result shows t hat : t his new algorithm can p ut t he highway design surface model toget her wit h t he digital terrain model, and has the characteristics of constructing net quickly, being superior in t he net shape, having high p recise in algorit hm co mp utatio n, it o bvio usly has t he advantage of building D EM in road location and design systems. 7 figs, 10 ref s. Key words : road engineering ; highway locating ; D EM ; Delaunay t riangulatio n ; co nst rained data set : : (2002BA901A43) : (19572),,,,,E2mail edu. cn

2 3, :Delaunay DEM 45 0 (DEM), Delaunay [123 ], Delaunay DEM, [ 4210 ],,, ;, ;,,,,,,,, 1, Delaunay,, 4, (LOP) : ;,, ; P, P t, P t 3, ; LOP ; 2 TIN ( ),,, 1, A 1 A 2 A 3 A 1 ( x1, y1 ) A 2 ( x2, y2 ) A 3 ( x3, y3 ), P( x, y), A 1 A 2 A 3 S1 S2 S3 : S1 = V 1 / V, S2 = V 2 / V, S3 = V 3 / V :V A 1 A 2 A 3 ;V 1 V 2 V 3 A 2 A 3 P A 3 A 1 P A 1 A 2 P,, P, P ( S1, S2, S3 ) S1 = ( y - y2 ) ( x3 - x2 ) - ( y3 - y2 ) ( x - x2 ) S2 = ( y - y3 ) ( x1 - x3 ) - ( y1 - y3 ) ( x - x3 ) S3 = ( y - y1 ) ( x2 - x1 ) - ( y2 - y1 ) ( x - x1 ) P P ( S1 S2 S3 ) : S1 > 0 S2 > 0 S3 > 0 P ; S1 < 0 S2 < 0 S3 < 0 P ; S1 = 0 S2 = 0 S3 = 0 P 1 P, 0 ; P, 0 ( 2) ; P AB C, BC, P S 1 < 0, S2 > 0, 2. 1,, ( 2) AB C CB D B ED D EG EFG FH G P 1, ( ( ) :S 1 1 < 0, S 1 2 > 0, S 1 3 > 0 ) 0 ( 2 BC ), 2, : S 2 1 < 0, S 2 2 >, 0, S 2 3 > 0 S3 > 0, 0 TIN,

3 46 ( ) ( BD ) 3,, P 6 : S 6 1 < 0, S 6 2 > 0, S 6 3 > 0 P 3 0, P 6 ( FH G) 2. 2 Delaunay,, A 7,, :S 1 < 0, S2 > 0,, S3 > 0 ( ), 0, A 2 A 3, ; A 7, : S1 < 0, S2 > 0, S3 > 0,, 0 A 2 A 4,,, A 7, : S1 = 0, S2 > 0, S3 = 0,, :,,,,,,,, 3, A 1 A 2 A 3 A 3 A 2 A 4 A 2 A 5 A 4 A 4 A 5 A 6 A 5 A 7 A 6, A 1 P, P A 1 A 1, :,, ;,, 3,, 3, A 1 A 7 A 5 A : A 2 A 3 A 2 A 4 A 5 A 4, Delaunay,,,, : ;,,, ;,,,,,

第3期马智民,等 :Delaunay 三角网构建 D EM 整体优化算法边形内, 便删除三角形 ; 否则, 保留三角形作者采用交点计数检验法, 判断点是否在多边形内这种方法能同时处理多边形是凸多边形和凹多边形的情况,甚至多边形带孔的情况也能处理具体做法是, 从判断点沿某一方向 ( 一般是 x 或 y 轴 ) 作一射线至无穷远,求射线与多边形所有边的交点个数若

D EM 的拼合将道路选线边缘线与 D EM 的交线作为多条约束线段嵌入原始 D EM 的结果见图 5 ; 将道路设计表面三维模型叠加到 D EM 的结果见图 6 图5 将边缘交线作为多条约束图 6 线段嵌入原始 DEM 图4 3 两个岛状约束区域嵌入程序生成平面效果对比道路表面模型与 D EM 的拼合在公路路线设计三维模拟中, 主要设计两个重要的三维模型 :

技术,开发实现了一套公路定线三维仿真系统用户只需给定公路设计中心线路面宽 ( 或公路等级 ) 和填挖坡率,该系统就可以快速生成真实剖面图横断面图纵断面图和填挖边坡面, 并对工程量进行统计,生成工程量表, 从而最终输出设计结果, 并对结果进行三维模拟显示在公路设计中, 将道路表面三维模型叠加到三维地面模型, 对设计结果进行三维仿真的效果见图 7 得的坡脚 ( 顶)

4 第3期马智民,等 :Delaunay 三角网构建 D EM 整体优化算法边形内, 便删除三角形 ; 否则, 保留三角形作者采用交点计数检验法, 判断点是否在多边形内这种方法能同时处理多边形是凸多边形和凹多边形的情况,甚至多边形带孔的情况也能处理具体做法是, 从判断点沿某一方向 ( 一般是 x 或 y 轴 ) 作一射线至无穷远,求射线与多边形所有边的交点个数若个数为奇数,则点在多边形内 ; 否则,点在多边形外图 4 为两个岛状约束区域嵌入生成的平面效果对比,图 4 ( a) 为未嵌入约束区域 ; 图 4 ( b ) 为嵌入两个岛状约束区域后的结果由图 4 很明显地看出, 嵌入约束区域后,DEM 的地形细部反映地更加精确了就是将有公路或边坡的地方镂空 ( 5) 将镂空区域用公路填坡挖坡等道路表面设计三维模型填充, 实现道路表面模型和 D EM 的拼合将道路选线边缘线与 D EM 的交线作为多条约束线段嵌入原始 D EM 的结果见图 5 ; 将道路设计表面三维模型叠加到 D EM 的结果见图 6 图5 将边缘交线作为多条约束图 6 线段嵌入原始 DEM 图4 3 两个岛状约束区域嵌入程序生成平面效果对比道路表面模型与 D EM 的拼合在公路路线设计三维模拟中, 主要设计两个重要的三维模型 : 一个是精密的地面三维模型 D EM ; 另一个是道路表面模型这两个模型的拼合在公路路线设计及三维模拟中起着十分重要的作用利用带约束数据域 Delaunay 三角剖分算法既能构建高精度的 D EM,又能够很好地实现两个模型的拼合具体思路是 : 首先计算出拼合交线 ( 将横断面设计所 47 道路表面设计三维模型叠加到 DEM 基于此算法, 在 VC + + 环境下结合 Open GL 技术,开发实现了一套公路定线三维仿真系统用户只需给定公路设计中心线路面宽 ( 或公路等级 ) 和填挖坡率,该系统就可以快速生成真实剖面图横断面图纵断面图和填挖边坡面, 并对工程量进行统计,生成工程量表, 从而最终输出设计结果, 并对结果进行三维模拟显示在公路设计中, 将道路表面三维模型叠加到三维地面模型, 对设计结果进行三维仿真的效果见图 7 得的坡脚 ( 顶) 点首尾相连,并在路线及桥梁隧道的起终断面处封闭 ) ; 然后应用带约束数据域 Delaunay 三角网构建算法, 将上述交线作为约束边嵌入到原地面三角网中, 再采用三角网裁剪算法吞噬交线所围区域内的三角形 ( 约束区域嵌入算法) ; 最后将已建好的道路表面模型叠加到上述裁剪后的 D EM 中,得到道路表面与地面拼合紧密的三维整体模型具体的实现过程如下所述 ( 1) 提取道路表面及边坡最大影响范围内的点, 以后所有的计算都是基于这些点 ( 2) 求出公路表面及边坡区域边缘与 D EM 的所有交点 ( 3) 将这些交点首尾连接起来,得到公路表面及图7 4 公路设计的三维仿真效果结语 ( 1) 数字地面模型是公路设计中连接野外勘测边坡区域边缘与 D EM 的交线 ( 多条线段构成 ), 将 (数据采集) 和内业设计 ( CAD 系统) 之间的纽带,在上述交线看作多条约束线段嵌入到 D EM 中 ( 4) 把边缘交线多边形内的所有三角形镂空,也公路设计 CAD 系统中起着重要的作用本文提出的约束数据域 Delaunay 三角剖分优化算法具有明

5 48 ( ) 2008 (2),,, (3),, O( N),,,, : References : [ 1 ] Miles R E. Solution to problem (probability distribution of a network of triangles) [ J ]. SIAM, 1969, (11) : [ 2 ] Sibson R. Locally equiangular triangulations[j ]. Compu2 ter Journal,1978,21 (3) : [ 3 ] Lingas A. The greedy and Delaunay triangulations are not bad in the average case [ J ]. Processing Letters,l986,22 : Information [ 4 ] Lee D T, Schacheer B J. Two algorithms for constructing a Delaunay triangulation [ J ]. International Journal of Computer and Information Science,1980,9(3) : [ 5 ] Lawson C L. Software for C surface interpolation [ M ]. New York :Academic Press,1977. [ 6 ] Watson D F. Computing the n2dimension Delaunay tessellation with application to Voronoi polygons[j ]. Computer Journal,1981,24 (2) : [ 7 ],,. [J ].,2000,13 (2) : L IU Xue2jun, FU Xin2sha, ZHAO Jian2san. A study of algorithm for fast constructing triangulation irregular net ( TIN) [ J ]. China Journal of Highway and Transport,2000,13 (2) : [ 8 ],,,. GIS TIN [J ]., 2002,25 (11) : ZHAN G Xiao2can, HUAN G Zhi2cai, DAI Qi2cheng, et al. An algorithm of speedily building TIN based on topological structure and convex shell in GIS[J ]. Chinese Journal of Computers,2002,25 (11) : [ 9 ],,. [J ].,2003,23 (4) : L IU Shao2hua, CH EN G Peng2gen, CH EN Hong2 hua. Study of algorithm for triangulation of restrained data set with islet s [ J ]. Computer Applications,2003,23 (4) : [10 ],,. Delaunay [J ].,1999,28 (1) : WU Xiao2bo, WAN G Shi2xin, XIAO Chun2sheng. A new study of Delaunay triangulation creation[j ]. ACTA Geodaetica et Cartographic Sinica,1999,28 (1) : ( 24 ) [ 2 ],,,. : [ R]. :,2005. [ 3 ] Nishizawa T, Fukute T, Kokubun S. Study of a method for analyzing the mechanical behavior of composite pavement [ C ]/ / TRB. Transportation Research Record Washington D C : TRB,1999 : [ 4 ],,. [J ].,2006,19 (3) : WAN G Xiao2fei, SH EN Ai2qin, ZHU Jian2hui. Properties of microcrack mending of granulated ground blast f urnace slag modified microfine cement [J ]. China Journal of Highway and Transport,2006, 19 (3) : [ 5 ],. [ M ]. :,1999. [ 6 ],,,. [J ].,2006,6 (3) : SONG Huan2sheng, ZHAO Xiang2mo, WANG Guo2qiang, et al. Ultrasonic2tomography system for nondestructive concrete structure testing [J ]. Journal of Traffic and Transportation Engineering,2006,6 (3) : [ 7 ],,. [J ].,2003,16 (2) : TAN Zhi2ming, YAO Zu2kang, L IU Bo2ying. Thermal stress analysis of two2layered concrete slabs [ J ]. China Journal of Highway and Transport,2003,16 (2) : [ 8 ],,. [J ].,2005,5 (4) : L I Zhu2long, WU De2ping,ZHANG Ya2zhou. Durabilities of polymer cement materials in highway engineering [J ]. Journal of Traffic and Transportation Engineering, 2005,5 (4) : [ 9 ],,. [J ].,2006,19 (1) : L I Shu2ming, XU Zhi2hong, CA I Xi2mian. Analysis of impact of geo2textile on stress of composite pavement structure[j ]. China Journal of Highway and Transport,2006,19 (1) : [10 ] J T G D , [ S].

2 3. 1,,,.,., CAD,,,. : 1) :, 1,,. ; 2) :,, ; 3) :,; 4) : Fig. 1 Flowchart of generation and application of 3D2digital2building 2 :.. 3 : 1) :,

2 3. 1,,,.,., CAD,,,. : 1) :, 1,,. ; 2) :,, ; 3) :,; 4) : Fig. 1 Flowchart of generation and application of 3D2digital2building 2 :.. 3 : 1) :, 3 1 Vol. 3. 1 2008 2 CAA I Transactions on Intelligent Systems Feb. 2008, (,210093) :.,; 3., 3. :; ; ; ; : TP391 :A :167324785 (2008) 0120001208 A system f or automatic generation of 3D building models