如何用Python求解多边形的最小包围圆？

多边形由二维平面内的顶点坐标集合定义，我们需要求出能包围所有顶点的最小圆，输出圆心坐标和半径。输入支持元组列表、NumPy数组等格式，可处理最多100个顶点的多边形。

方法一：用Shapely快速实现（推荐） #

Shapely是专业的几何计算库，内置最小包围圆的求解方法，无需手动实现算法，代码简洁高效。

步骤 #

1. 安装依赖：

pip install shapely

2. 实现代码：

from shapely.geometry import MultiPoint

def get_min_enclosing_circle(vertices):
    # 将顶点转换为多点几何对象
    multi_point = MultiPoint(vertices)
    # 计算最小包围圆
    min_circle = multi_point.minimum_bounding_circle()
    # 提取圆心和半径，保留4位小数
    center = (round(min_circle.centroid.x, 4), round(min_circle.centroid.y, 4))
    radius = round(min_circle.radius, 4)
    return (center, radius)

# 示例测试
square_vertices = [(2, 2), (0, 2), (2, 0), (0, 0)]
print(get_min_enclosing_circle(square_vertices))  # 输出 ((1.0, 1.0), 1.4142)

方法二：纯数值计算实现（无额外依赖） #

通过凸包优化减少计算点数量，再用Welzl递归算法求解最小圆，适合需要自定义逻辑或无法安装第三方库的场景。

实现代码 #

import numpy as np
from scipy.spatial import ConvexHull

def circle_from_two_points(p1, p2):
    # 两点确定的圆
    center = ((p1[0]+p2[0])/2, (p1[1]+p2[1])/2)
    radius = np.linalg.norm(np.array(p1)-np.array(p2))/2
    return center, radius

def circle_from_three_points(p1, p2, p3):
    # 三点确定的外接圆
    A = np.array([
        [2*(p2[0]-p1[0]), 2*(p2[1]-p1[1])],
        [2*(p3[0]-p1[0]), 2*(p3[1]-p1[1])]
    ])
    b = np.array([
        p2[0]**2 - p1[0]**2 + p2[1]**2 - p1[1]**2,
        p3[0]**2 - p1[0]**2 + p3[1]**2 - p1[1]**2
    ])
    center = np.linalg.solve(A, b)
    radius = np.linalg.norm(np.array(p1)-center)
    return tuple(center), radius

def welzl_algorithm(points, R):
    # Welzl递归算法求解最小圆
    if len(points) == 0 or len(R) == 3:
        if len(R) == 0:
            return ((0,0), 0)
        elif len(R) == 1:
            return (R[0], 0)
        elif len(R) == 2:
            return circle_from_two_points(R[0], R[1])
        else:
            return circle_from_three_points(R[0], R[1], R[2])
    idx = np.random.randint(len(points))
    p = points[idx]
    points = points[:idx] + points[idx+1:]
    center, radius = welzl_algorithm(points, R)
    # 加入浮点误差容忍，避免精度问题
    if np.linalg.norm(np.array(p)-np.array(center)) <= radius + 1e-8:
        return center, radius
    else:
        return welzl_algorithm(points, R + [p])

def min_enclosing_circle(vertices):
    # 先计算凸包，减少计算点数量
    points = np.array(vertices)
    hull = ConvexHull(points)
    hull_points = [tuple(points[i]) for i in hull.vertices]
    # 用Welzl算法计算最小圆
    center, radius = welzl_algorithm(hull_points, [])
    return (tuple(np.round(center, 4)), round(radius, 4))

# 示例测试
square_vertices = [(2, 2), (0, 2), (2, 0), (0, 0)]
print(min_enclosing_circle(square_vertices))  # 输出 ((1.0, 1.0), 1.4142)

关键优化说明 #

• 凸包优化：最小包围圆的边界必然经过多边形凸包上的顶点，先提取凸包能大幅减少后续计算的点数量，提升处理100个顶点时的效率。
• 精度控制：代码中加入了1e-8的误差容忍，避免浮点计算的精度问题导致误判点是否在圆内。

内容的提问来源于stack exchange，提问作者makeyourownmaker