modules/imgproc/test/test_convhull.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 "test_precomp.hpp"
  43
  44 namespace opencv_test { namespace {
  45
  46 /*static int
  47 cvTsPointConvexPolygon( CvPoint2D32f pt, CvPoint2D32f* v, int n )
  48 {
  49     CvPoint2D32f v0 = v[n-1];
  50     int i, sign = 0;
  51
  52     for( i = 0; i < n; i++ )
  53     {
  54         CvPoint2D32f v1 = v[i];
  55         float dx = pt.x - v0.x, dy = pt.y - v0.y;
  56         float dx1 = v1.x - v0.x, dy1 = v1.y - v0.y;
  57         double t = (double)dx*dy1 - (double)dx1*dy;
  58         if( fabs(t) > DBL_EPSILON )
  59         {
  60             if( t*sign < 0 )
  61                 break;
  62             if( sign == 0 )
  63                 sign = t < 0 ? -1 : 1;
  64         }
  65         else if( fabs(dx) + fabs(dy) < DBL_EPSILON )
  66             return i+1;
  67         v0 = v1;
  68     }
  69
  70     return i < n ? -1 : 0;
  71 }*/
  72
  73 CV_INLINE double
  74 cvTsDist( CvPoint2D32f a, CvPoint2D32f b )
  75 {
  76     double dx = a.x - b.x;
  77     double dy = a.y - b.y;
  78     return sqrt(dx*dx + dy*dy);
  79 }
  80 CV_INLINE double
  81 cvTsDist( const Point2f& a, const Point2f& b )
  82 {
  83     double dx = a.x - b.x;
  84     double dy = a.y - b.y;
  85     return sqrt(dx*dx + dy*dy);
  86 }
  87
  88 CV_INLINE double
  89 cvTsPtLineDist( CvPoint2D32f pt, CvPoint2D32f a, CvPoint2D32f b )
  90 {
  91     double d0 = cvTsDist( pt, a ), d1;
  92     double dd = cvTsDist( a, b );
  93     if( dd < FLT_EPSILON )
  94         return d0;
  95     d1 = cvTsDist( pt, b );
  96     dd = fabs((double)(pt.x - a.x)*(b.y - a.y) - (double)(pt.y - a.y)*(b.x - a.x))/dd;
  97     d0 = MIN( d0, d1 );
  98     return MIN( d0, dd );
  99 }
 100
 101 static double
 102 cvTsPointPolygonTest( CvPoint2D32f pt, const CvPoint2D32f* vv, int n, int* _idx=0, int* _on_edge=0 )
 103 {
 104     int i;
 105     Point2f v = vv[n-1], v0;
 106     double min_dist_num = FLT_MAX, min_dist_denom = 1;
 107     int min_dist_idx = -1, min_on_edge = 0;
 108     int counter = 0;
 109     double result;
 110
 111     for( i = 0; i < n; i++ )
 112     {
 113         double dx, dy, dx1, dy1, dx2, dy2, dist_num, dist_denom = 1;
 114         int on_edge = 0, idx = i;
 115
 116         v0 = v; v = vv[i];
 117         dx = v.x - v0.x; dy = v.y - v0.y;
 118         dx1 = pt.x - v0.x; dy1 = pt.y - v0.y;
 119         dx2 = pt.x - v.x; dy2 = pt.y - v.y;
 120
 121         if( dx2*dx + dy2*dy >= 0 )
 122             dist_num = dx2*dx2 + dy2*dy2;
 123         else if( dx1*dx + dy1*dy <= 0 )
 124         {
 125             dist_num = dx1*dx1 + dy1*dy1;
 126             idx = i - 1;
 127             if( idx < 0 ) idx = n-1;
 128         }
 129         else
 130         {
 131             dist_num = (dy1*dx - dx1*dy);
 132             dist_num *= dist_num;
 133             dist_denom = dx*dx + dy*dy;
 134             on_edge = 1;
 135         }
 136
 137         if( dist_num*min_dist_denom < min_dist_num*dist_denom )
 138         {
 139             min_dist_num = dist_num;
 140             min_dist_denom = dist_denom;
 141             min_dist_idx = idx;
 142             min_on_edge = on_edge;
 143             if( min_dist_num == 0 )
 144                 break;
 145         }
 146
 147         if( (v0.y <= pt.y && v.y <= pt.y) ||
 148             (v0.y > pt.y && v.y > pt.y) ||
 149             (v0.x < pt.x && v.x < pt.x) )
 150             continue;
 151
 152         dist_num = dy1*dx - dx1*dy;
 153         if( dy < 0 )
 154             dist_num = -dist_num;
 155         counter += dist_num > 0;
 156     }
 157
 158     result = sqrt(min_dist_num/min_dist_denom);
 159     if( counter % 2 == 0 )
 160         result = -result;
 161
 162     if( _idx )
 163         *_idx = min_dist_idx;
 164     if( _on_edge )
 165         *_on_edge = min_on_edge;
 166
 167     return result;
 168 }
 169
 170 static cv::Point2f
 171 cvTsMiddlePoint(const cv::Point2f &a, const cv::Point2f &b)
 172 {
 173     return cv::Point2f((a.x + b.x) / 2, (a.y + b.y) / 2);
 174 }
 175
 176 static bool
 177 cvTsIsPointOnLineSegment(const cv::Point2f &x, const cv::Point2f &a, const cv::Point2f &b)
 178 {
 179     double d1 = cvTsDist(cvPoint2D32f(x.x, x.y), cvPoint2D32f(a.x, a.y));
 180     double d2 = cvTsDist(cvPoint2D32f(x.x, x.y), cvPoint2D32f(b.x, b.y));
 181     double d3 = cvTsDist(cvPoint2D32f(a.x, a.y), cvPoint2D32f(b.x, b.y));
 182
 183     return (abs(d1 + d2 - d3) <= (1E-5));
 184 }
 185
 186
 187 /****************************************************************************************\
 188 *                              Base class for shape descriptor tests                     *
 189 \****************************************************************************************/
 190
 191 class CV_BaseShapeDescrTest : public cvtest::BaseTest
 192 {
 193 public:
 194     CV_BaseShapeDescrTest();
 195     virtual ~CV_BaseShapeDescrTest();
 196     void clear();
 197
 198 protected:
 199     int read_params( CvFileStorage* fs );
 200     void run_func(void);
 201     int prepare_test_case( int test_case_idx );
 202     int validate_test_results( int test_case_idx );
 203     virtual void generate_point_set( void* points );
 204     virtual void extract_points();
 205
 206     int min_log_size;
 207     int max_log_size;
 208     int dims;
 209     bool enable_flt_points;
 210
 211     CvMemStorage* storage;
 212     CvSeq* points1;
 213     CvMat* points2;
 214     void* points;
 215     void* result;
 216     double low_high_range;
 217     Scalar low, high;
 218
 219     bool test_cpp;
 220 };
 221
 222
 223 CV_BaseShapeDescrTest::CV_BaseShapeDescrTest()
 224 {
 225     points1 = 0;
 226     points2 = 0;
 227     points = 0;
 228     storage = 0;
 229     test_case_count = 500;
 230     min_log_size = 0;
 231     max_log_size = 10;
 232     low = high = cvScalarAll(0);
 233     low_high_range = 50;
 234     dims = 2;
 235     enable_flt_points = true;
 236
 237     test_cpp = false;
 238 }
 239
 240
 241 CV_BaseShapeDescrTest::~CV_BaseShapeDescrTest()
 242 {
 243     clear();
 244 }
 245
 246
 247 void CV_BaseShapeDescrTest::clear()
 248 {
 249     cvtest::BaseTest::clear();
 250     cvReleaseMemStorage( &storage );
 251     cvReleaseMat( &points2 );
 252     points1 = 0;
 253     points = 0;
 254 }
 255
 256
 257 int CV_BaseShapeDescrTest::read_params( CvFileStorage* fs )
 258 {
 259     int code = cvtest::BaseTest::read_params( fs );
 260     if( code < 0 )
 261         return code;
 262
 263     test_case_count = cvReadInt( find_param( fs, "struct_count" ), test_case_count );
 264     min_log_size = cvReadInt( find_param( fs, "min_log_size" ), min_log_size );
 265     max_log_size = cvReadInt( find_param( fs, "max_log_size" ), max_log_size );
 266
 267     min_log_size = cvtest::clipInt( min_log_size, 0, 8 );
 268     max_log_size = cvtest::clipInt( max_log_size, 0, 10 );
 269     if( min_log_size > max_log_size )
 270     {
 271         int t;
 272         CV_SWAP( min_log_size, max_log_size, t );
 273     }
 274
 275     return 0;
 276 }
 277
 278
 279 void CV_BaseShapeDescrTest::generate_point_set( void* pointsSet )
 280 {
 281     RNG& rng = ts->get_rng();
 282     int i, k, n, total, point_type;
 283     CvSeqReader reader;
 284     uchar* data = 0;
 285     double a[4], b[4];
 286
 287     for( k = 0; k < 4; k++ )
 288     {
 289         a[k] = high.val[k] - low.val[k];
 290         b[k] = low.val[k];
 291     }
 292     memset( &reader, 0, sizeof(reader) );
 293
 294     if( CV_IS_SEQ(pointsSet) )
 295     {
 296         CvSeq* ptseq = (CvSeq*)pointsSet;
 297         total = ptseq->total;
 298         point_type = CV_SEQ_ELTYPE(ptseq);
 299         cvStartReadSeq( ptseq, &reader );
 300     }
 301     else
 302     {
 303         CvMat* ptm = (CvMat*)pointsSet;
 304         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
 305         total = ptm->rows + ptm->cols - 1;
 306         point_type = CV_MAT_TYPE(ptm->type);
 307         data = ptm->data.ptr;
 308     }
 309
 310     n = CV_MAT_CN(point_type);
 311     point_type = CV_MAT_DEPTH(point_type);
 312
 313     assert( (point_type == CV_32S || point_type == CV_32F) && n <= 4 );
 314
 315     for( i = 0; i < total; i++ )
 316     {
 317         int* pi;
 318         float* pf;
 319         if( reader.ptr )
 320         {
 321             pi = (int*)reader.ptr;
 322             pf = (float*)reader.ptr;
 323             CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
 324         }
 325         else
 326         {
 327             pi = (int*)data + i*n;
 328             pf = (float*)data + i*n;
 329         }
 330         if( point_type == CV_32S )
 331             for( k = 0; k < n; k++ )
 332                 pi[k] = cvRound(cvtest::randReal(rng)*a[k] + b[k]);
 333         else
 334             for( k = 0; k < n; k++ )
 335                 pf[k] = (float)(cvtest::randReal(rng)*a[k] + b[k]);
 336     }
 337 }
 338
 339
 340 int CV_BaseShapeDescrTest::prepare_test_case( int test_case_idx )
 341 {
 342     int size;
 343     int use_storage = 0;
 344     int point_type;
 345     int i;
 346     RNG& rng = ts->get_rng();
 347
 348     cvtest::BaseTest::prepare_test_case( test_case_idx );
 349
 350     clear();
 351     size = cvRound( exp((cvtest::randReal(rng) * (max_log_size - min_log_size) + min_log_size)*CV_LOG2) );
 352     use_storage = cvtest::randInt(rng) % 2;
 353     point_type = CV_MAKETYPE(cvtest::randInt(rng) %
 354         (enable_flt_points ? 2 : 1) ? CV_32F : CV_32S, dims);
 355
 356     if( use_storage )
 357     {
 358         storage = cvCreateMemStorage( (cvtest::randInt(rng)%10 + 1)*1024 );
 359         points1 = cvCreateSeq( point_type, sizeof(CvSeq), CV_ELEM_SIZE(point_type), storage );
 360         cvSeqPushMulti( points1, 0, size );
 361         points = points1;
 362     }
 363     else
 364     {
 365         int rows = 1, cols = size;
 366         if( cvtest::randInt(rng) % 2 )
 367             rows = size, cols = 1;
 368
 369         points2 = cvCreateMat( rows, cols, point_type );
 370         points = points2;
 371     }
 372
 373     for( i = 0; i < 4; i++ )
 374     {
 375         low.val[i] = (cvtest::randReal(rng)-0.5)*low_high_range*2;
 376         high.val[i] = (cvtest::randReal(rng)-0.5)*low_high_range*2;
 377         if( low.val[i] > high.val[i] )
 378         {
 379             double t;
 380             CV_SWAP( low.val[i], high.val[i], t );
 381         }
 382         if( high.val[i] < low.val[i] + 1 )
 383             high.val[i] += 1;
 384     }
 385
 386     generate_point_set( points );
 387
 388     test_cpp = (cvtest::randInt(rng) & 16) == 0;
 389     return 1;
 390 }
 391
 392
 393 void CV_BaseShapeDescrTest::extract_points()
 394 {
 395     if( points1 )
 396     {
 397         points2 = cvCreateMat( 1, points1->total, CV_SEQ_ELTYPE(points1) );
 398         cvCvtSeqToArray( points1, points2->data.ptr );
 399     }
 400
 401     if( CV_MAT_DEPTH(points2->type) != CV_32F && enable_flt_points )
 402     {
 403         CvMat tmp = cvMat( points2->rows, points2->cols,
 404             (points2->type & ~CV_MAT_DEPTH_MASK) | CV_32F, points2->data.ptr );
 405         cvConvert( points2, &tmp );
 406     }
 407 }
 408
 409
 410 void CV_BaseShapeDescrTest::run_func(void)
 411 {
 412 }
 413
 414
 415 int CV_BaseShapeDescrTest::validate_test_results( int /*test_case_idx*/ )
 416 {
 417     extract_points();
 418     return 0;
 419 }
 420
 421
 422 /****************************************************************************************\
 423 *                                     Convex Hull Test                                   *
 424 \****************************************************************************************/
 425
 426 class CV_ConvHullTest : public CV_BaseShapeDescrTest
 427 {
 428 public:
 429     CV_ConvHullTest();
 430     virtual ~CV_ConvHullTest();
 431     void clear();
 432
 433 protected:
 434     void run_func(void);
 435     int prepare_test_case( int test_case_idx );
 436     int validate_test_results( int test_case_idx );
 437
 438     CvSeq* hull1;
 439     CvMat* hull2;
 440     void* hull_storage;
 441     int orientation;
 442     int return_points;
 443 };
 444
 445
 446 CV_ConvHullTest::CV_ConvHullTest()
 447 {
 448     hull1 = 0;
 449     hull2 = 0;
 450     hull_storage = 0;
 451     orientation = return_points = 0;
 452 }
 453
 454
 455 CV_ConvHullTest::~CV_ConvHullTest()
 456 {
 457     clear();
 458 }
 459
 460
 461 void CV_ConvHullTest::clear()
 462 {
 463     CV_BaseShapeDescrTest::clear();
 464     cvReleaseMat( &hull2 );
 465     hull1 = 0;
 466     hull_storage = 0;
 467 }
 468
 469
 470 int CV_ConvHullTest::prepare_test_case( int test_case_idx )
 471 {
 472     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
 473     int use_storage_for_hull = 0;
 474     RNG& rng = ts->get_rng();
 475
 476     if( code <= 0 )
 477         return code;
 478
 479     orientation = cvtest::randInt(rng) % 2 ? CV_CLOCKWISE : CV_COUNTER_CLOCKWISE;
 480     return_points = cvtest::randInt(rng) % 2;
 481
 482     use_storage_for_hull = (cvtest::randInt(rng) % 2) && !test_cpp;
 483     if( use_storage_for_hull )
 484     {
 485         if( !storage )
 486             storage = cvCreateMemStorage( (cvtest::randInt(rng)%10 + 1)*1024 );
 487         hull_storage = storage;
 488     }
 489     else
 490     {
 491         int rows, cols;
 492         int sz = points1 ? points1->total : points2->cols + points2->rows - 1;
 493         int point_type = points1 ? CV_SEQ_ELTYPE(points1) : CV_MAT_TYPE(points2->type);
 494
 495         if( cvtest::randInt(rng) % 2 )
 496             rows = sz, cols = 1;
 497         else
 498             rows = 1, cols = sz;
 499
 500         hull2 = cvCreateMat( rows, cols, return_points ? point_type : CV_32SC1 );
 501         hull_storage = hull2;
 502     }
 503
 504     return code;
 505 }
 506
 507
 508 void CV_ConvHullTest::run_func()
 509 {
 510     if(!test_cpp)
 511         hull1 = cvConvexHull2( points, hull_storage, orientation, return_points );
 512     else
 513     {
 514         cv::Mat _points = cv::cvarrToMat(points);
 515         bool clockwise = orientation == CV_CLOCKWISE;
 516         size_t n = 0;
 517         if( !return_points )
 518         {
 519             std::vector<int> _hull;
 520             cv::convexHull(_points, _hull, clockwise);
 521             n = _hull.size();
 522             memcpy(hull2->data.ptr, &_hull[0], n*sizeof(_hull[0]));
 523         }
 524         else if(_points.type() == CV_32SC2)
 525         {
 526             std::vector<cv::Point> _hull;
 527             cv::convexHull(_points, _hull, clockwise);
 528             n = _hull.size();
 529             memcpy(hull2->data.ptr, &_hull[0], n*sizeof(_hull[0]));
 530         }
 531         else if(_points.type() == CV_32FC2)
 532         {
 533             std::vector<cv::Point2f> _hull;
 534             cv::convexHull(_points, _hull, clockwise);
 535             n = _hull.size();
 536             memcpy(hull2->data.ptr, &_hull[0], n*sizeof(_hull[0]));
 537         }
 538         if(hull2->rows > hull2->cols)
 539             hull2->rows = (int)n;
 540         else
 541             hull2->cols = (int)n;
 542     }
 543 }
 544
 545
 546 int CV_ConvHullTest::validate_test_results( int test_case_idx )
 547 {
 548     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 549     CvMat* hull = 0;
 550     CvMat* mask = 0;
 551     int i, point_count, hull_count;
 552     CvPoint2D32f *p, *h;
 553     CvSeq header, hheader, *ptseq, *hseq;
 554     CvSeqBlock block, hblock;
 555
 556     if( points1 )
 557         ptseq = points1;
 558     else
 559         ptseq = cvMakeSeqHeaderForArray( CV_MAT_TYPE(points2->type),
 560             sizeof(CvSeq), CV_ELEM_SIZE(points2->type), points2->data.ptr,
 561             points2->rows + points2->cols - 1, &header, &block );
 562     point_count = ptseq->total;
 563     p = (CvPoint2D32f*)(points2->data.ptr);
 564
 565     if( hull1 )
 566         hseq = hull1;
 567     else
 568         hseq = cvMakeSeqHeaderForArray( CV_MAT_TYPE(hull2->type),
 569             sizeof(CvSeq), CV_ELEM_SIZE(hull2->type), hull2->data.ptr,
 570             hull2->rows + hull2->cols - 1, &hheader, &hblock );
 571     hull_count = hseq->total;
 572     hull = cvCreateMat( 1, hull_count, CV_32FC2 );
 573     mask = cvCreateMat( 1, hull_count, CV_8UC1 );
 574     cvZero( mask );
 575     Mat _mask = cvarrToMat(mask);
 576
 577     h = (CvPoint2D32f*)(hull->data.ptr);
 578
 579     // extract convex hull points
 580     if( return_points )
 581     {
 582         cvCvtSeqToArray( hseq, hull->data.ptr );
 583         if( CV_SEQ_ELTYPE(hseq) != CV_32FC2 )
 584         {
 585             CvMat tmp = cvMat( hull->rows, hull->cols, CV_32SC2, hull->data.ptr );
 586             cvConvert( &tmp, hull );
 587         }
 588     }
 589     else
 590     {
 591         CvSeqReader reader;
 592         cvStartReadSeq( hseq, &reader );
 593
 594         for( i = 0; i < hull_count; i++ )
 595         {
 596             schar* ptr = reader.ptr;
 597             int idx;
 598             CV_NEXT_SEQ_ELEM( hseq->elem_size, reader );
 599
 600             if( hull1 )
 601                 idx = cvSeqElemIdx( ptseq, *(uchar**)ptr );
 602             else
 603                 idx = *(int*)ptr;
 604
 605             if( idx < 0 || idx >= point_count )
 606             {
 607                 ts->printf( cvtest::TS::LOG, "Invalid convex hull point #%d\n", i );
 608                 code = cvtest::TS::FAIL_INVALID_OUTPUT;
 609                 goto _exit_;
 610             }
 611             h[i] = p[idx];
 612         }
 613     }
 614
 615     // check that the convex hull is a convex polygon
 616     if( hull_count >= 3 )
 617     {
 618         CvPoint2D32f pt0 = h[hull_count-1];
 619         for( i = 0; i < hull_count; i++ )
 620         {
 621             int j = i+1;
 622             CvPoint2D32f pt1 = h[i], pt2 = h[j < hull_count ? j : 0];
 623             float dx0 = pt1.x - pt0.x, dy0 = pt1.y - pt0.y;
 624             float dx1 = pt2.x - pt1.x, dy1 = pt2.y - pt1.y;
 625             double t = (double)dx0*dy1 - (double)dx1*dy0;
 626             if( (t < 0) ^ (orientation != CV_COUNTER_CLOCKWISE) )
 627             {
 628                 ts->printf( cvtest::TS::LOG, "The convex hull is not convex or has a wrong orientation (vtx %d)\n", i );
 629                 code = cvtest::TS::FAIL_INVALID_OUTPUT;
 630                 goto _exit_;
 631             }
 632             pt0 = pt1;
 633         }
 634     }
 635
 636     // check that all the points are inside the hull or on the hull edge
 637     // and at least hull_point points are at the hull vertices
 638     for( i = 0; i < point_count; i++ )
 639     {
 640         int idx = 0, on_edge = 0;
 641         double pptresult = cvTsPointPolygonTest( p[i], h, hull_count, &idx, &on_edge );
 642
 643         if( pptresult < 0 )
 644         {
 645             ts->printf( cvtest::TS::LOG, "The point #%d is outside of the convex hull\n", i );
 646             code = cvtest::TS::FAIL_BAD_ACCURACY;
 647             goto _exit_;
 648         }
 649
 650         if( pptresult < FLT_EPSILON && !on_edge )
 651             mask->data.ptr[idx] = (uchar)1;
 652     }
 653
 654     if( cvtest::norm( _mask, Mat::zeros(_mask.dims, _mask.size, _mask.type()), NORM_L1 ) != hull_count )
 655     {
 656         ts->printf( cvtest::TS::LOG, "Not every convex hull vertex coincides with some input point\n" );
 657         code = cvtest::TS::FAIL_BAD_ACCURACY;
 658         goto _exit_;
 659     }
 660
 661 _exit_:
 662
 663     cvReleaseMat( &hull );
 664     cvReleaseMat( &mask );
 665     if( code < 0 )
 666         ts->set_failed_test_info( code );
 667     return code;
 668 }
 669
 670
 671 /****************************************************************************************\
 672 *                                     MinAreaRect Test                                   *
 673 \****************************************************************************************/
 674
 675 class CV_MinAreaRectTest : public CV_BaseShapeDescrTest
 676 {
 677 public:
 678     CV_MinAreaRectTest();
 679
 680 protected:
 681     void run_func(void);
 682     int validate_test_results( int test_case_idx );
 683
 684     CvBox2D box;
 685     CvPoint2D32f box_pt[4];
 686 };
 687
 688
 689 CV_MinAreaRectTest::CV_MinAreaRectTest()
 690 {
 691 }
 692
 693
 694 void CV_MinAreaRectTest::run_func()
 695 {
 696     if(!test_cpp)
 697     {
 698         box = cvMinAreaRect2( points, storage );
 699         cvBoxPoints( box, box_pt );
 700     }
 701     else
 702     {
 703         cv::RotatedRect r = cv::minAreaRect(cv::cvarrToMat(points));
 704         box = cvBox2D(r);
 705         r.points((cv::Point2f*)box_pt);
 706     }
 707 }
 708
 709
 710 int CV_MinAreaRectTest::validate_test_results( int test_case_idx )
 711 {
 712     double eps = 1e-1;
 713     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 714     int i, j, point_count = points2->rows + points2->cols - 1;
 715     CvPoint2D32f *p = (CvPoint2D32f*)(points2->data.ptr);
 716     int mask[] = {0,0,0,0};
 717
 718     // check that the bounding box is a rotated rectangle:
 719     //  1. diagonals should be equal
 720     //  2. they must intersect in their middle points
 721     {
 722         double d0 = cvTsDist( box_pt[0], box_pt[2] );
 723         double d1 = cvTsDist( box_pt[1], box_pt[3] );
 724
 725         double x0 = (box_pt[0].x + box_pt[2].x)*0.5;
 726         double y0 = (box_pt[0].y + box_pt[2].y)*0.5;
 727         double x1 = (box_pt[1].x + box_pt[3].x)*0.5;
 728         double y1 = (box_pt[1].y + box_pt[3].y)*0.5;
 729
 730         if( fabs(d0 - d1) + fabs(x0 - x1) + fabs(y0 - y1) > eps*MAX(d0,d1) )
 731         {
 732             ts->printf( cvtest::TS::LOG, "The bounding box is not a rectangle\n" );
 733             code = cvtest::TS::FAIL_INVALID_OUTPUT;
 734             goto _exit_;
 735         }
 736     }
 737
 738 #if 0
 739     {
 740     int n = 4;
 741     double a = 8, c = 8, b = 100, d = 150;
 742     CvPoint bp[4], *bpp = bp;
 743     cvNamedWindow( "test", 1 );
 744     IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
 745     cvZero(img);
 746     for( i = 0; i < point_count; i++ )
 747         cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*c+d)), 3, CV_RGB(0,255,0), -1 );
 748     for( i = 0; i < n; i++ )
 749         bp[i] = cvPoint(cvRound(box_pt[i].x*a+b),cvRound(box_pt[i].y*c+d));
 750     cvPolyLine( img, &bpp, &n, 1, 1, CV_RGB(255,255,0), 1, CV_AA, 0 );
 751     cvShowImage( "test", img );
 752     cvWaitKey();
 753     cvReleaseImage(&img);
 754     }
 755 #endif
 756
 757     // check that the box includes all the points
 758     // and there is at least one point at (or very close to) every box side
 759     for( i = 0; i < point_count; i++ )
 760     {
 761         int idx = 0, on_edge = 0;
 762         double pptresult = cvTsPointPolygonTest( p[i], box_pt, 4, &idx, &on_edge );
 763         if( pptresult < -eps )
 764         {
 765             ts->printf( cvtest::TS::LOG, "The point #%d is outside of the box\n", i );
 766             code = cvtest::TS::FAIL_BAD_ACCURACY;
 767             goto _exit_;
 768         }
 769
 770         if( pptresult < eps )
 771         {
 772             for( j = 0; j < 4; j++ )
 773             {
 774                 double d = cvTsPtLineDist( p[i], box_pt[(j-1)&3], box_pt[j] );
 775                 if( d < eps )
 776                     mask[j] = (uchar)1;
 777             }
 778         }
 779     }
 780
 781     if( mask[0] + mask[1] + mask[2] + mask[3] != 4 )
 782     {
 783         ts->printf( cvtest::TS::LOG, "Not every box side has a point nearby\n" );
 784         code = cvtest::TS::FAIL_BAD_ACCURACY;
 785         goto _exit_;
 786     }
 787
 788 _exit_:
 789
 790     if( code < 0 )
 791         ts->set_failed_test_info( code );
 792     return code;
 793 }
 794
 795
 796 /****************************************************************************************\
 797 *                                   MinEnclosingTriangle Test                            *
 798 \****************************************************************************************/
 799
 800 class CV_MinTriangleTest : public CV_BaseShapeDescrTest
 801 {
 802 public:
 803     CV_MinTriangleTest();
 804
 805 protected:
 806     void run_func(void);
 807     int validate_test_results( int test_case_idx );
 808     std::vector<cv::Point2f> getTriangleMiddlePoints();
 809
 810     std::vector<cv::Point2f> convexPolygon;
 811     std::vector<cv::Point2f> triangle;
 812 };
 813
 814
 815 CV_MinTriangleTest::CV_MinTriangleTest()
 816 {
 817 }
 818
 819 std::vector<cv::Point2f> CV_MinTriangleTest::getTriangleMiddlePoints()
 820 {
 821     std::vector<cv::Point2f> triangleMiddlePoints;
 822
 823     for (int i = 0; i < 3; i++) {
 824         triangleMiddlePoints.push_back(cvTsMiddlePoint(triangle[i], triangle[(i + 1) % 3]));
 825     }
 826
 827     return triangleMiddlePoints;
 828 }
 829
 830
 831 void CV_MinTriangleTest::run_func()
 832 {
 833     std::vector<cv::Point2f> pointsAsVector;
 834
 835     cv::cvarrToMat(points).convertTo(pointsAsVector, CV_32F);
 836
 837     cv::minEnclosingTriangle(pointsAsVector, triangle);
 838     cv::convexHull(pointsAsVector, convexPolygon, true, true);
 839 }
 840
 841
 842 int CV_MinTriangleTest::validate_test_results( int test_case_idx )
 843 {
 844     bool errorEnclosed = false, errorMiddlePoints = false, errorFlush = true;
 845     double eps = 1e-4;
 846     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 847
 848 #if 0
 849     {
 850     int n = 3;
 851     double a = 8, c = 8, b = 100, d = 150;
 852     CvPoint bp[4], *bpp = bp;
 853     cvNamedWindow( "test", 1 );
 854     IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
 855     cvZero(img);
 856     for( i = 0; i < point_count; i++ )
 857         cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*c+d)), 3, CV_RGB(0,255,0), -1 );
 858     for( i = 0; i < n; i++ )
 859         bp[i] = cvPoint(cvRound(triangle[i].x*a+b),cvRound(triangle[i].y*c+d));
 860     cvPolyLine( img, &bpp, &n, 1, 1, CV_RGB(255,255,0), 1, CV_AA, 0 );
 861     cvShowImage( "test", img );
 862     cvWaitKey();
 863     cvReleaseImage(&img);
 864     }
 865 #endif
 866
 867     int polygonVertices = (int) convexPolygon.size();
 868
 869     if (polygonVertices > 2) {
 870         // Check if all points are enclosed by the triangle
 871         for (int i = 0; (i < polygonVertices) && (!errorEnclosed); i++)
 872         {
 873             if (cv::pointPolygonTest(triangle, cv::Point2f(convexPolygon[i].x, convexPolygon[i].y), true) < (-eps))
 874                 errorEnclosed = true;
 875         }
 876
 877         // Check if triangle edges middle points touch the polygon
 878         std::vector<cv::Point2f> middlePoints = getTriangleMiddlePoints();
 879
 880         for (int i = 0; (i < 3) && (!errorMiddlePoints); i++)
 881         {
 882             bool isTouching = false;
 883
 884             for (int j = 0; (j < polygonVertices) && (!isTouching); j++)
 885             {
 886                 if (cvTsIsPointOnLineSegment(middlePoints[i], convexPolygon[j],
 887                                              convexPolygon[(j + 1) % polygonVertices]))
 888                     isTouching = true;
 889             }
 890
 891             errorMiddlePoints = (isTouching) ? false : true;
 892         }
 893
 894         // Check if at least one of the edges is flush
 895         for (int i = 0; (i < 3) && (errorFlush); i++)
 896         {
 897             for (int j = 0; (j < polygonVertices) && (errorFlush); j++)
 898             {
 899                 if ((cvTsIsPointOnLineSegment(convexPolygon[j], triangle[i],
 900                                               triangle[(i + 1) % 3])) &&
 901                     (cvTsIsPointOnLineSegment(convexPolygon[(j + 1) % polygonVertices], triangle[i],
 902                                               triangle[(i + 1) % 3])))
 903                     errorFlush = false;
 904             }
 905         }
 906
 907         // Report any found errors
 908         if (errorEnclosed)
 909         {
 910             ts->printf( cvtest::TS::LOG,
 911             "All points should be enclosed by the triangle.\n" );
 912             code = cvtest::TS::FAIL_BAD_ACCURACY;
 913         }
 914         else if (errorMiddlePoints)
 915         {
 916             ts->printf( cvtest::TS::LOG,
 917             "All triangle edges middle points should touch the convex hull of the points.\n" );
 918             code = cvtest::TS::FAIL_INVALID_OUTPUT;
 919         }
 920         else if (errorFlush)
 921         {
 922             ts->printf( cvtest::TS::LOG,
 923             "At least one edge of the enclosing triangle should be flush with one edge of the polygon.\n" );
 924             code = cvtest::TS::FAIL_INVALID_OUTPUT;
 925         }
 926     }
 927
 928     if ( code < 0 )
 929         ts->set_failed_test_info( code );
 930
 931     return code;
 932 }
 933
 934
 935 /****************************************************************************************\
 936 *                                     MinEnclosingCircle Test                            *
 937 \****************************************************************************************/
 938
 939 class CV_MinCircleTest : public CV_BaseShapeDescrTest
 940 {
 941 public:
 942     CV_MinCircleTest();
 943
 944 protected:
 945     void run_func(void);
 946     int validate_test_results( int test_case_idx );
 947
 948     Point2f center;
 949     float radius;
 950 };
 951
 952
 953 CV_MinCircleTest::CV_MinCircleTest()
 954 {
 955 }
 956
 957
 958 void CV_MinCircleTest::run_func()
 959 {
 960     if(!test_cpp)
 961     {
 962         CvPoint2D32f c_center = cvPoint2D32f(center);
 963         cvMinEnclosingCircle( points, &c_center, &radius );
 964         center = c_center;
 965     }
 966     else
 967     {
 968         cv::Point2f tmpcenter;
 969         cv::minEnclosingCircle(cv::cvarrToMat(points), tmpcenter, radius);
 970         center = tmpcenter;
 971     }
 972 }
 973
 974
 975 int CV_MinCircleTest::validate_test_results( int test_case_idx )
 976 {
 977     double eps = 1.03;
 978     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
 979     int i, j = 0, point_count = points2->rows + points2->cols - 1;
 980     Point2f *p = (Point2f*)(points2->data.ptr);
 981     Point2f v[3];
 982
 983 #if 0
 984     {
 985     double a = 2, b = 200, d = 400;
 986     cvNamedWindow( "test", 1 );
 987     IplImage* img = cvCreateImage( cvSize(500,500), 8, 3 );
 988     cvZero(img);
 989     for( i = 0; i < point_count; i++ )
 990         cvCircle(img,cvPoint(cvRound(p[i].x*a+b),cvRound(p[i].y*a+d)), 3, CV_RGB(0,255,0), -1 );
 991     cvCircle( img, cvPoint(cvRound(center.x*a+b),cvRound(center.y*a+d)),
 992               cvRound(radius*a), CV_RGB(255,255,0), 1 );
 993     cvShowImage( "test", img );
 994     cvWaitKey();
 995     cvReleaseImage(&img);
 996     }
 997 #endif
 998
 999     // check that the circle contains all the points inside and
1000     // remember at most 3 points that are close to the boundary
1001     for( i = 0; i < point_count; i++ )
1002     {
1003         double d = cvTsDist(p[i], center);
1004         if( d > radius )
1005         {
1006             ts->printf( cvtest::TS::LOG, "The point #%d is outside of the circle\n", i );
1007             code = cvtest::TS::FAIL_BAD_ACCURACY;
1008             goto _exit_;
1009         }
1010
1011         if( radius - d < eps*radius && j < 3 )
1012             v[j++] = p[i];
1013     }
1014
1015     if( point_count >= 2 && (j < 2 || (j == 2 && cvTsDist(v[0],v[1]) < (radius-1)*2/eps)) )
1016     {
1017         ts->printf( cvtest::TS::LOG,
1018             "There should be at at least 3 points near the circle boundary or 2 points on the diameter\n" );
1019         code = cvtest::TS::FAIL_BAD_ACCURACY;
1020         goto _exit_;
1021     }
1022
1023 _exit_:
1024
1025     if( code < 0 )
1026         ts->set_failed_test_info( code );
1027     return code;
1028 }
1029
1030 /****************************************************************************************\
1031 *                                 MinEnclosingCircle Test 2                              *
1032 \****************************************************************************************/
1033
1034 class CV_MinCircleTest2 : public CV_BaseShapeDescrTest
1035 {
1036 public:
1037     CV_MinCircleTest2();
1038 protected:
1039     RNG rng;
1040     void run_func(void);
1041     int validate_test_results( int test_case_idx );
1042     float delta;
1043 };
1044
1045
1046 CV_MinCircleTest2::CV_MinCircleTest2()
1047 {
1048     rng = ts->get_rng();
1049 }
1050
1051
1052 void CV_MinCircleTest2::run_func()
1053 {
1054     Point2f center = Point2f(rng.uniform(0.0f, 1000.0f), rng.uniform(0.0f, 1000.0f));;
1055     float radius = rng.uniform(0.0f, 500.0f);
1056     float angle = (float)rng.uniform(0.0f, (float)(CV_2PI));
1057     vector<Point2f> pts;
1058     pts.push_back(center + Point2f(radius * cos(angle), radius * sin(angle)));
1059     angle += (float)CV_PI;
1060     pts.push_back(center + Point2f(radius * cos(angle), radius * sin(angle)));
1061     float radius2 = radius * radius;
1062     float x = rng.uniform(center.x - radius, center.x + radius);
1063     float deltaX = x - center.x;
1064     float upperBoundY = sqrt(radius2 - deltaX * deltaX);
1065     float y = rng.uniform(center.y - upperBoundY, center.y + upperBoundY);
1066     pts.push_back(Point2f(x, y));
1067     // Find the minimum area enclosing circle
1068     Point2f calcCenter;
1069     float calcRadius;
1070     minEnclosingCircle(pts, calcCenter, calcRadius);
1071     delta = (float)cv::norm(calcCenter - center) + abs(calcRadius - radius);
1072 }
1073
1074 int CV_MinCircleTest2::validate_test_results( int test_case_idx )
1075 {
1076     float eps = 1.0F;
1077     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1078     if (delta > eps)
1079     {
1080         ts->printf( cvtest::TS::LOG, "Delta center and calcCenter > %f\n", eps );
1081         code = cvtest::TS::FAIL_BAD_ACCURACY;
1082         ts->set_failed_test_info( code );
1083     }
1084     return code;
1085 }
1086
1087 /****************************************************************************************\
1088 *                                 minEnclosingCircle Test 3                              *
1089 \****************************************************************************************/
1090
1091 TEST(Imgproc_minEnclosingCircle, basic_test)
1092 {
1093     vector<Point2f> pts;
1094     pts.push_back(Point2f(0, 0));
1095     pts.push_back(Point2f(10, 0));
1096     pts.push_back(Point2f(5, 1));
1097     const float EPS = 1.0e-3f;
1098     Point2f center;
1099     float radius;
1100
1101     // pts[2] is within the circle with diameter pts[0] - pts[1].
1102     //        2
1103     // 0             1
1104     // NB: The triangle is obtuse, so the only pts[0] and pts[1] are on the circle.
1105     minEnclosingCircle(pts, center, radius);
1106     EXPECT_NEAR(center.x, 5, EPS);
1107     EXPECT_NEAR(center.y, 0, EPS);
1108     EXPECT_NEAR(5, radius, EPS);
1109
1110     // pts[2] is on the circle with diameter pts[0] - pts[1].
1111     //  2
1112     // 0 1
1113     pts[2] = Point2f(5, 5);
1114     minEnclosingCircle(pts, center, radius);
1115     EXPECT_NEAR(center.x, 5, EPS);
1116     EXPECT_NEAR(center.y, 0, EPS);
1117     EXPECT_NEAR(5, radius, EPS);
1118
1119     // pts[2] is outside the circle with diameter pts[0] - pts[1].
1120     //   2
1121     //
1122     //
1123     // 0   1
1124     // NB: The triangle is acute, so all 3 points are on the circle.
1125     pts[2] = Point2f(5, 10);
1126     minEnclosingCircle(pts, center, radius);
1127     EXPECT_NEAR(center.x, 5, EPS);
1128     EXPECT_NEAR(center.y, 3.75, EPS);
1129     EXPECT_NEAR(6.25f, radius, EPS);
1130
1131     // The 3 points are colinear.
1132     pts[2] = Point2f(3, 0);
1133     minEnclosingCircle(pts, center, radius);
1134     EXPECT_NEAR(center.x, 5, EPS);
1135     EXPECT_NEAR(center.y, 0, EPS);
1136     EXPECT_NEAR(5, radius, EPS);
1137
1138     // 2 points are the same.
1139     pts[2] = pts[1];
1140     minEnclosingCircle(pts, center, radius);
1141     EXPECT_NEAR(center.x, 5, EPS);
1142     EXPECT_NEAR(center.y, 0, EPS);
1143     EXPECT_NEAR(5, radius, EPS);
1144
1145     // 3 points are the same.
1146     pts[0] = pts[1];
1147     minEnclosingCircle(pts, center, radius);
1148     EXPECT_NEAR(center.x, 10, EPS);
1149     EXPECT_NEAR(center.y, 0, EPS);
1150     EXPECT_NEAR(0, radius, EPS);
1151 }
1152
1153 TEST(Imgproc_minEnclosingCircle, regression_16051) {
1154     vector<Point2f> pts;
1155     pts.push_back(Point2f(85, 1415));
1156     pts.push_back(Point2f(87, 1415));
1157     pts.push_back(Point2f(89, 1414));
1158     pts.push_back(Point2f(89, 1414));
1159     pts.push_back(Point2f(87, 1412));
1160     Point2f center;
1161     float radius;
1162     minEnclosingCircle(pts, center, radius);
1163     EXPECT_NEAR(center.x, 86.9f, 1e-3);
1164     EXPECT_NEAR(center.y, 1414.1f, 1e-3);
1165     EXPECT_NEAR(2.1024551f, radius, 1e-3);
1166 }
1167
1168 /****************************************************************************************\
1169 *                                   Perimeter Test                                     *
1170 \****************************************************************************************/
1171
1172 class CV_PerimeterTest : public CV_BaseShapeDescrTest
1173 {
1174 public:
1175     CV_PerimeterTest();
1176
1177 protected:
1178     int prepare_test_case( int test_case_idx );
1179     void run_func(void);
1180     int validate_test_results( int test_case_idx );
1181     CvSlice slice;
1182     int is_closed;
1183     double result;
1184 };
1185
1186
1187 CV_PerimeterTest::CV_PerimeterTest()
1188 {
1189 }
1190
1191
1192 int CV_PerimeterTest::prepare_test_case( int test_case_idx )
1193 {
1194     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1195     RNG& rng = ts->get_rng();
1196     int total;
1197
1198     if( code < 0 )
1199         return code;
1200
1201     is_closed = cvtest::randInt(rng) % 2;
1202
1203     if( points1 )
1204     {
1205         points1->flags |= CV_SEQ_KIND_CURVE;
1206         if( is_closed )
1207             points1->flags |= CV_SEQ_FLAG_CLOSED;
1208         total = points1->total;
1209     }
1210     else
1211         total = points2->cols + points2->rows - 1;
1212
1213     if( (cvtest::randInt(rng) % 3) && !test_cpp )
1214     {
1215         slice.start_index = cvtest::randInt(rng) % total;
1216         slice.end_index = cvtest::randInt(rng) % total;
1217     }
1218     else
1219         slice = CV_WHOLE_SEQ;
1220
1221     return 1;
1222 }
1223
1224
1225 void CV_PerimeterTest::run_func()
1226 {
1227     if(!test_cpp)
1228         result = cvArcLength( points, slice, points1 ? -1 : is_closed );
1229     else
1230         result = cv::arcLength(cv::cvarrToMat(points),
1231             !points1 ? is_closed != 0 : (points1->flags & CV_SEQ_FLAG_CLOSED) != 0);
1232 }
1233
1234
1235 int CV_PerimeterTest::validate_test_results( int test_case_idx )
1236 {
1237     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1238     int i, len = slice.end_index - slice.start_index, total = points2->cols + points2->rows - 1;
1239     double result0 = 0;
1240     Point2f prev_pt, pt;
1241     CvPoint2D32f *ptr;
1242
1243     if( len < 0 )
1244         len += total;
1245
1246     len = MIN( len, total );
1247     //len -= !is_closed && len == total;
1248
1249     ptr = (CvPoint2D32f*)points2->data.fl;
1250     prev_pt = ptr[(is_closed ? slice.start_index+len-1 : slice.start_index) % total];
1251
1252     for( i = 0; i < len + (len < total && (!is_closed || len==1)); i++ )
1253     {
1254         pt = ptr[(i + slice.start_index) % total];
1255         double dx = pt.x - prev_pt.x, dy = pt.y - prev_pt.y;
1256         result0 += sqrt(dx*dx + dy*dy);
1257         prev_pt = pt;
1258     }
1259
1260     if( cvIsNaN(result) || cvIsInf(result) )
1261     {
1262         ts->printf( cvtest::TS::LOG, "cvArcLength() returned invalid value (%g)\n", result );
1263         code = cvtest::TS::FAIL_INVALID_OUTPUT;
1264     }
1265     else if( fabs(result - result0) > FLT_EPSILON*100*result0 )
1266     {
1267         ts->printf( cvtest::TS::LOG, "The function returned %g, while the correct result is %g\n", result, result0 );
1268         code = cvtest::TS::FAIL_BAD_ACCURACY;
1269     }
1270
1271     if( code < 0 )
1272         ts->set_failed_test_info( code );
1273     return code;
1274 }
1275
1276
1277 /****************************************************************************************\
1278 *                                   FitEllipse Test                                      *
1279 \****************************************************************************************/
1280
1281 class CV_FitEllipseTest : public CV_BaseShapeDescrTest
1282 {
1283 public:
1284     CV_FitEllipseTest();
1285
1286 protected:
1287     int prepare_test_case( int test_case_idx );
1288     void generate_point_set( void* points );
1289     void run_func(void);
1290     int validate_test_results( int test_case_idx );
1291     RotatedRect box0, box;
1292     double min_ellipse_size, max_noise;
1293 };
1294
1295
1296 CV_FitEllipseTest::CV_FitEllipseTest()
1297 {
1298     min_log_size = 5; // for robust ellipse fitting a dozen of points is needed at least
1299     max_log_size = 10;
1300     min_ellipse_size = 10;
1301     max_noise = 0.05;
1302 }
1303
1304
1305 void CV_FitEllipseTest::generate_point_set( void* pointsSet )
1306 {
1307     RNG& rng = ts->get_rng();
1308     int i, total, point_type;
1309     CvSeqReader reader;
1310     uchar* data = 0;
1311     double a, b;
1312
1313     box0.center.x = (float)((low.val[0] + high.val[0])*0.5);
1314     box0.center.y = (float)((low.val[1] + high.val[1])*0.5);
1315     box0.size.width = (float)(MAX(high.val[0] - low.val[0], min_ellipse_size)*2);
1316     box0.size.height = (float)(MAX(high.val[1] - low.val[1], min_ellipse_size)*2);
1317     box0.angle = (float)(cvtest::randReal(rng)*180);
1318     a = cos(box0.angle*CV_PI/180.);
1319     b = sin(box0.angle*CV_PI/180.);
1320
1321     if( box0.size.width > box0.size.height )
1322     {
1323         float t;
1324         CV_SWAP( box0.size.width, box0.size.height, t );
1325     }
1326     memset( &reader, 0, sizeof(reader) );
1327
1328     if( CV_IS_SEQ(pointsSet) )
1329     {
1330         CvSeq* ptseq = (CvSeq*)pointsSet;
1331         total = ptseq->total;
1332         point_type = CV_SEQ_ELTYPE(ptseq);
1333         cvStartReadSeq( ptseq, &reader );
1334     }
1335     else
1336     {
1337         CvMat* ptm = (CvMat*)pointsSet;
1338         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
1339         total = ptm->rows + ptm->cols - 1;
1340         point_type = CV_MAT_TYPE(ptm->type);
1341         data = ptm->data.ptr;
1342     }
1343
1344     CV_Assert(point_type == CV_32SC2 || point_type == CV_32FC2);
1345
1346     for( i = 0; i < total; i++ )
1347     {
1348         CvPoint* pp;
1349         CvPoint2D32f p = {0, 0};
1350         double angle = cvtest::randReal(rng)*CV_PI*2;
1351         double x = box0.size.height*0.5*(cos(angle) + (cvtest::randReal(rng)-0.5)*2*max_noise);
1352         double y = box0.size.width*0.5*(sin(angle) + (cvtest::randReal(rng)-0.5)*2*max_noise);
1353         p.x = (float)(box0.center.x + a*x + b*y);
1354         p.y = (float)(box0.center.y - b*x + a*y);
1355
1356         if( reader.ptr )
1357         {
1358             pp = (CvPoint*)reader.ptr;
1359             CV_NEXT_SEQ_ELEM( sizeof(*pp), reader );
1360         }
1361         else
1362             pp = ((CvPoint*)data) + i;
1363         if( point_type == CV_32SC2 )
1364         {
1365             pp->x = cvRound(p.x);
1366             pp->y = cvRound(p.y);
1367         }
1368         else
1369             *(CvPoint2D32f*)pp = p;
1370     }
1371 }
1372
1373
1374 int CV_FitEllipseTest::prepare_test_case( int test_case_idx )
1375 {
1376     min_log_size = MAX(min_log_size,4);
1377     max_log_size = MAX(min_log_size,max_log_size);
1378     return CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1379 }
1380
1381
1382 void CV_FitEllipseTest::run_func()
1383 {
1384     if(!test_cpp)
1385         box = cvFitEllipse2( points );
1386     else
1387         box = cv::fitEllipse(cv::cvarrToMat(points));
1388 }
1389
1390 int CV_FitEllipseTest::validate_test_results( int test_case_idx )
1391 {
1392     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1393     double diff_angle;
1394
1395     if( cvIsNaN(box.center.x) || cvIsInf(box.center.x) ||
1396         cvIsNaN(box.center.y) || cvIsInf(box.center.y) ||
1397         cvIsNaN(box.size.width) || cvIsInf(box.size.width) ||
1398         cvIsNaN(box.size.height) || cvIsInf(box.size.height) ||
1399         cvIsNaN(box.angle) || cvIsInf(box.angle) )
1400     {
1401         ts->printf( cvtest::TS::LOG, "Some of the computed ellipse parameters are invalid (x=%g,y=%g,w=%g,h=%g,angle=%g)\n",
1402             box.center.x, box.center.y, box.size.width, box.size.height, box.angle );
1403         code = cvtest::TS::FAIL_INVALID_OUTPUT;
1404         goto _exit_;
1405     }
1406
1407     box.angle = (float)(90-box.angle);
1408     if( box.angle < 0 )
1409         box.angle += 360;
1410     if( box.angle > 360 )
1411         box.angle -= 360;
1412
1413     if( fabs(box.center.x - box0.center.x) > 3 ||
1414         fabs(box.center.y - box0.center.y) > 3 ||
1415         fabs(box.size.width - box0.size.width) > 0.1*fabs(box0.size.width) ||
1416         fabs(box.size.height - box0.size.height) > 0.1*fabs(box0.size.height) )
1417     {
1418         ts->printf( cvtest::TS::LOG, "The computed ellipse center and/or size are incorrect:\n\t"
1419             "(x=%.1f,y=%.1f,w=%.1f,h=%.1f), while it should be (x=%.1f,y=%.1f,w=%.1f,h=%.1f)\n",
1420             box.center.x, box.center.y, box.size.width, box.size.height,
1421             box0.center.x, box0.center.y, box0.size.width, box0.size.height );
1422         code = cvtest::TS::FAIL_BAD_ACCURACY;
1423         goto _exit_;
1424     }
1425
1426     diff_angle = fabs(box0.angle - box.angle);
1427     diff_angle = MIN( diff_angle, fabs(diff_angle - 360));
1428     diff_angle = MIN( diff_angle, fabs(diff_angle - 180));
1429
1430     if( box0.size.height >= 1.3*box0.size.width && diff_angle > 30 )
1431     {
1432         ts->printf( cvtest::TS::LOG, "Incorrect ellipse angle (=%1.f, should be %1.f)\n",
1433             box.angle, box0.angle );
1434         code = cvtest::TS::FAIL_BAD_ACCURACY;
1435         goto _exit_;
1436     }
1437
1438 _exit_:
1439
1440 #if 0
1441     if( code < 0 )
1442     {
1443     cvNamedWindow( "test", 0 );
1444     IplImage* img = cvCreateImage( cvSize(cvRound(low_high_range*4),
1445         cvRound(low_high_range*4)), 8, 3 );
1446     cvZero( img );
1447
1448     box.center.x += (float)low_high_range*2;
1449     box.center.y += (float)low_high_range*2;
1450     cvEllipseBox( img, box, CV_RGB(255,0,0), 3, 8 );
1451
1452     for( int i = 0; i < points2->rows + points2->cols - 1; i++ )
1453     {
1454         CvPoint pt;
1455         pt.x = cvRound(points2->data.fl[i*2] + low_high_range*2);
1456         pt.y = cvRound(points2->data.fl[i*2+1] + low_high_range*2);
1457         cvCircle( img, pt, 1, CV_RGB(255,255,255), -1, 8 );
1458     }
1459
1460     cvShowImage( "test", img );
1461     cvReleaseImage( &img );
1462     cvWaitKey(0);
1463     }
1464 #endif
1465
1466     if( code < 0 )
1467     {
1468         ts->set_failed_test_info( code );
1469     }
1470     return code;
1471 }
1472
1473
1474 class CV_FitEllipseSmallTest : public cvtest::BaseTest
1475 {
1476 public:
1477     CV_FitEllipseSmallTest() {}
1478     ~CV_FitEllipseSmallTest() {}
1479 protected:
1480     void run(int)
1481     {
1482         Size sz(50, 50);
1483         vector<vector<Point> > c;
1484         c.push_back(vector<Point>());
1485         int scale = 1;
1486         Point ofs = Point(0,0);//sz.width/2, sz.height/2) - Point(4,4)*scale;
1487         c[0].push_back(Point(2, 0)*scale+ofs);
1488         c[0].push_back(Point(0, 2)*scale+ofs);
1489         c[0].push_back(Point(0, 6)*scale+ofs);
1490         c[0].push_back(Point(2, 8)*scale+ofs);
1491         c[0].push_back(Point(6, 8)*scale+ofs);
1492         c[0].push_back(Point(8, 6)*scale+ofs);
1493         c[0].push_back(Point(8, 2)*scale+ofs);
1494         c[0].push_back(Point(6, 0)*scale+ofs);
1495
1496         RotatedRect e = fitEllipse(c[0]);
1497         CV_Assert( fabs(e.center.x - 4) <= 1. &&
1498                    fabs(e.center.y - 4) <= 1. &&
1499                    fabs(e.size.width - 9) <= 1. &&
1500                    fabs(e.size.height - 9) <= 1. );
1501     }
1502 };
1503
1504
1505 // Regression test for incorrect fitEllipse result reported in Bug #3989
1506 // Check edge cases for rotation angles of ellipse ([-180, 90, 0, 90, 180] degrees)
1507 class CV_FitEllipseParallelTest : public CV_FitEllipseTest
1508 {
1509 public:
1510     CV_FitEllipseParallelTest();
1511     ~CV_FitEllipseParallelTest();
1512 protected:
1513     void generate_point_set( void* points );
1514     void run_func(void);
1515     Mat pointsMat;
1516 };
1517
1518 CV_FitEllipseParallelTest::CV_FitEllipseParallelTest()
1519 {
1520     min_ellipse_size = 5;
1521 }
1522
1523 void CV_FitEllipseParallelTest::generate_point_set( void* )
1524 {
1525     RNG& rng = ts->get_rng();
1526     int height = (int)(MAX(high.val[0] - low.val[0], min_ellipse_size));
1527     int width = (int)(MAX(high.val[1] - low.val[1], min_ellipse_size));
1528     const int angle = ( (cvtest::randInt(rng) % 5) - 2 ) * 90;
1529     const int dim = max(height, width);
1530     const Point center = Point(dim*2, dim*2);
1531
1532     if( width > height )
1533     {
1534         int t;
1535         CV_SWAP( width, height, t );
1536     }
1537
1538     Mat image = Mat::zeros(dim*4, dim*4, CV_8UC1);
1539     ellipse(image, center, Size(height, width), angle,
1540             0, 360, Scalar(255, 0, 0), 1, 8);
1541
1542     box0.center.x = (float)center.x;
1543     box0.center.y = (float)center.y;
1544     box0.size.width = (float)width*2;
1545     box0.size.height = (float)height*2;
1546     box0.angle = (float)angle;
1547
1548     vector<vector<Point> > contours;
1549     findContours(image, contours,  RETR_EXTERNAL,  CHAIN_APPROX_NONE);
1550     Mat(contours[0]).convertTo(pointsMat, CV_32F);
1551 }
1552
1553 void CV_FitEllipseParallelTest::run_func()
1554 {
1555     box = cv::fitEllipse(pointsMat);
1556 }
1557
1558 CV_FitEllipseParallelTest::~CV_FitEllipseParallelTest(){
1559     pointsMat.release();
1560 }
1561
1562 /****************************************************************************************\
1563 *                                   FitLine Test                                         *
1564 \****************************************************************************************/
1565
1566 class CV_FitLineTest : public CV_BaseShapeDescrTest
1567 {
1568 public:
1569     CV_FitLineTest();
1570
1571 protected:
1572     int prepare_test_case( int test_case_idx );
1573     void generate_point_set( void* points );
1574     void run_func(void);
1575     int validate_test_results( int test_case_idx );
1576     double max_noise;
1577     AutoBuffer<float> line, line0;
1578     int dist_type;
1579     double reps, aeps;
1580 };
1581
1582
1583 CV_FitLineTest::CV_FitLineTest()
1584 {
1585     min_log_size = 5; // for robust line fitting a dozen of points is needed at least
1586     max_log_size = 10;
1587     max_noise = 0.05;
1588 }
1589
1590 void CV_FitLineTest::generate_point_set( void* pointsSet )
1591 {
1592     RNG& rng = ts->get_rng();
1593     int i, k, n, total, point_type;
1594     CvSeqReader reader;
1595     uchar* data = 0;
1596     double s = 0;
1597
1598     n = dims;
1599     for( k = 0; k < n; k++ )
1600     {
1601         line0[k+n] = (float)((low.val[k] + high.val[k])*0.5);
1602         line0[k] = (float)(high.val[k] - low.val[k]);
1603         if( cvtest::randInt(rng) % 2 )
1604             line0[k] = -line0[k];
1605         s += (double)line0[k]*line0[k];
1606     }
1607
1608     s = 1./sqrt(s);
1609     for( k = 0; k < n; k++ )
1610         line0[k] = (float)(line0[k]*s);
1611
1612     memset( &reader, 0, sizeof(reader) );
1613
1614     if( CV_IS_SEQ(pointsSet) )
1615     {
1616         CvSeq* ptseq = (CvSeq*)pointsSet;
1617         total = ptseq->total;
1618         point_type = CV_MAT_DEPTH(CV_SEQ_ELTYPE(ptseq));
1619         cvStartReadSeq( ptseq, &reader );
1620     }
1621     else
1622     {
1623         CvMat* ptm = (CvMat*)pointsSet;
1624         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
1625         total = ptm->rows + ptm->cols - 1;
1626         point_type = CV_MAT_DEPTH(CV_MAT_TYPE(ptm->type));
1627         data = ptm->data.ptr;
1628     }
1629
1630     for( i = 0; i < total; i++ )
1631     {
1632         int* pi;
1633         float* pf;
1634         float p[4], t;
1635         if( reader.ptr )
1636         {
1637             pi = (int*)reader.ptr;
1638             pf = (float*)reader.ptr;
1639             CV_NEXT_SEQ_ELEM( reader.seq->elem_size, reader );
1640         }
1641         else
1642         {
1643             pi = (int*)data + i*n;
1644             pf = (float*)data + i*n;
1645         }
1646
1647         t = (float)((cvtest::randReal(rng)-0.5)*low_high_range*2);
1648
1649         for( k = 0; k < n; k++ )
1650         {
1651             p[k] = (float)((cvtest::randReal(rng)-0.5)*max_noise*2 + t*line0[k] + line0[k+n]);
1652
1653             if( point_type == CV_32S )
1654                 pi[k] = cvRound(p[k]);
1655             else
1656                 pf[k] = p[k];
1657         }
1658     }
1659 }
1660
1661 int CV_FitLineTest::prepare_test_case( int test_case_idx )
1662 {
1663     RNG& rng = ts->get_rng();
1664     dims = cvtest::randInt(rng) % 2 + 2;
1665     line.allocate(dims * 2);
1666     line0.allocate(dims * 2);
1667     min_log_size = MAX(min_log_size,5);
1668     max_log_size = MAX(min_log_size,max_log_size);
1669     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1670     dist_type = cvtest::randInt(rng) % 6 + 1;
1671     dist_type += dist_type == CV_DIST_C;
1672     reps = 0.1; aeps = 0.01;
1673     return code;
1674 }
1675
1676
1677 void CV_FitLineTest::run_func()
1678 {
1679     if(!test_cpp)
1680         cvFitLine( points, dist_type, 0, reps, aeps, line.data());
1681     else if(dims == 2)
1682         cv::fitLine(cv::cvarrToMat(points), (cv::Vec4f&)line[0], dist_type, 0, reps, aeps);
1683     else
1684         cv::fitLine(cv::cvarrToMat(points), (cv::Vec6f&)line[0], dist_type, 0, reps, aeps);
1685 }
1686
1687 int CV_FitLineTest::validate_test_results( int test_case_idx )
1688 {
1689     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1690     int k, max_k = 0;
1691     double vec_diff = 0, t;
1692
1693     //std::cout << dims << " " << Mat(1, dims*2, CV_32FC1, line.data()) << " " << Mat(1, dims, CV_32FC1, line0.data()) << std::endl;
1694
1695     for( k = 0; k < dims*2; k++ )
1696     {
1697         if( cvIsNaN(line[k]) || cvIsInf(line[k]) )
1698         {
1699             ts->printf( cvtest::TS::LOG, "Some of the computed line parameters are invalid (line[%d]=%g)\n",
1700                 k, line[k] );
1701             code = cvtest::TS::FAIL_INVALID_OUTPUT;
1702             goto _exit_;
1703         }
1704     }
1705
1706     if( fabs(line0[1]) > fabs(line0[0]) )
1707         max_k = 1;
1708     if( fabs(line0[dims-1]) > fabs(line0[max_k]) )
1709         max_k = dims-1;
1710     if( line0[max_k] < 0 )
1711         for( k = 0; k < dims; k++ )
1712             line0[k] = -line0[k];
1713     if( line[max_k] < 0 )
1714         for( k = 0; k < dims; k++ )
1715             line[k] = -line[k];
1716
1717     for( k = 0; k < dims; k++ )
1718     {
1719         double dt = line[k] - line0[k];
1720         vec_diff += dt*dt;
1721     }
1722
1723     if( sqrt(vec_diff) > 0.05 )
1724     {
1725         if( dims == 2 )
1726             ts->printf( cvtest::TS::LOG,
1727                 "The computed line vector (%.2f,%.2f) is different from the actual (%.2f,%.2f)\n",
1728                 line[0], line[1], line0[0], line0[1] );
1729         else
1730             ts->printf( cvtest::TS::LOG,
1731                 "The computed line vector (%.2f,%.2f,%.2f) is different from the actual (%.2f,%.2f,%.2f)\n",
1732                 line[0], line[1], line[2], line0[0], line0[1], line0[2] );
1733         code = cvtest::TS::FAIL_BAD_ACCURACY;
1734         goto _exit_;
1735     }
1736
1737     t = (line[max_k+dims] - line0[max_k+dims])/line0[max_k];
1738     for( k = 0; k < dims; k++ )
1739     {
1740         double p = line0[k+dims] + t*line0[k] - line[k+dims];
1741         vec_diff += p*p;
1742     }
1743
1744     if( sqrt(vec_diff) > 1*MAX(fabs(t),1) )
1745     {
1746         if( dims == 2 )
1747             ts->printf( cvtest::TS::LOG,
1748                 "The computed line point (%.2f,%.2f) is too far from the actual line\n",
1749                 line[2]+line0[2], line[3]+line0[3] );
1750         else
1751             ts->printf( cvtest::TS::LOG,
1752                 "The computed line point (%.2f,%.2f,%.2f) is too far from the actual line\n",
1753                 line[3]+line0[3], line[4]+line0[4], line[5]+line0[5] );
1754         code = cvtest::TS::FAIL_BAD_ACCURACY;
1755         goto _exit_;
1756     }
1757
1758 _exit_:
1759
1760     if( code < 0 )
1761     {
1762         ts->set_failed_test_info( code );
1763     }
1764     return code;
1765 }
1766
1767 /****************************************************************************************\
1768 *                                   ContourMoments Test                                  *
1769 \****************************************************************************************/
1770
1771
1772 static void
1773 cvTsGenerateTousledBlob( CvPoint2D32f center, CvSize2D32f axes,
1774     double max_r_scale, double angle, CvArr* points, RNG& rng )
1775 {
1776     int i, total, point_type;
1777     uchar* data = 0;
1778     CvSeqReader reader;
1779     memset( &reader, 0, sizeof(reader) );
1780
1781     if( CV_IS_SEQ(points) )
1782     {
1783         CvSeq* ptseq = (CvSeq*)points;
1784         total = ptseq->total;
1785         point_type = CV_SEQ_ELTYPE(ptseq);
1786         cvStartReadSeq( ptseq, &reader );
1787     }
1788     else
1789     {
1790         CvMat* ptm = (CvMat*)points;
1791         assert( CV_IS_MAT(ptm) && CV_IS_MAT_CONT(ptm->type) );
1792         total = ptm->rows + ptm->cols - 1;
1793         point_type = CV_MAT_TYPE(ptm->type);
1794         data = ptm->data.ptr;
1795     }
1796
1797     assert( point_type == CV_32SC2 || point_type == CV_32FC2 );
1798
1799     for( i = 0; i < total; i++ )
1800     {
1801         CvPoint* pp;
1802         Point2f p;
1803
1804         double phi0 = 2*CV_PI*i/total;
1805         double phi = CV_PI*angle/180.;
1806         double t = cvtest::randReal(rng)*max_r_scale + (1 - max_r_scale);
1807         double ta = axes.height*t;
1808         double tb = axes.width*t;
1809         double c0 = cos(phi0)*ta, s0 = sin(phi0)*tb;
1810         double c = cos(phi), s = sin(phi);
1811         p.x = (float)(c0*c - s0*s + center.x);
1812         p.y = (float)(c0*s + s0*c + center.y);
1813
1814         if( reader.ptr )
1815         {
1816             pp = (CvPoint*)reader.ptr;
1817             CV_NEXT_SEQ_ELEM( sizeof(*pp), reader );
1818         }
1819         else
1820             pp = ((CvPoint*)data) + i;
1821
1822         if( point_type == CV_32SC2 )
1823         {
1824             pp->x = cvRound(p.x);
1825             pp->y = cvRound(p.y);
1826         }
1827         else
1828             *(CvPoint2D32f*)pp = cvPoint2D32f(p);
1829     }
1830 }
1831
1832
1833 class CV_ContourMomentsTest : public CV_BaseShapeDescrTest
1834 {
1835 public:
1836     CV_ContourMomentsTest();
1837
1838 protected:
1839     int prepare_test_case( int test_case_idx );
1840     void generate_point_set( void* points );
1841     void run_func(void);
1842     int validate_test_results( int test_case_idx );
1843     CvMoments moments0, moments;
1844     double area0, area;
1845     Size2f axes;
1846     Point2f center;
1847     int max_max_r_scale;
1848     double max_r_scale, angle;
1849     Size img_size;
1850 };
1851
1852
1853 CV_ContourMomentsTest::CV_ContourMomentsTest()
1854 {
1855     min_log_size = 3;
1856     max_log_size = 8;
1857     max_max_r_scale = 15;
1858     low_high_range = 200;
1859     enable_flt_points = false;
1860 }
1861
1862
1863 void CV_ContourMomentsTest::generate_point_set( void* pointsSet )
1864 {
1865     RNG& rng = ts->get_rng();
1866     float max_sz;
1867
1868     axes.width = (float)((cvtest::randReal(rng)*0.9 + 0.1)*low_high_range);
1869     axes.height = (float)((cvtest::randReal(rng)*0.9 + 0.1)*low_high_range);
1870     max_sz = MAX(axes.width, axes.height);
1871
1872     img_size.width = img_size.height = cvRound(low_high_range*2.2);
1873
1874     center.x = (float)(img_size.width*0.5 + (cvtest::randReal(rng)-0.5)*(img_size.width - max_sz*2)*0.8);
1875     center.y = (float)(img_size.height*0.5 + (cvtest::randReal(rng)-0.5)*(img_size.height - max_sz*2)*0.8);
1876
1877     assert( 0 < center.x - max_sz && center.x + max_sz < img_size.width &&
1878         0 < center.y - max_sz && center.y + max_sz < img_size.height );
1879
1880     max_r_scale = cvtest::randReal(rng)*max_max_r_scale*0.01;
1881     angle = cvtest::randReal(rng)*360;
1882
1883     cvTsGenerateTousledBlob( cvPoint2D32f(center), cvSize2D32f(axes), max_r_scale, angle, pointsSet, rng );
1884
1885     if( points1 )
1886         points1->flags = CV_SEQ_MAGIC_VAL + CV_SEQ_POLYGON;
1887 }
1888
1889
1890 int CV_ContourMomentsTest::prepare_test_case( int test_case_idx )
1891 {
1892     min_log_size = MAX(min_log_size,3);
1893     max_log_size = MIN(max_log_size,8);
1894     max_log_size = MAX(min_log_size,max_log_size);
1895     int code = CV_BaseShapeDescrTest::prepare_test_case( test_case_idx );
1896     return code;
1897 }
1898
1899
1900 void CV_ContourMomentsTest::run_func()
1901 {
1902     if(!test_cpp)
1903     {
1904         cvMoments( points, &moments );
1905         area = cvContourArea( points );
1906     }
1907     else
1908     {
1909         moments = cvMoments(cv::moments(cv::cvarrToMat(points)));
1910         area = cv::contourArea(cv::cvarrToMat(points));
1911     }
1912 }
1913
1914
1915 int CV_ContourMomentsTest::validate_test_results( int test_case_idx )
1916 {
1917     int code = CV_BaseShapeDescrTest::validate_test_results( test_case_idx );
1918     int i, n = (int)(sizeof(moments)/sizeof(moments.inv_sqrt_m00));
1919     CvMat* img = cvCreateMat( img_size.height, img_size.width, CV_8UC1 );
1920     CvPoint* pt = (CvPoint*)points2->data.i;
1921     int count = points2->cols + points2->rows - 1;
1922     double max_v0 = 0;
1923
1924     cvZero(img);
1925     cvFillPoly( img, &pt, &count, 1, cvScalarAll(1));
1926     cvMoments( img, &moments0 );
1927
1928     for( i = 0; i < n; i++ )
1929     {
1930         double t = fabs((&moments0.m00)[i]);
1931         max_v0 = MAX(max_v0, t);
1932     }
1933
1934     for( i = 0; i <= n; i++ )
1935     {
1936         double v = i < n ? (&moments.m00)[i] : area;
1937         double v0 = i < n ? (&moments0.m00)[i] : moments0.m00;
1938
1939         if( cvIsNaN(v) || cvIsInf(v) )
1940         {
1941             ts->printf( cvtest::TS::LOG,
1942                 "The contour %s is invalid (=%g)\n", i < n ? "moment" : "area", v );
1943             code = cvtest::TS::FAIL_INVALID_OUTPUT;
1944             break;
1945         }
1946
1947         if( fabs(v - v0) > 0.1*max_v0 )
1948         {
1949             ts->printf( cvtest::TS::LOG,
1950                 "The computed contour %s is %g, while it should be %g\n",
1951                 i < n ? "moment" : "area", v, v0 );
1952             code = cvtest::TS::FAIL_BAD_ACCURACY;
1953             break;
1954         }
1955     }
1956
1957     if( code < 0 )
1958     {
1959 #if 0
1960         cvCmpS( img, 0, img, CV_CMP_GT );
1961         cvNamedWindow( "test", 1 );
1962         cvShowImage( "test", img );
1963         cvWaitKey();
1964 #endif
1965         ts->set_failed_test_info( code );
1966     }
1967
1968     cvReleaseMat( &img );
1969     return code;
1970 }
1971
1972
1973 ////////////////////////////////////// Perimeter/Area/Slice test ///////////////////////////////////
1974
1975 class CV_PerimeterAreaSliceTest : public cvtest::BaseTest
1976 {
1977 public:
1978     CV_PerimeterAreaSliceTest();
1979     ~CV_PerimeterAreaSliceTest();
1980 protected:
1981     void run(int);
1982 };
1983
1984 CV_PerimeterAreaSliceTest::CV_PerimeterAreaSliceTest()
1985 {
1986 }
1987 CV_PerimeterAreaSliceTest::~CV_PerimeterAreaSliceTest() {}
1988
1989 void CV_PerimeterAreaSliceTest::run( int )
1990 {
1991     Ptr<CvMemStorage> storage(cvCreateMemStorage());
1992     RNG& rng = theRNG();
1993     const double min_r = 90, max_r = 120;
1994
1995     for( int i = 0; i < 100; i++ )
1996     {
1997         ts->update_context( this, i, true );
1998         int n = rng.uniform(3, 30);
1999         cvClearMemStorage(storage);
2000         CvSeq* contour = cvCreateSeq(CV_SEQ_POLYGON, sizeof(CvSeq), sizeof(CvPoint), storage);
2001         double dphi = CV_PI*2/n;
2002         Point center;
2003         center.x = rng.uniform(cvCeil(max_r), cvFloor(640-max_r));
2004         center.y = rng.uniform(cvCeil(max_r), cvFloor(480-max_r));
2005
2006         for( int j = 0; j < n; j++ )
2007         {
2008             CvPoint pt = CV_STRUCT_INITIALIZER;
2009             double r = rng.uniform(min_r, max_r);
2010             double phi = j*dphi;
2011             pt.x = cvRound(center.x + r*cos(phi));
2012             pt.y = cvRound(center.y - r*sin(phi));
2013             cvSeqPush(contour, &pt);
2014         }
2015
2016         CvSlice slice = {0, 0};
2017         for(;;)
2018         {
2019             slice.start_index = rng.uniform(-n/2, 3*n/2);
2020             slice.end_index = rng.uniform(-n/2, 3*n/2);
2021             int len = cvSliceLength(slice, contour);
2022             if( len > 2 )
2023                 break;
2024         }
2025         CvSeq *cslice = cvSeqSlice(contour, slice);
2026         /*printf( "%d. (%d, %d) of %d, length = %d, length1 = %d\n",
2027                i, slice.start_index, slice.end_index,
2028                contour->total, cvSliceLength(slice, contour), cslice->total );
2029
2030         double area0 = cvContourArea(cslice);
2031         double area1 = cvContourArea(contour, slice);
2032         if( area0 != area1 )
2033         {
2034             ts->printf(cvtest::TS::LOG,
2035                        "The contour area slice is computed differently (%g vs %g)\n", area0, area1 );
2036             ts->set_failed_test_info( cvtest::TS::FAIL_BAD_ACCURACY );
2037             return;
2038         }*/
2039
2040         double len0 = cvArcLength(cslice, CV_WHOLE_SEQ, 1);
2041         double len1 = cvArcLength(contour, slice, 1);
2042         if( len0 != len1 )
2043         {
2044             ts->printf(cvtest::TS::LOG,
2045                        "The contour arc length is computed differently (%g vs %g)\n", len0, len1 );
2046             ts->set_failed_test_info( cvtest::TS::FAIL_BAD_ACCURACY );
2047             return;
2048         }
2049     }
2050     ts->set_failed_test_info(cvtest::TS::OK);
2051 }
2052
2053
2054 TEST(Imgproc_ConvexHull, accuracy) { CV_ConvHullTest test; test.safe_run(); }
2055 TEST(Imgproc_MinAreaRect, accuracy) { CV_MinAreaRectTest test; test.safe_run(); }
2056 TEST(Imgproc_MinTriangle, accuracy) { CV_MinTriangleTest test; test.safe_run(); }
2057 TEST(Imgproc_MinCircle, accuracy) { CV_MinCircleTest test; test.safe_run(); }
2058 TEST(Imgproc_MinCircle2, accuracy) { CV_MinCircleTest2 test; test.safe_run(); }
2059 TEST(Imgproc_ContourPerimeter, accuracy) { CV_PerimeterTest test; test.safe_run(); }
2060 TEST(Imgproc_FitEllipse, accuracy) { CV_FitEllipseTest test; test.safe_run(); }
2061 TEST(Imgproc_FitEllipse, parallel) { CV_FitEllipseParallelTest test; test.safe_run(); }
2062 TEST(Imgproc_FitLine, accuracy) { CV_FitLineTest test; test.safe_run(); }
2063 TEST(Imgproc_ContourMoments, accuracy) { CV_ContourMomentsTest test; test.safe_run(); }
2064 TEST(Imgproc_ContourPerimeterSlice, accuracy) { CV_PerimeterAreaSliceTest test; test.safe_run(); }
2065 TEST(Imgproc_FitEllipse, small) { CV_FitEllipseSmallTest test; test.safe_run(); }
2066
2067
2068
2069 PARAM_TEST_CASE(ConvexityDefects_regression_5908, bool, int)
2070 {
2071 public:
2072     int start_index;
2073     bool clockwise;
2074
2075     Mat contour;
2076
2077     virtual void SetUp()
2078     {
2079         clockwise = GET_PARAM(0);
2080         start_index = GET_PARAM(1);
2081
2082         const int N = 11;
2083         const Point2i points[N] = {
2084             Point2i(154, 408),
2085             Point2i(45, 223),
2086             Point2i(115, 275), // inner
2087             Point2i(104, 166),
2088             Point2i(154, 256), // inner
2089             Point2i(169, 144),
2090             Point2i(185, 256), // inner
2091             Point2i(235, 170),
2092             Point2i(240, 320), // inner
2093             Point2i(330, 287),
2094             Point2i(224, 390)
2095         };
2096
2097         contour = Mat(N, 1, CV_32SC2);
2098         for (int i = 0; i < N; i++)
2099         {
2100             contour.at<Point2i>(i) = (!clockwise) // image and convexHull coordinate systems are different
2101                     ? points[(start_index + i) % N]
2102                     : points[N - 1 - ((start_index + i) % N)];
2103         }
2104     }
2105 };
2106
2107 TEST_P(ConvexityDefects_regression_5908, simple)
2108 {
2109     std::vector<int> hull;
2110     cv::convexHull(contour, hull, clockwise, false);
2111
2112     std::vector<Vec4i> result;
2113     cv::convexityDefects(contour, hull, result);
2114
2115     EXPECT_EQ(4, (int)result.size());
2116 }
2117
2118 INSTANTIATE_TEST_CASE_P(Imgproc, ConvexityDefects_regression_5908,
2119         testing::Combine(
2120                 testing::Bool(),
2121                 testing::Values(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
2122         ));
2123
2124 TEST(Imgproc_FitLine, regression_15083)
2125 {
2126     int points2i_[] = {
2127         432, 654,
2128         370, 656,
2129         390, 656,
2130         410, 656,
2131         348, 658
2132     };
2133     Mat points(5, 1, CV_32SC2, points2i_);
2134
2135     Vec4f lineParam;
2136     fitLine(points, lineParam, DIST_L1, 0, 0.01, 0.01);
2137     EXPECT_GE(fabs(lineParam[0]), fabs(lineParam[1]) * 4) << lineParam;
2138 }
2139
2140 TEST(Imgproc_FitLine, regression_4903)
2141 {
2142     float points2f_[] = {
2143         1224.0, 576.0,
2144         1234.0, 683.0,
2145         1215.0, 471.0,
2146         1184.0, 137.0,
2147         1079.0, 377.0,
2148         1239.0, 788.0,
2149     };
2150     Mat points(6, 1, CV_32FC2, points2f_);
2151
2152     Vec4f lineParam;
2153     fitLine(points, lineParam, DIST_WELSCH, 0, 0.01, 0.01);
2154     EXPECT_GE(fabs(lineParam[1]), fabs(lineParam[0]) * 4) << lineParam;
2155 }
2156
2157 }} // namespace
2158 /* End of file. */