Math...

This is a discussion on Math... within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Hey everyone, I have a math question that's been bugging me. Basically what I'm trying to do is this (view ...

  1. #1
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,904

    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 Attached Images  
    Last edited by jverkoey; 05-29-2006 at 01:04 PM.

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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.

  3. #3

    Join Date
    May 2005
    Posts
    1,041
    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?
    I'm not immature, I'm refined in the opposite direction.

  4. #4
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,904
    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.
    Last edited by jverkoey; 05-29-2006 at 05:29 PM.

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,598
    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.
    Last edited by VirtualAce; 05-29-2006 at 07:05 PM.

  6. #6
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,904
    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.

  7. #7
    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/(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.
    Last edited by Rash; 05-31-2006 at 06:41 AM.

  8. #8
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,904
    Awesome, that worked perfectly! Thank you very much!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Math
    By knightjp in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 04-01-2009, 06:36 PM
  2. Help with C++ Math
    By aonic in forum C++ Programming
    Replies: 4
    Last Post: 01-29-2005, 04:40 AM
  3. Basic Math Problem. Undefined Math Functions
    By gsoft in forum C Programming
    Replies: 1
    Last Post: 12-28-2004, 03:14 AM
  4. Math Header?
    By Rune Hunter in forum C++ Programming
    Replies: 26
    Last Post: 09-17-2004, 07:39 AM
  5. toughest math course
    By axon in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-28-2003, 10:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21