带岛屿多边形Delaunay三角剖分算法  

Study on Delaunay Triangulation Algorithm for Polygon with Inside Islets

作　　者：马洪滨[1] 郭甲腾[1] 何群[1] 刘馨蕊[1] 

机构地区：[1]东北大学资源与土木工程学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2009年第5期733-736,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(40571137);国家高技术研究发展计划项目(2006AA12Z216)

摘　　要：提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法.该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外三角形的判定法则,剔除CD-TIN中的域外三角形,实现了带岛屿多边形的三角剖分.实验表明,该算法在含有大量岛屿的带岛屿多边形三角剖分中具有很高的时间效率和很强的鲁棒性,并成功将其应用到基于剖面的三维矿体建模与可视化系统中,解决了含有夹石或孔洞的矿体剖面多边形三角剖分问题,具有一定的实际应用价值.A universal algorithm for Delaunay triangulation of any polygon with or without islets is presented. In this algorithm, the constrained Delaunay triangular irregular network （CD-TIN） including all the vertices of a polygon, i.e. , the vertices of the polygon itself and vertices of all inside islets, is constructed, of which all the edges of the polygon are constrained, then the criterion for seeking triangles outside or inside the polygon is presented to identify or eliminate unwanted triangles from the CD-TIN so as to triangulate the polygon with inside islets. A testing triangulation experiment for a polygon with 100 inside islets was done with this algorithm, and the result showed that this algorithm is efficient and robust for triangulating complex polygons with large numbers of inside islets. This algorithm has been successfully applied to the three- dimensional ore-body modeling and visualization system, in which it is used to triangulate the sectional polygons with inside islets, e. g. , the inside stones or holes in ore-body, and its high efficiency has been proved.

关 键 词：三角剖分 岛屿 DELAUNAY三角网 约束数据域 多边形 地理信息系统 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]