Untitled Document

05/01/2008

Convex Hull and related algorithms.

Simplest convex hull algorithm, per Toussaint, G., "A counter-example to a convex hull algorithm for polygons", Pattern Recognition 24(2):183-4 (1991).

Melkman, A.A., "Online Construction of the Convex-Hull of a simple Polyline", Information Processing Letters 25(1):11-12 (1987).

Algorithm Hull

1. t <- -1; b <- 0;
v1 <- input; v2 <- input; v3 <- input;
if (v1, v2, v3) > 0
then begin push v1; push v2; end
else begin push v2; push v1; end
push v3; insert v3;
2. v <- input;
until (v, db, db+) < 0 or (dt-, dt, v) < 0
do v <- input end;
3. until (dt-, dt, v) > 0 do pop dt end;
push v;
4. until (v, db, db+) > 0 do remove db end;
insert v;
goto 2.
(a b c) assumes values 1, 0 or -1 depending on whether c is to the right of,
collinear with, or to the left of the directed line a to b.

Left turn test

Ratschek, H. and Rokne, J., "Exact and optimal convex hulls in 2D", International Journal of Computational Geometry & Applications 10(2):109-129 (2000). p. 116.

c is strictly left to the directed line leading from a to b iff
|a1 a2 1 |
D = |b1 b2 1 | > 0
|c1 c2 1 |
D = (b1 - a1)(c2 - a2) - (b2 - a2)(c1 - a1) Fewest arithmetic ops.
= a1b2 + a2c1 + b1c2 - b2c1 - a2b1 - a1c2 Best for compting sign only
by Ratschek ESSA algorithm.
Note - D, the determinant, is twice the area (directed) of triangle abc.
Preparata '85, p. 43. D > 0 IFF (abc)form a counterclockwise cycle.
"So, a,b,c is a left turn IFF the determinant D is positive."

Feret diameters (max and min) can be had from the antipodal points of the convex hull. To get these points, see (Preparata '85) pp. 173-175. Preparata, F.P. and Shamos, M.I., COMPUTATIONAL GEOMETRY, An Introduction. Springer-Verlag, N.Y., 1985. QA447.p735

Over-all algorithm shown nicely in Hormoz Pirzadeh's pages on rotating calipers: http://cgm.cs.mcgill.ca/~orm/width.html.