Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Geometric solution solution in Clear category for Four To The Floor by martin_b
# the idea is that the room is fully covered if the bounding rectangle lines are covered
# and also all sensor circle intersection lines within the room are fully covered
from itertools import combinations
def circle_line_intersection(c, l):
(cx, cy, cr) = c
(px1, py1, px2, py2) = l
x1, y1, x2, y2 = px1 - cx, py1 - cy, px2 - cx, py2 - cy
dx, dy = x2 - x1, y2 - y1
dr = (dx ** 2 + dy ** 2)**.5
big_d = x1 * y2 - x2 * y1
d = cr ** 2 * dr ** 2 - big_d ** 2
if d < 0: # no intersection between circle and line
return []
else: # there is 1 or 2 intersections with the segment
intersections = [
(cx + (big_d * dy + sign * (-1 if dy < 0 else 1) * dx * d**.5) / dr ** 2,
cy + (-big_d * dx + sign * abs(dy) * d**.5) / dr ** 2)
for sign in ((1, -1) if dy < 0 else (-1, 1))] # this makes sure the order along the segment is correct
# if line is tangent to circle, return just one point (as both intersections have same location)
if len(intersections) == 2 and abs(d) < 1e-9:
return [intersections[0]]
return intersections
def circles_intersection(c1, c2):
(x0, y0, r0), (x1, y1, r1) = c1, c2
d = ((x1 - x0)**2 + (y1 - y0)**2)**.5
# non intersecting or one circle within other or coincident circles
if d > r0 + r1 or d < abs(r0 - r1) or d == 0 and r0 == r1:
return []
a = (r0**2 - r1**2 + d**2) / (2 * d)
h = (r0**2 - a**2)**.5
x2 = x0 + a * (x1 - x0) / d
y2 = y0 + a * (y1 - y0) / d
x3 = x2 + h * (y1 - y0) / d
y3 = y2 - h * (x1 - x0) / d
x4 = x2 - h * (y1 - y0) / d
y4 = y2 + h * (x1 - x0) / d
# if touching circles, return one point
if ((x3 - x4)**2 + (y3 - y4)**2)**.5 < 1e-9:
return [(x3, y3)]
return [(x3, y3), (x4, y4)]
# the function is_covered_line checks that the line given by two points
# is fully covered by the sensors withing the bounding rectangle
def is_covered_line(line, sensors, rx, ry):
(px1, py1, px2, py2) = line
dx, dy = px2 - px1, py2 - py1
# compute intersection of the line with the bounding rectangle as the initial not covered section
# it is enough to check only along one axis, use less steep gradient for better numerical precision
if abs(dx) < 1e-9:
x_axis = False
nl, nh = 0, ry
else:
k = dy / dx
c = py1 - k * px1
if abs(dx) > abs(dy):
# get range to check on x axis
x_axis = True
if abs(k) > 1e-9:
x0, xr = -c / k, (ry - c) / k
if x0 > xr:
x0, xr = xr, x0
else:
x0, xr = 0, rx
nl, nh = max(0, x0), min(rx, xr)
else:
# get range to check on y axis
x_axis = False
y0, yr = c, k * rx + c
if y0 > yr:
y0, yr = yr, y0
nl, nh = max(0, y0), min(ry, yr)
# collect all intersections
intersections = []
for s in sensors:
intersection = circle_line_intersection(s, line)
# 2 point intersecion is necessary for coverage
if len(intersection) != 2:
continue
if x_axis:
((low, _), (high, _)) = intersection
else:
((_, low), (_, high)) = intersection
if low > high:
low, high = high, low
intersections.append((low, high))
# sort them in growing order
intersections.sort()
for (low, high) in intersections:
if nl < low:
# the low part of the intersection does not cover the line segment
return False
if nh <= high:
# the line segment is completely covered
return True
if nl < high:
# make the not covered part smaller
nl = high
return False
def is_covered(room, sensors):
(rx, ry) = room
is_covered_line((30, 0, 30, 10), sensors, rx, ry)
edges = ((0, 0, rx, 0), (0, 0, 0, ry),
(rx, 0, rx, ry), (0, ry, rx, ry))
# check that the edges are fully covered
for edge in edges:
if not is_covered_line(edge, sensors, rx, ry):
return False
# if more than one sensor, check that all circle intersection lines is fully covered
if len(sensors) > 1:
for c in combinations(sensors, 2):
intersection = circles_intersection(c[0], c[1])
if len(intersection) == 2:
if not is_covered_line(sum(intersection, ()), sensors, rx, ry):
return False
return True
March 5, 2020
Comments:
