Fast Constrained Delaunay Triangulation for Planar Polygonal Domains

Based on the incremental idea and the uniform grid, constrained Delaunay triangles can be computed in local ranges for arbitrary planar polygonal domains. No triangles outside the valid region of the domain are computed and for domains with polylines, scattered points and holes, no extra operations are specially required. The tested analysis shows that for simple polygonal domains randomly generated, the algorithm is efficient in computation and has an almost linear run time. Furthermore, the algorithm is optimized on a special kind of polygons formed by the boundary of such band-images as texts, industrial patterns etc., with their characteristic of approximately equal width fully utilized. The feature has been applied for efficient skeleton extraction of band-like images.