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 |
|---|---|
SCALE = scalar |
Scaling factor for hulls; default 1.0 |
Parameters
Y = variate |
Y-coordinates of the points |
|---|---|
X = variate |
X-coordinates of the points |
YHULL = variate or pointer |
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 |
XHULL = variate or pointer |
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 |
PEEL = variate |
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[1] against XHULL[1], the second peel by plotting YHULL[2] against XHULL[2], 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.
See also
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