simplex - Maple Programming Help

Home : Support : Online Help : Mathematics : Optimization : Simplex Linear Optimization : simplex/convexhull

simplex

 convexhull
 find convex hull enclosing the given points

 Calling Sequence convexhull(P) convexhull(P, output=area) convexhull(P, output=hull) convexhull(P, output=plot)

Parameters

 P - list or set of points in 2 dimensions

Description

 • The command convexhull(P) returns a list of points defining the convex hull of the points in P in counter-clockwise order.
 • Every point in P must be a list of an x and y coordinate, both of which must be numbers (of type numeric).
 • If the option output=area is specified, the area of the convex hull of the points is returned.
 • If the option output=hull is specified, the convex hull is is returned as a list of points.  This is the default return value.
 • If the option output=plot is specified, a plot of the points and the convex hull is returned.
 • Multiple outputs can be specified, for example, output=[hull,area] returns a sequence of two values.
 • An $n\mathrm{log}\left(n\right)$ algorithm computing tangents of pairs of points is used.
 • For a slightly more geometrical interpretation of the same command, see geometry[convexhull].  The points input and output are geometric points, and the output is considered to be a convex polygon.
 • The command with(simplex,convexhull) allows the use of the abbreviated form of this command.

Examples

 > $\mathrm{with}\left(\mathrm{simplex}\right):$
 > $P≔\left\{\left[0,0\right],\left[\frac{1}{2},\frac{1}{2}\right],\left[1,1\right],\left[2,0\right],\left[1,0\right],\left[1,\frac{1}{2}\right]\right\}$
 ${P}{:=}\left\{\left[{0}{,}{0}\right]{,}\left[{1}{,}{0}\right]{,}\left[{1}{,}{1}\right]{,}\left[{1}{,}\frac{{1}}{{2}}\right]{,}\left[{2}{,}{0}\right]{,}\left[\frac{{1}}{{2}}{,}\frac{{1}}{{2}}\right]\right\}$ (1)
 > $\mathrm{convexhull}\left(P\right)$
 $\left[\left[{0}{,}{0}\right]{,}\left[{2}{,}{0}\right]{,}\left[{1}{,}{1}\right]\right]$ (2)
 > $\mathrm{convexhull}\left(P,\mathrm{output}=\mathrm{area}\right)$
 ${1}$ (3)
 > $H,A≔\mathrm{convexhull}\left(P,\mathrm{output}=\left[\mathrm{hull},\mathrm{area}\right]\right)$
 ${H}{,}{A}{:=}\left[\left[{0}{,}{0}\right]{,}\left[{2}{,}{0}\right]{,}\left[{1}{,}{1}\right]\right]{,}{1}$ (4)

Execute the following to get a plot of the points and the convex hull.

 > $\mathrm{convexhull}\left(P,\mathrm{output}=\mathrm{plot}\right)$

This creates 50 points uniformly distributed at random on [0,1).

 > $R≔\mathrm{rand}\left({10}^{10}\right):$
 > U01 := proc() Float( R(), -10 ) end proc:
 > $P≔\left\{\mathrm{seq}\left(\left[\mathrm{U01}\left(\right),\mathrm{U01}\left(\right)\right],i=1..50\right)\right\}:$
 > $\mathrm{convexhull}\left(P,\mathrm{output}=\mathrm{area}\right)$
 ${0.7570693924}$ (5)

Execute the following to get a plot of the points and the convex hull.

 > $\mathrm{convexhull}\left(P,\mathrm{output}=\mathrm{plot}\right)$