Core Library: Constrained Delaunay Triangulation

Constrained Delaunay Triangulation


This program uses a divide-and-conquer algorithm to compute the Constrained Delaunay Triangulation (CDT) of a planar straightline graph. The worst case time is O(n log n). The input and output files are basically in the .noff format, describing a set of points and line segments in the plane. Two related programs are included: (i) an OpenGL viewer for points and line segments, (ii) a random generator for planar points.

FILES:

NOTE: The paper is still a draft (12/2002). The code is written by Zhihua Wang, under the supervision of Chee Yap and Marsha Berger.