05/01/2008
Blob Tool | Blob Statistics

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.