Area of Rectangle-Rectangle Intersection

Area of rectangle-rectangle intersection

Since you stated that the rectangles may not be aligned, possible answers may be nothing, a point, a line segment, or a polygon with 3-8 sides.

The usual way to do this 2d boolean operation is to choose a counterclockwise ordering of the edges, and then evaluate edge segments between critical points (intersections or corners). At each intersection you switch between an edge segment of the first rectangle to an edge of the second, or visa-versa. You always pick the segment to the left of the previous segment.

There are LOTS of details, but the basic algorithm is to find all intersections and order them on their edges with an appropriate data structure. Choose an intersection (if there is one) and choose a line segment leading away from that intersection. Find the segment of the other rectangle to the left of the chosen starting segment. In the picture, we choose the green segment on intersection a (in the direction indicated by the arrow) as the reference segment. The segment of the other rectangle that is to the right, is the segment from a to b. Use that as the next reference segment, and choose a green segment to the left of it. That's the segment from b to c. Find segment cd the same way. The next segment is from d to the corner, so the corner is in the vertex list for the intersection as well. From the corn we get back to a.

To choose the left side each time, you use the determinate of the coordinates of the direction vectors for the edges that meet. If the determinant for the ordered pair of directed edges is positive, you're going the right way.

Now that you have the vertices of the intersection polygon, you can use the surveyor's formula to get the area.

Some of the details that I'm leaving to you are:

• What if a corner is coincident to to an edge or vertex of the other triangle?

• What if there are no intersections? (one rectangle is inside the other, or they are disjoint--you can use point-in-polygon checks to figure this out. See the Wikipedia article on polygons.

• What if the intersection is a single point or a segment?

Fast rectangle to rectangle intersection

This is how that code can be translated to JavaScript. Note that there is a typo in your code, and in that of the article, as the comments have suggested. Specifically r2->right left should be r2->right < r1->left and r2->bottom top should be r2->bottom < r1->top for the function to work.

function intersectRect(r1, r2) {
  return !(r2.left > r1.right || 
           r2.right < r1.left || 
           r2.top > r1.bottom ||
           r2.bottom < r1.top);
}

Test case:

var rectA = {
  left:   10,
  top:    10,
  right:  30,
  bottom: 30
};

var rectB = {
  left:   20,
  top:    20,
  right:  50,
  bottom: 50
};

var rectC = {
  left:   70,
  top:    70,
  right:  90,
  bottom: 90
};

intersectRect(rectA, rectB);  // returns true
intersectRect(rectA, rectC);  // returns false

Calculate overlapped area between two rectangles

This type of intersection is easily done by the "min of the maxes" and "max of the mins" idea. To write it out one needs a specific notion for the rectangle, and, just to make things clear I'll use a namedtuple:

from collections import namedtuple
Rectangle = namedtuple('Rectangle', 'xmin ymin xmax ymax')

ra = Rectangle(3., 3., 5., 5.)
rb = Rectangle(1., 1., 4., 3.5)
# intersection here is (3, 3, 4, 3.5), or an area of 1*.5=.5

def area(a, b):  # returns None if rectangles don't intersect
    dx = min(a.xmax, b.xmax) - max(a.xmin, b.xmin)
    dy = min(a.ymax, b.ymax) - max(a.ymin, b.ymin)
    if (dx>=0) and (dy>=0):
        return dx*dy

print area(ra, rb)
#  0.5 

If you don't like the namedtuple notation, you could just use:

dx = max(a[0], b[0]) - min(a[2], b[2])

etc, or whatever notation you prefer.

Intersection area of all n rectangles

You only need to find 4 items: the maximum value of the left position and the top position, and the minimum value of the right position and the bottom position. (Assuming the positive axis of X and Y point to right and down, as is often the case in CS)

So the minimal code could be:

int lv = -1, tv = -1, rv = 10001, bv = 10001;
int l, t, r, b;
for (int i = 0; i < N; i++) {
    // cin >> l >> t >> r >> b; Input
    lv = max(lv, l);
    tv = max(tv, t);
    rv = min(rv, r);
    bv = min(bv, b);
}

Then you know if lv <= rv && tv <= bv, there's an intersection specified by those 4 values. If lv > rv || tv > bv, there's no common intersection.

Area of Intersection of Two Rotated Rectangles

A simple algorithm that will give an approximate answer is sampling.

Divide one of your rectangles up into grids of small squares. For each intersection point, check if that point is inside the other rectangle. The number of points that lie inside the other rectangle will be a fairly good approximation to the area of the overlapping region. Increasing the density of points will increase the accuracy of the calculation, at the cost of performance.

Get the points of intersection from 2 rectangles

If the input rectangles are normalized, i.e. you already know that x1 < x2, y1 < y2 (and the same for the second rectangle), then all you need to do is calculate

int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);

and it will give you your intersection as rectangle (x5, y5)-(x6, y6). If the original rectangles do not intersect, the result will be a "degenerate" rectangle (with x5 >= x6 and/or y5 >= y6), which you can easily check for.

P.S. As usual, small details will depend on whether you have to consider touching rectangles as intersecting.

Determine if two rectangles overlap each other?

if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
     RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 

or, using Cartesian coordinates

(With X1 being left coord, X2 being right coord, increasing from left to right and Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top -- if this is not how your coordinate system [e.g. most computers have the Y direction reversed], swap the comparisons below) ...

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 > RectB.Y2 && RectA.Y2 < RectB.Y1) 

Say you have Rect A, and Rect B.
Proof is by contradiction. Any one of four conditions guarantees that no overlap can exist:

• Cond1. If A's left edge is to the right of the B's right edge,
  - then A is Totally to right Of B
• Cond2. If A's right edge is to the left of the B's left edge,
  - then A is Totally to left Of B
• Cond3. If A's top edge is below B's bottom edge,
  - then A is Totally below B
• Cond4. If A's bottom edge is above B's top edge,
  - then A is Totally above B

So condition for Non-Overlap is

NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

Therefore, a sufficient condition for Overlap is the opposite.

Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

De Morgan's law says

Not (A or B or C or D) is the same as Not A And Not B And Not C And Not D
so using De Morgan, we have

Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

This is equivalent to:

• A's Left Edge to left of B's right edge, [RectA.Left < RectB.Right], and
• A's right edge to right of B's left edge, [RectA.Right > RectB.Left], and
• A's top above B's bottom, [RectA.Top > RectB.Bottom], and
• A's bottom below B's Top [RectA.Bottom < RectB.Top]

Note 1: It is fairly obvious this same principle can be extended to any number of dimensions.

Note 2: It should also be fairly obvious to count overlaps of just one pixel, change the < and/or the > on that boundary to a <= or a >=.

Note 3: This answer, when utilizing Cartesian coordinates (X, Y) is based on standard algebraic Cartesian coordinates (x increases left to right, and Y increases bottom to top). Obviously, where a computer system might mechanize screen coordinates differently, (e.g., increasing Y from top to bottom, or X From right to left), the syntax will need to be adjusted accordingly/

getting the area of two intersecting rectangles

Your code is almost correct. The way you posted the code is confusing because it seems this refers to one rect and rect2 refers to a second rect. Why not make an Rect#area() method instead of computing the area of intersection separately?

class Rect {

    double x, y, width, height;

    ... members and stuff

    Rect intersection(Rect rect2) {
        double newX = Math.max(this.x, rect2.x);
        double newY = Math.max(this.y, rect2.y);

        double newWidth = Math.min(this.x + this.width, rect2.x + rect2.width) - newX;
        double newHeight = Math.min(this.y + this.height, rect2.y + rect2.height) - newY;

        if (newWidth <= 0d || newHeight <= 0d) return null;

        return new Rect(newX, newY, newWidth, newHeight);
    }

    double area() {
        return this.width * this.height;
    }

}

Then you would just do

Rect intersection = rect1.intersection(rect2);    
double areaOfIntersection = intersection == null ? 0 : intersection.area();

---

Related Topics