Checking whether two rectangles overlap in python using two bottom left corners and top right corners

Question

class Point:

    def __init__(self, xcoord=0, ycoord=0):
        self.x = xcoord
        self.y = ycoord

class Rectangle:
    def __init__(self, bottom_left, top_right, colour):
        self.bottom_left = bottom_left
        self.top_right = top_right
        self.colour = colour

    def intersects(self, other):

I am trying to see if two rectangles intersect based on the upper right and lower left corners however when I make the function:

def intersects(self, other):
    return self.top_right.x>=other.top_right.x>=self.bottom_left.x and self.top_right.x>=other.bottom_left.x>=self.bottom_left.x and self.top_right.y>=other.top_right.y>=self.bottom_left.y and self.top_right.x>=other.bottom_left.x>=self.bottom_left.x

The function will return false when inputting:

r1=Rectangle(Point(1,1), Point(2,2), 'blue')
r3=Rectangle(Point(1.5,0), Point(1.7,3), 'red')
r1.intersects(r3)

into the shell.

Answer 1

You can use a simple version of the Separating Axis Theorem to test for intersection. If the rectangles do not intersect, then at least one of the right sides will be to the left of the left side of the other rectangle (i.e. it will be a separating axis), or vice versa, or one of the top sides will be below the bottom side of the other rectange, or vice versa.

So change the test to check if it is not true that they don't intersect:

def intersects(self, other):
    return not (self.top_right.x < other.bottom_left.x
                or self.bottom_left.x > other.top_right.x
                or self.top_right.y < other.bottom_left.y
                or self.bottom_left.y > other.top_right.y)

This code assumes that the "top" has a greater y value than the "bottom" (y decreases down the screen), because that's how your example seems to work. If you were using the other convention then you'd just flip the signs of the y comparisons.

Answer 2

Awesome solutions here but I haven't seen any with the pattern (top_x, top_y) as the top-left point and (bottom_x, bottom_y) as the bottom-right point of the bounding box. I would like to share a solution that analyses this pattern, despite that you can just infer the top-right and bottom-left points from this pattern and use the mentioned solutions.

Here is the code:

def bbox_intersect(bbox_a, bbox_b):
    (a_top_x, a_top_y), (a_bot_x, a_bot_y) = bbox_a
    (b_top_x, b_top_y), (b_bot_x, b_bot_y) = bbox_b
    
    cond_1 = a_top_x < b_top_x < a_bot_x
    cond_2 = b_top_x < a_top_x < b_bot_x
    cond_3 = a_top_y < b_top_y < a_bot_y
    cond_4 = b_top_y < a_top_y < b_bot_y
    
    return (cond_1 or cond_2) and (cond_3 or cond_4)

Answer 3

Comparing all answers I found, @samgak answer is the best.

def is_overlapping_1D(line1, line2):
    """
    line:
        (xmin, xmax)
    """
    return line1[0] <= line2[1] and line2[0] <= line1[1]

def is_overlapping_2d(box1, box2):
    """
    box:
        (xmin, ymin, xmax, ymax)
    """
    return is_overlapping_1D([box1[0],box1[2]],[box2[0],box2[2]]) and is_overlapping_1D([box1[1],box1[3]],[box2[1],box2[3]])

from shapely.geometry import Polygon
def overlap2(box1, box2):
    p1 = Polygon([(box1[0],box1[1]), (box1[0],box1[3]), (box1[2],box1[3]),(box1[2],box1[1])])
    p2 = Polygon([(box2[0],box2[1]), (box2[0],box2[3]), (box2[2],box2[3]),(box2[2],box2[1])])
    return p1.intersects(p2)

def intersects(box1, box2):
    return not (box1[2] < box2[0] or box1[0] > box2[2] or box1[1] > box2[3] or box1[3] < box2[1])

# xyxy (xmin, xmax, ymin, ymax)
boxes = [
    (200,70,240,110),
    (10,10,60,60),
    (30,20,70,60),
    (100, 90, 190, 180),
    (50,100,150,200),
    (180,190,220,230),
    (10,210,40,240)
]

%%timeit
boxes_merged = iterate_merge(intersects, unify, boxes)

%%timeit
boxes_merged = iterate_merge(overlap2, unify, boxes)

%%timeit
boxes_merged = iterate_merge(is_overlapping_2d, unify, boxes)

67.5 µs ± 313 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

924 µs ± 1.12 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

83.1 µs ± 223 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 4

I recently came across this problem and today came across named tuples, so I thought I'd give it a go:

from collections import namedtuple

RECT_NAMEDTUPLE = namedtuple('RECT_NAMEDTUPLE', 'x1 x2 y1 y2')

Rect1 = RECT_NAMEDTUPLE(10,100,40,80)
Rect2 = RECT_NAMEDTUPLE(20,210,10,60)

def overlap(rec1, rec2):
  if (rec2.x2 > rec1.x1 and rec2.x2 < rec1.x2) or \
     (rec2.x1 > rec1.x1 and rec2.x1 < rec1.x2):
    x_match = True
  else:
    x_match = False
  if (rec2.y2 > rec1.y1 and rec2.y2 < rec1.y2) or \
     (rec2.y1 > rec1.y1 and rec2.y1 < rec1.y2):
    y_match = True
  else:
    y_match = False
  if x_match and y_match:
    return True
  else:
    return False

print ("Overlap found?", overlap(Rect1, Rect2))

Overlap found? True

Answer 5

It can also be done with Polygon from shapely (example for a rectangle with [x0,y0,x1,y1]

from shapely.geometry import Polygon
import numpy as np

rect1=np.array([0  ,0 ,3,  3])
rect2=np.array([1, 1 , 4 , 4])

def overlap2(rect1,rect2):
    p1 = Polygon([(rect1[0],rect1[1]), (rect1[1],rect1[1]),(rect1[2],rect1[3]),(rect1[2],rect1[1])])
    p2 = Polygon([(rect2[0],rect2[1]), (rect2[1],rect2[1]),(rect2[2],rect2[3]),(rect2[2],rect2[1])])
    return(p1.intersects(p2))

print(overlap2(rect1,rect2))

Answer 6

Here is what you can do before writing the code: 1. Think of the cases where the two rectangles won't overlap 2. Start by choosing the pair comparison of each color coded x and y. For example compare rectangle.A.X1 an compare it to Rectangle.B.X2

Here is the code

def check_for_overlap():
    rectangle_a  = {"x1":15, "y1":10, "x2":10,"y2":5}
    rectangle_b  = {"x1": 25, "y1":10, "x2":20,"y2":5}
    #black color                           or    red color
    if(rectangle_a["y1"]<rectangle_b["y2"] or rectangle_a["x1"]<rectangle_b["x2"]):
        print("no overlap ")
    #the blue color                          or   green 
    elif(rectangle_a["x2"]>rectangle_b["x1"] or rectangle_a["y2"]>rectangle_b["y1"]):
        print("no overlap ")
    else:
        print("YES ! there is a overlap")

check_for_overlap()

Answer 7

What I did was to figure out which rectangle is at the top, which is at the bottom; also which is to the left, which is to the right. Eventually, we are talking about the same two rectangles that we are comparing. But getting the right/left and top/bottom help use simplify the conditions. Once we got the right/left, and top/down, we can compare overlap, non-overlap, and contains.

class Rectangle:
# Create rectangle with center at (x, y)
# width x, and height h

    def __init__(self, x, y, w, h):
    self._x = float(x)
    self._y = float(y)
    self._width = float(w)
    self._height = float(h)
    # Extended four instance variables
    self._x0 = self._x - self._width / 2
    self._x1 = self._x + self._width / 2
    self._y0 = self._y - self._height / 2
    self._y1 = self._y + self._height/2
    # True if self intersects other; False otherwise
    def intersects(self, other):

        # find which rectangle is on the left
        leftRec = None
        rightRec = None
        if self._x1 >= other._x1:
            leftRec = other
            rightRec = self
        else:
            leftRec = self
            rightRec = other

        # find which rectangle is on the top
        topRec = None
        lowRec = None
        if self._y1 >= other._y1:
            topRec = self
            lowRec = other
        else:
            topRec = other
            lowRec = self

        if (leftRec._x0 + leftRec._width <= rightRec._x0) or (lowRec._y0 + lowRec._height <= topRec._y0):
            # Not overlap
            return False
        elif (leftRec._x0 + leftRec._width <= rightRec._x0 + rightRec._width) or (lowRec._y0 + lowRec._height <= topRec._y0 + topRec._height):
            # full overlap, contains
            return False
        else:
            # intersect
            return True

Basically, if the bottom left x value of the left rectangle plus its width is less than the right rectangle's bottom left x value, then it is non-overlapping. If the bottom left x value of the left rectangle plus its width is less or equal to the right rectangle's bottom left x value plus its width, than the right fully overlaps the left. Other than these, it is intersection. Compare the same for top and down, then combine together, you'll be able to find intersection.