find the Delaunay triangulation for a given list of points
list of 2-element lists representing n coordinates
This function computes a Delaunay triangulation of the region bounded by the sequence of line segments connecting the outermost of the input points, returning a sequence of two outputs: the set of triangles and an edge adjacency Matrix.
The Delaunay triangulation is a triangulation that maximizes the smallest angle of the triangles in the triangulation (i.e. it avoids thin triangles).
The triangles are returned in a set containing the three vertices of each triangle as integer references to the input points list.
The adjacency matrix is an n by n symmetric Matrix that contains a 1 in entry i,j if one of the triangle edges is from pointsi to pointsj, and 0 otherwise.
For this example we first construct a point list containing all points at coordinates (i,j) for i=0..4,j=0..4, and the center points of all enclosed squares (that is, (1/2,1/2)..(7/2,7/2)).
pts ≔ seq⁡0,j−1,j=1..5:
forito4dopts ≔ pts,seq⁡i−12,j−12,j=1..4,seq⁡i,j−1,j=1..5end do:
pts ≔ pts
Use the DelaunayTriangulation command to get the set of triangles (tris) and the adjacency matrix (amat) for the point list pts.
tris,amat ≔ DelaunayTriangulation⁡pts:
Build and display a plot of all triangles.
plt ≔ NULL:
forvintrisdoplt ≔ plt,ptsv1,ptsv2,ptsv2,ptsv3,ptsv3,ptsv1end do:
Note that in the preceding plot, many of the triangles are chosen randomly because there are two optimal choices for many of the subdivisions. A slight shift of the points will make the optimal triangulation unique:
forito4dopts ≔ pts,seq⁡i−12,j−0.49999,j=1..4,seq⁡i,j−1,j=1..5end do:
The GraphTheory[DelaunayTriangulation] command was introduced in Maple 16.
For more information on Maple 16 changes, see Updates in Maple 16.
Download Help Document