git.maemo.org Git - opencv/blob - tests/cv/src/aconvhull.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   5 //  By downloading, copying, installing or using the software you agree to this license.
   6 //  If you do not agree to this license, do not download, install,
   7 //  copy or use the software.
   8 //
   9 //
  10 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  22 //   * Redistribution's in binary form must reproduce the above copyright notice,
  23 //     this list of conditions and the following disclaimer in the documentation
  24 //     and/or other materials provided with the distribution.
  25 //
  26 //   * The name of Intel Corporation may not be used to endorse or promote products
  27 //     derived from this software without specific prior written permission.
  28 //
  29 // This software is provided by the copyright holders and contributors "as is" and
  30 // any express or implied warranties, including, but not limited to, the implied
  31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  32 // In no event shall the Intel Corporation or contributors be liable for any direct,
  33 // indirect, incidental, special, exemplary, or consequential damages
  34 // (including, but not limited to, procurement of substitute goods or services;
  35 // loss of use, data, or profits; or business interruption) however caused
  36 // and on any theory of liability, whether in contract, strict liability,
  37 // or tort (including negligence or otherwise) arising in any way out of
  38 // the use of this software, even if advised of the possibility of such damage.
  39 //
  40 //M*/
  41
  42 #include "cvtest.h"
  43
  44 /*static int
  45 cvTsPointConvexPolygon( CvPoint2D32f pt, CvPoint2D32f* v, int n )
  46 {
  47     CvPoint2D32f v0 = v[n-1];
  48     int i, sign = 0;
  49
  50     for( i = 0; i < n; i++ )
  51     {
  52         CvPoint2D32f v1 = v[i];
  53         float dx = pt.x - v0.x, dy = pt.y - v0.y;
  54         float dx1 = v1.x - v0.x, dy1 = v1.y - v0.y;
  55         double t = (double)dx*dy1 - (double)dx1*dy;
  56         if( fabs(t) > DBL_EPSILON )
  57         {
  58             if( t*sign < 0 )
  59                 break;
  60             if( sign == 0 )
  61                 sign = t < 0 ? -1 : 1;
  62         }
  63         else if( fabs(dx) + fabs(dy) < DBL_EPSILON )
  64             return i+1;
  65         v0 = v1;
  66     }
  67
  68     return i < n ? -1 : 0;
  69 }*/
  70
  71 CV_INLINE double
  72 cvTsDist( CvPoint2D32f a, CvPoint2D32f b )
  73 {
  74     double dx = a.x - b.x;
  75     double dy = a.y - b.y;
  76     return sqrt(dx*dx + dy*dy);
  77 }
  78
  79 CV_INLINE double
  80 cvTsPtLineDist( CvPoint2D32f pt, CvPoint2D32f a, CvPoint2D32f b )
  81 {
  82     double d0 = cvTsDist( pt, a ), d1;
  83     double dd = cvTsDist( a, b );
  84     if( dd < FLT_EPSILON )
  85         return d0;
  86     d1 = cvTsDist( pt, b );
  87     dd = fabs((double)(pt.x - a.x)*(b.y - a.y) - (double)(pt.y - a.y)*(b.x - a.x))/dd;
  88     d0 = MIN( d0, d1 );
  89     return MIN( d0, dd );
  90 }
  91
  92 static double
  93 cvTsPointPolygonTest( CvPoint2D32f pt, const CvPoint2D32f* vv, int n, int* _idx=0, int* _on_edge=0 )
  94 {
  95     int i;
  96     CvPoint2D32f v = vv[n-1], v0;
  97     double min_dist_num = FLT_MAX, min_dist_denom = 1;
  98     int min_dist_idx = -1, min_on_edge = 0;
  99     int counter = 0;
 100     double result;
 101
 102     for( i = 0; i < n; i++ )
 103     {
 104         double dx, dy, dx1, dy1, dx2, dy2, dist_num, dist_denom = 1;
 105         int on_edge = 0, idx = i;
 106
 107         v0 = v; v = vv[i];
 108         dx = v.x - v0.x; dy = v.y - v0.y;
 109         dx1 = pt.x - v0.x; dy1 = pt.y - v0.y;
 110         dx2 = pt.x - v.x; dy2 = pt.y - v.y;
 111
 112         if( dx2*dx + dy2*dy >= 0 )
 113             dist_num = dx2*dx2 + dy2*dy2;
 114         else if( dx1*dx + dy1*dy <= 0 )
 115         {
 116             dist_num = dx1*dx1 + dy1*dy1;
 117             idx = i - 1;
 118             if( idx < 0 ) idx = n-1;
 119         }
 120         else
 121         {
 122             dist_num = (dy1*dx - dx1*dy);
 123             dist_num *= dist_num;
 124             dist_denom = dx*dx + dy*dy;
 125             on_edge = 1;
 126         }
 127
 128         if( dist_num*min_dist_denom < min_dist_num*dist_denom )
 129         {
 130             min_dist_num = dist_num;
 131             min_dist_denom = dist_denom;
 132             min_dist_idx = idx;
 133             min_on_edge = on_edge;
 134             if( min_dist_num == 0 )
 135                 break;
 136         }
 137
 138         if( v0.y <= pt.y && v.y <= pt.y ||
 139             v0.y > pt.y && v.y > pt.y ||
 140             v0.x < pt.x && v.x < pt.x )
 141             continue;
 142
 143         dist_num = dy1*dx - dx1*dy;
 144         if( dy < 0 )
 145             dist_num = -dist_num;
 146         counter += dist_num > 0;
 147     }
 148
 149     result = sqrt(min_dist_num/min_dist_denom);
 150     if( counter % 2 == 0 )
 151         result = -result;
 152
 153     if( _idx )
 154         *_idx = min_dist_idx;
 155     if( _on_edge )
 156         *_on_edge = min_on_edge;
 157
 158     return result;
 159 }
 160
 161
 162 /****************************************************************************************\
 163 *                              Base class for shape descriptor tests                     *
 164 \****************************************************************************************/
 165
 166 class CV_BaseShapeDescrTest : public CvTest
 167 {
 168 public:
 169     CV_BaseShapeDescrTest( const char* test_name, const char* test_funcs );
 170     virtual ~CV_BaseShapeDescrTest();
 171     void clear();
 172     int write_default_params(CvFileStorage* fs);
 173
 174 protected:
 175     int read_params( CvFileStorage* fs );
 176     void run_func(void);
 177     int prepare_test_case( int test_case_idx );
 178     int validate_test_results( int test_case_idx );
 179     virtual void generate_point_set( void* points );
 180     virtual void extract_points();
 181
 182     int min_log_size;
 183     int max_log_size;
 184     int dims;
 185     bool enable_flt_points;
 186
 187     CvMemStorage* storage;
 188     CvSeq* points1;
 189     CvMat* points2;
 190     void* points;
 191     void* result;
 192     double low_high_range;
 193     CvScalar low, high;
 194 };
 195
 196
 197 CV_BaseShapeDescrTest::CV_BaseShapeDescrTest( const char* test_name, const char* test_funcs ):
 198     CvTest( test_name, test_funcs )
 199 {
 200     points1 = 0;
 201     points2 = 0;
 202     points = 0;
 203     storage = 0;
 204     test_case_count = 500;
 205     min_log_size = 0;
 206     max_log_size = 10;
 207     low = high = cvScalarAll(0);
 208     low_high_range = 50;
 209     dims = 2;
 210     enable_flt_points = true;
 211
 212     support_testing_modes = CvTS::CORRECTNESS_CHECK_MODE;
 213 }
 214
 215
 216 CV_BaseShapeDescrTest::~CV_BaseShapeDescrTest()
 217 {
 218     clear();
 219 }
 220
 221
 222 void CV_BaseShapeDescrTest::clear()
 223 {
 224     CvTest::clear();
 225     cvReleaseMemStorage( &storage );
 226     cvReleaseMat( &points2 );
 227     points1 = 0;
 228     points = 0;
 229 }
 230
 231
 232 int CV_BaseShapeDescrTest::write_default_params( CvFileStorage* fs )
 233 {
 234     CvTest::write_default_params( fs );
 235     if( ts->get_testing_mode() != CvTS::TIMING_MODE )
 236     {
 237         write_param( fs, "test_case_count", test_case_count );
 238         write_param( fs, "min_log_size", min_log_size );
 239         write_param( fs, "max_log_size", max_log_size );
 240     }
 241     return 0;
 242 }
 243
 244
 245 int CV_BaseShapeDescrTest::read_params( CvFileStorage* fs )
 246 {
 247     int code = CvTest::read_params( fs );
 248     if( code < 0 )
 249         return code;
 250
 251     test_case_count = cvReadInt( find_param( fs, "struct_count" ), test_case_count );
 252     min_log_size = cvReadInt( find_param( fs, "min_log_size" ), min_log_size );
 253     max_log_size = cvReadInt( find_param( fs, "max_log_size" ), max_log_size );
 254
 255     min_log_size = cvTsClipInt( min_log_size, 0, 8 );
 256     max_log_size = cvTsClipInt( max_log_size, 0, 10 );
 257     if( min_log_size > max_log_size )
 258     {
 259         int t;
 260         CV_SWAP( min_log_size, max_log_size, t );
 261     }
 262
 263     return 0;
 264 }
 265
 266
 267 void CV_BaseShapeDescrTest::generate_point_set( void* points )
 268 {
 269     CvRNG* rng = ts->get_rng();
 270     int i, k, n, total, point_type;
 271     CvSeqReader reader;
 272     uchar* data = 0;
 273     double a[4], b[4];
 274
 275     for( k = 0; k < 4; k++ )
 276     {
 277         a[k] = high.val[k] - low.val[k];
 278         b[k] = low.val[k];
 279     }
 280     memset( &reader, 0, sizeof(reader) );
 281
 282     if( CV_IS_SEQ(points) )
 283     {
 284         CvSeq* ptseq = (CvSeq*)points;
 285         total = ptseq->total;
 286         point_type = CV_SEQ_ELTYPE(ptseq);
 287         cvStartReadSeq( ptseq, &reader );
 288     }
 289     else
 290     {
 291         CvMat* ptm = (CvMat*)points;
 292         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
 293         total = ptm->rows + ptm->cols - 1;
 294         point_type = CV_MAT_TYPE(ptm->type);
 295         data = ptm->data.ptr;
 296     }
 297
 298     n = CV_MAT_CN(point_type);
 299     point_type = CV_MAT_DEPTH(point_type);
 300
 301     assert( (point_type == CV_32S || point_type == CV_32F) && n <= 4 );
 302
 303     for( i = 0; i < total; i++ )
 304     {
 305         int* pi;
 306         float* pf;
 307         if( reader.ptr )
 308         {
 309             pi = (int*)reader.ptr;
 310             pf = (float*)reader.ptr;
 311             CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
 312         }
 313         else
 314         {
 315             pi = (int*)data + i*n;
 316             pf = (float*)data + i*n;
 317         }
 318         if( point_type == CV_32S )
 319             for( k = 0; k < n; k++ )
 320                 pi[k] = cvRound(cvTsRandReal(rng)*a[k] + b[k]);
 321         else
 322             for( k = 0; k < n; k++ )
 323                 pf[k] = (float)(cvTsRandReal(rng)*a[k] + b[k]);
 324     }
 325 }
 326
 327
 328 int CV_BaseShapeDescrTest::prepare_test_case( int test_case_idx )
 329 {
 330     int size;
 331     int use_storage = 0;
 332     int point_type;
 333     int i;
 334     CvRNG* rng = ts->get_rng();
 335
 336     CvTest::prepare_test_case( test_case_idx );
 337
 338     clear();
 339     size = cvRound( exp((cvTsRandReal(rng) * (max_log_size - min_log_size) + min_log_size)*CV_LOG2) );
 340     use_storage = cvTsRandInt(rng) % 2;
 341     point_type = CV_MAKETYPE(cvTsRandInt(rng) %
 342         (enable_flt_points ? 2 : 1) ? CV_32F : CV_32S, dims);
 343
 344     if( use_storage )
 345     {
 346         storage = cvCreateMemStorage( (cvTsRandInt(rng)%10 + 1)*1024 );
 347         points1 = cvCreateSeq( point_type, sizeof(CvSeq), CV_ELEM_SIZE(point_type), storage );
 348         cvSeqPushMulti( points1, 0, size );
 349         points = points1;
 350     }
 351     else
 352     {
 353         int rows = 1, cols = size;
 354         if( cvTsRandInt(rng) % 2 )
 355             rows = size, cols = 1;
 356
 357         points2 = cvCreateMat( rows, cols, point_type );
 358         points = points2;
 359     }
 360
 361     for( i = 0; i < 4; i++ )
 362     {
 363         low.val[i] = (cvTsRandReal(rng)-0.5)*low_high_range*2;
 364         high.val[i] = (cvTsRandReal(rng)-0.5)*low_high_range*2;
 365         if( low.val[i] > high.val[i] )
 366         {
 367             double t;
 368             CV_SWAP( low.val[i], high.val[i], t );
 369         }
 370     }
 371
 372     generate_point_set( points );
 373     return 1;
 374 }
 375
 376
 377 void CV_BaseShapeDescrTest::extract_points()
 378 {
 379     if( points1 )
 380     {
 381         points2 = cvCreateMat( 1, points1->total, CV_SEQ_ELTYPE(points1) );
 382         cvCvtSeqToArray( points1, points2->data.ptr );
 383     }
 384
 385     if( CV_MAT_DEPTH(points2->type) != CV_32F && enable_flt_points )
 386     {
 387         CvMat tmp = cvMat( points2->rows, points2->cols,
 388             (points2->type & ~CV_MAT_DEPTH_MASK) | CV_32F, points2->data.ptr );
 389         cvConvert( points2, &tmp );
 390     }
 391 }
 392
 393
 394 void CV_BaseShapeDescrTest::run_func(void)
 395 {
 396 }
 397
 398
 399 int CV_BaseShapeDescrTest::validate_test_results( int /*test_case_idx*/ )
 400 {
 401     extract_points();
 402     return 0;
 403 }
 404
 405
 406 CV_BaseShapeDescrTest shape_basetest( "shape", "" );
 407
 408
 409 /****************************************************************************************\
 410 *                                     Convex Hull Test                                   *
 411 \****************************************************************************************/
 412
 413 class CV_ConvHullTest : public CV_BaseShapeDescrTest
 414 {
 415 public:
 416     CV_ConvHullTest();
 417     virtual ~CV_ConvHullTest();
 418     void clear();
 419
 420 protected:
 421     void run_func(void);
 422     int prepare_test_case( int test_case_idx );
 423     int validate_test_results( int test_case_idx );
 424
 425     CvSeq* hull1;
 426     CvMat* hull2;
 427     void* hull_storage;
 428     int orientation;
 429     int return_points;
 430 };
 431
 432
 433 CV_ConvHullTest::CV_ConvHullTest():
 434     CV_BaseShapeDescrTest( "shape-convhull", "cvConvexHull2" )
 435 {
 436     hull1 = 0;
 437     hull2 = 0;
 438     hull_storage = 0;
 439     orientation = return_points = 0;
 440 }
 441
 442
 443 CV_ConvHullTest::~CV_ConvHullTest()
 444 {
 445     clear();
 446 }
 447
 448
 449 void CV_ConvHullTest::clear()
 450 {
 451     CV_BaseShapeDescrTest::clear();
 452     cvReleaseMat( &hull2 );
 453     hull1 = 0;
 454     hull_storage = 0;
 455 }
 456
 457
 458 int CV_ConvHullTest::prepare_test_case( int test_case_idx )
 459 {
 460     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
 461     int use_storage_for_hull = 0;
 462     CvRNG* rng = ts->get_rng();
 463
 464     if( code <= 0 )
 465         return code;
 466
 467     orientation = cvTsRandInt(rng) % 2 ? CV_CLOCKWISE : CV_COUNTER_CLOCKWISE;
 468     return_points = cvTsRandInt(rng) % 2;
 469
 470     use_storage_for_hull = cvTsRandInt(rng) % 2;
 471     if( use_storage_for_hull )
 472     {
 473         if( !storage )
 474             storage = cvCreateMemStorage( (cvTsRandInt(rng)%10 + 1)*1024 );
 475         hull_storage = storage;
 476     }
 477     else
 478     {
 479         int rows, cols;
 480         int sz = points1 ? points1->total : points2->cols + points2->rows - 1;
 481         int point_type = points1 ? CV_SEQ_ELTYPE(points1) : CV_MAT_TYPE(points2->type);
 482
 483         if( cvTsRandInt(rng) % 2 )
 484             rows = sz, cols = 1;
 485         else
 486             rows = 1, cols = sz;
 487
 488         hull2 = cvCreateMat( rows, cols, return_points ? point_type : CV_32SC1 );
 489         hull_storage = hull2;
 490     }
 491
 492     return code;
 493 }
 494
 495
 496 void CV_ConvHullTest::run_func()
 497 {
 498     hull1 = cvConvexHull2( points, hull_storage, orientation, return_points );
 499 }
 500
 501
 502 int CV_ConvHullTest::validate_test_results( int test_case_idx )
 503 {
 504     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 505     CvMat* hull = 0;
 506     CvMat* mask = 0;
 507     int i, point_count, hull_count;
 508     CvPoint2D32f *p, *h;
 509     CvSeq header, hheader, *ptseq, *hseq;
 510     CvSeqBlock block, hblock;
 511
 512     if( points1 )
 513         ptseq = points1;
 514     else
 515         ptseq = cvMakeSeqHeaderForArray( CV_MAT_TYPE(points2->type),
 516             sizeof(CvSeq), CV_ELEM_SIZE(points2->type), points2->data.ptr,
 517             points2->rows + points2->cols - 1, &header, &block );
 518     point_count = ptseq->total;
 519     p = (CvPoint2D32f*)(points2->data.ptr);
 520
 521     if( hull1 )
 522         hseq = hull1;
 523     else
 524         hseq = cvMakeSeqHeaderForArray( CV_MAT_TYPE(hull2->type),
 525             sizeof(CvSeq), CV_ELEM_SIZE(hull2->type), hull2->data.ptr,
 526             hull2->rows + hull2->cols - 1, &hheader, &hblock );
 527     hull_count = hseq->total;
 528     hull = cvCreateMat( 1, hull_count, CV_32FC2 );
 529     mask = cvCreateMat( 1, hull_count, CV_8UC1 );
 530     cvZero( mask );
 531     h = (CvPoint2D32f*)(hull->data.ptr);
 532
 533     // extract convex hull points
 534     if( return_points )
 535     {
 536         cvCvtSeqToArray( hseq, hull->data.ptr );
 537         if( CV_SEQ_ELTYPE(hseq) != CV_32FC2 )
 538         {
 539             CvMat tmp = cvMat( hull->rows, hull->cols, CV_32SC2, hull->data.ptr );
 540             cvConvert( &tmp, hull );
 541         }
 542     }
 543     else
 544     {
 545         CvSeqReader reader;
 546         cvStartReadSeq( hseq, &reader );
 547
 548         for( i = 0; i < hull_count; i++ )
 549         {
 550             schar* ptr = reader.ptr;
 551             int idx;
 552             CV_NEXT_SEQ_ELEM( hseq->elem_size, reader );
 553
 554             if( hull1 )
 555                 idx = cvSeqElemIdx( ptseq, *(uchar**)ptr );
 556             else
 557                 idx = *(int*)ptr;
 558
 559             if( idx < 0 || idx >= point_count )
 560             {
 561                 ts->printf( CvTS::LOG, "Invalid convex hull point #%d\n", i );
 562                 code = CvTS::FAIL_INVALID_OUTPUT;
 563                 goto _exit_;
 564             }
 565             h[i] = p[idx];
 566         }
 567     }
 568
 569     // check that the convex hull is a convex polygon
 570     if( hull_count >= 3 )
 571     {
 572         CvPoint2D32f pt0 = h[hull_count-1];
 573         for( i = 0; i < hull_count; i++ )
 574         {
 575             int j = i+1;
 576             CvPoint2D32f pt1 = h[i], pt2 = h[j < hull_count ? j : 0];
 577             float dx0 = pt1.x - pt0.x, dy0 = pt1.y - pt0.y;
 578             float dx1 = pt2.x - pt1.x, dy1 = pt2.y - pt1.y;
 579             double t = (double)dx0*dy1 - (double)dx1*dy0;
 580             if( (t < 0) ^ (orientation != CV_COUNTER_CLOCKWISE) )
 581             {
 582                 ts->printf( CvTS::LOG, "The convex hull is not convex or has a wrong orientation (vtx %d)\n", i );
 583                 code = CvTS::FAIL_INVALID_OUTPUT;
 584                 goto _exit_;
 585             }
 586             pt0 = pt1;
 587         }
 588     }
 589
 590     // check that all the points are inside the hull or on the hull edge
 591     // and at least hull_point points are at the hull vertices
 592     for( i = 0; i < point_count; i++ )
 593     {
 594         int idx = 0, on_edge = 0;
 595         double result = cvTsPointPolygonTest( p[i], h, hull_count, &idx, &on_edge );
 596
 597         if( result < 0 )
 598         {
 599             ts->printf( CvTS::LOG, "The point #%d is outside of the convex hull\n", i );
 600             code = CvTS::FAIL_BAD_ACCURACY;
 601             goto _exit_;
 602         }
 603
 604         if( result < FLT_EPSILON && !on_edge )
 605             mask->data.ptr[idx] = (uchar)1;
 606     }
 607
 608     if( cvNorm( mask, 0, CV_L1 ) != hull_count )
 609     {
 610         ts->printf( CvTS::LOG, "Not every convex hull vertex coincides with some input point\n" );
 611         code = CvTS::FAIL_BAD_ACCURACY;
 612         goto _exit_;
 613     }
 614
 615 _exit_:
 616
 617     cvReleaseMat( &hull );
 618     cvReleaseMat( &mask );
 619     if( code < 0 )
 620         ts->set_failed_test_info( code );
 621     return code;
 622 }
 623
 624
 625 CV_ConvHullTest shape_convhull_test;
 626
 627
 628 /****************************************************************************************\
 629 *                                     MinAreaRect Test                                   *
 630 \****************************************************************************************/
 631
 632 class CV_MinAreaRectTest : public CV_BaseShapeDescrTest
 633 {
 634 public:
 635     CV_MinAreaRectTest();
 636
 637 protected:
 638     void run_func(void);
 639     int validate_test_results( int test_case_idx );
 640
 641     CvBox2D box;
 642     CvPoint2D32f box_pt[4];
 643 };
 644
 645
 646 CV_MinAreaRectTest::CV_MinAreaRectTest():
 647     CV_BaseShapeDescrTest( "shape-minarearect", "cvMinAreaRect2, cvBoxPoints" )
 648 {
 649 }
 650
 651
 652 void CV_MinAreaRectTest::run_func()
 653 {
 654     box = cvMinAreaRect2( points, storage );
 655     cvBoxPoints( box, box_pt );
 656 }
 657
 658
 659 int CV_MinAreaRectTest::validate_test_results( int test_case_idx )
 660 {
 661     double eps = 1e-1;
 662     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 663     int i, j, point_count = points2->rows + points2->cols - 1;
 664     CvPoint2D32f *p = (CvPoint2D32f*)(points2->data.ptr);
 665     int mask[] = {0,0,0,0};
 666
 667     // check that the bounding box is a rotated rectangle:
 668     //  1. diagonals should be equal
 669     //  2. they must intersect in their middle points
 670     {
 671         double d0 = cvTsDist( box_pt[0], box_pt[2] );
 672         double d1 = cvTsDist( box_pt[1], box_pt[3] );
 673
 674         double x0 = (box_pt[0].x + box_pt[2].x)*0.5;
 675         double y0 = (box_pt[0].y + box_pt[2].y)*0.5;
 676         double x1 = (box_pt[1].x + box_pt[3].x)*0.5;
 677         double y1 = (box_pt[1].y + box_pt[3].y)*0.5;
 678
 679         if( fabs(d0 - d1) + fabs(x0 - x1) + fabs(y0 - y1) > eps*MAX(d0,d1) )
 680         {
 681             ts->printf( CvTS::LOG, "The bounding box is not a rectangle\n" );
 682             code = CvTS::FAIL_INVALID_OUTPUT;
 683             goto _exit_;
 684         }
 685     }
 686
 687 #if 0
 688     {
 689     int n = 4;
 690     double a = 8, c = 8, b = 100, d = 150;
 691     CvPoint bp[4], *bpp = bp;
 692     cvNamedWindow( "test", 1 );
 693     IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
 694     cvZero(img);
 695     for( i = 0; i < point_count; i++ )
 696         cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*c+d)), 3, CV_RGB(0,255,0), -1 );
 697     for( i = 0; i < n; i++ )
 698         bp[i] = cvPoint(cvRound(box_pt[i].x*a+b),cvRound(box_pt[i].y*c+d));
 699     cvPolyLine( img, &bpp, &n, 1, 1, CV_RGB(255,255,0), 1, CV_AA, 0 );
 700     cvShowImage( "test", img );
 701     cvWaitKey();
 702     cvReleaseImage(&img);
 703     }
 704 #endif
 705
 706     // check that the box includes all the points
 707     // and there is at least one point at (or very close to) every box side
 708     for( i = 0; i < point_count; i++ )
 709     {
 710         int idx = 0, on_edge = 0;
 711         double result = cvTsPointPolygonTest( p[i], box_pt, 4, &idx, &on_edge );
 712         if( result < -eps )
 713         {
 714             ts->printf( CvTS::LOG, "The point #%d is outside of the box\n", i );
 715             code = CvTS::FAIL_BAD_ACCURACY;
 716             goto _exit_;
 717         }
 718
 719         if( result < eps )
 720         {
 721             for( j = 0; j < 4; j++ )
 722             {
 723                 double d = cvTsPtLineDist( p[i], box_pt[(j-1)&3], box_pt[j] );
 724                 if( d < eps )
 725                     mask[j] = (uchar)1;
 726             }
 727         }
 728     }
 729
 730     if( mask[0] + mask[1] + mask[2] + mask[3] != 4 )
 731     {
 732         ts->printf( CvTS::LOG, "Not every box side has a point nearby\n" );
 733         code = CvTS::FAIL_BAD_ACCURACY;
 734         goto _exit_;
 735     }
 736
 737 _exit_:
 738
 739     if( code < 0 )
 740         ts->set_failed_test_info( code );
 741     return code;
 742 }
 743
 744
 745 CV_MinAreaRectTest shape_minarearect_test;
 746
 747
 748 /****************************************************************************************\
 749 *                                     MinEnclosingCircle Test                            *
 750 \****************************************************************************************/
 751
 752 class CV_MinCircleTest : public CV_BaseShapeDescrTest
 753 {
 754 public:
 755     CV_MinCircleTest();
 756
 757 protected:
 758     void run_func(void);
 759     int validate_test_results( int test_case_idx );
 760
 761     CvPoint2D32f center;
 762     float radius;
 763 };
 764
 765
 766 CV_MinCircleTest::CV_MinCircleTest():
 767     CV_BaseShapeDescrTest( "shape-mincircle", "cvMinEnclosingCircle" )
 768 {
 769 }
 770
 771
 772 void CV_MinCircleTest::run_func()
 773 {
 774     cvMinEnclosingCircle( points, &center, &radius );
 775 }
 776
 777
 778 int CV_MinCircleTest::validate_test_results( int test_case_idx )
 779 {
 780     double eps = 1.03;
 781     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 782     int i, j = 0, point_count = points2->rows + points2->cols - 1;
 783     CvPoint2D32f *p = (CvPoint2D32f*)(points2->data.ptr);
 784     CvPoint2D32f v[3];
 785
 786 #if 0
 787     {
 788     double a = 2, b = 200, d = 400;
 789     cvNamedWindow( "test", 1 );
 790     IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
 791     cvZero(img);
 792     for( i = 0; i < point_count; i++ )
 793         cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*a+d)), 3, CV_RGB(0,255,0), -1 );
 794     cvCircle( img, cvPoint(cvRound(center.x*a+b),cvRound(center.y*a+d)),
 795               cvRound(radius*a), CV_RGB(255,255,0), 1 );
 796     cvShowImage( "test", img );
 797     cvWaitKey();
 798     cvReleaseImage(&img);
 799     }
 800 #endif
 801
 802     // check that the circle contains all the points inside and
 803     // remember at most 3 points that are close to the boundary
 804     for( i = 0; i < point_count; i++ )
 805     {
 806         double d = cvTsDist( p[i], center );
 807         if( d > radius )
 808         {
 809             ts->printf( CvTS::LOG, "The point #%d is outside of the circle\n", i );
 810             code = CvTS::FAIL_BAD_ACCURACY;
 811             goto _exit_;
 812         }
 813
 814         if( radius - d < eps*radius && j < 3 )
 815             v[j++] = p[i];
 816     }
 817
 818     if( point_count >= 2 && (j < 2 || j == 2 && cvTsDist(v[0],v[1]) < (radius-1)*2/eps) )
 819     {
 820         ts->printf( CvTS::LOG,
 821             "There should be at at least 3 points near the circle boundary or 2 points on the diameter\n" );
 822         code = CvTS::FAIL_BAD_ACCURACY;
 823         goto _exit_;
 824     }
 825
 826 _exit_:
 827
 828     if( code < 0 )
 829         ts->set_failed_test_info( code );
 830     return code;
 831 }
 832
 833
 834 CV_MinCircleTest shape_mincircle_test;
 835
 836
 837 /****************************************************************************************\
 838 *                                   Perimeter Test                                     *
 839 \****************************************************************************************/
 840
 841 class CV_PerimeterTest : public CV_BaseShapeDescrTest
 842 {
 843 public:
 844     CV_PerimeterTest();
 845
 846 protected:
 847     int prepare_test_case( int test_case_idx );
 848     void run_func(void);
 849     int validate_test_results( int test_case_idx );
 850     CvSlice slice;
 851     int is_closed;
 852     double result;
 853 };
 854
 855
 856 CV_PerimeterTest::CV_PerimeterTest():
 857     CV_BaseShapeDescrTest( "shape-perimeter", "cvArcLength" )
 858 {
 859 }
 860
 861
 862 int CV_PerimeterTest::prepare_test_case( int test_case_idx )
 863 {
 864     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
 865     CvRNG* rng = ts->get_rng();
 866     int total;
 867
 868     if( code < 0 )
 869         return code;
 870
 871     is_closed = cvTsRandInt(rng) % 2;
 872
 873     if( points1 )
 874     {
 875         points1->flags |= CV_SEQ_KIND_CURVE;
 876         if( is_closed )
 877             points1->flags |= CV_SEQ_FLAG_CLOSED;
 878         total = points1->total;
 879     }
 880     else
 881         total = points2->cols + points2->rows - 1;
 882
 883     if( cvTsRandInt(rng) % 3 )
 884     {
 885         slice.start_index = cvTsRandInt(rng) % total;
 886         slice.end_index = cvTsRandInt(rng) % total;
 887     }
 888     else
 889         slice = CV_WHOLE_SEQ;
 890
 891     return 1;
 892 }
 893
 894
 895 void CV_PerimeterTest::run_func()
 896 {
 897     result = cvArcLength( points, slice, points1 ? -1 : is_closed );
 898 }
 899
 900
 901 int CV_PerimeterTest::validate_test_results( int test_case_idx )
 902 {
 903     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 904     int i, len = slice.end_index - slice.start_index, total = points2->cols + points2->rows - 1;
 905     double result0 = 0;
 906     CvPoint2D32f prev_pt, pt, *ptr;
 907
 908     if( len < 0 )
 909         len += total;
 910
 911     len = MIN( len, total );
 912     len -= !is_closed && len == total;
 913
 914     ptr = (CvPoint2D32f*)points2->data.fl;
 915     prev_pt = ptr[slice.start_index % total];
 916
 917     for( i = 1; i <= len; i++ )
 918     {
 919         pt = ptr[(i + slice.start_index) % total];
 920         double dx = pt.x - prev_pt.x, dy = pt.y - prev_pt.y;
 921         result0 += sqrt(dx*dx + dy*dy);
 922         prev_pt = pt;
 923     }
 924
 925     if( cvIsNaN(result) || cvIsInf(result) )
 926     {
 927         ts->printf( CvTS::LOG, "cvArcLength() returned invalid value (%g)\n", result );
 928         code = CvTS::FAIL_INVALID_OUTPUT;
 929     }
 930     else if( fabs(result - result0) > FLT_EPSILON*100*result0 )
 931     {
 932         ts->printf( CvTS::LOG, "The function returned %g, while the correct result is %g\n", result, result0 );
 933         code = CvTS::FAIL_BAD_ACCURACY;
 934     }
 935
 936     if( code < 0 )
 937         ts->set_failed_test_info( code );
 938     return code;
 939 }
 940
 941
 942 CV_PerimeterTest shape_perimeter_test;
 943
 944
 945
 946 /****************************************************************************************\
 947 *                                   FitEllipse Test                                      *
 948 \****************************************************************************************/
 949
 950 class CV_FitEllipseTest : public CV_BaseShapeDescrTest
 951 {
 952 public:
 953     CV_FitEllipseTest();
 954
 955 protected:
 956     int prepare_test_case( int test_case_idx );
 957     void generate_point_set( void* points );
 958     void run_func(void);
 959     int validate_test_results( int test_case_idx );
 960     CvBox2D box0, box;
 961     double min_ellipse_size, max_noise;
 962 };
 963
 964
 965 CV_FitEllipseTest::CV_FitEllipseTest():
 966     CV_BaseShapeDescrTest( "shape-fit-ellipse", "cvFitEllipse" )
 967 {
 968     min_log_size = 4; // for robust ellipse fitting a dozen of points is needed at least
 969     max_log_size = 10;
 970     min_ellipse_size = 10;
 971     max_noise = 0.05;
 972 }
 973
 974
 975 void CV_FitEllipseTest::generate_point_set( void* points )
 976 {
 977     CvRNG* rng = ts->get_rng();
 978     int i, total, point_type;
 979     CvSeqReader reader;
 980     uchar* data = 0;
 981     double a, b;
 982
 983     box0.center.x = (float)((low.val[0] + high.val[0])*0.5);
 984     box0.center.y = (float)((low.val[1] + high.val[1])*0.5);
 985     box0.size.width = (float)(MAX(high.val[0] - low.val[0], min_ellipse_size)*2);
 986     box0.size.height = (float)(MAX(high.val[1] - low.val[1], min_ellipse_size)*2);
 987     box0.angle = (float)(cvTsRandReal(rng)*180);
 988     a = cos(box0.angle*CV_PI/180.);
 989     b = sin(box0.angle*CV_PI/180.);
 990
 991     if( box0.size.width > box0.size.height )
 992     {
 993         float t;
 994         CV_SWAP( box0.size.width, box0.size.height, t );
 995     }
 996     memset( &reader, 0, sizeof(reader) );
 997
 998     if( CV_IS_SEQ(points) )
 999     {
1000         CvSeq* ptseq = (CvSeq*)points;
1001         total = ptseq->total;
1002         point_type = CV_SEQ_ELTYPE(ptseq);
1003         cvStartReadSeq( ptseq, &reader );
1004     }
1005     else
1006     {
1007         CvMat* ptm = (CvMat*)points;
1008         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
1009         total = ptm->rows + ptm->cols - 1;
1010         point_type = CV_MAT_TYPE(ptm->type);
1011         data = ptm->data.ptr;
1012     }
1013
1014     assert( point_type == CV_32SC2 || point_type == CV_32FC2 );
1015
1016     for( i = 0; i < total; i++ )
1017     {
1018         CvPoint* pp;
1019         CvPoint2D32f p;
1020         double angle = cvTsRandReal(rng)*CV_PI*2;
1021         double x = box0.size.height*0.5*(cos(angle) + (cvTsRandReal(rng)-0.5)*2*max_noise);
1022         double y = box0.size.width*0.5*(sin(angle) + (cvTsRandReal(rng)-0.5)*2*max_noise);
1023         p.x = (float)(box0.center.x + a*x + b*y);
1024         p.y = (float)(box0.center.y - b*x + a*y);
1025
1026         if( reader.ptr )
1027         {
1028             pp = (CvPoint*)reader.ptr;
1029             CV_NEXT_SEQ_ELEM( sizeof(*pp), reader );
1030         }
1031         else
1032             pp = ((CvPoint*)data) + i;
1033         if( point_type == CV_32SC2 )
1034         {
1035             pp->x = cvRound(p.x);
1036             pp->y = cvRound(p.y);
1037         }
1038         else
1039             *(CvPoint2D32f*)pp = p;
1040     }
1041 }
1042
1043
1044 int CV_FitEllipseTest::prepare_test_case( int test_case_idx )
1045 {
1046     min_log_size = MAX(min_log_size,4);
1047     max_log_size = MAX(min_log_size,max_log_size);
1048     return CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1049 }
1050
1051
1052 void CV_FitEllipseTest::run_func()
1053 {
1054     box = cvFitEllipse2( points );
1055 }
1056
1057
1058 int CV_FitEllipseTest::validate_test_results( int test_case_idx )
1059 {
1060     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1061     double diff_angle;
1062
1063     if( cvIsNaN(box.center.x) || cvIsInf(box.center.x) ||
1064         cvIsNaN(box.center.y) || cvIsInf(box.center.y) ||
1065         cvIsNaN(box.size.width) || cvIsInf(box.size.width) ||
1066         cvIsNaN(box.size.height) || cvIsInf(box.size.height) ||
1067         cvIsNaN(box.angle) || cvIsInf(box.angle) )
1068     {
1069         ts->printf( CvTS::LOG, "Some of the computed ellipse parameters are invalid (x=%g,y=%g,w=%g,h=%g,angle=%g)\n",
1070             box.center.x, box.center.y, box.size.width, box.size.height, box.angle );
1071         code = CvTS::FAIL_INVALID_OUTPUT;
1072         goto _exit_;
1073     }
1074
1075     box.angle = (float)(90-box.angle);
1076     if( box.angle < 0 )
1077         box.angle += 360;
1078     if( box.angle > 360 )
1079         box.angle -= 360;
1080
1081     if( fabs(box.center.x - box0.center.x) > 3 ||
1082         fabs(box.center.y - box0.center.y) > 3 ||
1083         fabs(box.size.width - box0.size.width) > 0.1*fabs(box0.size.width) ||
1084         fabs(box.size.height - box0.size.height) > 0.1*fabs(box0.size.height) )
1085     {
1086         ts->printf( CvTS::LOG, "The computed ellipse center and/or size are incorrect:\n\t"
1087             "(x=%.1f,y=%.1f,w=%.1f,h=%.1f), while it should be (x=%.1f,y=%.1f,w=%.1f,h=%.1f)\n",
1088             box.center.x, box.center.y, box.size.width, box.size.height,
1089             box0.center.x, box0.center.y, box0.size.width, box0.size.height );
1090         code = CvTS::FAIL_BAD_ACCURACY;
1091         goto _exit_;
1092     }
1093
1094     diff_angle = fabs(box0.angle - box.angle);
1095     diff_angle = MIN( diff_angle, fabs(diff_angle - 360));
1096     diff_angle = MIN( diff_angle, fabs(diff_angle - 180));
1097
1098     if( box0.size.height >= 1.3*box0.size.width && diff_angle > 30 )
1099     {
1100         ts->printf( CvTS::LOG, "Incorrect ellipse angle (=%1.f, should be %1.f)\n",
1101             box.angle, box0.angle );
1102         code = CvTS::FAIL_BAD_ACCURACY;
1103         goto _exit_;
1104     }
1105
1106 _exit_:
1107
1108 #if 0
1109     cvNamedWindow( "test", 0 );
1110     IplImage* img = cvCreateImage( cvSize(cvRound(low_high_range*4),
1111         cvRound(low_high_range*4)), 8, 3 );
1112     cvZero( img );
1113
1114     box.center.x += (float)low_high_range*2;
1115     box.center.y += (float)low_high_range*2;
1116     cvEllipseBox( img, box, CV_RGB(255,0,0), 3, 8 );
1117
1118     for( int i = 0; i < points2->rows + points2->cols - 1; i++ )
1119     {
1120         CvPoint pt;
1121         pt.x = cvRound(points2->data.fl[i*2] + low_high_range*2);
1122         pt.y = cvRound(points2->data.fl[i*2+1] + low_high_range*2);
1123         cvCircle( img, pt, 1, CV_RGB(255,255,255), -1, 8 );
1124     }
1125
1126     cvShowImage( "test", img );
1127     cvReleaseImage( &img );
1128     cvWaitKey(0);
1129 #endif
1130
1131     if( code < 0 )
1132     {
1133         ts->set_failed_test_info( code );
1134     }
1135     return code;
1136 }
1137
1138
1139 CV_FitEllipseTest fit_ellipse_test;
1140
1141
1142
1143 /****************************************************************************************\
1144 *                                   FitLine Test                                         *
1145 \****************************************************************************************/
1146
1147 class CV_FitLineTest : public CV_BaseShapeDescrTest
1148 {
1149 public:
1150     CV_FitLineTest();
1151
1152 protected:
1153     int prepare_test_case( int test_case_idx );
1154     void generate_point_set( void* points );
1155     void run_func(void);
1156     int validate_test_results( int test_case_idx );
1157     double max_noise;
1158     float line[6], line0[6];
1159     int dist_type;
1160     double reps, aeps;
1161 };
1162
1163
1164 CV_FitLineTest::CV_FitLineTest():
1165     CV_BaseShapeDescrTest( "shape-fit-line", "cvFitLine" )
1166 {
1167     min_log_size = 4; // for robust ellipse fitting a dozen of points is needed at least
1168     max_log_size = 10;
1169     max_noise = 0.05;
1170 }
1171
1172
1173 void CV_FitLineTest::generate_point_set( void* points )
1174 {
1175     CvRNG* rng = ts->get_rng();
1176     int i, k, n, total, point_type;
1177     CvSeqReader reader;
1178     uchar* data = 0;
1179     double s = 0;
1180
1181     n = dims;
1182     for( k = 0; k < n; k++ )
1183     {
1184         line0[k+n] = (float)((low.val[k] + high.val[k])*0.5);
1185         line0[k] = (float)(high.val[k] - low.val[k]);
1186         if( cvTsRandInt(rng) % 2 )
1187             line0[k] = -line0[k];
1188         s += (double)line0[k]*line0[k];
1189     }
1190
1191     s = 1./sqrt(s);
1192     for( k = 0; k < n; k++ )
1193         line0[k] = (float)(line0[k]*s);
1194
1195     memset( &reader, 0, sizeof(reader) );
1196
1197     if( CV_IS_SEQ(points) )
1198     {
1199         CvSeq* ptseq = (CvSeq*)points;
1200         total = ptseq->total;
1201         point_type = CV_MAT_DEPTH(CV_SEQ_ELTYPE(ptseq));
1202         cvStartReadSeq( ptseq, &reader );
1203     }
1204     else
1205     {
1206         CvMat* ptm = (CvMat*)points;
1207         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
1208         total = ptm->rows + ptm->cols - 1;
1209         point_type = CV_MAT_DEPTH(CV_MAT_TYPE(ptm->type));
1210         data = ptm->data.ptr;
1211     }
1212
1213     for( i = 0; i < total; i++ )
1214     {
1215         int* pi;
1216         float* pf;
1217         float p[4], t;
1218         if( reader.ptr )
1219         {
1220             pi = (int*)reader.ptr;
1221             pf = (float*)reader.ptr;
1222             CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
1223         }
1224         else
1225         {
1226             pi = (int*)data + i*n;
1227             pf = (float*)data + i*n;
1228         }
1229
1230         t = (float)((cvTsRandReal(rng)-0.5)*low_high_range*2);
1231
1232         for( k = 0; k < n; k++ )
1233             p[k] = (float)((cvTsRandReal(rng)-0.5)*max_noise*2 + t*line0[k] + line0[k+n]);
1234
1235         if( point_type == CV_32S )
1236             for( k = 0; k < n; k++ )
1237                 pi[k] = cvRound(p[k]);
1238         else
1239             for( k = 0; k < n; k++ )
1240                 pf[k] = p[k];
1241     }
1242 }
1243
1244
1245 int CV_FitLineTest::prepare_test_case( int test_case_idx )
1246 {
1247     CvRNG* rng = ts->get_rng();
1248     dims = cvTsRandInt(rng) % 2 + 2;
1249     min_log_size = MAX(min_log_size,5);
1250     max_log_size = MAX(min_log_size,max_log_size);
1251     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1252     dist_type = cvTsRandInt(rng) % 6 + 1;
1253     dist_type += dist_type == CV_DIST_C;
1254     reps = 0.1; aeps = 0.01;
1255     return code;
1256 }
1257
1258
1259 void CV_FitLineTest::run_func()
1260 {
1261     cvFitLine( points, dist_type, 0, reps, aeps, line );
1262 }
1263
1264
1265 int CV_FitLineTest::validate_test_results( int test_case_idx )
1266 {
1267     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1268     int k, max_k = 0;
1269     double vec_diff = 0, t;
1270
1271     for( k = 0; k < dims*2; k++ )
1272     {
1273         if( cvIsNaN(line[k]) || cvIsInf(line[k]) )
1274         {
1275             ts->printf( CvTS::LOG, "Some of the computed line parameters are invalid (line[%d]=%g)\n",
1276                 k, line[k] );
1277             code = CvTS::FAIL_INVALID_OUTPUT;
1278             goto _exit_;
1279         }
1280     }
1281
1282     if( fabs(line0[1]) > fabs(line0[0]) )
1283         max_k = 1;
1284     if( fabs(line0[dims-1]) > fabs(line0[max_k]) )
1285         max_k = dims-1;
1286     if( line0[max_k] < 0 )
1287         for( k = 0; k < dims; k++ )
1288             line0[k] = -line0[k];
1289     if( line[max_k] < 0 )
1290         for( k = 0; k < dims; k++ )
1291             line[k] = -line[k];
1292
1293     for( k = 0; k < dims; k++ )
1294     {
1295         double dt = line[k] - line0[k];
1296         vec_diff += dt*dt;
1297     }
1298
1299     if( sqrt(vec_diff) > 0.05 )
1300     {
1301         if( dims == 2 )
1302             ts->printf( CvTS::LOG,
1303                 "The computed line vector (%.2f,%.2f) is different from the actual (%.2f,%.2f)\n",
1304                 line[0], line[1], line0[0], line0[1] );
1305         else
1306             ts->printf( CvTS::LOG,
1307                 "The computed line vector (%.2f,%.2f,%.2f) is different from the actual (%.2f,%.2f,%.2f)\n",
1308                 line[0], line[1], line[2], line0[0], line0[1], line0[2] );
1309         code = CvTS::FAIL_BAD_ACCURACY;
1310         goto _exit_;
1311     }
1312
1313     t = (line[max_k+dims] - line0[max_k+dims])/line0[max_k];
1314     for( k = 0; k < dims; k++ )
1315     {
1316         double p = line0[k+dims] + t*line0[k] - line[k+dims];
1317         vec_diff += p*p;
1318     }
1319
1320     if( sqrt(vec_diff) > 1*MAX(fabs(t),1) )
1321     {
1322         if( dims == 2 )
1323             ts->printf( CvTS::LOG,
1324                 "The computed line point (%.2f,%.2f) is too far from the actual line\n",
1325                 line[2]+line0[2], line[3]+line0[3] );
1326         else
1327             ts->printf( CvTS::LOG,
1328                 "The computed line point (%.2f,%.2f,%.2f) is too far from the actual line\n",
1329                 line[3]+line0[3], line[4]+line0[4], line[5]+line0[5] );
1330         code = CvTS::FAIL_BAD_ACCURACY;
1331         goto _exit_;
1332     }
1333
1334 _exit_:
1335
1336     if( code < 0 )
1337     {
1338         ts->set_failed_test_info( code );
1339     }
1340     return code;
1341 }
1342
1343
1344 CV_FitLineTest fit_line_test;
1345
1346
1347 /****************************************************************************************\
1348 *                                   ContourMoments Test                                  *
1349 \****************************************************************************************/
1350
1351
1352 static void
1353 cvTsGenerateTousledBlob( CvPoint2D32f center, CvSize2D32f axes,
1354     double max_r_scale, double angle, CvArr* points, CvRNG* rng )
1355 {
1356     int i, total, point_type;
1357     uchar* data = 0;
1358     CvSeqReader reader;
1359     memset( &reader, 0, sizeof(reader) );
1360
1361     if( CV_IS_SEQ(points) )
1362     {
1363         CvSeq* ptseq = (CvSeq*)points;
1364         total = ptseq->total;
1365         point_type = CV_SEQ_ELTYPE(ptseq);
1366         cvStartReadSeq( ptseq, &reader );
1367     }
1368     else
1369     {
1370         CvMat* ptm = (CvMat*)points;
1371         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
1372         total = ptm->rows + ptm->cols - 1;
1373         point_type = CV_MAT_TYPE(ptm->type);
1374         data = ptm->data.ptr;
1375     }
1376
1377     assert( point_type == CV_32SC2 || point_type == CV_32FC2 );
1378
1379     for( i = 0; i < total; i++ )
1380     {
1381         CvPoint* pp;
1382         CvPoint2D32f p;
1383
1384         double phi0 = 2*CV_PI*i/total;
1385         double phi = CV_PI*angle/180.;
1386         double t = cvTsRandReal(rng)*max_r_scale + (1 - max_r_scale);
1387         double ta = axes.height*t;
1388         double tb = axes.width*t;
1389         double c0 = cos(phi0)*ta, s0 = sin(phi0)*tb;
1390         double c = cos(phi), s = sin(phi);
1391         p.x = (float)(c0*c - s0*s + center.x);
1392         p.y = (float)(c0*s + s0*c + center.y);
1393
1394         if( reader.ptr )
1395         {
1396             pp = (CvPoint*)reader.ptr;
1397             CV_NEXT_SEQ_ELEM( sizeof(*pp), reader );
1398         }
1399         else
1400             pp = ((CvPoint*)data) + i;
1401
1402         if( point_type == CV_32SC2 )
1403         {
1404             pp->x = cvRound(p.x);
1405             pp->y = cvRound(p.y);
1406         }
1407         else
1408             *(CvPoint2D32f*)pp = p;
1409     }
1410 }
1411
1412
1413 class CV_ContourMomentsTest : public CV_BaseShapeDescrTest
1414 {
1415 public:
1416     CV_ContourMomentsTest();
1417
1418 protected:
1419     int prepare_test_case( int test_case_idx );
1420     void generate_point_set( void* points );
1421     void run_func(void);
1422     int validate_test_results( int test_case_idx );
1423     CvMoments moments0, moments;
1424     double area0, area;
1425     CvSize2D32f axes;
1426     CvPoint2D32f center;
1427     int max_max_r_scale;
1428     double max_r_scale, angle;
1429     CvSize img_size;
1430 };
1431
1432
1433 CV_ContourMomentsTest::CV_ContourMomentsTest():
1434     CV_BaseShapeDescrTest( "shape-moments", "cvMoments, cvContourArea" )
1435 {
1436     min_log_size = 3;
1437     max_log_size = 8;
1438     max_max_r_scale = 25;
1439     low_high_range = 200;
1440     enable_flt_points = false;
1441 }
1442
1443
1444 void CV_ContourMomentsTest::generate_point_set( void* points )
1445 {
1446     CvRNG* rng = ts->get_rng();
1447     float max_sz;
1448
1449     axes.width = (float)((cvTsRandReal(rng)*0.9 + 0.1)*low_high_range);
1450     axes.height = (float)((cvTsRandReal(rng)*0.9 + 0.1)*low_high_range);
1451     max_sz = MAX(axes.width, axes.height);
1452
1453     img_size.width = img_size.height = cvRound(low_high_range*2.2);
1454
1455     center.x = (float)(img_size.width*0.5 + (cvTsRandReal(rng)-0.5)*(img_size.width - max_sz*2)*0.8);
1456     center.y = (float)(img_size.height*0.5 + (cvTsRandReal(rng)-0.5)*(img_size.height - max_sz*2)*0.8);
1457
1458     assert( 0 < center.x - max_sz && center.x + max_sz < img_size.width &&
1459         0 < center.y - max_sz && center.y + max_sz < img_size.height );
1460
1461     max_r_scale = cvTsRandReal(rng)*max_max_r_scale*0.01;
1462     angle = cvTsRandReal(rng)*360;
1463
1464     cvTsGenerateTousledBlob( center, axes, max_r_scale, angle, points, rng );
1465
1466     if( points1 )
1467         points1->flags = CV_SEQ_MAGIC_VAL + CV_SEQ_POLYGON;
1468 }
1469
1470
1471 int CV_ContourMomentsTest::prepare_test_case( int test_case_idx )
1472 {
1473     min_log_size = MAX(min_log_size,3);
1474     max_log_size = MIN(max_log_size,8);
1475     max_log_size = MAX(min_log_size,max_log_size);
1476     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1477     return code;
1478 }
1479
1480
1481 void CV_ContourMomentsTest::run_func()
1482 {
1483     cvMoments( points, &moments );
1484     area = cvContourArea( points );
1485 }
1486
1487
1488 int CV_ContourMomentsTest::validate_test_results( int test_case_idx )
1489 {
1490     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1491     int i, n = (int)(sizeof(moments)/sizeof(moments.inv_sqrt_m00));
1492     CvMat* img = cvCreateMat( img_size.height, img_size.width, CV_8UC1 );
1493     CvPoint* pt = (CvPoint*)points2->data.i;
1494     int count = points2->cols + points2->rows - 1;
1495     double max_v0 = 0;
1496
1497     cvZero(img);
1498     cvFillPoly( img, &pt, &count, 1, cvScalarAll(1));
1499     cvMoments( img, &moments0 );
1500
1501     for( i = 0; i < n; i++ )
1502     {
1503         double t = fabs((&moments0.m00)[i]);
1504         max_v0 = MAX(max_v0, t);
1505     }
1506
1507     for( i = 0; i <= n; i++ )
1508     {
1509         double v = i < n ? (&moments.m00)[i] : area;
1510         double v0 = i < n ? (&moments0.m00)[i] : moments0.m00;
1511
1512         if( cvIsNaN(v) || cvIsInf(v) )
1513         {
1514             ts->printf( CvTS::LOG,
1515                 "The contour %s is invalid (=%g)\n", i < n ? "moment" : "area", v );
1516             code = CvTS::FAIL_INVALID_OUTPUT;
1517             break;
1518         }
1519
1520         if( fabs(v - v0) > 0.1*max_v0 )
1521         {
1522             ts->printf( CvTS::LOG,
1523                 "The computed contour %s is %g, while it should be %g\n",
1524                 i < n ? "moment" : "area", v, v0 );
1525             code = CvTS::FAIL_BAD_ACCURACY;
1526             break;
1527         }
1528     }
1529
1530     if( code < 0 )
1531     {
1532 #if 0
1533         cvCmpS( img, 0, img, CV_CMP_GT );
1534         cvNamedWindow( "test", 1 );
1535         cvShowImage( "test", img );
1536         cvWaitKey();
1537 #endif
1538         ts->set_failed_test_info( code );
1539     }
1540
1541     cvReleaseMat( &img );
1542     return code;
1543 }
1544
1545
1546 CV_ContourMomentsTest contour_moments_test;
1547
1548
1549 /* End of file. */
1550