rotating calipers

File:Rotating Caliper Antipodal Pair.svg

The rotating calipers method was first used in the dissertation of Michael Shamos in 1978.{{Cite web|url = http://euro.ecom.cmu.edu/people/faculty/mshamos/1978ShamosThesis.pdf|title = Computational Geometry|date = 1978|publisher = Yale University|last = Shamos|first = Michael|author-link = Michael Shamos|pages = 76–81}} Shamos used this method to generate all antipodal pairs of points on a convex polygon and to compute the diameter of a convex polygon in $O(n)$ time. Godfried Toussaint coined the phrase "rotating calipers" and demonstrated that the method was applicable in solving many other computational geometry problems.{{cite conference

| last = Toussaint | first = Godfried T. | author-link = Godfried Toussaint

| title = Solving geometric problems with the rotating calipers

| book-title=Proceedings of MELECON '83, Mediterranean Electrotechnical Conference, Athens, Greece, 24–26 May 1983

| publisher = IEEE

| editor1-first = E. N. | editor1-last = Protonotarios

| editor2-first = G. I. | editor2-last = Stassinopoulos

| editor3-first = P. P. | editor3-last = Civalleri

|year = 1983

| citeseerx = 10.1.1.155.5671

| pages = A10.02/1–4

}}

File:Rotating calipers, finding a bridge between two convex polygons.svg

Shamos gave the following algorithm in his dissertation (pp. 77–82) for the rotating calipers method, which generated all antipodal pairs of vertices on a convex polygon:

/* p[] is in standard form, ie, counter clockwise order,

distinct vertices, no collinear vertices.

ANGLE(m, n) is a procedure that returns the clockwise angle

swept out by a ray as it rotates from a position parallel

to the directed segment Pm,Pm+1 to a position parallel to Pn, Pn+1

We assume all indices are reduced to mod N (so that N+1 = 1).

• /

GetAllAntiPodalPairs(p[1..n])

// Find first anti-podal pair by locating vertex opposite P1

i = 1

j = 2

while angle(i, j) < pi

j++

yield i, j

/* Now proceed around the polygon taking account of

possibly parallel edges. Line L passes through

Pi, Pi+1 and M passes through Pj, Pj+1

*/

// Loop on j until all of P has been scanned

current = i

while j != n

if angle(current, i + 1) <= angle(current, j + 1)

j++

current = j

else

i++

current = i

yield i, j

// Now take care of parallel edges

if angle(current, i + 1) = angle(current, j + 1)

yield i + 1, j

yield i, j + 1

yield i + 1, j + 1

if current = i

j++

else

i++

Another version of this algorithm appeared in the text by Preparata and Shamos in 1985 that avoided calculation of angles:{{cite book|last1=Shamos|first1=Franco P. Preparata, Michael Ian|title=Computational Geometry An Introduction|date=1985|publisher=Springer New York|location=New York, NY|isbn=978-1-4612-7010-2}}

GetAllAntiPodalPairs(p[1..n])

i = n

j = i + 1

while (Area(i, i + 1, j + 1) > Area(i, i + 1, j))

j = j + 1

j0 = j

while (i != j0)

i = i + 1

yield i, j

while (Area(i, i + 1, j + 1) > Area(i, i + 1, j))

j = j + 1

if ((i, j) != (j0, 1))

yield i, j

if (Area(i, i + 1, j + 1) = Area(i, i + 1, j))

if ((i, j) != (j0, n))

yield i, j + 1

Pirzadeh{{cite thesis|last1=Pirzadeh|first1=Hormoz|title=Computational geometry with the rotating calipers|url=https://escholarship.mcgill.ca/concern/theses/fx719p46g|publisher=McGill University|year=1999|type=Master's thesis}} describes various applications of rotating calipers method.

• Diameter (maximum width) of a convex polygonBinay K. Bhattacharya and Godfried T. Toussaint, "Fast algorithms for computing the diameter of a finite planar set," The Visual Computer, Vol. 3, No. 6, May 1988, pp.379–388.Binay K. Bhattacharya and Godfried T. Toussaint, "A counter example to a diameter algorithm for convex polygons," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-4, No. 3, May 1982, pp. 306–309.
• Width (minimum width) of a convex polygonMichael E. Houle and Godfried T. Toussaint, "Computing the width of a set," IEEE Transactions on Pattern Analysis & Machine Intelligence, Vol. 10, no. 5, September 1988, pp. 761–765.
• Maximum distance between two convex polygonsGodfried T. Toussaint and Jim A. McAlear, "A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets," Pattern Recognition Letters, Vol. 1, 1982, pp. 21–24.Binay K. Bhattacharya and Godfried T. Toussaint, "Efficient algorithms for computing the maximum distance between two finite planar sets," Journal of Algorithms, vol. 14, 1983, pp. 121–136.
• Minimum distance between two convex polygonsGodfried T. Toussaint and Binay K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," Pattern Recognition Letters, vol. 2, December, 1983, pp. 79–82.{{Cite web|url=http://cgm.cs.mcgill.ca/~orm/rotcal.html |title=Rotating Calipers |date=2015-03-30 |access-date=2017-03-22 |url-status=bot: unknown |archive-url=https://web.archive.org/web/20150330010154/http://cgm.cs.mcgill.ca/~orm/rotcal.html |archive-date=2015-03-30 }}
• Widest empty (or separating) strip between two convex polygons (a simplified low-dimensional variant of a problem arising in support vector machine based machine learning)
• Grenander distance between two convex polygons{{Cite journal|title = Review of: "PATTERN SYNTHESIS", by U. Grenander, Springer-Verlag, New York, 1976. 509 pp.|journal = International Journal of General Systems|date = January 1, 1978|issn = 0308-1079|pages = 126–127|volume = 4|issue = 2|doi = 10.1080/03081077808960672|first = HUGO M.|last = MARTINEZ}}
• Optimal strip separation (used in medical imaging and solid modeling){{Cite journal|title = Optimizing a Strip Separating Two Polygons|last = Barequet and Wolfers|date = 1998|journal = Graphical Models and Image Processing|volume = 60|issue = 3|pages = 214–221|doi = 10.1006/gmip.1998.0470|doi-access = free}}

• Minimum area oriented bounding box
• Minimum perimeter oriented bounding box

• Onion triangulations
• Spiral triangulations
• Quadrangulation
• Nice triangulation
• Art gallery problem
• Wedge placement optimization problem{{Cite thesis|url = https://escholarship.mcgill.ca/concern/theses/r207tq60s|title = Wedge placement optimization problems|date = 1989|last = Teichmann|first = Marek|publisher=McGill University|type=Master's thesis}}

• Union of two convex polygons
• Common tangents to two convex polygons
• Intersection of two convex polygonsGodfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons, The Visual Computer, Vol. 1, 1985, pp. 118–123.
• Critical support lines of two convex polygons
• Vector sums (or Minkowski sum) of two convex polygonsTomas Lozano-Perez, "Spatial planning: A configuration space approach," IEEE Transactions on Computers, Vol. 32, No. 2, 1983, pp. 108–120.
• Convex hull of two convex polygons

• Shortest transversalsBinay K. Bhattacharya and Godfried T. Toussaint, "Computing shortest transversals," Computing, vol. 46, 1991, pp. 93–119.Binay K. Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenovic, Godfried T. Toussaint, and Jorje Urrutia, "Computing shortest transversals of sets," International Journal of Computational Geometry and Applications, Vol. 2, No. 4, December 1992, pp. 417–436.
• Thinnest-strip transversalsJean-Marc Robert and Godfried T. Toussaint, "Linear approximation of simple objects," Computational Geometry: Theory and Applications, Vol. 4, 1994, pp. 27–52.

• Non parametric decision rules for machine learned classification{{Cite journal|title = Geometrical tools in classification|last = Rasson and Granville|date = 1996|journal = Computational Statistics & Data Analysis|doi = 10.1016/S0167-9473(96)00024-2|volume = 23|issue = 1|pages = 105–123}}
• Aperture angle optimizations for visibility problems in computer vision{{Cite journal|title = Some Aperture-Angle Optimization Problems|journal = Algorithmica|date = 2002-08-01|issn = 0178-4617|pages = 411–435|volume = 33|issue = 4|doi = 10.1007/s00453-001-0112-9|last1 = Bose|first1 = P.|last2 = Hurtado-Diaz|first2 = F.|last3 = Omaña-Pulido|first3 = E.|last4 = Snoeyink|first4 = J.|last5 = Toussaint|first5 = G. T.|citeseerx = 10.1.1.16.7118| s2cid=27455160 }}
• Finding longest cells in millions of biological cells{{Cite web|url = http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2000/MS/diameter/document.html|title = Incorrect Diameter Algorithms for Convex Polygons}}
• Comparing precision of two people at firing range
• Classify sections of brain from scan images

• Convex polygon
• Convex hull
• Smallest enclosing box

Category:Geometric algorithms

Category:Convex geometry