Finds the points of a single or a full peel of convex hulls (P.G.N. Digby).
||Specifies whether the procedure is to form the full set of peels, or just the convex hull (
||Scaling factor for hulls; default 1.0|
||Y-coordinates of the points|
||X-coordinates of the points|
||Variate storing the y-coordinates of the points defining the convex hull (for
||Variate storing the x-coordinates of the points defining the convex hull (for
||Stores the number of the peel to which each point belongs|
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
Y parameters, and the convex hull or hulls are output by the
YHULL parameters. By default, a single hull is formed and the parameters
YHULL return a pair of variates. To construct hulls representing a full set of peels, option
PEELING should be set to
YHULL then return pointers containing a variate for each hull, and the convex hull can be displayed by plotting
XHULL, the second peel by plotting
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.
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
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.
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.
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
Y and will be similarly restricted.
Green, P.J. (1981). Peeling bivariate data. In: Interpreting Multivariate Data (ed. V.Barnett). Wiley, New York.
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