Fortune´s algorithm for computing of Voronoi diagram
Input a set of point sites in the plane.
Output The Voronoi diagram
- Initialize the event queue Q with all site events, initialize an empty
status structure T and an empty doubly-connected edge list D.
- while Q is not empty
- do Remove the event with largest y coordinate from
Q
- if the event is site event occuring at the
site p
- then HandleSiteEvent(p)
- else
HandleCircleEvent(c),where c
is the leaf of T representing the arc that will disappear.
HandleSiteEvent(p)
- if T is empty, insert p onto it and return.
- Search in T for the arc a vertically above p. If the leaf
representing a has a pointer to a circle event in Q, then this
circle event is a false alarm and it must be be deleted from Q.
- Replace the leaf of T that represents a with a subtree having
three leaves. The middle leaf stores the new site p and the other two
leaves store the site q that was originally stored with a.Store
the tuples {p,q} and {q,p} representing the new
breakpoints at the two new internal nodes.
- Create new half edge records in the Voronoi diagram structure for the edge
separating V(p) and V(q), which will be traced by
the two new breakpoints.
- Check the triple of consequtive arcs where the new arc for p is the
left arc to see if the breakpoints converge. If so, insert the circle into
Q and add pointers between the node in T and the node in Q.
Do the same for the triple where the new arc is the right arc.
HandleCircleEvent(c)
- Delete the leaf c that represents the disappearing arc a from
T.Update the tuples representing the breakpoints at the internal nodes.
Delete all circle events involving afrom Q; these can be found using the pointers from the
predecessor and the successor of c in T.
- Add the center of the circle causing the event as a vertex record to the
doubly connected edge list D storing the Voronoi diagram under
construction. Create two half-edge records corresponding to the new breakpoint
of the beach line. Set the pointers between them appropriately.
- Check the new triple of consequitive arcs that has the former left neighbor
of a as its middle arc to see if the two breakpoints of the triple
converge. If so, insert the corresponding circle event into Q and set pointers between the new circle event
in Q and the corresponding leaf of T. Do the
same for the triple where the former right neighbor is the middle arc.
Back to the Applet Page
How to use this Applet