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]

I'm extremely new to collision detection. In fact the only way I know how to do collision detection is tile-based or hard-coded. Anyway, I'm a little confused as to why you would want a rectangular bounding-box to be rotated on any angle...

If your detecting it based on a rectangle wouldn't you just use a flush rectangle? In other words, the maximum and minimum x's and y's...?

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.

Wouldn't it be more efficient to calculate only when the shape changes and store the bounding box?

Sorry, Steve, this doesn't help you much.

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

Is there even a valid way to do that? I'd imagine that any method would be hugely intensive since it'd need to check the various angles of boxes and determine which produces the "smallest" box. I'd either go with AABB (Axis-Aligned Bounding Box, as in your first example), or build the bounding box with your shape in an upright position, and just rotate it with the object.

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!

Watch Numb3rs on Friday nights (or record it for later) and hope they eventually tell you the solution!

Is a bounding box even the best solution for collision detection? I would assume when you get into weird shapes there must be a better, more complex way...

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.

The only way I can think of is guesses... Make a guess and check if you are too far. If you are, move back by half the distance you moved last time and check again. If you're not, move forward again.

Besides, how can you know what angle the box will be at for an oddly shaped object?

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.

I don't really know what I'm talking about, but it seems to me that trying to find such a rectangle by approximations would take a lot of time, which I don't think is too god for any kind of game...

What I can think of doing is: take the standard rectangle bounding box of your example and divide it in smaller rectangles, maybe 32x32. Generate a pixel perfect collision detection mask for each of the rectangles, discard those that are all 0. This might take more time than a mathematical approximation, I don't know, but you would get a pixel perfect mask of the shape.

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

That sounds like a great idea. Yes, I think I'll take credit for that one.

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 was hoping this was a bounding box check thread , I like answering that question.

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).

I think you would need to find the quickest path around the shape without entering it. I can find a few routes that don't enter the shape and aren't your resulting polygon.

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.

CGames... why Paint!? Paint sucks at drawing lines too! (esp at changing them)

What you want is inkscape. It does vector drawing.

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 you are using vector objects, wouldn't it be easier just to check if the vector objects overlap directly?

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

For some reason my vague memory is saying something about the covariance matrix and possibly eigenvectors. I'm off to the 'net...