algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

rectangle-overlap.py (2646B)


      1 class Solution:
      2 
      3     def intersect(self, e1,e2):
      4         v1 = e1[0]
      5         v2 = e1[1]
      6 
      7         v3 = e2[0]
      8         v4 = e2[1]
      9 
     10         e1_is_vert = False
     11         e2_is_vert = False
     12 
     13         if v1[0] == v2[0]:
     14             e1_is_vert = True
     15         if v3[0] == v4[0]:
     16             e2_is_vert = True
     17         
     18         if e1_is_vert == e2_is_vert:
     19             return False
     20         
     21         if e1_is_vert:
     22             if v3[1] >= max(v1[1],v2[1]) or v3[1] <= min(v1[1],v2[1]):
     23                 return False
     24             if min(v3[0], v4[0]) < v1[0] and  max(v3[0], v4[0]) > v1[0]:
     25                 return True
     26             return False
     27         else:
     28             if v2[1] >= max(v3[1],v4[1]) or v2[1] <= min(v3[1],v4[1]):
     29                 return False
     30             if min(v1[0], v2[0]) < v3[0] and  max(v1[0], v2[0]) > v3[0]:
     31                 return True
     32             return False
     33     
     34     def contains(self,rect1,rect2):
     35         min_x_1 = rect1[0]
     36         max_x_1 = rect1[2]
     37         min_y_1 = rect1[1]
     38         max_y_1 = rect1[3]
     39 
     40         min_x_2 = rect2[0]
     41         max_x_2 = rect2[2]
     42         min_y_2 = rect2[1]
     43         max_y_2 = rect2[3]
     44 
     45         if min_x_1 >= min_x_2 and max_x_1 <= max_x_2:
     46             if min_y_1 >= min_y_2 and max_y_1 <= max_y_2:
     47                 return True
     48         return False
     49        
     50 
     51     def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
     52         # [x1,y1,           x2,y2]
     53         # bottom left,      top right
     54 
     55         # if rec1 and rec2 overlap return true
     56         # must fully overlap not just border
     57 
     58         # top left
     59         top_left = (rec2[0], rec2[3])
     60         # bottom left
     61         bottom_left = (rec2[0], rec2[1])
     62         # bottom right
     63         bottom_right = (rec2[2], rec2[1])
     64         # top right
     65         top_right = (rec2[2], rec2[3])
     66 
     67         rec2_edges = [
     68             [top_left, top_right],
     69             [top_left, bottom_left],
     70             [bottom_left, bottom_right],
     71             [bottom_right, top_right]
     72         ]
     73 
     74         # top left
     75         top_left = (rec1[0], rec1[3])
     76         # bottom left
     77         bottom_left = (rec1[0], rec1[1])
     78         # bottom right
     79         bottom_right = (rec1[2], rec1[1])
     80         # top right
     81         top_right = (rec1[2], rec1[3])
     82 
     83         rec1_edges = [
     84             [top_left, top_right],
     85             [top_left, bottom_left],
     86             [bottom_left, bottom_right],
     87             [bottom_right, top_right]
     88         ]
     89 
     90         for e1 in rec1_edges:
     91             for e2 in rec2_edges:
     92                 if self.intersect(e1,e2):
     93                     return True
     94 
     95         if self.contains(rec1,rec2) or self.contains(rec2,rec1):
     96             return True
     97         return False