GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/DelaunayTriangulation

GraphTheory

  

DelaunayTriangulation

  

find the Delaunay triangulation for a given list of points

 

Calling Sequence

Parameters

Description

Examples

Compatibility

Calling Sequence

DelaunayTriangulation(points)

Parameters

points

-

list of 2 element lists representing n coordinates

Description

• 

This function computes a Delaunay triangulation 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.

Examples

withGraphTheory:

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)).

ptsseq0,j1,j=1..5:

forito4doptspts,seqi12,j12,j=1..4,seqi,j1,j=1..5end do:

ptspts

pts:=0,0,0,1,0,2,0,3,0,4,12,12,12,32,12,52,12,72,1,0,1,1,1,2,1,3,1,4,32,12,32,32,32,52,32,72,2,0,2,1,2,2,2,3,2,4,52,12,52,32,52,52,52,72,3,0,3,1,3,2,3,3,3,4,72,12,72,32,72,52,72,72,4,0,4,1,4,2,4,3,4,4

(1)

Use the DelaunayTriangulation command to get the set of triangles (tris) and the adjacency matrix (amat) for the point list pts.

tris,amatDelaunayTriangulationpts:

Build and display a plot of all triangles.

pltNULL:

forvintrisdopltplt,ptsv1,ptsv2,ptsv2,ptsv3,ptsv3,ptsv1end do:

PLOTCURVESplt,COLORRGB,1,0,0,SCALINGCONSTRAINED,AXESSTYLEBOX

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:

ptsseq0,j1,j=1..5:

forito4doptspts,seqi12,j0.49999,j=1..4,seqi,j1,j=1..5end do:

ptspts

pts:=0,0,0,1,0,2,0,3,0,4,12,0.50001,12,1.50001,12,2.50001,12,3.50001,1,0,1,1,1,2,1,3,1,4,32,0.50001,32,1.50001,32,2.50001,32,3.50001,2,0,2,1,2,2,2,3,2,4,52,0.50001,52,1.50001,52,2.50001,52,3.50001,3,0,3,1,3,2,3,3,3,4,72,0.50001,72,1.50001,72,2.50001,72,3.50001,4,0,4,1,4,2,4,3,4,4

(2)

tris,amatDelaunayTriangulationpts:

pltNULL:

forvintrisdopltplt,ptsv1,ptsv2,ptsv2,ptsv3,ptsv3,ptsv1end do:

PLOTCURVESplt,COLORRGB,1,0,0,SCALINGCONSTRAINED,AXESSTYLEBOX

Compatibility

• 

The GraphTheory[DelaunayTriangulation] command was introduced in Maple 16.

• 

For more information on Maple 16 changes, see Updates in Maple 16.

See Also

GraphTheory

PLOT

seq

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam