CIS677 - Voronoi Sweepline Algorithm

User Guide

The applet demonstrates the sweepline algorithm to calculate Voronoi diagrams (and Delaunay graph) of a set of sites in the plane.

Basic Operations

It is possible to insert new sites into the plane by simply clickling into the plane where the new site should be located. The new Voronoi diagram will be calculated and displayed instantaneously.

Furthermore, it is possible to move sites within the plane to new positions. Again, the Voronoi diagram and the Delaunay graph will be calculated and displayed immediately.

The plane can be emptied by pressing the button "Reset" on the left side of the applet.

Showing the Steps of the Sweepline Algorithm

All the steps of the sweepline algorithm can be demonstrated in an automated sequence for the current set of sites in the plane by pressing the button "Demo". If there is no or only one point in the plane, pressing the button "Demo" will firstly lead to the insertion of 50 random sites in the site.

Of course, the display of the steps might go too fast and it is possible to interrupt the sequence by pressing on of the button on the right side of the applet. The execution stops at a certain point and it is possible to go backward and forward in the execution of the sweeline algorithm by pressing "<<" and ">>". The automatic execution can always resumed by pressing "Demo" again.

The sweepline steps, of course, could be considered as being a continuous sequence so that the sweepline goes from the top to the bottom of the plane. In the sweepline demo used here, only the sweeplines are displayed whenever an sweep event occurs and in the middle between two sweepevent. During each of the sweepline steps, the following information will be displayed:

The sweepline and the beachline (green)
The line segments that will belong to the final Voronoi diagram (blue)
The lines that are currently in the internal edgelist and which might become part of the final Voronoi diagram (red)
The intersection points that impose a new sweep event that could lead to a new point in the Voronoi diagram. The intersection point is displayed with a vertical line leading to the associated sweep event.

It is possible to show the Delaunay graph instead or in addition to the Voronoi diagram. For this reason, the two checkboxes on the right side are used. The status can be changed at any time.

The Delaunay edges are drawn in color magenta. The Delaunay dual of the current sweepline lines are drawn in orange, which form a polygon that encloses all already known Delaunay edges. The sweepline algorithm simply extends this polygon.

It is possible to show the circles that are used during the sweepline algorithm by pressing button "Show circles". Note that the heap is empty at the end of the sweepline algorithm so that no circles are visible after finishing up. Therefore, these circles do not represent the cirumference of the Delaunay triangles (although each circumference of a Delaunay triangle has to be a heap circle at some point during the sweepline algorithm !).

Showing each Sweepline Step in more detail

By pressing the button "Show detail", it is possible to show each (forward) step of the sweepline algorithm in detail. Elements like sites and lines that are involved in the current step are highlighted and modified.

Implementation

The implementation is based on Steve Fortune's sweepline algorithm. THe current events are maintained on a heap. "Unfinished" edges are maintained in an doubly connected list. To make the implementation more efficient, the popular halfedge approach has been implemented. The internal representation of coordinates is in "float"-values. Obviously, this can be insuffucient for certain degenerate cases. It should be very easy to change the coordinate type from "float" to "double". An implementation of the type as an arbitry-length numbers would be useful. But due to the critical computational speed especially in Java, the arbitry-length number implementation has not been considered.

Hartmut Liefke