037-几何-最小覆盖圆

1. YAML 元数据 已设置 tags: [KACTL, 几何, 核心实体]。

2. 核心概述 以随机增量方式在线构造包含所有点的最小覆盖圆（Minimum Enclosing Circle, MEC），返回圆心与半径，期望线性时间。

3. 原文引述

Description: Computes the minimum circle that encloses a set of points. Time: expected O(n)

4. 展开阐述

• 定义与背景

  • 最小覆盖圆：在平面点集上找到面积最小（等价于半径最小）的圆，使其覆盖所有输入点。
  • 几何性质：最优圆由 2 个或 3 个“极端点”决定：
    • 若由 2 点决定，则这两点是直径的两端点，圆心为其中点；
    • 若由 3 点决定，则三点位于圆周上且圆心为外接圆圆心（ccCenter）。
  • 典型场景：几何外形粗略拟合、包围体初始化（碰撞/可视化）、与028-几何-凸包直径的最远点对互为上下界参考。

• 接口/数据结构（据实现约定）

  • 函数签名：pair<P, double> mec(vector

    ps)

    • P = Point；
    • 返回：{圆心 c, 半径 r}，r 为 double。
  • 随机化：在算法开始对点序列执行随机打乱，以保证期望线性复杂度与数值稳定性。

• 核心流程/要点（Welzl 随机增量）

  1. 初始化：随机打乱点集，令当前圆 C 的圆心为第一个点，半径 r=0。
  2. 外点修正（一层）：
     • 依次处理每个点 i，若 i 在 C 内（含边界，使用 EPS 判定）则跳过；
     • 否则将 C 设为“以 i 为圆心、半径为 0”的圆。
  3. 外点修正（二层）：
     • 对当前 i，枚举此前所有点 j；若 j 在 C 外：
       • 将 C 设为以 i 与 j 的中点为圆心、|ij|/2 为半径的“直径圆”。
  4. 外点修正（三层）：
     • 对同一 i，再枚举此前点 k；若 k 仍在 C 外：
       • 计算三点 i,j,k 的外接圆圆心 c = ccCenter(i, j, k)；
       • 更新 C：圆心为 c，半径为 |c−i|（或等价 |c−j|/|c−k|）。
  5. 终止：扫描结束得到 MEC；随机化保证期望 O(n) 次外点修正，三重循环仅在必要时触发。

• 数值阈值与稳健性

  • EPS：实现中常取 EPS = 1 + 1e−8 或使用固定容差比较，以吸收舍入误差。
  • 共线/近退化：
    • 三点几乎共线时，外接圆半径趋于由“直径对”决定；应以叉积绝对值与 EPS 结合判断；
    • 对非常小的三角形，求圆心时建议使用 long double 与稳定公式以降低误差。
  • 精度选择：
    • 坐标/半径建议使用 double/long double；若输入坐标绝对值较大，优先 long double。
  • 判“在圆内”：以 |p−c| ≤ r + eps 作为包含条件，避免误删外点修正机会。

• 复杂度与边界条件

  • 复杂度：随机化后期望 O(n)；最坏情况下（构造对抗顺序）可能退化到 O(n^3)，但随机打乱可避免。
  • 边界：
    • n=0：返回半径 0 的“空圆”（按实现约定处理）；
    • n=1：圆心为该点，半径 0；
    • 重合点：不影响最优性，外点修正时按包含判断正常处理。

• 变体/扩展

  • 返回语义扩展：除 {c, r} 外，可返回“支撑点集”（2 或 3 个在圆上的点）以便下游验证或可视化。
  • 三维推广：最小包围球（支持函数/随机增量）思想一致，但实现复杂度与数值稳定性要求更高。
  • 与凸包协同：MEC 的支撑点一定在凸包上；可先求 025-几何-凸包 再在其顶点上做 MEC，平均常数更小。

• 正确性要点与直觉性证明

  • 极端点原理：若最优圆由两点决策，则这两点必须作为直径两端（否则可收缩）；由三点决策时，三点共圆且圆内空。
  • 随机增量不变式：当前圆始终覆盖已处理点集；当出现外点时，新的最小圆必须“贴住”该外点并至少再贴住另一个（或两个）此前点，从而在二/三层修正中被捕获。

• 与相邻技术的对比与取舍

  • 与 028-几何-凸包直径：凸包直径给出“最远点对”，提供 MEC 半径的下界；MEC 需要可能的第三点来“撑开”圆心位置。
  • 与网格/采样近似：当允许近似时，可用采样或迭代膨胀获得近似 MEC；但精确问题以 Welzl 最佳。

5. 关联节点

• 023-几何-外接圆
• 039-几何-点
• 025-几何-凸包