Contents || Index
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                                            

   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.


 

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.