cvconvhull.cpp

opencv库在TI DM6437上的移植,目前包括两个库cv.lib和cxcore.lib的工程

        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 )
        {
            CV_CALL( icvCalcAndWritePtIndices( pointer, bl_stack,
                                               0, bl_count-1, ptseq, &writer ));
            CV_CALL( 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:
    CV_CALL( 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;*/
    }

    __END__;

    cvFree( &pointer );
    cvFree( &stack );

    return hull.s;
}


/* contour must be a simple polygon */
/* it must have more than 3 points  */
CV_IMPL CvSeq*
cvConvexityDefects( const CvArr* array,
                    const CvArr* hullarray,
                    CvMemStorage* storage )
{
    CvSeq* defects = 0;
    
    CV_FUNCNAME( "cvConvexityDefects" );

    __BEGIN__;

    int i, index;
    CvPoint* hull_cur;

    /* is orientation of hull different from contour one */
    int rev_orientation;

    CvContour contour_header;
    union { CvContour c; CvSeq s; } hull_header;
    CvSeqBlock block, hullblock;
    CvSeq *ptseq = (CvSeq*)array, *hull = (CvSeq*)hullarray;

    CvSeqReader hull_reader;
    CvSeqReader ptseq_reader;
    CvSeqWriter writer;
    int is_index;

    if( CV_IS_SEQ( ptseq ))
    {
        if( !CV_IS_SEQ_POINT_SET( ptseq ))
            CV_ERROR( CV_StsUnsupportedFormat,
                "Input sequence is not a sequence of points" );
        if( !storage )
            storage = ptseq->storage;
    }
    else
    {
        CV_CALL( ptseq = cvPointSeqFromMat(
            CV_SEQ_KIND_GENERIC, array, &contour_header, &block ));
    }

    if( CV_SEQ_ELTYPE( ptseq ) != CV_32SC2 )
        CV_ERROR( CV_StsUnsupportedFormat,
            "Floating-point coordinates are not supported here" );

    if( CV_IS_SEQ( hull ))
    {
        int hulltype = CV_SEQ_ELTYPE( hull );
        if( hulltype != CV_SEQ_ELTYPE_PPOINT && hulltype != CV_SEQ_ELTYPE_INDEX )
            CV_ERROR( CV_StsUnsupportedFormat,
                "Convex hull must represented as a sequence "
                "of indices or sequence of pointers" );
        if( !storage )
            storage = hull->storage;
    }
    else
    {
        CvMat* mat = (CvMat*)hull;
        
        if( !CV_IS_MAT( hull ))
            CV_ERROR(CV_StsBadArg, "Convex hull is neither sequence nor matrix");

        if( mat->cols != 1 && mat->rows != 1 ||
            !CV_IS_MAT_CONT(mat->type) || CV_MAT_TYPE(mat->type) != CV_32SC1 )
            CV_ERROR( CV_StsBadArg,
            "The matrix should be 1-dimensional and continuous array of int's" );

        if( mat->cols + mat->rows - 1 > ptseq->total )
            CV_ERROR( CV_StsBadSize, "Convex hull is larger than the point sequence" );
        
        CV_CALL( hull = cvMakeSeqHeaderForArray(
            CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
            sizeof(CvContour), CV_ELEM_SIZE(mat->type), mat->data.ptr,
            mat->cols + mat->rows - 1, &hull_header.s, &hullblock ));
    }

    is_index = CV_SEQ_ELTYPE(hull) == CV_SEQ_ELTYPE_INDEX;

    if( !storage )
        CV_ERROR( CV_StsNullPtr, "NULL storage pointer" );

    CV_CALL( defects = cvCreateSeq( CV_SEQ_KIND_GENERIC, sizeof(CvSeq),
                                    sizeof(CvConvexityDefect), storage ));

    if( ptseq->total < 4 || hull->total < 3)
    {
        //CV_ERROR( CV_StsBadSize,
        //    "point seq size must be >= 4, convex hull size must be >= 3" );
        EXIT;
    }

    /* recognize co-orientation of ptseq and its hull */
    {
        int sign = 0;
        int index1, index2, index3;

        if( !is_index )
        {
            CvPoint* pos = *CV_SEQ_ELEM( hull, CvPoint*, 0 );
            CV_CALL( index1 = cvSeqElemIdx( ptseq, pos ));

            pos = *CV_SEQ_ELEM( hull, CvPoint*, 1 );
            CV_CALL( index2 = cvSeqElemIdx( ptseq, pos ));

            pos = *CV_SEQ_ELEM( hull, CvPoint*, 2 );
            CV_CALL( index3 = cvSeqElemIdx( ptseq, pos ));
        }
        else
        {
            index1 = *CV_SEQ_ELEM( hull, int, 0 );
            index2 = *CV_SEQ_ELEM( hull, int, 1 );
            index3 = *CV_SEQ_ELEM( hull, int, 2 );
        }

        sign += (index2 > index1) ? 1 : 0;
        sign += (index3 > index2) ? 1 : 0;
        sign += (index1 > index3) ? 1 : 0;

        rev_orientation = (sign == 2) ? 0 : 1;
    }

    cvStartReadSeq( ptseq, &ptseq_reader, 0 );
    cvStartReadSeq( hull, &hull_reader, rev_orientation );

    if( !is_index )
    {
        hull_cur = *(CvPoint**)hull_reader.prev_elem;
        index = cvSeqElemIdx( ptseq, (char*)hull_cur, 0 );
    }
    else
    {
        index = *(int*)hull_reader.prev_elem;
        hull_cur = CV_GET_SEQ_ELEM( CvPoint, ptseq, index );
    }
    cvSetSeqReaderPos( &ptseq_reader, index );
    cvStartAppendToSeq( defects, &writer );

    /* cycle through ptseq and hull with computing defects */
    for( i = 0; i < hull->total; i++ )
    {
        CvConvexityDefect defect;
        int is_defect = 0;
        double dx0, dy0;
        double depth = 0, scale;
        CvPoint* hull_next;

        if( !is_index )
            hull_next = *(CvPoint**)hull_reader.ptr;
        else
        {
            int t = *(int*)hull_reader.ptr;
            hull_next = CV_GET_SEQ_ELEM( CvPoint, ptseq, t );
        }

        dx0 = (double)hull_next->x - (double)hull_cur->x;
        dy0 = (double)hull_next->y - (double)hull_cur->y;
        assert( dx0 != 0 || dy0 != 0 ); 
        scale = 1./sqrt(dx0*dx0 + dy0*dy0);

        defect.start = hull_cur;
        defect.end = hull_next;

        for(;;)
        {
            /* go through ptseq to achieve next hull point */
            CV_NEXT_SEQ_ELEM( sizeof(CvPoint), ptseq_reader );

            if( ptseq_reader.ptr == (char*)hull_next )
                break;
            else
            {
                CvPoint* cur = (CvPoint*)ptseq_reader.ptr;
            
                /* compute distance from current point to hull edge */
                double dx = (double)cur->x - (double)hull_cur->x;
                double dy = (double)cur->y - (double)hull_cur->y;

                /* compute depth */
                double dist = fabs(-dy0*dx + dx0*dy) * scale;

                if( dist > depth )
                {
                    depth = dist;
                    defect.depth_point = cur;
                    defect.depth = (float)depth;
                    is_defect = 1;
                }
            }
        }
        if( is_defect )
        {
            CV_WRITE_SEQ_ELEM( defect, writer );
        }

        hull_cur = hull_next;
        if( rev_orientation )
        {
            CV_PREV_SEQ_ELEM( hull->elem_size, hull_reader );
        }
        else
        {
            CV_NEXT_SEQ_ELEM( hull->elem_size, hull_reader );
        }
    }

    defects = cvEndWriteSeq( &writer );

    __END__;

    return defects;
}


CV_IMPL int
cvCheckContourConvexity( const CvArr* array )
{
    int flag = -1;

    CV_FUNCNAME( "cvCheckContourConvexity" );

    __BEGIN__;

    int i;
    int orientation = 0;
    CvSeqReader reader;
    CvContour contour_header;
    CvSeqBlock block;
    CvSeq* contour = (CvSeq*)array;

    if( CV_IS_SEQ(contour) )
    {
        if( !CV_IS_SEQ_POLYGON(contour))
            CV_ERROR( CV_StsUnsupportedFormat,
                "Input sequence must be polygon (closed 2d curve)" );
    }
    else
    {
        CV_CALL( contour = cvPointSeqFromMat(
            CV_SEQ_KIND_CURVE|CV_SEQ_FLAG_CLOSED, array, &contour_header, &block ));
    }

    if( contour->total == 0 )
        EXIT;

    cvStartReadSeq( contour, &reader, 0 );
    
    flag = 1;

    if( CV_SEQ_ELTYPE( contour ) == CV_32SC2 )
    {
        CvPoint *prev_pt = (CvPoint*)reader.prev_elem;
        CvPoint *cur_pt = (CvPoint*)reader.ptr;
    
        int dx0 = cur_pt->x - prev_pt->x;
        int dy0 = cur_pt->y - prev_pt->y;

        for( i = 0; i < contour->total; i++ )
        {
            int dxdy0, dydx0;
            int dx, dy;

            /*int orient; */
            CV_NEXT_SEQ_ELEM( sizeof(CvPoint), reader );
            prev_pt = cur_pt;
            cur_pt = (CvPoint *) reader.ptr;

            dx = cur_pt->x - prev_pt->x;
            dy = cur_pt->y - prev_pt->y;
            dxdy0 = dx * dy0;
            dydx0 = dy * dx0;

            /* find orientation */
            /*orient = -dy0 * dx + dx0 * dy;
               orientation |= (orient > 0) ? 1 : 2;
             */
            orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);

            if( orientation == 3 )
            {
                flag = 0;
                break;
            }

            dx0 = dx;
            dy0 = dy;
        }
    }
    else
    {
        assert( CV_SEQ_ELTYPE(contour) == CV_32FC2 );

        CvPoint2D32f *prev_pt = (CvPoint2D32f*)reader.prev_elem;
        CvPoint2D32f *cur_pt = (CvPoint2D32f*)reader.ptr;
    
        float dx0 = cur_pt->x - prev_pt->x;
        float dy0 = cur_pt->y - prev_pt->y;

        for( i = 0; i < contour->total; i++ )
        {
            float dxdy0, dydx0;
            float dx, dy;

            /*int orient; */
            CV_NEXT_SEQ_ELEM( sizeof(CvPoint2D32f), reader );
            prev_pt = cur_pt;
            cur_pt = (CvPoint2D32f*) reader.ptr;

            dx = cur_pt->x - prev_pt->x;
            dy = cur_pt->y - prev_pt->y;
            dxdy0 = dx * dy0;
            dydx0 = dy * dx0;

            /* find orientation */
            /*orient = -dy0 * dx + dx0 * dy;
               orientation |= (orient > 0) ? 1 : 2;
             */
            orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);

            if( orientation == 3 )
            {
                flag = 0;
                break;
            }

            dx0 = dx;
            dy0 = dy;
        }
    }

    __END__;

    return flag;
}


/* End of file. */