ConvexHull - Maple Help

ComputationalGeometry

 ConvexHull
 compute convex hull of a set of points in n dimensions

 Calling Sequence ConvexHull(points) ConvexHull(points) ConvexHull(points,output=volume)

Parameters

 points - a list of n element lists or an m by n Matrix representing m n-dimensional points

Description

 • The ConvexHull command computes the convex hull of the set of input points.
 • If points is a Matrix, then each row of points is treated as a point. If it is a list of lists, then each sublist is a point.
 • All entries of points must evaluate to floating-point values when evalf is applied. This happens as a preprocessing step.
 • If the option output=volume is specified, the volume of the convex hull is returned. Note that the volume of a 2-D convex hull is its area.
 • For 2-D inputs, the command returns a list of integer references into the input points list or Matrix defining the convex hull in counterclockwise order.
 • For 2-D inputs, the command discards duplicate or collinear points.
 • For 3-D or higher dimensional inputs, the command returns a list of n element lists; each inner list specifies the vertices of a simplicial facet as integer references.
 • The maximum allowed dimension is 11.
 • There is also a ConvexHulls command in the PolyhedralSets package. The Convex Hulls Example Worksheet discusses both commands and the usefulness of each.

Examples

 > $\mathrm{with}\left(\mathrm{ComputationalGeometry}\right):$
 > $\mathrm{xy}≔\left[\left[0,0\right],\left[0,0\right],\left[1,0\right],\left[2,0\right],\left[0,1\right],\left[1,1\right],\left[2,1\right],\left[0,2\right],\left[1,2\right],\left[2,2\right]\right]$
 ${\mathrm{xy}}{≔}\left[\left[{0}{,}{0}\right]{,}\left[{0}{,}{0}\right]{,}\left[{1}{,}{0}\right]{,}\left[{2}{,}{0}\right]{,}\left[{0}{,}{1}\right]{,}\left[{1}{,}{1}\right]{,}\left[{2}{,}{1}\right]{,}\left[{0}{,}{2}\right]{,}\left[{1}{,}{2}\right]{,}\left[{2}{,}{2}\right]\right]$ (1)

Note that xy contains duplicate and collinear points

 > $\mathrm{ConvexHull}\left(\mathrm{xy}\right)$
 $\left[{1}{,}{4}{,}{10}{,}{8}\right]$ (2)

Convex hull of the unit cube.

 > $\mathrm{xyz}≔\left[\left[0,0,0\right],\left[0,0,1\right],\left[0,1,0\right],\left[0,1,1\right],\left[1,0,0\right],\left[1,0,1\right],\left[1,1,0\right],\left[1,1,1\right]\right]$
 ${\mathrm{xyz}}{≔}\left[\left[{0}{,}{0}{,}{0}\right]{,}\left[{0}{,}{0}{,}{1}\right]{,}\left[{0}{,}{1}{,}{0}\right]{,}\left[{0}{,}{1}{,}{1}\right]{,}\left[{1}{,}{0}{,}{0}\right]{,}\left[{1}{,}{0}{,}{1}\right]{,}\left[{1}{,}{1}{,}{0}\right]{,}\left[{1}{,}{1}{,}{1}\right]\right]$ (3)
 > $h≔\mathrm{ConvexHull}\left(\mathrm{xyz}\right)$
 ${h}{≔}\left[\left[{7}{,}{3}{,}{1}\right]{,}\left[{5}{,}{7}{,}{1}\right]{,}\left[{6}{,}{5}{,}{1}\right]{,}\left[{2}{,}{6}{,}{1}\right]{,}\left[{6}{,}{7}{,}{5}\right]{,}\left[{7}{,}{6}{,}{8}\right]{,}\left[{3}{,}{4}{,}{1}\right]{,}\left[{4}{,}{2}{,}{1}\right]{,}\left[{7}{,}{4}{,}{3}\right]{,}\left[{4}{,}{7}{,}{8}\right]{,}\left[{4}{,}{6}{,}{2}\right]{,}\left[{6}{,}{4}{,}{8}\right]\right]$ (4)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{map}\left(x↦\mathrm{plottools}:-\mathrm{polygon}\left(\mathrm{xyz}\left[x\right]\right),h\right)\right)$

Convex hull of 50 random points in 3-D.

 > $m≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(50,3\right)$
 ${m}{≔}\begin{array}{c}\left[\begin{array}{ccc}{-94}& {-38}& {76}\\ {27}& {91}& {-44}\\ {18}& {-1}& {24}\\ {18}& {63}& {65}\\ {63}& {-23}& {86}\\ {86}& {-63}& {20}\\ {-51}& {-26}& {-61}\\ {51}& {30}& {-48}\\ {38}& {10}& {77}\\ {-38}& {22}& {9}\\ {⋮}& {⋮}& {⋮}\end{array}\right]\\ \hfill {\text{50 × 3 Matrix}}\end{array}$ (5)
 > $h≔\mathrm{ConvexHull}\left(m\right)$
 ${h}{≔}\left[\left[{48}{,}{20}{,}{45}\right]{,}\left[{45}{,}{2}{,}{29}\right]{,}\left[{13}{,}{39}{,}{29}\right]{,}\left[{2}{,}{13}{,}{29}\right]{,}\left[{13}{,}{2}{,}{31}\right]{,}\left[{35}{,}{13}{,}{31}\right]{,}\left[{16}{,}{45}{,}{29}\right]{,}\left[{16}{,}{48}{,}{45}\right]{,}\left[{2}{,}{24}{,}{31}\right]{,}\left[{20}{,}{24}{,}{45}\right]{,}\left[{24}{,}{2}{,}{45}\right]{,}\left[{13}{,}{40}{,}{39}\right]{,}\left[{40}{,}{13}{,}{35}\right]{,}\left[{40}{,}{47}{,}{39}\right]{,}\left[{40}{,}{35}{,}{21}\right]{,}\left[{47}{,}{40}{,}{21}\right]{,}\left[{1}{,}{47}{,}{21}\right]{,}\left[{47}{,}{1}{,}{48}\right]{,}\left[{20}{,}{1}{,}{21}\right]{,}\left[{1}{,}{20}{,}{48}\right]{,}\left[{16}{,}{5}{,}{48}\right]{,}\left[{5}{,}{47}{,}{48}\right]{,}\left[{5}{,}{16}{,}{29}\right]{,}\left[{36}{,}{20}{,}{21}\right]{,}\left[{35}{,}{36}{,}{21}\right]{,}\left[{36}{,}{35}{,}{31}\right]{,}\left[{47}{,}{6}{,}{39}\right]{,}\left[{5}{,}{6}{,}{47}\right]{,}\left[{39}{,}{6}{,}{29}\right]{,}\left[{6}{,}{5}{,}{29}\right]{,}\left[{32}{,}{24}{,}{20}\right]{,}\left[{36}{,}{32}{,}{20}\right]{,}\left[{24}{,}{32}{,}{31}\right]{,}\left[{32}{,}{36}{,}{31}\right]\right]$ (6)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{map}\left(x↦\mathrm{plottools}:-\mathrm{polygon}\left(m\left[x\right]\right),h\right),\mathrm{axes}=\mathrm{none}\right)$
 > $\mathrm{ConvexHull}\left(m,\mathrm{output}=\mathrm{volume}\right)$
 ${4.53480266666666791}{×}{{10}}^{{6}}$ (7)

Compatibility

 • The ComputationalGeometry[ConvexHull] command was introduced in Maple 2018.