Rotating calipers

Last updated
Sequence of probes around the convex hull of a polygon to determine its diameter using Rotating Caliper method. Rotating Caliper 3x2.svg
Sequence of probes around the convex hull of a polygon to determine its diameter using Rotating Caliper method.

In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.

Contents

The method is so named because the idea is analogous to rotating a spring-loaded vernier caliper around the outside of a convex polygon. [1] Every time one blade of the caliper lies flat against an edge of the polygon, it forms an antipodal pair with the point or edge touching the opposite blade. The complete "rotation" of the caliper around the polygon detects all antipodal pairs; the set of all pairs, viewed as a graph, forms a thrackle. The method of rotating calipers can be interpreted as the projective dual of a sweep line algorithm in which the sweep is across slopes of lines rather than across x- or y-coordinates of points.

History

An antipodal pair of vertex and their supporting parallel lines. Rotating Caliper Antipodal Pair.svg
An antipodal pair of vertex and their supporting parallel lines.

The rotating calipers method was first used in the dissertation of Michael Shamos in 1978. [2] 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 time. Godfried Toussaint coined the phrase "rotating calipers" and demonstrated that the method was applicable in solving many other computational geometry problems. [3]

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

Shamos's algorithm

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: [2] 

/* 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 P1i=1j=2whileangle(i,j)<pij++yieldi,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 scannedcurrent=iwhilej!=nifangle(current,i+1)<=angle(current,j+1)j++current=jelsei++current=iyieldi,j// Now take care of parallel edgesifangle(current,i+1)=angle(current,j+1)yieldi+1,jyieldi,j+1yieldi+1,j+1ifcurrent=ij++elsei++

Another version of this algorithm appeared in the text by Preparata and Shamos in 1985 that avoided calculation of angles: [4] 

GetAllAntiPodalPairs(p[1..n])i0=ni=1j=i+1while(Area(i,i+1,j+1)>Area(i,i+1,j))j=j+1j0=jwhile(i!=j0)i=i+1yieldi,jwhile(Area(i,i+1,j+1)>Area(i,i+1,j))j=j+1if((i,j)!=(j0,i0))yieldi,jelsereturnif(Area(j,i+1,j+1)=Area(i,i+1,j))if((i,j)!=(j0,i0))yieldi,j+1elseyieldi+1,j

Applications

Pirzadeh [5] describes various applications of rotating calipers method.

Distances

Bounding boxes

Triangulations

Multi-polygon operations

Traversals

Others

See also

Related Research Articles

<span class="mw-page-title-main">Convex hull</span> Smallest convex set containing a given set

In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

<span class="mw-page-title-main">Polygon triangulation</span> Partition of a simple polygon into triangles

In computational geometry, polygon triangulation is the partition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

<span class="mw-page-title-main">Simple polygon</span> Shape bounded by non-intersecting line segments

In geometry, a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a piecewise-linear Jordan curve consisting of finitely many line segments. These polygons include as special cases the convex polygons, star-shaped polygons, and monotone polygons.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from the following real-world problem:

"In an art gallery, what is the minimum number of guards who together can observe the whole gallery?"

<span class="mw-page-title-main">Sweep line algorithm</span> Class of algorithms which use a moving line to solve geometrical problems

In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. It is one of the critical techniques in computational geometry.

A thrackle is an embedding of a graph in the plane in which each edge is a Jordan arc and every pair of edges meet exactly once. Edges may either meet at a common endpoint, or, if they have no endpoints in common, at a point in their interiors. In the latter case, they must cross at their intersection point: the intersection must be transverse.

<span class="mw-page-title-main">Pseudotriangle</span>

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

<span class="mw-page-title-main">Euclidean shortest path</span> Problem of computing shortest paths around geometric obstacles

The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

<span class="mw-page-title-main">Minimum bounding box</span> Smallest box which encloses some set of points

In geometry, the minimum bounding box or smallest bounding box for a point set S in N dimensions is the box with the smallest measure within which all the points lie. When other kinds of measure are used, the minimum box is usually called accordingly, e.g., "minimum-perimeter bounding box".

In computational geometry, the smallest enclosing box problem is that of finding the oriented minimum bounding box enclosing a set of points. It is a type of bounding volume. "Smallest" may refer to volume, area, perimeter, etc. of the box.

<span class="mw-page-title-main">Godfried Toussaint</span> Canadian computer scientist (1944–2019)

Godfried Theodore Patrick Toussaint was a Canadian computer scientist, a professor of computer science, and the head of the Computer Science Program at New York University Abu Dhabi (NYUAD) in Abu Dhabi, United Arab Emirates. He is considered to be the father of computational geometry in Canada. He did research on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition, motion planning, visualization, knot theory, linkage (mechanical) reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality, and others. Other interests included meander (art), compass and straightedge constructions, instance-based learning, music information retrieval, and computational music theory.

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

In geometry, a covering of a polygon is a set of primitive units whose union equals the polygon. A polygon covering problem is a problem of finding a covering with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon covering problems, depending on the type of polygon being covered. An example polygon covering problem is: given a rectilinear polygon, find a smallest set of squares whose union equals the polygon.

In geometry, a partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

<span class="mw-page-title-main">Convex hull of a simple polygon</span> Smallest convex polygon containing a given polygon

In discrete geometry and computational geometry, the convex hull of a simple polygon is the polygon of minimum perimeter that contains a given simple polygon. It is a special case of the more general concept of a convex hull. It can be computed in linear time, faster than algorithms for convex hulls of point sets.

<span class="mw-page-title-main">Relative convex hull</span>

In discrete geometry and computational geometry, the relative convex hull or geodesic convex hull is an analogue of the convex hull for the points inside a simple polygon or a rectifiable simple closed curve.

<span class="mw-page-title-main">Polygonalization</span> Polygon through a set of points

In computational geometry, a polygonalization of a finite set of points in the Euclidean plane is a simple polygon with the given points as its vertices. A polygonalization may also be called a polygonization, simple polygonalization, Hamiltonian polygon, non-crossing Hamiltonian cycle, or crossing-free straight-edge spanning cycle.

References

  1. ↑ "Rotating Calipers" at Toussaint's home page
  2. 1 2 Shamos, Michael (1978). "Computational Geometry" (PDF). Yale University. pp. 76–81.
  3. ↑ 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 .
  4. ↑ 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)
  5. ↑ Pirzadeh, Hormoz (1999). Computational geometry with the rotating calipers (Master's thesis). McGill University.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ 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.
  10. ↑ 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.
  11. ↑ 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.
  12. ↑ "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)
  13. ↑ 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.
  14. ↑ 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 .
  15. ↑ Teichmann, Marek (1989). Wedge placement optimization problems (Master's thesis). McGill University.
  16. ↑ Godfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons, The Visual Computer, Vol. 1, 1985, pp. 118–123.
  17. ↑ Tomas Lozano-Perez, "Spatial planning: A configuration space approach," IEEE Transactions on Computers, Vol. 32, No. 2, 1983, pp. 108–120.
  18. ↑ Binay K. Bhattacharya and Godfried T. Toussaint, "Computing shortest transversals," Computing, vol. 46, 1991, pp. 93–119.
  19. ↑ 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.
  20. ↑ Jean-Marc Robert and Godfried T. Toussaint, "Linear approximation of simple objects," Computational Geometry: Theory and Applications , Vol. 4, 1994, pp. 27–52.
  21. ↑ Rasson and Granville (1996). "Geometrical tools in classification". Computational Statistics & Data Analysis. 23 (1): 105–123. doi:10.1016/S0167-9473(96)00024-2.
  22. ↑ 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.
  23. ↑ "Incorrect Diameter Algorithms for Convex Polygons".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.