vcs.maemo.org Git - opencv/blob - cv/src/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_POLYGON( 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) && s_c <= sn1_c
 232                 && s_c <= sn2_c && s_c < e && j > 1 && prev2_null == 0 || (s_c < eps && j > 0
 233                                                                            && prev_null == 0) )
 234
 235             {
 236                 prev_null = prev2_null = 1;
 237                 if( s_c < threshold )
 238                 {
 239                     if( ptr1[j_1] == NULL && ptr1[j] == NULL )
 240                     {
 241                         if( i_buf > 0 )
 242                             ptr2[i_buf - 1] = NULL;
 243                         else
 244                             i_end = 0;
 245                     }
 246                     else
 247                     {
 248 /*   form next vertex  */
 249                         tree_one.pt = t;
 250                         tree_one.sign = (char) (CV_SIGN( s ));
 251                         tree_one.r1 = h / a;
 252                         tree_one.r2 = b / a;
 253                         tree_one.area = fabs( s );
 254                         tree_one.next_v1 = ptr1[j_1];
 255                         tree_one.next_v2 = ptr1[j];
 256
 257                         CV_WRITE_SEQ_ELEM( tree_one, writer );
 258                         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 259
 260                         if( ptr1[j_1] != NULL )
 261                             ptr1[j_1]->prev_v = cur_adr;
 262                         if( ptr1[j] != NULL )
 263                             ptr1[j]->prev_v = cur_adr;
 264
 265                         if( i_buf > 0 )
 266                             ptr2[i_buf - 1] = cur_adr;
 267                         else
 268                         {
 269                             tree_end = (_CvTrianAttr *) writer.ptr;
 270                             i_end = 1;
 271                         }
 272                         i_tree++;
 273                     }
 274                 }
 275                 else
 276 /*   form next vertex    */
 277                 {
 278                     tree_one.pt = t;
 279                     tree_one.sign = (char) (CV_SIGN( s ));
 280                     tree_one.area = fabs( s );
 281                     tree_one.r1 = h / a;
 282                     tree_one.r2 = b / a;
 283                     tree_one.next_v1 = ptr1[j_1];
 284                     tree_one.next_v2 = ptr1[j];
 285
 286                     CV_WRITE_SEQ_ELEM( tree_one, writer );
 287                     cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 288
 289                     if( ptr1[j_1] != NULL )
 290                         ptr1[j_1]->prev_v = cur_adr;
 291                     if( ptr1[j] != NULL )
 292                         ptr1[j]->prev_v = cur_adr;
 293
 294                     if( i_buf > 0 )
 295                         ptr2[i_buf - 1] = cur_adr;
 296                     else
 297                     {
 298                         tree_end = cur_adr;
 299                         i_end = 1;
 300                     }
 301                     i_tree++;
 302                 }
 303             }
 304             else
 305 /*   the current triangle is'not LMIAT    */
 306             {
 307                 prev_null = 0;
 308                 switch (prev2_null)
 309                 {
 310                 case 0:
 311                     break;
 312                 case 1:
 313                     {
 314                         prev2_null = 2;
 315                         break;
 316                     }
 317                 case 2:
 318                     {
 319                         prev2_null = 0;
 320                         break;
 321                     }
 322                 }
 323                 if( j != i - 1 || i_end == -1 )
 324                     ptr2[i_buf] = ptr1[j];
 325                 else if( i_end == 0 )
 326                     ptr2[i_buf] = NULL;
 327                 else
 328                     ptr2[i_buf] = tree_end;
 329                 pt2[i_buf] = t;
 330                 num2[i_buf] = num1[j];
 331                 i_buf++;
 332             }
 333 /*    go to next vertex    */
 334             tp3 = tp2;
 335             tp2 = tp1;
 336             tp1 = t;
 337             t = tn1;
 338             tn1 = tn2;
 339             tn2 = tn3;
 340             nmp3 = nmp2;
 341             nmp2 = nmp1;
 342             nmp1 = nm;
 343             nm = nmn1;
 344             nmn1 = nmn2;
 345             nmn2 = nmn3;
 346
 347             sp2 = sp1;
 348             sp1 = s;
 349             s = sn1;
 350             sn1 = sn2;
 351             sp2_c = sp1_c;
 352             sp1_c = s_c;
 353             s_c = sn1_c;
 354             sn1_c = sn2_c;
 355
 356             ap2 = ap1;
 357             ap1 = a;
 358             a = an1;
 359             an1 = an2;
 360             bp2 = bp1;
 361             bp1 = b;
 362             b = bn1;
 363             bn1 = bn2;
 364             hp2 = hp1;
 365             hp1 = h;
 366             h = hn1;
 367             hn1 = hn2;
 368             j_3++;
 369             if( j_3 >= i )
 370                 j_3 = 0;
 371         }
 372
 373         i = i_buf;
 374         e = e * koef;
 375     }
 376
 377 /*  constract tree root  */
 378     if( i != 4 )
 379         return CV_BADFACTOR_ERR;
 380
 381     t = pt2[0];
 382     tn1 = pt2[1];
 383     tn2 = pt2[2];
 384     tp1 = pt2[3];
 385     nm = num2[0];
 386     nmn1 = num2[1];
 387     nmn2 = num2[2];
 388     nmp1 = num2[3];
 389 /*   first pair of the triangles   */
 390     CV_MATCH_CHECK( status,
 391                     icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, &b ));
 392     CV_MATCH_CHECK( status,
 393                     icvCalcTriAttr( contour, tn2, tn1, nmn1, tp1, nmp1, &sn2, &sn2_c, &hn2,
 394                                     &an2, &bn2 ));
 395 /*   second pair of the triangles   */
 396     CV_MATCH_CHECK( status,
 397                     icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1,
 398                                     &bn1 ));
 399     CV_MATCH_CHECK( status,
 400                     icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1,
 401                                     &bp1 ));
 402
 403     a_s_c = fabs( s_c - sn2_c );
 404     a_sp1_c = fabs( sp1_c - sn1_c );
 405
 406     if( a_s_c > a_sp1_c )
 407 /*   form child vertexs for the root     */
 408     {
 409         tree_one.pt = t;
 410         tree_one.sign = (char) (CV_SIGN( s ));
 411         tree_one.area = fabs( s );
 412         tree_one.r1 = h / a;
 413         tree_one.r2 = b / a;
 414         tree_one.next_v1 = ptr2[3];
 415         tree_one.next_v2 = ptr2[0];
 416
 417         tree_two.pt = tn2;
 418         tree_two.sign = (char) (CV_SIGN( sn2 ));
 419         tree_two.area = fabs( sn2 );
 420         tree_two.r1 = hn2 / an2;
 421         tree_two.r2 = bn2 / an2;
 422         tree_two.next_v1 = ptr2[1];
 423         tree_two.next_v2 = ptr2[2];
 424
 425         CV_WRITE_SEQ_ELEM( tree_one, writer );
 426         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 427
 428         if( s_c > sn2_c )
 429         {
 430             if( ptr2[3] != NULL )
 431                 ptr2[3]->prev_v = cur_adr;
 432             if( ptr2[0] != NULL )
 433                 ptr2[0]->prev_v = cur_adr;
 434             ptr1[0] = cur_adr;
 435
 436             i_tree++;
 437
 438             CV_WRITE_SEQ_ELEM( tree_two, writer );
 439             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 440
 441             if( ptr2[1] != NULL )
 442                 ptr2[1]->prev_v = cur_adr;
 443             if( ptr2[2] != NULL )
 444                 ptr2[2]->prev_v = cur_adr;
 445             ptr1[1] = cur_adr;
 446
 447             i_tree++;
 448
 449             pt1[0] = tp1;
 450             pt1[1] = tn1;
 451         }
 452         else
 453         {
 454             CV_WRITE_SEQ_ELEM( tree_two, writer );
 455             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 456
 457             if( ptr2[1] != NULL )
 458                 ptr2[1]->prev_v = cur_adr;
 459             if( ptr2[2] != NULL )
 460                 ptr2[2]->prev_v = cur_adr;
 461             ptr1[0] = cur_adr;
 462
 463             i_tree++;
 464
 465             CV_WRITE_SEQ_ELEM( tree_one, writer );
 466             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 467
 468             if( ptr2[3] != NULL )
 469                 ptr2[3]->prev_v = cur_adr;
 470             if( ptr2[0] != NULL )
 471                 ptr2[0]->prev_v = cur_adr;
 472             ptr1[1] = cur_adr;
 473
 474             i_tree++;
 475
 476             pt1[0] = tn1;
 477             pt1[1] = tp1;
 478         }
 479     }
 480     else
 481     {
 482         tree_one.pt = tp1;
 483         tree_one.sign = (char) (CV_SIGN( sp1 ));
 484         tree_one.area = fabs( sp1 );
 485         tree_one.r1 = hp1 / ap1;
 486         tree_one.r2 = bp1 / ap1;
 487         tree_one.next_v1 = ptr2[2];
 488         tree_one.next_v2 = ptr2[3];
 489
 490         tree_two.pt = tn1;
 491         tree_two.sign = (char) (CV_SIGN( sn1 ));
 492         tree_two.area = fabs( sn1 );
 493         tree_two.r1 = hn1 / an1;
 494         tree_two.r2 = bn1 / an1;
 495         tree_two.next_v1 = ptr2[0];
 496         tree_two.next_v2 = ptr2[1];
 497
 498         CV_WRITE_SEQ_ELEM( tree_one, writer );
 499         cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 500
 501         if( sp1_c > sn1_c )
 502         {
 503             if( ptr2[2] != NULL )
 504                 ptr2[2]->prev_v = cur_adr;
 505             if( ptr2[3] != NULL )
 506                 ptr2[3]->prev_v = cur_adr;
 507             ptr1[0] = cur_adr;
 508
 509             i_tree++;
 510
 511             CV_WRITE_SEQ_ELEM( tree_two, writer );
 512             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 513
 514             if( ptr2[0] != NULL )
 515                 ptr2[0]->prev_v = cur_adr;
 516             if( ptr2[1] != NULL )
 517                 ptr2[1]->prev_v = cur_adr;
 518             ptr1[1] = cur_adr;
 519
 520             i_tree++;
 521
 522             pt1[0] = tn2;
 523             pt1[1] = t;
 524         }
 525         else
 526         {
 527             CV_WRITE_SEQ_ELEM( tree_two, writer );
 528             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 529
 530             if( ptr2[0] != NULL )
 531                 ptr2[0]->prev_v = cur_adr;
 532             if( ptr2[1] != NULL )
 533                 ptr2[1]->prev_v = cur_adr;
 534             ptr1[0] = cur_adr;
 535
 536             i_tree++;
 537
 538             CV_WRITE_SEQ_ELEM( tree_one, writer );
 539             cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size);
 540
 541             if( ptr2[2] != NULL )
 542                 ptr2[2]->prev_v = cur_adr;
 543             if( ptr2[3] != NULL )
 544                 ptr2[3]->prev_v = cur_adr;
 545             ptr1[1] = cur_adr;
 546
 547             i_tree++;
 548
 549             pt1[0] = t;
 550             pt1[1] = tn2;
 551
 552         }
 553     }
 554
 555 /*    form root   */
 556     s = cvContourArea( contour );
 557
 558     tree_root->pt = pt1[1];
 559     tree_root->sign = 0;
 560     tree_root->area = fabs( s );
 561     tree_root->r1 = 0;
 562     tree_root->r2 = 0;
 563     tree_root->next_v1 = ptr1[0];
 564     tree_root->next_v2 = ptr1[1];
 565     tree_root->prev_v = NULL;
 566
 567     ptr1[0]->prev_v = (_CvTrianAttr *) tree_root;
 568     ptr1[1]->prev_v = (_CvTrianAttr *) tree_root;
 569
 570 /*     write binary tree root   */
 571 /*    CV_WRITE_SEQ_ELEM (tree_one, start_writer);   */
 572     i_tree++;
 573 /*  create Sequence hearder     */
 574     *((CvSeq **) tree) = cvEndWriteSeq( &writer );
 575 /*   write points for the main segment into sequence header   */
 576     (*tree)->p1 = pt1[0];
 577
 578   M_END:
 579
 580     cvFree( &ptr_n );
 581     cvFree( &ptr_p );
 582     cvFree( &num_n );
 583     cvFree( &num_p );
 584     cvFree( &pt_n );
 585     cvFree( &pt_p );
 586
 587     return status;
 588 }
 589
 590 /****************************************************************************************\
 591
 592  triangle attributes calculations
 593
 594 \****************************************************************************************/
 595 static CvStatus
 596 icvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1,
 597                 CvPoint t3, int n3, double *s, double *s_c,
 598                 double *h, double *a, double *b )
 599 {
 600     double x13, y13, x12, y12, l_base, nx, ny, qq;
 601     double eps = 1.e-5;
 602
 603     x13 = t3.x - t1.x;
 604     y13 = t3.y - t1.y;
 605     x12 = t2.x - t1.x;
 606     y12 = t2.y - t1.y;
 607     qq = x13 * x13 + y13 * y13;
 608     l_base = cvSqrt( (float) (qq) );
 609     if( l_base > eps )
 610     {
 611         nx = y13 / l_base;
 612         ny = -x13 / l_base;
 613
 614         *h = nx * x12 + ny * y12;
 615
 616         *s = (*h) * l_base / 2.;
 617
 618         *b = nx * y12 - ny * x12;
 619
 620         *a = l_base;
 621 /*   calculate interceptive area   */
 622         *s_c = cvContourArea( contour, cvSlice(n1, n3+1));
 623     }
 624     else
 625     {
 626         *h = 0;
 627         *s = 0;
 628         *s_c = 0;
 629         *b = 0;
 630         *a = 0;
 631     }
 632
 633     return CV_OK;
 634 }
 635
 636 /*F///////////////////////////////////////////////////////////////////////////////////////
 637 //    Name: cvCreateContourTree
 638 //    Purpose:
 639 //    Create binary tree representation for the contour
 640 //    Context:
 641 //    Parameters:
 642 //      contour - pointer to input contour object.
 643 //      storage - pointer to the current storage block
 644 //      tree   -  output pointer to the binary tree representation
 645 //      threshold - threshold for the binary tree building
 646 //
 647 //F*/
 648 CV_IMPL CvContourTree*
 649 cvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold )
 650 {
 651     CvContourTree* tree = 0;
 652
 653     CV_FUNCNAME( "cvCreateContourTree" );
 654     __BEGIN__;
 655
 656     IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold ));
 657
 658     __CLEANUP__;
 659     __END__;
 660
 661     return tree;
 662 }
 663
 664
 665 /*F///////////////////////////////////////////////////////////////////////////////////////
 666 //    Name: icvContourFromContourTree
 667 //    Purpose:
 668 //    reconstracts contour from binary tree representation
 669 //    Context:
 670 //    Parameters:
 671 //      tree   -  pointer to the input binary tree representation
 672 //      storage - pointer to the current storage block
 673 //      contour - pointer to output contour object.
 674 //      criteria - criteria for the definition threshold value
 675 //                 for the contour reconstracting (level or precision)
 676 //F*/
 677 CV_IMPL CvSeq*
 678 cvContourFromContourTree( const CvContourTree*  tree,
 679                           CvMemStorage*  storage,
 680                           CvTermCriteria  criteria )
 681 {
 682     CvSeq* contour = 0;
 683     _CvTrianAttr **ptr_buf = 0;     /*  pointer to the pointer's buffer  */
 684     int *level_buf = 0;
 685     int i_buf;
 686
 687     int lpt;
 688     double area_all;
 689     double threshold;
 690     int cur_level;
 691     int level;
 692     int seq_flags;
 693     char log_iter, log_eps;
 694     int out_hearder_size;
 695     _CvTrianAttr *tree_one = 0, tree_root;  /*  current vertex  */
 696
 697     CvSeqReader reader;
 698     CvSeqWriter writer;
 699
 700     CV_FUNCNAME("cvContourFromContourTree");
 701
 702     __BEGIN__;
 703
 704     if( !tree )
 705         CV_ERROR( CV_StsNullPtr, "" );
 706
 707     if( !CV_IS_SEQ_POLYGON_TREE( tree ))
 708         CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR );
 709
 710     criteria = cvCheckTermCriteria( criteria, 0., 100 );
 711
 712     lpt = tree->total;
 713     ptr_buf = NULL;
 714     level_buf = NULL;
 715     i_buf = 0;
 716     cur_level = 0;
 717     log_iter = (char) (criteria.type == CV_TERMCRIT_ITER ||
 718                        (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
 719     log_eps = (char) (criteria.type == CV_TERMCRIT_EPS ||
 720                       (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS));
 721
 722     cvStartReadSeq( (CvSeq *) tree, &reader, 0 );
 723
 724     out_hearder_size = sizeof( CvContour );
 725
 726     seq_flags = CV_SEQ_POLYGON;
 727     cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer );
 728
 729     ptr_buf = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * ));
 730     if( ptr_buf == NULL )
 731         CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
 732     if( log_iter )
 733     {
 734         level_buf = (int *) cvAlloc( lpt * (sizeof( int )));
 735
 736         if( level_buf == NULL )
 737             CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR );
 738     }
 739
 740     memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * ));
 741
 742 /*     write the first tree root's point as a start point of the result contour  */
 743     CV_WRITE_SEQ_ELEM( tree->p1, writer );
 744 /*     write the second tree root"s point into buffer    */
 745
 746 /*     read the root of the tree   */
 747     CV_READ_SEQ_ELEM( tree_root, reader );
 748
 749     tree_one = &tree_root;
 750     area_all = tree_one->area;
 751
 752     if( log_eps )
 753         threshold = criteria.epsilon * area_all;
 754     else
 755         threshold = 10 * area_all;
 756
 757     if( log_iter )
 758         level = criteria.max_iter;
 759     else
 760         level = -1;
 761
 762 /*  contour from binary tree constraction    */
 763     while( i_buf >= 0 )
 764     {
 765         if( tree_one != NULL && (cur_level <= level || tree_one->area >= threshold) )
 766 /*   go to left sub tree for the vertex and save pointer to the right vertex   */
 767 /*   into the buffer     */
 768         {
 769             ptr_buf[i_buf] = tree_one;
 770             if( log_iter )
 771             {
 772                 level_buf[i_buf] = cur_level;
 773                 cur_level++;
 774             }
 775             i_buf++;
 776             tree_one = tree_one->next_v1;
 777         }
 778         else
 779         {
 780             i_buf--;
 781             if( i_buf >= 0 )
 782             {
 783                 CvPoint pt = ptr_buf[i_buf]->pt;
 784                 CV_WRITE_SEQ_ELEM( pt, writer );
 785                 tree_one = ptr_buf[i_buf]->next_v2;
 786                 if( log_iter )
 787                 {
 788                     cur_level = level_buf[i_buf] + 1;
 789                 }
 790             }
 791         }
 792     }
 793
 794     contour = cvEndWriteSeq( &writer );
 795     cvBoundingRect( contour, 1 );
 796
 797     __CLEANUP__;
 798     __END__;
 799
 800     cvFree( &level_buf );
 801     cvFree( &ptr_buf );
 802
 803     return contour;
 804 }
 805