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