Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Tried to identify critical points solution in Clear category for Four To The Floor by HeNeArKr
# Attempt 2
# Test 'critical' points along the edge of each circle for membership in another
# circle. Critical points are
# 1) points closest to the room corners
# 2) points of intersection between circles
import math
from itertools import combinations
def four_corners(rect, circ):
""" Return the x, y coordinates of points on the circle closest to the
four corners of the rectangle.
"""
w, h = rect
x0, y0, r0 = circ
angles = [math.atan2(-y0, -x0), math.atan2(-y0, w-x0),
math.atan2(h-y0, w-x0), math.atan2(h-y0, -x0)]
return [(x0 + r0 * math.cos(angle), y0 + r0 * math.sin(angle))
for angle in angles]
def int_points(circ1, circ2):
""" Return list of x, y coordinates of 0, 1, or 2 points of intersection
between circ1 and circ2.
"""
x1, y1, r1 = circ1
x2, y2, r2 = circ2
d = math.sqrt((x2-x1)**2 + (y2-y1)**2)
# d = math.dist((x1, y1), (x2, y2)) # math.dist in Python 3.8
# Make sure circles intersect: neither entirely separate nor fully contained
if d <= r1 + r2 and d > abs(r1 - r2):
# 'parallel' = along line between the two centers
int_dist_par = (d**2 - r2**2 + r1**2) / (2*d)
angle1 = math.atan2(y2-y1, x2-x1)
xi = x1 + int_dist_par * math.cos(angle1)
yi = y1 + int_dist_par * math.sin(angle1)
if d == r1 + r2:
return [(xi, yi)]
else:
# 'perpendicular' = perpendicular distance to line between centers
int_dist_per = math.sqrt(r1**2 - int_dist_par**2)
dx = int_dist_per * math.cos(math.pi/2 - angle1)
dy = int_dist_per * math.sin(math.pi/2 - angle1)
return [(xi - dx, yi + dy), (xi + dx, yi - dy)]
return []
def in_circle(pt, circ):
x, y = pt
x0, y0, r0 = circ
return (x - x0)**2 + (y - y0)**2 <= r0**2
def is_covered(room, pirs):
w, h = room
# Test 'corners'
for pir in pirs:
x0, y0, r0 = pir
for x, y in four_corners(room, pir):
if 0 < x < w and 0 < y < h:
if not any(in_circle((x, y), other_pir)
for other_pir in pirs if other_pir != pir):
return False
# Test intersection points
for pir1, pir2 in combinations(pirs, 2):
for x, y in int_points(pir1, pir2):
if 0 < x < w and 0 < y < h:
if not any(in_circle((x, y), other_pir)
for other_pir in pirs if other_pir not in (pir1, pir2)):
return False
return True
Dec. 8, 2019
Comments:
