24 
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.

Improve this question
2
  • "I am trying to see if two triangles intersect" – did you mean "rectangles"? Commented Nov 24, 2016 at 23:30
  • This would be really easy if you used 4 points for a rectangle or calculate the remaining 2 points for each rectangle. Then everytime a point of rectangle a is contained in rectangle b they would overlap. ;) Commented Nov 24, 2016 at 23:39

7 Answers 7

Reset to default
39

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

is there a way to check this with multiple rectangles?
@prb the brute force way is just to do pair-wise checks between each rectangle with all the other rectangles. To make it more efficient, store your rectangles in a spatial data structure (e.g. quadtree) and use it to generate a list of candidate pairs to compare. The exact type of data structure that works for you depends on you data (e.g. whether the rectangles are all of similar size, densely packed or sparsely spread etc)
dumb question but in this solution, your x axis starts at the left most, is that correct/
Isn't confusing using self as a python variable name?
@lorenzo it is self because it is for a class member function so the code calling/using it would look something like: ``` r1=Rectangle(Point(1,1), Point(2,2), 'blue') r3=Rectangle(Point(1.5,0), Point(1.7,3), 'red') r1.intersects(r3)
|
6

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
Improve this answer

Comments

4

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)
Improve this answer

Comments

3

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))
Improve this answer

3 Comments

hey hey. Is the try / except there to handle rects with equal bounds?
no, i think the try/except was a redundant remainder of my larger code project - I removed it to make the solution simpler, thanks
Due to edit queue is full, here is the correction: Polygon([(rect1[0],rect1[1]), (rect1[1],rect1[1]),(rect1[2],rect1[3]),(rect1[2],rect1[1]) to Polygon([(rect1[0],rect1[1]), (rect1[0],rect1[3]),(rect1[2],rect1[3]),(rect1[2],rect1[1])
1

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()

enter image description here

Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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)
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.