Rotating Calipers Algorithm dissected

I've noticed this myself. For some reason, web pages that talk about rotating calipers algorithms tend to leave out this important piece of information and I was confused by it at first too.

What they aren't mentioning is that rotating calipers is a sort of sweep-line algorithm. These algorithms work by conceptually sweeping a line over the input geometry (or in this case, rotating the calipers around the geometry) and computing things as the line reaches certain events (like end-points or line-intersections).

The sweeping or rotating is used to provide an intuitive understanding of how the algorithm works but is not literally implemented. The only important things to implement are the events. In rotating calipers, the events are when one of the edges representing the calipers is coincidental to one of the edges of the convex polygon. In the part of the algorithm where it says to rotate until this event, there are four possible events, one for each side of the rotating calipers, and you calculate which event will occur next.

The big advantage of doing this rather than just walking around the edges of the polygon individually is that you always know where the extreme vertices are as you are walking around. You then use the extreme vertices to calculate the perimeter of the box, update the extreme vertex for the coincident side, and find the next event.

The next event is the one that requires the least rotation from the current state and this can be found using dot products. This algorithm can be implemented without any trig functions. You can imagine the 4 sides representing the calipers as also having a direction associated with them (and the calipers themselves as being clockwise or counterclockwise). You only need to store one vector to represent the direction of all four calipers; the others can be quickly calculated from that, eg (x,y), (x,-y), (-x,-y), (-x,y). Each caliper also has a point it is currently on. The next event a caliper can generate is when it is coincident with the next line segment from that point. Take the dot product of the direction of that caliper with the direction of that next line segment and divide by the length of the next line segment. The resulting value is proportional to the cosine of angle between the caliper and the segment. Since this angle is between 0 and 180 degrees and the cosine function is strictly decreasing on that inverval, the order is preserved and we can just compare these values to find the one that has the least angle. If the polygon and the calipers have the same winding (both clockwise or both counterclockwise) then the one with the highest value will be the next event (if the windings are different then the lowest value corresponds to the next event).

[Edited by - Vorpy on January 8, 2007 9:11:08 PM]

Thanks for the explanation. I also found a C++ implementation here...

http://www.geometrictools.com/

It makes alot more sense now.

I'm not sure about Vorpy's post, but I'll say this... the algorithm is, at its heart, an iteration over the edges of the object.

1. Take the object in its initial position, and make initial X/Y bounds calculations.
2. Find the highest vertex (min/max Y position).
3. Find the edge going clockwise from that vertex, and for each edge (starting with this one)...
3.1. Rotate the object so the current edge is horizontal and at top of the shape.
3.2. If the rotation angle is more than 90' counterclockwise, end loop.
3.3. Otherwise, make new X/Y bounds calculations and update algorithm status.
3.4. Let the current edge be the next edge clockwise from the current one.
4. Return algorithm status.

That's the core of it. The only difference between the different caliber algorithms is how you update the algorithm status; all the rest is the same. You could implement it as a trivial "list fold"-like operation, over the list of edges.

Wyrframe, that's not exactly the same but it's much easier to implement and probably of comparable speed if you locate the extreme points intelligently. In fact if you keep track of the extreme points and update them by shifting them over in each iteration I think you'd end up with an O(n) algorith...

But you'd need to loop around the entire shape, not just 90 degrees. Rotating calipers keeps track of all four possible sides of the bounding box as it rotates around which is why after going around 90 degrees it has checked every side of the polygon. Rotating calipers also always knows where the four extreme points that determine the bounding box are. If you're only looping around the edges of the polygon, at best you could keep track of what the previous extreme points were and use them as a starting point to search for the next ones. But it seems to me that this searching would be O(n) over the course of the entire algorith since each extreme point sort of goes around the polygon once, making the whole algorithm still O(n).

Both methods incur overhead in different ways, with rotating calipers calculating normals for the directions of each of the edges and calculating which of the four possible edges to check next and this other method having to loop around and perform more conditional statements looking for the extreme points. I think a good implementation of rotating calipers would use less branching and iterating than the other method, but the other method sounds easier to implement.