利用minAreaRect求轮廓最小外接矩形

利用minAreaRect求轮廓最小外接矩形

1、minAreaRect函数

Finds a rotated rectangle of the minimum area enclosing the input 2D point set.

（1）定义：C++: RotatedRect minAreaRect(InputArray points)

（2）函数实现：

cv::RotatedRect cv::minAreaRect( InputArray _points ){    Mat points = _points.getMat();    CV_Assert(points.checkVector(2) >= 0 && (points.depth() == CV_32F || points.depth() == CV_32S));    CvMat _cpoints = points;    return cvMinAreaRect2(&_cpoints, 0);}
CV_IMPL  CvBox2DcvMinAreaRect2( const CvArr* array, CvMemStorage* storage ){    cv::Ptr<CvMemStorage> temp_storage;    CvBox2D box;    cv::AutoBuffer<CvPoint2D32f> _points;    CvPoint2D32f* points;    memset(&box, 0, sizeof(box));    int i, n;    CvSeqReader reader;    CvContour contour_header;    CvSeqBlock block;    CvSeq* ptseq = (CvSeq*)array;    CvPoint2D32f out[3];    if( CV_IS_SEQ(ptseq) )    {        if( !CV_IS_SEQ_POINT_SET(ptseq) &&            (CV_SEQ_KIND(ptseq) != CV_SEQ_KIND_CURVE ||            CV_SEQ_ELTYPE(ptseq) != CV_SEQ_ELTYPE_PPOINT ))            CV_Error( CV_StsUnsupportedFormat,                "Input sequence must consist of 2d points or pointers to 2d points" );        if( !storage )            storage = ptseq->storage;    }    else    {        ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );    }    if( storage )    {        temp_storage = cvCreateChildMemStorage( storage );    }    else    {        temp_storage = cvCreateMemStorage(1 << 10);    }    ptseq = cvConvexHull2( ptseq, temp_storage, CV_CLOCKWISE, 1 );    n = ptseq->total;    _points.allocate(n);    points = _points;    cvStartReadSeq( ptseq, &reader );    if( CV_SEQ_ELTYPE( ptseq ) == CV_32SC2 )    {        for( i = 0; i < n; i++ )        {            CvPoint pt;            CV_READ_SEQ_ELEM( pt, reader );            points[i].x = (float)pt.x;            points[i].y = (float)pt.y;        }    }    else    {        for( i = 0; i < n; i++ )        {            CV_READ_SEQ_ELEM( points[i], reader );        }    }    if( n > 2 )    {        icvRotatingCalipers( points, n, CV_CALIPERS_MINAREARECT, (float*)out );        box.center.x = out[0].x + (out[1].x + out[2].x)*0.5f;        box.center.y = out[0].y + (out[1].y + out[2].y)*0.5f;        box.size.width = (float)sqrt((double)out[1].x*out[1].x + (double)out[1].y*out[1].y);        box.size.height = (float)sqrt((double)out[2].x*out[2].x + (double)out[2].y*out[2].y);        box.angle = (float)atan2( (double)out[1].y, (double)out[1].x );    }    else if( n == 2 )    {        box.center.x = (points[0].x + points[1].x)*0.5f;        box.center.y = (points[0].y + points[1].y)*0.5f;        double dx = points[1].x - points[0].x;        double dy = points[1].y - points[0].y;        box.size.width = (float)sqrt(dx*dx + dy*dy);        box.size.height = 0;        box.angle = (float)atan2( dy, dx );    }    else    {        if( n == 1 )            box.center = points[0];    }    box.angle = (float)(box.angle*180/CV_PI);    return box;}
（3）结构体定义：
typedef struct CvBox2D{    CvPoint2D32f center;  /* Center of the box.----盒子的中心        */    CvSize2D32f  size;  /* Box width and length.----盒子的长和宽     */    float angle;       /* Angle between the horizontal axis and the first side (i.e. length) in degrees--水平轴与第一个边的夹角，用弧度表示*/}CvBox2D;
2、convexHull函数（凸包）
Finds the convex hull of a point set.
（1）定义：C++: void convexHull(InputArray points, OutputArray hull, bool clockwise=false, bool returnPoints=true )C: CvSeq* cvConvexHull2(const CvArr* input, void* hull_storage=NULL, int orientation=CV_CLOCKWISE, int return_points=0 )（2）convexHull源码实现：
void cv::convexHull( InputArray _points, OutputArray _hull, bool clockwise, bool returnPoints ){    Mat points = _points.getMat();    int nelems = points.checkVector(2), depth = points.depth();    CV_Assert(nelems >= 0 && (depth == CV_32F || depth == CV_32S));    if( nelems == 0 )    {        _hull.release();        return;    }    returnPoints = !_hull.fixedType() ? returnPoints : _hull.type() != CV_32S;    Mat hull(nelems, 1, returnPoints ? CV_MAKETYPE(depth, 2) : CV_32S);    CvMat _cpoints = points, _chull = hull;    cvConvexHull2(&_cpoints, &_chull, clockwise ? CV_CLOCKWISE : CV_COUNTER_CLOCKWISE, returnPoints);    _hull.create(_chull.rows, 1, hull.type(), -1, true);    Mat dhull = _hull.getMat(), shull(dhull.size(), dhull.type(), hull.data);    shull.copyTo(dhull);}
（3）cvConvexHull2源码实现
CV_IMPL CvSeq*cvConvexHull2( const CvArr* array, void* hull_storage,               int orientation, int return_points ){    union { CvContour* c; CvSeq* s; } hull;    cv::AutoBuffer<CvPoint*> _pointer;    CvPoint** pointer;    CvPoint2D32f** pointerf = 0;    cv::AutoBuffer<int> _stack;    int* stack;    hull.s = 0;    CvMat* mat = 0;    CvSeqReader reader;    CvSeqWriter writer;    CvContour contour_header;    union { CvContour c; CvSeq s; } hull_header;    CvSeqBlock block, hullblock;    CvSeq* ptseq = 0;    CvSeq* hullseq = 0;    int is_float;    int* t_stack;    int t_count;    int i, miny_ind = 0, maxy_ind = 0, total;    int hulltype;    int stop_idx;    sklansky_func sklansky;    if( CV_IS_SEQ( array ))    {        ptseq = (CvSeq*)array;        if( !CV_IS_SEQ_POINT_SET( ptseq ))            CV_Error( CV_StsBadArg, "Unsupported sequence type" );        if( hull_storage == 0 )            hull_storage = ptseq->storage;    }    else    {        ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );    }    if( CV_IS_STORAGE( hull_storage ))    {        if( return_points )        {            hullseq = cvCreateSeq(                CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE(ptseq)|                CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,                sizeof(CvContour), sizeof(CvPoint),(CvMemStorage*)hull_storage );        }        else        {            hullseq = cvCreateSeq(                CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_PPOINT|                CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,                sizeof(CvContour), sizeof(CvPoint*), (CvMemStorage*)hull_storage );        }    }    else    {        if( !CV_IS_MAT( hull_storage ))            CV_Error(CV_StsBadArg, "Destination must be valid memory storage or matrix");        mat = (CvMat*)hull_storage;        if( (mat->cols != 1 && mat->rows != 1) || !CV_IS_MAT_CONT(mat->type))            CV_Error( CV_StsBadArg,            "The hull matrix should be continuous and have a single row or a single column" );        if( mat->cols + mat->rows - 1 < ptseq->total )            CV_Error( CV_StsBadSize, "The hull matrix size might be not enough to fit the hull" );        if( CV_MAT_TYPE(mat->type) != CV_SEQ_ELTYPE(ptseq) &&            CV_MAT_TYPE(mat->type) != CV_32SC1 )            CV_Error( CV_StsUnsupportedFormat,            "The hull matrix must have the same type as input or 32sC1 (integers)" );        hullseq = cvMakeSeqHeaderForArray(            CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,            sizeof(contour_header), CV_ELEM_SIZE(mat->type), mat->data.ptr,            mat->cols + mat->rows - 1, &hull_header.s, &hullblock );        cvClearSeq( hullseq );    }    total = ptseq->total;    if( total == 0 )    {        if( mat )            CV_Error( CV_StsBadSize,            "Point sequence can not be empty if the output is matrix" );        return hull.s;    }    cvStartAppendToSeq( hullseq, &writer );    is_float = CV_SEQ_ELTYPE(ptseq) == CV_32FC2;    hulltype = CV_SEQ_ELTYPE(hullseq);    sklansky = !is_float ? (sklansky_func)icvSklansky_32s :                           (sklansky_func)icvSklansky_32f;    _pointer.allocate( ptseq->total );    _stack.allocate( ptseq->total + 2);    pointer = _pointer;    pointerf = (CvPoint2D32f**)pointer;    stack = _stack;    cvStartReadSeq( ptseq, &reader );    for( i = 0; i < total; i++ )    {        pointer[i] = (CvPoint*)reader.ptr;        CV_NEXT_SEQ_ELEM( ptseq->elem_size, reader );    }    // sort the point set by x-coordinate, find min and max y    if( !is_float )    {        icvSortPointsByPointers_32s( pointer, total, 0 );        for( i = 1; i < total; i++ )        {            int y = pointer[i]->y;            if( pointer[miny_ind]->y > y )                miny_ind = i;            if( pointer[maxy_ind]->y < y )                maxy_ind = i;        }    }    else    {        icvSortPointsByPointers_32f( pointerf, total, 0 );        for( i = 1; i < total; i++ )        {            float y = pointerf[i]->y;            if( pointerf[miny_ind]->y > y )                miny_ind = i;            if( pointerf[maxy_ind]->y < y )                maxy_ind = i;        }    }    if( pointer[0]->x == pointer[total-1]->x &&        pointer[0]->y == pointer[total-1]->y )    {        if( hulltype == CV_SEQ_ELTYPE_PPOINT )        {            CV_WRITE_SEQ_ELEM( pointer[0], writer );        }        else if( hulltype == CV_SEQ_ELTYPE_INDEX )        {            int index = 0;            CV_WRITE_SEQ_ELEM( index, writer );        }        else        {            CvPoint pt = pointer[0][0];            CV_WRITE_SEQ_ELEM( pt, writer );        }        goto finish_hull;    }    /*upper half */    {        int *tl_stack = stack;        int tl_count = sklansky( pointer, 0, maxy_ind, tl_stack, -1, 1 );        int *tr_stack = tl_stack + tl_count;        int tr_count = sklansky( pointer, ptseq->total - 1, maxy_ind, tr_stack, -1, -1 );        /* gather upper part of convex hull to output */        if( orientation == CV_COUNTER_CLOCKWISE )        {            CV_SWAP( tl_stack, tr_stack, t_stack );            CV_SWAP( tl_count, tr_count, t_count );        }        if( hulltype == CV_SEQ_ELTYPE_PPOINT )        {            for( i = 0; i < tl_count - 1; i++ )                CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]], writer );            for( i = tr_count - 1; i > 0; i-- )                CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]], writer );        }        else if( hulltype == CV_SEQ_ELTYPE_INDEX )        {            icvCalcAndWritePtIndices( pointer, tl_stack, 0, tl_count-1, ptseq, &writer );            icvCalcAndWritePtIndices( pointer, tr_stack, tr_count-1, 0, ptseq, &writer );        }        else        {            for( i = 0; i < tl_count - 1; i++ )                CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]][0], writer );            for( i = tr_count - 1; i > 0; i-- )                CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]][0], writer );        }        stop_idx = tr_count > 2 ? tr_stack[1] : tl_count > 2 ? tl_stack[tl_count - 2] : -1;    }    /* lower half */    {        int *bl_stack = stack;        int bl_count = sklansky( pointer, 0, miny_ind, bl_stack, 1, -1 );        int *br_stack = stack + bl_count;        int br_count = sklansky( pointer, ptseq->total - 1, miny_ind, br_stack, 1, 1 );        if( orientation != CV_COUNTER_CLOCKWISE )        {            CV_SWAP( bl_stack, br_stack, t_stack );            CV_SWAP( bl_count, br_count, t_count );        }        if( stop_idx >= 0 )        {            int check_idx = bl_count > 2 ? bl_stack[1] :                            bl_count + br_count > 2 ? br_stack[2-bl_count] : -1;            if( check_idx == stop_idx || (check_idx >= 0 &&                pointer[check_idx]->x == pointer[stop_idx]->x &&                pointer[check_idx]->y == pointer[stop_idx]->y) )            {                /* if all the points lie on the same line, then                   the bottom part of the convex hull is the mirrored top part                   (except the exteme points).*/                bl_count = MIN( bl_count, 2 );                br_count = MIN( br_count, 2 );            }        }        if( hulltype == CV_SEQ_ELTYPE_PPOINT )        {            for( i = 0; i < bl_count - 1; i++ )                CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]], writer );            for( i = br_count - 1; i > 0; i-- )                CV_WRITE_SEQ_ELEM( pointer[br_stack[i]], writer );        }        else if( hulltype == CV_SEQ_ELTYPE_INDEX )        {            icvCalcAndWritePtIndices( pointer, bl_stack, 0, bl_count-1, ptseq, &writer );            icvCalcAndWritePtIndices( pointer, br_stack, br_count-1, 0, ptseq, &writer );        }        else        {            for( i = 0; i < bl_count - 1; i++ )                CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]][0], writer );            for( i = br_count - 1; i > 0; i-- )                CV_WRITE_SEQ_ELEM( pointer[br_stack[i]][0], writer );        }    }finish_hull:    cvEndWriteSeq( &writer );    if( mat )    {        if( mat->rows > mat->cols )            mat->rows = hullseq->total;        else            mat->cols = hullseq->total;    }    else    {        hull.s = hullseq;        hull.c->rect = cvBoundingRect( ptseq,            ptseq->header_size < (int)sizeof(CvContour) ||            &ptseq->flags == &contour_header.flags );        /*if( ptseq != (CvSeq*)&contour_header )            hullseq->v_PRev = ptseq;*/    }    return hull.s;}