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