16acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*M/////////////////////////////////////////////////////////////////////////////////////// 26acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 36acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 46acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 56acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// By downloading, copying, installing or using the software you agree to this license. 66acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// If you do not agree to this license, do not download, install, 76acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// copy or use the software. 86acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 96acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Intel License Agreement 116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// For Open Source Computer Vision Library 126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Copyright (C) 2000, Intel Corporation, all rights reserved. 146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Third party copyrights are property of their respective owners. 156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Redistribution and use in source and binary forms, with or without modification, 176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// are permitted provided that the following conditions are met: 186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's of source code must retain the above copyright notice, 206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer. 216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * Redistribution's in binary form must reproduce the above copyright notice, 236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// this list of conditions and the following disclaimer in the documentation 246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and/or other materials provided with the distribution. 256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// * The name of Intel Corporation may not be used to endorse or promote products 276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// derived from this software without specific prior written permission. 286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// This software is provided by the copyright holders and contributors "as is" and 306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// any express or implied warranties, including, but not limited to, the implied 316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// warranties of merchantability and fitness for a particular purpose are disclaimed. 326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// In no event shall the Intel Corporation or contributors be liable for any direct, 336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// indirect, incidental, special, exemplary, or consequential damages 346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// (including, but not limited to, procurement of substitute goods or services; 356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// loss of use, data, or profits; or business interruption) however caused 366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// and on any theory of liability, whether in contract, strict liability, 376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// or tort (including negligence or otherwise) arising in any way out of 386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// the use of this software, even if advised of the possibility of such damage. 396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//M*/ 416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#include "_cv.h" 426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn#define CV_MATCH_CHECK( status, cvFun ) \ 446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { \ 456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn status = cvFun; \ 466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( status != CV_OK ) \ 476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn goto M_END; \ 486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1, 526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint t3, int n3, double *s, double *s_c, 536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double *h, double *a, double *b ); 546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*F/////////////////////////////////////////////////////////////////////////////////////// 566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Name: icvCreateContourTree 576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Purpose: 586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Create binary tree representation for the contour 596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Context: 606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Parameters: 616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// contour - pointer to input contour object. 626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// storage - pointer to the current storage block 636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// tree - output pointer to the binary tree representation 646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// threshold - threshold for the binary tree building 656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//F*/ 676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCreateContourTree( const CvSeq * contour, CvMemStorage * storage, 696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourTree ** tree, double threshold ) 706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint *pt_p; /* pointer to previos points */ 726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint *pt_n; /* pointer to next points */ 736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint *pt1, *pt2; /* pointer to current points */ 746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint t, tp1, tp2, tp3, tn1, tn2, tn3; 766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int lpt, flag, i, j, i_tree, j_1, j_3, i_buf; 776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double s, sp1, sp2, sn1, sn2, s_c, sp1_c, sp2_c, sn1_c, sn2_c, h, hp1, hp2, hn1, hn2, 786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a, ap1, ap2, an1, an2, b, bp1, bp2, bn1, bn2; 796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double a_s_c, a_sp1_c; 806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvTrianAttr **ptr_p, **ptr_n, **ptr1, **ptr2; /* pointers to pointers of triangles */ 826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvTrianAttr *cur_adr; 836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *num_p, *num_n, *num1, *num2; /* numbers of input contour points */ 856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int nm, nmp1, nmp2, nmp3, nmn1, nmn2, nmn3; 866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int seq_flags = 1, i_end, prev_null, prev2_null; 876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double koef = 1.5; 886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double eps = 1.e-7; 896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double e; 906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvStatus status; 916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int hearder_size; 926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvTrianAttr tree_one, tree_two, *tree_end, *tree_root; 936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqWriter writer; 956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( contour != NULL && contour->total >= 4 ); 976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn status = CV_OK; 986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( contour == NULL ) 1006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_NULLPTR_ERR; 1016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( contour->total < 4 ) 1026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADSIZE_ERR; 1036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SEQ_POLYGON( contour )) 1056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADFLAG_ERR; 1066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Convert Sequence to array */ 1096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lpt = contour->total; 1106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt_p = pt_n = NULL; 1116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num_p = num_n = NULL; 1126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr_p = ptr_n = ptr1 = ptr2 = NULL; 1136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_end = NULL; 1146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt_p = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint )); 1166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt_n = (CvPoint *) cvAlloc( lpt * sizeof( CvPoint )); 1176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num_p = (int *) cvAlloc( lpt * sizeof( int )); 1196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num_n = (int *) cvAlloc( lpt * sizeof( int )); 1206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn hearder_size = sizeof( CvContourTree ); 1226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn seq_flags = CV_SEQ_POLYGON_TREE; 1236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartWriteSeq( seq_flags, hearder_size, sizeof( _CvTrianAttr ), storage, &writer ); 1246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr_p = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * )); 1266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr_n = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * )); 1276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( ptr_p, 0, lpt * sizeof( _CvTrianAttr * )); 1296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( ptr_n, 0, lpt * sizeof( _CvTrianAttr * )); 1306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( pt_p == NULL || pt_n == NULL ) 1326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OUTOFMEM_ERR; 1336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr_p == NULL || ptr_n == NULL ) 1346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OUTOFMEM_ERR; 1356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* write fild for the binary tree root */ 1376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* start_writer = writer; */ 1386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.pt.x = tree_one.pt.y = 0; 1406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.sign = 0; 1416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.area = 0; 1426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r1 = tree_one.r2 = 0; 1436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v1 = tree_one.next_v2 = tree_one.prev_v = NULL; 1446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 1466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 1476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( cvCvtSeqToArray( contour, (char *) pt_p ) == (char *) contour ) 1496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADPOINT_ERR; 1506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < lpt; i++ ) 1526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num_p[i] = i; 1536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = lpt; 1556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn flag = 0; 1566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree = 0; 1576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn e = 20.; /* initial threshold value */ 1586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1 = ptr_p; 1596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2 = ptr_n; 1606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1 = pt_p; 1616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2 = pt_n; 1626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num1 = num_p; 1636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num2 = num_n; 1646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* binary tree constraction */ 1656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( i > 4 ) 1666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( flag == 0 ) 1686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1 = ptr_p; 1706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2 = ptr_n; 1716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1 = pt_p; 1726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2 = pt_n; 1736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num1 = num_p; 1746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num2 = num_n; 1756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn flag = 1; 1766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 1786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1 = ptr_n; 1806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2 = ptr_p; 1816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1 = pt_n; 1826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2 = pt_p; 1836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num1 = num_n; 1846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num2 = num_p; 1856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn flag = 0; 1866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = pt1[0]; 1886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nm = num1[0]; 1896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp1 = pt1[i - 1]; 1906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp1 = num1[i - 1]; 1916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp2 = pt1[i - 2]; 1926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp2 = num1[i - 2]; 1936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp3 = pt1[i - 3]; 1946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp3 = num1[i - 3]; 1956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn1 = pt1[1]; 1966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn1 = num1[1]; 1976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn2 = pt1[2]; 1986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn2 = num1[2]; 1996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_buf = 0; 2016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_end = -1; 2026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 2036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, 2046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &b )); 2056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 2066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, tp1, tp2, nmp2, t, nm, &sp1, &sp1_c, &hp1, 2076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &ap1, &bp1 )); 2086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 2096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, tp2, tp3, nmp3, tp1, nmp1, &sp2, &sp2_c, &hp2, 2106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &ap2, &bp2 )); 2116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 2126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, 2136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &an1, &bn1 )); 2146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j_3 = 3; 2176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_null = prev2_null = 0; 2186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 0; j < i; j++ ) 2196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn3 = pt1[j_3]; 2216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn3 = num1[j_3]; 2226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j == 0 ) 2236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j_1 = i - 1; 2246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j_1 = j - 1; 2266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, icvCalcTriAttr( contour, tn2, tn1, nmn1, tn3, nmn3, 2286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &sn2, &sn2_c, &hn2, &an2, &bn2 )); 2296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (s_c < sp1_c && s_c < sp2_c && s_c <= sn1_c && s_c <= sn2_c && s_c < e) || 2316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (((s_c == sp1_c && s_c <= sp2_c) || (s_c == sp2_c && s_c <= sp1_c)) && 2326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s_c <= sn1_c && s_c <= sn2_c && s_c < e && j > 1 && prev2_null == 0) || 2336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (s_c < eps && j > 0 && prev_null == 0) ) 2346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_null = prev2_null = 1; 2366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( s_c < threshold ) 2376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr1[j_1] == NULL && ptr1[j] == NULL ) 2396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i_buf > 0 ) 2416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[i_buf - 1] = NULL; 2426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_end = 0; 2446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* form next vertex */ 2486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.pt = t; 2496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.sign = (char) (CV_SIGN( s )); 2506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r1 = h / a; 2516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r2 = b / a; 2526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.area = fabs( s ); 2536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v1 = ptr1[j_1]; 2546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v2 = ptr1[j]; 2556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 2576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 2586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr1[j_1] != NULL ) 2606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[j_1]->prev_v = cur_adr; 2616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr1[j] != NULL ) 2626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[j]->prev_v = cur_adr; 2636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i_buf > 0 ) 2656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[i_buf - 1] = cur_adr; 2666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_end = (_CvTrianAttr *) writer.ptr; 2696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_end = 1; 2706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 2726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* form next vertex */ 2766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.pt = t; 2786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.sign = (char) (CV_SIGN( s )); 2796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.area = fabs( s ); 2806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r1 = h / a; 2816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r2 = b / a; 2826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v1 = ptr1[j_1]; 2836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v2 = ptr1[j]; 2846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 2866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 2876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr1[j_1] != NULL ) 2896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[j_1]->prev_v = cur_adr; 2906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr1[j] != NULL ) 2916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[j]->prev_v = cur_adr; 2926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i_buf > 0 ) 2946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[i_buf - 1] = cur_adr; 2956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_end = cur_adr; 2986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_end = 1; 2996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 3016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* the current triangle is'not LMIAT */ 3056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_null = 0; 3076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch (prev2_null) 3086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 0: 3106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 3116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 1: 3126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev2_null = 2; 3146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 3156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case 2: 3176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev2_null = 0; 3196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 3206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j != i - 1 || i_end == -1 ) 3236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[i_buf] = ptr1[j]; 3246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( i_end == 0 ) 3256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[i_buf] = NULL; 3266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[i_buf] = tree_end; 3286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt2[i_buf] = t; 3296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn num2[i_buf] = num1[j]; 3306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_buf++; 3316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* go to next vertex */ 3336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp3 = tp2; 3346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp2 = tp1; 3356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp1 = t; 3366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = tn1; 3376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn1 = tn2; 3386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn2 = tn3; 3396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp3 = nmp2; 3406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp2 = nmp1; 3416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp1 = nm; 3426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nm = nmn1; 3436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn1 = nmn2; 3446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn2 = nmn3; 3456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sp2 = sp1; 3476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sp1 = s; 3486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = sn1; 3496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sn1 = sn2; 3506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sp2_c = sp1_c; 3516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sp1_c = s_c; 3526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s_c = sn1_c; 3536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sn1_c = sn2_c; 3546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ap2 = ap1; 3566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ap1 = a; 3576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a = an1; 3586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn an1 = an2; 3596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn bp2 = bp1; 3606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn bp1 = b; 3616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn b = bn1; 3626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn bn1 = bn2; 3636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn hp2 = hp1; 3646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn hp1 = h; 3656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn h = hn1; 3666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn hn1 = hn2; 3676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j_3++; 3686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j_3 >= i ) 3696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn j_3 = 0; 3706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = i_buf; 3736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn e = e * koef; 3746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* constract tree root */ 3776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i != 4 ) 3786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADFACTOR_ERR; 3796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn t = pt2[0]; 3816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn1 = pt2[1]; 3826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tn2 = pt2[2]; 3836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tp1 = pt2[3]; 3846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nm = num2[0]; 3856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn1 = num2[1]; 3866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmn2 = num2[2]; 3876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nmp1 = num2[3]; 3886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* first pair of the triangles */ 3896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 3906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, t, tp1, nmp1, tn1, nmn1, &s, &s_c, &h, &a, &b )); 3916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 3926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, tn2, tn1, nmn1, tp1, nmp1, &sn2, &sn2_c, &hn2, 3936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &an2, &bn2 )); 3946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* second pair of the triangles */ 3956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 3966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, tn1, t, nm, tn2, nmn2, &sn1, &sn1_c, &hn1, &an1, 3976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &bn1 )); 3986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_MATCH_CHECK( status, 3996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn icvCalcTriAttr( contour, tp1, tn2, nmn2, t, nm, &sp1, &sp1_c, &hp1, &ap1, 4006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &bp1 )); 4016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a_s_c = fabs( s_c - sn2_c ); 4036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn a_sp1_c = fabs( sp1_c - sn1_c ); 4046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( a_s_c > a_sp1_c ) 4066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* form child vertexs for the root */ 4076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.pt = t; 4096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.sign = (char) (CV_SIGN( s )); 4106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.area = fabs( s ); 4116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r1 = h / a; 4126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r2 = b / a; 4136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v1 = ptr2[3]; 4146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v2 = ptr2[0]; 4156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.pt = tn2; 4176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.sign = (char) (CV_SIGN( sn2 )); 4186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.area = fabs( sn2 ); 4196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.r1 = hn2 / an2; 4206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.r2 = bn2 / an2; 4216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.next_v1 = ptr2[1]; 4226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.next_v2 = ptr2[2]; 4236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 4256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 4266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( s_c > sn2_c ) 4286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[3] != NULL ) 4306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[3]->prev_v = cur_adr; 4316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[0] != NULL ) 4326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[0]->prev_v = cur_adr; 4336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[0] = cur_adr; 4346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 4366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_two, writer ); 4386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 4396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[1] != NULL ) 4416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[1]->prev_v = cur_adr; 4426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[2] != NULL ) 4436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[2]->prev_v = cur_adr; 4446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[1] = cur_adr; 4456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 4476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[0] = tp1; 4496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[1] = tn1; 4506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 4526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_two, writer ); 4546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 4556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[1] != NULL ) 4576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[1]->prev_v = cur_adr; 4586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[2] != NULL ) 4596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[2]->prev_v = cur_adr; 4606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[0] = cur_adr; 4616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 4636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 4656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 4666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[3] != NULL ) 4686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[3]->prev_v = cur_adr; 4696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[0] != NULL ) 4706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[0]->prev_v = cur_adr; 4716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[1] = cur_adr; 4726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 4746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[0] = tn1; 4766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[1] = tp1; 4776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 4806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.pt = tp1; 4826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.sign = (char) (CV_SIGN( sp1 )); 4836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.area = fabs( sp1 ); 4846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r1 = hp1 / ap1; 4856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.r2 = bp1 / ap1; 4866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v1 = ptr2[2]; 4876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one.next_v2 = ptr2[3]; 4886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.pt = tn1; 4906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.sign = (char) (CV_SIGN( sn1 )); 4916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.area = fabs( sn1 ); 4926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.r1 = hn1 / an1; 4936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.r2 = bn1 / an1; 4946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.next_v1 = ptr2[0]; 4956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_two.next_v2 = ptr2[1]; 4966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 4986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 4996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( sp1_c > sn1_c ) 5016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[2] != NULL ) 5036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[2]->prev_v = cur_adr; 5046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[3] != NULL ) 5056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[3]->prev_v = cur_adr; 5066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[0] = cur_adr; 5076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 5096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_two, writer ); 5116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 5126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[0] != NULL ) 5146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[0]->prev_v = cur_adr; 5156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[1] != NULL ) 5166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[1]->prev_v = cur_adr; 5176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[1] = cur_adr; 5186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 5206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[0] = tn2; 5226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[1] = t; 5236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 5256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_two, writer ); 5276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 5286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[0] != NULL ) 5306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[0]->prev_v = cur_adr; 5316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[1] != NULL ) 5326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[1]->prev_v = cur_adr; 5336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[0] = cur_adr; 5346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 5366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree_one, writer ); 5386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_adr = (_CvTrianAttr *) (writer.ptr - writer.seq->elem_size); 5396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[2] != NULL ) 5416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[2]->prev_v = cur_adr; 5426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr2[3] != NULL ) 5436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr2[3]->prev_v = cur_adr; 5446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[1] = cur_adr; 5456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 5476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[0] = t; 5496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt1[1] = tn2; 5506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* form root */ 5556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = cvContourArea( contour ); 5566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->pt = pt1[1]; 5586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->sign = 0; 5596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->area = fabs( s ); 5606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->r1 = 0; 5616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->r2 = 0; 5626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->next_v1 = ptr1[0]; 5636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->next_v2 = ptr1[1]; 5646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_root->prev_v = NULL; 5656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[0]->prev_v = (_CvTrianAttr *) tree_root; 5676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr1[1]->prev_v = (_CvTrianAttr *) tree_root; 5686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* write binary tree root */ 5706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* CV_WRITE_SEQ_ELEM (tree_one, start_writer); */ 5716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_tree++; 5726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* create Sequence hearder */ 5736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvSeq **) tree) = cvEndWriteSeq( &writer ); 5746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* write points for the main segment into sequence header */ 5756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (*tree)->p1 = pt1[0]; 5766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn M_END: 5786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &ptr_n ); 5806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &ptr_p ); 5816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &num_n ); 5826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &num_p ); 5836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &pt_n ); 5846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &pt_p ); 5856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return status; 5876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 5886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 5906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn triangle attributes calculations 5926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 5946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 5956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvCalcTriAttr( const CvSeq * contour, CvPoint t2, CvPoint t1, int n1, 5966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint t3, int n3, double *s, double *s_c, 5976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double *h, double *a, double *b ) 5986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 5996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double x13, y13, x12, y12, l_base, nx, ny, qq; 6006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double eps = 1.e-5; 6016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x13 = t3.x - t1.x; 6036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y13 = t3.y - t1.y; 6046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn x12 = t2.x - t1.x; 6056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn y12 = t2.y - t1.y; 6066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn qq = x13 * x13 + y13 * y13; 6076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn l_base = cvSqrt( (float) (qq) ); 6086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( l_base > eps ) 6096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn nx = y13 / l_base; 6116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ny = -x13 / l_base; 6126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *h = nx * x12 + ny * y12; 6146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *s = (*h) * l_base / 2.; 6166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *b = nx * y12 - ny * x12; 6186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *a = l_base; 6206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* calculate interceptive area */ 6216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *s_c = cvContourArea( contour, cvSlice(n1, n3+1)); 6226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *h = 0; 6266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *s = 0; 6276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *s_c = 0; 6286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *b = 0; 6296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *a = 0; 6306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OK; 6336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 6346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*F/////////////////////////////////////////////////////////////////////////////////////// 6366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Name: cvCreateContourTree 6376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Purpose: 6386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Create binary tree representation for the contour 6396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Context: 6406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Parameters: 6416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// contour - pointer to input contour object. 6426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// storage - pointer to the current storage block 6436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// tree - output pointer to the binary tree representation 6446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// threshold - threshold for the binary tree building 6456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// 6466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//F*/ 6476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvContourTree* 6486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvCreateContourTree( const CvSeq* contour, CvMemStorage* storage, double threshold ) 6496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 6506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContourTree* tree = 0; 6516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvCreateContourTree" ); 6536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 6546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IPPI_CALL( icvCreateContourTree( contour, storage, &tree, threshold )); 6566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __CLEANUP__; 6586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 6596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return tree; 6616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 6626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*F/////////////////////////////////////////////////////////////////////////////////////// 6656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Name: icvContourFromContourTree 6666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Purpose: 6676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// reconstracts contour from binary tree representation 6686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Context: 6696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// Parameters: 6706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// tree - pointer to the input binary tree representation 6716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// storage - pointer to the current storage block 6726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// contour - pointer to output contour object. 6736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// criteria - criteria for the definition threshold value 6746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn// for the contour reconstracting (level or precision) 6756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn//F*/ 6766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSeq* 6776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvContourFromContourTree( const CvContourTree* tree, 6786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage, 6796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvTermCriteria criteria ) 6806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 6816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* contour = 0; 6826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvTrianAttr **ptr_buf = 0; /* pointer to the pointer's buffer */ 6836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int *level_buf = 0; 6846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i_buf; 6856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int lpt; 6876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double area_all; 6886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double threshold; 6896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int cur_level; 6906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int level; 6916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int seq_flags; 6926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char log_iter, log_eps; 6936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int out_hearder_size; 6946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvTrianAttr *tree_one = 0, tree_root; /* current vertex */ 6956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqReader reader; 6976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqWriter writer; 6986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME("cvContourFromContourTree"); 7006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 7026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !tree ) 7046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 7056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SEQ_POLYGON_TREE( tree )) 7076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_BADFLAG_ERR ); 7086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn criteria = cvCheckTermCriteria( criteria, 0., 100 ); 7106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lpt = tree->total; 7126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr_buf = NULL; 7136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn level_buf = NULL; 7146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_buf = 0; 7156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_level = 0; 7166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn log_iter = (char) (criteria.type == CV_TERMCRIT_ITER || 7176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS)); 7186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn log_eps = (char) (criteria.type == CV_TERMCRIT_EPS || 7196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (criteria.type == CV_TERMCRIT_ITER + CV_TERMCRIT_EPS)); 7206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( (CvSeq *) tree, &reader, 0 ); 7226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn out_hearder_size = sizeof( CvContour ); 7246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn seq_flags = CV_SEQ_POLYGON; 7266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartWriteSeq( seq_flags, out_hearder_size, sizeof( CvPoint ), storage, &writer ); 7276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr_buf = (_CvTrianAttr **) cvAlloc( lpt * sizeof( _CvTrianAttr * )); 7296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( ptr_buf == NULL ) 7306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR ); 7316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( log_iter ) 7326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn level_buf = (int *) cvAlloc( lpt * (sizeof( int ))); 7346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( level_buf == NULL ) 7366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR_FROM_STATUS( CV_OUTOFMEM_ERR ); 7376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn memset( ptr_buf, 0, lpt * sizeof( _CvTrianAttr * )); 7406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* write the first tree root's point as a start point of the result contour */ 7426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( tree->p1, writer ); 7436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* write the second tree root"s point into buffer */ 7446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* read the root of the tree */ 7466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( tree_root, reader ); 7476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one = &tree_root; 7496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn area_all = tree_one->area; 7506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( log_eps ) 7526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn threshold = criteria.epsilon * area_all; 7536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 7546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn threshold = 10 * area_all; 7556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( log_iter ) 7576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn level = criteria.max_iter; 7586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 7596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn level = -1; 7606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* contour from binary tree constraction */ 7626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( i_buf >= 0 ) 7636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( tree_one != NULL && (cur_level <= level || tree_one->area >= threshold) ) 7656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* go to left sub tree for the vertex and save pointer to the right vertex */ 7666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* into the buffer */ 7676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ptr_buf[i_buf] = tree_one; 7696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( log_iter ) 7706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn level_buf[i_buf] = cur_level; 7726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_level++; 7736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_buf++; 7756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one = tree_one->next_v1; 7766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 7786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i_buf--; 7806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i_buf >= 0 ) 7816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt = ptr_buf[i_buf]->pt; 7836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( pt, writer ); 7846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn tree_one = ptr_buf[i_buf]->next_v2; 7856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( log_iter ) 7866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cur_level = level_buf[i_buf] + 1; 7886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn contour = cvEndWriteSeq( &writer ); 7946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvBoundingRect( contour, 1 ); 7956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __CLEANUP__; 7976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 7986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &level_buf ); 8006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &ptr_buf ); 8016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return contour; 8036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 8046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 805