| /*M/////////////////////////////////////////////////////////////////////////////////////// |
| // |
| // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. |
| // |
| // By downloading, copying, installing or using the software you agree to this license. |
| // If you do not agree to this license, do not download, install, |
| // copy or use the software. |
| // |
| // |
| // Intel License Agreement |
| // For Open Source Computer Vision Library |
| // |
| // Copyright (C) 2000, Intel Corporation, all rights reserved. |
| // Third party copyrights are property of their respective owners. |
| // |
| // Redistribution and use in source and binary forms, with or without modification, |
| // are permitted provided that the following conditions are met: |
| // |
| // * Redistribution's of source code must retain the above copyright notice, |
| // this list of conditions and the following disclaimer. |
| // |
| // * Redistribution's in binary form must reproduce the above copyright notice, |
| // this list of conditions and the following disclaimer in the documentation |
| // and/or other materials provided with the distribution. |
| // |
| // * The name of Intel Corporation may not be used to endorse or promote products |
| // derived from this software without specific prior written permission. |
| // |
| // This software is provided by the copyright holders and contributors "as is" and |
| // any express or implied warranties, including, but not limited to, the implied |
| // warranties of merchantability and fitness for a particular purpose are disclaimed. |
| // In no event shall the Intel Corporation or contributors be liable for any direct, |
| // indirect, incidental, special, exemplary, or consequential damages |
| // (including, but not limited to, procurement of substitute goods or services; |
| // loss of use, data, or profits; or business interruption) however caused |
| // and on any theory of liability, whether in contract, strict liability, |
| // or tort (including negligence or otherwise) arising in any way out of |
| // the use of this software, even if advised of the possibility of such damage. |
| // |
| //M*/ |
| |
| #include "_cv.h" |
| |
| static int |
| icvSklansky_32s( CvPoint** array, int start, int end, int* stack, int nsign, int sign2 ) |
| { |
| int incr = end > start ? 1 : -1; |
| /* prepare first triangle */ |
| int pprev = start, pcur = pprev + incr, pnext = pcur + incr; |
| int stacksize = 3; |
| |
| if( start == end || |
| (array[start]->x == array[end]->x && |
| array[start]->y == array[end]->y) ) |
| { |
| stack[0] = start; |
| return 1; |
| } |
| |
| stack[0] = pprev; |
| stack[1] = pcur; |
| stack[2] = pnext; |
| |
| end += incr; /* make end = afterend */ |
| |
| while( pnext != end ) |
| { |
| /* check the angle p1,p2,p3 */ |
| int cury = array[pcur]->y; |
| int nexty = array[pnext]->y; |
| int by = nexty - cury; |
| |
| if( CV_SIGN(by) != nsign ) |
| { |
| int ax = array[pcur]->x - array[pprev]->x; |
| int bx = array[pnext]->x - array[pcur]->x; |
| int ay = cury - array[pprev]->y; |
| int convexity = ay*bx - ax*by;/* if >0 then convex angle */ |
| |
| if( CV_SIGN(convexity) == sign2 && (ax != 0 || ay != 0) ) |
| { |
| pprev = pcur; |
| pcur = pnext; |
| pnext += incr; |
| stack[stacksize] = pnext; |
| stacksize++; |
| } |
| else |
| { |
| if( pprev == start ) |
| { |
| pcur = pnext; |
| stack[1] = pcur; |
| pnext += incr; |
| stack[2] = pnext; |
| } |
| else |
| { |
| stack[stacksize-2] = pnext; |
| pcur = pprev; |
| pprev = stack[stacksize-4]; |
| stacksize--; |
| } |
| } |
| } |
| else |
| { |
| pnext += incr; |
| stack[stacksize-1] = pnext; |
| } |
| } |
| |
| return --stacksize; |
| } |
| |
| |
| static int |
| icvSklansky_32f( CvPoint2D32f** array, int start, int end, int* stack, int nsign, int sign2 ) |
| { |
| int incr = end > start ? 1 : -1; |
| /* prepare first triangle */ |
| int pprev = start, pcur = pprev + incr, pnext = pcur + incr; |
| int stacksize = 3; |
| |
| if( start == end || |
| (array[start]->x == array[end]->x && |
| array[start]->y == array[end]->y) ) |
| { |
| stack[0] = start; |
| return 1; |
| } |
| |
| stack[0] = pprev; |
| stack[1] = pcur; |
| stack[2] = pnext; |
| |
| end += incr; /* make end = afterend */ |
| |
| while( pnext != end ) |
| { |
| /* check the angle p1,p2,p3 */ |
| float cury = array[pcur]->y; |
| float nexty = array[pnext]->y; |
| float by = nexty - cury; |
| |
| if( CV_SIGN( by ) != nsign ) |
| { |
| float ax = array[pcur]->x - array[pprev]->x; |
| float bx = array[pnext]->x - array[pcur]->x; |
| float ay = cury - array[pprev]->y; |
| float convexity = ay*bx - ax*by;/* if >0 then convex angle */ |
| |
| if( CV_SIGN( convexity ) == sign2 && (ax != 0 || ay != 0) ) |
| { |
| pprev = pcur; |
| pcur = pnext; |
| pnext += incr; |
| stack[stacksize] = pnext; |
| stacksize++; |
| } |
| else |
| { |
| if( pprev == start ) |
| { |
| pcur = pnext; |
| stack[1] = pcur; |
| pnext += incr; |
| stack[2] = pnext; |
| |
| } |
| else |
| { |
| stack[stacksize-2] = pnext; |
| pcur = pprev; |
| pprev = stack[stacksize-4]; |
| stacksize--; |
| } |
| } |
| } |
| else |
| { |
| pnext += incr; |
| stack[stacksize-1] = pnext; |
| } |
| } |
| |
| return --stacksize; |
| } |
| |
| typedef int (*sklansky_func)( CvPoint** points, int start, int end, |
| int* stack, int sign, int sign2 ); |
| |
| #define cmp_pts( pt1, pt2 ) \ |
| ((pt1)->x < (pt2)->x || ((pt1)->x <= (pt2)->x && (pt1)->y < (pt2)->y)) |
| static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32s, CvPoint*, cmp_pts ) |
| static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32f, CvPoint2D32f*, cmp_pts ) |
| |
| static void |
| icvCalcAndWritePtIndices( CvPoint** pointer, int* stack, int start, int end, |
| CvSeq* ptseq, CvSeqWriter* writer ) |
| { |
| CV_FUNCNAME( "icvCalcAndWritePtIndices" ); |
| |
| __BEGIN__; |
| |
| int i, incr = start < end ? 1 : -1; |
| int idx, first_idx = ptseq->first->start_index; |
| |
| for( i = start; i != end; i += incr ) |
| { |
| CvPoint* ptr = (CvPoint*)pointer[stack[i]]; |
| CvSeqBlock* block = ptseq->first; |
| while( (unsigned)(idx = (int)(ptr - (CvPoint*)block->data)) >= (unsigned)block->count ) |
| { |
| block = block->next; |
| if( block == ptseq->first ) |
| CV_ERROR( CV_StsError, "Internal error" ); |
| } |
| idx += block->start_index - first_idx; |
| CV_WRITE_SEQ_ELEM( idx, *writer ); |
| } |
| |
| __END__; |
| } |
| |
| |
| CV_IMPL CvSeq* |
| cvConvexHull2( const CvArr* array, void* hull_storage, |
| int orientation, int return_points ) |
| { |
| union { CvContour* c; CvSeq* s; } hull; |
| CvPoint** pointer = 0; |
| CvPoint2D32f** pointerf = 0; |
| int* stack = 0; |
| |
| CV_FUNCNAME( "cvConvexHull2" ); |
| |
| hull.s = 0; |
| |
| __BEGIN__; |
| |
| 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 |
| { |
| CV_CALL( ptseq = cvPointSeqFromMat( |
| CV_SEQ_KIND_GENERIC, array, &contour_header, &block )); |
| } |
| |
| if( CV_IS_STORAGE( hull_storage )) |
| { |
| if( return_points ) |
| { |
| CV_CALL( 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 |
| { |
| CV_CALL( 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)" ); |
| |
| CV_CALL( 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" ); |
| EXIT; |
| } |
| |
| 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; |
| |
| CV_CALL( pointer = (CvPoint**)cvAlloc( ptseq->total*sizeof(pointer[0]) )); |
| CV_CALL( stack = (int*)cvAlloc( (ptseq->total + 2)*sizeof(stack[0]) )); |
| pointerf = (CvPoint2D32f**)pointer; |
| |
| 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 ) |
| { |
| CV_CALL( icvCalcAndWritePtIndices( pointer, tl_stack, |
| 0, tl_count-1, ptseq, &writer )); |
| CV_CALL( 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 ) |
| { |
| 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 == (schar*)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. */ |
