Today, I will give you the outline for Fortune's Sweepline algorithm for determining the Voronoi diagram and Delaunay triangulation of a point set. A picture is worth a thousand words, and so this post will probably clock in at several million as I generate a bunch of animations.
We begin with a point set:
I will then take a horizontal line starting above my point set, and 'sweep' it down across the point set:
I will then do the same thing again, but in addition to the sweep line, I will also take the points above the line, and draw parabolas corresponding to each point as a locus and the sweepline as the directrix:
Now, I will edit the previous animation by only drawing the pieces of the parabolas that are closest to the sweepline. The resulting wavy line is called the beachline, as it resembles the shape of a wave crashing against the beach:
Finally, I will draw the paths taken by the intersection points of adjacent arcs on the beachline:
These intersection points are tracing out the Voronoi edges!
In the next post, we will investigate WHY this process produces the diagram we seek.
No comments:
Post a Comment