Voronoi and Delaunay

Math 282 Computational Geometry

(Based on code from Joseph O’Rourke.)

Delaunay triangulation

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

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

Create and store the Delaunay triangulation:

𝒟=DelaunayMesh[pts];
delaunayGraphic=HighlightMesh[𝒟,{Style[0,Blue,PointSize[Medium]],Style[1,Purple],Style[2,Opacity[0.2],Cyan]}]

Make a list of the circumcircles of the triangles:

listOfIndexes=First/@MeshCells[𝒟,2];
listOfTriPts=pts[[#]]& /@listOfIndexes;
listOfCircles=Circumsphere/@listOfTriPts;

Voronoi diagram

Create and store the Voronoi diagram:

𝒱=VoronoiMesh[pts,{{-2,2},{-2,2}}];
voronoiGraphic=HighlightMesh[𝒱,{Style[0,Orange],Style[1,Brown],Style[2,LightYellow]}]

Voronoi and Delaunay

Now show both the Voronoi diagram and the Delaunay triangulation:

Show[voronoiGraphic,delaunayGraphic]

Also show the circumcircles of the triangles:

Manipulate[Show[voronoiGraphic,delaunayGraphic,Graphics[{Opacity[0.5,Orange],Polygon[listOfTriPts[[i]]],Orange,listOfCircles[[i]]}],PlotRange->{{-2,2},{-2,2}}],{i,1,Length[listOfTriPts],1}]