# Introduction

Quote:

*"The rotating calipers constitutes a powerful, simple and elegant tool that can solve many computational geometric problems efficiently in practice. The idea was first proposed by Michael Shamos in his Ph.D. thesis in 1978 for computing the diameter of a convex polygon. [...] I coined the name "Rotating Calipers" for the procedure and generalized it to solve many other problems. In 1983 I presented some of these results at a conference in Athens, Greece in the following paper:*

• Godfried T. Toussaint, "Solving geometric problems with the rotating calipers," Proceedings of IEEE MELECON'83, Athens, Greece, May 1983."

• Godfried T. Toussaint, "Solving geometric problems with the rotating calipers," Proceedings of IEEE MELECON'83, Athens, Greece, May 1983."

^{2}

This implementation, in Java, finds all bounding rectangles of a polygon

^{1}using the Rotating Calipers

^{2}algorithm. The Rotating Calipers algorithm finds all rectangles in

`O(n)`

time after the convex hull^{3}is found, which is an

`O(n × log(n))`

operation. # Outline of the algorithm

- find the vertices with the minimum and maximum x an y coordinates. These vertices (points) will be denoted by
`{P`

_{I}, P_{J}, P_{K}, P_{L}} - construct
`CAL`

and_{L}`CAL`

as the first set of calipers parallel to the x-axis, and_{J}`CAL`

and_{I}`CAL`

as the second set of calipers parallel to the y-axis_{K} - create for every
`CAL`

a next caliper,_{X}`NEXT_CAL`

, based on the next point in the convex hull and calculate the tangent of_{X}`CAL`

and it's_{X}`NEXT_CAL`

_{X} - get the smallest positive tangent between all
`CAL`

and_{X}`NEXT_CAL`

and rotate every caliper by that smallest gradient_{X} - repeat step 3 and 4 untill the calipers have turned more then 90 degrees

For a more detailed explanation of the algorithm, see the original paper

^{4}.

# Example

The source, including examples, are moved to Github.

# References

- Weisstein, Eric W. "Polygon." From
*MathWorld*--A Wolfram Web Resource. http://mathworld.wolfram.com/Polygon.html - Toussaint, Godfried T., School of Computer Science, McGill University. http://cgm.cs.mcgill.ca/~godfried/research/calipers.html
- Weisstein, Eric W. "ConvexHull." From
*MathWorld*--A Wolfram Web Resource. http://mathworld.wolfram.com/ConvexHull.html - Toussaint, Godfried T., School of Computer Science, McGill University. http://cgm.cs.mcgill.ca/~godfried/publications/calipers.pdf

## 1 comment:

awesome! a true programmer!

Post a Comment