--- /dev/null
+/*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. */
projects / opencv / blobdiff