一种基于最小搜索圆平面多边形域约束Delaunay三角剖分算法

Constrained Delaun Triangulation Algorithm for Planar Polygonal Domains Based on Minimum Search Circle

给出一种新的基于边优先的二维多边形域任意散乱数据的约束Delaunay三角剖分算法.算法结合网格分块技术,提出基于最小搜索圆的点搜索思想,并证明了该思想的正确性,有效地提高了搜索"第三点"的速度.算法中散乱数据可以是任意复杂的折线、封闭多边形环及离散点.另外,在三角剖分过程中,实时地去掉封闭点和封闭边,极大地加快了构网速度,实现了平面多边形域散乱数据的快速约束Delaunay三角化.

This paper presents a new algorithm based on the edge priority for Constrained Delaunay Triangulation of arbitrary data scattered in 2D region with polygonal boundary. Combining with grid partition technology, the new algorithm presents the point searching idea based on minimum search circle. The new idea is proved correctly and improves the speed of searching the third point effective- ly. The characteristic constraints of the data could be complicated broken lines, closed polygons and scatter points. Besides , removing the occluded edges and occluded points can accelerate the speed of triangulation and realize the Constrained Delaanay Triangulation fast.