Patent ID: 8212814
Filing Date: 2012-07-03
Classification: G06F,G06T

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