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

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

Study on Delaunay Triangulation Algorithm for Polygon with Inside Islets

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