Home Bookmarks Papers Blog

Curve Reconstruction

Applet By Amit Rosner


            The following Java applet demonstrates how to construct a crust curve from some
            scattered points in the plane.

            The solution is simple, and involves two important concepts in computational geometry:
            the Voronoi Diagram and the Delaunay Triangulation.

            Definition: 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:

            1) 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.


        Set of points                      Voronoi diagram                Delaunay triangulation
                                                                                  (the crust highlighted)

            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.

            Reference: paper by Nina Amenta, Marshall Bern and David Eppstein from 2.12.1997:
                          "The Crust and the Beta-Skeleton: Combinatorial Curve Reconstruction".