Contour / polyline simplification

advanced
#1

hi all,

ive been doing some research into simplifying contours and poly lines… haven’t been completely happy with results given by the poly_simplify algorithm i found here the forum and so just wanted to share my findings.

poly_simplify uses a Douglas-Peucker recursive simplification routine, although ive noticed it is very jump as the tolerance changes, meaning the dominant points always change position.

i tried contour simplification using openCV with much better results. the dominant points always stay the same which suggests to me it is better at recognising general shape of the curve or polygon.

here is the code,

  
void testApp :: simplifyDP_openCV ( const vector<ofPoint>& contourIn, vector<ofPoint>& contourOut, float tolerance )		  
{  
	//-- copy points.  
	  
	int numOfPoints;  
	numOfPoints = contourIn.size();  
	  
	CvPoint* cvpoints;  
	cvpoints = new CvPoint[ numOfPoints ];  
	  
	for( int i=0; i<numOfPoints; i++)  
	{  
		int j = i % numOfPoints;  
		  
		cvpoints[ i ].x = contourIn[ j ].x;  
		cvpoints[ i ].y = contourIn[ j ].y;  
	}  
	  
	//-- create contour.  
	  
	CvContour	contour;  
	CvSeqBlock	contour_block;  
	  
	cvMakeSeqHeaderForArray  
	(  
		CV_SEQ_POLYLINE,  
		sizeof(CvContour),  
		sizeof(CvPoint),  
		cvpoints,  
		numOfPoints,  
		(CvSeq*)&contour,  
		&contour_block  
	);  
	  
	printf( "length = %f \n", cvArcLength( &contour ) );  
	  
	//-- simplify contour.  
	  
	CvMemStorage* storage;  
	storage = cvCreateMemStorage( 1000 );  
	  
	CvSeq *result = 0;  
	result = cvApproxPoly  
	(  
		&contour,  
		sizeof( CvContour ),  
		storage,  
		CV_POLY_APPROX_DP,  
		cvContourPerimeter( &contour ) * tolerance,  
		0  
	);  
	  
	//-- contour out points.  
	  
	contourOut.clear();  
	for( int j=0; j<result->total; j++ )  
	{  
		CvPoint * pt = (CvPoint*)cvGetSeqElem( result, j );  
		  
		contourOut.push_back( ofPoint() );  
		contourOut.back().x = (float)pt->x;  
		contourOut.back().y = (float)pt->y;  
	}  
	  
	//-- clean up.  
	  
	if( storage != NULL )  
		cvReleaseMemStorage( &storage );  
	  
	delete[] cvpoints;  
}

also attached a testApp ive been using to test these algorithms so you can see the results for yourself.

[attachment=0:1hd8j7n2]curveAnalysis.zip[/attachment:1hd8j7n2]

L.

curveAnalysis.zip

#2

Looks great! Each one has a certain charm, I think they could all animate in interesting ways, especially combining with some of Zach’s Drawing ± code.

#3

yeah sweet, glad that it might come in handy.
whats the ± code you’re referring to?
don’t think ive seen it…

#4

i don’t know if its worth to mention, but is it not recommended to use lists in this case rather than vectors? I am not a c++ expert, but all the time i read "if you don’t know the size of your datatype, than use lists.

by the way thank you very much for this usefull snippet.:wink:

#5

I’d say this is a fine place for vectors. Lists are best when you want to constantly reorganize, add, and delete arbitrary items.

#6

i agree with kyle. Also, lists are way faster than vectors when processing say, 100, 000 entries.

#7

here’s a different (and very intuitive) algorithm:

great explanation here:
http://bost.ocks.org/mike/simplify/