This program uses a divideandconquer 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.
6 points

19 points

1234 points

10,000 points
