Subscribe via feed.

Intersection of 2 Rectangles

Posted by rajesh on August 6, 2011 – 3:17 am

Give the formula for the coordinates of the intersecting rectangles formed by two separate rectangles in 2D space ?


This post is under “Mathemagic” and has 12 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

12 Responds so far- Add one»

  1. 1. Chris Said:

    Hi Rajesh, the question is too vague. There are many possible answers depending on the sizes, where they intersect and their orientation.

  2. 2. Scott Said:

    Ax1 = Smaller x coordinate of rectangle A.
    Ay1 = Smaller y coordinate of rectangle A.

    Bx2 = Larger x coordinate of rectangle B.
    By2 = Larger y coordinate of rectangle B.

    Intersecting rectangle of rectangles A & B is as follows:

    Cx1 = min(Ax1,Bx1) + abs(Ax1-Bx1)
    Cy1 = min(Ay1,By1) + abs(Ay1-By1)

    Cx2 = max(Ax2,Bx2) – abs(Ax2-Bx2)
    Cy2 = max(Ay2,By2) – abs(Ay2-By2)

  3. 3. Scott Said:

    Also in order for 2 rectangles to intersect the following statements must all be true:

    Ax1 < Bx2
    Ay1 < By2

    Ax2 > Bx1
    Ay2 > By1

  4. 4. Chris Said:

    I’m slightly a twit. In order for the intersection to be a rectangle, the original rectangles must have the same orientation.

    I’m sure Scott has answered the question as intended.

    To get the full answer, the co-ordinate system must then be rotated; but that simply uglifies the solution.

  5. 5. cazayoux Said:

    This can be a very ugly one.
    There might be no intersections (no overlap between the two rectangles) or somewhere between 2 and 8 intersecting points (think of an octogon created by two squares with the same center, but rotated).

    There might also be an infinite number of intersecting points. (consider two rectagles of the same size, with one shifted slightly along one axis, where there is a line shared between the two rectangles)

  6. 6. Chris Said:

    Hi cazayoux. The question implies that there is an intersection and that it does form a rectangle. I didn’t recognise that at first either.

    Scott has taken the liberty of orienting the system so that the edges of the rectangles are parallel to the coordinate axes.

    I dread to imagine what the equations would become if the sides weren’t parallel to the axes.

  7. 7. Scott Said:

    “I dread to imagine what the equations would become if the sides weren’t parallel to the axes.”

    It’s not that bad, would probably just need coords of a 3rd corner of one of the rectangles in order to determine the rotation & lengths of sides.

    Without modification, my equations will still provide the coordinates for the diagonal corners of the overlapping rectangle whether or not the sides are parallel to the axes.

    Then, if say the bottom right coordinates (Ax3,Ay3) were known for at least one of the rectangles you can get the angle of rotation with:

    Rot = atan( (Ay3-Ay1) / (Ax3-Ax1) )

    this would then give:
    SideA = (Ax3-Ax1) / cos(Rot)
    SideB = (Ax3-Ax2) / sin(Rot)

    Or just get old man Pythagoras to help you out with:
    SideA = sqrt( (Ax3-Ax1)^2 + (Ay3-Ay1)^2 )
    SideB = sqrt( (Ax3-Ax2)^2 + (Ay3-Ay2)^2 )

    From here you can keep rockin’ the trig till you have everything you need.

    But you are right, I do this stuff for my day job developing parametric manufacturing systems and it can get pretty ugly.
    Especially when you start adding curves.

  8. 8. Scott Said:

    Just s quick correction to my last post. It turns out that I was a little hasty. My original equations will still work in ’some’ cases when then rectangles are rotated such as when the rectangles only overlap at one corner.

    They will fail if an entire side of a rotated rectangle is included within the other. In this case, as Chris mentioned, you would need to first rotate the rectangles before applying the original equations.

    This is a fun challenge, I’ll go ahead and work out the rotation equations and post them up shortly.

  9. 9. Scott Said:

    To rotate the rectangles parallel to the axes apply the following equations to the coordinates:

    Rot = Angle of rectangle from x axis

    X’ = SQRT( x^2 + y^2 ) * COS( ATAN( y / x ) – Rot )
    Y’ = SQRT( x^2 + y^2 ) * SIN( ATAN( y / x ) – Rot )

  10. 10. Chris Said:

    Hi Scott. I might have a think about this. My comment was because I can’t think of a way to rotate min(…) and abs(…)

  11. 11. Scott Said:

    Just rotate the coords before using the abs & min functions.

    Using the variable definitions already established in my previous posts, the full procedure is as follows.

    Get angle of rectangles from x-axis
    Rot = atan( (Ay3-Ay1) / (Ax3-Ax1) )

    Rotate rectangle A around origin
    ‘Ax1 = SQRT( Ax1^2 + Ay1^2 ) * COS( ATAN( Ay1 / Ax1 ) – Rot )
    ‘Ay1 = SQRT( Ax1^2 + Ay1^2 ) * SIN( ATAN( Ay1 / Ax1 ) – Rot )
    ‘Ax2 = SQRT( Ax2^2 + Ay2^2 ) * COS( ATAN( Ay2 / Ax2 ) – Rot )
    ‘Ay2 = SQRT( Ax2^2 + Ay2^2 ) * SIN( ATAN( Ay2 / Ax2 ) – Rot )

    Rotate rectangle B around origin
    ‘Bx1 = SQRT( Bx1^2 + By1^2 ) * COS( ATAN( By1 / Bx1 ) – Rot )
    ‘By1 = SQRT( Bx1^2 + By1^2 ) * SIN( ATAN( By1 / Bx1 ) – Rot )
    ‘Bx2 = SQRT( Bx2^2 + By2^2 ) * COS( ATAN( By2 / Bx2 ) – Rot )
    ‘By2 = SQRT( Bx2^2 + By2^2 ) * SIN( ATAN( By2 / Bx2 ) – Rot )

    Extract rotated coords of overlapping rectangle A-B
    ‘Cx1 = min(‘Ax1,’Bx1) + abs(‘Ax1-’Bx1)
    ‘Cy1 = min(‘Ay1,’By1) + abs(‘Ay1-’By1)
    ‘Cx2 = max(‘Ax2,’Bx2) – abs(‘Ax2-’Bx2)
    ‘Cy2 = max(‘Ay2,’By2) – abs(‘Ay2-’By2)

    Rotate rectangle ‘C back into the orientation of the parent rectangles
    Cx1 = SQRT( ‘Cx1^2 + ‘Cy1^2 ) * COS( ATAN( ‘Cy1 / ‘Cx1 ) + Rot )
    Cy1 = SQRT( ‘Cx1^2 + ‘Cy1^2 ) * SIN( ATAN( ‘Cy1 / ‘Cx1 ) + Rot )
    Cx2 = SQRT( ‘Cx2^2 + ‘Cy2^2 ) * COS( ATAN( ‘Cy2 / ‘Cx2 ) + Rot )
    Cy2 = SQRT( ‘Cx2^2 + ‘Cy2^2 ) * SIN( ATAN( ‘Cy2 / ‘Cx2 ) + Rot )

    Actually, I think it looks rather pretty :-)
    Wouldn’t take much work to code that into a c++ function.

  12. 12. Scott Said:

    I have of course cheated by not calculating each corner of the rectangles, but that can be done for ‘C quite easily after the extraction step.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0