Calculate overlapped area between two rectangles

Question

I want to calculate the overlapped area "THE GRAY REGION" between red and blue rectangles.

Each rectangle is defined by its four corner coordinates. The resulted unit of the overlapped area is unit square.

I could not imagine how can I do it?

Any creative comments would be appreciated.

Solution 1

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.

Solution 2

As this question has a shapely tag, here is a solution using it. I will use the same rectangles as in the tom10 answer:

from shapely.geometry import Polygon

polygon = Polygon([(3, 3), (5, 3), (5, 5), (3, 5)])
other_polygon = Polygon([(1, 1), (4, 1), (4, 3.5), (1, 3.5)])
intersection = polygon.intersection(other_polygon)
print(intersection.area)
# 0.5

This is much more concise than the version in the accepted answer. You don't have to construct your own Rectangle class as Shapely already provides the ready ones. It's less error-prone (go figure out the logic in that area function). And the code itself is self-explanatory.

---

References:
Docs for object.intersection(other) method

Solution 3

Since the post is very related to computer vision and object detection, I thought of putting some code together that I use for finding the intersection of bounding boxes and also finding their intersection over union (IoU). This code was originally developed by Adrian Rosebrock in this blog post:

This is the module (where I named it Bbox):

class Bbox:
    def __init__(self, x1, y1, x2, y2):
        self.x1 = max(x1, x2)
        self.x2 = min(x1, x2)
        self.y1 = max(y1, y2)
        self.y2 = max(y1, y2)
        self.box = [self.x1, self.y1, self.x2, self.y2]
        self.width = abs(self.x1 - self.x2)
        self.height = abs(self.y1 - self.y2)

    @property
    def area(self):
        """
        Calculates the surface area. useful for IOU!
        """
        return (self.x2 - self.x1 + 1) * (self.y2 - self.y1 + 1)

    def intersect(self, bbox):
        x1 = max(self.x1, bbox.x1)
        y1 = max(self.y1, bbox.y1)
        x2 = min(self.x2, bbox.x2)
        y2 = min(self.y2, bbox.y2)
        intersection = max(0, x2 - x1 + 1) * max(0, y2 - y1 + 1)
        return intersection

    def iou(self, bbox):
        intersection = self.intersection(bbox)

        iou = intersection / float(self.area + bbox.area - intersection)
        # return the intersection over union value
        return iou

And to use it:

a = Bbox([516, 289, 529, 303])
b = Bbox([487, 219, 533, 342])

result = a.intersect(b)

Comments

[Eric Bal]

thanks accepted, but does your code still works even if the blue polygon is at left side of the red polygon?

[tom10]

@just: Yes, it works either way. Using the max and min approach is just an easy way of what would otherwise be a complicated set of conditionals to determine the relative positions. That is, read max(a.xmin, b.xmin) as the "righmost left corner", etc. Also, I changed my answer to now include the case when the rectangles don't intersect.

[Santhosh Dhaipule Chandrakanth]

How to get the percentage area of overlap?

[tom10]

@SanthoshDhaipuleChandrakanth: It would be better to ask a separate question. For example, here it's not clear what you mean by percentage, specifically, the area of overlap is clear, by what area are you comparing that to -- the maximum area, the area of the two initial rectangles, etc?

[Georgy]

@quant No, Shapely can be used only for planar geometry computations.

[quant]

According to your knowledge, is there something similar for higher dimensions ?

[Georgy]

@quant I've never worked with geometries of 3 or more dimensions. Googling gives the following links. Maybe they can be of any help: 3D Geometry Package for Python, Geometric Computing with Python, Open3D.

[Vorpal Swordsman]

Just a note: Be sure to use the right points -- on Cartesian axes, the "top left" is x.min, but y.max. On a monitor, x.min, y.min is at the upper left and x.max, y.max is lower right.

[rayryeng]

@tom10: Hi! This answer was very useful for me and thanks for posting it. As we see in the previous comment, the points to sample are dependent on whether you are using the traditional Cartesian system, meaning the y-axis is positive upwards, or in images / graphics where the y-axis is pointing downwards. May I modify your post so that it can take in an optional parameter to decide what convention we would use to output the right area by sampling the right coordinates? I think it would be more useful and more people would benefit! I'll also be verbose and add more comments to clarify.

[tom10]

@rayryeng: That seems like a good idea. My caveat is that both the appealing aspect and the confusion of this min/max approach is that it deals with multiple cases through the min/max functions. To now deal with another case seems even more confusing. My suggestion then is that even if your changes are elegant and minimal, it will probably better to post it as a separate piece of code below the simple version I already have, in order to build it up conceptually. With that in mind, I think it would be great to extend this answer to that case. Thanks!

[rayryeng]

@tom10 Oh! Yeah that's an even better idea. I don't want to pollute your answer as it is already ready-to-go and easy to understand. I can make another answer that can extend what you have here to accommodate for what I've mentioned. Thanks!

[tom10]

@rayryeng: Actually, I wasn't implying writing your own answer, but just extending mine, making it longer with your code rather than replacing my code. (I'm fine if you want to write your own answer, but usually people won't see it since it will be low on the list, and these seem like a useful and important addition. And I'm not at all worried about my answer being "polluted"--it could really use improvement. My answer is a fine core idea, but other than that, isn't as helpful as it could be.)

[tom10]

@rayryeng: Also, my previous comment was primarily about code, but, to be clear, any explanatory or descriptive text that you think would help will be appreciated, and feel free to edit or delete what I have. In retrospect, my explanation here could use improvement. At the least I should have put what I have in my first comment into the answer, but I'm interested to see what you have in mind.

[rayryeng]

Oh I see! Sorry I misunderstood. Sure! I'll add it as an amendment.

[tom10]

Let us continue this discussion in chat.