CONVEX HULL

CONVEX HULL

LET Subcommand

Compute the 2-dimensional convex hull of a set of points.

The 2-dimensional convex hull of a set of 2-dimensional points are the vertices that form the minimum area convex polygon that contains all of the points.

LET <y2> <x2> = CONVEX HULL <y> <x>
            <SUBSET/EXPCEPT/FOR qualification>
where <y> is a variable containing the y-coordinates of the full data set;
            <x> is a variable containing the x-coordinates of the full data set;
            <y2> is a variable that will contain the y-coordinats of the returned convex hull;
            <x2> is a variable that will contain the x-coordinats of the returned convex hull;
and where the <SUBSET/EXCEPT/FOR qualification> is optional.

LET Y2 X2 = CONVEX HULL Y X
LET Y2 X2 = CONVEX HULL Y X SUBSET X > 0 SUBSET Y > 0

Dataplot uses Eddy's CONVEX routine given in ACM algorithm 523 to compute the convex hull. The algorithm is described in the references given below.

None.

None

MINIMAL SPANNING TREE	= Determine the minimal spanning tree.
SPAINNING FOREST	= Determine the spanning forest.

W. F. Eddy (1977), "A New Convex Hull Algorithm for Planar Sets", ACM Transactions on Mathematical Software (TOMS), Vol. 3, No. 4, pp. 398-403.

W. F. Eddy (1977), "Algorithm 523: CONVEX, A New Convex Hull Algorithm for Planar Sets", ACM Transactions on Mathematical Software (TOMS), Vol. 3, No. 4, pp. 411-412.

O'Rourke (1998), "Computational Geometry in C", Second Edition, Cambridge Unversity Press, Chapter 3.

Computational Geometry

2008/4

 
.  Following data from Eddy'w ACM article
read x y
2.0       0.0
1.73      -1.0
1.0       1.73
0.0       2.0
0.1       0.1
-1.0      -1.73
0.2       -0.2
-1.73     1.0
-0.3      0.3
0.0       -2.0
-0.4      -0.4
-2.0      0.0
0.5       0.5
1.73      1.0
0.6       -0.6
-1.0      1.73
-0.7      0.7
-1.73     -1.0
-0.8      -0.8
1.0       -1.73
end of data
.
let y2 x2 = 2d convex hull y x
let n = size y
let id = sequence 1 1 n
.
title case asis
title offset 2
title Convex Hull
y1label Y
x1label X
tic offset units screen
tic offset 3 3
x3label
.
character automatic id
line blank all
.
plot y x id
line so
line color blue
char blank all
pre-erase off
limits freeze
pre-sort off
let n2 = size y2
let n2 = n2 + 1
let y2(n2) = y2(1)
let x2(n2) = x2(1)
plot y2 x2