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 "precomp.hpp" 43 #include <iostream> 44 45 namespace cv 46 { 47 48 template<typename _Tp> 49 static int Sklansky_( Point_<_Tp>** array, int start, int end, int* stack, int nsign, int sign2 ) 50 { 51 int incr = end > start ? 1 : -1; 52 // prepare first triangle 53 int pprev = start, pcur = pprev + incr, pnext = pcur + incr; 54 int stacksize = 3; 55 56 if( start == end || 57 (array[start]->x == array[end]->x && 58 array[start]->y == array[end]->y) ) 59 { 60 stack[0] = start; 61 return 1; 62 } 63 64 stack[0] = pprev; 65 stack[1] = pcur; 66 stack[2] = pnext; 67 68 end += incr; // make end = afterend 69 70 while( pnext != end ) 71 { 72 // check the angle p1,p2,p3 73 _Tp cury = array[pcur]->y; 74 _Tp nexty = array[pnext]->y; 75 _Tp by = nexty - cury; 76 77 if( CV_SIGN( by ) != nsign ) 78 { 79 _Tp ax = array[pcur]->x - array[pprev]->x; 80 _Tp bx = array[pnext]->x - array[pcur]->x; 81 _Tp ay = cury - array[pprev]->y; 82 _Tp convexity = ay*bx - ax*by; // if >0 then convex angle 83 84 if( CV_SIGN( convexity ) == sign2 && (ax != 0 || ay != 0) ) 85 { 86 pprev = pcur; 87 pcur = pnext; 88 pnext += incr; 89 stack[stacksize] = pnext; 90 stacksize++; 91 } 92 else 93 { 94 if( pprev == start ) 95 { 96 pcur = pnext; 97 stack[1] = pcur; 98 pnext += incr; 99 stack[2] = pnext; 100 } 101 else 102 { 103 stack[stacksize-2] = pnext; 104 pcur = pprev; 105 pprev = stack[stacksize-4]; 106 stacksize--; 107 } 108 } 109 } 110 else 111 { 112 pnext += incr; 113 stack[stacksize-1] = pnext; 114 } 115 } 116 117 return --stacksize; 118 } 119 120 121 template<typename _Tp> 122 struct CHullCmpPoints 123 { 124 bool operator()(const Point_<_Tp>* p1, const Point_<_Tp>* p2) const 125 { return p1->x < p2->x || (p1->x == p2->x && p1->y < p2->y); } 126 }; 127 128 129 void convexHull( InputArray _points, OutputArray _hull, bool clockwise, bool returnPoints ) 130 { 131 Mat points = _points.getMat(); 132 int i, total = points.checkVector(2), depth = points.depth(), nout = 0; 133 int miny_ind = 0, maxy_ind = 0; 134 CV_Assert(total >= 0 && (depth == CV_32F || depth == CV_32S)); 135 136 if( total == 0 ) 137 { 138 _hull.release(); 139 return; 140 } 141 142 returnPoints = !_hull.fixedType() ? returnPoints : _hull.type() != CV_32S; 143 144 bool is_float = depth == CV_32F; 145 AutoBuffer<Point*> _pointer(total); 146 AutoBuffer<int> _stack(total + 2), _hullbuf(total); 147 Point** pointer = _pointer; 148 Point2f** pointerf = (Point2f**)pointer; 149 Point* data0 = points.ptr<Point>(); 150 int* stack = _stack; 151 int* hullbuf = _hullbuf; 152 153 CV_Assert(points.isContinuous()); 154 155 for( i = 0; i < total; i++ ) 156 pointer[i] = &data0[i]; 157 158 // sort the point set by x-coordinate, find min and max y 159 if( !is_float ) 160 { 161 std::sort(pointer, pointer + total, CHullCmpPoints<int>()); 162 for( i = 1; i < total; i++ ) 163 { 164 int y = pointer[i]->y; 165 if( pointer[miny_ind]->y > y ) 166 miny_ind = i; 167 if( pointer[maxy_ind]->y < y ) 168 maxy_ind = i; 169 } 170 } 171 else 172 { 173 std::sort(pointerf, pointerf + total, CHullCmpPoints<float>()); 174 for( i = 1; i < total; i++ ) 175 { 176 float y = pointerf[i]->y; 177 if( pointerf[miny_ind]->y > y ) 178 miny_ind = i; 179 if( pointerf[maxy_ind]->y < y ) 180 maxy_ind = i; 181 } 182 } 183 184 if( pointer[0]->x == pointer[total-1]->x && 185 pointer[0]->y == pointer[total-1]->y ) 186 { 187 hullbuf[nout++] = 0; 188 } 189 else 190 { 191 // upper half 192 int *tl_stack = stack; 193 int tl_count = !is_float ? 194 Sklansky_( pointer, 0, maxy_ind, tl_stack, -1, 1) : 195 Sklansky_( pointerf, 0, maxy_ind, tl_stack, -1, 1); 196 int *tr_stack = stack + tl_count; 197 int tr_count = !is_float ? 198 Sklansky_( pointer, total-1, maxy_ind, tr_stack, -1, -1) : 199 Sklansky_( pointerf, total-1, maxy_ind, tr_stack, -1, -1); 200 201 // gather upper part of convex hull to output 202 if( !clockwise ) 203 { 204 std::swap( tl_stack, tr_stack ); 205 std::swap( tl_count, tr_count ); 206 } 207 208 for( i = 0; i < tl_count-1; i++ ) 209 hullbuf[nout++] = int(pointer[tl_stack[i]] - data0); 210 for( i = tr_count - 1; i > 0; i-- ) 211 hullbuf[nout++] = int(pointer[tr_stack[i]] - data0); 212 int stop_idx = tr_count > 2 ? tr_stack[1] : tl_count > 2 ? tl_stack[tl_count - 2] : -1; 213 214 // lower half 215 int *bl_stack = stack; 216 int bl_count = !is_float ? 217 Sklansky_( pointer, 0, miny_ind, bl_stack, 1, -1) : 218 Sklansky_( pointerf, 0, miny_ind, bl_stack, 1, -1); 219 int *br_stack = stack + bl_count; 220 int br_count = !is_float ? 221 Sklansky_( pointer, total-1, miny_ind, br_stack, 1, 1) : 222 Sklansky_( pointerf, total-1, miny_ind, br_stack, 1, 1); 223 224 if( clockwise ) 225 { 226 std::swap( bl_stack, br_stack ); 227 std::swap( bl_count, br_count ); 228 } 229 230 if( stop_idx >= 0 ) 231 { 232 int check_idx = bl_count > 2 ? bl_stack[1] : 233 bl_count + br_count > 2 ? br_stack[2-bl_count] : -1; 234 if( check_idx == stop_idx || (check_idx >= 0 && 235 pointer[check_idx]->x == pointer[stop_idx]->x && 236 pointer[check_idx]->y == pointer[stop_idx]->y) ) 237 { 238 // if all the points lie on the same line, then 239 // the bottom part of the convex hull is the mirrored top part 240 // (except the exteme points). 241 bl_count = MIN( bl_count, 2 ); 242 br_count = MIN( br_count, 2 ); 243 } 244 } 245 246 for( i = 0; i < bl_count-1; i++ ) 247 hullbuf[nout++] = int(pointer[bl_stack[i]] - data0); 248 for( i = br_count-1; i > 0; i-- ) 249 hullbuf[nout++] = int(pointer[br_stack[i]] - data0); 250 } 251 252 if( !returnPoints ) 253 Mat(nout, 1, CV_32S, hullbuf).copyTo(_hull); 254 else 255 { 256 _hull.create(nout, 1, CV_MAKETYPE(depth, 2)); 257 Mat hull = _hull.getMat(); 258 size_t step = !hull.isContinuous() ? hull.step[0] : sizeof(Point); 259 for( i = 0; i < nout; i++ ) 260 *(Point*)(hull.ptr() + i*step) = data0[hullbuf[i]]; 261 } 262 } 263 264 265 void convexityDefects( InputArray _points, InputArray _hull, OutputArray _defects ) 266 { 267 Mat points = _points.getMat(); 268 int i, j = 0, npoints = points.checkVector(2, CV_32S); 269 CV_Assert( npoints >= 0 ); 270 271 if( npoints <= 3 ) 272 { 273 _defects.release(); 274 return; 275 } 276 277 Mat hull = _hull.getMat(); 278 int hpoints = hull.checkVector(1, CV_32S); 279 CV_Assert( hpoints > 2 ); 280 281 const Point* ptr = points.ptr<Point>(); 282 const int* hptr = hull.ptr<int>(); 283 std::vector<Vec4i> defects; 284 285 // 1. recognize co-orientation of the contour and its hull 286 bool rev_orientation = ((hptr[1] > hptr[0]) + (hptr[2] > hptr[1]) + (hptr[0] > hptr[2])) != 2; 287 288 // 2. cycle through points and hull, compute defects 289 int hcurr = hptr[rev_orientation ? 0 : hpoints-1]; 290 CV_Assert( 0 <= hcurr && hcurr < npoints ); 291 292 for( i = 0; i < hpoints; i++ ) 293 { 294 int hnext = hptr[rev_orientation ? hpoints - i - 1 : i]; 295 CV_Assert( 0 <= hnext && hnext < npoints ); 296 297 Point pt0 = ptr[hcurr], pt1 = ptr[hnext]; 298 double dx0 = pt1.x - pt0.x; 299 double dy0 = pt1.y - pt0.y; 300 double scale = dx0 == 0 && dy0 == 0 ? 0. : 1./std::sqrt(dx0*dx0 + dy0*dy0); 301 302 int defect_deepest_point = -1; 303 double defect_depth = 0; 304 bool is_defect = false; 305 306 for(;;) 307 { 308 // go through points to achieve next hull point 309 j++; 310 j &= j >= npoints ? 0 : -1; 311 if( j == hnext ) 312 break; 313 314 // compute distance from current point to hull edge 315 double dx = ptr[j].x - pt0.x; 316 double dy = ptr[j].y - pt0.y; 317 double dist = fabs(-dy0*dx + dx0*dy) * scale; 318 319 if( dist > defect_depth ) 320 { 321 defect_depth = dist; 322 defect_deepest_point = j; 323 is_defect = true; 324 } 325 } 326 327 if( is_defect ) 328 { 329 int idepth = cvRound(defect_depth*256); 330 defects.push_back(Vec4i(hcurr, hnext, defect_deepest_point, idepth)); 331 } 332 333 hcurr = hnext; 334 } 335 336 Mat(defects).copyTo(_defects); 337 } 338 339 340 template<typename _Tp> 341 static bool isContourConvex_( const Point_<_Tp>* p, int n ) 342 { 343 Point_<_Tp> prev_pt = p[(n-2+n) % n]; 344 Point_<_Tp> cur_pt = p[n-1]; 345 346 _Tp dx0 = cur_pt.x - prev_pt.x; 347 _Tp dy0 = cur_pt.y - prev_pt.y; 348 int orientation = 0; 349 350 for( int i = 0; i < n; i++ ) 351 { 352 _Tp dxdy0, dydx0; 353 _Tp dx, dy; 354 355 prev_pt = cur_pt; 356 cur_pt = p[i]; 357 358 dx = cur_pt.x - prev_pt.x; 359 dy = cur_pt.y - prev_pt.y; 360 dxdy0 = dx * dy0; 361 dydx0 = dy * dx0; 362 363 // find orientation 364 // orient = -dy0 * dx + dx0 * dy; 365 // orientation |= (orient > 0) ? 1 : 2; 366 orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3); 367 if( orientation == 3 ) 368 return false; 369 370 dx0 = dx; 371 dy0 = dy; 372 } 373 374 return true; 375 } 376 377 378 bool isContourConvex( InputArray _contour ) 379 { 380 Mat contour = _contour.getMat(); 381 int total = contour.checkVector(2), depth = contour.depth(); 382 CV_Assert(total >= 0 && (depth == CV_32F || depth == CV_32S)); 383 384 if( total == 0 ) 385 return false; 386 387 return depth == CV_32S ? 388 isContourConvex_(contour.ptr<Point>(), total ) : 389 isContourConvex_(contour.ptr<Point2f>(), total ); 390 } 391 392 } 393 394 CV_IMPL CvSeq* 395 cvConvexHull2( const CvArr* array, void* hull_storage, 396 int orientation, int return_points ) 397 { 398 union { CvContour* c; CvSeq* s; } hull; 399 hull.s = 0; 400 401 CvMat* mat = 0; 402 CvContour contour_header; 403 CvSeq hull_header; 404 CvSeqBlock block, hullblock; 405 CvSeq* ptseq = 0; 406 CvSeq* hullseq = 0; 407 408 if( CV_IS_SEQ( array )) 409 { 410 ptseq = (CvSeq*)array; 411 if( !CV_IS_SEQ_POINT_SET( ptseq )) 412 CV_Error( CV_StsBadArg, "Unsupported sequence type" ); 413 if( hull_storage == 0 ) 414 hull_storage = ptseq->storage; 415 } 416 else 417 { 418 ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block ); 419 } 420 421 if( CV_IS_STORAGE( hull_storage )) 422 { 423 if( return_points ) 424 { 425 hullseq = cvCreateSeq(CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE(ptseq)| 426 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX, 427 sizeof(CvContour), sizeof(CvPoint),(CvMemStorage*)hull_storage ); 428 } 429 else 430 { 431 hullseq = cvCreateSeq( 432 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_PPOINT| 433 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX, 434 sizeof(CvContour), sizeof(CvPoint*), (CvMemStorage*)hull_storage ); 435 } 436 } 437 else 438 { 439 if( !CV_IS_MAT( hull_storage )) 440 CV_Error(CV_StsBadArg, "Destination must be valid memory storage or matrix"); 441 442 mat = (CvMat*)hull_storage; 443 444 if( (mat->cols != 1 && mat->rows != 1) || !CV_IS_MAT_CONT(mat->type)) 445 CV_Error( CV_StsBadArg, 446 "The hull matrix should be continuous and have a single row or a single column" ); 447 448 if( mat->cols + mat->rows - 1 < ptseq->total ) 449 CV_Error( CV_StsBadSize, "The hull matrix size might be not enough to fit the hull" ); 450 451 if( CV_MAT_TYPE(mat->type) != CV_SEQ_ELTYPE(ptseq) && 452 CV_MAT_TYPE(mat->type) != CV_32SC1 ) 453 CV_Error( CV_StsUnsupportedFormat, 454 "The hull matrix must have the same type as input or 32sC1 (integers)" ); 455 456 hullseq = cvMakeSeqHeaderForArray( 457 CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED, 458 sizeof(hull_header), CV_ELEM_SIZE(mat->type), mat->data.ptr, 459 mat->cols + mat->rows - 1, &hull_header, &hullblock ); 460 cvClearSeq( hullseq ); 461 } 462 463 int hulltype = CV_SEQ_ELTYPE(hullseq); 464 int total = ptseq->total; 465 if( total == 0 ) 466 { 467 if( mat ) 468 CV_Error( CV_StsBadSize, 469 "Point sequence can not be empty if the output is matrix" ); 470 return hull.s; 471 } 472 473 cv::AutoBuffer<double> _ptbuf; 474 cv::Mat h0; 475 cv::convexHull(cv::cvarrToMat(ptseq, false, false, 0, &_ptbuf), h0, 476 orientation == CV_CLOCKWISE, CV_MAT_CN(hulltype) == 2); 477 478 479 if( hulltype == CV_SEQ_ELTYPE_PPOINT ) 480 { 481 const int* idx = h0.ptr<int>(); 482 int ctotal = (int)h0.total(); 483 for( int i = 0; i < ctotal; i++ ) 484 { 485 void* ptr = cvGetSeqElem(ptseq, idx[i]); 486 cvSeqPush( hullseq, &ptr ); 487 } 488 } 489 else 490 cvSeqPushMulti(hullseq, h0.ptr(), (int)h0.total()); 491 492 if( mat ) 493 { 494 if( mat->rows > mat->cols ) 495 mat->rows = hullseq->total; 496 else 497 mat->cols = hullseq->total; 498 } 499 else 500 { 501 hull.s = hullseq; 502 hull.c->rect = cvBoundingRect( ptseq, 503 ptseq->header_size < (int)sizeof(CvContour) || 504 &ptseq->flags == &contour_header.flags ); 505 } 506 507 return hull.s; 508 } 509 510 511 /* contour must be a simple polygon */ 512 /* it must have more than 3 points */ 513 CV_IMPL CvSeq* cvConvexityDefects( const CvArr* array, 514 const CvArr* hullarray, 515 CvMemStorage* storage ) 516 { 517 CvSeq* defects = 0; 518 519 int i, index; 520 CvPoint* hull_cur; 521 522 /* is orientation of hull different from contour one */ 523 int rev_orientation; 524 525 CvContour contour_header; 526 CvSeq hull_header; 527 CvSeqBlock block, hullblock; 528 CvSeq *ptseq = (CvSeq*)array, *hull = (CvSeq*)hullarray; 529 530 CvSeqReader hull_reader; 531 CvSeqReader ptseq_reader; 532 CvSeqWriter writer; 533 int is_index; 534 535 if( CV_IS_SEQ( ptseq )) 536 { 537 if( !CV_IS_SEQ_POINT_SET( ptseq )) 538 CV_Error( CV_StsUnsupportedFormat, 539 "Input sequence is not a sequence of points" ); 540 if( !storage ) 541 storage = ptseq->storage; 542 } 543 else 544 { 545 ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block ); 546 } 547 548 if( CV_SEQ_ELTYPE( ptseq ) != CV_32SC2 ) 549 CV_Error( CV_StsUnsupportedFormat, "Floating-point coordinates are not supported here" ); 550 551 if( CV_IS_SEQ( hull )) 552 { 553 int hulltype = CV_SEQ_ELTYPE( hull ); 554 if( hulltype != CV_SEQ_ELTYPE_PPOINT && hulltype != CV_SEQ_ELTYPE_INDEX ) 555 CV_Error( CV_StsUnsupportedFormat, 556 "Convex hull must represented as a sequence " 557 "of indices or sequence of pointers" ); 558 if( !storage ) 559 storage = hull->storage; 560 } 561 else 562 { 563 CvMat* mat = (CvMat*)hull; 564 565 if( !CV_IS_MAT( hull )) 566 CV_Error(CV_StsBadArg, "Convex hull is neither sequence nor matrix"); 567 568 if( (mat->cols != 1 && mat->rows != 1) || 569 !CV_IS_MAT_CONT(mat->type) || CV_MAT_TYPE(mat->type) != CV_32SC1 ) 570 CV_Error( CV_StsBadArg, 571 "The matrix should be 1-dimensional and continuous array of int's" ); 572 573 if( mat->cols + mat->rows - 1 > ptseq->total ) 574 CV_Error( CV_StsBadSize, "Convex hull is larger than the point sequence" ); 575 576 hull = cvMakeSeqHeaderForArray( 577 CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED, 578 sizeof(CvContour), CV_ELEM_SIZE(mat->type), mat->data.ptr, 579 mat->cols + mat->rows - 1, &hull_header, &hullblock ); 580 } 581 582 is_index = CV_SEQ_ELTYPE(hull) == CV_SEQ_ELTYPE_INDEX; 583 584 if( !storage ) 585 CV_Error( CV_StsNullPtr, "NULL storage pointer" ); 586 587 defects = cvCreateSeq( CV_SEQ_KIND_GENERIC, sizeof(CvSeq), sizeof(CvConvexityDefect), storage ); 588 589 if( ptseq->total < 4 || hull->total < 3) 590 { 591 //CV_ERROR( CV_StsBadSize, 592 // "point seq size must be >= 4, convex hull size must be >= 3" ); 593 return defects; 594 } 595 596 /* recognize co-orientation of ptseq and its hull */ 597 { 598 int sign = 0; 599 int index1, index2, index3; 600 601 if( !is_index ) 602 { 603 CvPoint* pos = *CV_SEQ_ELEM( hull, CvPoint*, 0 ); 604 index1 = cvSeqElemIdx( ptseq, pos ); 605 606 pos = *CV_SEQ_ELEM( hull, CvPoint*, 1 ); 607 index2 = cvSeqElemIdx( ptseq, pos ); 608 609 pos = *CV_SEQ_ELEM( hull, CvPoint*, 2 ); 610 index3 = cvSeqElemIdx( ptseq, pos ); 611 } 612 else 613 { 614 index1 = *CV_SEQ_ELEM( hull, int, 0 ); 615 index2 = *CV_SEQ_ELEM( hull, int, 1 ); 616 index3 = *CV_SEQ_ELEM( hull, int, 2 ); 617 } 618 619 sign += (index2 > index1) ? 1 : 0; 620 sign += (index3 > index2) ? 1 : 0; 621 sign += (index1 > index3) ? 1 : 0; 622 623 rev_orientation = (sign == 2) ? 0 : 1; 624 } 625 626 cvStartReadSeq( ptseq, &ptseq_reader, 0 ); 627 cvStartReadSeq( hull, &hull_reader, rev_orientation ); 628 629 if( !is_index ) 630 { 631 hull_cur = *(CvPoint**)hull_reader.prev_elem; 632 index = cvSeqElemIdx( ptseq, (char*)hull_cur, 0 ); 633 } 634 else 635 { 636 index = *(int*)hull_reader.prev_elem; 637 hull_cur = CV_GET_SEQ_ELEM( CvPoint, ptseq, index ); 638 } 639 cvSetSeqReaderPos( &ptseq_reader, index ); 640 cvStartAppendToSeq( defects, &writer ); 641 642 /* cycle through ptseq and hull with computing defects */ 643 for( i = 0; i < hull->total; i++ ) 644 { 645 CvConvexityDefect defect; 646 int is_defect = 0; 647 double dx0, dy0; 648 double depth = 0, scale; 649 CvPoint* hull_next; 650 651 if( !is_index ) 652 hull_next = *(CvPoint**)hull_reader.ptr; 653 else 654 { 655 int t = *(int*)hull_reader.ptr; 656 hull_next = CV_GET_SEQ_ELEM( CvPoint, ptseq, t ); 657 } 658 659 dx0 = (double)hull_next->x - (double)hull_cur->x; 660 dy0 = (double)hull_next->y - (double)hull_cur->y; 661 assert( dx0 != 0 || dy0 != 0 ); 662 scale = 1./std::sqrt(dx0*dx0 + dy0*dy0); 663 664 defect.start = hull_cur; 665 defect.end = hull_next; 666 667 for(;;) 668 { 669 /* go through ptseq to achieve next hull point */ 670 CV_NEXT_SEQ_ELEM( sizeof(CvPoint), ptseq_reader ); 671 672 if( ptseq_reader.ptr == (schar*)hull_next ) 673 break; 674 else 675 { 676 CvPoint* cur = (CvPoint*)ptseq_reader.ptr; 677 678 /* compute distance from current point to hull edge */ 679 double dx = (double)cur->x - (double)hull_cur->x; 680 double dy = (double)cur->y - (double)hull_cur->y; 681 682 /* compute depth */ 683 double dist = fabs(-dy0*dx + dx0*dy) * scale; 684 685 if( dist > depth ) 686 { 687 depth = dist; 688 defect.depth_point = cur; 689 defect.depth = (float)depth; 690 is_defect = 1; 691 } 692 } 693 } 694 if( is_defect ) 695 { 696 CV_WRITE_SEQ_ELEM( defect, writer ); 697 } 698 699 hull_cur = hull_next; 700 if( rev_orientation ) 701 { 702 CV_PREV_SEQ_ELEM( hull->elem_size, hull_reader ); 703 } 704 else 705 { 706 CV_NEXT_SEQ_ELEM( hull->elem_size, hull_reader ); 707 } 708 } 709 710 return cvEndWriteSeq( &writer ); 711 } 712 713 714 CV_IMPL int 715 cvCheckContourConvexity( const CvArr* array ) 716 { 717 CvContour contour_header; 718 CvSeqBlock block; 719 CvSeq* contour = (CvSeq*)array; 720 721 if( CV_IS_SEQ(contour) ) 722 { 723 if( !CV_IS_SEQ_POINT_SET(contour)) 724 CV_Error( CV_StsUnsupportedFormat, 725 "Input sequence must be polygon (closed 2d curve)" ); 726 } 727 else 728 { 729 contour = cvPointSeqFromMat(CV_SEQ_KIND_CURVE| 730 CV_SEQ_FLAG_CLOSED, array, &contour_header, &block ); 731 } 732 733 if( contour->total == 0 ) 734 return -1; 735 736 cv::AutoBuffer<double> _buf; 737 return cv::isContourConvex(cv::cvarrToMat(contour, false, false, 0, &_buf)) ? 1 : 0; 738 } 739 740 /* End of file. */ 741
