Home > Software > Overlapping rectangles

Overlapping rectangles


I come up to another geometry problem while coding.
Problem: Found the overlapping region of two rectangles with parallel sides (two by two).
Solution: Actually quite simple.

The problem can be reduced (from two dimensions to one dimension) to find the overlapping section of two segments on the same line. Let’s say that the first segment is from x1 to x2 (x1<=x2) and the second one is from z1 to z2 (z1v2 then the segments do not overlap.

By extension to rectangles specified by (top,left) and (bottom,right) corners, the overlapping region of two rectangles:

  1. (x1,y1)(x2,y2), where x1 <= x2 and y1 <= y2
  2. (z1,t1)(z2,t2), where z1 <= z2 and t1 <= t2

will be (v1=max(x1, z1), w1=max(y1,t1))(v2=min(x2, z2), w2=min(y2,t2)). If v1 > v2 or w1 > w2 then the two rectangles do not overlap.

To express it in plain English, we calculate the maximum of the lower coordinates and the minimum of the upper one. If the results maintain the same relationship, then there is no overlap.

Please see the image below to visually illustrate the above.

If interested I also have the SVG code for this image:

<svg width="640" height="480" xmlns="http://www.w3.org/2000/svg">
  <g>
    <title>Overlapping Rectangles</title>
    <text fill="#111111" stroke="#111111" stroke-width="3" x="187" y="52" id="text1" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve">Overlapping segments on the same line</text>
    <line id="l1" y2="78" x2="243" y1="78" x1="83" stroke-width="5" stroke="#00dd00"/>
    <line id="l1" y2="78" x2="283" y1="78" x1="103" stroke-width="5" stroke="#0000dd"/>
    <line id="l1_2" y2="78" x2="243" y1="78" x1="103" stroke-width="5" stroke="#dd0000"/>
    <text fill="#111111" stroke="#111111" stroke-width="3" x="190" y="139" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve" id="text2">Overlapping rectangles</text>
    <rect fill-opacity="0" fill="#ffffff" id="r1" height="120" width="100" y="167" x="87" stroke-width="5" stroke="#00dd00"/>
    <rect fill-opacity="0" fill="#ffffff" id="r2" height="90" width="140" y="217" x="147" stroke-width="5" stroke="#0000dd"/>
    <rect fill-opacity="0" fill="#ffffff" id="r1_2" height="70" width="40" y="217" x="147" stroke-width="5" stroke="#dd0000"/>
    <text id="text3" fill="#111111" stroke="#111111" stroke-width="3" x="470" y="52" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve">Non-overlapping segments on the same line</text>
    <line id="l3" y2="78" x2="400" y1="78" x1="360" stroke-width="5" stroke="#00dd00"/>
    <line id="l4" y2="78" x2="560" y1="78" x1="410" stroke-width="5" stroke="#0000dd"/>
    <text id="text4" fill="#111111" stroke="#111111" stroke-width="3" x="473" y="139" font-size="14" font-family="serif" text-anchor="middle" xml:space="preserve">Non-overlapping rectangles</text>
    <rect id="r3" fill-opacity="0" fill="#ffffff" height="120" width="80" y="167" x="370" stroke-width="5" stroke="#00dd00"/>
    <rect id="r4" fill-opacity="0" fill="#ffffff" height="70" width="50" y="197" x="470" stroke-width="5" stroke="#0000dd"/>
  </g>
</svg>
Categories: Software Tags:
  1. August 3, 2010 at 12:47 am

    Cool :)!

    How did you generate the SVG code?

  2. August 3, 2010 at 1:20 am

    Partially using http://code.google.com/p/svg-edit/, partially editing directly the source🙂.

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: