text: /*M///////////////////////////////////////////////////////////////////////////////////////
  //
  //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
  //
  //  By downloading, copying, installing or using the software you agree to this license.
  //  If you do not agree to this license, do not download, install,
  //  copy or use the software.
  //
  //
  //                        Intel License Agreement
  //                For Open Source Computer Vision Library
  //
  // Copyright (C) 2000, Intel Corporation, all rights reserved.
  // Third party copyrights are property of their respective owners.
  //
  // Redistribution and use in source and binary forms, with or without modification,
  // are permitted provided that the following conditions are met:
  //
  //   * Redistribution's of source code must retain the above copyright notice,
  //     this list of conditions and the following disclaimer.
  //
  //   * Redistribution's in binary form must reproduce the above copyright notice,
  //     this list of conditions and the following disclaimer in the documentation
  //     and/or other materials provided with the distribution.
  //
  //   * The name of Intel Corporation may not be used to endorse or promote products
  //     derived from this software without specific prior written permission.
  //
  // This software is provided by the copyright holders and contributors "as is" and
  // any express or implied warranties, including, but not limited to, the implied
  // warranties of merchantability and fitness for a particular purpose are disclaimed.
  // In no event shall the Intel Corporation or contributors be liable for any direct,
  // indirect, incidental, special, exemplary, or consequential damages
  // (including, but not limited to, procurement of substitute goods or services;
  // loss of use, data, or profits; or business interruption) however caused
  // and on any theory of liability, whether in contract, strict liability,
  // or tort (including negligence or otherwise) arising in any way out of
  // the use of this software, even if advised of the possibility of such damage.
  //
  //M*/
  #include "_cv.h"
  
  /****************************************************************************************\
  *                                  Chain Approximation                                   *
  \****************************************************************************************/
  
  typedef struct _CvPtInfo
  {
      CvPoint pt;
      int k;                      /* support region */
      int s;                      /* curvature value */
      struct _CvPtInfo *next;
  }
  _CvPtInfo;
  
  
  /* curvature: 0 - 1-curvature, 1 - k-cosine curvature. */
  CvStatus
  icvApproximateChainTC89( CvChain*               chain,
                           int                    header_size,
                           CvMemStorage*          storage, 
                           CvSeq**                contour, 
                           int    method )
  {
      static const int abs_diff[] = { 1, 2, 3, 4, 3, 2, 1, 0, 1, 2, 3, 4, 3, 2, 1 };
  
      char            local_buffer[1 << 16];
      char*           buffer = local_buffer;
      int             buffer_size;
  
      _CvPtInfo       temp;
      _CvPtInfo       *array, *first = 0, *current = 0, *prev_current = 0;
      int             i, j, i1, i2, s, len;
      int             count;
  
      CvChainPtReader reader;
      CvSeqWriter     writer;
      CvPoint         pt = chain->origin;
     
      assert( chain && contour && buffer );
  
      buffer_size = (chain->total + 8) * sizeof( _CvPtInfo );
  
      *contour = 0;
  
      if( !CV_IS_SEQ_CHAIN_CONTOUR( chain ))
          return CV_BADFLAG_ERR;
  
      if( header_size < (int)sizeof(CvContour) )
          return CV_BADSIZE_ERR;
      
      cvStartWriteSeq( (chain->flags & ~CV_SEQ_ELTYPE_MASK) | CV_SEQ_ELTYPE_POINT,
                       header_size, sizeof( CvPoint ), storage, &writer );
      
      if( chain->total == 0 )
      {        
          CV_WRITE_SEQ_ELEM( pt, writer );
          goto exit_function;
      }
  
      cvStartReadChainPoints( chain, &reader );
  
      if( method > CV_CHAIN_APPROX_SIMPLE && buffer_size > (int)sizeof(local_buffer))
      {
          buffer = (char *) cvAlloc( buffer_size );
          if( !buffer )
              return CV_OUTOFMEM_ERR;
      }
  
      array = (_CvPtInfo *) buffer;
      count = chain->total;
  
      temp.next = 0;
      current = &temp;
  
      /* Pass 0.
         Restores all the digital curve points from the chain code.
         Removes the points (from the resultant polygon)
         that have zero 1-curvature */
      for( i = 0; i < count; i++ )
      {
          int prev_code = *reader.prev_elem;
  
          reader.prev_elem = reader.ptr;
          CV_READ_CHAIN_POINT( pt, reader );
  
          /* calc 1-curvature */
          s = abs_diff[reader.code - prev_code + 7];
  
          if( method <= CV_CHAIN_APPROX_SIMPLE )
          {
              if( method == CV_CHAIN_APPROX_NONE || s != 0 )
              {
                  CV_WRITE_SEQ_ELEM( pt, writer );
              }
          }
          else
          {
              if( s != 0 )
                  current = current->next = array + i;
              array[i].s = s;
              array[i].pt = pt;
          }
      }
  
      //assert( pt.x == chain->origin.x && pt.y == chain->origin.y );
  
      if( method <= CV_CHAIN_APPROX_SIMPLE )
          goto exit_function;
  
      current->next = 0;
  
      len = i;
      current = temp.next;
  
      assert( current );
  
      /* Pass 1.
         Determines support region for all the remained points */
      do
      {
          CvPoint pt0;
          int k, l = 0, d_num = 0;
  
          i = (int)(current - array);
          pt0 = array[i].pt;
  
          /* determine support region */
          for( k = 1;; k++ )
          {
              int lk, dk_num;
              int dx, dy;
              Cv32suf d;
  
              assert( k <= len );
  
              /* calc indices */
              i1 = i - k;
              i1 += i1 < 0 ? len : 0;
              i2 = i + k;
              i2 -= i2 >= len ? len : 0;
  
              dx = array[i2].pt.x - array[i1].pt.x;
              dy = array[i2].pt.y - array[i1].pt.y;
  
              /* distance between p_(i - k) and p_(i + k) */
              lk = dx * dx + dy * dy;
  
              /* distance between p_i and the line (p_(i-k), p_(i+k)) */
              dk_num = (pt0.x - array[i1].pt.x) * dy - (pt0.y - array[i1].pt.y) * dx;
              d.f = (float) (((double) d_num) * lk - ((double) dk_num) * l);
  
              if( k > 1 && (l >= lk || ((d_num > 0 && d.i <= 0) || (d_num < 0 && d.i >= 0))))
                  break;
  
              d_num = dk_num;
              l = lk;
          }
  
          current->k = --k;
  
          /* determine cosine curvature if it should be used */
          if( method == CV_CHAIN_APPROX_TC89_KCOS )
          {
              /* calc k-cosine curvature */
              for( j = k, s = 0; j > 0; j-- )
              {
                  double temp_num;
                  int dx1, dy1, dx2, dy2;
                  Cv32suf sk;
  
                  i1 = i - j;
                  i1 += i1 < 0 ? len : 0;
                  i2 = i + j;
                  i2 -= i2 >= len ? len : 0;
  
                  dx1 = array[i1].pt.x - pt0.x;
                  dy1 = array[i1].pt.y - pt0.y;
                  dx2 = array[i2].pt.x - pt0.x;
                  dy2 = array[i2].pt.y - pt0.y;
  
                  if( (dx1 | dy1) == 0 || (dx2 | dy2) == 0 )
                      break;
  
                  temp_num = dx1 * dx2 + dy1 * dy2;
                  temp_num =
                      (float) (temp_num /
                               sqrt( ((double)dx1 * dx1 + (double)dy1 * dy1) *
                                     ((double)dx2 * dx2 + (double)dy2 * dy2) ));
                  sk.f = (float) (temp_num + 1.1);
  
                  assert( 0 <= sk.f && sk.f <= 2.2 );
                  if( j < k && sk.i <= s )
                      break;
  
                  s = sk.i;
              }
              current->s = s;
          }
          current = current->next;
      }
      while( current != 0 );
  
      prev_current = &temp;
      current = temp.next;
  
      /* Pass 2.
         Performs non-maxima supression */
      do
      {
          int k2 = current->k >> 1;
  
          s = current->s;
          i = (int)(current - array);
  
          for( j = 1; j <= k2; j++ )
          {
              i2 = i - j;
              i2 += i2 < 0 ? len : 0;
  
              if( array[i2].s > s )
                  break;
  
              i2 = i + j;
              i2 -= i2 >= len ? len : 0;
  
              if( array[i2].s > s )
                  break;
          }
  
          if( j <= k2 )           /* exclude point */
          {
              prev_current->next = current->next;
              current->s = 0;     /* "clear" point */
          }
          else
              prev_current = current;
          current = current->next;
      }
      while( current != 0 );
  
      /* Pass 3.
         Removes non-dominant points with 1-length support region */
      current = temp.next;
      assert( current );
      prev_current = &temp;
  
      do
      {
          if( current->k == 1 )
          {
              s = current->s;
              i = (int)(current - array);
  
              i1 = i - 1;
              i1 += i1 < 0 ? len : 0;
  
              i2 = i + 1;
              i2 -= i2 >= len ? len : 0;
  
              if( s <= array[i1].s || s <= array[i2].s )
              {
                  prev_current->next = current->next;
                  current->s = 0;
              }
              else
                  prev_current = current;
          }
          else
              prev_current = current;
          current = current->next;
      }
      while( current != 0 );
  
      if( method == CV_CHAIN_APPROX_TC89_KCOS )
          goto copy_vect;
  
      /* Pass 4.
         Cleans remained couples of points */
      assert( temp.next );
  
      if( array[0].s != 0 && array[len - 1].s != 0 )      /* specific case */
      {
          for( i1 = 1; i1 < len && array[i1].s != 0; i1++ )
          {
              array[i1 - 1].s = 0;
          }
          if( i1 == len )
              goto copy_vect;     /* all points survived */
          i1--;
  
          for( i2 = len - 2; i2 > 0 && array[i2].s != 0; i2-- )
          {
              array[i2].next = 0;
              array[i2 + 1].s = 0;
          }
          i2++;
  
          if( i1 == 0 && i2 == len - 1 )  /* only two points */
          {
              i1 = (int)(array[0].next - array);
              array[len] = array[0];      /* move to the end */
              array[len].next = 0;
              array[len - 1].next = array + len;
          }
          temp.next = array + i1;
      }
  
      current = temp.next;
      first = prev_current = &temp;
      count = 1;
  
      /* do last pass */
      do
      {
          if( current->next == 0 || current->next - current != 1 )
          {
              if( count >= 2 )
              {
                  if( count == 2 )
                  {
                      int s1 = prev_current->s;
                      int s2 = current->s;
  
                      if( s1 > s2 || (s1 == s2 && prev_current->k <= current->k) )
                          /* remove second */
                          prev_current->next = current->next;
                      else
                          /* remove first */
                          first->next = current;
                  }
                  else
                      first->next->next = current;
              }
              first = current;
              count = 1;
          }
          else
              count++;
          prev_current = current;
          current = current->next;
      }
      while( current != 0 );
  
    copy_vect:
  
      /* gather points */
      current = temp.next;
      assert( current );
  
      do
      {
          CV_WRITE_SEQ_ELEM( current->pt, writer );
          current = current->next;
      }
      while( current != 0 );
  
  exit_function:
  
      *contour = cvEndWriteSeq( &writer );
  
      assert( writer.seq->total > 0 );
  
      if( buffer != local_buffer )
          cvFree( &buffer );
      return CV_OK;
  }
  
  
  /*Applies some approximation algorithm to chain-coded contour(s) and
    converts it/them to polygonal representation */
  CV_IMPL CvSeq*
  cvApproxChains( CvSeq*              src_seq,
                  CvMemStorage*       storage,
                  int                 method,
                  double              /*parameter*/, 
                  int                 minimal_perimeter, 
                  int                 recursive )
  {
      CvSeq *prev_contour = 0, *parent = 0;
      CvSeq *dst_seq = 0;
      
      CV_FUNCNAME( "cvApproxChains" );
  
      __BEGIN__;
  
      if( !src_seq || !storage )
          CV_ERROR( CV_StsNullPtr, "" );
      if( method > CV_CHAIN_APPROX_TC89_KCOS || method <= 0 || minimal_perimeter < 0 )
          CV_ERROR( CV_StsOutOfRange, "" );
  
      while( src_seq != 0 )
      {
          int len = src_seq->total;
  
          if( len >= minimal_perimeter )
          {
              CvSeq *contour;
              
              switch( method )
              {
              case CV_CHAIN_APPROX_NONE:
              case CV_CHAIN_APPROX_SIMPLE:
              case CV_CHAIN_APPROX_TC89_L1:
              case CV_CHAIN_APPROX_TC89_KCOS:
                  IPPI_CALL( icvApproximateChainTC89( (CvChain *) src_seq,
                                                      sizeof( CvContour ), storage,
                                                      (CvSeq**)&contour, method ));
                  break;
              default:
                  assert(0);
                  CV_ERROR( CV_StsOutOfRange, "" );
              }
  
              assert( contour );
  
              if( contour->total > 0 )
              {
                  cvBoundingRect( contour, 1 );
  
                  contour->v_prev = parent;
                  contour->h_prev = prev_contour;
  
                  if( prev_contour )
                      prev_contour->h_next = contour;
                  else if( parent )
                      parent->v_next = contour;
                  prev_contour = contour;
                  if( !dst_seq )
                      dst_seq = prev_contour;
              }
              else                /* if resultant contour has zero length, skip it */
              {
                  len = -1;
              }
          }
  
          if( !recursive )
              break;
  
          if( src_seq->v_next && len >= minimal_perimeter )
          {
              assert( prev_contour != 0 );
              parent = prev_contour;
              prev_contour = 0;
              src_seq = src_seq->v_next;
          }
          else
          {
              while( src_seq->h_next == 0 )
              {
                  src_seq = src_seq->v_prev;
                  if( src_seq == 0 )
                      break;
                  prev_contour = parent;
                  if( parent )
                      parent = parent->v_prev;
              }
              if( src_seq )
                  src_seq = src_seq->h_next;
          }
      }
  
      __END__;
  
      return dst_seq;
  }
  
  
  /****************************************************************************************\
  *                               Polygonal Approximation                                  *
  \****************************************************************************************/
  
  /* Ramer-Douglas-Peucker algorithm for polygon simplification */
  
  /* the version for integer point coordinates */
  static CvStatus
  icvApproxPolyDP_32s( CvSeq* src_contour, int header_size, 
                       CvMemStorage* storage,
                       CvSeq** dst_contour, float eps )
  {
      int             init_iters = 3;
      CvSlice         slice = {0, 0}, right_slice = {0, 0};
      CvSeqReader     reader, reader2;
      CvSeqWriter     writer;
      CvPoint         start_pt = {INT_MIN, INT_MIN}, end_pt = {0, 0}, pt = {0,0};
      int             i = 0, j, count = src_contour->total, new_count;
      int             is_closed = CV_IS_SEQ_CLOSED( src_contour );
      int             le_eps = 0;
      CvMemStorage*   temp_storage = 0;
      CvSeq*          stack = 0;
      
      assert( CV_SEQ_ELTYPE(src_contour) == CV_32SC2 );
      cvStartWriteSeq( src_contour->flags, header_size, sizeof(pt), storage, &writer );
  
      if( src_contour->total == 0  )
      {
          *dst_contour = cvEndWriteSeq( &writer );
          return CV_OK;
      }
  
      temp_storage = cvCreateChildMemStorage( storage );
  
      assert( src_contour->first != 0 );
      stack = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSlice), temp_storage );
      eps *= eps;
      cvStartReadSeq( src_contour, &reader, 0 );
  
      if( !is_closed )
      {
          right_slice.start_index = count;
          end_pt = *(CvPoint*)(reader.ptr);
          start_pt = *(CvPoint*)cvGetSeqElem( src_contour, -1 );
  
          if( start_pt.x != end_pt.x || start_pt.y != end_pt.y )
          {
              slice.start_index = 0;
              slice.end_index = count - 1;
              cvSeqPush( stack, &slice );
          }
          else
          {
              is_closed = 1;
              init_iters = 1;
          }
      }
      
      if( is_closed )
      {
          /* 1. Find approximately two farthest points of the contour */
          right_slice.start_index = 0;
  
          for( i = 0; i < init_iters; i++ )
          {
              int max_dist = 0;
              cvSetSeqReaderPos( &reader, right_slice.start_index, 1 );
              CV_READ_SEQ_ELEM( start_pt, reader );   /* read the first point */
  
              for( j = 1; j < count; j++ )
              {
                  int dx, dy, dist;
  
                  CV_READ_SEQ_ELEM( pt, reader );
                  dx = pt.x - start_pt.x;
                  dy = pt.y - start_pt.y;
  
                  dist = dx * dx + dy * dy;
  
                  if( dist > max_dist )
                  {
                      max_dist = dist;
                      right_slice.start_index = j;
                  }
              }
  
              le_eps = max_dist <= eps;
          }
  
          /* 2. initialize the stack */
          if( !le_eps )
          {
              slice.start_index = cvGetSeqReaderPos( &reader );
              slice.end_index = right_slice.start_index += slice.start_index;
  
              right_slice.start_index -= right_slice.start_index >= count ? count : 0;
              right_slice.end_index = slice.start_index;
              if( right_slice.end_index < right_slice.start_index )
                  right_slice.end_index += count;
  
              cvSeqPush( stack, &right_slice );
              cvSeqPush( stack, &slice );
          }
          else
              CV_WRITE_SEQ_ELEM( start_pt, writer );
      }
  
      /* 3. run recursive process */
      while( stack->total != 0 )
      {
          cvSeqPop( stack, &slice );
  
          cvSetSeqReaderPos( &reader, slice.end_index );
          CV_READ_SEQ_ELEM( end_pt, reader );
  
          cvSetSeqReaderPos( &reader, slice.start_index );
          CV_READ_SEQ_ELEM( start_pt, reader );
  
          if( slice.end_index > slice.start_index + 1 )
          {
              int dx, dy, dist, max_dist = 0;
  
              dx = end_pt.x - start_pt.x;
              dy = end_pt.y - start_pt.y;
  
              assert( dx != 0 || dy != 0 );
  
              for( i = slice.start_index + 1; i < slice.end_index; i++ )
              {
                  CV_READ_SEQ_ELEM( pt, reader );
                  dist = abs((pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy);
  
                  if( dist > max_dist )
                  {
                      max_dist = dist;
                      right_slice.start_index = i;
                  }
              }
  
              le_eps = (double)max_dist * max_dist <= eps * ((double)dx * dx + (double)dy * dy);
          }
          else
          {
              assert( slice.end_index > slice.start_index );
              le_eps = 1;
              /* read starting point */
              cvSetSeqReaderPos( &reader, slice.start_index );
              CV_READ_SEQ_ELEM( start_pt, reader );
          }
  
          if( le_eps )
          {
              CV_WRITE_SEQ_ELEM( start_pt, writer );
          }
          else
          {
              right_slice.end_index = slice.end_index;
              slice.end_index = right_slice.start_index;
              cvSeqPush( stack, &right_slice );
              cvSeqPush( stack, &slice );
          }
      }
  
      is_closed = CV_IS_SEQ_CLOSED( src_contour );
      if( !is_closed )
          CV_WRITE_SEQ_ELEM( end_pt, writer );
  
      *dst_contour = cvEndWriteSeq( &writer );
      
      cvStartReadSeq( *dst_contour, &reader, is_closed );
      CV_READ_SEQ_ELEM( start_pt, reader );
  
      reader2 = reader;
      CV_READ_SEQ_ELEM( pt, reader );
  
      new_count = count = (*dst_contour)->total;
      for( i = !is_closed; i < count - !is_closed && new_count > 2; i++ )
      {
          int dx, dy, dist;
          CV_READ_SEQ_ELEM( end_pt, reader );
  
          dx = end_pt.x - start_pt.x;
          dy = end_pt.y - start_pt.y;
          dist = abs((pt.x - start_pt.x)*dy - (pt.y - start_pt.y)*dx);
          if( (double)dist * dist <= 0.5*eps*((double)dx*dx + (double)dy*dy) && dx != 0 && dy != 0 )
          {
              new_count--;
              *((CvPoint*)reader2.ptr) = start_pt = end_pt;
              CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 );
              CV_READ_SEQ_ELEM( pt, reader );
              i++;
              continue;
          }
          *((CvPoint*)reader2.ptr) = start_pt = pt;
          CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 );
          pt = end_pt;
      }
  
      if( !is_closed )
          *((CvPoint*)reader2.ptr) = pt;
  
      if( new_count < count )
          cvSeqPopMulti( *dst_contour, 0, count - new_count );
  
      cvReleaseMemStorage( &temp_storage );
  
      return CV_OK;
  }
  
  
  /* the version for integer point coordinates */
  static CvStatus
  icvApproxPolyDP_32f( CvSeq* src_contour, int header_size, 
                       CvMemStorage* storage,
                       CvSeq** dst_contour, float eps )
  {
      int             init_iters = 3;
      CvSlice         slice = {0, 0}, right_slice = {0, 0};
      CvSeqReader     reader, reader2;
      CvSeqWriter     writer;
      CvPoint2D32f    start_pt = {-1e6f, -1e6f}, end_pt = {0, 0}, pt = {0,0};
      int             i = 0, j, count = src_contour->total, new_count;
      int             is_closed = CV_IS_SEQ_CLOSED( src_contour );
      int             le_eps = 0;
      CvMemStorage*   temp_storage = 0;
      CvSeq*          stack = 0;
      
      assert( CV_SEQ_ELTYPE(src_contour) == CV_32FC2 );
      cvStartWriteSeq( src_contour->flags, header_size, sizeof(pt), storage, &writer );
  
      if( src_contour->total == 0  )
      {
          *dst_contour = cvEndWriteSeq( &writer );
          return CV_OK;
      }
  
      temp_storage = cvCreateChildMemStorage( storage );
  
      assert( src_contour->first != 0 );
      stack = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvSlice), temp_storage );
      eps *= eps;
      cvStartReadSeq( src_contour, &reader, 0 );
  
      if( !is_closed )
      {
          right_slice.start_index = count;
          end_pt = *(CvPoint2D32f*)(reader.ptr);
          start_pt = *(CvPoint2D32f*)cvGetSeqElem( src_contour, -1 );
  
          if( fabs(start_pt.x - end_pt.x) > FLT_EPSILON ||
              fabs(start_pt.y - end_pt.y) > FLT_EPSILON )
          {
              slice.start_index = 0;
              slice.end_index = count - 1;
              cvSeqPush( stack, &slice );
          }
          else
          {
              is_closed = 1;
              init_iters = 1;
          }
      }
      
      if( is_closed )
      {
          /* 1. Find approximately two farthest points of the contour */
          right_slice.start_index = 0;
  
          for( i = 0; i < init_iters; i++ )
          {
              double max_dist = 0;
              cvSetSeqReaderPos( &reader, right_slice.start_index, 1 );
              CV_READ_SEQ_ELEM( start_pt, reader );   /* read the first point */
  
              for( j = 1; j < count; j++ )
              {
                  double dx, dy, dist;
  
                  CV_READ_SEQ_ELEM( pt, reader );
                  dx = pt.x - start_pt.x;
                  dy = pt.y - start_pt.y;
  
                  dist = dx * dx + dy * dy;
  
                  if( dist > max_dist )
                  {
                      max_dist = dist;
                      right_slice.start_index = j;
                  }
              }
  
              le_eps = max_dist <= eps;
          }
  
          /* 2. initialize the stack */
          if( !le_eps )
          {
              slice.start_index = cvGetSeqReaderPos( &reader );
              slice.end_index = right_slice.start_index += slice.start_index;
  
              right_slice.start_index -= right_slice.start_index >= count ? count : 0;
              right_slice.end_index = slice.start_index;
              if( right_slice.end_index < right_slice.start_index )
                  right_slice.end_index += count;
  
              cvSeqPush( stack, &right_slice );
              cvSeqPush( stack, &slice );
          }
          else
              CV_WRITE_SEQ_ELEM( start_pt, writer );
      }
  
      /* 3. run recursive process */
      while( stack->total != 0 )
      {
          cvSeqPop( stack, &slice );
  
          cvSetSeqReaderPos( &reader, slice.end_index );
          CV_READ_SEQ_ELEM( end_pt, reader );
  
          cvSetSeqReaderPos( &reader, slice.start_index );
          CV_READ_SEQ_ELEM( start_pt, reader );
  
          if( slice.end_index > slice.start_index + 1 )
          {
              double dx, dy, dist, max_dist = 0;
              
              dx = end_pt.x - start_pt.x;
              dy = end_pt.y - start_pt.y;
  
              assert( dx != 0 || dy != 0 );
  
              for( i = slice.start_index + 1; i < slice.end_index; i++ )
              {
                  CV_READ_SEQ_ELEM( pt, reader );
                  dist = fabs((pt.y - start_pt.y) * dx - (pt.x - start_pt.x) * dy);
  
                  if( dist > max_dist )
                  {
                      max_dist = dist;
                      right_slice.start_index = i;
                  }
              }
  
              le_eps = (double)max_dist * max_dist <= eps * ((double)dx * dx + (double)dy * dy);
          }
          else
          {
              assert( slice.end_index > slice.start_index );
              le_eps = 1;
              /* read starting point */
              cvSetSeqReaderPos( &reader, slice.start_index );
              CV_READ_SEQ_ELEM( start_pt, reader );
          }
  
          if( le_eps )
          {
              CV_WRITE_SEQ_ELEM( start_pt, writer );
          }
          else
          {
              right_slice.end_index = slice.end_index;
              slice.end_index = right_slice.start_index;
              cvSeqPush( stack, &right_slice );
              cvSeqPush( stack, &slice );
          }
      }
  
      is_closed = CV_IS_SEQ_CLOSED( src_contour );
      if( !is_closed )
          CV_WRITE_SEQ_ELEM( end_pt, writer );
  
      *dst_contour = cvEndWriteSeq( &writer );
      
      cvStartReadSeq( *dst_contour, &reader, is_closed );
      CV_READ_SEQ_ELEM( start_pt, reader );
  
      reader2 = reader;
      CV_READ_SEQ_ELEM( pt, reader );
  
      new_count = count = (*dst_contour)->total;
      for( i = !is_closed; i < count - !is_closed && new_count > 2; i++ )
      {
          double dx, dy, dist;
          CV_READ_SEQ_ELEM( end_pt, reader );
  
          dx = end_pt.x - start_pt.x;
          dy = end_pt.y - start_pt.y;
          dist = fabs((pt.x - start_pt.x)*dy - (pt.y - start_pt.y)*dx);
          if( (double)dist * dist <= 0.5*eps*((double)dx*dx + (double)dy*dy) )
          {
              new_count--;
              *((CvPoint2D32f*)reader2.ptr) = start_pt = end_pt;
              CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 );
              CV_READ_SEQ_ELEM( pt, reader );
              i++;
              continue;
          }
          *((CvPoint2D32f*)reader2.ptr) = start_pt = pt;
          CV_NEXT_SEQ_ELEM( sizeof(pt), reader2 );
          pt = end_pt;
      }
  
      if( !is_closed )
          *((CvPoint2D32f*)reader2.ptr) = pt;
  
      if( new_count < count )
          cvSeqPopMulti( *dst_contour, 0, count - new_count );
  
      cvReleaseMemStorage( &temp_storage );
  
      return CV_OK;
  }
  
  
  CV_IMPL CvSeq*
  cvApproxPoly( const void*  array, int  header_size,
                CvMemStorage*  storage, int  method, 
                double  parameter, int parameter2 )
  {
      CvSeq* dst_seq = 0;
      CvSeq *prev_contour = 0, *parent = 0;
      CvContour contour_header;
      CvSeq* src_seq = 0;
      CvSeqBlock block;
      int recursive = 0;
  
      CV_FUNCNAME( "cvApproxPoly" );
  
      __BEGIN__;
  
      if( CV_IS_SEQ( array ))
      {
          src_seq = (CvSeq*)array;
          if( !CV_IS_SEQ_POLYLINE( src_seq ))
              CV_ERROR( CV_StsBadArg, "Unsupported sequence type" );
  
          recursive = parameter2;
  
          if( !storage )
              storage = src_seq->storage;
      }
      else
      {
          CV_CALL( src_seq = cvPointSeqFromMat(
              CV_SEQ_KIND_CURVE | (parameter2 ? CV_SEQ_FLAG_CLOSED : 0),
              array, &contour_header, &block ));
      }
  
      if( !storage )
          CV_ERROR( CV_StsNullPtr, "NULL storage pointer " );
  
      if( header_size < 0 )
          CV_ERROR( CV_StsOutOfRange, "header_size is negative. "
                    "Pass 0 to make the destination header_size == input header_size" );
  
      if( header_size == 0 )
          header_size = src_seq->header_size;
  
      if( !CV_IS_SEQ_POLYLINE( src_seq ))
      {
          if( CV_IS_SEQ_CHAIN( src_seq ))
          {
              CV_ERROR( CV_StsBadArg, "Input curves are not polygonal. "
                                      "Use cvApproxChains first" );
          }
          else
          {
              CV_ERROR( CV_StsBadArg, "Input curves have uknown type" );
          }
      }
  
      if( header_size == 0 )
          header_size = src_seq->header_size;
  
      if( header_size < (int)sizeof(CvContour) )
          CV_ERROR( CV_StsBadSize, "New header size must be non-less than sizeof(CvContour)" );
  
      if( method != CV_POLY_APPROX_DP )
          CV_ERROR( CV_StsOutOfRange, "Unknown approximation method" );
  
      while( src_seq != 0 )
      {
          CvSeq *contour = 0;
  
          switch (method)
          {
          case CV_POLY_APPROX_DP:
              if( parameter < 0 )
                  CV_ERROR( CV_StsOutOfRange, "Accuracy must be non-negative" );
  
              if( CV_SEQ_ELTYPE(src_seq) == CV_32SC2 )
              {
                  IPPI_CALL( icvApproxPolyDP_32s( src_seq, header_size, storage,
                                                  &contour, (float)parameter ));
              }
              else
              {
                  IPPI_CALL( icvApproxPolyDP_32f( src_seq, header_size, storage,
                                                  &contour, (float)parameter ));
              }
              break;
          default:
              assert(0);
              CV_ERROR( CV_StsBadArg, "Invalid approximation method" );
          }
  
          assert( contour );
  
          if( header_size >= (int)sizeof(CvContour))
              cvBoundingRect( contour, 1 );
  
          contour->v_prev = parent;
          contour->h_prev = prev_contour;
  
          if( prev_contour )
              prev_contour->h_next = contour;
          else if( parent )
              parent->v_next = contour;
          prev_contour = contour;
          if( !dst_seq )
              dst_seq = prev_contour;
  
          if( !recursive )
              break;
  
          if( src_seq->v_next )
          {
              assert( prev_contour != 0 );
              parent = prev_contour;
              prev_contour = 0;
              src_seq = src_seq->v_next;
          }
          else
          {
              while( src_seq->h_next == 0 )
              {
                  src_seq = src_seq->v_prev;
                  if( src_seq == 0 )
                      break;
                  prev_contour = parent;
                  if( parent )
                      parent = parent->v_prev;
              }
              if( src_seq )
                  src_seq = src_seq->h_next;
          }
      }
  
      __END__;
  
      return dst_seq;
  }
  
  /* End of file. */
  