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
What kind of issue would you like to report? (Optional)