Voronoi Diagrams

Math 282 Computational Geometry

(Based on code from Joseph O’Rourke.)

Voronoi Diagram from a set of points

Generate some 2D points (sites) with coords in [-1, 1]:

pts=RandomReal[{-1,1},{30,2}];
Graphics[{Blue,PointSize[0.02],Point[pts]},Frame->True]

Mathematica can compute the Voronoi diagram, giving it to us as a “mesh region”:

𝒱=VoronoiMesh[pts,{{-2,2},{-2,2}}];

The argument {{-2,2},{-2,2}} specifies the bounding region in which the Voronoi mesh is computed. Note that Mathematica always computes bounded Voronoi diagrams, while our text defines Voronoi diagrams as being unbounded.

Now draw the sites and the Voronoi diagram:

Show[{
HighlightMesh[𝒱,{Style[0,Blue],Style[1,Purple],Style[2,LightCyan]}],
Graphics[{PointSize[Medium],Orange,Point[pts]}]
}]

Interactive Voronoi Diagram

The following code produces an interactive Voronoi Diagram: you can move the points and see how the Voronoi cells change. ⌘-click or Alt-click to add or delete points.

npts=10;
b=1.5;
Manipulate[
HighlightMesh[VoronoiMesh[pts,{{-b,b},{-b,b}}],{Style[0,Blue],Style[1,Purple],Style[2,LightCyan]}],
{{pts,RandomReal[{-1,1},{npts,2}]},Locator,LocatorAutoCreate->{2,∞}}
]