modules/imgproc/src/convhull.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 "precomp.hpp"
  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     int i, incr = start < end ? 1 : -1;
 203     int idx, first_idx = ptseq->first->start_index;
 204
 205     for( i = start; i != end; i += incr )
 206     {
 207         CvPoint* ptr = (CvPoint*)pointer[stack[i]];
 208         CvSeqBlock* block = ptseq->first;
 209         while( (unsigned)(idx = (int)(ptr - (CvPoint*)block->data)) >= (unsigned)block->count )
 210         {
 211             block = block->next;
 212             if( block == ptseq->first )
 213                 CV_Error( CV_StsError, "Internal error" );
 214         }
 215         idx += block->start_index - first_idx;
 216         CV_WRITE_SEQ_ELEM( idx, *writer );
 217     }
 218 }
 219
 220
 221 CV_IMPL CvSeq*
 222 cvConvexHull2( const CvArr* array, void* hull_storage,
 223                int orientation, int return_points )
 224 {
 225     union { CvContour* c; CvSeq* s; } hull;
 226     cv::AutoBuffer<CvPoint*> _pointer;
 227     CvPoint** pointer;
 228     CvPoint2D32f** pointerf = 0;
 229     cv::AutoBuffer<int> _stack;
 230     int* stack;
 231
 232     hull.s = 0;
 233
 234     CvMat* mat = 0;
 235     CvSeqReader reader;
 236     CvSeqWriter writer;
 237     CvContour contour_header;
 238     union { CvContour c; CvSeq s; } hull_header;
 239     CvSeqBlock block, hullblock;
 240     CvSeq* ptseq = 0;
 241     CvSeq* hullseq = 0;
 242     int is_float;
 243     int* t_stack;
 244     int t_count;
 245     int i, miny_ind = 0, maxy_ind = 0, total;
 246     int hulltype;
 247     int stop_idx;
 248     sklansky_func sklansky;
 249
 250     if( CV_IS_SEQ( array ))
 251     {
 252         ptseq = (CvSeq*)array;
 253         if( !CV_IS_SEQ_POINT_SET( ptseq ))
 254             CV_Error( CV_StsBadArg, "Unsupported sequence type" );
 255         if( hull_storage == 0 )
 256             hull_storage = ptseq->storage;
 257     }
 258     else
 259     {
 260         ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );
 261     }
 262
 263     if( CV_IS_STORAGE( hull_storage ))
 264     {
 265         if( return_points )
 266         {
 267             hullseq = cvCreateSeq(
 268                 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE(ptseq)|
 269                 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,
 270                 sizeof(CvContour), sizeof(CvPoint),(CvMemStorage*)hull_storage );
 271         }
 272         else
 273         {
 274             hullseq = cvCreateSeq(
 275                 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_PPOINT|
 276                 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,
 277                 sizeof(CvContour), sizeof(CvPoint*), (CvMemStorage*)hull_storage );
 278         }
 279     }
 280     else
 281     {
 282         if( !CV_IS_MAT( hull_storage ))
 283             CV_Error(CV_StsBadArg, "Destination must be valid memory storage or matrix");
 284
 285         mat = (CvMat*)hull_storage;
 286
 287         if( (mat->cols != 1 && mat->rows != 1) || !CV_IS_MAT_CONT(mat->type))
 288             CV_Error( CV_StsBadArg,
 289             "The hull matrix should be continuous and have a single row or a single column" );
 290
 291         if( mat->cols + mat->rows - 1 < ptseq->total )
 292             CV_Error( CV_StsBadSize, "The hull matrix size might be not enough to fit the hull" );
 293
 294         if( CV_MAT_TYPE(mat->type) != CV_SEQ_ELTYPE(ptseq) &&
 295             CV_MAT_TYPE(mat->type) != CV_32SC1 )
 296             CV_Error( CV_StsUnsupportedFormat,
 297             "The hull matrix must have the same type as input or 32sC1 (integers)" );
 298
 299         hullseq = cvMakeSeqHeaderForArray(
 300             CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
 301             sizeof(contour_header), CV_ELEM_SIZE(mat->type), mat->data.ptr,
 302             mat->cols + mat->rows - 1, &hull_header.s, &hullblock );
 303
 304         cvClearSeq( hullseq );
 305     }
 306
 307     total = ptseq->total;
 308     if( total == 0 )
 309     {
 310         if( mat )
 311             CV_Error( CV_StsBadSize,
 312             "Point sequence can not be empty if the output is matrix" );
 313         return hull.s;
 314     }
 315
 316     cvStartAppendToSeq( hullseq, &writer );
 317
 318     is_float = CV_SEQ_ELTYPE(ptseq) == CV_32FC2;
 319     hulltype = CV_SEQ_ELTYPE(hullseq);
 320     sklansky = !is_float ? (sklansky_func)icvSklansky_32s :
 321                            (sklansky_func)icvSklansky_32f;
 322
 323     _pointer.allocate( ptseq->total );
 324     _stack.allocate( ptseq->total + 2);
 325     pointer = _pointer;
 326     pointerf = (CvPoint2D32f**)pointer;
 327     stack = _stack;
 328
 329     cvStartReadSeq( ptseq, &reader );
 330
 331     for( i = 0; i < total; i++ )
 332     {
 333         pointer[i] = (CvPoint*)reader.ptr;
 334         CV_NEXT_SEQ_ELEM( ptseq->elem_size, reader );
 335     }
 336
 337     // sort the point set by x-coordinate, find min and max y
 338     if( !is_float )
 339     {
 340         icvSortPointsByPointers_32s( pointer, total, 0 );
 341         for( i = 1; i < total; i++ )
 342         {
 343             int y = pointer[i]->y;
 344             if( pointer[miny_ind]->y > y )
 345                 miny_ind = i;
 346             if( pointer[maxy_ind]->y < y )
 347                 maxy_ind = i;
 348         }
 349     }
 350     else
 351     {
 352         icvSortPointsByPointers_32f( pointerf, total, 0 );
 353         for( i = 1; i < total; i++ )
 354         {
 355             float y = pointerf[i]->y;
 356             if( pointerf[miny_ind]->y > y )
 357                 miny_ind = i;
 358             if( pointerf[maxy_ind]->y < y )
 359                 maxy_ind = i;
 360         }
 361     }
 362
 363     if( pointer[0]->x == pointer[total-1]->x &&
 364         pointer[0]->y == pointer[total-1]->y )
 365     {
 366         if( hulltype == CV_SEQ_ELTYPE_PPOINT )
 367         {
 368             CV_WRITE_SEQ_ELEM( pointer[0], writer );
 369         }
 370         else if( hulltype == CV_SEQ_ELTYPE_INDEX )
 371         {
 372             int index = 0;
 373             CV_WRITE_SEQ_ELEM( index, writer );
 374         }
 375         else
 376         {
 377             CvPoint pt = pointer[0][0];
 378             CV_WRITE_SEQ_ELEM( pt, writer );
 379         }
 380         goto finish_hull;
 381     }
 382
 383     /*upper half */
 384     {
 385         int *tl_stack = stack;
 386         int tl_count = sklansky( pointer, 0, maxy_ind, tl_stack, -1, 1 );
 387         int *tr_stack = tl_stack + tl_count;
 388         int tr_count = sklansky( pointer, ptseq->total - 1, maxy_ind, tr_stack, -1, -1 );
 389
 390         /* gather upper part of convex hull to output */
 391         if( orientation == CV_COUNTER_CLOCKWISE )
 392         {
 393             CV_SWAP( tl_stack, tr_stack, t_stack );
 394             CV_SWAP( tl_count, tr_count, t_count );
 395         }
 396
 397         if( hulltype == CV_SEQ_ELTYPE_PPOINT )
 398         {
 399             for( i = 0; i < tl_count - 1; i++ )
 400                 CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]], writer );
 401
 402             for( i = tr_count - 1; i > 0; i-- )
 403                 CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]], writer );
 404         }
 405         else if( hulltype == CV_SEQ_ELTYPE_INDEX )
 406         {
 407             icvCalcAndWritePtIndices( pointer, tl_stack, 0, tl_count-1, ptseq, &writer );
 408             icvCalcAndWritePtIndices( pointer, tr_stack, tr_count-1, 0, ptseq, &writer );
 409         }
 410         else
 411         {
 412             for( i = 0; i < tl_count - 1; i++ )
 413                 CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]][0], writer );
 414
 415             for( i = tr_count - 1; i > 0; i-- )
 416                 CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]][0], writer );
 417         }
 418         stop_idx = tr_count > 2 ? tr_stack[1] : tl_count > 2 ? tl_stack[tl_count - 2] : -1;
 419     }
 420
 421     /* lower half */
 422     {
 423         int *bl_stack = stack;
 424         int bl_count = sklansky( pointer, 0, miny_ind, bl_stack, 1, -1 );
 425         int *br_stack = stack + bl_count;
 426         int br_count = sklansky( pointer, ptseq->total - 1, miny_ind, br_stack, 1, 1 );
 427
 428         if( orientation != CV_COUNTER_CLOCKWISE )
 429         {
 430             CV_SWAP( bl_stack, br_stack, t_stack );
 431             CV_SWAP( bl_count, br_count, t_count );
 432         }
 433
 434         if( stop_idx >= 0 )
 435         {
 436             int check_idx = bl_count > 2 ? bl_stack[1] :
 437                             bl_count + br_count > 2 ? br_stack[2-bl_count] : -1;
 438             if( check_idx == stop_idx || (check_idx >= 0 &&
 439                 pointer[check_idx]->x == pointer[stop_idx]->x &&
 440                 pointer[check_idx]->y == pointer[stop_idx]->y) )
 441             {
 442                 /* if all the points lie on the same line, then
 443                    the bottom part of the convex hull is the mirrored top part
 444                    (except the exteme points).*/
 445                 bl_count = MIN( bl_count, 2 );
 446                 br_count = MIN( br_count, 2 );
 447             }
 448         }
 449
 450         if( hulltype == CV_SEQ_ELTYPE_PPOINT )
 451         {
 452             for( i = 0; i < bl_count - 1; i++ )
 453                 CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]], writer );
 454
 455             for( i = br_count - 1; i > 0; i-- )
 456                 CV_WRITE_SEQ_ELEM( pointer[br_stack[i]], writer );
 457         }
 458         else if( hulltype == CV_SEQ_ELTYPE_INDEX )
 459         {
 460             icvCalcAndWritePtIndices( pointer, bl_stack, 0, bl_count-1, ptseq, &writer );
 461             icvCalcAndWritePtIndices( pointer, br_stack, br_count-1, 0, ptseq, &writer );
 462         }
 463         else
 464         {
 465             for( i = 0; i < bl_count - 1; i++ )
 466                 CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]][0], writer );
 467
 468             for( i = br_count - 1; i > 0; i-- )
 469                 CV_WRITE_SEQ_ELEM( pointer[br_stack[i]][0], writer );
 470         }
 471     }
 472
 473 finish_hull:
 474     cvEndWriteSeq( &writer );
 475
 476     if( mat )
 477     {
 478         if( mat->rows > mat->cols )
 479             mat->rows = hullseq->total;
 480         else
 481             mat->cols = hullseq->total;
 482     }
 483     else
 484     {
 485         hull.s = hullseq;
 486         hull.c->rect = cvBoundingRect( ptseq,
 487             ptseq->header_size < (int)sizeof(CvContour) ||
 488             &ptseq->flags == &contour_header.flags );
 489
 490         /*if( ptseq != (CvSeq*)&contour_header )
 491             hullseq->v_prev = ptseq;*/
 492     }
 493
 494     return hull.s;
 495 }
 496
 497
 498 /* contour must be a simple polygon */
 499 /* it must have more than 3 points  */
 500 CV_IMPL CvSeq* cvConvexityDefects( const CvArr* array,
 501                                    const CvArr* hullarray,
 502                                    CvMemStorage* storage )
 503 {
 504     CvSeq* defects = 0;
 505
 506     int i, index;
 507     CvPoint* hull_cur;
 508
 509     /* is orientation of hull different from contour one */
 510     int rev_orientation;
 511
 512     CvContour contour_header;
 513     union { CvContour c; CvSeq s; } hull_header;
 514     CvSeqBlock block, hullblock;
 515     CvSeq *ptseq = (CvSeq*)array, *hull = (CvSeq*)hullarray;
 516
 517     CvSeqReader hull_reader;
 518     CvSeqReader ptseq_reader;
 519     CvSeqWriter writer;
 520     int is_index;
 521
 522     if( CV_IS_SEQ( ptseq ))
 523     {
 524         if( !CV_IS_SEQ_POINT_SET( ptseq ))
 525             CV_Error( CV_StsUnsupportedFormat,
 526                 "Input sequence is not a sequence of points" );
 527         if( !storage )
 528             storage = ptseq->storage;
 529     }
 530     else
 531     {
 532         ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );
 533     }
 534
 535     if( CV_SEQ_ELTYPE( ptseq ) != CV_32SC2 )
 536         CV_Error( CV_StsUnsupportedFormat, "Floating-point coordinates are not supported here" );
 537
 538     if( CV_IS_SEQ( hull ))
 539     {
 540         int hulltype = CV_SEQ_ELTYPE( hull );
 541         if( hulltype != CV_SEQ_ELTYPE_PPOINT && hulltype != CV_SEQ_ELTYPE_INDEX )
 542             CV_Error( CV_StsUnsupportedFormat,
 543                 "Convex hull must represented as a sequence "
 544                 "of indices or sequence of pointers" );
 545         if( !storage )
 546             storage = hull->storage;
 547     }
 548     else
 549     {
 550         CvMat* mat = (CvMat*)hull;
 551
 552         if( !CV_IS_MAT( hull ))
 553             CV_Error(CV_StsBadArg, "Convex hull is neither sequence nor matrix");
 554
 555         if( (mat->cols != 1 && mat->rows != 1) ||
 556             !CV_IS_MAT_CONT(mat->type) || CV_MAT_TYPE(mat->type) != CV_32SC1 )
 557             CV_Error( CV_StsBadArg,
 558             "The matrix should be 1-dimensional and continuous array of int's" );
 559
 560         if( mat->cols + mat->rows - 1 > ptseq->total )
 561             CV_Error( CV_StsBadSize, "Convex hull is larger than the point sequence" );
 562
 563         hull = cvMakeSeqHeaderForArray(
 564             CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
 565             sizeof(CvContour), CV_ELEM_SIZE(mat->type), mat->data.ptr,
 566             mat->cols + mat->rows - 1, &hull_header.s, &hullblock );
 567     }
 568
 569     is_index = CV_SEQ_ELTYPE(hull) == CV_SEQ_ELTYPE_INDEX;
 570
 571     if( !storage )
 572         CV_Error( CV_StsNullPtr, "NULL storage pointer" );
 573
 574     defects = cvCreateSeq( CV_SEQ_KIND_GENERIC, sizeof(CvSeq), sizeof(CvConvexityDefect), storage );
 575
 576     if( ptseq->total < 4 || hull->total < 3)
 577     {
 578         //CV_ERROR( CV_StsBadSize,
 579         //    "point seq size must be >= 4, convex hull size must be >= 3" );
 580         return defects;
 581     }
 582
 583     /* recognize co-orientation of ptseq and its hull */
 584     {
 585         int sign = 0;
 586         int index1, index2, index3;
 587
 588         if( !is_index )
 589         {
 590             CvPoint* pos = *CV_SEQ_ELEM( hull, CvPoint*, 0 );
 591             index1 = cvSeqElemIdx( ptseq, pos );
 592
 593             pos = *CV_SEQ_ELEM( hull, CvPoint*, 1 );
 594             index2 = cvSeqElemIdx( ptseq, pos );
 595
 596             pos = *CV_SEQ_ELEM( hull, CvPoint*, 2 );
 597             index3 = cvSeqElemIdx( ptseq, pos );
 598         }
 599         else
 600         {
 601             index1 = *CV_SEQ_ELEM( hull, int, 0 );
 602             index2 = *CV_SEQ_ELEM( hull, int, 1 );
 603             index3 = *CV_SEQ_ELEM( hull, int, 2 );
 604         }
 605
 606         sign += (index2 > index1) ? 1 : 0;
 607         sign += (index3 > index2) ? 1 : 0;
 608         sign += (index1 > index3) ? 1 : 0;
 609
 610         rev_orientation = (sign == 2) ? 0 : 1;
 611     }
 612
 613     cvStartReadSeq( ptseq, &ptseq_reader, 0 );
 614     cvStartReadSeq( hull, &hull_reader, rev_orientation );
 615
 616     if( !is_index )
 617     {
 618         hull_cur = *(CvPoint**)hull_reader.prev_elem;
 619         index = cvSeqElemIdx( ptseq, (char*)hull_cur, 0 );
 620     }
 621     else
 622     {
 623         index = *(int*)hull_reader.prev_elem;
 624         hull_cur = CV_GET_SEQ_ELEM( CvPoint, ptseq, index );
 625     }
 626     cvSetSeqReaderPos( &ptseq_reader, index );
 627     cvStartAppendToSeq( defects, &writer );
 628
 629     /* cycle through ptseq and hull with computing defects */
 630     for( i = 0; i < hull->total; i++ )
 631     {
 632         CvConvexityDefect defect;
 633         int is_defect = 0;
 634         double dx0, dy0;
 635         double depth = 0, scale;
 636         CvPoint* hull_next;
 637
 638         if( !is_index )
 639             hull_next = *(CvPoint**)hull_reader.ptr;
 640         else
 641         {
 642             int t = *(int*)hull_reader.ptr;
 643             hull_next = CV_GET_SEQ_ELEM( CvPoint, ptseq, t );
 644         }
 645
 646         dx0 = (double)hull_next->x - (double)hull_cur->x;
 647         dy0 = (double)hull_next->y - (double)hull_cur->y;
 648         assert( dx0 != 0 || dy0 != 0 );
 649         scale = 1./sqrt(dx0*dx0 + dy0*dy0);
 650
 651         defect.start = hull_cur;
 652         defect.end = hull_next;
 653
 654         for(;;)
 655         {
 656             /* go through ptseq to achieve next hull point */
 657             CV_NEXT_SEQ_ELEM( sizeof(CvPoint), ptseq_reader );
 658
 659             if( ptseq_reader.ptr == (schar*)hull_next )
 660                 break;
 661             else
 662             {
 663                 CvPoint* cur = (CvPoint*)ptseq_reader.ptr;
 664
 665                 /* compute distance from current point to hull edge */
 666                 double dx = (double)cur->x - (double)hull_cur->x;
 667                 double dy = (double)cur->y - (double)hull_cur->y;
 668
 669                 /* compute depth */
 670                 double dist = fabs(-dy0*dx + dx0*dy) * scale;
 671
 672                 if( dist > depth )
 673                 {
 674                     depth = dist;
 675                     defect.depth_point = cur;
 676                     defect.depth = (float)depth;
 677                     is_defect = 1;
 678                 }
 679             }
 680         }
 681         if( is_defect )
 682         {
 683             CV_WRITE_SEQ_ELEM( defect, writer );
 684         }
 685
 686         hull_cur = hull_next;
 687         if( rev_orientation )
 688         {
 689             CV_PREV_SEQ_ELEM( hull->elem_size, hull_reader );
 690         }
 691         else
 692         {
 693             CV_NEXT_SEQ_ELEM( hull->elem_size, hull_reader );
 694         }
 695     }
 696
 697     return cvEndWriteSeq( &writer );
 698 }
 699
 700
 701 CV_IMPL int
 702 cvCheckContourConvexity( const CvArr* array )
 703 {
 704     int flag = -1;
 705
 706     int i;
 707     int orientation = 0;
 708     CvSeqReader reader;
 709     CvContour contour_header;
 710     CvSeqBlock block;
 711     CvSeq* contour = (CvSeq*)array;
 712
 713     if( CV_IS_SEQ(contour) )
 714     {
 715         if( !CV_IS_SEQ_POINT_SET(contour))
 716             CV_Error( CV_StsUnsupportedFormat,
 717                 "Input sequence must be polygon (closed 2d curve)" );
 718     }
 719     else
 720     {
 721         contour = cvPointSeqFromMat(CV_SEQ_KIND_CURVE|CV_SEQ_FLAG_CLOSED, array, &contour_header, &block );
 722     }
 723
 724     if( contour->total == 0 )
 725         return -1;
 726
 727     cvStartReadSeq( contour, &reader, 0 );
 728     flag = 1;
 729
 730     if( CV_SEQ_ELTYPE( contour ) == CV_32SC2 )
 731     {
 732         CvPoint *prev_pt = (CvPoint*)reader.prev_elem;
 733         CvPoint *cur_pt = (CvPoint*)reader.ptr;
 734
 735         int dx0 = cur_pt->x - prev_pt->x;
 736         int dy0 = cur_pt->y - prev_pt->y;
 737
 738         for( i = 0; i < contour->total; i++ )
 739         {
 740             int dxdy0, dydx0;
 741             int dx, dy;
 742
 743             /*int orient; */
 744             CV_NEXT_SEQ_ELEM( sizeof(CvPoint), reader );
 745             prev_pt = cur_pt;
 746             cur_pt = (CvPoint *) reader.ptr;
 747
 748             dx = cur_pt->x - prev_pt->x;
 749             dy = cur_pt->y - prev_pt->y;
 750             dxdy0 = dx * dy0;
 751             dydx0 = dy * dx0;
 752
 753             /* find orientation */
 754             /*orient = -dy0 * dx + dx0 * dy;
 755                orientation |= (orient > 0) ? 1 : 2;
 756              */
 757             orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);
 758
 759             if( orientation == 3 )
 760             {
 761                 flag = 0;
 762                 break;
 763             }
 764
 765             dx0 = dx;
 766             dy0 = dy;
 767         }
 768     }
 769     else
 770     {
 771         CV_Assert( CV_SEQ_ELTYPE(contour) == CV_32FC2 );
 772
 773         CvPoint2D32f *prev_pt = (CvPoint2D32f*)reader.prev_elem;
 774         CvPoint2D32f *cur_pt = (CvPoint2D32f*)reader.ptr;
 775
 776         float dx0 = cur_pt->x - prev_pt->x;
 777         float dy0 = cur_pt->y - prev_pt->y;
 778
 779         for( i = 0; i < contour->total; i++ )
 780         {
 781             float dxdy0, dydx0;
 782             float dx, dy;
 783
 784             /*int orient; */
 785             CV_NEXT_SEQ_ELEM( sizeof(CvPoint2D32f), reader );
 786             prev_pt = cur_pt;
 787             cur_pt = (CvPoint2D32f*) reader.ptr;
 788
 789             dx = cur_pt->x - prev_pt->x;
 790             dy = cur_pt->y - prev_pt->y;
 791             dxdy0 = dx * dy0;
 792             dydx0 = dy * dx0;
 793
 794             /* find orientation */
 795             /*orient = -dy0 * dx + dx0 * dy;
 796                orientation |= (orient > 0) ? 1 : 2;
 797              */
 798             orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);
 799
 800             if( orientation == 3 )
 801             {
 802                 flag = 0;
 803                 break;
 804             }
 805
 806             dx0 = dx;
 807             dy0 = dy;
 808         }
 809     }
 810
 811     return flag;
 812 }
 813
 814
 815 /* End of file. */