C++ 中的最小包围圆 (MEC)

2025 年 5 月 17 日 | 阅读 7 分钟

计算几何学中最具挑战性的问题之一是最小外接圆（Minimum Enclosing Circle, MEC），也称为最小覆盖圆。最小外接圆的定义是能够完全包围二维平面上给定点集的最小圆。此问题的目标是在保持圆周内或圆周上的所有点的前提下，减小圆的半径。

问题定义

目标是找到一个最小的圆，该圆能够包围二维平面上给定点集中的所有点。该圆应满足以下条件：

所有点必须位于圆的内部或圆周上。
圆的半径应尽可能小。

最小外接圆的性质

最小外接圆具有几个重要的性质，有助于设计高效的算法来解决它。

唯一性

对于给定的点集，最小外接圆是唯一的。只能存在一个最小的圆来包围所有点。

边界点

最小外接圆最多可以由三个点定义。边界点位于圆的周长上。
如果只有两个边界点，则圆心是连接这两个点的线段的中点，半径是它们之间距离的一半。
只有三个边界点的情况下，圆可以由位于其周长上的这三个点唯一确定。

特殊情况

对于单个点：半径为零，圆心与该点重合。
两个点：圆心是连接两点的线段的中点，半径是它们之间距离的一半。

计算复杂性

暴力方法：检查所有点组合在计算上非常昂贵。在实际场景中，需要像 Welzl 算法这样的高效算法。

最小外接圆的算法

已经开发了多种算法来高效地解决 MEC 问题。其中包括：

1. 朴素方法

朴素方法包括检查所有可能的点子集来形成圆的边界，然后检查它是否包围了所有其他点。工作原理如下：

生成由两点或三点组合形成的所有可能的圆。
检查圆是否包围了所有点。
选择满足要求的半径最小的圆。

时间复杂度：此方法的时??间复杂度为 O(n³)，因为我们需要测试每对或每三个点，并验证每个圆。

2. 优化算法：Welzl 算法

Welzl 算法是解决最小外接圆问题的优化、概率性递归版本。它可以通过一组位于边界上的点迭代地形成 MEC。这个子集称为支撑集。该算法的期望时间复杂度为 O(n)。因此，对于大量数据集，它消耗的时间非常少。

关键步骤

随机打乱点顺序可以提供概率保证。
从一个空圆开始。
逐个添加点，并在点位于圆外时更新圆。
如果一个点位于圆外，则通过包含该新点并更改边界来更新圆。

最小外接圆的应用

最小外接圆在各种领域都有广泛的应用。其中一些如下：

机器人技术：在机器人领域，MEC 是一个关键概念，可用于避免碰撞和自我碰撞，这有助于机器人设定安全移动越过或绕过障碍物的边界。
图形和动画：在计算机图形学中，最小外接圆在包围体积层次结构中的应用有助于快速渲染和命中测试，从而加快碰撞检测过程。
地理空间分析：MEC 在 GIS 中用于查找包围一组地理数据点（例如建筑物或地标的位置）的最小圆。
数据聚类：MEC 用于数据聚类，以识别集群的空间分布，并确保找到集群的最小外接边界。
材料设计和包装：涉及包装和布局设计的行业使用 MEC 来计算圆形物体的最佳包装和布局。
游戏开发：在游戏开发中，MEC 主要用于为角色定义圆形命中框，以确保游戏中的正确碰撞检测。

Welzl 算法的 C++ 实现

现在，让我们看看 Welzl 算法的详细 C++ 实现。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <random>  // Include for random_shuffle replacement

using namespace std;

// Point structure
struct Point {
    double x, y;
};

struct Circle {
    Point center;
    double radius;

    Circle(Point c, double r) : center(c), radius(r) {}
    bool contains(const Point& p) const {
        return sqrt((center.x - p.x) * (center.x - p.x) + (center.y - p.y) * (center.y - p.y)) <= radius + 1e-9;
    }
};

double getDistance(const Point& a, const Point& b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

Circle circleFromTwoPoints(const Point& a, const Point& b) {
    Point center = {(a.x + b.x) / 2.0, (a.y + b.y) / 2.0};
    double radius = getDistance(a, b) / 2.0;
    return Circle(center, radius);
}

Circle circleFromThreePoints(const Point& a, const Point& b, const Point& c) {
    double d = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
    double centerX = ((a.x * a.x + a.y * a.y) * (b.y - c.y) +
                      (b.x * b.x + b.y * b.y) * (c.y - a.y) +
                      (c.x * c.x + c.y * c.y) * (a.y - b.y)) / d;
    double centerY = ((a.x * a.x + a.y * a.y) * (c.x - b.x) +
                      (b.x * b.x + b.y * b.y) * (a.x - c.x) +
                      (c.x * c.x + c.y * c.y) * (b.x - a.x)) / d;
    Point center = {centerX, centerY};
    double radius = getDistance(center, a);
    return Circle(center, radius);
}

Circle welzlRecursive(vector<Point>& points, vector<Point> boundary, int n) {
    if (n == 0 || boundary.size() == 3) {
        if (boundary.empty()) {
            return Circle({0, 0}, 0);
        } else if (boundary.size() == 1) {
            return Circle(boundary[0], 0);
        } else if (boundary.size() == 2) {
            return circleFromTwoPoints(boundary[0], boundary[1]);
        } else {
            return circleFromThreePoints(boundary[0], boundary[1], boundary[2]);
        }
    }
    Point p = points[n - 1];
    Circle currentCircle = welzlRecursive(points, boundary, n - 1);
    if (currentCircle.contains(p)) {
        return currentCircle;
    }

    // Add the point to the boundary and recurse
    boundary.push_back(p);
    return welzlRecursive(points, boundary, n - 1);
}

// Main function for Welzl's Algorithm
Circle findMinimumEnclosingCircle(vector<Point>& points) {
    random_device rd;  // Initialize random_device
    mt19937 rng(rd());   // Initialize Mersenne Twister RNG
    shuffle(points.begin(), points.end(), rng);  // Replace random_shuffle with shuffle
    return welzlRecursive(points, {}, points.size());
}

int main() {
    srand(time(0));

    // Input points
    vector<Point> points = {{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0.5, 0.5}};

    // Compute Minimum Enclosing Circle
    Circle mec = findMinimumEnclosingCircle(points);

    // Output result
    cout << "Center: (" << mec.center.x << ", " << mec.center.y << ")\n";
    cout << "Radius: " << mec.radius << "\n";

    return 0;
}

输出

代码解释

数据结构:
- Point：一个结构，表示二维空间中的一个点，具有 x 和 y 坐标。
- Circle：一个结构，表示一个圆，具有一个中心（一个 Point）和一个半径。它还包含一个方法来检查一个点是否位于圆的内部或边界上。
辅助函数
- Distance：计算两点之间的欧几里得距离。
- circleFromTwoPoints 和 circleFromThreePoints：这两个函数分别计算由两点和三点确定的圆。
Welzl 算法
- welzlHelper：Welzl 算法通过逐个处理点来执行最小外接圆的整个计算，并将其传递给其辅助递归函数 welzlHelper。如果一个点超出特定圆的范围，它将使用圆的边界重新计算。
- minimumEnclosingCircle：它通过打乱给定点来调用 MEC，然后调用 welzlHelper，welzlHelper 会将整个计算向前推进 MEC。

高级优化

为了使 MEC 算法对实际数据更加健壮，可以包括以下优化和考虑：

数值稳定性：在实际应用中，数值稳定性很重要，尤其是在处理非常小或非常大的坐标时。在这种情况下，浮点计算的精度可以避免错误。
并行处理：并行处理可应用于大型数据集。可以将数据集划分为子数据集，并在子数据集上并行处理，以加速计算。
与其他几何图元的集成：将 MEC 与其他几何技术（如凸包或 Voronoi 图）相结合，可以实现更高级的几何处理应用。

结论

总而言之，最小外接圆问题在计算几何学中非常重要，并且已经为机器人技术、GIS、游戏开发以及许多其他领域的许多实际挑战提供了解决方案。Welzl 算法等算法可以在线性时间内高效地解决此问题，使其能够应用于大规模数据集。除了其广泛的应用外，MEC 算法的进一步优化使其成为理论和应用计算几何学中不可或缺的工具。

下一主题C++ 中的 Sophie Germain 素数

C++ 中的最小包围圆 (MEC)

问题定义

最小外接圆的性质

唯一性

边界点