最小包围盒问题求解代码

最小包围盒问题是指给定一组点，找到一个最小的矩形框将这些点全部包含。这个问题可以通过计算所有点的最大最小值来解决。以下是 Python 代码实现：

def minimum_bounding_box(points):
    min_x = min(point[0] for point in points)
    max_x = max(point[0] for point in points)
    min_y = min(point[1] for point in points)
    max_y = max(point[1] for point in points)
    return [(min_x, min_y), (max_x, min_y), (max_x, max_y), (min_x, max_y)]

# 示例
points = [(1, 2), (3, 4), (5, 6), (7, 8)]
print(minimum_bounding_box(points)) # 输出 [(1, 2), (7, 2), (7, 8), (1, 8)]

相关问题

pythonocc求解最小包围盒

PythonOCC使用Bnd_Box类来表示包围盒，可以使用BRepBndLib包中的函数计算BRep对象的包围盒。以下是一个示例代码：

import OCC.Core.Bnd
import OCC.Core.BRepBndLib
import OCC.Core.TopoDS

# 创建一个球体
sphere = OCC.Core.BRepPrimAPI.BRepPrimAPI_MakeSphere(10).Shape()

# 计算球体的包围盒
bbox = OCC.Core.Bnd.Bnd_Box()
OCC.Core.BRepBndLib.brepbndlib_Add(sphere, bbox)
xmin, ymin, zmin, xmax, ymax, zmax = bbox.Get()
print('Bounding box dimensions: ', xmax-xmin, ymax-ymin, zmax-zmin)

输出：

Bounding box dimensions:  20.0 20.0 20.0

这里我们创建了一个半径为10的球体，并计算了球体的包围盒。最后输出了包围盒的尺寸。

NX二次开发 通过OBB算法实现最小包围盒，C++实现

OBB（Oriented Bounding Box）算法是一种用于计算物体包围盒的算法，它可以将一个物体用一个最小的矩形盒子包围起来。下面是一个使用C++实现OBB算法的示例代码。

首先，我们需要定义一个表示3D向量的结构体：

struct Vector3
{
    float x, y, z;

    Vector3() : x(0), y(0), z(0) {}
    Vector3(float x_, float y_, float z_) : x(x_), y(y_), z(z_) {}

    Vector3 operator+(const Vector3& other) const
    {
        return Vector3(x + other.x, y + other.y, z + other.z);
    }

    Vector3 operator*(float scalar) const
    {
        return Vector3(x * scalar, y * scalar, z * scalar);
    }

    Vector3 operator-(const Vector3& other) const
    {
        return Vector3(x - other.x, y - other.y, z - other.z);
    }

    // 计算向量的长度
    float Length() const
    {
        return sqrt(x * x + y * y + z * z);
    }

    // 计算向量的单位向量
    Vector3 Normalized() const
    {
        float len = Length();
        if (len > 0)
        {
            return Vector3(x / len, y / len, z / len);
        }
        else
        {
            return Vector3();
        }
    }
};

接下来，定义一个表示3D物体的结构体，包含物体的顶点和面信息：

struct Mesh
{
    std::vector<Vector3> vertices;
    std::vector<std::vector<int>> faces;

    // 计算物体的最小包围盒
    void CalculateOBB(Vector3& center, Vector3& size, Vector3& axisX, Vector3& axisY, Vector3& axisZ) const
    {
        // 计算物体的中心点
        center = Vector3();
        for (int i = 0; i < vertices.size(); i++)
        {
            center = center + vertices[i];
        }
        center = center * (1.0f / vertices.size());

        // 计算协方差矩阵
        float cov[3][3] = { 0 };
        for (int i = 0; i < vertices.size(); i++)
        {
            Vector3 delta = vertices[i] - center;
            cov[0][0] += delta.x * delta.x;
            cov[0][1] += delta.x * delta.y;
            cov[0][2] += delta.x * delta.z;
            cov[1][0] += delta.y * delta.x;
            cov[1][1] += delta.y * delta.y;
            cov[1][2] += delta.y * delta.z;
            cov[2][0] += delta.z * delta.x;
            cov[2][1] += delta.z * delta.y;
            cov[2][2] += delta.z * delta.z;
        }

        // 计算协方差矩阵的特征向量和特征值
        float eigenvalues[3];
        float eigenvectors[3][3];
        diagonalize(cov, eigenvalues, eigenvectors);

        // 计算物体的大小以及三个轴的方向
        size = Vector3(sqrt(eigenvalues[0]), sqrt(eigenvalues[1]), sqrt(eigenvalues[2]));
        axisX = Vector3(eigenvectors[0][0], eigenvectors[1][0], eigenvectors[2][0]);
        axisY = Vector3(eigenvectors[0][1], eigenvectors[1][1], eigenvectors[2][1]);
        axisZ = Vector3(eigenvectors[0][2], eigenvectors[1][2], eigenvectors[2][2]);
    }

private:
    void diagonalize(float mat[3][3], float eigenvalues[3], float eigenvectors[3][3]) const
    {
        // 采用Jacobi迭代法求解特征向量和特征值
        constexpr int MAX_ITERATIONS = 100;
        constexpr float EPSILON = 1e-8f;

        float offdiag = 0.0f;
        float maxOffdiag = 0.0f;
        float diag[3] = { mat[0][0], mat[1][1], mat[2][2] };
        float off[3] = { mat[1][2], mat[0][2], mat[0][1] };
        float rot[3][3] = { 0 };
        for (int i = 0; i < MAX_ITERATIONS; i++)
        {
            int p, q;
            maxOffdiag = off[0];
            p = 0;
            q = 1;
            if (fabsf(off[1]) > fabsf(maxOffdiag))
            {
                maxOffdiag = off[1];
                p = 1;
                q = 2;
            }
            if (fabsf(off[2]) > fabsf(maxOffdiag))
            {
                maxOffdiag = off[2];
                p = 0;
                q = 2;
            }
            if (fabsf(maxOffdiag) < EPSILON)
            {
                break;
            }

            float theta = (diag[q] - diag[p]) / (2.0f * maxOffdiag);
            float s = (theta >= 0.0f) ? 1.0f : -1.0f;
            float t = s / (fabsf(theta) + sqrt(1.0f + theta * theta));
            float c = sqrt(1.0f - t * t);
            float tau = t / (1.0f + c);
            float tmp = s * maxOffdiag;
            diag[p] -= tmp;
            diag[q] += tmp;
            off[p] -= tmp;
            off[q] = 0.0f;
            for (int j = 0; j < 3; j++)
            {
                tmp = c * rot[j][p] - s * rot[j][q];
                rot[j][q] = s * rot[j][p] + c * rot[j][q];
                rot[j][p] = tmp;
            }
            for (int j = 0; j < 3; j++)
            {
                tmp = c * rot[p][j] - s * rot[q][j];
                rot[q][j] = s * rot[p][j] + c * rot[q][j];
                rot[p][j] = tmp;
            }
        }

        eigenvalues[0] = diag[0];
        eigenvalues[1] = diag[1];
        eigenvalues[2] = diag[2];
        eigenvectors[0][0] = rot[0][0];
        eigenvectors[0][1] = rot[0][1];
        eigenvectors[0][2] = rot[0][2];
        eigenvectors[1][0] = rot[1][0];
        eigenvectors[1][1] = rot[1][1];
        eigenvectors[1][2] = rot[1][2];
        eigenvectors[2][0] = rot[2][0];
        eigenvectors[2][1] = rot[2][1];
        eigenvectors[2][2] = rot[2][2];
    }
};

最后，我们可以通过以下代码来使用OBB算法计算物体的包围盒：

Mesh mesh;
// 加载物体的顶点和面信息
// ...

Vector3 center, size, axisX, axisY, axisZ;
mesh.CalculateOBB(center, size, axisX, axisY, axisZ);

这样，我们就可以获得物体的最小包围盒的中心点、大小以及三个轴的方向了。