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

**Bubba** · 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.

**Bubba** · 05-29-2006, 05:59 PM

Quote:

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.

Code:

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!

05-29-2006, 12:00 PM	#1
jverkoey Software Developer Join Date: Feb 2003 Location: University of Waterloo Posts: 1,916	Math... 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). Attached Images __________________ GameDev Guys HQ TheJeffFiles Articles Last edited by jverkoey; 05-29-2006 at 12:04 PM.
jverkoey is offline

05-29-2006, 12:18 PM	#2
Bubba Super Moderator Join Date: Aug 2001 Posts: 7,813	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.
Bubba is offline

05-29-2006, 03:45 PM	#3
BobMcGee123 ∞ Join Date: May 2005 Posts: 970	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? __________________ argus triad mingus
BobMcGee123 is offline

05-29-2006, 04:24 PM	#4
jverkoey Software Developer Join Date: Feb 2003 Location: University of Waterloo Posts: 1,916	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. __________________ GameDev Guys HQ TheJeffFiles Articles Last edited by jverkoey; 05-29-2006 at 04:29 PM.
jverkoey is offline

05-30-2006, 07:26 PM	#6
jverkoey Software Developer Join Date: Feb 2003 Location: University of Waterloo Posts: 1,916	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. __________________ GameDev Guys HQ TheJeffFiles Articles
jverkoey is offline

05-31-2006, 05:38 AM	#7
Rash Registered User Join Date: May 2006 Location: Troy Posts: 14	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/(rsin(t)+cos(t)), n/(sin(t)+rcos(t) }. And of course the top has length rx. 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. Last edited by Rash; 05-31-2006 at 05:41 AM.*
Rash is offline

05-31-2006, 07:12 AM	#8
jverkoey Software Developer Join Date: Feb 2003 Location: University of Waterloo Posts: 1,916	Awesome, that worked perfectly! Thank you very much! __________________ GameDev Guys HQ TheJeffFiles Articles
jverkoey is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Math	knightjp	General Discussions	16	04-01-2009 05:36 PM
Help with C++ Math	aonic	C++ Programming	4	01-29-2005 04:40 AM
Basic Math Problem. Undefined Math Functions	gsoft	C Programming	1	12-28-2004 03:14 AM
Math Header?	Rune Hunter	C++ Programming	26	09-17-2004 06:39 AM
toughest math course	axon	A Brief History of Cprogramming.com	12	10-28-2003 10:06 PM