Rotating calipers

<h2 id="history">History</h2>

<p>The rotating calipers method was first used in the dissertation of <a href="/facts/Michael_Shamos/38cn2KNA">Michael Shamos</a> in 1978.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> Shamos used this method to generate all <a href="/facts/Antipodal_point/2V3228jA">antipodal</a> pairs of points on a <a href="/facts/Convex_polygon/7x35w610">convex polygon</a> and to compute the diameter of a convex polygon in 
  
    
      
        O
        (
        n
        )
      
    
    {\displaystyle O(n)}
  
 time. <a href="/facts/Godfried_Toussaint/AN8GxkAS">Godfried Toussaint</a> coined the phrase "rotating calipers" and demonstrated that the method was applicable in solving many other computational geometry problems.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>

<h2 id="shamoss-algorithm">Shamos's algorithm</h2>
<p>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:<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
/* 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++

<p>Another version of this algorithm appeared in the text by Preparata and Shamos in 1985 that avoided calculation of angles:<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
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

<h2 id="applications">Applications</h2>
<p>Pirzadeh<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> describes various applications of rotating calipers method.
</p>
<h3>Distances</h3>
<ul><li><a href="/facts/Diameter_(computational_geometry)/HKLtlIgq">Diameter</a> (maximum width) of a convex polygon<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a><a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li>
<li>Width (minimum width) of a convex polygon<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a></li>
<li>Maximum distance between two convex polygons<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a><a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></li>
<li><a href="/facts/Closest_pair_of_points_problem/54Aw1kRV">Minimum distance</a> between two convex polygons<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a><a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a></li>
<li>Widest empty (or separating) strip between two convex polygons (a simplified low-dimensional variant of a problem arising in <a href="/facts/Support_vector_machine/XobxpdBG">support vector machine</a> based machine learning)</li>
<li>Grenander distance between two convex polygons<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a></li>
<li>Optimal strip separation (used in medical imaging and solid modeling)<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a></li></ul>
<h3>Bounding boxes</h3>
<ul><li>Minimum area <a href="/facts/Oriented_bounding_box/oFHL8bxI">oriented bounding box</a></li>
<li>Minimum perimeter <a href="/facts/Oriented_bounding_box/oFHL8bxI">oriented bounding box</a></li></ul>
<h3>Triangulations</h3>
<ul><li>Onion <a href="/facts/Polygon_triangulation/FF0205ye">triangulations</a></li>
<li>Spiral <a href="/facts/Polygon_triangulation/FF0205ye">triangulations</a></li>
<li>Quadrangulation</li>
<li>Nice triangulation</li>
<li>Art gallery problem</li>
<li>Wedge placement optimization problem<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a></li></ul>
<h3>Multi-polygon operations</h3>
<ul><li>Union of two convex polygons</li>
<li>Common tangents to two convex polygons</li>
<li>Intersection of two convex polygons<a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a></li>
<li><a href="/facts/Critical_support_line/FzTIaF47">Critical support lines</a> of two convex polygons</li>
<li>Vector sums (or Minkowski sum) of two convex polygons<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a></li>
<li>Convex hull of two convex polygons</li></ul>
<h3>Traversals</h3>
<ul><li>Shortest transversals<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a></li>
<li>Thinnest-strip transversals<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a></li></ul>
<h3>Others</h3>
<ul><li>Non parametric decision rules for machine learned classification<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a></li>
<li>Aperture angle optimizations for visibility problems in computer vision<a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a></li>
<li>Finding longest cells in millions of biological cells<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a></li>
<li>Comparing precision of two people at firing range</li>
<li>Classify sections of brain from scan images</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Convex_polygon/7x35w610">Convex polygon</a></li>
<li><a href="/facts/Convex_hull/D4Id3JDS">Convex hull</a></li>
<li><a href="/facts/Smallest_enclosing_box/NgMKHabc">Smallest enclosing box</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>"Rotating Calipers" at Toussaint's home page <a href="http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html" target="_blank">http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Shamos, Michael (1978). "Computational Geometry" (PDF). Yale University. pp. 76–81. <a href="/wiki/Michael_Shamos" target="_blank">/wiki/Michael_Shamos</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Toussaint, Godfried T. (1983). "Solving geometric problems with the rotating calipers". In Protonotarios, E. N.; Stassinopoulos, G. I.; Civalleri, P. P. (eds.). Proceedings of MELECON '83, Mediterranean Electrotechnical Conference, Athens, Greece, 24–26 May 1983. IEEE. pp. A10.02/1–4. CiteSeerX 10.1.1.155.5671. <a href="/wiki/Godfried_Toussaint" target="_blank">/wiki/Godfried_Toussaint</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Shamos, Michael (1978). "Computational Geometry" (PDF). Yale University. pp. 76–81. <a href="/wiki/Michael_Shamos" target="_blank">/wiki/Michael_Shamos</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Shamos, Franco P. Preparata, Michael Ian (1985). Computational Geometry An Introduction. New York, NY: Springer New York. ISBN 978-1-4612-7010-2.{{cite book}}:  CS1 maint: multiple names: authors list (link) <a href="978-1-4612-7010-2" target="_blank">978-1-4612-7010-2</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Pirzadeh, Hormoz (1999). Computational geometry with the rotating calipers (Master's thesis). McGill University. <a href="https://escholarship.mcgill.ca/concern/theses/fx719p46g" target="_blank">https://escholarship.mcgill.ca/concern/theses/fx719p46g</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Binay 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. <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>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. <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Michael 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. <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Godfried 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. <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>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. <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
<li id="fn:12"><p>Godfried 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. <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li>
<li id="fn:13"><p>"Rotating Calipers". 2015-03-30. Archived from the original on 2015-03-30. Retrieved 2017-03-22.{{cite web}}:  CS1 maint: bot: original URL status unknown (link) <a href="https://web.archive.org/web/20150330010154/http://cgm.cs.mcgill.ca/~orm/rotcal.html" target="_blank">https://web.archive.org/web/20150330010154/http://cgm.cs.mcgill.ca/~orm/rotcal.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li>
<li id="fn:14"><p>MARTINEZ, HUGO M. (January 1, 1978). "Review of: "PATTERN SYNTHESIS", by U. Grenander, Springer-Verlag, New York, 1976. 509 pp". International Journal of General Systems. 4 (2): 126–127. doi:10.1080/03081077808960672. ISSN 0308-1079. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li>
<li id="fn:15"><p>Barequet and Wolfers (1998). "Optimizing a Strip Separating Two Polygons". Graphical Models and Image Processing. 60 (3): 214–221. doi:10.1006/gmip.1998.0470. <a href="https://doi.org/10.1006%2Fgmip.1998.0470" target="_blank">https://doi.org/10.1006%2Fgmip.1998.0470</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li>
<li id="fn:16"><p>Teichmann, Marek (1989). Wedge placement optimization problems (Master's thesis). McGill University. <a href="https://escholarship.mcgill.ca/concern/theses/r207tq60s" target="_blank">https://escholarship.mcgill.ca/concern/theses/r207tq60s</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li>
<li id="fn:17"><p>Godfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons, The Visual Computer, Vol. 1, 1985, pp. 118–123. <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li>
<li id="fn:18"><p>Tomas Lozano-Perez, "Spatial planning: A configuration space approach," IEEE Transactions on Computers, Vol. 32, No. 2, 1983, pp. 108–120. <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li>
<li id="fn:19"><p>Binay K. Bhattacharya and Godfried T. Toussaint, "Computing shortest transversals," Computing, vol. 46, 1991, pp. 93–119. <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li>
<li id="fn:20"><p>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. <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li>
<li id="fn:21"><p>Jean-Marc Robert and Godfried T. Toussaint, "Linear approximation of simple objects," Computational Geometry: Theory and Applications, Vol. 4, 1994, pp. 27–52. <a href="/wiki/Computational_Geometry_(journal)" target="_blank">/wiki/Computational_Geometry_(journal)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li>
<li id="fn:22"><p>Rasson and Granville (1996). "Geometrical tools in classification". Computational Statistics & Data Analysis. 23 (1): 105–123. doi:10.1016/S0167-9473(96)00024-2. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li>
<li id="fn:23"><p>Bose, P.; Hurtado-Diaz, F.; Omaña-Pulido, E.; Snoeyink, J.; Toussaint, G. T. (2002-08-01). "Some Aperture-Angle Optimization Problems". Algorithmica. 33 (4): 411–435. CiteSeerX 10.1.1.16.7118. doi:10.1007/s00453-001-0112-9. ISSN 0178-4617. S2CID 27455160. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li>
<li id="fn:24"><p>"Incorrect Diameter Algorithms for Convex Polygons". <a href="http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2000/MS/diameter/document.html" target="_blank">http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2000/MS/diameter/document.html</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li>
</ol>

Rotating calipers open-in-new

Rotating calipers