Applet By Amit Rosner
following Java applet demonstrates how to construct a crust
curve from some
scattered points in the plane.
solution is simple, and involves two important concepts in computational
the Voronoi Diagram and the Delaunay Triangulation.
Let S be a finite set of points in the plane, and
let V be the vertices of the
Voronoi diagram of S. An edge between points s1, s2 (both belong to S)
belongs to the crust of S if there is a disk, empty of points in the union
of S and V, touching s1 and s2.
Therefore, the algorithm is simply as follows:
Let S and V be as stated above, and Let S' be the
union of S and V.
2) Let D be the Delaunay triangulation of S'.
3) An edge of D belongs to the crust of S if both its endpoints belong to S.
The applet extends an applet by Denis Constales that implements the triangulation
algorithm, that can be found at http://cage.rug.ac.be/~dc/alhtml/Delaunay.html.
paper by Nina Amenta, Marshall Bern and David Eppstein from 2.12.1997:
"The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction".