#include "cvtest.h"
-int atsCheckConvexHull( CvPoint* Pts, int psize, int* hull, int hsize, int orient )
+/*static int
+cvTsPointConvexPolygon( CvPoint2D32f pt, CvPoint2D32f* v, int n )
{
- int i;
- int errors = 0;
+ CvPoint2D32f v0 = v[n-1];
+ int i, sign = 0;
- CvPoint* hullvect = (CvPoint*)cvAlloc( hsize * sizeof(CvSize) );
-
- for ( i = 1 ; i < hsize; i++ )
+ for( i = 0; i < n; i++ )
{
- hullvect[i-1].x = Pts[hull[i]].x - Pts[hull[i-1]].x;
- hullvect[i-1].y = Pts[hull[i]].y - Pts[hull[i-1]].y;
+ CvPoint2D32f v1 = v[i];
+ float dx = pt.x - v0.x, dy = pt.y - v0.y;
+ float dx1 = v1.x - v0.x, dy1 = v1.y - v0.y;
+ double t = (double)dx*dy1 - (double)dx1*dy;
+ if( fabs(t) > DBL_EPSILON )
+ {
+ if( t*sign < 0 )
+ break;
+ if( sign == 0 )
+ sign = t < 0 ? -1 : 1;
+ }
+ else if( fabs(dx) + fabs(dy) < DBL_EPSILON )
+ return i+1;
+ v0 = v1;
}
- hullvect[hsize-1].x = Pts[hull[0]].x - Pts[hull[hsize-1]].x;
- hullvect[hsize-1].y = Pts[hull[0]].y - Pts[hull[hsize-1]].y;
- /* check two consequtive vectors */
- for ( i = 0 ; i < hsize - 1; i++ )
- {
- int conv = hullvect[i].x * hullvect[i+1].y - hullvect[i].y * hullvect[i+1].x ;
- if (orient == CV_CLOCKWISE) conv = -conv;
- if (conv < 0)
- errors++;
- }
- {
- int conv = hullvect[hsize-1].x * hullvect[0].y -
- hullvect[hsize-1].y * hullvect[0].x ;
- if (orient == CV_CLOCKWISE) conv = -conv;
- if (conv < 0)
- errors++;
- }
-
+ return i < n ? -1 : 0;
+}*/
+CV_INLINE double
+cvTsDist( CvPoint2D32f a, CvPoint2D32f b )
+{
+ double dx = a.x - b.x;
+ double dy = a.y - b.y;
+ return sqrt(dx*dx + dy*dy);
+}
- for ( i = 0 ; i < psize; i++ )
+CV_INLINE double
+cvTsPtLineDist( CvPoint2D32f pt, CvPoint2D32f a, CvPoint2D32f b )
+{
+ double d0 = cvTsDist( pt, a ), d1;
+ double dd = cvTsDist( a, b );
+ if( dd < FLT_EPSILON )
+ return d0;
+ d1 = cvTsDist( pt, b );
+ dd = fabs((double)(pt.x - a.x)*(b.y - a.y) - (double)(pt.y - a.y)*(b.x - a.x))/dd;
+ d0 = MIN( d0, d1 );
+ return MIN( d0, dd );
+}
+
+static double
+cvTsPointPolygonTest( CvPoint2D32f pt, const CvPoint2D32f* vv, int n, int* _idx=0, int* _on_edge=0 )
+{
+ int i;
+ CvPoint2D32f v = vv[n-1], v0;
+ double min_dist_num = FLT_MAX, min_dist_denom = 1;
+ int min_dist_idx = -1, min_on_edge = 0;
+ int counter = 0;
+ double result;
+
+ for( i = 0; i < n; i++ )
{
- int j;
- for( j = 0 ; j < hsize; j++ )
- {
- int dx = Pts[i].x - Pts[hull[j]].x;
- int dy = Pts[i].y - Pts[hull[j]].y;
+ double dx, dy, dx1, dy1, dx2, dy2, dist_num, dist_denom = 1;
+ int on_edge = 0, idx = i;
- int conv = dy*hullvect[j].x - dx*hullvect[j].y;
-
- /*if ( (i==hull[j])||(i==hull[j+1]) ) continue; */
+ v0 = v; v = vv[i];
+ dx = v.x - v0.x; dy = v.y - v0.y;
+ dx1 = pt.x - v0.x; dy1 = pt.y - v0.y;
+ dx2 = pt.x - v.x; dy2 = pt.y - v.y;
- if (orient == CV_CLOCKWISE) conv = -conv;
+ if( dx2*dx + dy2*dy >= 0 )
+ dist_num = dx2*dx2 + dy2*dy2;
+ else if( dx1*dx + dy1*dy <= 0 )
+ {
+ dist_num = dx1*dx1 + dy1*dy1;
+ idx = i - 1;
+ if( idx < 0 ) idx = n-1;
+ }
+ else
+ {
+ dist_num = (dy1*dx - dx1*dy);
+ dist_num *= dist_num;
+ dist_denom = dx*dx + dy*dy;
+ on_edge = 1;
+ }
- if ( conv < 0 )
- errors++;
+ if( dist_num*min_dist_denom < min_dist_num*dist_denom )
+ {
+ min_dist_num = dist_num;
+ min_dist_denom = dist_denom;
+ min_dist_idx = idx;
+ min_on_edge = on_edge;
+ if( min_dist_num == 0 )
+ break;
}
+
+ if( v0.y <= pt.y && v.y <= pt.y ||
+ v0.y > pt.y && v.y > pt.y ||
+ v0.x < pt.x && v.x < pt.x )
+ continue;
+
+ dist_num = dy1*dx - dx1*dy;
+ if( dy < 0 )
+ dist_num = -dist_num;
+ counter += dist_num > 0;
}
- cvFree((void**)&hullvect);
- /*assert( errors == 0); */
- return errors;
+
+ result = sqrt(min_dist_num/min_dist_denom);
+ if( counter % 2 == 0 )
+ result = -result;
+
+ if( _idx )
+ *_idx = min_dist_idx;
+ if( _on_edge )
+ *_on_edge = min_on_edge;
+
+ return result;
}
-int atsCheckConvexHullP( CvPoint* Pts, int psize, CvPoint** hull, int hsize, int orient )
+
+
+/****************************************************************************************\
+* Base class for shape descriptor tests *
+\****************************************************************************************/
+
+class CV_BaseShapeDescrTest : public CvTest
{
- int i;
- int errors = 0;
+public:
+ CV_BaseShapeDescrTest( const char* test_name, const char* test_funcs );
+ void clear();
+ int write_default_params(CvFileStorage* fs);
+
+protected:
+ int read_params( CvFileStorage* fs );
+ void run_func(void);
+ int prepare_test_case( int test_case_idx );
+ int validate_test_results( int test_case_idx );
+ virtual void generate_point_set( void* points );
+ virtual void extract_points();
+
+ int min_log_size;
+ int max_log_size;
- CvPoint* hullvect = (CvPoint*)cvAlloc( hsize * sizeof(CvSize) );
+ CvMemStorage* storage;
+ CvSeq* points1;
+ CvMat* points2;
+ void* points;
+ void* result;
+ CvScalar low, high;
+};
+
+
+CV_BaseShapeDescrTest::CV_BaseShapeDescrTest( const char* test_name, const char* test_funcs ):
+ CvTest( test_name, test_funcs )
+{
+ points1 = 0;
+ points2 = 0;
+ points = 0;
+ storage = 0;
+ test_case_count = 500;
+ min_log_size = 0;
+ max_log_size = 9;
+ low = high = cvScalarAll(0);
+
+ support_testing_modes = CvTS::CORRECTNESS_CHECK_MODE;
+}
+
+
+void CV_BaseShapeDescrTest::clear()
+{
+ cvReleaseMemStorage( &storage );
+ cvReleaseMat( &points2 );
+ points1 = 0;
+ points = 0;
+}
+
+
+int CV_BaseShapeDescrTest::write_default_params( CvFileStorage* fs )
+{
+ write_param( fs, "test_case_count", test_case_count );
+ write_param( fs, "min_log_size", min_log_size );
+ write_param( fs, "max_log_size", max_log_size );
+ return 0;
+}
- for ( i = 1 ; i < hsize; i++ )
+
+int CV_BaseShapeDescrTest::read_params( CvFileStorage* fs )
+{
+ int code = CvTest::read_params( fs );
+ if( code < 0 )
+ return code;
+
+ test_case_count = cvReadInt( find_param( fs, "struct_count" ), test_case_count );
+ min_log_size = cvReadInt( find_param( fs, "min_log_size" ), min_log_size );
+ max_log_size = cvReadInt( find_param( fs, "max_log_size" ), max_log_size );
+
+ min_log_size = cvTsClipInt( min_log_size, 0, 8 );
+ max_log_size = cvTsClipInt( max_log_size, 0, 10 );
+ if( min_log_size > max_log_size )
{
- hullvect[i-1].x = hull[i]->x - hull[i-1]->x;
- hullvect[i-1].y = hull[i]->y - hull[i-1]->y;
+ int t;
+ CV_SWAP( min_log_size, max_log_size, t );
}
- hullvect[hsize-1].x = hull[0]->x - hull[hsize-1]->x;
- hullvect[hsize-1].y = hull[0]->y - hull[hsize-1]->y;
- /* check two consequtive vectors */
- for ( i = 0 ; i < hsize - 1; i++ )
+ return 0;
+}
+
+
+void CV_BaseShapeDescrTest::generate_point_set( void* points )
+{
+ CvRNG* rng = ts->get_rng();
+ int i, total, point_type;
+ CvSeqReader reader;
+ uchar* data = 0;
+ double a0 = high.val[0] - low.val[0], b0 = low.val[0];
+ double a1 = high.val[1] - low.val[1], b1 = low.val[1];
+ memset( &reader, 0, sizeof(reader) );
+
+ if( CV_IS_SEQ(points) )
{
- int conv = hullvect[i].x * hullvect[i+1].y - hullvect[i].y * hullvect[i+1].x ;
- if (orient == CV_CLOCKWISE) conv = -conv;
- if (conv < 0)
- errors++;
+ CvSeq* ptseq = (CvSeq*)points;
+ total = ptseq->total;
+ point_type = CV_SEQ_ELTYPE(ptseq);
+ cvStartReadSeq( ptseq, &reader );
}
+ else
{
- int conv = hullvect[hsize-1].x * hullvect[0].y -
- hullvect[hsize-1].y * hullvect[0].x ;
- if (orient == CV_CLOCKWISE) conv = -conv;
- if (conv < 0)
- errors++;
+ CvMat* ptm = (CvMat*)points;
+ assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
+ total = ptm->rows + ptm->cols - 1;
+ point_type = CV_MAT_TYPE(ptm->type);
+ data = ptm->data.ptr;
}
-
+ assert( point_type == CV_32SC2 || point_type == CV_32FC2 );
- for ( i = 0 ; i < psize; i++ )
+ for( i = 0; i < total; i++ )
{
- int j;
- for( j = 0 ; j < hsize; j++ )
- {
- int dx = Pts[i].x - hull[j]->x;
- int dy = Pts[i].y - hull[j]->y;
+ CvPoint* pp;
+ CvPoint2D32f p;
+ if( reader.ptr )
+ {
+ pp = (CvPoint*)reader.ptr;
+ CV_NEXT_SEQ_ELEM( sizeof(*pp), reader );
+ }
+ else
+ pp = ((CvPoint*)data) + i;
+ p.x = (float)(cvTsRandReal(rng)*a0 + b0);
+ p.y = (float)(cvTsRandReal(rng)*a1 + b1);
+ if( point_type == CV_32SC2 )
+ {
+ pp->x = cvRound(p.x);
+ pp->y = cvRound(p.y);
+ }
+ else
+ {
+ *(CvPoint2D32f*)pp = p;
+ }
+ }
+}
+
- int conv = dy*hullvect[j].x - dx*hullvect[j].y;
-
- /*if ( (i==hull[j])||(i==hull[j+1]) ) continue; */
+int CV_BaseShapeDescrTest::prepare_test_case( int test_case_idx )
+{
+ int size;
+ int use_storage = 0;
+ int point_type;
+ int i;
+ CvRNG* rng = ts->get_rng();
+
+ CvTest::prepare_test_case( test_case_idx );
+
+ clear();
+ size = cvRound( exp((cvTsRandReal(rng) * (max_log_size - min_log_size) + min_log_size)*CV_LOG2) );
+ use_storage = cvTsRandInt(rng) % 2;
+ point_type = cvTsRandInt(rng) % 2 ? CV_32FC2 : CV_32SC2;
+
+ if( use_storage )
+ {
+ storage = cvCreateMemStorage( (cvTsRandInt(rng)%10 + 1)*1024 );
+ points1 = cvCreateSeq( point_type, sizeof(CvSeq), CV_ELEM_SIZE(point_type), storage );
+ cvSeqPushMulti( points1, 0, size );
+ points = points1;
+ }
+ else
+ {
+ int rows = 1, cols = size;
+ if( cvTsRandInt(rng) % 2 )
+ rows = size, cols = 1;
- if (orient == CV_CLOCKWISE) conv = -conv;
+ points2 = cvCreateMat( rows, cols, point_type );
+ points = points2;
+ }
- if ( conv < 0 )
- errors++;
+ for( i = 0; i < 2; i++ )
+ {
+ low.val[i] = cvTsRandReal(rng)*100 - 50;
+ high.val[i] = cvTsRandReal(rng)*100 - 50;
+ if( low.val[i] > high.val[i] )
+ {
+ double t;
+ CV_SWAP( low.val[i], high.val[i], t );
}
}
- cvFree((void**)&hullvect);
- /*assert( errors == 0); */
- return errors;
+
+ generate_point_set( points );
+ return 1;
+}
+
+
+void CV_BaseShapeDescrTest::extract_points()
+{
+ if( points1 )
+ {
+ points2 = cvCreateMat( 1, points1->total, CV_SEQ_ELTYPE(points1) );
+ cvCvtSeqToArray( points1, points2->data.ptr );
+ }
+
+ if( CV_MAT_DEPTH(points2->type) != CV_32F )
+ {
+ CvMat tmp = cvMat( points2->rows, points2->cols,
+ (points2->type & ~CV_MAT_DEPTH_MASK) | CV_32F, points2->data.ptr );
+ cvConvert( points2, &tmp );
+ }
}
-/* Testing parameters */
-static char test_desc[] = "Convex hull";
+void CV_BaseShapeDescrTest::run_func(void)
+{
+}
-static char TestClass[] = "Algorithm";
-static char* func_name[4] =
+
+int CV_BaseShapeDescrTest::validate_test_results( int /*test_case_idx*/ )
{
- "cvConvexHullApprox",
- "cvConvexHull",
- "cvContourConvexHullApprox",
- "cvContourConvexHull"
+ extract_points();
+ return 0;
+}
+
+
+CV_BaseShapeDescrTest shape_basetest( "shape", "" );
+
+
+/****************************************************************************************\
+* Convex Hull Test *
+\****************************************************************************************/
+
+class CV_ConvHullTest : public CV_BaseShapeDescrTest
+{
+public:
+ CV_ConvHullTest();
+ void clear();
+
+protected:
+ void run_func(void);
+ int prepare_test_case( int test_case_idx );
+ int validate_test_results( int test_case_idx );
+
+ CvSeq* hull1;
+ CvMat* hull2;
+ void* hull_storage;
+ int orientation;
+ int return_points;
};
-#define APPROX 0
-#define EXACT 1
-static int lScreenSize;
-static long lLoopsProp;
-static long lNumPoints;
+CV_ConvHullTest::CV_ConvHullTest():
+ CV_BaseShapeDescrTest( "shape-convhull", "cvConvexHull2" )
+{
+ hull1 = 0;
+ hull2 = 0;
+ hull_storage = 0;
+ orientation = return_points = 0;
+}
-static int fmaConvexHull(void* prm)
-{
- long lErrors = 0;
-
-
- static int read_param = 0;
- int i,j;
-
- CvPoint* Pts;
- int* hull;
- int count = 0;
-
- CvRect rect;
-
- int minx = 1000000, maxx = -10000;
- int miny = 1000000, maxy = -10000;
- long lParam = (long)(size_t)prm;
+void CV_ConvHullTest::clear()
+{
+ CV_BaseShapeDescrTest::clear();
+ cvReleaseMat( &hull2 );
+ hull1 = 0;
+ hull_storage = 0;
+}
+
+
+int CV_ConvHullTest::prepare_test_case( int test_case_idx )
+{
+ int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
+ int use_storage_for_hull = 0;
+ CvRNG* rng = ts->get_rng();
- if(!read_param)
+ if( code <= 0 )
+ return code;
+
+ orientation = cvTsRandInt(rng) % 2 ? CV_CLOCKWISE : CV_COUNTER_CLOCKWISE;
+ return_points = cvTsRandInt(rng) % 2;
+
+ use_storage_for_hull = cvTsRandInt(rng) % 2;
+ if( use_storage_for_hull )
{
- read_param=1;
-
- /* Reading test-parameters */
- trslRead( &lNumPoints, "4096", "Maximal number of points" );
- trslRead( &lLoopsProp, "100", "Loops" );
+ if( !storage )
+ storage = cvCreateMemStorage( (cvTsRandInt(rng)%10 + 1)*1024 );
+ hull_storage = storage;
}
-
- /* Allocating image */
- Pts = (CvPoint*)cvAlloc( lNumPoints * sizeof(CvPoint) );
- hull = (int*)cvAlloc( lNumPoints * sizeof(int) );
-
- for( j = 0; j < lLoopsProp; j++ )
+ else
{
- int numpts;
- ats1iInitRandom( 5, lNumPoints, &numpts, 1 );
+ int rows, cols;
+ int sz = points1 ? points1->total : points2->cols + points2->rows - 1;
+ int point_type = points1 ? CV_SEQ_ELTYPE(points1) : CV_MAT_TYPE(points2->type);
- /* init points */
- ats1iInitRandom( 5, 1024, &lScreenSize, 1 );
- ats1iInitRandom( 0, lScreenSize, (int*)Pts, 2*numpts ) ;
+ if( cvTsRandInt(rng) % 2 )
+ rows = sz, cols = 1;
+ else
+ rows = 1, cols = sz;
- for( i = 0; i < numpts ; i++ )
+ hull2 = cvCreateMat( rows, cols, return_points ? point_type : CV_32SC1 );
+ hull_storage = hull2;
+ }
+
+ return code;
+}
+
+
+void CV_ConvHullTest::run_func()
+{
+ hull1 = cvConvexHull2( points, hull_storage, orientation, return_points );
+}
+
+
+int CV_ConvHullTest::validate_test_results( int test_case_idx )
+{
+ int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
+ CvMat* hull = 0;
+ CvMat* mask = 0;
+ int i, point_count, hull_count;
+ CvPoint2D32f *p, *h;
+ CvSeq header, hheader, *ptseq, *hseq;
+ CvSeqBlock block, hblock;
+
+ if( points1 )
+ ptseq = points1;
+ else
+ ptseq = cvMakeSeqHeaderForArray( CV_MAT_TYPE(points2->type),
+ sizeof(CvSeq), CV_ELEM_SIZE(points2->type), points2->data.ptr,
+ points2->rows + points2->cols - 1, &header, &block );
+ point_count = ptseq->total;
+ p = (CvPoint2D32f*)(points2->data.ptr);
+
+ if( hull1 )
+ hseq = hull1;
+ else
+ hseq = cvMakeSeqHeaderForArray( CV_MAT_TYPE(hull2->type),
+ sizeof(CvSeq), CV_ELEM_SIZE(hull2->type), hull2->data.ptr,
+ hull2->rows + hull2->cols - 1, &hheader, &hblock );
+ hull_count = hseq->total;
+ hull = cvCreateMat( 1, hull_count, CV_32FC2 );
+ mask = cvCreateMat( 1, hull_count, CV_8UC1 );
+ cvZero( mask );
+ h = (CvPoint2D32f*)(hull->data.ptr);
+
+ // extract convex hull points
+ if( return_points )
+ {
+ cvCvtSeqToArray( hseq, hull->data.ptr );
+ if( CV_SEQ_ELTYPE(hseq) != CV_32FC2 )
{
- minx = MIN(Pts[i].x, minx );
- maxx = MAX(Pts[i].x, maxx );
- miny = MIN(Pts[i].y, miny );
- maxy = MAX(Pts[i].y, maxy );
+ CvMat tmp = cvMat( hull->rows, hull->cols, CV_32SC2, hull->data.ptr );
+ cvConvert( &tmp, hull );
}
+ }
+ else
+ {
+ CvSeqReader reader;
+ cvStartReadSeq( hseq, &reader );
- rect.x = minx;
- rect.y = miny;
- rect.width = maxx- minx + 1;
- rect.height = maxy- miny + 1;
-
- switch (lParam)
+ for( i = 0; i < hull_count; i++ )
{
- case APPROX:
- cvConvexHullApprox( Pts,
- numpts,
- &rect,
- 1,
- CV_COUNTER_CLOCKWISE,
- hull, &count );
- break;
- case EXACT:
- cvConvexHull( Pts,
- numpts,NULL,
- CV_COUNTER_CLOCKWISE,
- hull, &count );
- break;
-
- }/*switch */
-
- /* check errors */
- lErrors += atsCheckConvexHull( Pts, numpts, hull, count, CV_COUNTER_CLOCKWISE );
-
- } /* for */
+ char* ptr = reader.ptr;
+ int idx;
+ CV_NEXT_SEQ_ELEM( hseq->elem_size, reader );
+
+ if( hull1 )
+ idx = cvSeqElemIdx( ptseq, *(uchar**)ptr );
+ else
+ idx = *(int*)ptr;
+
+ if( idx < 0 || idx >= point_count )
+ {
+ ts->printf( CvTS::LOG, "Invalid convex hull point #%d\n", i );
+ code = CvTS::FAIL_INVALID_OUTPUT;
+ goto _exit_;
+ }
+ h[i] = p[idx];
+ }
+ }
-
- if( lErrors == 0 ) return trsResult( TRS_OK, "No errors fixed for this test" );
- else return trsResult( TRS_FAIL, "Total fixed %d errors", lErrors );
+ // check that the convex hull is a convex polygon
+ if( hull_count >= 3 )
+ {
+ CvPoint2D32f pt0 = h[hull_count-1];
+ for( i = 0; i < hull_count; i++ )
+ {
+ int j = i+1;
+ CvPoint2D32f pt1 = h[i], pt2 = h[j < hull_count ? j : 0];
+ float dx0 = pt1.x - pt0.x, dy0 = pt1.y - pt0.y;
+ float dx1 = pt2.x - pt1.x, dy1 = pt2.y - pt1.y;
+ double t = (double)dx0*dy1 - (double)dx1*dy0;
+ if( (t < 0) ^ (orientation != CV_COUNTER_CLOCKWISE) )
+ {
+ ts->printf( CvTS::LOG, "The convex hull is not convex or has a wrong orientation (vtx %d)\n", i );
+ code = CvTS::FAIL_INVALID_OUTPUT;
+ goto _exit_;
+ }
+ pt0 = pt1;
+ }
+ }
-}
+ // check that all the points are inside the hull or on the hull edge
+ // and at least hull_point points are at the hull vertices
+ for( i = 0; i < point_count; i++ )
+ {
+ int idx = 0, on_edge = 0;
+ double result = cvTsPointPolygonTest( p[i], h, hull_count, &idx, &on_edge );
-static int fmaConvexHullContour(void* prm)
-{
- long lErrors = 0;
-
- static int read_param = 0;
- int i,j;
-
- CvRect rect;
-
- int minx = 1000000, maxx = -10000;
- int miny = 1000000, maxy = -10000;
- long lParam = (long)(size_t)prm;
-
- CvPoint* points;
- CvPoint** pointers;
+ if( result < 0 )
+ {
+ ts->printf( CvTS::LOG, "The point #%d is outside of the convex hull\n", i );
+ code = CvTS::FAIL_BAD_ACCURACY;
+ goto _exit_;
+ }
+
+ if( result < FLT_EPSILON && !on_edge )
+ mask->data.ptr[idx] = (uchar)1;
+ }
+
+ if( cvNorm( mask, 0, CV_L1 ) != hull_count )
+ {
+ ts->printf( CvTS::LOG, "Not every convex hull vertex coincides with some input point\n" );
+ code = CvTS::FAIL_BAD_ACCURACY;
+ goto _exit_;
+ }
- CvSeqWriter writer;
- CvSeqReader reader;
+_exit_:
- CvSeq* contour;
- CvSeq* hull = NULL;
- CvMemStorage* storage;
+ cvReleaseMat( &hull );
+ cvReleaseMat( &mask );
+ if( code < 0 )
+ ts->set_failed_test_info( code );
+ return code;
+}
+
+
+CV_ConvHullTest shape_convhull_test;
+
+
+/****************************************************************************************\
+* MinAreaRect Test *
+\****************************************************************************************/
+
+class CV_MinAreaRectTest : public CV_BaseShapeDescrTest
+{
+public:
+ CV_MinAreaRectTest();
+
+protected:
+ void run_func(void);
+ int validate_test_results( int test_case_idx );
- if(!read_param)
+ CvBox2D box;
+ CvPoint2D32f box_pt[4];
+};
+
+
+CV_MinAreaRectTest::CV_MinAreaRectTest():
+ CV_BaseShapeDescrTest( "shape-minarearect", "cvMinAreaRect2, cvBoxPoints" )
+{
+}
+
+
+void CV_MinAreaRectTest::run_func()
+{
+ box = cvMinAreaRect2( points, storage );
+ cvBoxPoints( box, box_pt );
+}
+
+
+int CV_MinAreaRectTest::validate_test_results( int test_case_idx )
+{
+ double eps = 1e-2;
+ int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
+ int i, j, point_count = points2->rows + points2->cols - 1;
+ CvPoint2D32f *p = (CvPoint2D32f*)(points2->data.ptr);
+ int mask[] = {0,0,0,0};
+
+ // check that the bounding box is a rotated rectangle:
+ // 1. diagonals should be equal
+ // 2. they must intersect in their middle points
{
- read_param=1;
+ double d0 = cvTsDist( box_pt[0], box_pt[2] );
+ double d1 = cvTsDist( box_pt[1], box_pt[3] );
- /* Reading test-parameters */
- trslRead( &lNumPoints, "4096", "Maximal number of points" );
- trslRead( &lLoopsProp, "100", "Loops" );
+ double x0 = (box_pt[0].x + box_pt[2].x)*0.5;
+ double y0 = (box_pt[0].y + box_pt[2].y)*0.5;
+ double x1 = (box_pt[1].x + box_pt[3].x)*0.5;
+ double y1 = (box_pt[1].y + box_pt[3].y)*0.5;
+
+ if( fabs(d0 - d1) + fabs(x0 - x1) + fabs(y0 - y1) > eps*MAX(d0,d1) )
+ {
+ ts->printf( CvTS::LOG, "The bounding box is not a rectangle\n" );
+ code = CvTS::FAIL_INVALID_OUTPUT;
+ goto _exit_;
+ }
}
- storage = cvCreateMemStorage(0);
- cvClearMemStorage( storage );
-
- points = (CvPoint*)cvAlloc( lNumPoints * sizeof(CvPoint) );
- pointers = (CvPoint**)cvAlloc( lNumPoints * sizeof(CvPoint*) );
-
- for( j = 0; j < lLoopsProp; j++ )
+#if 0
{
- int numpts;
- /* Allocating points */
-
- cvStartWriteSeq( CV_SEQ_SIMPLE_POLYGON , sizeof(CvContour),
- sizeof(CvPoint), storage, &writer );
+ int n = 4;
+ double a = 4, c = 4, b = 200, d = 150;
+ CvPoint bp[4], *bpp = bp;
+ cvNamedWindow( "test", 1 );
+ IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
+ cvZero(img);
+ for( i = 0; i < point_count; i++ )
+ cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*c+d)), 3, CV_RGB(0,255,0), -1 );
+ for( i = 0; i < n; i++ )
+ bp[i] = cvPoint(cvRound(box_pt[i].x*a+b),cvRound(box_pt[i].y*c+d));
+ cvPolyLine( img, &bpp, &n, 1, 1, CV_RGB(255,255,0), 1, CV_AA, 0 );
+ cvShowImage( "test", img );
+ cvWaitKey();
+ cvReleaseImage(&img);
+ }
+#endif
- ats1iInitRandom( 5, lNumPoints, &numpts, 1 );
-
- /* init points */
- ats1iInitRandom( 5, 1024, &lScreenSize, 1 );
-
- for( i = 0; i < numpts ; i++ )
+ // check that the box includes all the points
+ // and there is at least one point at (or very close to) every box side
+ for( i = 0; i < point_count; i++ )
+ {
+ int idx = 0, on_edge = 0;
+ double result = cvTsPointPolygonTest( p[i], box_pt, 4, &idx, &on_edge );
+ if( result < -eps )
{
- CvPoint pt;
- ats1iInitRandom( 0, lScreenSize, (int*)&pt, 2 );
- CV_WRITE_SEQ_ELEM( pt, writer );
+ ts->printf( CvTS::LOG, "The point #%d is outside of the box\n", i );
+ code = CvTS::FAIL_BAD_ACCURACY;
+ goto _exit_;
+ }
- minx = MIN(pt.x, minx );
- maxx = MAX(pt.x, maxx );
- miny = MIN(pt.y, miny );
- maxy = MAX(pt.y, maxy );
+ if( result < eps )
+ {
+ for( j = 0; j < 4; j++ )
+ {
+ double d = cvTsPtLineDist( p[i], box_pt[(j-1)&3], box_pt[j] );
+ if( d < eps )
+ mask[j] = (uchar)1;
+ }
}
- contour = cvEndWriteSeq( &writer );
+ }
- rect.x = minx;
- rect.y = miny;
- rect.width = maxx- minx + 1;
- rect.height = maxy- miny + 1;
+ if( mask[0] + mask[1] + mask[2] + mask[3] != 4 )
+ {
+ ts->printf( CvTS::LOG, "Not every box side has a point nearby\n" );
+ code = CvTS::FAIL_BAD_ACCURACY;
+ goto _exit_;
+ }
- switch (lParam)
- {
- case APPROX:
- hull = cvContourConvexHullApprox( contour, 1, CV_COUNTER_CLOCKWISE,
- storage );
- break;
- case EXACT:
- hull = cvContourConvexHull( contour,CV_COUNTER_CLOCKWISE,
- storage );
- break;
-
- }/*switch */
+_exit_:
- /* check errors */
-
- cvStartReadSeq( contour, &reader, 0 );
- for( i = 0; i < contour->total; i++ )
- {
- CV_READ_SEQ_ELEM( points[i], reader );
- }
- cvStartReadSeq( hull, &reader, 0 );
- for( i = 0; i < hull->total; i++ )
- {
- CV_READ_SEQ_ELEM( pointers[i], reader );
-
- }
+ if( code < 0 )
+ ts->set_failed_test_info( code );
+ return code;
+}
- cvClearMemStorage( storage );
- lErrors += atsCheckConvexHullP( points, contour->total, pointers, hull->total,
- CV_COUNTER_CLOCKWISE );
-
-
- } /* for */
+CV_MinAreaRectTest shape_minarearect_test;
- cvFree((void**)&points);
- cvFree((void**)&pointers);
- cvReleaseMemStorage(&storage);
-
- if( lErrors == 0 ) return trsResult( TRS_OK, "No errors fixed for this test" );
- else return trsResult( TRS_FAIL, "Total fixed %d errors", lErrors );
-}
+/****************************************************************************************\
+* MinEnclosingCircle Test *
+\****************************************************************************************/
+
+class CV_MinCircleTest : public CV_BaseShapeDescrTest
+{
+public:
+ CV_MinCircleTest();
+
+protected:
+ void run_func(void);
+ int validate_test_results( int test_case_idx );
+
+ CvPoint2D32f center;
+ float radius;
+};
+
-void InitAConvexHull(void)
+CV_MinCircleTest::CV_MinCircleTest():
+ CV_BaseShapeDescrTest( "shape-mincircle", "cvMinEnclosingCircle" )
{
- /* Register test function */
- trsRegArg( func_name[0], test_desc, atsAlgoClass, fmaConvexHull, APPROX );
- trsRegArg( func_name[1], test_desc, atsAlgoClass, fmaConvexHull, EXACT );
- trsRegArg( func_name[2], test_desc, atsAlgoClass, fmaConvexHullContour, APPROX );
- trsRegArg( func_name[3], test_desc, atsAlgoClass, fmaConvexHullContour, EXACT );
+}
+
+
+void CV_MinCircleTest::run_func()
+{
+ cvMinEnclosingCircle( points, ¢er, &radius );
+}
+
+
+int CV_MinCircleTest::validate_test_results( int test_case_idx )
+{
+ double eps = 1.03;
+ int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
+ int i, j = 0, point_count = points2->rows + points2->cols - 1;
+ CvPoint2D32f *p = (CvPoint2D32f*)(points2->data.ptr);
+ CvPoint2D32f v[3];
+
+#if 0
+ {
+ double a = 2, b = 200, d = 400;
+ cvNamedWindow( "test", 1 );
+ IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
+ cvZero(img);
+ for( i = 0; i < point_count; i++ )
+ cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*a+d)), 3, CV_RGB(0,255,0), -1 );
+ cvCircle( img, cvPoint(cvRound(center.x*a+b),cvRound(center.y*a+d)),
+ cvRound(radius*a), CV_RGB(255,255,0), 1 );
+ cvShowImage( "test", img );
+ cvWaitKey();
+ cvReleaseImage(&img);
+ }
+#endif
+
+ // check that the circle contains all the points inside and
+ // remember at most 3 points that are close to the boundary
+ for( i = 0; i < point_count; i++ )
+ {
+ double d = cvTsDist( p[i], center );
+ if( d > radius )
+ {
+ ts->printf( CvTS::LOG, "The point #%d is outside of the circle\n", i );
+ code = CvTS::FAIL_BAD_ACCURACY;
+ goto _exit_;
+ }
+
+ if( radius - d < eps*radius && j < 3 )
+ v[j++] = p[i];
+ }
+
+ if( point_count >= 2 && (j < 2 || j == 2 && cvTsDist(v[0],v[1]) < (radius-1)*2/eps) )
+ {
+ ts->printf( CvTS::LOG,
+ "There should be at at least 3 points near the circle boundary or 2 points on the diameter\n" );
+ code = CvTS::FAIL_BAD_ACCURACY;
+ goto _exit_;
+ }
+_exit_:
+
+ if( code < 0 )
+ ts->set_failed_test_info( code );
+ return code;
+}
+
+
+CV_MinCircleTest shape_mincircle_test;
+
-} /* InitAConvexHull */
+/* End of file. */