From 7a59d6c77e5ed7b6f609ddc028d2c400dd07f08d Mon Sep 17 00:00:00 2001 From: Vadim Pisarevsky Date: Mon, 26 Mar 2012 13:45:49 +0000 Subject: [PATCH] improved convergence of minEnclosingCircle algorithm, patch #947 (thanks to Hannes Sommer) --- modules/imgproc/src/shapedescr.cpp | 27 +++++++++++++++++++++++---- 1 file changed, 23 insertions(+), 4 deletions(-) diff --git a/modules/imgproc/src/shapedescr.cpp b/modules/imgproc/src/shapedescr.cpp index 8af036d..8150cb2 100644 --- a/modules/imgproc/src/shapedescr.cpp +++ b/modules/imgproc/src/shapedescr.cpp @@ -371,9 +371,11 @@ cvMinEnclosingCircle( const void* array, CvPoint2D32f * _center, float *_radius for( k = 0; k < max_iters; k++ ) { double min_delta = 0, delta; - CvPoint2D32f ptfl; - - icvFindEnslosingCicle4pts_32f( pts, ¢er, &radius ); + CvPoint2D32f ptfl, farAway = { 0, 0}; + /*only for first iteration because the alg is repared at the loop's foot*/ + if(k==0) + icvFindEnslosingCicle4pts_32f( pts, ¢er, &radius ); + cvStartReadSeq( sequence, &reader, 0 ); for( i = 0; i < count; i++ ) @@ -393,12 +395,29 @@ cvMinEnclosingCircle( const void* array, CvPoint2D32f * _center, float *_radius if( delta < min_delta ) { min_delta = delta; - pts[3] = ptfl; + farAway = ptfl; } } result = min_delta >= 0; if( result ) break; + + CvPoint2D32f ptsCopy[4]; + /* find good replacement partner for the point which is at most far away, + starting with the one that lays in the actual circle (i=3) */ + for(int i = 3; i >=0; i-- ) + { + for(int j = 0; j < 4; j++ ) + { + ptsCopy[j]=(i != j)? pts[j]: farAway; + } + + icvFindEnslosingCicle4pts_32f(ptsCopy, ¢er, &radius ); + if( icvIsPtInCircle( pts[i], center, radius )>=0){ // replaced one again in the new circle? + pts[i] = farAway; + break; + } + } } if( !result ) -- 2.7.4