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)