https://blog.csdn.net/qq_30974369/article/details/76405546

https://blog.csdn.net/qpswwww/article/details/44102039?spm=1001.2101.3001.6650.7&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7ERate-7-44102039-blog-96774375.pc_relevant_multi_platform_featuressortv2dupreplace&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EOPENSEARCH%7ERate-7-44102039-blog-96774375.pc_relevant_multi_platform_featuressortv2dupreplace&utm_relevant_index=8

给定一个凸多边形 P ， 面积最小的能装下 P （就外围而言）的矩形是怎样的呢？ 从技术上说， 给定一个方向， 能计算出 P 的端点并且构由此造出外接矩形。 但是我们需要测试每个情形来获得每个矩形来计算最小面积吗？ 谢天谢地， 我们不必那么干。

对于多边形 P 的一个外接矩形存在一条边与原多边形的边共线。

上述结论有力地限制了矩形的可能范围。 我们不仅不必去检测所有可能的方向， 而且只需要检测与多边形边数相等数量的矩形。

图示上述结论： 四条切线（红色）， 其中一条与多边形一条边重合， 确定了外接矩形（蓝色）

一个简单的算法是依次将每条边作为与矩形重合的边进行计算。 但是这种构造矩形的方法涉及到计算多边形每条边端点， 一个花费 O(n) 时间（因为有 n 条边）的计算。 整个算法将有二次时间复杂度。

一个更高效的算法已经发现。 利用旋转卡壳， 我们可以在常数时间内实时更新， 而不是重新计算端点。

实际上， 考虑一个凸多边形， 拥有两对和 x 和 y 方向上四个端点相切的切线。 四条线已经确定了一个多边形的外接矩形。 但是除非多边形有一条水平的或是垂直的边， 这个矩形的面积就不能算入最小面积中。
然而， 可以通过旋转线直到条件满足。 这个过程是下属算法的核心。 假设按照顺时针顺序输入一个凸多边形的n 个顶点。

• 计算全部四个多边形的端点， 称之为 xminP， xmaxP， yminP， ymaxP。

• 通过四个点构造 P 的四条切线。 他们确定了两个“卡壳”集合。

• 如果一条（或两条）线与一条边重合， 那么计算由四条线决定的矩形的面积， 并且保存为当前最小值。 否则将当前最小值定义为无穷大。

• 顺时针旋转线直到其中一条和多边形的一条边重合。

• 重复步骤4和步骤5， 直到线旋转过的角度大于90度。

• 输出外接矩形的最小面积。

因为两对的“卡壳”确定了一个外接矩形， 这个算法考虑到了所有可能算出最小面积的矩形。 进一步， 除了初始值外， 算法的主循环只需要执行顶点总数多次。 因此算法是线性时间复杂度的。

minAreaRect()函数计算并返回指定点集的最小区域边界斜矩形

RotatedRect minAreaRect(InputArray points)

• point：输入信息，可为包含点的容器vector或mat

• RotatedRect：返回一个轮廓的外接矩形，包覆输入信息的最小斜矩形，是一个Box2D结构rect：（最小外接矩形的中心（x，y），（宽度，高度），旋转角度）。
  

• 旋转角度θ是水平轴（x轴）逆时针旋转，与碰到的矩形的第一条边的夹角。并且这个边的边长是width，另一条边边长是height。也就是说，在这里，width与height不是按照长短来定义的。

• 在opencv中，坐标系原点在左上角，相对于x轴，逆时针旋转角度为负，顺时针旋转角度为正。所以，θ∈（-90度，0]。

求矩形顶点：
函数：

cvBoxPoints(CvBox2D box, CvPoint2D32f pt[4]) 

• box：输入矩形数据，minAreaRect返回的RotatedRect 类就是一个Box2D结构的矩形
• pt 返回的顶点数组

opencv源码：

void RotatedRect::points(Point2f pt[]) const
{
    double _angle = angle*CV_PI/180.;
    float b = (float)cos(_angle)*0.5f;
    float a = (float)sin(_angle)*0.5f;

    pt[0].x = center.x - a*size.height - b*size.width;
    pt[0].y = center.y + b*size.height - a*size.width;
    pt[1].x = center.x + a*size.height - b*size.width;
    pt[1].y = center.y - b*size.height - a*size.width;
    pt[2].x = 2*center.x - pt[0].x;
    pt[2].y = 2*center.y - pt[0].y;
    pt[3].x = 2*center.x - pt[1].x;
    pt[3].y = 2*center.y - pt[1].y;
}
CV_IMPL void cvBoxPoints( CvBox2D box, CvPoint2D32f pt[4] )
{
    if( !pt )
        CV_Error( CV_StsNullPtr, "NULL vertex array pointer" );
    cv::RotatedRect(box).points((cv::Point2f*)pt);
}

eg:

double rz=0;
std::vector<cv::Point2f>points;
for(unsigned int i=0;i<current_cluster->points.size();i++){
   cv::Point2f pt;
   pt.x = current_cluster->points[i].x;
   pt.y = current_cluster->points[i].y;
   points.push_back(pt);
}

std::vector<cv::Point2f> hull;
cv::convexHull(points,hull);

polygon_.header = in_ros_header;
for(size_t i=0; i< hull.size();i++){
    geometry_msgs::Point32 point;
    point.x = hull[i%hull.size()].x
    point.y = hull[i%hull.size()].y
    point.z = min_point.z;
    polygon_.polygon.points.push_back(point);
}

if(in_estimate_pose){
    cv::RotateRect box = minAreaRect(hull);
    rz = box.angle *3.14/100;
    //jsk_recognition_msgs::BoundingBox bounding_box_;
    bounding_box.pose.position.x = box.center.x;
    bounding_box.pose.position.y = box.center.y;
    bounding_box.dimension.x = box.size.width;
    bounding_box.dimension.y = box.size.height;   
}

//设置bounding box的方向
tf::Quaternion quat = tf::createQuaternionFromRPY(0.0,0.0,rz)
tf::quaternionTFToMsg(quat, bounding_box_.pose.oriention)

current_cluster->width = current_cluster->points.size();
current_cluster->height = 1;
current_cluster->is_dense = true;