algorithms

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

circle-and-rectangle-overlap.py (2542B)


      1 class Solution:
      2     def isVertical(self,p1,p2):
      3         return p1[0] == p2[0]
      4 
      5     def distance(self,p1,p2):
      6         return sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
      7     
      8     # t == target
      9     # s1 == relevant second scalar
     10     # s2 == relevant second scalar
     11     def nearestPos(self,s1,s2,t):
     12         lv = min(s1,s2)
     13         up = max(s2,s1)
     14         if t < up and t > lv:
     15             return t
     16         else:
     17             if t >= up:
     18                 return up
     19             else:
     20                 return lv
     21 
     22     def dist(self,a):
     23         return a[2]
     24     def nearest(self, corners, center, radius):
     25         
     26         best_by_edge = []
     27 
     28         for i in range(0,len(corners)):
     29             for j in range(i,len(corners)):
     30                 first = corners[i]
     31                 second = corners[j]
     32                 if self.isVertical(first, second):
     33                     ny = self.nearestPos(first[1], second[1], center[1])
     34                     ns = [first[0], ny]
     35                     ns.append(self.distance(ns,center))
     36                     best_by_edge.append(ns)
     37                 else:
     38                     nx = self.nearestPos(first[0], second[0], center[0])
     39                     ns = [nx,first[1]]
     40                     ns.append(self.distance(ns,center))
     41                     best_by_edge.append(ns)
     42         
     43         best_by_edge.sort(key=self.dist)
     44         return best_by_edge[0]
     45 
     46 
     47     def containsNearest(self, corners, center, radius):
     48         np = self.nearest(corners,center,radius)
     49         return self.distance(np,center) <= radius
     50     
     51     def centerEnclosed(self, corners,center):
     52         left = corners[0][0]
     53         right = corners[1][0]
     54         bottom = corners[2][1]
     55         top = corners[0][1]
     56 
     57         if top >= center[1] and bottom <= center[1] and left <= center[0] and right >= center[0]:
     58             return True
     59         return False
     60 
     61 
     62     def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:
     63         # idea:
     64             # if we consider the point in the rectangle, neares to xCenter,yCenter, if it's in the circle we return true
     65             # other case is circle is totally enclosed
     66 
     67         top_left = (x1,y2)
     68         top_right = (x2,y2)
     69         bottom_left = (x1,y1)
     70         bottom_right = (x2,y1)
     71 
     72         corners = (top_left,top_right,bottom_left,bottom_right)
     73         center = (xCenter,yCenter)
     74 
     75         res = self.containsNearest(corners, center, radius)
     76         if res:
     77             return res
     78         
     79         res = self.centerEnclosed(corners,center)
     80 
     81         return res