东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2009, Vol. 30 ›› Issue (5): 733-736.DOI: -

• 论著 • 上一篇    下一篇

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

马洪滨;郭甲腾;何群;刘馨蕊;   

  1. 东北大学资源与土木工程学院;
  • 收稿日期:2013-06-22 修回日期:2013-06-22 出版日期:2009-05-15 发布日期:2013-06-22
  • 通讯作者: Guo, J.-T.
  • 作者简介:-
  • 基金资助:
    国家自然科学基金资助项目(40571137);;

Study on Delaunay triangulation algorithm for polygon with inside islets

Ma, Hong-Bin (1); Guo, Jia-Teng (1); He, Qun (1); Liu, Xin-Rui (1)   

  1. (1) School of Resources and Civil Engineering, Northeastern University, Shenyang 110004, China
  • Received:2013-06-22 Revised:2013-06-22 Online:2009-05-15 Published:2013-06-22
  • Contact: Guo, J.-T.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

1258

摘要： 提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法.该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外三角形的判定法则,剔除CD-TIN中的域外三角形,实现了带岛屿多边形的三角剖分.实验表明,该算法在含有大量岛屿的带岛屿多边形三角剖分中具有很高的时间效率和很强的鲁棒性,并成功将其应用到基于剖面的三维矿体建模与可视化系统中,解决了含有夹石或孔洞的矿体剖面多边形三角剖分问题,具有一定的实际应用价值.

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

Abstract: 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.

中图分类号: