Patent Document ID: 8212814
Application ID: 13049561
Patent Flag: 1

Claim One:
1. A computer-implemented method for generating a constrained Delaunay triangulation for a planar domain with boundaries and internal features, the method comprising the following steps, at least one of which is implemented using a computer: approximating the boundaries and internal features of the domain with polylines; constructing unconstrained Delaunay triangulation for the domain; modifying the unconstrained Delaunay triangulation to conform triangle sides to the polylines; and correcting the modified triangulation to make it a constrained Delaunay triangulation, wherein correcting the modified triangulation to make it constrained Delaunay triangulation comprises an iterated mesh correction procedure performed by snapping an interior point to a feature segment such that when the interior point is a vertex of a triangle opposite a feature edge and the angle at the vertex is obtuse, the interior point is projected onto the feature edge followed by a swap of the feature edge, moving a point from a feature segment into the interior when the interior point is opposing feature edges on the same feature segment in at least three triangles and a summary of the angles at the point is acute, such that during this one of the edges connecting the interior point and said point is shrunk, repositioning all points to mass centers of their Voronoi regions, and recursively applying local edge-swap to non-feature edges until all non-feature edges of triangulation are optimal.