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.

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 has submitted a paper on this to the applied track of the 1999 ACM Symposium on Computational Geometry. I'll be joining the journal version.

• 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.

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