1. Home
2. CONVEXHULL procedure

# CONVEXHULL procedure

Finds the points of a single or a full peel of convex hulls (P.G.N. Digby).

### Options

`PEELING` = string token Specifies whether the procedure is to form the full set of peels, or just the convex hull (`no`, `yes`); default `no` Scaling factor for hulls; default 1.0

### Parameters

`Y` = variate Y-coordinates of the points X-coordinates of the points Variate storing the y-coordinates of the points defining the convex hull (for `PEELING=no`) or pointer to a set of variates storing the y-coordinates of the convex hulls forming the complete set of peels Variate storing the x-coordinates of the points defining the convex hull (for `PEELING=no`) or pointer to a set of variates storing the x-coordinates of the convex hulls forming the complete set of peels Stores the number of the peel to which each point belongs

### Description

The convex hull of a set of points in two dimensions is the convex polygon that exactly encloses all the points. The operation of repeatedly finding the convex hull for a set of points, removing all the points that lie on hull, and then finding the next hull is known as (convex hull) peeling; eventually, either all the points will be deleted, or a single point will remain. Peeling can be used, for example, to calculate robust estimates of location or to give a bivariate analogue of a box-and-whisker plot; see Green (1981).

The coordinates of the set of points are given by the `X` and `Y` parameters, and the convex hull or hulls are output by the `XHULL` and `YHULL` parameters. By default, a single hull is formed and the parameters `XHULL` and `YHULL` return a pair of variates. To construct hulls representing a full set of peels, option `PEELING` should be set to `yes`. Parameters `XHULL` and `YHULL` then return pointers containing a variate for each hull, and the convex hull can be displayed by plotting `YHULL` against `XHULL`, the second peel by plotting `YHULL` against `XHULL`, and so on. The variates defining each convex polygon need not contain all of the points on the polygon but only those at the vertices. The first point in each variate is repeated as an extra last point, so that the polygon is closed. For high-resolution plotting, the parameters of `PEN` are best set as

`LINESTYLE=1; METHOD=line; JOIN=given; SYMBOL=0.`

The `SCALE` option supplies a scale factor that can be applied to the convex hulls, so that they are suitable for plotting as cosmetic “envelopes” enclosing the points. Values in the range 1.15 to 1.20 have been found suitable with test data sets. Plots of these data envelopes can be further enhanced by setting the `PEN` method to `closed`.

The fifth parameter, `PEEL`, returns a variate that indicates the number of the peel on which each point lies. Thus, for example, the `PEEL` variate will store value 1 for all the points on the convex hull itself; if `PEELING=no`, all the other points will have the value zero.

Option: `PEELING`.

Parameters: `Y`, `X`, `YHULL`, `XHULL`, `PEEL`.

### Method

Each convex hull is defined by a set of points. The first point is at the minimum y value; if there are several such points then one with the maximum absolute value of x is chosen. The search for subsequent points proceeds in an anti-clockwise direction: at each stage the furthest possible point is used to define the convex hull; however, any intervening (or coincident) points are deemed to lie on the convex hull, and so will be removed if peeling is taking place. Peeling is performed by repeatedly restricting the relevant variates at each stage.

### Action with `RESTRICT`

If either the `X` or the `Y` variates is restricted, the procedure will consider only the points not excluded by the restriction. The `PEEL` variate will be of the same length as `X` and `Y` and will be similarly restricted.

### Reference

Green, P.J. (1981). Peeling bivariate data. In: Interpreting Multivariate Data (ed. V.Barnett). Wiley, New York.

Procedures: `PTBOX`, `PTSINPOLYGON`.

Commands for: Graphics, Spatial statistics.

### Example

```CAPTION      'CONVEXHULL example'; STYLE=meta
VARIATE      [VALUES=1...20] n,u,v,x,y
CALCULATE    u,v = URAND(54321,0)
&            x,y = u + (1,-1) * v
CAPTION      'Form and plot just the convex hull.'
CONVEXHULL   Y=y; X=x; YHULL=yh; XHULL=xh; PEEL=peel
PRINT        n,x,y,peel
&            xh,yh
PEN          1,2,3; METHOD=point,point,line; JOIN=given; SYMBOL=2,2,0;\
CLINE='black'; CSYMBOL='red','blue'; CFILL='red','blue'
DGRAPH       [TITLE='Convex hull'; WINDOW=3; KEY=0] y,yh; x,xh; PEN=1,3
CAPTION      'Use the procedure for peeling.'
CONVEXHULL   [PEELING=yes] x; y; px; py; p
PRINT        n,x,y,p
FOR          dpx=px[]; dpy=py[]
PRINT      dpx,dpy
ENDFOR
CAPTION      'Specify a grouping and find convex hulls for each group.'
FACTOR       [LEVELS=2; VALUES=10(1,2)] group
CALC         x,y = x,y + group - 1
PRINT        n,x,y,group
FOR          dg=1,2; dgy=gy1,gy2; dgx=gx1,gx2
RESTRICT   x,y; group == dg
CONVEXHULL Y=y; X=x; YHULL=dgy; XHULL=dgx
PRINT      dgx,dgy
ENDFOR
RESTRICT     x,y
DGRAPH       [TITLE='Two groups'; WINDOW=3; KEY=0] gy1,gy2,y; gx1,gx2,x;\
PEN=3,3,group
```
Updated on March 8, 2019