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