Friday, May 20, 2011

Rotating Calipers in Java

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."
2



This implementation, in Java, finds all bounding rectangles of a polygon1 using the Rotating Calipers2 algorithm. The Rotating Calipers algorithm finds all rectangles in O(n) time after the convex hull3 is found, which is an O(n × log(n)) operation.

Outline of the algorithm

  1. find the vertices with the minimum and maximum x an y coordinates. These vertices (points) will be denoted by {PI, PJ, PK, PL}
  2. construct CALL and CALJ as the first set of calipers parallel to the x-axis, and CALI and CALK as the second set of calipers parallel to the y-axis
  3. create for every CALX a next caliper, NEXT_CALX, based on the next point in the convex hull and calculate the tangent of CALX and it's NEXT_CALX
  4. get the smallest positive tangent between all CALX and NEXT_CALX and rotate every caliper by that smallest gradient
  5. 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 paper4.

Example

The source, including examples, are moved to Github.

References

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

1 comment:

Shen said...

awesome! a true programmer!