1/*M/////////////////////////////////////////////////////////////////////////////////////// 2// 3// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4// 5// By downloading, copying, installing or using the software you agree to this license. 6// If you do not agree to this license, do not download, install, 7// copy or use the software. 8// 9// 10// Intel License Agreement 11// For Open Source Computer Vision Library 12// 13// Copyright (C) 2000, Intel Corporation, all rights reserved. 14// Third party copyrights are property of their respective owners. 15// 16// Redistribution and use in source and binary forms, with or without modification, 17// are permitted provided that the following conditions are met: 18// 19// * Redistribution's of source code must retain the above copyright notice, 20// this list of conditions and the following disclaimer. 21// 22// * Redistribution's in binary form must reproduce the above copyright notice, 23// this list of conditions and the following disclaimer in the documentation 24// and/or other materials provided with the distribution. 25// 26// * The name of Intel Corporation may not be used to endorse or promote products 27// derived from this software without specific prior written permission. 28// 29// This software is provided by the copyright holders and contributors "as is" and 30// any express or implied warranties, including, but not limited to, the implied 31// warranties of merchantability and fitness for a particular purpose are disclaimed. 32// In no event shall the Intel Corporation or contributors be liable for any direct, 33// indirect, incidental, special, exemplary, or consequential damages 34// (including, but not limited to, procurement of substitute goods or services; 35// loss of use, data, or profits; or business interruption) however caused 36// and on any theory of liability, whether in contract, strict liability, 37// or tort (including negligence or otherwise) arising in any way out of 38// the use of this software, even if advised of the possibility of such damage. 39// 40//M*/ 41 42#include "_cv.h" 43 44static int 45icvSklansky_32s( CvPoint** array, int start, int end, int* stack, int nsign, int sign2 ) 46{ 47 int incr = end > start ? 1 : -1; 48 /* prepare first triangle */ 49 int pprev = start, pcur = pprev + incr, pnext = pcur + incr; 50 int stacksize = 3; 51 52 if( start == end || 53 (array[start]->x == array[end]->x && 54 array[start]->y == array[end]->y) ) 55 { 56 stack[0] = start; 57 return 1; 58 } 59 60 stack[0] = pprev; 61 stack[1] = pcur; 62 stack[2] = pnext; 63 64 end += incr; /* make end = afterend */ 65 66 while( pnext != end ) 67 { 68 /* check the angle p1,p2,p3 */ 69 int cury = array[pcur]->y; 70 int nexty = array[pnext]->y; 71 int by = nexty - cury; 72 73 if( CV_SIGN(by) != nsign ) 74 { 75 int ax = array[pcur]->x - array[pprev]->x; 76 int bx = array[pnext]->x - array[pcur]->x; 77 int ay = cury - array[pprev]->y; 78 int convexity = ay*bx - ax*by;/* if >0 then convex angle */ 79 80 if( CV_SIGN(convexity) == sign2 && (ax != 0 || ay != 0) ) 81 { 82 pprev = pcur; 83 pcur = pnext; 84 pnext += incr; 85 stack[stacksize] = pnext; 86 stacksize++; 87 } 88 else 89 { 90 if( pprev == start ) 91 { 92 pcur = pnext; 93 stack[1] = pcur; 94 pnext += incr; 95 stack[2] = pnext; 96 } 97 else 98 { 99 stack[stacksize-2] = pnext; 100 pcur = pprev; 101 pprev = stack[stacksize-4]; 102 stacksize--; 103 } 104 } 105 } 106 else 107 { 108 pnext += incr; 109 stack[stacksize-1] = pnext; 110 } 111 } 112 113 return --stacksize; 114} 115 116 117static int 118icvSklansky_32f( CvPoint2D32f** array, int start, int end, int* stack, int nsign, int sign2 ) 119{ 120 int incr = end > start ? 1 : -1; 121 /* prepare first triangle */ 122 int pprev = start, pcur = pprev + incr, pnext = pcur + incr; 123 int stacksize = 3; 124 125 if( start == end || 126 (array[start]->x == array[end]->x && 127 array[start]->y == array[end]->y) ) 128 { 129 stack[0] = start; 130 return 1; 131 } 132 133 stack[0] = pprev; 134 stack[1] = pcur; 135 stack[2] = pnext; 136 137 end += incr; /* make end = afterend */ 138 139 while( pnext != end ) 140 { 141 /* check the angle p1,p2,p3 */ 142 float cury = array[pcur]->y; 143 float nexty = array[pnext]->y; 144 float by = nexty - cury; 145 146 if( CV_SIGN( by ) != nsign ) 147 { 148 float ax = array[pcur]->x - array[pprev]->x; 149 float bx = array[pnext]->x - array[pcur]->x; 150 float ay = cury - array[pprev]->y; 151 float convexity = ay*bx - ax*by;/* if >0 then convex angle */ 152 153 if( CV_SIGN( convexity ) == sign2 && (ax != 0 || ay != 0) ) 154 { 155 pprev = pcur; 156 pcur = pnext; 157 pnext += incr; 158 stack[stacksize] = pnext; 159 stacksize++; 160 } 161 else 162 { 163 if( pprev == start ) 164 { 165 pcur = pnext; 166 stack[1] = pcur; 167 pnext += incr; 168 stack[2] = pnext; 169 170 } 171 else 172 { 173 stack[stacksize-2] = pnext; 174 pcur = pprev; 175 pprev = stack[stacksize-4]; 176 stacksize--; 177 } 178 } 179 } 180 else 181 { 182 pnext += incr; 183 stack[stacksize-1] = pnext; 184 } 185 } 186 187 return --stacksize; 188} 189 190typedef int (*sklansky_func)( CvPoint** points, int start, int end, 191 int* stack, int sign, int sign2 ); 192 193#define cmp_pts( pt1, pt2 ) \ 194 ((pt1)->x < (pt2)->x || ((pt1)->x <= (pt2)->x && (pt1)->y < (pt2)->y)) 195static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32s, CvPoint*, cmp_pts ) 196static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32f, CvPoint2D32f*, cmp_pts ) 197 198static void 199icvCalcAndWritePtIndices( CvPoint** pointer, int* stack, int start, int end, 200 CvSeq* ptseq, CvSeqWriter* writer ) 201{ 202 CV_FUNCNAME( "icvCalcAndWritePtIndices" ); 203 204 __BEGIN__; 205 206 int i, incr = start < end ? 1 : -1; 207 int idx, first_idx = ptseq->first->start_index; 208 209 for( i = start; i != end; i += incr ) 210 { 211 CvPoint* ptr = (CvPoint*)pointer[stack[i]]; 212 CvSeqBlock* block = ptseq->first; 213 while( (unsigned)(idx = (int)(ptr - (CvPoint*)block->data)) >= (unsigned)block->count ) 214 { 215 block = block->next; 216 if( block == ptseq->first ) 217 CV_ERROR( CV_StsError, "Internal error" ); 218 } 219 idx += block->start_index - first_idx; 220 CV_WRITE_SEQ_ELEM( idx, *writer ); 221 } 222 223 __END__; 224} 225 226 227CV_IMPL CvSeq* 228cvConvexHull2( const CvArr* array, void* hull_storage, 229 int orientation, int return_points ) 230{ 231 union { CvContour* c; CvSeq* s; } hull; 232 CvPoint** pointer = 0; 233 CvPoint2D32f** pointerf = 0; 234 int* stack = 0; 235 236 CV_FUNCNAME( "cvConvexHull2" ); 237 238 hull.s = 0; 239 240 __BEGIN__; 241 242 CvMat* mat = 0; 243 CvSeqReader reader; 244 CvSeqWriter writer; 245 CvContour contour_header; 246 union { CvContour c; CvSeq s; } hull_header; 247 CvSeqBlock block, hullblock; 248 CvSeq* ptseq = 0; 249 CvSeq* hullseq = 0; 250 int is_float; 251 int* t_stack; 252 int t_count; 253 int i, miny_ind = 0, maxy_ind = 0, total; 254 int hulltype; 255 int stop_idx; 256 sklansky_func sklansky; 257 258 if( CV_IS_SEQ( array )) 259 { 260 ptseq = (CvSeq*)array; 261 if( !CV_IS_SEQ_POINT_SET( ptseq )) 262 CV_ERROR( CV_StsBadArg, "Unsupported sequence type" ); 263 if( hull_storage == 0 ) 264 hull_storage = ptseq->storage; 265 } 266 else 267 { 268 CV_CALL( ptseq = cvPointSeqFromMat( 269 CV_SEQ_KIND_GENERIC, array, &contour_header, &block )); 270 } 271 272 if( CV_IS_STORAGE( hull_storage )) 273 { 274 if( return_points ) 275 { 276 CV_CALL( hullseq = cvCreateSeq( 277 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE(ptseq)| 278 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX, 279 sizeof(CvContour), sizeof(CvPoint),(CvMemStorage*)hull_storage )); 280 } 281 else 282 { 283 CV_CALL( hullseq = cvCreateSeq( 284 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_PPOINT| 285 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX, 286 sizeof(CvContour), sizeof(CvPoint*), (CvMemStorage*)hull_storage )); 287 } 288 } 289 else 290 { 291 if( !CV_IS_MAT( hull_storage )) 292 CV_ERROR(CV_StsBadArg, "Destination must be valid memory storage or matrix"); 293 294 mat = (CvMat*)hull_storage; 295 296 if( (mat->cols != 1 && mat->rows != 1) || !CV_IS_MAT_CONT(mat->type)) 297 CV_ERROR( CV_StsBadArg, 298 "The hull matrix should be continuous and have a single row or a single column" ); 299 300 if( mat->cols + mat->rows - 1 < ptseq->total ) 301 CV_ERROR( CV_StsBadSize, "The hull matrix size might be not enough to fit the hull" ); 302 303 if( CV_MAT_TYPE(mat->type) != CV_SEQ_ELTYPE(ptseq) && 304 CV_MAT_TYPE(mat->type) != CV_32SC1 ) 305 CV_ERROR( CV_StsUnsupportedFormat, 306 "The hull matrix must have the same type as input or 32sC1 (integers)" ); 307 308 CV_CALL( hullseq = cvMakeSeqHeaderForArray( 309 CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED, 310 sizeof(contour_header), CV_ELEM_SIZE(mat->type), mat->data.ptr, 311 mat->cols + mat->rows - 1, &hull_header.s, &hullblock )); 312 313 cvClearSeq( hullseq ); 314 } 315 316 total = ptseq->total; 317 if( total == 0 ) 318 { 319 if( mat ) 320 CV_ERROR( CV_StsBadSize, 321 "Point sequence can not be empty if the output is matrix" ); 322 EXIT; 323 } 324 325 cvStartAppendToSeq( hullseq, &writer ); 326 327 is_float = CV_SEQ_ELTYPE(ptseq) == CV_32FC2; 328 hulltype = CV_SEQ_ELTYPE(hullseq); 329 sklansky = !is_float ? (sklansky_func)icvSklansky_32s : 330 (sklansky_func)icvSklansky_32f; 331 332 CV_CALL( pointer = (CvPoint**)cvAlloc( ptseq->total*sizeof(pointer[0]) )); 333 CV_CALL( stack = (int*)cvAlloc( (ptseq->total + 2)*sizeof(stack[0]) )); 334 pointerf = (CvPoint2D32f**)pointer; 335 336 cvStartReadSeq( ptseq, &reader ); 337 338 for( i = 0; i < total; i++ ) 339 { 340 pointer[i] = (CvPoint*)reader.ptr; 341 CV_NEXT_SEQ_ELEM( ptseq->elem_size, reader ); 342 } 343 344 // sort the point set by x-coordinate, find min and max y 345 if( !is_float ) 346 { 347 icvSortPointsByPointers_32s( pointer, total, 0 ); 348 for( i = 1; i < total; i++ ) 349 { 350 int y = pointer[i]->y; 351 if( pointer[miny_ind]->y > y ) 352 miny_ind = i; 353 if( pointer[maxy_ind]->y < y ) 354 maxy_ind = i; 355 } 356 } 357 else 358 { 359 icvSortPointsByPointers_32f( pointerf, total, 0 ); 360 for( i = 1; i < total; i++ ) 361 { 362 float y = pointerf[i]->y; 363 if( pointerf[miny_ind]->y > y ) 364 miny_ind = i; 365 if( pointerf[maxy_ind]->y < y ) 366 maxy_ind = i; 367 } 368 } 369 370 if( pointer[0]->x == pointer[total-1]->x && 371 pointer[0]->y == pointer[total-1]->y ) 372 { 373 if( hulltype == CV_SEQ_ELTYPE_PPOINT ) 374 { 375 CV_WRITE_SEQ_ELEM( pointer[0], writer ); 376 } 377 else if( hulltype == CV_SEQ_ELTYPE_INDEX ) 378 { 379 int index = 0; 380 CV_WRITE_SEQ_ELEM( index, writer ); 381 } 382 else 383 { 384 CvPoint pt = pointer[0][0]; 385 CV_WRITE_SEQ_ELEM( pt, writer ); 386 } 387 goto finish_hull; 388 } 389 390 /*upper half */ 391 { 392 int *tl_stack = stack; 393 int tl_count = sklansky( pointer, 0, maxy_ind, tl_stack, -1, 1 ); 394 int *tr_stack = tl_stack + tl_count; 395 int tr_count = sklansky( pointer, ptseq->total - 1, maxy_ind, tr_stack, -1, -1 ); 396 397 /* gather upper part of convex hull to output */ 398 if( orientation == CV_COUNTER_CLOCKWISE ) 399 { 400 CV_SWAP( tl_stack, tr_stack, t_stack ); 401 CV_SWAP( tl_count, tr_count, t_count ); 402 } 403 404 if( hulltype == CV_SEQ_ELTYPE_PPOINT ) 405 { 406 for( i = 0; i < tl_count - 1; i++ ) 407 CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]], writer ); 408 409 for( i = tr_count - 1; i > 0; i-- ) 410 CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]], writer ); 411 } 412 else if( hulltype == CV_SEQ_ELTYPE_INDEX ) 413 { 414 CV_CALL( icvCalcAndWritePtIndices( pointer, tl_stack, 415 0, tl_count-1, ptseq, &writer )); 416 CV_CALL( icvCalcAndWritePtIndices( pointer, tr_stack, 417 tr_count-1, 0, ptseq, &writer )); 418 } 419 else 420 { 421 for( i = 0; i < tl_count - 1; i++ ) 422 CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]][0], writer ); 423 424 for( i = tr_count - 1; i > 0; i-- ) 425 CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]][0], writer ); 426 } 427 stop_idx = tr_count > 2 ? tr_stack[1] : tl_count > 2 ? tl_stack[tl_count - 2] : -1; 428 } 429 430 /* lower half */ 431 { 432 int *bl_stack = stack; 433 int bl_count = sklansky( pointer, 0, miny_ind, bl_stack, 1, -1 ); 434 int *br_stack = stack + bl_count; 435 int br_count = sklansky( pointer, ptseq->total - 1, miny_ind, br_stack, 1, 1 ); 436 437 if( orientation != CV_COUNTER_CLOCKWISE ) 438 { 439 CV_SWAP( bl_stack, br_stack, t_stack ); 440 CV_SWAP( bl_count, br_count, t_count ); 441 } 442 443 if( stop_idx >= 0 ) 444 { 445 int check_idx = bl_count > 2 ? bl_stack[1] : 446 bl_count + br_count > 2 ? br_stack[2-bl_count] : -1; 447 if( check_idx == stop_idx || (check_idx >= 0 && 448 pointer[check_idx]->x == pointer[stop_idx]->x && 449 pointer[check_idx]->y == pointer[stop_idx]->y) ) 450 { 451 /* if all the points lie on the same line, then 452 the bottom part of the convex hull is the mirrored top part 453 (except the exteme points).*/ 454 bl_count = MIN( bl_count, 2 ); 455 br_count = MIN( br_count, 2 ); 456 } 457 } 458 459 if( hulltype == CV_SEQ_ELTYPE_PPOINT ) 460 { 461 for( i = 0; i < bl_count - 1; i++ ) 462 CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]], writer ); 463 464 for( i = br_count - 1; i > 0; i-- ) 465 CV_WRITE_SEQ_ELEM( pointer[br_stack[i]], writer ); 466 } 467 else if( hulltype == CV_SEQ_ELTYPE_INDEX ) 468 { 469 CV_CALL( icvCalcAndWritePtIndices( pointer, bl_stack, 470 0, bl_count-1, ptseq, &writer )); 471 CV_CALL( icvCalcAndWritePtIndices( pointer, br_stack, 472 br_count-1, 0, ptseq, &writer )); 473 } 474 else 475 { 476 for( i = 0; i < bl_count - 1; i++ ) 477 CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]][0], writer ); 478 479 for( i = br_count - 1; i > 0; i-- ) 480 CV_WRITE_SEQ_ELEM( pointer[br_stack[i]][0], writer ); 481 } 482 } 483 484finish_hull: 485 CV_CALL( cvEndWriteSeq( &writer )); 486 487 if( mat ) 488 { 489 if( mat->rows > mat->cols ) 490 mat->rows = hullseq->total; 491 else 492 mat->cols = hullseq->total; 493 } 494 else 495 { 496 hull.s = hullseq; 497 hull.c->rect = cvBoundingRect( ptseq, 498 ptseq->header_size < (int)sizeof(CvContour) || 499 &ptseq->flags == &contour_header.flags ); 500 501 /*if( ptseq != (CvSeq*)&contour_header ) 502 hullseq->v_prev = ptseq;*/ 503 } 504 505 __END__; 506 507 cvFree( &pointer ); 508 cvFree( &stack ); 509 510 return hull.s; 511} 512 513 514/* contour must be a simple polygon */ 515/* it must have more than 3 points */ 516CV_IMPL CvSeq* 517cvConvexityDefects( const CvArr* array, 518 const CvArr* hullarray, 519 CvMemStorage* storage ) 520{ 521 CvSeq* defects = 0; 522 523 CV_FUNCNAME( "cvConvexityDefects" ); 524 525 __BEGIN__; 526 527 int i, index; 528 CvPoint* hull_cur; 529 530 /* is orientation of hull different from contour one */ 531 int rev_orientation; 532 533 CvContour contour_header; 534 union { CvContour c; CvSeq s; } hull_header; 535 CvSeqBlock block, hullblock; 536 CvSeq *ptseq = (CvSeq*)array, *hull = (CvSeq*)hullarray; 537 538 CvSeqReader hull_reader; 539 CvSeqReader ptseq_reader; 540 CvSeqWriter writer; 541 int is_index; 542 543 if( CV_IS_SEQ( ptseq )) 544 { 545 if( !CV_IS_SEQ_POINT_SET( ptseq )) 546 CV_ERROR( CV_StsUnsupportedFormat, 547 "Input sequence is not a sequence of points" ); 548 if( !storage ) 549 storage = ptseq->storage; 550 } 551 else 552 { 553 CV_CALL( ptseq = cvPointSeqFromMat( 554 CV_SEQ_KIND_GENERIC, array, &contour_header, &block )); 555 } 556 557 if( CV_SEQ_ELTYPE( ptseq ) != CV_32SC2 ) 558 CV_ERROR( CV_StsUnsupportedFormat, 559 "Floating-point coordinates are not supported here" ); 560 561 if( CV_IS_SEQ( hull )) 562 { 563 int hulltype = CV_SEQ_ELTYPE( hull ); 564 if( hulltype != CV_SEQ_ELTYPE_PPOINT && hulltype != CV_SEQ_ELTYPE_INDEX ) 565 CV_ERROR( CV_StsUnsupportedFormat, 566 "Convex hull must represented as a sequence " 567 "of indices or sequence of pointers" ); 568 if( !storage ) 569 storage = hull->storage; 570 } 571 else 572 { 573 CvMat* mat = (CvMat*)hull; 574 575 if( !CV_IS_MAT( hull )) 576 CV_ERROR(CV_StsBadArg, "Convex hull is neither sequence nor matrix"); 577 578 if( (mat->cols != 1 && mat->rows != 1) || 579 !CV_IS_MAT_CONT(mat->type) || CV_MAT_TYPE(mat->type) != CV_32SC1 ) 580 CV_ERROR( CV_StsBadArg, 581 "The matrix should be 1-dimensional and continuous array of int's" ); 582 583 if( mat->cols + mat->rows - 1 > ptseq->total ) 584 CV_ERROR( CV_StsBadSize, "Convex hull is larger than the point sequence" ); 585 586 CV_CALL( hull = cvMakeSeqHeaderForArray( 587 CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED, 588 sizeof(CvContour), CV_ELEM_SIZE(mat->type), mat->data.ptr, 589 mat->cols + mat->rows - 1, &hull_header.s, &hullblock )); 590 } 591 592 is_index = CV_SEQ_ELTYPE(hull) == CV_SEQ_ELTYPE_INDEX; 593 594 if( !storage ) 595 CV_ERROR( CV_StsNullPtr, "NULL storage pointer" ); 596 597 CV_CALL( defects = cvCreateSeq( CV_SEQ_KIND_GENERIC, sizeof(CvSeq), 598 sizeof(CvConvexityDefect), storage )); 599 600 if( ptseq->total < 4 || hull->total < 3) 601 { 602 //CV_ERROR( CV_StsBadSize, 603 // "point seq size must be >= 4, convex hull size must be >= 3" ); 604 EXIT; 605 } 606 607 /* recognize co-orientation of ptseq and its hull */ 608 { 609 int sign = 0; 610 int index1, index2, index3; 611 612 if( !is_index ) 613 { 614 CvPoint* pos = *CV_SEQ_ELEM( hull, CvPoint*, 0 ); 615 CV_CALL( index1 = cvSeqElemIdx( ptseq, pos )); 616 617 pos = *CV_SEQ_ELEM( hull, CvPoint*, 1 ); 618 CV_CALL( index2 = cvSeqElemIdx( ptseq, pos )); 619 620 pos = *CV_SEQ_ELEM( hull, CvPoint*, 2 ); 621 CV_CALL( index3 = cvSeqElemIdx( ptseq, pos )); 622 } 623 else 624 { 625 index1 = *CV_SEQ_ELEM( hull, int, 0 ); 626 index2 = *CV_SEQ_ELEM( hull, int, 1 ); 627 index3 = *CV_SEQ_ELEM( hull, int, 2 ); 628 } 629 630 sign += (index2 > index1) ? 1 : 0; 631 sign += (index3 > index2) ? 1 : 0; 632 sign += (index1 > index3) ? 1 : 0; 633 634 rev_orientation = (sign == 2) ? 0 : 1; 635 } 636 637 cvStartReadSeq( ptseq, &ptseq_reader, 0 ); 638 cvStartReadSeq( hull, &hull_reader, rev_orientation ); 639 640 if( !is_index ) 641 { 642 hull_cur = *(CvPoint**)hull_reader.prev_elem; 643 index = cvSeqElemIdx( ptseq, (char*)hull_cur, 0 ); 644 } 645 else 646 { 647 index = *(int*)hull_reader.prev_elem; 648 hull_cur = CV_GET_SEQ_ELEM( CvPoint, ptseq, index ); 649 } 650 cvSetSeqReaderPos( &ptseq_reader, index ); 651 cvStartAppendToSeq( defects, &writer ); 652 653 /* cycle through ptseq and hull with computing defects */ 654 for( i = 0; i < hull->total; i++ ) 655 { 656 CvConvexityDefect defect; 657 int is_defect = 0; 658 double dx0, dy0; 659 double depth = 0, scale; 660 CvPoint* hull_next; 661 662 if( !is_index ) 663 hull_next = *(CvPoint**)hull_reader.ptr; 664 else 665 { 666 int t = *(int*)hull_reader.ptr; 667 hull_next = CV_GET_SEQ_ELEM( CvPoint, ptseq, t ); 668 } 669 670 dx0 = (double)hull_next->x - (double)hull_cur->x; 671 dy0 = (double)hull_next->y - (double)hull_cur->y; 672 assert( dx0 != 0 || dy0 != 0 ); 673 scale = 1./sqrt(dx0*dx0 + dy0*dy0); 674 675 defect.start = hull_cur; 676 defect.end = hull_next; 677 678 for(;;) 679 { 680 /* go through ptseq to achieve next hull point */ 681 CV_NEXT_SEQ_ELEM( sizeof(CvPoint), ptseq_reader ); 682 683 if( ptseq_reader.ptr == (schar*)hull_next ) 684 break; 685 else 686 { 687 CvPoint* cur = (CvPoint*)ptseq_reader.ptr; 688 689 /* compute distance from current point to hull edge */ 690 double dx = (double)cur->x - (double)hull_cur->x; 691 double dy = (double)cur->y - (double)hull_cur->y; 692 693 /* compute depth */ 694 double dist = fabs(-dy0*dx + dx0*dy) * scale; 695 696 if( dist > depth ) 697 { 698 depth = dist; 699 defect.depth_point = cur; 700 defect.depth = (float)depth; 701 is_defect = 1; 702 } 703 } 704 } 705 if( is_defect ) 706 { 707 CV_WRITE_SEQ_ELEM( defect, writer ); 708 } 709 710 hull_cur = hull_next; 711 if( rev_orientation ) 712 { 713 CV_PREV_SEQ_ELEM( hull->elem_size, hull_reader ); 714 } 715 else 716 { 717 CV_NEXT_SEQ_ELEM( hull->elem_size, hull_reader ); 718 } 719 } 720 721 defects = cvEndWriteSeq( &writer ); 722 723 __END__; 724 725 return defects; 726} 727 728 729CV_IMPL int 730cvCheckContourConvexity( const CvArr* array ) 731{ 732 int flag = -1; 733 734 CV_FUNCNAME( "cvCheckContourConvexity" ); 735 736 __BEGIN__; 737 738 int i; 739 int orientation = 0; 740 CvSeqReader reader; 741 CvContour contour_header; 742 CvSeqBlock block; 743 CvSeq* contour = (CvSeq*)array; 744 745 if( CV_IS_SEQ(contour) ) 746 { 747 if( !CV_IS_SEQ_POLYGON(contour)) 748 CV_ERROR( CV_StsUnsupportedFormat, 749 "Input sequence must be polygon (closed 2d curve)" ); 750 } 751 else 752 { 753 CV_CALL( contour = cvPointSeqFromMat( 754 CV_SEQ_KIND_CURVE|CV_SEQ_FLAG_CLOSED, array, &contour_header, &block )); 755 } 756 757 if( contour->total == 0 ) 758 EXIT; 759 760 cvStartReadSeq( contour, &reader, 0 ); 761 762 flag = 1; 763 764 if( CV_SEQ_ELTYPE( contour ) == CV_32SC2 ) 765 { 766 CvPoint *prev_pt = (CvPoint*)reader.prev_elem; 767 CvPoint *cur_pt = (CvPoint*)reader.ptr; 768 769 int dx0 = cur_pt->x - prev_pt->x; 770 int dy0 = cur_pt->y - prev_pt->y; 771 772 for( i = 0; i < contour->total; i++ ) 773 { 774 int dxdy0, dydx0; 775 int dx, dy; 776 777 /*int orient; */ 778 CV_NEXT_SEQ_ELEM( sizeof(CvPoint), reader ); 779 prev_pt = cur_pt; 780 cur_pt = (CvPoint *) reader.ptr; 781 782 dx = cur_pt->x - prev_pt->x; 783 dy = cur_pt->y - prev_pt->y; 784 dxdy0 = dx * dy0; 785 dydx0 = dy * dx0; 786 787 /* find orientation */ 788 /*orient = -dy0 * dx + dx0 * dy; 789 orientation |= (orient > 0) ? 1 : 2; 790 */ 791 orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3); 792 793 if( orientation == 3 ) 794 { 795 flag = 0; 796 break; 797 } 798 799 dx0 = dx; 800 dy0 = dy; 801 } 802 } 803 else 804 { 805 assert( CV_SEQ_ELTYPE(contour) == CV_32FC2 ); 806 807 CvPoint2D32f *prev_pt = (CvPoint2D32f*)reader.prev_elem; 808 CvPoint2D32f *cur_pt = (CvPoint2D32f*)reader.ptr; 809 810 float dx0 = cur_pt->x - prev_pt->x; 811 float dy0 = cur_pt->y - prev_pt->y; 812 813 for( i = 0; i < contour->total; i++ ) 814 { 815 float dxdy0, dydx0; 816 float dx, dy; 817 818 /*int orient; */ 819 CV_NEXT_SEQ_ELEM( sizeof(CvPoint2D32f), reader ); 820 prev_pt = cur_pt; 821 cur_pt = (CvPoint2D32f*) reader.ptr; 822 823 dx = cur_pt->x - prev_pt->x; 824 dy = cur_pt->y - prev_pt->y; 825 dxdy0 = dx * dy0; 826 dydx0 = dy * dx0; 827 828 /* find orientation */ 829 /*orient = -dy0 * dx + dx0 * dy; 830 orientation |= (orient > 0) ? 1 : 2; 831 */ 832 orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3); 833 834 if( orientation == 3 ) 835 { 836 flag = 0; 837 break; 838 } 839 840 dx0 = dx; 841 dy0 = dy; 842 } 843 } 844 845 __END__; 846 847 return flag; 848} 849 850 851/* End of file. */ 852