# Overlap of circle to Rectangle

Today (04/04/2020)’s leetcode biweekly contest we have an interestinig problem.

1401. Circle and Rectangle Overlapping

I didn’t fully use the property of axis-aligned and made the solution much longer.
Also “The cool thing is that the same idea works not just for rectangles but for the intersection of a circle with any simple polygon — doesn’t even have to be convex!”
The idea is from
https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection
Ugly coding it up for reference.

# Axis not aligned

`class Solution:    def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:        #https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection        def dot_(A,B):            return A[0]*B[0]+A[1]*B[1]        def dis_(x,y):            return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5        def pointInRectangle(P, A,B,C,D):            #0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD            AB = [B[i]-A[i] for i in range(2)]            AP = [P[i]-A[i] for i in range(2)]            AD = [D[i]-A[i] for i in range(2)]            return 0<=dot_(AP, AB)<=dot_(AB,AB) and 0<=dot_(AP, AD)<=dot_(AD, AD)        def findFoot(a, b, c, x1, y1):              #https://www.geeksforgeeks.org/find-foot-of-perpendicular-from-a-point-in-2-d-plane-to-a-line/            temp = (-1 * (a * x1 + b * y1 + c) // (a * a + b * b))              x = temp * a + x1              y = temp * b + y1              return [x, y]        def intersectCircle(S, A, B):            P, R =S            if dis_(A, P)<=R or  dis_(B, P) <=R:return True            foot = [0, 0]            if A[0]==B[0]:                foot[0] = A[0]                foot[1] = P[1]            elif A[1]==B[1]:                foot[0] = P[0]                foot[1] = A[1]            else: # axis aligned does not need this branch                xa, ya = A                xb, yb = B                #(yA−yB)x−(xA−xB)y+xAyB−xByA=0.                a,b,c = ya-yb, xb-xa, xa*yb-xb*ya                foot=findFoot(a, b, c, P[0], P[1])            if min(A[0], B[0])<=foot[0]<=max(A[0], B[0]) and min(A[1], B[1])<=foot[1]<=max(A[1], B[1]):                if dis_(foot, P)<=R:return True                        return False                         def intersect(P, R, A, B, C, D):            S = (P, R)            return (pointInRectangle(P, A, B, C, D) or                    intersectCircle(S, A, B) or                    intersectCircle(S, B, C) or                    intersectCircle(S, C, D) or                    intersectCircle(S, D, A))        A, B, C, D = (x1,y2),(x2,y2),(x2,y1),(x1,y1)        return intersect((x_center, y_center), radius, A, B, C, D)`

# Axis aligned

`class Solution:    def checkOverlap(self, radius: int, x_center: int, y_center: int, x1: int, y1: int, x2: int, y2: int) -> bool:        #https://stackoverflow.com/questions/401847/circle-rectangle-collision-detection-intersection        def dot_(A,B):            return A[0]*B[0]+A[1]*B[1]        def dis_(x,y):            return ((x[0]-y[0])**2+(x[1]-y[1])**2)**0.5        def pointInRectangle(P, A,B,C,D):            #0 ≤ AP·AB ≤ AB·AB and 0 ≤ AP·AD ≤ AD·AD            AB = [B[i]-A[i] for i in range(2)]            AP = [P[i]-A[i] for i in range(2)]            AD = [D[i]-A[i] for i in range(2)]            return 0<=dot_(AP, AB)<=dot_(AB,AB) and 0<=dot_(AP, AD)<=dot_(AD, AD)        def intersectCircle(S, A, B):            P, R =S            if dis_(A, P)<=R or  dis_(B, P) <=R:return True            foot = [0, 0]            if A[0]==B[0]:                foot[0] = A[0]                foot[1] = P[1]            elif A[1]==B[1]:                foot[0] = P[0]                foot[1] = A[1]            if min(A[0], B[0])<=foot[0]<=max(A[0], B[0]) and min(A[1], B[1])<=foot[1]<=max(A[1], B[1]):                if dis_(foot, P)<=R:return True                        return False                         def intersect(P, R, A, B, C, D):            S = (P, R)            return (pointInRectangle(P, A, B, C, D) or                    intersectCircle(S, A, B) or                    intersectCircle(S, B, C) or                    intersectCircle(S, C, D) or                    intersectCircle(S, D, A))        A, B, C, D = (x1,y2),(x2,y2),(x2,y1),(x1,y1)        return intersect((x_center, y_center), radius, A, B, C, D)`

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi