Anyone know of a good C/C++ algorithm for calculating the minimum area bounding box for any type of solid? For example if you have a solid shape made of any number of vertices how would you calculate a rectangle around the shape with a minimum amount of area? I can get the min/max of all the vertices but it only gives you rough box, not rotated in any way such that it touches the maximum amount of vertices and minimizes the extra area.

[edit]
I'll post a pic as soon as I figure out where my upload link went...
[/edit]

Here is what I want:
{"name":"img","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/a\/fa0f69e588a33c9f536dadb352d16b0d.png","w":292,"h":269,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/a\/fa0f69e588a33c9f536dadb352d16b0d"}

This shows two methods of bounding boxes on an odd shaped object. There are many reasons to do the minimum area, one is collision detection like you mentioned. The box is not precalculated so I will have to calculate it on the fly. I don't want bounding spheres or bounding elipses, but boxes.

I would like to know the algorithm before I can calculate it

A single equation.. no!

But i can see how to do an iterative solution. Start out with an approximation (such as standard rectangle). Calculate the energy function.. in this case the area. Now you want to find a function that minimizes the area. Now it becomes a standard optimization problem. Might take some work to do a gradient descent but its probably a correct approach. Maybe define area( shape, boxAngle ).

sorry if that's a little obtuse.. but when dealing with hammers soo much everything looks like a nail.

Computationally that is not very efficient. You should probably pre-calculate it!

I'm not looking for speed here and if it helps any I do have the axis angle calculated so I know the angle the box will be at, just don't know how to shrink it down.

If you are looking for an algorithm that will do that from scratch, google gives this as the first result:

link

Otherwise, if you know the axis of the box, what's preventing you from rotating the set of points in such a way as to make this axis be, say, vertical and then simply using the standard min/max algorithm to find the box? When you obtain the box you can rotate the box corners back into the original orientation as needed.

If you say you know the angle then that's an easy one. Take a side, say the top, and move it in until that line intersects an edge. The check another side..

Seems like you should just calculate the slope of all of the pairs of vertices and create lines using them. Discard any lines that intersect with any other edges on the shape, of course. Take the line closest to the center of mass of the shape, then use that to find the next three edges.

I think CGames has the right idea. Draw a line from each vertice to all other vertices, discarding any lines that enter the shape. This reduces your shape as follows:

{"name":"591890","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/7\/97a2347d189310d24347d33dc5ffbe82.jpg","w":254,"h":150,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/9\/7\/97a2347d189310d24347d33dc5ffbe82"}

This new image will be much easier to find the minimum area bounding box (I would assume).

Stupid GIMP can't draw lies, so I booted Windows and I'm doing this from MS Paint.

{"name":"591891","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/7\/579ae9e12f7c48259f01e1ee34e5cd46.png","w":345,"h":453,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/5\/7\/579ae9e12f7c48259f01e1ee34e5cd46"}

1. Find all the lines between all the vertices. Discard those that intersect the polygon. The valid lines are shown in blue, some of the invalid ones are shown in red.

2. Find the shortest distance of each of the valid lines to the center of the shape. The shortest is shown in green, the rest in yellow.

3. From the point that the line come closest to the center of the shape (where the green line hits the blue on in step 2), find the first perpendicular line to the left and right that doesn't intersect with the shape.

3 b. Find the first parallel line down that doesn't intersect with the shape.

Stupid Gimp can draw lines. Click on start point. Shift-click on next points (vertices). Works with pencil, paintbrush, airbrush etc.

I would rotate my polygon in both directions and see what happens with the bounding rectangle. Compare rotate +epsilon degrees and -epsilon degrees and see in which direction you want to rotate to make the rectangle smaller. Then some kind of binary search for the minim.

If...

Then it makes sense to me to...

As in...

{"name":"591899","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/d\/6d4b18ffc221daeddbf5789624d05009.jpg","w":543,"h":513,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/6\/d\/6d4b18ffc221daeddbf5789624d05009"}

(Pretend the objects are the same... MSPaint is rotationally challenged and I'm no artist)

Otherwise, I'm out of my league. ;D