Generating Wavefronts
A wavefront is composed of the minimum of parabolas formed by sites and a sweep line. Any point on a parabola is equidistant from the site and the sweep line.
As we sweep a line to create the Voronoi diagram, we maintain the invariant that every point already surpassed by the wavefront is known to belong to a specific Voronoi region.
Some Basics
- To create a Voronoi diagram, we start with a list of sites
- Each Voronoi region is associated with a site
- At each step of the sweep, our wavefront is determined by a set of arcs, which are parabolas defined by sites
- We add an arc to the wavefront when we encounter a new site with our sweep line
- This is called a Site Event
- We delete an arc when its two adjacent arcs intersect, creating a Voronoi vertex
- This is called a Circle Event
- Events are handled in order of priority where the highest priority event is the event the sweep line will encounter next
Parabola Math
A parabola in the wavefront is generated by a site, which is the focus, and the position of the sweep line, which is the directrix. As the sweep line moves past a site, the parabolic arc associated with that site changes.
Sweeping
Sites →blue
Wavefront → purple
Sweep line → black
Drag the black point to move the sweep line
Drag the blue points to change site location
Drawing Edges
Arcs change as the sweep line moves downwards because they are defined by a site and the sweep line.
As the sweep line continues to move, the intersecting arcs draw out their Voronoi edges (green lines).
Use the black dot to adjust the sweep line.
Adding and Removing Arcs
When the sweep line hits a Site Event, a parabola is computed for the new site and spliced into the existing wavefront. On the left, the sweep line has encountered the site (0, 0). When the sweep line is y = 0, the parabola for site (0, 0) is infinitely narrow. As the sweep line moves past y = 0, the parabola grows wider. To visualize the addition of the arc, the sweep line is currently at y = -0.01.
As the sweep line moves towards the Circle Event for a triple of sites, the range of the middle arc is getting increasingly shorter. The arcs for all three sites intersect at the Voronoi vertex and at that time, the middle arc consists of a single point. This middle arc is removed from the wavefront.
When the sweep line reaches a Circle Event, a Voronoi vertex is recorded at the center of a circle defined by the three sites. The Voronoi vertex marks the intersection of three edges of Voronoi regions.
Adding an arc for site (0, 0)
Removing an arc for site (0, 5)
Voronoi Diagrams
After the sweep line surpasses all events, all edges for Voronoi regions have been drawn. In the Voronoi diagram for sites [(0, 0), (0, 5), (4, 3)], all red points are closer to site (0, 0) than any of the other sites. All orange points are closest to site (4, 3) and all green points are closest to site (0, 5).
The edges of the regions, which were created by intersecting parabolas, are points equidistant to the sites on either side of the edge. A Voronoi vertex, which was created by the center of a circle defined by three points, is equidistant to the three sites it bounds.
A Voronoi region is unbounded if and only if its site lies on the convex hull of the sites.
Voronoi Diagram for sites [(0, 0), (0, 5), (4, 3)]
Voronoi Diagram for sites [(0, 0), (0, 5), (4, 3), (1, 2), (2.5, 0)]