PDA

View Full Version : Math...



jverkoey
05-29-2006, 12:00 PM
Hey everyone, I have a math question that's been bugging me.

Basically what I'm trying to do is this (view images attached):

I have an outer rectangle of WxH dimensions.

I have some arbitrary rectangle which is some MxN dimension and rotated at an angle from 0-360 degrees.

I need to find the best-fitting rectangle which can fit inside of this rotated rectangle, but is basically a shrunken version of the WxH rectangle (the inner white rectangle). How would I go about finding that mathematically?

As far as what I've tried, I've tried a lot of random mathematical calculations but nothing really works in all cases (when there is a tall rectangle as opposed to a wide one, etc).

VirtualAce
05-29-2006, 12:18 PM
Do you have access to the rotated positions of the outer rectangle?

If so you can produce an AABB based on these transformed values. You can alter the AABB creation so that it does not bound the rectangle, but is bounded by it.

BobMcGee123
05-29-2006, 03:45 PM
What is the mathematical definition for 'best-fitting' in this case?

I am not sure where you are at in your studies. In general, once you have got the formula for the area/fit function, you take the first and second derivatives to find the optimization points.

Find where the first derivative is zero. If the second derivative is positive this point (on the function) is a minimum. If the second derivative is negative, it is a maximum. Are you already doing problems like that?

jverkoey
05-29-2006, 04:24 PM
Sorry, should have been more clear.

At this point I have the coordinates of the large, outer rectangle, I also have the coordinates of the rotated grey rectangle. What I need to find are the coordinates of the inner white rectangle. By best fit I mean the largest rectangle that fits inside of the grey rectangle that has the same aspect ratio as the large outer rectangle.

I don't think calculus can really do much for this. I would think some simple geometry I'm not seeing would cover this problem, but I could be mistaken.

Also, to Bubba, what's an AABB?
-edit-
Nevermind, found the answer. I'm not quite sure how I'd apply that exact math to this problem though, as it's more the other way around correct?
"If so you can produce an AABB based on these transformed values. You can alter the AABB creation so that it does not bound the rectangle, but is bounded by it."
I can easily make an AABB of the outer edges, it's producing one of the inner edges that's the tricky part. And this inner box is basically a shrunken version of the outer, large box.

VirtualAce
05-29-2006, 05:59 PM
I can easily make an AABB of the outer edges, it's producing one of the inner edges that's the tricky part. And this inner box is basically a shrunken version of the outer, large box.


If you are looking to make a smaller box inside of the larger that is at the same orientation as the larger, simple trig can do that for you.



float fSizeDiffX=LargerBox.Width()-SmallerBox.DesiredWidth;
float fSizeDiffY=LargerBox.Height()-SmallerBox.DesiredHeight;

//Vertices
// 0....1
// ........
// 2....3

SmallerBox.v[0].x=LargerBox.v[0].x+(cos(LargerBox.fXangle)*fSizeDiffX);
SmallerBox.v[0].y=LargerBox.v[0].y+(sin(LargerBox.fYangle)*fSizeDiffY);

SmallerBox.v[1].x=LargerBox.v[1].x-(cos(LargerBox.fXangle)*fSizeDiffX);
SmallerBox.v[1].y=LargerBox.v[1].y+(sin(LargerBox.fYangle)*fSizeDiffY);

SmallerBox.v[2].x=LargerBox.v[2].x+(cos(LargerBox.fXangle)*fSizeDiffX);
SmallerBox.v[2].y=LargerBox.v[2].y-(sin(LargerBox.fYangle)*fSizeDiffY);

SmallerBox.v[3].x=LargerBox.v[3].x-(cos(LargerBox.fXangle)*fSizeDiffX);
SmallerBox.v[3].y=LargerBox.v[3].y+(sin(LargerBox.fYangle)*fSizeDiffY);


You may have to mess with the signs in the calculations depending on your coordinate setup.

If you are looking to find a smaller box with no orientation that fits into a larger box with a set orientation, this is a bit more tricker. You are essentially finding the point at which a line intersects another line. Eventually though there will be an orientation for which no box with 0 orientation will fit.

By 0 orientation I mean as is - just a 2D box like a button in a window.

jverkoey
05-30-2006, 07:26 PM
The problem is, I don't know the SmallerBox.DesiredWidth and SmallerBox.DesiredHeight values. I'm trying to find the smallerbox.

To clarify again, the large outer rectangle needs to be shrunk down to fit inside of the rotated rectangle.

Rash
05-31-2006, 05:38 AM
First, move the angle of rotation so that it's between 0 and 90. Call this angle t. (If it's between -90 and 0, use its negative, if between 90 and 270, subtract from 180.) Let the ratio of the sides of the desired rectangle be defined by r = toplength / sidelength. Let m be the length of the left side and n be the length of the top of the rotated rectangle, before it was rotated. (It's not like the lengths changed in rotation, of course, but 'left side' and 'top' would be ambiguous terms.)

Then, if x is the length of the left side (of the desired rectangle) then x = min{ m/(r*sin(t)+cos(t)), n/(sin(t)+r*cos(t) }. And of course the top has length r*x.

You can derive this by sliding the desired rectangle up the angled one so that the desired rectangle touches the angled at three vertices -- then similar triangles and such play their game.

jverkoey
05-31-2006, 07:12 AM
Awesome, that worked perfectly! Thank you very much!