寻找另外 3 个圆的封闭圆的算法

Question

我有 3 个圆圈，它们可能/可能不互相接触。是否有可能通过算法找到包含所有这些圆并且具有最小尺寸的圆？

这似乎是最小圆问题，但用的是圆而不是点。我认为 Welzl 的算法不能用于这种情况。

我也认为不能使用计算三角形外接圆的算法。

有什么好的方法吗？

Answer 1

算法：

• 如果一个圆包含另外两个圆，则返回该圆作为结果。
• 对于任意两个给定的圆，计算它们的圆心之间的距离。
• 对于任意两个圆，如果一个圆足够大以完全包含另一个圆，则返回较大的圆。否则，计算包含两个圆的最小外接圆。
• 对于三个圆圈，首先尝试使用

  find_enclosing_circle_two

  将它们成对包围。如果任何一对可以包围第三个圆，则返回该包围圆。
• 如果没有成对解决方案，请计算三个圆的加权中心，权重与其半径成反比。
• 通过找出所有三个圆的中心到边缘的最大距离来计算封闭圆的半径。

实施：

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()

结果