C++ 创建最小包围盒子

最小包围盒子（bounding box）是一种能够包围物体或几何形状的盒子，通常用于计算机图形学、物理模拟、碰撞检测等领域。创建最小包围盒子的方法主要有以下几种：

1. 基于几何形状的包围盒子：对于一些简单的几何形状，如球体、立方体等，可以直接创建其对应的包围盒子。

2. 基于顶点的包围盒子：对于复杂的几何模型，可以计算其所有顶点的最小和最大值，从而得到一个包围盒子。

3. 基于包围盒子的包围盒子：对于一组物体或几何形状，可以先创建一个包围所有物体的大包围盒子，再在其中创建每个物体的小包围盒子。

4. 基于分治的包围盒子：将一个物体或几何形状分成多个小部分，对每个小部分分别创建包围盒子，再将这些小包围盒子合并成一个大包围盒子。

在实际应用中，根据需要选择不同的方法创建最小包围盒子，以提高计算效率和精度。

相关问题

基于c++ 最小包围球WeIzI算法

最小包围球（Minimum Enclosing Ball）是一种用于包含给定点集的最小球体的算法。WeIzI算法是一种基于递归的最小包围球算法，它的时间复杂度为 O(n)。

以下是基于C++的WeIzI算法实现：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>

using namespace std;

const double eps = 1e-12;

struct Point {
    double x, y, z;
};

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

Point get_circumcenter(const Point &a, const Point &b, const Point &c) {
    double x1 = a.x, y1 = a.y, z1 = a.z;
    double x2 = b.x, y2 = b.y, z2 = b.z;
    double x3 = c.x, y3 = c.y, z3 = c.z;
    double A = x2 - x1, B = y2 - y1, C = z2 - z1;
    double D = x3 - x1, E = y3 - y1, F = z3 - z1;
    double G = A * (x1 + x2) + B * (y1 + y2) + C * (z1 + z2);
    double H = D * (x1 + x3) + E * (y1 + y3) + F * (z1 + z3);
    double I = 2 * (A * (y3 - y2) - B * (x3 - x2));
    double J = 2 * (D * (y2 - y1) - E * (x2 - x1));
    double K = 2 * (B * F - C * E);
    double x = (H * K - G * J) / (I * K - J * J);
    double y = (G - I * x) / J;
    double z = -(A * x + B * y + G) / C;
    return {x, y, z};
}

double get_radius(const Point &a, const Point &b, const Point &c) {
    Point o = get_circumcenter(a, b, c);
    return dis(o, a);
}

void WeiZi(const vector<Point> &p, int n, Point &c, double &r) {
    if (n == 0) {
        c = {0, 0, 0};
        r = -1;
        return;
    }
    if (n == 1) {
        c = p[0];
        r = 0;
        return;
    }
    if (n == 2) {
        c = {(p[0].x + p[1].x) / 2, (p[0].y + p[1].y) / 2, (p[0].z + p[1].z) / 2};
        r = dis(c, p[0]);
        return;
    }
    random_device rd;
    mt19937 gen(rd());
    shuffle(p.begin(), p.end(), gen);
    c = {(p[0].x + p[1].x + p[2].x) / 3, (p[0].y + p[1].y + p[2].y) / 3, (p[0].z + p[1].z + p[2].z) / 3};
    r = dis(c, p[0]);
    for (int i = 1; i < n; i++) {
        if (dis(c, p[i]) - r > eps) {
            vector<Point> q;
            for (int j = 0; j < i; j++) {
                if (dis(c, p[j]) - r > eps) {
                    q.push_back(p[j]);
                }
            }
            WeiZi(q, q.size(), c, r);
            r = dis(c, p[i]);
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].x >> p[i].y >> p[i].z;
    }
    Point c;
    double r;
    WeiZi(p, n, c, r);
    cout << "Center: (" << c.x << ", " << c.y << ", " << c.z << ")" << endl;
    cout << "Radius: " << r << endl;
    return 0;
}

其中，`Point` 表示三维空间中的一个点，`dis` 函数计算两点之间的距离，`get_circumcenter` 函数计算三角形外心坐标，`get_radius` 函数计算三角形外接圆半径，`WeiZi` 函数是核心算法实现，它通过递归不断缩小包围球的半径和中心坐标。主函数中读入点集，调用 `WeiZi` 函数计算最小包围球的圆心和半径。

用opencv和C++实现点集的最小包围球

可以使用 Welzl 算法来实现点集的最小包围球。以下是使用 OpenCV 和 C++ 实现的示例代码：

#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>
#include <iostream>
#include <vector>
#include <random>

using namespace cv;
using namespace std;

// 计算两个点之间的距离
double dist(Point3d p1, Point3d p2) {
    return norm(p1 - p2);
}

// 判断点 p 是否在圆心为 center，半径为 radius 的圆内
bool insideCircle(Point3d p, Point3d center, double radius) {
    return dist(p, center) < radius + 1e-6;
}

// 返回最小包围球的半径和圆心
void minSphere(vector<Point3d>& points, double& radius, Point3d& center) {
    int n = points.size();
    if (n == 0) {
        radius = 0;
        center = Point3d(0, 0, 0);
        return;
    } else if (n == 1) {
        radius = 0;
        center = points[0];
        return;
    } else if (n == 2) {
        radius = dist(points[0], points[1]) / 2;
        center = (points[0] + points[1]) / 2;
        return;
    }

    // 随机打乱顺序
    random_shuffle(points.begin(), points.end());

    // 递归求解
    vector<Point3d> rest(points.begin() + 1, points.end());
    minSphere(rest, radius, center);
    if (insideCircle(points[0], center, radius)) return;

    rest.push_back(points[0]);
    radius = 0;
    center = points[0];
    for (int i = 0; i < rest.size(); i++) {
        if (!insideCircle(rest[i], center, radius)) {
            vector<Point3d> sub(rest.begin(), rest.begin() + i);
            minSphere(sub, radius, center);
            if (insideCircle(rest[i], center, radius)) return;
            rest.erase(sub.begin(), sub.end());
            rest.push_back(rest[i]);
        }
    }
}

int main() {
    // 生成随机点集
    vector<Point3d> points;
    random_device rd;
    mt19937 gen(rd());
    uniform_real_distribution<double> dis(-1.0, 1.0);
    for (int i = 0; i < 10; i++) {
        double x = dis(gen);
        double y = dis(gen);
        double z = dis(gen);
        points.push_back(Point3d(x, y, z));
    }

    // 求解最小包围球
    double radius;
    Point3d center;
    minSphere(points, radius, center);

    // 绘制点集和最小包围球
    Mat img(600, 600, CV_8UC3, Scalar(255, 255, 255));
    for (auto p : points) {
        Point2d p2d(p.x * 200 + 300, p.y * 200 + 300);
        circle(img, p2d, 2, Scalar(0, 0, 255), -1);
    }
    Point2d center2d(center.x * 200 + 300, center.y * 200 + 300);
    circle(img, center2d, radius * 200, Scalar(0, 255, 0), 2);
    imshow("Minimum Bounding Sphere", img);
    waitKey();

    return 0;
}

这里我们使用了 `Point3d` 类型来表示三维点，`minSphere` 函数实现了递归求解最小包围球的过程，`insideCircle` 函数用于判断一个点是否在圆内。最后，我们使用 OpenCV 绘制了点集和最小包围球。