Delaunay Triangulations

Math 282 Computational Geometry

(Based on code from Joseph O’Rourke.)

First, generate a set of 2D points with coords in [-1, 1] :

pts=RandomReal[{-1,1},{20,2}];

Graphics[{Blue,PointSize[0.02],Point[pts]},Frame->True]

Mathematica can easily create the Delaunay triangulation.  Mathematica gives us the triangulation as a “mesh region”:

ℛ=DelaunayMesh[pts];

Note that the symbol ℛ can be entered by EscscREsc.

Now show Delaunay triangulation.

delaunayGraphic=HighlightMesh[ℛ,{Style[0,Blue,PointSize[Medium]],Style[1,Purple],Style[2,LightCyan]}]

We can extract the 2D cells from the triangulation.

We will store the triangles in a list Δs. Note the cells are graphics objects Polygon, speficied using indices in our list pts.

Δs=MeshCells[ℛ,2]

We can also extract the indexes of the triangles.

We can do this by looping over triangles in the list Δs:

listOfIndexes={};
Do[
AppendTo[listOfIndexes,tri[[1]]],  (* need [[1]] to get the indices from the polygon *)
{tri,Δs}]
listOfIndexes

Now we will convert the indexes to 2D coordinates (ordered pairs)

Here is a simple way to do it:

listOfTriPts = {};
Do[
AppendTo[listOfTriPts,pts[[idx]]],
{idx,listOfIndexes}];
listOfTriPts

We can then display both the Delaunay triangulation and the circumsphere of a triangle

c1=Circumsphere[listOfTriPts[[1]]]

Show[
delaunayGraphic,
Graphics[{LightGreen,Polygon[listOfTriPts[[1]]],Green,c1}],
PlotRange->{{-2,2},{-2,2}}
]

Can you show the circumcircles of all triangles in the Delaunay triangulation?