I have 3 circles which may/may not be touching each other. Is it possible to find algorithmically circle which contains all those circles and have the minimal size?
It seems to be smallest-circle problem but with circles instead of points. I do not think Welzl’s algorithm can be used for this case.
I also think that algorithms for computing Circumcircle of triangle can not be used.
Any ideas what could be a good approach?
Algorithm:
- If one circle encompasses the other two, return that circle as the result.
- For any two given circles, calculate the distance between their centers.
- For any two circles, if one circle is large enough to fully contain the other one, return the larger one. Otherwise, calculate the smallest enclosing circle that contains both circles.
- For three circles, first try enclosing them pairwise using the
find_enclosing_circle_two
. If any pair can enclose the third circle, return that enclosing circle. - If no pairwise solution works, compute the weighted center of the three circles, with weights inversely proportional to their radii.
- Calculate the radius of the enclosing circle by finding out the max distance from the center to the edges of all the three circles.
Implementation:
import math
import matplotlib.pyplot as plt
def get_smallest(c1, r1, c2, r2, c3, r3):
def get_eucl_dist(p1, p2):
return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)
def encompass(c, r, cirs):
return all(get_eucl_dist(c, cir[0]) + cir[1] <= r for cir in cirs)
def find_enclosing_circle_two(c1, r1, c2, r2):
d = get_eucl_dist(c1, c2)
if r1 >= r2 + d:
return c1, r1
if r2 >= r1 + d:
return c2, r2
new_r = (d + r1 + r2) / 2
t = (new_r - r1) / d
new_c = (c1[0] + t * (c2[0] - c1[0]), c1[1] + t * (c2[1] - c1[1]))
return new_c, new_r
def find_enclosing_circle_three(c1, r1, c2, r2, c3, r3):
c12, r12 = find_enclosing_circle_two(c1, r1, c2, r2)
if encompass(c12, r12, [(c3, r3)]):
return c12, r12
c23, r23 = find_enclosing_circle_two(c2, r2, c3, r3)
if encompass(c23, r23, [(c1, r1)]):
return c23, r23
c31, r31 = find_enclosing_circle_two(c3, r3, c1, r1)
if encompass(c31, r31, [(c2, r2)]):
return c31, r31
def get_weighted_center_of_three_cirs(p1, r1, p2, r2, p3, r3):
W = [1 / r1, 1 / r2, 1 / r3]
total_w = sum(W)
x = (W[0] * p1[0] + W[1] * p2[0] + W[2] * p3[0]) / total_w
y = (W[0] * p1[1] + W[1] * p2[1] + W[2] * p3[1]) / total_w
return (x, y)
c = get_weighted_center_of_three_cirs(c1, r1, c2, r2, c3, r3)
r = max(get_eucl_dist(c, c1) + r1, get_eucl_dist(c, c2) + r2, get_eucl_dist(c, c3) + r3)
return c, r
return find_enclosing_circle_three(c1, r1, c2, r2, c3, r3)
cirs = (((10, 11), 5), ((7, 8), 3), ((13, 9), 4))
c1, r1 = cirs[0]
c2, r2 = cirs[1]
c3, r3 = cirs[2]
sm_c, sm_r = get_smallest(c1, r1, c2, r2, c3, r3)
fig, ax = plt.subplots()
for ct, rd in cirs:
cir = plt.Circle(ct, rd, color='blue', alpha=0.2)
ax.add_patch(cir)
ax.add_patch(plt.Circle(sm_c, sm_r, color='green', alpha=0.2, linewidth=1))
for ct, _ in cirs:
ax.plot(ct[0], ct[1], 'bo')
ax.plot(sm_c[0], sm_c[1], 'ro')
ax.set_xlim(0, 20)
ax.set_ylim(0, 20)
ax.set_aspect('equal')
plt.grid(True)
plt.show()
Result