approx.cpp

00001 /*M///////////////////////////////////////////////////////////////////////////////////////
00002 //
00003 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
00004 //
00005 //  By downloading, copying, installing or using the software you agree to this license.
00006 //  If you do not agree to this license, do not download, install,
00007 //  copy or use the software.
00008 //
00009 //
00010 //                        Intel License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000, Intel Corporation, all rights reserved.
00014 // Third party copyrights are property of their respective owners.
00015 //
00016 // Redistribution and use in source and binary forms, with or without modification,
00017 // are permitted provided that the following conditions are met:
00018 //
00019 //   * Redistribution's of source code must retain the above copyright notice,
00020 //     this list of conditions and the following disclaimer.
00021 //
00022 //   * Redistribution's in binary form must reproduce the above copyright notice,
00023 //     this list of conditions and the following disclaimer in the documentation
00024 //     and/or other materials provided with the distribution.
00025 //
00026 //   * The name of Intel Corporation may not be used to endorse or promote products
00027 //     derived from this software without specific prior written permission.
00028 //
00029 // This software is provided by the copyright holders and contributors "as is" and
00030 // any express or implied warranties, including, but not limited to, the implied
00031 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00032 // In no event shall the Intel Corporation or contributors be liable for any direct,
00033 // indirect, incidental, special, exemplary, or consequential damages
00034 // (including, but not limited to, procurement of substitute goods or services;
00035 // loss of use, data, or profits; or business interruption) however caused
00036 // and on any theory of liability, whether in contract, strict liability,
00037 // or tort (including negligence or otherwise) arising in any way out of
00038 // the use of this software, even if advised of the possibility of such damage.
00039 //
00040 //M*/
00041 #include "precomp.hpp"
00042 
00043 /****************************************************************************************\
00044 *                                  Chain Approximation                                   *
00045 \****************************************************************************************/
00046 
00047 typedef struct _CvPtInfo
00048 {
00049     CvPoint pt;
00050     int k;                      /* support region */
00051     int s;                      /* curvature value */
00052     struct _CvPtInfo *next;
00053 }
00054 _CvPtInfo;
00055 
00056 
00057 /* curvature: 0 - 1-curvature, 1 - k-cosine curvature. */
00058 CvSeq* icvApproximateChainTC89( CvChain* chain, int header_size,
00059                                 CvMemStorage* storage, int method )
00060 {
00061     static const int abs_diff[] = { 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1 };
00062 
00063     cv::AutoBuffer<_CvPtInfo> buf(chain->total + 8);
00064 
00065     _CvPtInfo       temp;
00066     _CvPtInfo       *array = buf, *first = 0, *current = 0, *prev_current = 0;
00067     int             i, j, i1, i2, s, len;
00068     int             count = chain->total;
00069 
00070     CvChainPtReader reader;
00071     CvSeqWriter     writer;
00072     CvPoint         pt = chain->origin;
00073 
00074     CV_Assert( CV_IS_SEQ_CHAIN_CONTOUR( chain ));
00075     CV_Assert( header_size >= (int)sizeof(CvContour) );
00076 
00077     cvStartWriteSeq( (chain->flags & ~CV_SEQ_ELTYPE_MASK) | CV_SEQ_ELTYPE_POINT,
00078                      header_size, sizeof( CvPoint ), storage, &writer );
00079 
00080     if( chain->total == 0 )
00081     {
00082         CV_WRITE_SEQ_ELEM( pt, writer );
00083         return cvEndWriteSeq( &writer );
00084     }
00085 
00086     cvStartReadChainPoints( chain, &reader );
00087 
00088     temp.next = 0;
00089     current = &temp;
00090 
00091     /* Pass 0.
00092        Restores all the digital curve points from the chain code.
00093        Removes the points (from the resultant polygon)
00094        that have zero 1-curvature */
00095     for( i = 0; i < count; i++ )
00096     {
00097         int prev_code = *reader.prev_elem;
00098 
00099         reader.prev_elem = reader.ptr;
00100         CV_READ_CHAIN_POINT( pt, reader );
00101 
00102         /* calc 1-curvature */
00103         s = abs_diff[reader.code - prev_code + 7];
00104 
00105         if( method <= CV_CHAIN_APPROX_SIMPLE )
00106         {
00107             if( method == CV_CHAIN_APPROX_NONE || s != 0 )
00108             {
00109                 CV_WRITE_SEQ_ELEM( pt, writer );
00110             }
00111         }
00112         else
00113         {
00114             if( s != 0 )
00115                 current = current->next = array + i;
00116             array[i].s = s;
00117             array[i].pt = pt;
00118         }
00119     }
00120 
00121     //assert( pt.x == chain->origin.x && pt.y == chain->origin.y );
00122 
00123     if( method <= CV_CHAIN_APPROX_SIMPLE )
00124         return cvEndWriteSeq( &writer );
00125 
00126     current->next = 0;
00127 
00128     len = i;
00129     current = temp.next;
00130 
00131     assert( current );
00132 
00133     /* Pass 1.
00134        Determines support region for all the remained points */
00135     do
00136     {
00137         CvPoint pt0;
00138         int k, l = 0, d_num = 0;
00139 
00140         i = (int)(current - array);
00141         pt0 = array[i].pt;
00142 
00143         /* determine support region */
00144         for( k = 1;; k++ )
00145         {
00146             int lk, dk_num;
00147             int dx, dy;
00148             Cv32suf d;
00149 
00150             assert( k <= len );
00151 
00152             /* calc indices */
00153             i1 = i - k;
00154             i1 += i1 < 0 ? len : 0;
00155             i2 = i + k;
00156             i2 -= i2 >= len ? len : 0;
00157 
00158             dx = array[i2].pt.x - array[i1].pt.x;
00159             dy = array[i2].pt.y - array[i1].pt.y;
00160 
00161             /* distance between p_(i - k) and p_(i + k) */
00162             lk = dx * dx + dy * dy;
00163 
00164             /* distance between p_i and the line (p_(i-k), p_(i+k)) */
00165             dk_num = (pt0.x - array[i1].pt.x) * dy - (pt0.y - array[i1].pt.y) * dx;
00166             d.f = (float) (((double) d_num) * lk - ((double) dk_num) * l);
00167 
00168             if( k > 1 && (l >= lk || ((d_num > 0 && d.i <= 0) || (d_num < 0 && d.i >= 0))))
00169                 break;
00170 
00171             d_num = dk_num;
00172             l = lk;
00173         }
00174 
00175         current->k = --k;
00176 
00177         /* determine cosine curvature if it should be used */
00178         if( method == CV_CHAIN_APPROX_TC89_KCOS )
00179         {
00180             /* calc k-cosine curvature */
00181             for( j = k, s = 0; j > 0; j-- )
00182             {
00183                 double temp_num;
00184                 int dx1, dy1, dx2, dy2;
00185                 Cv32suf sk;
00186 
00187                 i1 = i - j;
00188                 i1 += i1 < 0 ? len : 0;
00189                 i2 = i + j;
00190                 i2 -= i2 >= len ? len : 0;
00191 
00192                 dx1 = array[i1].pt.x - pt0.x;
00193                 dy1 = array[i1].pt.y - pt0.y;
00194                 dx2 = array[i2].pt.x - pt0.x;
00195                 dy2 = array[i2].pt.y - pt0.y;
00196 
00197                 if( (dx1 | dy1) == 0 || (dx2 | dy2) == 0 )
00198                     break;
00199 
00200                 temp_num = dx1 * dx2 + dy1 * dy2;
00201                 temp_num =
00202                     (float) (temp_num /
00203                              sqrt( ((double)dx1 * dx1 + (double)dy1 * dy1) *
00204                                    ((double)dx2 * dx2 + (double)dy2 * dy2) ));
00205                 sk.f = (float) (temp_num + 1.1);
00206 
00207                 assert( 0 <= sk.f && sk.f <= 2.2 );
00208                 if( j < k && sk.i <= s )
00209                     break;
00210 
00211                 s = sk.i;
00212             }
00213             current->s = s;
00214         }
00215         current = current->next;
00216     }
00217     while( current != 0 );
00218 
00219     prev_current = &temp;
00220     current = temp.next;
00221 
00222     /* Pass 2.
00223        Performs non-maxima suppression */
00224     do
00225     {
00226         int k2 = current->k >> 1;
00227 
00228         s = current->s;
00229         i = (int)(current - array);
00230 
00231         for( j = 1; j <= k2; j++ )
00232         {
00233             i2 = i - j;
00234             i2 += i2 < 0 ? len : 0;
00235 
00236             if( array[i2].s > s )
00237                 break;
00238 
00239             i2 = i + j;
00240             i2 -= i2 >= len ? len : 0;
00241 
00242             if( array[i2].s > s )
00243                 break;
00244         }
00245 
00246         if( j <= k2 )           /* exclude point */
00247         {
00248             prev_current->next = current->next;
00249             current->s = 0;     /* "clear" point */
00250         }
00251         else
00252             prev_current = current;
00253         current = current->next;
00254     }
00255     while( current != 0 );
00256 
00257     /* Pass 3.
00258        Removes non-dominant points with 1-length support region */
00259     current = temp.next;
00260     assert( current );
00261     prev_current = &temp;
00262 
00263     do
00264     {
00265         if( current->k == 1 )
00266         {
00267             s = current->s;
00268             i = (int)(current - array);
00269 
00270             i1 = i - 1;
00271             i1 += i1 < 0 ? len : 0;
00272 
00273             i2 = i + 1;
00274             i2 -= i2 >= len ? len : 0;
00275 
00276             if( s <= array[i1].s || s <= array[i2].s )
00277             {
00278                 prev_current->next = current->next;
00279                 current->s = 0;
00280             }
00281             else
00282                 prev_current = current;
00283         }
00284         else
00285             prev_current = current;
00286         current = current->next;
00287     }
00288     while( current != 0 );
00289 
00290     if( method == CV_CHAIN_APPROX_TC89_KCOS )
00291         goto copy_vect;
00292 
00293     /* Pass 4.
00294        Cleans remained couples of points */
00295     assert( temp.next );
00296 
00297     if( array[0].s != 0 && array[len - 1].s != 0 )      /* specific case */
00298     {
00299         for( i1 = 1; i1 < len && array[i1].s != 0; i1++ )
00300         {
00301             array[i1 - 1].s = 0;
00302         }
00303         if( i1 == len )
00304             goto copy_vect;     /* all points survived */
00305         i1--;
00306 
00307         for( i2 = len - 2; i2 > 0 && array[i2].s != 0; i2-- )
00308         {
00309             array[i2].next = 0;
00310             array[i2 + 1].s = 0;
00311         }
00312         i2++;
00313 
00314         if( i1 == 0 && i2 == len - 1 )  /* only two points */
00315         {
00316             i1 = (int)(array[0].next - array);
00317             array[len] = array[0];      /* move to the end */
00318             array[len].next = 0;
00319             array[len - 1].next = array + len;
00320         }
00321         temp.next = array + i1;
00322     }
00323 
00324     current = temp.next;
00325     first = prev_current = &temp;
00326     count = 1;
00327 
00328     /* do last pass */
00329     do
00330     {
00331         if( current->next == 0 || current->next - current != 1 )
00332         {
00333             if( count >= 2 )
00334             {
00335                 if( count == 2 )
00336                 {
00337                     int s1 = prev_current->s;
00338                     int s2 = current->s;
00339 
00340                     if( s1 > s2 || (s1 == s2 && prev_current->k <= current->k) )
00341                         /* remove second */
00342                         prev_current->next = current->next;
00343                     else
00344                         /* remove first */
00345                         first->next = current;
00346                 }
00347                 else
00348                     first->next->next = current;
00349             }
00350             first = current;
00351             count = 1;
00352         }
00353         else
00354             count++;
00355         prev_current = current;
00356         current = current->next;
00357     }
00358     while( current != 0 );
00359 
00360 copy_vect:
00361 
00362     // gather points
00363     current = temp.next;
00364     assert( current );
00365 
00366     do
00367     {
00368         CV_WRITE_SEQ_ELEM( current->pt, writer );
00369         current = current->next;
00370     }
00371     while( current != 0 );
00372 
00373     return cvEndWriteSeq( &writer );
00374 }
00375 
00376 
00377 /*Applies some approximation algorithm to chain-coded contour(s) and
00378   converts it/them to polygonal representation */
00379 CV_IMPL CvSeq*
00380 cvApproxChains( CvSeq*              src_seq,
00381                 CvMemStorage*       storage,
00382                 int                 method,
00383                 double              /*parameter*/,
00384                 int                 minimal_perimeter,
00385                 int                 recursive )
00386 {
00387     CvSeq *prev_contour = 0, *parent = 0;
00388     CvSeq *dst_seq = 0;
00389 
00390     if( !src_seq || !storage )
00391         CV_Error( CV_StsNullPtr, "" );
00392     if( method > CV_CHAIN_APPROX_TC89_KCOS || method <= 0 || minimal_perimeter < 0 )
00393         CV_Error( CV_StsOutOfRange, "" );
00394 
00395     while( src_seq != 0 )
00396     {
00397         int len = src_seq->total;
00398 
00399         if( len >= minimal_perimeter )
00400         {
00401             CvSeq *contour = 0;
00402 
00403             switch( method )
00404             {
00405             case CV_CHAIN_APPROX_NONE:
00406             case CV_CHAIN_APPROX_SIMPLE:
00407             case CV_CHAIN_APPROX_TC89_L1:
00408             case CV_CHAIN_APPROX_TC89_KCOS:
00409                 contour = icvApproximateChainTC89( (CvChain *) src_seq, sizeof( CvContour ), storage, method );
00410                 break;
00411             default:
00412                 CV_Error( CV_StsOutOfRange, "" );
00413             }
00414 
00415             if( contour->total > 0 )
00416             {
00417                 cvBoundingRect( contour, 1 );
00418 
00419                 contour->v_prev = parent;
00420                 contour->h_prev = prev_contour;
00421 
00422                 if( prev_contour )
00423                     prev_contour->h_next = contour;
00424                 else if( parent )
00425                     parent->v_next = contour;
00426                 prev_contour = contour;
00427                 if( !dst_seq )
00428                     dst_seq = prev_contour;
00429             }
00430             else                /* if resultant contour has zero length, skip it */
00431             {
00432                 len = -1;
00433             }
00434         }
00435 
00436         if( !recursive )
00437             break;
00438 
00439         if( src_seq->v_next && len >= minimal_perimeter )
00440         {
00441             assert( prev_contour != 0 );
00442             parent = prev_contour;
00443             prev_contour = 0;
00444             src_seq = src_seq->v_next;
00445         }
00446         else
00447         {
00448             while( src_seq->h_next == 0 )
00449             {
00450                 src_seq = src_seq->v_prev;
00451                 if( src_seq == 0 )
00452                     break;
00453                 prev_contour = parent;
00454                 if( parent )
00455                     parent = parent->v_prev;
00456             }
00457             if( src_seq )
00458                 src_seq = src_seq->h_next;
00459         }
00460     }
00461 
00462     return dst_seq;
00463 }
00464 
00465 
00466 /****************************************************************************************\
00467 *                               Polygonal Approximation                                  *
00468 \****************************************************************************************/
00469 
00470 /* Ramer-Douglas-Peucker algorithm for polygon simplification */
00471 
00472 namespace cv
00473 {
00474 
00475 template<typename T> static int
00476 approxPolyDP_( const Point_<T>* src_contour, int count0, Point_<T>* dst_contour,
00477               bool is_closed0, double eps, AutoBuffer<Range>* _stack )
00478 {
00479     #define PUSH_SLICE(slice) \
00480         if( top >= stacksz ) \
00481         { \
00482             _stack->resize(stacksz*3/2); \
00483             stack = *_stack; \
00484             stacksz = _stack->size(); \
00485         } \
00486         stack[top++] = slice
00487 
00488     #define READ_PT(pt, pos) \
00489         pt = src_contour[pos]; \
00490         if( ++pos >= count ) pos = 0
00491 
00492     #define READ_DST_PT(pt, pos) \
00493         pt = dst_contour[pos]; \
00494         if( ++pos >= count ) pos = 0
00495 
00496     #define WRITE_PT(pt) \
00497         dst_contour[new_count++] = pt
00498 
00499     typedef cv::Point_<T> PT;
00500     int             init_iters = 3;
00501     Range           slice(0, 0), right_slice(0, 0);
00502     PT              start_pt((T)-1000000, (T)-1000000), end_pt(0, 0), pt(0,0);
00503     int             i = 0, j, pos = 0, wpos, count = count0, new_count=0;
00504     int             is_closed = is_closed0;
00505     bool            le_eps = false;
00506     size_t top = 0, stacksz = _stack->size();
00507     Range*          stack = *_stack;
00508 
00509     if( count == 0  )
00510         return 0;
00511 
00512     eps *= eps;
00513 
00514     if( !is_closed )
00515     {
00516         right_slice.start = count;
00517         end_pt = src_contour[0];
00518         start_pt = src_contour[count-1];
00519 
00520         if( start_pt.x != end_pt.x || start_pt.y != end_pt.y )
00521         {
00522             slice.start = 0;
00523             slice.end = count - 1;
00524             PUSH_SLICE(slice);
00525         }
00526         else
00527         {
00528             is_closed = 1;
00529             init_iters = 1;
00530         }
00531     }
00532 
00533     if( is_closed )
00534     {
00535         // 1. Find approximately two farthest points of the contour
00536         right_slice.start = 0;
00537 
00538         for( i = 0; i < init_iters; i++ )
00539         {
00540             double dist, max_dist = 0;
00541             pos = (pos + right_slice.start) % count;
00542             READ_PT(start_pt, pos);
00543 
00544             for( j = 1; j < count; j++ )
00545             {
00546                 double dx, dy;
00547 
00548                 READ_PT(pt, pos);
00549                 dx = pt.x - start_pt.x;
00550                 dy = pt.y - start_pt.y;
00551 
00552                 dist = dx * dx + dy * dy;
00553 
00554                 if( dist > max_dist )
00555                 {
00556                     max_dist = dist;
00557                     right_slice.start = j;
00558                 }
00559             }
00560 
00561             le_eps = max_dist <= eps;
00562         }
00563 
00564         // 2. initialize the stack
00565         if( !le_eps )
00566         {
00567             right_slice.end = slice.start = pos % count;
00568             slice.end = right_slice.start = (right_slice.start + slice.start) % count;
00569 
00570             PUSH_SLICE(right_slice);
00571             PUSH_SLICE(slice);
00572         }
00573         else
00574             WRITE_PT(start_pt);
00575     }
00576 
00577     // 3. run recursive process
00578     while( top > 0 )
00579     {
00580         slice = stack[--top];
00581         end_pt = src_contour[slice.end];
00582         pos = slice.start;
00583         READ_PT(start_pt, pos);
00584 
00585         if( pos != slice.end )
00586         {
00587             double dx, dy, dist, max_dist = 0;
00588 
00589             dx = end_pt.x - start_pt.x;
00590             dy = end_pt.y - start_pt.y;
00591 
00592             assert( dx != 0 || dy != 0 );
00593 
00594             while( pos != slice.end )
00595             {
00596                 READ_PT(pt, pos);
00597                 dist = fabs((pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy);
00598 
00599                 if( dist > max_dist )
00600                 {
00601                     max_dist = dist;
00602                     right_slice.start = (pos+count-1)%count;
00603                 }
00604             }
00605 
00606             le_eps = max_dist * max_dist <= eps * (dx * dx + dy * dy);
00607         }
00608         else
00609         {
00610             le_eps = true;
00611             // read starting point
00612             start_pt = src_contour[slice.start];
00613         }
00614 
00615         if( le_eps )
00616         {
00617             WRITE_PT(start_pt);
00618         }
00619         else
00620         {
00621             right_slice.end = slice.end;
00622             slice.end = right_slice.start;
00623             PUSH_SLICE(right_slice);
00624             PUSH_SLICE(slice);
00625         }
00626     }
00627 
00628     if( !is_closed )
00629         WRITE_PT( src_contour[count-1] );
00630 
00631     // last stage: do final clean-up of the approximated contour -
00632     // remove extra points on the [almost] stright lines.
00633     is_closed = is_closed0;
00634     count = new_count;
00635     pos = is_closed ? count - 1 : 0;
00636     READ_DST_PT(start_pt, pos);
00637     wpos = pos;
00638     READ_DST_PT(pt, pos);
00639 
00640     for( i = !is_closed; i < count - !is_closed && new_count > 2; i++ )
00641     {
00642         double dx, dy, dist, successive_inner_product;
00643         READ_DST_PT( end_pt, pos );
00644 
00645         dx = end_pt.x - start_pt.x;
00646         dy = end_pt.y - start_pt.y;
00647         dist = fabs((pt.x - start_pt.x)*dy - (pt.y - start_pt.y)*dx);
00648         successive_inner_product = (pt.x - start_pt.x) * (end_pt.x - pt.x) +
00649         (pt.y - start_pt.y) * (end_pt.y - pt.y);
00650 
00651         if( dist * dist <= 0.5*eps*(dx*dx + dy*dy) && dx != 0 && dy != 0 &&
00652            successive_inner_product >= 0 )
00653         {
00654             new_count--;
00655             dst_contour[wpos] = start_pt = end_pt;
00656             if(++wpos >= count) wpos = 0;
00657             READ_DST_PT(pt, pos);
00658             i++;
00659             continue;
00660         }
00661         dst_contour[wpos] = start_pt = pt;
00662         if(++wpos >= count) wpos = 0;
00663         pt = end_pt;
00664     }
00665 
00666     if( !is_closed )
00667         dst_contour[wpos] = pt;
00668 
00669     return new_count;
00670 }
00671 
00672 }
00673 
00674 void cv::approxPolyDP( InputArray _curve, OutputArray _approxCurve,
00675                       double epsilon, bool closed )
00676 {
00677     Mat curve = _curve.getMat();
00678     int npoints = curve.checkVector(2), depth = curve.depth();
00679     CV_Assert( npoints >= 0 && (depth == CV_32S || depth == CV_32F));
00680 
00681     if( npoints == 0 )
00682     {
00683         _approxCurve.release();
00684         return;
00685     }
00686 
00687     AutoBuffer<Point> _buf(npoints);
00688     AutoBuffer<Range> _stack(npoints);
00689     Point* buf = _buf;
00690     int nout = 0;
00691 
00692     if( depth == CV_32S )
00693         nout = approxPolyDP_(curve.ptr<Point>(), npoints, buf, closed, epsilon, &_stack);
00694     else if( depth == CV_32F )
00695         nout = approxPolyDP_(curve.ptr<Point2f >(), npoints, (Point2f *)buf, closed, epsilon, &_stack);
00696     else
00697         CV_Error( CV_StsUnsupportedFormat, "" );
00698 
00699     Mat(nout, 1, CV_MAKETYPE(depth, 2), buf).copyTo(_approxCurve);
00700 }
00701 
00702 
00703 CV_IMPL CvSeq*
00704 cvApproxPoly( const void* array, int header_size,
00705              CvMemStorage* storage, int method,
00706              double parameter, int parameter2 )
00707 {
00708     cv::AutoBuffer<cv::Point> _buf;
00709     cv::AutoBuffer<cv::Range> stack(100);
00710     CvSeq* dst_seq = 0;
00711     CvSeq *prev_contour = 0, *parent = 0;
00712     CvContour contour_header;
00713     CvSeq* src_seq = 0;
00714     CvSeqBlock block;
00715     int recursive = 0;
00716 
00717     if( CV_IS_SEQ( array ))
00718     {
00719         src_seq = (CvSeq*)array;
00720         if( !CV_IS_SEQ_POLYLINE( src_seq ))
00721             CV_Error( CV_StsBadArg, "Unsupported sequence type" );
00722 
00723         recursive = parameter2;
00724 
00725         if( !storage )
00726             storage = src_seq->storage;
00727     }
00728     else
00729     {
00730         src_seq = cvPointSeqFromMat(
00731                                     CV_SEQ_KIND_CURVE | (parameter2 ? CV_SEQ_FLAG_CLOSED : 0),
00732                                     array, &contour_header, &block );
00733     }
00734 
00735     if( !storage )
00736         CV_Error( CV_StsNullPtr, "NULL storage pointer " );
00737 
00738     if( header_size < 0 )
00739         CV_Error( CV_StsOutOfRange, "header_size is negative. "
00740                  "Pass 0 to make the destination header_size == input header_size" );
00741 
00742     if( header_size == 0 )
00743         header_size = src_seq->header_size;
00744 
00745     if( !CV_IS_SEQ_POLYLINE( src_seq ))
00746     {
00747         if( CV_IS_SEQ_CHAIN( src_seq ))
00748         {
00749             CV_Error( CV_StsBadArg, "Input curves are not polygonal. "
00750                      "Use cvApproxChains first" );
00751         }
00752         else
00753         {
00754             CV_Error( CV_StsBadArg, "Input curves have uknown type" );
00755         }
00756     }
00757 
00758     if( header_size == 0 )
00759         header_size = src_seq->header_size;
00760 
00761     if( header_size < (int)sizeof(CvContour) )
00762         CV_Error( CV_StsBadSize, "New header size must be non-less than sizeof(CvContour)" );
00763 
00764     if( method != CV_POLY_APPROX_DP )
00765         CV_Error( CV_StsOutOfRange, "Unknown approximation method" );
00766 
00767     while( src_seq != 0 )
00768     {
00769         CvSeq *contour = 0;
00770 
00771         switch (method)
00772         {
00773         case CV_POLY_APPROX_DP:
00774             if( parameter < 0 )
00775                 CV_Error( CV_StsOutOfRange, "Accuracy must be non-negative" );
00776 
00777             CV_Assert( CV_SEQ_ELTYPE(src_seq) == CV_32SC2 ||
00778                       CV_SEQ_ELTYPE(src_seq) == CV_32FC2 );
00779 
00780             {
00781             int npoints = src_seq->total, nout = 0;
00782             _buf.allocate(npoints*2);
00783             cv::Point  *src = _buf, *dst = src + npoints;
00784             bool closed = CV_IS_SEQ_CLOSED(src_seq);
00785 
00786             if( src_seq->first->next == src_seq->first )
00787                 src = (cv::Point *)src_seq->first->data;
00788             else
00789                 cvCvtSeqToArray(src_seq, src);
00790 
00791             if( CV_SEQ_ELTYPE(src_seq) == CV_32SC2 )
00792                 nout = cv::approxPolyDP_(src, npoints, dst, closed, parameter, &stack);
00793             else if( CV_SEQ_ELTYPE(src_seq) == CV_32FC2 )
00794                 nout = cv::approxPolyDP_((cv::Point2f *)src, npoints,
00795                                          (cv::Point2f *)dst, closed, parameter, &stack);
00796             else
00797                 CV_Error( CV_StsUnsupportedFormat, "" );
00798 
00799             contour = cvCreateSeq( src_seq->flags, header_size,
00800                                   src_seq->elem_size, storage );
00801             cvSeqPushMulti(contour, dst, nout);
00802             }
00803             break;
00804         default:
00805             CV_Error( CV_StsBadArg, "Invalid approximation method" );
00806         }
00807 
00808         assert( contour );
00809 
00810         if( header_size >= (int)sizeof(CvContour))
00811             cvBoundingRect( contour, 1 );
00812 
00813         contour->v_prev = parent;
00814         contour->h_prev = prev_contour;
00815 
00816         if( prev_contour )
00817             prev_contour->h_next = contour;
00818         else if( parent )
00819             parent->v_next = contour;
00820         prev_contour = contour;
00821         if( !dst_seq )
00822             dst_seq = prev_contour;
00823 
00824         if( !recursive )
00825             break;
00826 
00827         if( src_seq->v_next )
00828         {
00829             assert( prev_contour != 0 );
00830             parent = prev_contour;
00831             prev_contour = 0;
00832             src_seq = src_seq->v_next;
00833         }
00834         else
00835         {
00836             while( src_seq->h_next == 0 )
00837             {
00838                 src_seq = src_seq->v_prev;
00839                 if( src_seq == 0 )
00840                     break;
00841                 prev_contour = parent;
00842                 if( parent )
00843                     parent = parent->v_prev;
00844             }
00845             if( src_seq )
00846                 src_seq = src_seq->h_next;
00847         }
00848     }
00849 
00850     return dst_seq;
00851 }
00852 
00853 /* End of file. */
00854