如何拟合包围全部数据点的闭合曲线（如椭圆、圆）？

一、最小包围圆实现 #

最小包围圆是能包含所有数据点的面积最小的圆，Welzl算法是高效的实现方案，这是一种递归随机算法，可快速处理任意点集。

代码实现（Python） #

import numpy as np

def welzl(points, r):
    if len(points) == 0 or len(r) == 3:
        return trivial_circle(r)
    p = points[-1]
    circle = welzl(points[:-1], r)
    if is_inside(circle, p):
        return circle
    return welzl(points[:-1], r + [p])

def trivial_circle(points):
    if len(points) == 0:
        return (0, 0), 0
    elif len(points) == 1:
        return points[0], 0
    elif len(points) == 2:
        return circle_from_two_points(points[0], points[1])
    else:
        return circle_from_three_points(points[0], points[1], points[2])

def circle_from_two_points(a, b):
    center = ((a[0]+b[0])/2, (a[1]+b[1])/2)
    radius = np.linalg.norm(np.array(a)-np.array(b))/2
    return center, radius

def circle_from_three_points(a, b, c):
    A = 2*(b[0]-a[0])
    B = 2*(b[1]-a[1])
    C = b[0]**2 + b[1]**2 - a[0]**2 - a[1]**2
    D = 2*(c[0]-a[0])
    E = 2*(c[1]-a[1])
    F = c[0]**2 + c[1]**2 - a[0]**2 - a[1]**2
    det = A*E - B*D
    if det == 0:
        return circle_from_two_points(a, b)
    x = (E*C - B*F)/det
    y = (A*F - D*C)/det
    radius = np.linalg.norm(np.array(a)-np.array((x,y)))
    return (x,y), radius

def is_inside(circle, point):
    center, radius = circle
    return np.linalg.norm(np.array(point)-np.array(center)) <= radius + 1e-8

# 使用示例
points = np.array([[1,2], [3,4], [5,1], [2,5], [4,2]])
circle_center, circle_radius = welzl(points.tolist(), [])
print(f"最小包围圆：中心({circle_center[0]:.2f}, {circle_center[1]:.2f})，半径{circle_radius:.2f}")

二、最小包围椭圆实现 #

最小包围椭圆是能包含所有数据点的面积最小的椭圆，通常先提取点集的凸包（内部点不影响包围边界），再用现成工具拟合。

代码实现（Python + OpenCV） #

import numpy as np
import cv2
import matplotlib.pyplot as plt

# 自定义数据点
points = np.array([[1,2], [3,4], [5,1], [2,5], [4,2]], dtype=np.float32)

# 提取点集的凸包
hull = cv2.convexHull(points)

# 拟合最小包围椭圆
ellipse = cv2.fitEllipse(hull)
center, axes, angle = ellipse
major_axis, minor_axis = axes

# 输出结果
print(f"最小包围椭圆：中心({center[0]:.2f}, {center[1]:.2f})，长轴{major_axis:.2f}，短轴{minor_axis:.2f}，旋转角度{angle:.2f}°")

# 可视化验证（可选）
fig, ax = plt.subplots()
ax.scatter(points[:,0], points[:,1], color='red', label='数据点')
ellipse_patch = plt.matplotlib.patches.Ellipse(center, major_axis, minor_axis, angle=angle, fill=False, color='blue', label='包围椭圆')
ax.add_patch(ellipse_patch)
ax.set_aspect('equal')
plt.legend()
plt.show()

补充说明 #

• 若需要更精细的椭圆拟合（比如自定义目标函数），可以用scipy.optimize.minimize构建优化问题：以椭圆参数为变量，最小化椭圆面积，同时约束所有点在椭圆内部，但复杂度高于OpenCV的现成方法。
• 无论是圆还是椭圆，先提取凸包都能减少计算量，提升效率。

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