基于凹凸顶点判定的简单多边形Delaunay三角剖分

DELAUNAY TRIANGULATION OF SIMPLE POLYGON BASED ON DETERMINATION OF CONVEX-CONCAVE VERTICES

摘要: 提出一种基于凹凸顶点判定的简单多边形Delaunay三角剖分算法.该算法首先求出简单多边形的凹凸顶点,然后,逐次割去一个权值最大的三角形构造三角形网格,修改多边形顶点链表,并重新计算受影响的顶点的凹凸性.重复这个过程,直到边界顶点链表空为止.

Abstract: This paper presents a fast algorithm for Delaunay triangulation of simple polygon based on determination of convex-concave vertices．Its basic idea is to calculate convex-concave vertices first，then get a triangle with maximum weight，delete the vertex and modify linked list．Repeat above steps until termination condition is met．