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:

• cdt.tar: contains source code and test data.

  If you also want our paper on Constraint Delaunay Triangulation which describes the algorithm, then download cdtall.tar.

  Some Images
  

  6 points	19 points	1234 points	10,000 points

  Click pictures to see graphs before and after trianglualtion.