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/****************************************************************************************\ 446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Chain Approximation * 456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renntypedef struct _CvPtInfo 486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt; 506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int k; /* support region */ 516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int s; /* curvature value */ 526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn struct _CvPtInfo *next; 536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn_CvPtInfo; 556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* curvature: 0 - 1-curvature, 1 - k-cosine curvature. */ 586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCvStatus 596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvApproximateChainTC89( CvChain* chain, 606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int header_size, 616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage, 626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq** contour, 636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int method ) 646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn static const int abs_diff[] = { 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1 }; 666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char local_buffer[1 << 16]; 686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn char* buffer = local_buffer; 696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int buffer_size; 706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvPtInfo temp; 726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn _CvPtInfo *array, *first = 0, *current = 0, *prev_current = 0; 736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i, j, i1, i2, s, len; 746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int count; 756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvChainPtReader reader; 776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqWriter writer; 786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt = chain->origin; 796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( chain && contour && buffer ); 816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer_size = (chain->total + 8) * sizeof( _CvPtInfo ); 836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *contour = 0; 856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SEQ_CHAIN_CONTOUR( chain )) 876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADFLAG_ERR; 886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size < (int)sizeof(CvContour) ) 906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_BADSIZE_ERR; 916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartWriteSeq( (chain->flags & ~CV_SEQ_ELTYPE_MASK) | CV_SEQ_ELTYPE_POINT, 936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn header_size, sizeof( CvPoint ), storage, &writer ); 946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( chain->total == 0 ) 966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( pt, writer ); 986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn goto exit_function; 996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadChainPoints( chain, &reader ); 1026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method > CV_CHAIN_APPROX_SIMPLE && buffer_size > (int)sizeof(local_buffer)) 1046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn buffer = (char *) cvAlloc( buffer_size ); 1066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !buffer ) 1076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OUTOFMEM_ERR; 1086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array = (_CvPtInfo *) buffer; 1116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = chain->total; 1126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp.next = 0; 1146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = &temp; 1156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Pass 0. 1176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Restores all the digital curve points from the chain code. 1186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Removes the points (from the resultant polygon) 1196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn that have zero 1-curvature */ 1206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < count; i++ ) 1216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int prev_code = *reader.prev_elem; 1236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn reader.prev_elem = reader.ptr; 1256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_CHAIN_POINT( pt, reader ); 1266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* calc 1-curvature */ 1286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = abs_diff[reader.code - prev_code + 7]; 1296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method <= CV_CHAIN_APPROX_SIMPLE ) 1316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method == CV_CHAIN_APPROX_NONE || s != 0 ) 1336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( pt, writer ); 1356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 1386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( s != 0 ) 1406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = current->next = array + i; 1416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[i].s = s; 1426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[i].pt = pt; 1436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn //assert( pt.x == chain->origin.x && pt.y == chain->origin.y ); 1476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method <= CV_CHAIN_APPROX_SIMPLE ) 1496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn goto exit_function; 1506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current->next = 0; 1526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn len = i; 1546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = temp.next; 1556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( current ); 1576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Pass 1. 1596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Determines support region for all the remained points */ 1606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 1616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint pt0; 1636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int k, l = 0, d_num = 0; 1646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(current - array); 1666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt0 = array[i].pt; 1676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* determine support region */ 1696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( k = 1;; k++ ) 1706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 1716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int lk, dk_num; 1726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dx, dy; 1736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Cv32suf d; 1746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( k <= len ); 1766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* calc indices */ 1786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = i - k; 1796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 += i1 < 0 ? len : 0; 1806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 = i + k; 1816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 -= i2 >= len ? len : 0; 1826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = array[i2].pt.x - array[i1].pt.x; 1846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = array[i2].pt.y - array[i1].pt.y; 1856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* distance between p_(i - k) and p_(i + k) */ 1876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn lk = dx * dx + dy * dy; 1886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* distance between p_i and the line (p_(i-k), p_(i+k)) */ 1906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dk_num = (pt0.x - array[i1].pt.x) * dy - (pt0.y - array[i1].pt.y) * dx; 1916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d.f = (float) (((double) d_num) * lk - ((double) dk_num) * l); 1926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( k > 1 && (l >= lk || ((d_num > 0 && d.i <= 0) || (d_num < 0 && d.i >= 0)))) 1946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 1956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 1966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn d_num = dk_num; 1976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn l = lk; 1986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 1996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current->k = --k; 2016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* determine cosine curvature if it should be used */ 2036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method == CV_CHAIN_APPROX_TC89_KCOS ) 2046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* calc k-cosine curvature */ 2066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = k, s = 0; j > 0; j-- ) 2076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double temp_num; 2096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dx1, dy1, dx2, dy2; 2106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Cv32suf sk; 2116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = i - j; 2136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 += i1 < 0 ? len : 0; 2146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 = i + j; 2156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 -= i2 >= len ? len : 0; 2166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx1 = array[i1].pt.x - pt0.x; 2186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy1 = array[i1].pt.y - pt0.y; 2196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx2 = array[i2].pt.x - pt0.x; 2206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy2 = array[i2].pt.y - pt0.y; 2216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (dx1 | dy1) == 0 || (dx2 | dy2) == 0 ) 2236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp_num = dx1 * dx2 + dy1 * dy2; 2266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp_num = 2276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (float) (temp_num / 2286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sqrt( ((double)dx1 * dx1 + (double)dy1 * dy1) * 2296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn ((double)dx2 * dx2 + (double)dy2 * dy2) )); 2306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sk.f = (float) (temp_num + 1.1); 2316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( 0 <= sk.f && sk.f <= 2.2 ); 2336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j < k && sk.i <= s ) 2346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = sk.i; 2376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current->s = s; 2396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = current->next; 2416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( current != 0 ); 2436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current = &temp; 2456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = temp.next; 2466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Pass 2. 2486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Performs non-maxima supression */ 2496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 2506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int k2 = current->k >> 1; 2526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = current->s; 2546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(current - array); 2556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 1; j <= k2; j++ ) 2576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 = i - j; 2596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 += i2 < 0 ? len : 0; 2606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( array[i2].s > s ) 2626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 = i + j; 2656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 -= i2 >= len ? len : 0; 2666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( array[i2].s > s ) 2686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 2696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( j <= k2 ) /* exclude point */ 2726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current->next = current->next; 2746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current->s = 0; /* "clear" point */ 2756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 2776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current = current; 2786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = current->next; 2796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 2806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( current != 0 ); 2816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Pass 3. 2836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Removes non-dominant points with 1-length support region */ 2846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = temp.next; 2856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( current ); 2866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current = &temp; 2876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 2896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( current->k == 1 ) 2916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 2926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn s = current->s; 2936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i = (int)(current - array); 2946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = i - 1; 2966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 += i1 < 0 ? len : 0; 2976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 2986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 = i + 1; 2996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2 -= i2 >= len ? len : 0; 3006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( s <= array[i1].s || s <= array[i2].s ) 3026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current->next = current->next; 3046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current->s = 0; 3056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current = current; 3086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current = current; 3116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = current->next; 3126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( current != 0 ); 3146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method == CV_CHAIN_APPROX_TC89_KCOS ) 3166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn goto copy_vect; 3176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* Pass 4. 3196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn Cleans remained couples of points */ 3206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( temp.next ); 3216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( array[0].s != 0 && array[len - 1].s != 0 ) /* specific case */ 3236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i1 = 1; i1 < len && array[i1].s != 0; i1++ ) 3256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[i1 - 1].s = 0; 3276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i1 == len ) 3296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn goto copy_vect; /* all points survived */ 3306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1--; 3316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i2 = len - 2; i2 > 0 && array[i2].s != 0; i2-- ) 3336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[i2].next = 0; 3356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[i2 + 1].s = 0; 3366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i2++; 3386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( i1 == 0 && i2 == len - 1 ) /* only two points */ 3406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i1 = (int)(array[0].next - array); 3426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[len] = array[0]; /* move to the end */ 3436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[len].next = 0; 3446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array[len - 1].next = array + len; 3456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp.next = array + i1; 3476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = temp.next; 3506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = prev_current = &temp; 3516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = 1; 3526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* do last pass */ 3546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 3556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( current->next == 0 || current->next - current != 1 ) 3576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( count >= 2 ) 3596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( count == 2 ) 3616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int s1 = prev_current->s; 3636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int s2 = current->s; 3646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( s1 > s2 || (s1 == s2 && prev_current->k <= current->k) ) 3666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* remove second */ 3676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current->next = current->next; 3686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* remove first */ 3706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first->next = current; 3716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first->next->next = current; 3746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn first = current; 3766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count = 1; 3776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 3796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn count++; 3806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_current = current; 3816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = current->next; 3826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( current != 0 ); 3846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn copy_vect: 3866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* gather points */ 3886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = temp.next; 3896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( current ); 3906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn do 3926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 3936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( current->pt, writer ); 3946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn current = current->next; 3956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 3966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( current != 0 ); 3976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 3986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennexit_function: 3996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *contour = cvEndWriteSeq( &writer ); 4016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( writer.seq->total > 0 ); 4036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( buffer != local_buffer ) 4056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvFree( &buffer ); 4066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OK; 4076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 4086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/*Applies some approximation algorithm to chain-coded contour(s) and 4116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn converts it/them to polygonal representation */ 4126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSeq* 4136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvApproxChains( CvSeq* src_seq, 4146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage, 4156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int method, 4166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double /*parameter*/, 4176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int minimal_perimeter, 4186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int recursive ) 4196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 4206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *prev_contour = 0, *parent = 0; 4216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *dst_seq = 0; 4226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvApproxChains" ); 4246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 4266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !src_seq || !storage ) 4286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "" ); 4296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method > CV_CHAIN_APPROX_TC89_KCOS || method <= 0 || minimal_perimeter < 0 ) 4306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "" ); 4316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( src_seq != 0 ) 4336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int len = src_seq->total; 4356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( len >= minimal_perimeter ) 4376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *contour; 4396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch( method ) 4416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_CHAIN_APPROX_NONE: 4436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_CHAIN_APPROX_SIMPLE: 4446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_CHAIN_APPROX_TC89_L1: 4456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_CHAIN_APPROX_TC89_KCOS: 4466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IPPI_CALL( icvApproximateChainTC89( (CvChain *) src_seq, 4476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn sizeof( CvContour ), storage, 4486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn (CvSeq**)&contour, method )); 4496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 4516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert(0); 4526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "" ); 4536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( contour ); 4566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( contour->total > 0 ) 4586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvBoundingRect( contour, 1 ); 4606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn contour->v_prev = parent; 4626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn contour->h_prev = prev_contour; 4636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( prev_contour ) 4656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour->h_next = contour; 4666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( parent ) 4676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent->v_next = contour; 4686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour = contour; 4696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !dst_seq ) 4706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_seq = prev_contour; 4716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else /* if resultant contour has zero length, skip it */ 4736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn len = -1; 4756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !recursive ) 4796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 4816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_seq->v_next && len >= minimal_perimeter ) 4826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( prev_contour != 0 ); 4846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent = prev_contour; 4856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour = 0; 4866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = src_seq->v_next; 4876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 4896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( src_seq->h_next == 0 ) 4916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 4926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = src_seq->v_prev; 4936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_seq == 0 ) 4946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 4956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour = parent; 4966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( parent ) 4976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent = parent->v_prev; 4986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 4996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_seq ) 5006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = src_seq->h_next; 5016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 5056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return dst_seq; 5076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 5086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/****************************************************************************************\ 5116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn* Polygonal Approximation * 5126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn\****************************************************************************************/ 5136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* Ramer-Douglas-Peucker algorithm for polygon simplification */ 5156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* the version for integer point coordinates */ 5176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 5186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvApproxPolyDP_32s( CvSeq* src_contour, int header_size, 5196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage, 5206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq** dst_contour, float eps ) 5216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 5226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int init_iters = 3; 5236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSlice slice = {0, 0}, right_slice = {0, 0}; 5246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqReader reader, reader2; 5256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqWriter writer; 5266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint start_pt = {INT_MIN, INT_MIN}, end_pt = {0, 0}, pt = {0,0}; 5276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i = 0, j, count = src_contour->total, new_count; 5286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int is_closed = CV_IS_SEQ_CLOSED( src_contour ); 5296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int le_eps = 0; 5306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* temp_storage = 0; 5316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* stack = 0; 5326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( CV_SEQ_ELTYPE(src_contour) == CV_32SC2 ); 5346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartWriteSeq( src_contour->flags, header_size, sizeof(pt), storage, &writer ); 5356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_contour->total == 0 ) 5376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *dst_contour = cvEndWriteSeq( &writer ); 5396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OK; 5406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp_storage = cvCreateChildMemStorage( storage ); 5436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( src_contour->first != 0 ); 5456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn stack = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSlice), temp_storage ); 5466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn eps *= eps; 5476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( src_contour, &reader, 0 ); 5486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !is_closed ) 5506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = count; 5526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_pt = *(CvPoint*)(reader.ptr); 5536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start_pt = *(CvPoint*)cvGetSeqElem( src_contour, -1 ); 5546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( start_pt.x != end_pt.x || start_pt.y != end_pt.y ) 5566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.start_index = 0; 5586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.end_index = count - 1; 5596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &slice ); 5606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 5626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_closed = 1; 5646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn init_iters = 1; 5656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( is_closed ) 5696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* 1. Find approximately two farthest points of the contour */ 5716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = 0; 5726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < init_iters; i++ ) 5746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int max_dist = 0; 5766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, right_slice.start_index, 1 ); 5776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); /* read the first point */ 5786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 1; j < count; j++ ) 5806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dx, dy, dist; 5826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 5846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt.x - start_pt.x; 5856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt.y - start_pt.y; 5866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = dx * dx + dy * dy; 5886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist > max_dist ) 5906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 5916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_dist = dist; 5926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = j; 5936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn le_eps = max_dist <= eps; 5976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 5986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 5996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* 2. initialize the stack */ 6006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !le_eps ) 6016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.start_index = cvGetSeqReaderPos( &reader ); 6036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.end_index = right_slice.start_index += slice.start_index; 6046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index -= right_slice.start_index >= count ? count : 0; 6066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.end_index = slice.start_index; 6076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_slice.end_index < right_slice.start_index ) 6086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.end_index += count; 6096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &right_slice ); 6116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &slice ); 6126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( start_pt, writer ); 6156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* 3. run recursive process */ 6186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( stack->total != 0 ) 6196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPop( stack, &slice ); 6216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, slice.end_index ); 6236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( end_pt, reader ); 6246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, slice.start_index ); 6266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); 6276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( slice.end_index > slice.start_index + 1 ) 6296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dx, dy, dist, max_dist = 0; 6316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = end_pt.x - start_pt.x; 6336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = end_pt.y - start_pt.y; 6346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( dx != 0 || dy != 0 ); 6366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = slice.start_index + 1; i < slice.end_index; i++ ) 6386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 6406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = abs((pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy); 6416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist > max_dist ) 6436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_dist = dist; 6456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = i; 6466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn le_eps = (double)max_dist * max_dist <= eps * ((double)dx * dx + (double)dy * dy); 6506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( slice.end_index > slice.start_index ); 6546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn le_eps = 1; 6556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* read starting point */ 6566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, slice.start_index ); 6576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); 6586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( le_eps ) 6616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( start_pt, writer ); 6636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 6656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.end_index = slice.end_index; 6676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.end_index = right_slice.start_index; 6686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &right_slice ); 6696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &slice ); 6706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 6726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_closed = CV_IS_SEQ_CLOSED( src_contour ); 6746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !is_closed ) 6756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( end_pt, writer ); 6766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *dst_contour = cvEndWriteSeq( &writer ); 6786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( *dst_contour, &reader, is_closed ); 6806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); 6816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn reader2 = reader; 6836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 6846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_count = count = (*dst_contour)->total; 6866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = !is_closed; i < count - !is_closed && new_count > 2; i++ ) 6876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int dx, dy, dist; 6896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( end_pt, reader ); 6906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 6916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = end_pt.x - start_pt.x; 6926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = end_pt.y - start_pt.y; 6936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = abs((pt.x - start_pt.x)*dy - (pt.y - start_pt.y)*dx); 6946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (double)dist * dist <= 0.5*eps*((double)dx*dx + (double)dy*dy) && dx != 0 && dy != 0 ) 6956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 6966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_count--; 6976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvPoint*)reader2.ptr) = start_pt = end_pt; 6986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 ); 6996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 7006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i++; 7016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 7026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvPoint*)reader2.ptr) = start_pt = pt; 7046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 ); 7056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt = end_pt; 7066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !is_closed ) 7096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvPoint*)reader2.ptr) = pt; 7106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( new_count < count ) 7126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPopMulti( *dst_contour, 0, count - new_count ); 7136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 7156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OK; 7176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 7186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* the version for integer point coordinates */ 7216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Rennstatic CvStatus 7226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennicvApproxPolyDP_32f( CvSeq* src_contour, int header_size, 7236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage, 7246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq** dst_contour, float eps ) 7256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 7266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int init_iters = 3; 7276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSlice slice = {0, 0}, right_slice = {0, 0}; 7286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqReader reader, reader2; 7296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqWriter writer; 7306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvPoint2D32f start_pt = {-1e6f, -1e6f}, end_pt = {0, 0}, pt = {0,0}; 7316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int i = 0, j, count = src_contour->total, new_count; 7326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int is_closed = CV_IS_SEQ_CLOSED( src_contour ); 7336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int le_eps = 0; 7346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* temp_storage = 0; 7356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* stack = 0; 7366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( CV_SEQ_ELTYPE(src_contour) == CV_32FC2 ); 7386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartWriteSeq( src_contour->flags, header_size, sizeof(pt), storage, &writer ); 7396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_contour->total == 0 ) 7416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *dst_contour = cvEndWriteSeq( &writer ); 7436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OK; 7446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn temp_storage = cvCreateChildMemStorage( storage ); 7476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( src_contour->first != 0 ); 7496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn stack = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSlice), temp_storage ); 7506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn eps *= eps; 7516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( src_contour, &reader, 0 ); 7526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !is_closed ) 7546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = count; 7566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn end_pt = *(CvPoint2D32f*)(reader.ptr); 7576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn start_pt = *(CvPoint2D32f*)cvGetSeqElem( src_contour, -1 ); 7586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( fabs(start_pt.x - end_pt.x) > FLT_EPSILON || 7606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn fabs(start_pt.y - end_pt.y) > FLT_EPSILON ) 7616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.start_index = 0; 7636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.end_index = count - 1; 7646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &slice ); 7656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 7676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_closed = 1; 7696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn init_iters = 1; 7706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( is_closed ) 7746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* 1. Find approximately two farthest points of the contour */ 7766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = 0; 7776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = 0; i < init_iters; i++ ) 7796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double max_dist = 0; 7816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, right_slice.start_index, 1 ); 7826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); /* read the first point */ 7836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( j = 1; j < count; j++ ) 7856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double dx, dy, dist; 7876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 7896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = pt.x - start_pt.x; 7906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = pt.y - start_pt.y; 7916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = dx * dx + dy * dy; 7936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 7946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist > max_dist ) 7956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 7966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_dist = dist; 7976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = j; 7986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 7996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn le_eps = max_dist <= eps; 8026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* 2. initialize the stack */ 8056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !le_eps ) 8066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.start_index = cvGetSeqReaderPos( &reader ); 8086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.end_index = right_slice.start_index += slice.start_index; 8096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index -= right_slice.start_index >= count ? count : 0; 8116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.end_index = slice.start_index; 8126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( right_slice.end_index < right_slice.start_index ) 8136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.end_index += count; 8146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &right_slice ); 8166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &slice ); 8176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( start_pt, writer ); 8206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* 3. run recursive process */ 8236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( stack->total != 0 ) 8246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPop( stack, &slice ); 8266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, slice.end_index ); 8286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( end_pt, reader ); 8296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, slice.start_index ); 8316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); 8326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( slice.end_index > slice.start_index + 1 ) 8346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double dx, dy, dist, max_dist = 0; 8366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = end_pt.x - start_pt.x; 8386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = end_pt.y - start_pt.y; 8396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( dx != 0 || dy != 0 ); 8416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = slice.start_index + 1; i < slice.end_index; i++ ) 8436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 8456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = fabs((pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy); 8466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( dist > max_dist ) 8486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn max_dist = dist; 8506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.start_index = i; 8516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn le_eps = (double)max_dist * max_dist <= eps * ((double)dx * dx + (double)dy * dy); 8556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( slice.end_index > slice.start_index ); 8596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn le_eps = 1; 8606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn /* read starting point */ 8616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSetSeqReaderPos( &reader, slice.start_index ); 8626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); 8636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( le_eps ) 8666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( start_pt, writer ); 8686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 8706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn right_slice.end_index = slice.end_index; 8726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn slice.end_index = right_slice.start_index; 8736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &right_slice ); 8746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPush( stack, &slice ); 8756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 8776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn is_closed = CV_IS_SEQ_CLOSED( src_contour ); 8796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !is_closed ) 8806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_WRITE_SEQ_ELEM( end_pt, writer ); 8816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *dst_contour = cvEndWriteSeq( &writer ); 8836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvStartReadSeq( *dst_contour, &reader, is_closed ); 8856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( start_pt, reader ); 8866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn reader2 = reader; 8886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 8896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_count = count = (*dst_contour)->total; 8916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn for( i = !is_closed; i < count - !is_closed && new_count > 2; i++ ) 8926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 8936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double dx, dy, dist; 8946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( end_pt, reader ); 8956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 8966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dx = end_pt.x - start_pt.x; 8976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dy = end_pt.y - start_pt.y; 8986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dist = fabs((pt.x - start_pt.x)*dy - (pt.y - start_pt.y)*dx); 8996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( (double)dist * dist <= 0.5*eps*((double)dx*dx + (double)dy*dy) ) 9006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn new_count--; 9026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvPoint2D32f*)reader2.ptr) = start_pt = end_pt; 9036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 ); 9046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_READ_SEQ_ELEM( pt, reader ); 9056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn i++; 9066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn continue; 9076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvPoint2D32f*)reader2.ptr) = start_pt = pt; 9096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 ); 9106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn pt = end_pt; 9116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !is_closed ) 9146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn *((CvPoint2D32f*)reader2.ptr) = pt; 9156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( new_count < count ) 9176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvSeqPopMulti( *dst_contour, 0, count - new_count ); 9186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvReleaseMemStorage( &temp_storage ); 9206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return CV_OK; 9226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 9236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RennCV_IMPL CvSeq* 9266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius RenncvApproxPoly( const void* array, int header_size, 9276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvMemStorage* storage, int method, 9286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn double parameter, int parameter2 ) 9296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn{ 9306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* dst_seq = 0; 9316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *prev_contour = 0, *parent = 0; 9326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvContour contour_header; 9336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq* src_seq = 0; 9346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeqBlock block; 9356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn int recursive = 0; 9366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_FUNCNAME( "cvApproxPoly" ); 9386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __BEGIN__; 9406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_SEQ( array )) 9426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = (CvSeq*)array; 9446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SEQ_POLYLINE( src_seq )) 9456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Unsupported sequence type" ); 9466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn recursive = parameter2; 9486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !storage ) 9506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn storage = src_seq->storage; 9516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 9536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_CALL( src_seq = cvPointSeqFromMat( 9556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_SEQ_KIND_CURVE | (parameter2 ? CV_SEQ_FLAG_CLOSED : 0), 9566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn array, &contour_header, &block )); 9576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !storage ) 9606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsNullPtr, "NULL storage pointer " ); 9616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size < 0 ) 9636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "header_size is negative. " 9646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "Pass 0 to make the destination header_size == input header_size" ); 9656acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9666acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size == 0 ) 9676acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn header_size = src_seq->header_size; 9686acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9696acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !CV_IS_SEQ_POLYLINE( src_seq )) 9706acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9716acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_IS_SEQ_CHAIN( src_seq )) 9726acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9736acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Input curves are not polygonal. " 9746acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn "Use cvApproxChains first" ); 9756acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9766acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 9776acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9786acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Input curves have uknown type" ); 9796acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9806acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 9816acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9826acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size == 0 ) 9836acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn header_size = src_seq->header_size; 9846acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9856acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size < (int)sizeof(CvContour) ) 9866acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadSize, "New header size must be non-less than sizeof(CvContour)" ); 9876acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9886acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( method != CV_POLY_APPROX_DP ) 9896acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "Unknown approximation method" ); 9906acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9916acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( src_seq != 0 ) 9926acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9936acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CvSeq *contour = 0; 9946acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 9956acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn switch (method) 9966acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 9976acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn case CV_POLY_APPROX_DP: 9986acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( parameter < 0 ) 9996acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsOutOfRange, "Accuracy must be non-negative" ); 10006acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10016acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( CV_SEQ_ELTYPE(src_seq) == CV_32SC2 ) 10026acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10036acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IPPI_CALL( icvApproxPolyDP_32s( src_seq, header_size, storage, 10046acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &contour, (float)parameter )); 10056acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10066acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 10076acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10086acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn IPPI_CALL( icvApproxPolyDP_32f( src_seq, header_size, storage, 10096acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn &contour, (float)parameter )); 10106acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10116acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 10126acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn default: 10136acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert(0); 10146acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn CV_ERROR( CV_StsBadArg, "Invalid approximation method" ); 10156acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10166acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10176acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( contour ); 10186acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10196acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( header_size >= (int)sizeof(CvContour)) 10206acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn cvBoundingRect( contour, 1 ); 10216acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10226acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn contour->v_prev = parent; 10236acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn contour->h_prev = prev_contour; 10246acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10256acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( prev_contour ) 10266acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour->h_next = contour; 10276acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else if( parent ) 10286acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent->v_next = contour; 10296acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour = contour; 10306acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !dst_seq ) 10316acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn dst_seq = prev_contour; 10326acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10336acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( !recursive ) 10346acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 10356acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10366acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_seq->v_next ) 10376acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10386acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn assert( prev_contour != 0 ); 10396acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent = prev_contour; 10406acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour = 0; 10416acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = src_seq->v_next; 10426acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10436acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn else 10446acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10456acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn while( src_seq->h_next == 0 ) 10466acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn { 10476acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = src_seq->v_prev; 10486acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_seq == 0 ) 10496acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn break; 10506acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn prev_contour = parent; 10516acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( parent ) 10526acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn parent = parent->v_prev; 10536acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10546acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn if( src_seq ) 10556acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn src_seq = src_seq->h_next; 10566acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10576acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn } 10586acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10596acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn __END__; 10606acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10616acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn return dst_seq; 10626acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn} 10636acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn 10646acb9a7ea3d7564944e12cbc73a857b88c1301eeMarius Renn/* End of file. */ 1065