Dataplot Vol 2 Vol 1

# CONVEX HULL

Name:
CONVEX HULL
Type:
LET Subcommand
Purpose:
Compute the 2-dimensional convex hull of a set of points.
Description:
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.
Syntax:
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.
Examples:
LET Y2 X2 = CONVEX HULL Y X
LET Y2 X2 = CONVEX HULL Y X SUBSET X > 0 SUBSET Y > 0
Note:
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.
Default:
None.
Synonyms:
None
Related Commands:
 MINIMAL SPANNING TREE = Determine the minimal spanning tree. SPAINNING FOREST = Determine the spanning forest.
References:
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.

Applications:
Computational Geometry
Implementation Date:
2008/4
Program:
```
.  Following data from Eddy'w ACM article
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
```

Date created: 10/15/2008
Last updated: 10/15/2008