Rotating calipers

Rotating calipers

Rotating calipers is a computational algorithm developed by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a convex polygon or convex hull. The term "rotating calipers" was later coined in 1983 by the computer scientist Godfried Toussaintcite_paper
author = Toussaint, G. T
title = Solving geometric problems with the rotating calipers
publisher=Proc. MELECON '83, Athens
url=http://citeseer.ist.psu.edu/toussaint83solving.html
date = 1983
] .The name comes from the analogy of rotating a spring-loaded caliper around the outside of a convex polygon. 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 algorithm runs in
O(n) time.

Applicable problems [ [http://cgm.cs.mcgill.ca/~orm/rotcal.html Rotating Calipers ] ]

* Diameter (maximum width) of a convex polygon
* Width (minimum width) of a convex polygon
* Maximum distance between two convex polygons
* Minimum distance between two convex polygons
* Minimum area oriented bounding box
* Minimum perimeter oriented bounding box
* Onion triangulations
* Spiral triangulations
* Quadrangulations
* Merging two convex polygons
* Common tangents to two convex polygons
* Intersection points of two convex polygons
* Critical support lines of two convex polygons
* Vector sums of two convex polygons
* Thinnest-strip transversals across multiple convex polygons

Minimum width of a convex polygon

ARRAY points := {P1, P2, ... , PN}; points.delete(middle vertices of any collinear sequence of three points); REAL p_a := index of vertex with minimum y-coordinate; REAL p_b := index of vertex with maximum y-coordinate; REAL rotated_angle := 0; REAL min_width := INFINITY; VECTOR caliper_a(1,0); // Caliper A points along the positive x-axis VECTOR caliper_b(-1,0); // Caliper B points along the negative x-axis WHILE rotated_angle < PI // Determine the angle between each caliper and the next adjacent edge in the polygon VECTOR edge_a(points [p_a + 1] .x - points [p_a] .x, points [p_a + 1] .y - points [p_a] .y); VECTOR edge_b(points [p_b + 1] .x - points [p_b] .x, points [p_b + 1] .y - points [p_b] .y); REAL angle_a := angle(edge_a, caliper_a); REAL angle_b := angle(edge_b, caliper_b); REAL width := 0; // Rotate the calipers by the smaller of these angles caliper_a.rotate(min(angle_a, angle_b)); caliper_b.rotate(min(angle_a, angle_b)); IF angle_a < angle_b p_a++; // This index should wrap around to the beginning of the array once it hits the end width = caliper_a.distance(points [p_b] ); ELSE p_b++; // This index should wrap around to the beginning of the array once it hits the end width = caliper_b.distance(points [p_a] ); END IF rotated_angle = rotated_angle + min(angle_a, angle_b); IF (width < min_width) min_width = width; END IF END WHILE RETURN min_width;

References

See also

* Convex polygon
* Convex hull
* Smallest enclosing box


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Minimum bounding box algorithms — 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. It is… …   Wikipedia

  • Convex hull — The convex hull of the red set is the blue convex set. See also: Convex set and Convex combination In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the min …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их… …   Википедия

  • Компьютерная геометрия — Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного… …   Википедия

  • Michael Ian Shamos — (born April 21, 1947, and often referred to as Mike Shamos) is an American mathematician, attorney, book author, journal editor, consultant and company director. He is (with Franco P. Preparata) the author of Computational Geometry (Springer… …   Wikipedia

  • Metalworking — Machining a bar of metal on a lathe. Metalworking is the process of working with metals to create individual parts, assemblies, or large scale structures. The term covers a wide range of work from large ships and bridges to precise engine parts… …   Wikipedia

  • Lancia Delta — See also: Lancia Delta S4 Lancia Delta Lancia Delta (3rd generation) Manufacturer Lancia Production …   Wikipedia

  • Threading (manufacturing) — Threading is the process of creating a screw thread. More screw threads are produced each year than any other machine element.[1] There are many methods of generating threads, including subtractive methods (many kinds of thread cutting and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”