基于Delaunay算法的排土场可视化设计系统研究
|
摘要
露天矿山排土场可视化、空间查询、空间形体设计及计算的自动化,对排土场设计和生产管理具有重要意义及应用价值。本文的主要研究内容包括：
(1)分析了数字地面模型的表面建模方法及数字地形的表示,比较了规则格网与不规则三角网的特点,重点研究了Delaunay不规则三角网格的准则、特性、局部优化处理等地形建模基本理论和方法,归纳了三种经典Delaunay三角网生成算法并进行了比较分析。提出了一种快速构建凸包及两个子三角网优化合并的改进的分治算法,提高了子网合并的效率。
(2)分析了Delaunay三角网的等高线追踪算法,增强了地形模型地势起伏变化的效果。研究了限定性Delaunay三角网的生成,采用了删除影响域内对角线重新进行三角剖分的方法克服了多对角线交换算法交换对角线步骤环节计算繁冗的缺陷,有效地解决了约束边嵌入Delaunay三角网的问题。
(3)分析了排土场边坡设计的几种实际形状及排土场空间形体设计方案,总结了传统排土场土方量计算的方法,给出了基于Delaunay三角网的排土场土方量及占地面积计算方法,提高了排土场土方量、占地面积计算的效率和精度。
本文以Delaunay三角网建模算法为基础,以OpenGL和VC++6.0为工具,建立了一个排土场可视化设计系统,实现了排土场地形快速建模、排土场空间形体设计及排土场的计算功能,为排土场设计和生产管理提供了一种有效的技术手段。
Open mine dump visualization, spatial query, spatial design and calculation of automated form, on the dump design and production management has important significance and value. The main contents of this article:
(1) The surface of the digital terrain model and digital terrain modeling method that compares the regular grid and the characteristics of TIN, focus on the Delaunay Triangulation criteria grid, features, local optimization, etc. Terrain basic theory and method, summed up the three classical Delaunay triangulation algorithm and generate a comparative analysis. A fast convex hull construction and optimization of two sub-triangular partition of the improved combined algorithm not only improves the efficiency of terrain modeling, and the resulting Delaunay triangulation accuracy is very high.
(2) The Delaunay triangulation of the contour tracing algorithm, rugged terrain model enhances the effect of changes. Of the limited generation of Delaunay triangulation, remove the affected area with a diagonal re-triangulation method to overcome multiple diagonal exchanging algorithm calculating the exchange part of a protracted diagonal step defects, effectively solve the constrained edge embedded Delaunay triangulation problem.
(3) Analysis of the dump slope shape and design of several actual physical design of dump space program, summed up the traditional dump earthwork calculation method is presented based on Delaunay triangulation dump earthwork and covers an area of computing methods to improve the dump earthwork, covering an area of computing efficiency and accuracy.
In this paper, Delaunay triangulation modeling algorithm-based, OpenGL and VC ++6.0 as a tool for the establishment of a dump visual design system to achieve a rapid modeling terrain dump, dump body design and space Dump computing, for the dump design and production management technology provides an effective means.
(1)分析了数字地面模型的表面建模方法及数字地形的表示,比较了规则格网与不规则三角网的特点,重点研究了Delaunay不规则三角网格的准则、特性、局部优化处理等地形建模基本理论和方法,归纳了三种经典Delaunay三角网生成算法并进行了比较分析。提出了一种快速构建凸包及两个子三角网优化合并的改进的分治算法,提高了子网合并的效率。
(2)分析了Delaunay三角网的等高线追踪算法,增强了地形模型地势起伏变化的效果。研究了限定性Delaunay三角网的生成,采用了删除影响域内对角线重新进行三角剖分的方法克服了多对角线交换算法交换对角线步骤环节计算繁冗的缺陷,有效地解决了约束边嵌入Delaunay三角网的问题。
(3)分析了排土场边坡设计的几种实际形状及排土场空间形体设计方案,总结了传统排土场土方量计算的方法,给出了基于Delaunay三角网的排土场土方量及占地面积计算方法,提高了排土场土方量、占地面积计算的效率和精度。
本文以Delaunay三角网建模算法为基础,以OpenGL和VC++6.0为工具,建立了一个排土场可视化设计系统,实现了排土场地形快速建模、排土场空间形体设计及排土场的计算功能,为排土场设计和生产管理提供了一种有效的技术手段。
Open mine dump visualization, spatial query, spatial design and calculation of automated form, on the dump design and production management has important significance and value. The main contents of this article:
(1) The surface of the digital terrain model and digital terrain modeling method that compares the regular grid and the characteristics of TIN, focus on the Delaunay Triangulation criteria grid, features, local optimization, etc. Terrain basic theory and method, summed up the three classical Delaunay triangulation algorithm and generate a comparative analysis. A fast convex hull construction and optimization of two sub-triangular partition of the improved combined algorithm not only improves the efficiency of terrain modeling, and the resulting Delaunay triangulation accuracy is very high.
(2) The Delaunay triangulation of the contour tracing algorithm, rugged terrain model enhances the effect of changes. Of the limited generation of Delaunay triangulation, remove the affected area with a diagonal re-triangulation method to overcome multiple diagonal exchanging algorithm calculating the exchange part of a protracted diagonal step defects, effectively solve the constrained edge embedded Delaunay triangulation problem.
(3) Analysis of the dump slope shape and design of several actual physical design of dump space program, summed up the traditional dump earthwork calculation method is presented based on Delaunay triangulation dump earthwork and covers an area of computing methods to improve the dump earthwork, covering an area of computing efficiency and accuracy.
In this paper, Delaunay triangulation modeling algorithm-based, OpenGL and VC ++6.0 as a tool for the establishment of a dump visual design system to achieve a rapid modeling terrain dump, dump body design and space Dump computing, for the dump design and production management technology provides an effective means.
引文
[1]李志林,朱庆.数字高程模型[M]武汉大学出版社,2001
[2]陆玲,杨勇.计算机图形学[M]科学出版社,2006
[3]靳海亮,高井祥.三维地形可视化技术研究进展[J].测绘科学2006(06)：56-59.
[4]张超.地理信息系统[M]高等教育出版社,1995
[5]胡昌龙,易燕.数字高程模型DEM及其显示[J].黑龙江科技学院学报,2004,(04)：36-39.
[6]晓宇,戚爰伟,永会,魏志勇.基于分治策略的快速构建Delaunay三角网算法[J].沈阳建筑大学学报(自然科学版).2007,(05)：66-69.
[7]王永会,李玉梅,宋晓宇。高阶Delaunay三角网及生成算法研究[J]。计算机工程与应用,2008,44(27)：62-64.
[8]彭认灿,王家耀,田震,郭立新,陈子澎.基于凸壳构造技术的领海基点选取问题研究[J].测绘学报,2005,(01)：25-28.
[9]van Kreveld, Marc;L??ffler, Maarten;Silveira, Rodrigo. Optimization for first order Delaunay triangulations;Computational Geometry-Theory and Application; 09257721; 2010(4)
[10]张向京.基于离散点构建凸包算法的研究[J].测绘信息与工程,2000,(04)：32-38.
[11]栾晓岩.一种TIN生成算法及其三维显示[J].海洋测绘,2004,(05)：43-45
[12]赖鸿斌,李永树.基于不规则三角网的DTM若干问题的探讨[J].重庆交通学院学报,2004,(02)：77-80.
[13]刘立娜,徐云,贾进东,王鹏.边界为简单多边形的离散点Delaunay三角剖分及可视化研究[J].测绘科学,2005,(03)：17-19.
[14]李立新,谭建荣.约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法[J].计算机学报,1999,(10)：22-26.
[15]黄运保,王启付,武剑洁,黄正东.基于局部三维Delaunay的插值网格边界增量构造算法[J].工程图学学报,2004,(03)：86-89.
[16]武晓波,王世新,肖春生.一种生成Delaunay三角网的合成算法[J].遥感学报,2000,(01)：45-50.
[17]吴宇晓,张登荣.生成Delaunay三角网的快速合成算法[J].浙江大学学报(理学版),2004,(03)：61-63.
[18]Steve Y. W. Lam and Conrad H. W. Tang.Geometric Modeling Systems for Construction Surveying of Highway Tunnels. J. Surv. Engrg.129,146 (2003)
[19]张学军,张丽颖.数学形态学原理及应用[J].丹东纺专学报,2005,(02)：56-59.
[20]杨强,黄地龙,张洁.基于凸壳和二次优化的三角网生成算法[J].四川理工学院学报(自然科学版),2007,(01)：35-39.
[21]刘晓成,崔汉国,张星,王大宇.虚拟环境中多细节层次模型生成新算法[J].微计算机信息,2006(09)：57-59.
[22]王建华,徐强勋,张锐.任意形状三维物体的Delaunay网格生成算法[J].岩石力学与工程学报,2003,(05)：15-18.
[23]郭兆胜,张登荣.一种改进的高效Delaunay三角网的生成算法[J].遥感信息,2005(01)：322-327.
[24]钟剑龙.TIN DEM线性内插不确定性的随机过程模型[J].武汉大学学报(信息科学版).2010(02)：167-170.
[25]薛惠锋,吴慧欣,解丹蕊.OpenGL图形程序开发实务.[M].西北工业大学出版社,2005(06)：21-25.
[26]张丽艳,聂军洪,周来水,周儒荣.自适应三角网格模型重新布点算法的研究[J].计算机辅助设计与图形学学报.2002,(03)：234-239.
[27]黄丁发,卓健成.GPS相位观测值周跳检测的小波分析法.[J]《测绘学报》1997,(04)：312-316.
[28]De Floriani L and Puppo E.An on-Line Algorithm for Constrained Delaunay Triangulation CVGIP:Graphical Model and Image Processing.1992,54(3):290-300
[29]永超,胡月明.不规则三角网递归生长算法过程的动态实时可视化[J].工程图学学报,2007,(02)：337-339.
[30]杜晓辉,易宝才,孔德慧.一种边折叠三角网格简化算法[J].计算机工程2007,(12)：21-25.
[31]汤雪茜,陈天伟.土方量计算方法的探讨[J].资源网2008(06)：64-69.
[32]圣华,方源敏.利用凸壳建TIN的算法研究[J].昆明理工大学学报(理工版),2006,(02)：132-137.
[33]刘晓利,刘则毅,高鹏东,彭翔.基于尖特征度的边折叠简化算法[J].软件学报,2005(05)：33-36.
[34]陈希清,杨晓君,陈富文,高立宝.应用MAPGIS数字高程模型提取区域地球化学异常信息的方法探讨[J].地球学报.2009(01)：156-158.
[35]汪连贺,董江.Delaunay三角剖分的快速实现[J].海洋测绘,2005,(03)：63-66.
[36]永和,刘玉芳,王燕平.基于凸包切割的不规则三角网及其邻接关系的生成算法[J].河南理工大学学报(自然科学版).2007,(03)：122-126.
[37]宋哲,刘衍聪,牛文杰.GIS中TIN模型的实现算法.2003(12)：171-176.
[38]Gert Brouns, Alain De Wulf, and Denis Constales, Delaunay Triangulation Algorithms Useful for Multibeam Echosounding,2003 American Society of Civil Engineers:129-132.
[39]晓宇,戚爰伟,永会,魏志勇.基于分治策略的快速构建Delaunay三角网算法[J].沈阳建筑大学学报(自然科学版).2007,(05)：132-136.
[40]陈世元.平面域中的Delaunay三角算法[J].防爆机,2007,(04)：56-59.
[41]李春民,李仲学,王云海.“数字矿山”三维可视化研究[J].系统仿真学.2006(08)：32-37.
[42]牛铮.构建Delaunay三角网的改进算法[J].计算机用,2007,(01)：31-33.
[43]姚圣华,方源敏.利用凸壳建TIN的算法研究[J].昆明理工大学学报(理工版),2006,(02)：19-23.
[44]彭认灿,王家耀,田震,郭立新,陈子澎.基于凸壳构造技术的领海基点选取问题研究[J].测绘学报,2005,(01)：32-56.
[45]邢建业,程铭.D-TIN生成算法[J].水利科技与经济.2007(05)：22-26.
[46]周秋生,王延亮,马俊海.对TIN模型边界生成算法的究.2005(05)：35-39.
[47]王家耀,崔铁军,苗国强.数字高程模型及其数据结构[J].海洋测绘.2004(05)：12-15.
[48]赖鸿斌,李永树.基于不规则三角网的DTM若干问题的探讨[J].重庆交通学院学报,2004,(02)：77-80.
[49]曾芬芳,周 琴,姚 煜.基于边折叠的网格简化算法及其应用[J].计算机应用2002(1)：56-58.
[50]Malerei:Die Beziehung der Expressionisten August Macke, Franz Marc und Robert Delaunay ist Thema einer grossen Ausstellung in Hannover - eine fruchtbare Dreiecksgeschichte; Art-Hamburg; 01732781; 2009(06):66-68.
[51]P.J.GreenandR.Sibson, ComPutingDirichletTessellationsinthePlane, The Computer Joumal,1978,2(2):168-173.
[2]陆玲,杨勇.计算机图形学[M]科学出版社,2006
[3]靳海亮,高井祥.三维地形可视化技术研究进展[J].测绘科学2006(06)：56-59.
[4]张超.地理信息系统[M]高等教育出版社,1995
[5]胡昌龙,易燕.数字高程模型DEM及其显示[J].黑龙江科技学院学报,2004,(04)：36-39.
[6]晓宇,戚爰伟,永会,魏志勇.基于分治策略的快速构建Delaunay三角网算法[J].沈阳建筑大学学报(自然科学版).2007,(05)：66-69.
[7]王永会,李玉梅,宋晓宇。高阶Delaunay三角网及生成算法研究[J]。计算机工程与应用,2008,44(27)：62-64.
[8]彭认灿,王家耀,田震,郭立新,陈子澎.基于凸壳构造技术的领海基点选取问题研究[J].测绘学报,2005,(01)：25-28.
[9]van Kreveld, Marc;L??ffler, Maarten;Silveira, Rodrigo. Optimization for first order Delaunay triangulations;Computational Geometry-Theory and Application; 09257721; 2010(4)
[10]张向京.基于离散点构建凸包算法的研究[J].测绘信息与工程,2000,(04)：32-38.
[11]栾晓岩.一种TIN生成算法及其三维显示[J].海洋测绘,2004,(05)：43-45
[12]赖鸿斌,李永树.基于不规则三角网的DTM若干问题的探讨[J].重庆交通学院学报,2004,(02)：77-80.
[13]刘立娜,徐云,贾进东,王鹏.边界为简单多边形的离散点Delaunay三角剖分及可视化研究[J].测绘科学,2005,(03)：17-19.
[14]李立新,谭建荣.约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法[J].计算机学报,1999,(10)：22-26.
[15]黄运保,王启付,武剑洁,黄正东.基于局部三维Delaunay的插值网格边界增量构造算法[J].工程图学学报,2004,(03)：86-89.
[16]武晓波,王世新,肖春生.一种生成Delaunay三角网的合成算法[J].遥感学报,2000,(01)：45-50.
[17]吴宇晓,张登荣.生成Delaunay三角网的快速合成算法[J].浙江大学学报(理学版),2004,(03)：61-63.
[18]Steve Y. W. Lam and Conrad H. W. Tang.Geometric Modeling Systems for Construction Surveying of Highway Tunnels. J. Surv. Engrg.129,146 (2003)
[19]张学军,张丽颖.数学形态学原理及应用[J].丹东纺专学报,2005,(02)：56-59.
[20]杨强,黄地龙,张洁.基于凸壳和二次优化的三角网生成算法[J].四川理工学院学报(自然科学版),2007,(01)：35-39.
[21]刘晓成,崔汉国,张星,王大宇.虚拟环境中多细节层次模型生成新算法[J].微计算机信息,2006(09)：57-59.
[22]王建华,徐强勋,张锐.任意形状三维物体的Delaunay网格生成算法[J].岩石力学与工程学报,2003,(05)：15-18.
[23]郭兆胜,张登荣.一种改进的高效Delaunay三角网的生成算法[J].遥感信息,2005(01)：322-327.
[24]钟剑龙.TIN DEM线性内插不确定性的随机过程模型[J].武汉大学学报(信息科学版).2010(02)：167-170.
[25]薛惠锋,吴慧欣,解丹蕊.OpenGL图形程序开发实务.[M].西北工业大学出版社,2005(06)：21-25.
[26]张丽艳,聂军洪,周来水,周儒荣.自适应三角网格模型重新布点算法的研究[J].计算机辅助设计与图形学学报.2002,(03)：234-239.
[27]黄丁发,卓健成.GPS相位观测值周跳检测的小波分析法.[J]《测绘学报》1997,(04)：312-316.
[28]De Floriani L and Puppo E.An on-Line Algorithm for Constrained Delaunay Triangulation CVGIP:Graphical Model and Image Processing.1992,54(3):290-300
[29]永超,胡月明.不规则三角网递归生长算法过程的动态实时可视化[J].工程图学学报,2007,(02)：337-339.
[30]杜晓辉,易宝才,孔德慧.一种边折叠三角网格简化算法[J].计算机工程2007,(12)：21-25.
[31]汤雪茜,陈天伟.土方量计算方法的探讨[J].资源网2008(06)：64-69.
[32]圣华,方源敏.利用凸壳建TIN的算法研究[J].昆明理工大学学报(理工版),2006,(02)：132-137.
[33]刘晓利,刘则毅,高鹏东,彭翔.基于尖特征度的边折叠简化算法[J].软件学报,2005(05)：33-36.
[34]陈希清,杨晓君,陈富文,高立宝.应用MAPGIS数字高程模型提取区域地球化学异常信息的方法探讨[J].地球学报.2009(01)：156-158.
[35]汪连贺,董江.Delaunay三角剖分的快速实现[J].海洋测绘,2005,(03)：63-66.
[36]永和,刘玉芳,王燕平.基于凸包切割的不规则三角网及其邻接关系的生成算法[J].河南理工大学学报(自然科学版).2007,(03)：122-126.
[37]宋哲,刘衍聪,牛文杰.GIS中TIN模型的实现算法.2003(12)：171-176.
[38]Gert Brouns, Alain De Wulf, and Denis Constales, Delaunay Triangulation Algorithms Useful for Multibeam Echosounding,2003 American Society of Civil Engineers:129-132.
[39]晓宇,戚爰伟,永会,魏志勇.基于分治策略的快速构建Delaunay三角网算法[J].沈阳建筑大学学报(自然科学版).2007,(05)：132-136.
[40]陈世元.平面域中的Delaunay三角算法[J].防爆机,2007,(04)：56-59.
[41]李春民,李仲学,王云海.“数字矿山”三维可视化研究[J].系统仿真学.2006(08)：32-37.
[42]牛铮.构建Delaunay三角网的改进算法[J].计算机用,2007,(01)：31-33.
[43]姚圣华,方源敏.利用凸壳建TIN的算法研究[J].昆明理工大学学报(理工版),2006,(02)：19-23.
[44]彭认灿,王家耀,田震,郭立新,陈子澎.基于凸壳构造技术的领海基点选取问题研究[J].测绘学报,2005,(01)：32-56.
[45]邢建业,程铭.D-TIN生成算法[J].水利科技与经济.2007(05)：22-26.
[46]周秋生,王延亮,马俊海.对TIN模型边界生成算法的究.2005(05)：35-39.
[47]王家耀,崔铁军,苗国强.数字高程模型及其数据结构[J].海洋测绘.2004(05)：12-15.
[48]赖鸿斌,李永树.基于不规则三角网的DTM若干问题的探讨[J].重庆交通学院学报,2004,(02)：77-80.
[49]曾芬芳,周 琴,姚 煜.基于边折叠的网格简化算法及其应用[J].计算机应用2002(1)：56-58.
[50]Malerei:Die Beziehung der Expressionisten August Macke, Franz Marc und Robert Delaunay ist Thema einer grossen Ausstellung in Hannover - eine fruchtbare Dreiecksgeschichte; Art-Hamburg; 01732781; 2009(06):66-68.
[51]P.J.GreenandR.Sibson, ComPutingDirichletTessellationsinthePlane, The Computer Joumal,1978,2(2):168-173.