Delaunay triangulation

This applet shows the crust and the anti-crust that can be obtained from the Voronoi diagram/Delaunay triangulation of a set of points.

• Click points in the screen.
• Select from the menu to choose whether to see the Delaunay, Voronoi or Crust.
• Reset clears all points.
• Redraw redraws.

The crust is named by Amenta~et al., who give a two-step algorithm to reconstruct a curve from a set of sample points that satisfy a density condition that depends on "local feature size". Christopher Gold observed that you could get something like their crust just from a single Voronoi diagram by selecting which edges to draw as Delaunay and which edges to draw as Voronoi edges. I showed that Chris' computation gives the same reconstruction as the original crust if the sample satisfies the same conditions. (It can be different when the samples do not respect "local feature size".)

Christopher Gold and I have submitted a joint paper, "A One-Step Boundary and Skeleton Extraction Algorithm," to a special issue of Algorithmica. We have a pdf version, which is still close to 4Mbytes because of the number of figures.

Code by Jack Snoeyink, University of British Columbia.
Back to Jack's Computational Geometry Demo page.