Calculate overlapped area between two rectangles

Question

enter image description here

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.

So what is your problem exactly? If you know all the corners points, you can easily calculate the corner of the intersection rectangle. The corner coordinates and the `min` and `max` functions should be all you need. — cel, Nov 26 '14 at 15:34
does shapely can calculate corner of the intersection rectangle? — Eric Bal, Nov 26 '14 at 15:43
I don't know that. Yet, I'm pretty sure you can figure out how you can calculate those corners on your own. Just look at the upper left corner: To be in the intersection you have to have an x_coord at least as large as the maximum of red and blue's left ends and a y_coord at most the minimum of red and blue's upper ends... you have similar arguments for each of the four corner points. — cel, Nov 26 '14 at 15:53
This is easy, but the main problem is notation. How do you define a rectangle in your code? For example, a tuple with values like: `(xmin, ymin, xmax, ymax)`, etc? — tom10, Nov 26 '14 at 22:38
@tom10 Each corner of rectangle is defined as (x,y) coordinate values, which can be used for getting (xmin, ymin, xmax, ymax) as you said. — Eric Bal, Nov 27 '14 at 02:41
Usually with a rectangle one only defines two points or four values since the other four are redundant. But, I'll just write am answer for (xmin,...) and let you go from there. — tom10, Nov 27 '14 at 03:09

tom10 · Accepted Answer · 2014-11-27T14:57:13.753

84

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.

edited Nov 27 '14 at 14:57

answered Nov 27 '14 at 02:54

tom10

67,082
10
127
137

1

thanks accepted, but does your code still works even if the blue polygon is at left side of the red polygon? – Eric Bal Nov 27 '14 at 05:30
4

@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. – tom10 Nov 27 '14 at 14:58
How to get the percentage area of overlap? – Santhosh Dhaipule Chandrakanth Aug 05 '19 at 13:32
@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? – tom10 Aug 14 '19 at 01:39
1

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. – Vorpal Swordsman May 06 '21 at 00:22
@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. – rayryeng Jun 10 '22 at 13:36
@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! – tom10 Jun 10 '22 at 16:25
@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! – rayryeng Jun 10 '22 at 17:28
@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 Jun 10 '22 at 18:07
@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. – tom10 Jun 10 '22 at 18:08
Oh I see! Sorry I misunderstood. Sure! I'll add it as an amendment. – rayryeng Jun 10 '22 at 18:46
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/245506/discussion-between-tom10-and-rayryeng). – tom10 Jun 10 '22 at 22:14

score 37 · Answer 2 · answered May 24 '19 at 09:57

37

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

answered May 24 '19 at 09:57

Georgy

12,464
7
65
73

1

@quant No, Shapely can be used only for planar geometry computations. – Georgy Jul 11 '20 at 09:43
According to your knowledge, is there something similar for higher dimensions ? – quant Jul 11 '20 at 09:47
1

@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](https://stackoverflow.com/q/38637603/7851470), [Geometric Computing with Python](https://geometryprocessing.github.io/geometric-computing-python/#packages-description), [Open3D](http://www.open3d.org/docs/release/). – Georgy Jul 11 '20 at 09:54

score 7 · Answer 3 · edited Jun 10 '22 at 13:29

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)

Calculate overlapped area between two rectangles

3 Answers3

Linked

Related