vcs.maemo.org Git - opencv/blob - src/cv/cvcontourtree.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 #include "_cv.h"
  42
  43 #define CV_MATCH_CHECK( status, cvFun )                                    \
  44   {                                                                        \
  45     status = cvFun;                                                        \
  46     if( status != CV_OK )                                                  \
  47      goto M_END;                                                           \
  48   }
  49
  50 static CvStatus
  51 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1,
  52                 CvPoint t3, int n3, double *s, double *s_c,
  53                 double *h, double *a, double *b );
  54
  55 /*F///////////////////////////////////////////////////////////////////////////////////////
  56 //    Name: icvCreateContourTree
  57 //    Purpose:
  58 //    Create binary tree representation for the contour
  59 //    Context:
  60 //    Parameters:
  61 //      contour - pointer to input contour object.
  62 //      storage - pointer to the current storage block
  63 //      tree   -  output pointer to the binary tree representation
  64 //      threshold - threshold for the binary tree building
  65 //
  66 //F*/
  67 static CvStatus
  68 icvCreateContourTree( const CvSeq * contour, CvMemStorage * storage,
  69                       CvContourTree ** tree, double threshold )
  70 {
  71     CvPoint *pt_p;              /*  pointer to previos points   */
  72     CvPoint *pt_n;              /*  pointer to next points      */
  73     CvPoint *pt1, *pt2;         /*  pointer to current points   */
  74
  75     CvPoint t, tp1, tp2, tp3, tn1, tn2, tn3;
  76     int lpt, flag, i, j, i_tree, j_1, j_3, i_buf;
  77     double s, sp1, sp2, sn1, sn2, s_c, sp1_c, sp2_c, sn1_c, sn2_c, h, hp1, hp2, hn1, hn2,
  78         a, ap1, ap2, an1, an2, b, bp1, bp2, bn1, bn2;
  79     double a_s_c, a_sp1_c;
  80
  81     _CvTrianAttr **ptr_p, **ptr_n, **ptr1, **ptr2;      /*  pointers to pointers of triangles  */
  82     _CvTrianAttr *cur_adr;
  83
  84     int *num_p, *num_n, *num1, *num2;   /*   numbers of input contour points   */
  85     int nm, nmp1, nmp2, nmp3, nmn1, nmn2, nmn3;
  86     int seq_flags = 1, i_end, prev_null, prev2_null;
  87     double koef = 1.5;
  88     double eps = 1.e-7;
  89     double e;
  90     CvStatus status;
  91     int hearder_size;
  92     _CvTrianAttr tree_one, tree_two, *tree_end, *tree_root;
  93
  94     CvSeqWriter writer;
  95
  96     assert( contour != NULL && contour->total >= 4 );
  97     status = CV_OK;
  98
  99     if( contour == NULL )
 100         return CV_NULLPTR_ERR;
 101     if( contour->total < 4 )
 102         return CV_BADSIZE_ERR;
 103
 104     if( !CV_IS_SEQ_POINT_SET( contour ))
 105         return CV_BADFLAG_ERR;
 106
 107
 108 /*   Convert Sequence to array    */
 109     lpt = contour->total;
 110     pt_p = pt_n = NULL;
 111     num_p = num_n = NULL;
 112     ptr_p = ptr_n = ptr1 = ptr2 = NULL;
 113     tree_end = NULL;
 114
 115     pt_p = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
 116     pt_n = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint ));
 117
 118     num_p = (int *) cvAlloc( lpt * sizeof( int ));
 119     num_n = (int *) cvAlloc( lpt * sizeof( int ));
 120
 121     hearder_size = sizeof( CvContourTree );
 122     seq_flags = CV_SEQ_POLYGON_TREE;
 123     cvStartWriteSeq( seq_flags, hearder_size, sizeof( _CvTrianAttr ), storage, &writer );
 124
 125     ptr_p = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
 126     ptr_n = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
 127
 128     memset( ptr_p, 0, lpt * sizeof( _CvTrianAttr * ));
 129     memset( ptr_n, 0, lpt * sizeof( _CvTrianAttr * ));
 130
 131     if( pt_p == NULL || pt_n == NULL )
 132         return CV_OUTOFMEM_ERR;
 133     if( ptr_p == NULL || ptr_n == NULL )
 134         return CV_OUTOFMEM_ERR;
 135
 136 /*     write fild for the binary tree root   */
 137 /*  start_writer = writer;   */
 138
 139     tree_one.pt.x = tree_one.pt.y = 0;
 140     tree_one.sign = 0;
 141     tree_one.area = 0;
 142     tree_one.r1 = tree_one.r2 = 0;
 143     tree_one.next_v1 = tree_one.next_v2 = tree_one.prev_v = NULL;
 144
 145     CV_WRITE_SEQ_ELEM( tree_one, writer );
 146     tree_root = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 147
 148     if( cvCvtSeqToArray( contour, (char *) pt_p ) == (char *) contour )
 149         return CV_BADPOINT_ERR;
 150
 151     for( i = 0; i < lpt; i++ )
 152         num_p[i] = i;
 153
 154     i = lpt;
 155     flag = 0;
 156     i_tree = 0;
 157     e = 20.;                    /*  initial threshold value   */
 158     ptr1 = ptr_p;
 159     ptr2 = ptr_n;
 160     pt1 = pt_p;
 161     pt2 = pt_n;
 162     num1 = num_p;
 163     num2 = num_n;
 164 /*  binary tree constraction    */
 165     while( i > 4 )
 166     {
 167         if( flag == 0 )
 168         {
 169             ptr1 = ptr_p;
 170             ptr2 = ptr_n;
 171             pt1 = pt_p;
 172             pt2 = pt_n;
 173             num1 = num_p;
 174             num2 = num_n;
 175             flag = 1;
 176         }
 177         else
 178         {
 179             ptr1 = ptr_n;
 180             ptr2 = ptr_p;
 181             pt1 = pt_n;
 182             pt2 = pt_p;
 183             num1 = num_n;
 184             num2 = num_p;
 185             flag = 0;
 186         }
 187         t = pt1[0];
 188         nm = num1[0];
 189         tp1 = pt1[i - 1];
 190         nmp1 = num1[i - 1];
 191         tp2 = pt1[i - 2];
 192         nmp2 = num1[i - 2];
 193         tp3 = pt1[i - 3];
 194         nmp3 = num1[i - 3];
 195         tn1 = pt1[1];
 196         nmn1 = num1[1];
 197         tn2 = pt1[2];
 198         nmn2 = num1[2];
 199
 200         i_buf = 0;
 201         i_end = -1;
 202         CV_MATCH_CHECK( status,
 203                         icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a,
 204                                         &b ));
 205         CV_MATCH_CHECK( status,
 206                         icvCalcTriAttr( contour, tp1, tp2, nmp2, t, nm, &sp1, &sp1_c, &hp1,
 207                                         &ap1, &bp1 ));
 208         CV_MATCH_CHECK( status,
 209                         icvCalcTriAttr( contour, tp2, tp3, nmp3, tp1, nmp1, &sp2, &sp2_c, &hp2,
 210                                         &ap2, &bp2 ));
 211         CV_MATCH_CHECK( status,
 212                         icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1,
 213                                         &an1, &bn1 ));
 214
 215
 216         j_3 = 3;
 217         prev_null = prev2_null = 0;
 218         for( j = 0; j < i; j++ )
 219         {
 220             tn3 = pt1[j_3];
 221             nmn3 = num1[j_3];
 222             if( j == 0 )
 223                 j_1 = i - 1;
 224             else
 225                 j_1 = j - 1;
 226
 227             CV_MATCH_CHECK( status, icvCalcTriAttr( contour, tn2, tn1, nmn1, tn3, nmn3,
 228                                                     &sn2, &sn2_c, &hn2, &an2, &bn2 ));
 229
 230             if( (s_c < sp1_c && s_c < sp2_c && s_c <= sn1_c && s_c <= sn2_c && s_c < e) ||
 231                 (((s_c == sp1_c && s_c <= sp2_c) || (s_c == sp2_c && s_c <= sp1_c)) &&
 232                 s_c <= sn1_c && s_c <= sn2_c && s_c < e && j > 1 && prev2_null == 0) ||
 233                 (s_c < eps && j > 0 && prev_null == 0) )
 234             {
 235                 prev_null = prev2_null = 1;
 236                 if( s_c < threshold )
 237                 {
 238                     if( ptr1[j_1] == NULL && ptr1[j] == NULL )
 239                     {
 240                         if( i_buf > 0 )
 241                             ptr2[i_buf - 1] = NULL;
 242                         else
 243                             i_end = 0;
 244                     }
 245                     else
 246                     {
 247 /*   form next vertex  */
 248                         tree_one.pt = t;
 249                         tree_one.sign = (char) (CV_SIGN( s ));
 250                         tree_one.r1 = h / a;
 251                         tree_one.r2 = b / a;
 252                         tree_one.area = fabs( s );
 253                         tree_one.next_v1 = ptr1[j_1];
 254                         tree_one.next_v2 = ptr1[j];
 255
 256                         CV_WRITE_SEQ_ELEM( tree_one, writer );
 257                         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 258
 259                         if( ptr1[j_1] != NULL )
 260                             ptr1[j_1]->prev_v = cur_adr;
 261                         if( ptr1[j] != NULL )
 262                             ptr1[j]->prev_v = cur_adr;
 263
 264                         if( i_buf > 0 )
 265                             ptr2[i_buf - 1] = cur_adr;
 266                         else
 267                         {
 268                             tree_end = (_CvTrianAttr *) writer.ptr;
 269                             i_end = 1;
 270                         }
 271                         i_tree++;
 272                     }
 273                 }
 274                 else
 275 /*   form next vertex    */
 276                 {
 277                     tree_one.pt = t;
 278                     tree_one.sign = (char) (CV_SIGN( s ));
 279                     tree_one.area = fabs( s );
 280                     tree_one.r1 = h / a;
 281                     tree_one.r2 = b / a;
 282                     tree_one.next_v1 = ptr1[j_1];
 283                     tree_one.next_v2 = ptr1[j];
 284
 285                     CV_WRITE_SEQ_ELEM( tree_one, writer );
 286                     cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 287
 288                     if( ptr1[j_1] != NULL )
 289                         ptr1[j_1]->prev_v = cur_adr;
 290                     if( ptr1[j] != NULL )
 291                         ptr1[j]->prev_v = cur_adr;
 292
 293                     if( i_buf > 0 )
 294                         ptr2[i_buf - 1] = cur_adr;
 295                     else
 296                     {
 297                         tree_end = cur_adr;
 298                         i_end = 1;
 299                     }
 300                     i_tree++;
 301                 }
 302             }
 303             else
 304 /*   the current triangle is'not LMIAT    */
 305             {
 306                 prev_null = 0;
 307                 switch (prev2_null)
 308                 {
 309                 case 0:
 310                     break;
 311                 case 1:
 312                     {
 313                         prev2_null = 2;
 314                         break;
 315                     }
 316                 case 2:
 317                     {
 318                         prev2_null = 0;
 319                         break;
 320                     }
 321                 }
 322                 if( j != i - 1 || i_end == -1 )
 323                     ptr2[i_buf] = ptr1[j];
 324                 else if( i_end == 0 )
 325                     ptr2[i_buf] = NULL;
 326                 else
 327                     ptr2[i_buf] = tree_end;
 328                 pt2[i_buf] = t;
 329                 num2[i_buf] = num1[j];
 330                 i_buf++;
 331             }
 332 /*    go to next vertex    */
 333             tp3 = tp2;
 334             tp2 = tp1;
 335             tp1 = t;
 336             t = tn1;
 337             tn1 = tn2;
 338             tn2 = tn3;
 339             nmp3 = nmp2;
 340             nmp2 = nmp1;
 341             nmp1 = nm;
 342             nm = nmn1;
 343             nmn1 = nmn2;
 344             nmn2 = nmn3;
 345
 346             sp2 = sp1;
 347             sp1 = s;
 348             s = sn1;
 349             sn1 = sn2;
 350             sp2_c = sp1_c;
 351             sp1_c = s_c;
 352             s_c = sn1_c;
 353             sn1_c = sn2_c;
 354
 355             ap2 = ap1;
 356             ap1 = a;
 357             a = an1;
 358             an1 = an2;
 359             bp2 = bp1;
 360             bp1 = b;
 361             b = bn1;
 362             bn1 = bn2;
 363             hp2 = hp1;
 364             hp1 = h;
 365             h = hn1;
 366             hn1 = hn2;
 367             j_3++;
 368             if( j_3 >= i )
 369                 j_3 = 0;
 370         }
 371
 372         i = i_buf;
 373         e = e * koef;
 374     }
 375
 376 /*  constract tree root  */
 377     if( i != 4 )
 378         return CV_BADFACTOR_ERR;
 379
 380     t = pt2[0];
 381     tn1 = pt2[1];
 382     tn2 = pt2[2];
 383     tp1 = pt2[3];
 384     nm = num2[0];
 385     nmn1 = num2[1];
 386     nmn2 = num2[2];
 387     nmp1 = num2[3];
 388 /*   first pair of the triangles   */
 389     CV_MATCH_CHECK( status,
 390                     icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, &b ));
 391     CV_MATCH_CHECK( status,
 392                     icvCalcTriAttr( contour, tn2, tn1, nmn1, tp1, nmp1, &sn2, &sn2_c, &hn2,
 393                                     &an2, &bn2 ));
 394 /*   second pair of the triangles   */
 395     CV_MATCH_CHECK( status,
 396                     icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1,
 397                                     &bn1 ));
 398     CV_MATCH_CHECK( status,
 399                     icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1,
 400                                     &bp1 ));
 401
 402     a_s_c = fabs( s_c - sn2_c );
 403     a_sp1_c = fabs( sp1_c - sn1_c );
 404
 405     if( a_s_c > a_sp1_c )
 406 /*   form child vertexs for the root     */
 407     {
 408         tree_one.pt = t;
 409         tree_one.sign = (char) (CV_SIGN( s ));
 410         tree_one.area = fabs( s );
 411         tree_one.r1 = h / a;
 412         tree_one.r2 = b / a;
 413         tree_one.next_v1 = ptr2[3];
 414         tree_one.next_v2 = ptr2[0];
 415
 416         tree_two.pt = tn2;
 417         tree_two.sign = (char) (CV_SIGN( sn2 ));
 418         tree_two.area = fabs( sn2 );
 419         tree_two.r1 = hn2 / an2;
 420         tree_two.r2 = bn2 / an2;
 421         tree_two.next_v1 = ptr2[1];
 422         tree_two.next_v2 = ptr2[2];
 423
 424         CV_WRITE_SEQ_ELEM( tree_one, writer );
 425         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 426
 427         if( s_c > sn2_c )
 428         {
 429             if( ptr2[3] != NULL )
 430                 ptr2[3]->prev_v = cur_adr;
 431             if( ptr2[0] != NULL )
 432                 ptr2[0]->prev_v = cur_adr;
 433             ptr1[0] = cur_adr;
 434
 435             i_tree++;
 436
 437             CV_WRITE_SEQ_ELEM( tree_two, writer );
 438             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 439
 440             if( ptr2[1] != NULL )
 441                 ptr2[1]->prev_v = cur_adr;
 442             if( ptr2[2] != NULL )
 443                 ptr2[2]->prev_v = cur_adr;
 444             ptr1[1] = cur_adr;
 445
 446             i_tree++;
 447
 448             pt1[0] = tp1;
 449             pt1[1] = tn1;
 450         }
 451         else
 452         {
 453             CV_WRITE_SEQ_ELEM( tree_two, writer );
 454             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 455
 456             if( ptr2[1] != NULL )
 457                 ptr2[1]->prev_v = cur_adr;
 458             if( ptr2[2] != NULL )
 459                 ptr2[2]->prev_v = cur_adr;
 460             ptr1[0] = cur_adr;
 461
 462             i_tree++;
 463
 464             CV_WRITE_SEQ_ELEM( tree_one, writer );
 465             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 466
 467             if( ptr2[3] != NULL )
 468                 ptr2[3]->prev_v = cur_adr;
 469             if( ptr2[0] != NULL )
 470                 ptr2[0]->prev_v = cur_adr;
 471             ptr1[1] = cur_adr;
 472
 473             i_tree++;
 474
 475             pt1[0] = tn1;
 476             pt1[1] = tp1;
 477         }
 478     }
 479     else
 480     {
 481         tree_one.pt = tp1;
 482         tree_one.sign = (char) (CV_SIGN( sp1 ));
 483         tree_one.area = fabs( sp1 );
 484         tree_one.r1 = hp1 / ap1;
 485         tree_one.r2 = bp1 / ap1;
 486         tree_one.next_v1 = ptr2[2];
 487         tree_one.next_v2 = ptr2[3];
 488
 489         tree_two.pt = tn1;
 490         tree_two.sign = (char) (CV_SIGN( sn1 ));
 491         tree_two.area = fabs( sn1 );
 492         tree_two.r1 = hn1 / an1;
 493         tree_two.r2 = bn1 / an1;
 494         tree_two.next_v1 = ptr2[0];
 495         tree_two.next_v2 = ptr2[1];
 496
 497         CV_WRITE_SEQ_ELEM( tree_one, writer );
 498         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 499
 500         if( sp1_c > sn1_c )
 501         {
 502             if( ptr2[2] != NULL )
 503                 ptr2[2]->prev_v = cur_adr;
 504             if( ptr2[3] != NULL )
 505                 ptr2[3]->prev_v = cur_adr;
 506             ptr1[0] = cur_adr;
 507
 508             i_tree++;
 509
 510             CV_WRITE_SEQ_ELEM( tree_two, writer );
 511             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 512
 513             if( ptr2[0] != NULL )
 514                 ptr2[0]->prev_v = cur_adr;
 515             if( ptr2[1] != NULL )
 516                 ptr2[1]->prev_v = cur_adr;
 517             ptr1[1] = cur_adr;
 518
 519             i_tree++;
 520
 521             pt1[0] = tn2;
 522             pt1[1] = t;
 523         }
 524         else
 525         {
 526             CV_WRITE_SEQ_ELEM( tree_two, writer );
 527             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 528
 529             if( ptr2[0] != NULL )
 530                 ptr2[0]->prev_v = cur_adr;
 531             if( ptr2[1] != NULL )
 532                 ptr2[1]->prev_v = cur_adr;
 533             ptr1[0] = cur_adr;
 534
 535             i_tree++;
 536
 537             CV_WRITE_SEQ_ELEM( tree_one, writer );
 538             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 539
 540             if( ptr2[2] != NULL )
 541                 ptr2[2]->prev_v = cur_adr;
 542             if( ptr2[3] != NULL )
 543                 ptr2[3]->prev_v = cur_adr;
 544             ptr1[1] = cur_adr;
 545
 546             i_tree++;
 547
 548             pt1[0] = t;
 549             pt1[1] = tn2;
 550
 551         }
 552     }
 553
 554 /*    form root   */
 555     s = cvContourArea( contour );
 556
 557     tree_root->pt = pt1[1];
 558     tree_root->sign = 0;
 559     tree_root->area = fabs( s );
 560     tree_root->r1 = 0;
 561     tree_root->r2 = 0;
 562     tree_root->next_v1 = ptr1[0];
 563     tree_root->next_v2 = ptr1[1];
 564     tree_root->prev_v = NULL;
 565
 566     ptr1[0]->prev_v = (_CvTrianAttr *) tree_root;
 567     ptr1[1]->prev_v = (_CvTrianAttr *) tree_root;
 568
 569 /*     write binary tree root   */
 570 /*    CV_WRITE_SEQ_ELEM (tree_one, start_writer);   */
 571     i_tree++;
 572 /*  create Sequence hearder     */
 573     *((CvSeq **) tree) = cvEndWriteSeq( &writer );
 574 /*   write points for the main segment into sequence header   */
 575     (*tree)->p1 = pt1[0];
 576
 577   M_END:
 578
 579     cvFree( &ptr_n );
 580     cvFree( &ptr_p );
 581     cvFree( &num_n );
 582     cvFree( &num_p );
 583     cvFree( &pt_n );
 584     cvFree( &pt_p );
 585
 586     return status;
 587 }
 588
 589 /****************************************************************************************\
 590
 591  triangle attributes calculations
 592
 593 \****************************************************************************************/
 594 static CvStatus
 595 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1,
 596                 CvPoint t3, int n3, double *s, double *s_c,
 597                 double *h, double *a, double *b )
 598 {
 599     double x13, y13, x12, y12, l_base, nx, ny, qq;
 600     double eps = 1.e-5;
 601
 602     x13 = t3.x - t1.x;
 603     y13 = t3.y - t1.y;
 604     x12 = t2.x - t1.x;
 605     y12 = t2.y - t1.y;
 606     qq = x13 * x13 + y13 * y13;
 607     l_base = cvSqrt( (float) (qq) );
 608     if( l_base > eps )
 609     {
 610         nx = y13 / l_base;
 611         ny = -x13 / l_base;
 612
 613         *h = nx * x12 + ny * y12;
 614
 615         *s = (*h) * l_base / 2.;
 616
 617         *b = nx * y12 - ny * x12;
 618
 619         *a = l_base;
 620 /*   calculate interceptive area   */
 621         *s_c = cvContourArea( contour, cvSlice(n1, n3+1));
 622     }
 623     else
 624     {
 625         *h = 0;
 626         *s = 0;
 627         *s_c = 0;
 628         *b = 0;
 629         *a = 0;
 630     }
 631
 632     return CV_OK;
 633 }
 634
 635 /*F///////////////////////////////////////////////////////////////////////////////////////
 636 //    Name: cvCreateContourTree
 637 //    Purpose:
 638 //    Create binary tree representation for the contour
 639 //    Context:
 640 //    Parameters:
 641 //      contour - pointer to input contour object.
 642 //      storage - pointer to the current storage block
 643 //      tree   -  output pointer to the binary tree representation
 644 //      threshold - threshold for the binary tree building
 645 //
 646 //F*/
 647 CV_IMPL CvContourTree*
 648 cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold )
 649 {
 650     CvContourTree* tree = 0;
 651
 652     IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold ));
 653
 654     return tree;
 655 }
 656
 657
 658 /*F///////////////////////////////////////////////////////////////////////////////////////
 659 //    Name: icvContourFromContourTree
 660 //    Purpose:
 661 //    reconstracts contour from binary tree representation
 662 //    Context:
 663 //    Parameters:
 664 //      tree   -  pointer to the input binary tree representation
 665 //      storage - pointer to the current storage block
 666 //      contour - pointer to output contour object.
 667 //      criteria - criteria for the definition threshold value
 668 //                 for the contour reconstracting (level or precision)
 669 //F*/
 670 CV_IMPL CvSeq*
 671 cvContourFromContourTree( const CvContourTree*  tree,
 672                           CvMemStorage*  storage,
 673                           CvTermCriteria  criteria )
 674 {
 675     CvSeq* contour = 0;
 676     _CvTrianAttr **ptr_buf = 0;     /*  pointer to the pointer's buffer  */
 677     int *level_buf = 0;
 678     int i_buf;
 679
 680     int lpt;
 681     double area_all;
 682     double threshold;
 683     int cur_level;
 684     int level;
 685     int seq_flags;
 686     char log_iter, log_eps;
 687     int out_hearder_size;
 688     _CvTrianAttr *tree_one = 0, tree_root;  /*  current vertex  */
 689
 690     CvSeqReader reader;
 691     CvSeqWriter writer;
 692
 693     CV_FUNCNAME("cvContourFromContourTree");
 694
 695     __BEGIN__;
 696
 697     if( !tree )
 698         CV_ERROR( CV_StsNullPtr, "" );
 699
 700     if( !CV_IS_SEQ_POLYGON_TREE( tree ))
 701         CV_ERROR( CV_StsBadArg, "" );
 702
 703     criteria = cvCheckTermCriteria( criteria, 0., 100 );
 704
 705     lpt = tree->total;
 706     ptr_buf = NULL;
 707     level_buf = NULL;
 708     i_buf = 0;
 709     cur_level = 0;
 710     log_iter = (char) (criteria.type == CV_TERMCRIT_ITER ||
 711                        (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
 712     log_eps = (char) (criteria.type == CV_TERMCRIT_EPS ||
 713                       (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
 714
 715     cvStartReadSeq( (CvSeq *) tree, &reader, 0 );
 716
 717     out_hearder_size = sizeof( CvContour );
 718
 719     seq_flags = CV_SEQ_POLYGON;
 720     cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer );
 721
 722     ptr_buf = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
 723     if( log_iter )
 724         level_buf = (int *) cvAlloc( lpt * (sizeof( int )));
 725
 726     memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * ));
 727
 728 /*     write the first tree root's point as a start point of the result contour  */
 729     CV_WRITE_SEQ_ELEM( tree->p1, writer );
 730 /*     write the second tree root"s point into buffer    */
 731
 732 /*     read the root of the tree   */
 733     CV_READ_SEQ_ELEM( tree_root, reader );
 734
 735     tree_one = &tree_root;
 736     area_all = tree_one->area;
 737
 738     if( log_eps )
 739         threshold = criteria.epsilon * area_all;
 740     else
 741         threshold = 10 * area_all;
 742
 743     if( log_iter )
 744         level = criteria.max_iter;
 745     else
 746         level = -1;
 747
 748 /*  contour from binary tree constraction    */
 749     while( i_buf >= 0 )
 750     {
 751         if( tree_one != NULL && (cur_level <= level || tree_one->area >= threshold) )
 752 /*   go to left sub tree for the vertex and save pointer to the right vertex   */
 753 /*   into the buffer     */
 754         {
 755             ptr_buf[i_buf] = tree_one;
 756             if( log_iter )
 757             {
 758                 level_buf[i_buf] = cur_level;
 759                 cur_level++;
 760             }
 761             i_buf++;
 762             tree_one = tree_one->next_v1;
 763         }
 764         else
 765         {
 766             i_buf--;
 767             if( i_buf >= 0 )
 768             {
 769                 CvPoint pt = ptr_buf[i_buf]->pt;
 770                 CV_WRITE_SEQ_ELEM( pt, writer );
 771                 tree_one = ptr_buf[i_buf]->next_v2;
 772                 if( log_iter )
 773                 {
 774                     cur_level = level_buf[i_buf] + 1;
 775                 }
 776             }
 777         }
 778     }
 779
 780     contour = cvEndWriteSeq( &writer );
 781     cvBoundingRect( contour, 1 );
 782
 783     __CLEANUP__;
 784     __END__;
 785
 786     cvFree( &level_buf );
 787     cvFree( &ptr_buf );
 788
 789     return contour;
 790 }
 791