git.maemo.org Git - opencv/blob - cv/src/cvconvhull.cpp

   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
  44 static int
  45 icvSklansky_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
 117 static int
 118 icvSklansky_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
 190 typedef 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)
 195 static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32s, CvPoint*, cmp_pts )
 196 static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32f, CvPoint2D32f*, cmp_pts )
 197
 198 static void
 199 icvCalcAndWritePtIndices( 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
 227 CV_IMPL CvSeq*
 228 cvConvexHull2( 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
 484 finish_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  */
 516 CV_IMPL CvSeq*
 517 cvConvexityDefects( 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
 729 CV_IMPL int
 730 cvCheckContourConvexity( 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. */