modules/core/src/drawing.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 #include "precomp.hpp"
  42
  43 namespace cv
  44 {
  45
  46 enum { XY_SHIFT = 16, XY_ONE = 1 << XY_SHIFT, DRAWING_STORAGE_BLOCK = (1<<12) - 256 };
  47
  48 struct PolyEdge
  49 {
  50     PolyEdge() : y0(0), y1(0), x(0), dx(0), next(0) {}
  51     //PolyEdge(int _y0, int _y1, int _x, int _dx) : y0(_y0), y1(_y1), x(_x), dx(_dx) {}
  52
  53     int y0, y1;
  54     int x, dx;
  55     PolyEdge *next;
  56 };
  57
  58 static void
  59 CollectPolyEdges( Mat& img, const Point* v, int npts,
  60                   vector<PolyEdge>& edges, const void* color, int line_type,
  61                   int shift, Point offset=Point() );
  62
  63 static void
  64 FillEdgeCollection( Mat& img, vector<PolyEdge>& edges, const void* color );
  65
  66 static void
  67 PolyLine( Mat& img, const Point* v, int npts, bool closed,
  68           const void* color, int thickness, int line_type, int shift );
  69
  70 static void
  71 FillConvexPoly( Mat& img, const Point* v, int npts,
  72                 const void* color, int line_type, int shift );
  73
  74 /****************************************************************************************\
  75 *                                   Lines                                                *
  76 \****************************************************************************************/
  77
  78 bool clipLine( Size img_size, Point& pt1, Point& pt2 )
  79 {
  80     int64 x1, y1, x2, y2;
  81     int c1, c2;
  82     int64 right = img_size.width-1, bottom = img_size.height-1;
  83
  84     if( img_size.width <= 0 || img_size.height <= 0 )
  85         return false;
  86
  87     x1 = pt1.x; y1 = pt1.y; x2 = pt2.x; y2 = pt2.y;
  88     c1 = (x1 < 0) + (x1 > right) * 2 + (y1 < 0) * 4 + (y1 > bottom) * 8;
  89     c2 = (x2 < 0) + (x2 > right) * 2 + (y2 < 0) * 4 + (y2 > bottom) * 8;
  90
  91     if( (c1 & c2) == 0 && (c1 | c2) != 0 )
  92     {
  93         int64 a;
  94         if( c1 & 12 )
  95         {
  96             a = c1 < 8 ? 0 : bottom;
  97             x1 +=  (a - y1) * (x2 - x1) / (y2 - y1);
  98             y1 = a;
  99             c1 = (x1 < 0) + (x1 > right) * 2;
 100         }
 101         if( c2 & 12 )
 102         {
 103             a = c2 < 8 ? 0 : bottom;
 104             x2 += (a - y2) * (x2 - x1) / (y2 - y1);
 105             y2 = a;
 106             c2 = (x2 < 0) + (x2 > right) * 2;
 107         }
 108         if( (c1 & c2) == 0 && (c1 | c2) != 0 )
 109         {
 110             if( c1 )
 111             {
 112                 a = c1 == 1 ? 0 : right;
 113                 y1 += (a - x1) * (y2 - y1) / (x2 - x1);
 114                 x1 = a;
 115                 c1 = 0;
 116             }
 117             if( c2 )
 118             {
 119                 a = c2 == 1 ? 0 : right;
 120                 y2 += (a - x2) * (y2 - y1) / (x2 - x1);
 121                 x2 = a;
 122                 c2 = 0;
 123             }
 124         }
 125
 126         assert( (c1 & c2) != 0 || (x1 | y1 | x2 | y2) >= 0 );
 127
 128         pt1.x = (int)x1;
 129         pt1.y = (int)y1;
 130         pt2.x = (int)x2;
 131         pt2.y = (int)y2;
 132     }
 133
 134     return (c1 | c2) == 0;
 135 }
 136
 137 bool clipLine( Rect img_rect, Point& pt1, Point& pt2 )
 138 {
 139     Point tl = img_rect.tl();
 140     pt1 -= tl; pt2 -= tl;
 141     bool inside = clipLine(img_rect.size(), pt1, pt2);
 142     pt1 += tl; pt2 += tl;
 143
 144     return inside;
 145 }
 146
 147 /*
 148    Initializes line iterator.
 149    Returns number of points on the line or negative number if error.
 150 */
 151 LineIterator::LineIterator(const Mat& img, Point pt1, Point pt2,
 152                            int connectivity, bool left_to_right)
 153 {
 154     count = -1;
 155
 156     CV_Assert( connectivity == 8 || connectivity == 4 );
 157
 158     if( (unsigned)pt1.x >= (unsigned)(img.cols) ||
 159         (unsigned)pt2.x >= (unsigned)(img.cols) ||
 160         (unsigned)pt1.y >= (unsigned)(img.rows) ||
 161         (unsigned)pt2.y >= (unsigned)(img.rows) )
 162     {
 163         if( !clipLine( img.size(), pt1, pt2 ) )
 164         {
 165             ptr = img.data;
 166             err = plusDelta = minusDelta = plusStep = minusStep = count = 0;
 167             return;
 168         }
 169     }
 170
 171     int bt_pix0 = (int)img.elemSize(), bt_pix = bt_pix0;
 172     size_t istep = img.step;
 173
 174     int dx = pt2.x - pt1.x;
 175     int dy = pt2.y - pt1.y;
 176     int s = dx < 0 ? -1 : 0;
 177
 178     if( left_to_right )
 179     {
 180         dx = (dx ^ s) - s;
 181         dy = (dy ^ s) - s;
 182         pt1.x ^= (pt1.x ^ pt2.x) & s;
 183         pt1.y ^= (pt1.y ^ pt2.y) & s;
 184     }
 185     else
 186     {
 187         dx = (dx ^ s) - s;
 188         bt_pix = (bt_pix ^ s) - s;
 189     }
 190
 191     ptr = (uchar*)(img.data + pt1.y * istep + pt1.x * bt_pix0);
 192
 193     s = dy < 0 ? -1 : 0;
 194     dy = (dy ^ s) - s;
 195     istep = (istep ^ s) - s;
 196
 197     s = dy > dx ? -1 : 0;
 198
 199     /* conditional swaps */
 200     dx ^= dy & s;
 201     dy ^= dx & s;
 202     dx ^= dy & s;
 203
 204     bt_pix ^= istep & s;
 205     istep ^= bt_pix & s;
 206     bt_pix ^= istep & s;
 207
 208     if( connectivity == 8 )
 209     {
 210         assert( dx >= 0 && dy >= 0 );
 211
 212         err = dx - (dy + dy);
 213         plusDelta = dx + dx;
 214         minusDelta = -(dy + dy);
 215         plusStep = (int)istep;
 216         minusStep = bt_pix;
 217         count = dx + 1;
 218     }
 219     else /* connectivity == 4 */
 220     {
 221         assert( dx >= 0 && dy >= 0 );
 222
 223         err = 0;
 224         plusDelta = (dx + dx) + (dy + dy);
 225         minusDelta = -(dy + dy);
 226         plusStep = (int)istep - bt_pix;
 227         minusStep = bt_pix;
 228         count = dx + dy + 1;
 229     }
 230
 231     this->ptr0 = img.data;
 232     this->step = (int)img.step;
 233     this->elemSize = bt_pix0;
 234 }
 235
 236 static void
 237 Line( Mat& img, Point pt1, Point pt2,
 238       const void* _color, int connectivity = 8 )
 239 {
 240     if( connectivity == 0 )
 241         connectivity = 8;
 242     if( connectivity == 1 )
 243         connectivity = 4;
 244
 245     LineIterator iterator(img, pt1, pt2, connectivity, true);
 246     int i, count = iterator.count;
 247     int pix_size = (int)img.elemSize();
 248     const uchar* color = (const uchar*)_color;
 249
 250     for( i = 0; i < count; i++, ++iterator )
 251     {
 252         uchar* ptr = *iterator;
 253         if( pix_size == 1 )
 254             ptr[0] = color[0];
 255         else if( pix_size == 3 )
 256         {
 257             ptr[0] = color[0];
 258             ptr[1] = color[1];
 259             ptr[2] = color[2];
 260         }
 261         else
 262             memcpy( *iterator, color, pix_size );
 263     }
 264 }
 265
 266
 267 /* Correction table depent on the slope */
 268 static const uchar SlopeCorrTable[] = {
 269     181, 181, 181, 182, 182, 183, 184, 185, 187, 188, 190, 192, 194, 196, 198, 201,
 270     203, 206, 209, 211, 214, 218, 221, 224, 227, 231, 235, 238, 242, 246, 250, 254
 271 };
 272
 273 /* Gaussian for antialiasing filter */
 274 static const int FilterTable[] = {
 275     168, 177, 185, 194, 202, 210, 218, 224, 231, 236, 241, 246, 249, 252, 254, 254,
 276     254, 254, 252, 249, 246, 241, 236, 231, 224, 218, 210, 202, 194, 185, 177, 168,
 277     158, 149, 140, 131, 122, 114, 105, 97, 89, 82, 75, 68, 62, 56, 50, 45,
 278     40, 36, 32, 28, 25, 22, 19, 16, 14, 12, 11, 9, 8, 7, 5, 5
 279 };
 280
 281 static void
 282 LineAA( Mat& img, Point pt1, Point pt2, const void* color )
 283 {
 284     int dx, dy;
 285     int ecount, scount = 0;
 286     int slope;
 287     int ax, ay;
 288     int x_step, y_step;
 289     int i, j;
 290     int ep_table[9];
 291     int cb = ((uchar*)color)[0], cg = ((uchar*)color)[1], cr = ((uchar*)color)[2];
 292     int _cb, _cg, _cr;
 293     int nch = img.channels();
 294     uchar* ptr = img.data;
 295     size_t step = img.step;
 296     Size size = img.size();
 297
 298     if( !((nch == 1 || nch == 3) && img.depth() == CV_8U) )
 299     {
 300         Line(img, pt1, pt2, color);
 301         return;
 302     }
 303
 304     pt1.x -= XY_ONE*2;
 305     pt1.y -= XY_ONE*2;
 306     pt2.x -= XY_ONE*2;
 307     pt2.y -= XY_ONE*2;
 308     ptr += img.step*2 + 2*nch;
 309
 310     size.width = ((size.width - 5) << XY_SHIFT) + 1;
 311     size.height = ((size.height - 5) << XY_SHIFT) + 1;
 312
 313     if( !clipLine( size, pt1, pt2 ))
 314         return;
 315
 316     dx = pt2.x - pt1.x;
 317     dy = pt2.y - pt1.y;
 318
 319     j = dx < 0 ? -1 : 0;
 320     ax = (dx ^ j) - j;
 321     i = dy < 0 ? -1 : 0;
 322     ay = (dy ^ i) - i;
 323
 324     if( ax > ay )
 325     {
 326         dx = ax;
 327         dy = (dy ^ j) - j;
 328         pt1.x ^= pt2.x & j;
 329         pt2.x ^= pt1.x & j;
 330         pt1.x ^= pt2.x & j;
 331         pt1.y ^= pt2.y & j;
 332         pt2.y ^= pt1.y & j;
 333         pt1.y ^= pt2.y & j;
 334
 335         x_step = XY_ONE;
 336         y_step = (int) (((int64) dy << XY_SHIFT) / (ax | 1));
 337         pt2.x += XY_ONE;
 338         ecount = (pt2.x >> XY_SHIFT) - (pt1.x >> XY_SHIFT);
 339         j = -(pt1.x & (XY_ONE - 1));
 340         pt1.y += (int) ((((int64) y_step) * j) >> XY_SHIFT) + (XY_ONE >> 1);
 341         slope = (y_step >> (XY_SHIFT - 5)) & 0x3f;
 342         slope ^= (y_step < 0 ? 0x3f : 0);
 343
 344         /* Get 4-bit fractions for end-point adjustments */
 345         i = (pt1.x >> (XY_SHIFT - 7)) & 0x78;
 346         j = (pt2.x >> (XY_SHIFT - 7)) & 0x78;
 347     }
 348     else
 349     {
 350         dy = ay;
 351         dx = (dx ^ i) - i;
 352         pt1.x ^= pt2.x & i;
 353         pt2.x ^= pt1.x & i;
 354         pt1.x ^= pt2.x & i;
 355         pt1.y ^= pt2.y & i;
 356         pt2.y ^= pt1.y & i;
 357         pt1.y ^= pt2.y & i;
 358
 359         x_step = (int) (((int64) dx << XY_SHIFT) / (ay | 1));
 360         y_step = XY_ONE;
 361         pt2.y += XY_ONE;
 362         ecount = (pt2.y >> XY_SHIFT) - (pt1.y >> XY_SHIFT);
 363         j = -(pt1.y & (XY_ONE - 1));
 364         pt1.x += (int) ((((int64) x_step) * j) >> XY_SHIFT) + (XY_ONE >> 1);
 365         slope = (x_step >> (XY_SHIFT - 5)) & 0x3f;
 366         slope ^= (x_step < 0 ? 0x3f : 0);
 367
 368         /* Get 4-bit fractions for end-point adjustments */
 369         i = (pt1.y >> (XY_SHIFT - 7)) & 0x78;
 370         j = (pt2.y >> (XY_SHIFT - 7)) & 0x78;
 371     }
 372
 373     slope = (slope & 0x20) ? 0x100 : SlopeCorrTable[slope];
 374
 375     /* Calc end point correction table */
 376     {
 377         int t0 = slope << 7;
 378         int t1 = ((0x78 - i) | 4) * slope;
 379         int t2 = (j | 4) * slope;
 380
 381         ep_table[0] = 0;
 382         ep_table[8] = slope;
 383         ep_table[1] = ep_table[3] = ((((j - i) & 0x78) | 4) * slope >> 8) & 0x1ff;
 384         ep_table[2] = (t1 >> 8) & 0x1ff;
 385         ep_table[4] = ((((j - i) + 0x80) | 4) * slope >> 8) & 0x1ff;
 386         ep_table[5] = ((t1 + t0) >> 8) & 0x1ff;
 387         ep_table[6] = (t2 >> 8) & 0x1ff;
 388         ep_table[7] = ((t2 + t0) >> 8) & 0x1ff;
 389     }
 390
 391     if( nch == 3 )
 392     {
 393         #define  ICV_PUT_POINT()            \
 394         {                                   \
 395             _cb = tptr[0];                  \
 396             _cb += ((cb - _cb)*a + 127)>> 8;\
 397             _cg = tptr[1];                  \
 398             _cg += ((cg - _cg)*a + 127)>> 8;\
 399             _cr = tptr[2];                  \
 400             _cr += ((cr - _cr)*a + 127)>> 8;\
 401             tptr[0] = (uchar)_cb;           \
 402             tptr[1] = (uchar)_cg;           \
 403             tptr[2] = (uchar)_cr;           \
 404         }
 405         if( ax > ay )
 406         {
 407             ptr += (pt1.x >> XY_SHIFT) * 3;
 408
 409             while( ecount >= 0 )
 410             {
 411                 uchar *tptr = ptr + ((pt1.y >> XY_SHIFT) - 1) * step;
 412
 413                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 414                                        (((ecount >= 2) + 1) & (ecount | 2))];
 415                 int a, dist = (pt1.y >> (XY_SHIFT - 5)) & 31;
 416
 417                 a = (ep_corr * FilterTable[dist + 32] >> 8) & 0xff;
 418                 ICV_PUT_POINT();
 419                 ICV_PUT_POINT();
 420
 421                 tptr += step;
 422                 a = (ep_corr * FilterTable[dist] >> 8) & 0xff;
 423                 ICV_PUT_POINT();
 424                 ICV_PUT_POINT();
 425
 426                 tptr += step;
 427                 a = (ep_corr * FilterTable[63 - dist] >> 8) & 0xff;
 428                 ICV_PUT_POINT();
 429                 ICV_PUT_POINT();
 430
 431                 pt1.y += y_step;
 432                 ptr += 3;
 433                 scount++;
 434                 ecount--;
 435             }
 436         }
 437         else
 438         {
 439             ptr += (pt1.y >> XY_SHIFT) * step;
 440
 441             while( ecount >= 0 )
 442             {
 443                 uchar *tptr = ptr + ((pt1.x >> XY_SHIFT) - 1) * 3;
 444
 445                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 446                                        (((ecount >= 2) + 1) & (ecount | 2))];
 447                 int a, dist = (pt1.x >> (XY_SHIFT - 5)) & 31;
 448
 449                 a = (ep_corr * FilterTable[dist + 32] >> 8) & 0xff;
 450                 ICV_PUT_POINT();
 451                 ICV_PUT_POINT();
 452
 453                 tptr += 3;
 454                 a = (ep_corr * FilterTable[dist] >> 8) & 0xff;
 455                 ICV_PUT_POINT();
 456                 ICV_PUT_POINT();
 457
 458                 tptr += 3;
 459                 a = (ep_corr * FilterTable[63 - dist] >> 8) & 0xff;
 460                 ICV_PUT_POINT();
 461                 ICV_PUT_POINT();
 462
 463                 pt1.x += x_step;
 464                 ptr += step;
 465                 scount++;
 466                 ecount--;
 467             }
 468         }
 469         #undef ICV_PUT_POINT
 470     }
 471     else
 472     {
 473         #define  ICV_PUT_POINT()            \
 474         {                                   \
 475             _cb = tptr[0];                  \
 476             _cb += ((cb - _cb)*a + 127)>> 8;\
 477             tptr[0] = (uchar)_cb;           \
 478         }
 479
 480         if( ax > ay )
 481         {
 482             ptr += (pt1.x >> XY_SHIFT);
 483
 484             while( ecount >= 0 )
 485             {
 486                 uchar *tptr = ptr + ((pt1.y >> XY_SHIFT) - 1) * step;
 487
 488                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 489                                        (((ecount >= 2) + 1) & (ecount | 2))];
 490                 int a, dist = (pt1.y >> (XY_SHIFT - 5)) & 31;
 491
 492                 a = (ep_corr * FilterTable[dist + 32] >> 8) & 0xff;
 493                 ICV_PUT_POINT();
 494                 ICV_PUT_POINT();
 495
 496                 tptr += step;
 497                 a = (ep_corr * FilterTable[dist] >> 8) & 0xff;
 498                 ICV_PUT_POINT();
 499                 ICV_PUT_POINT();
 500
 501                 tptr += step;
 502                 a = (ep_corr * FilterTable[63 - dist] >> 8) & 0xff;
 503                 ICV_PUT_POINT();
 504                 ICV_PUT_POINT();
 505
 506                 pt1.y += y_step;
 507                 ptr++;
 508                 scount++;
 509                 ecount--;
 510             }
 511         }
 512         else
 513         {
 514             ptr += (pt1.y >> XY_SHIFT) * step;
 515
 516             while( ecount >= 0 )
 517             {
 518                 uchar *tptr = ptr + ((pt1.x >> XY_SHIFT) - 1);
 519
 520                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 521                                        (((ecount >= 2) + 1) & (ecount | 2))];
 522                 int a, dist = (pt1.x >> (XY_SHIFT - 5)) & 31;
 523
 524                 a = (ep_corr * FilterTable[dist + 32] >> 8) & 0xff;
 525                 ICV_PUT_POINT();
 526                 ICV_PUT_POINT();
 527
 528                 tptr++;
 529                 a = (ep_corr * FilterTable[dist] >> 8) & 0xff;
 530                 ICV_PUT_POINT();
 531                 ICV_PUT_POINT();
 532
 533                 tptr++;
 534                 a = (ep_corr * FilterTable[63 - dist] >> 8) & 0xff;
 535                 ICV_PUT_POINT();
 536                 ICV_PUT_POINT();
 537
 538                 pt1.x += x_step;
 539                 ptr += step;
 540                 scount++;
 541                 ecount--;
 542             }
 543         }
 544         #undef ICV_PUT_POINT
 545     }
 546 }
 547
 548
 549 static void
 550 Line2( Mat& img, Point pt1, Point pt2, const void* color )
 551 {
 552     int dx, dy;
 553     int ecount;
 554     int ax, ay;
 555     int i, j, x, y;
 556     int x_step, y_step;
 557     int cb = ((uchar*)color)[0];
 558     int cg = ((uchar*)color)[1];
 559     int cr = ((uchar*)color)[2];
 560     int pix_size = (int)img.elemSize();
 561     uchar *ptr = img.data, *tptr;
 562     size_t step = img.step;
 563     Size size = img.size(), sizeScaled(size.width*XY_ONE, size.height*XY_ONE);
 564
 565     //assert( img && (nch == 1 || nch == 3) && img.depth() == CV_8U );
 566
 567     if( !clipLine( sizeScaled, pt1, pt2 ))
 568         return;
 569
 570     dx = pt2.x - pt1.x;
 571     dy = pt2.y - pt1.y;
 572
 573     j = dx < 0 ? -1 : 0;
 574     ax = (dx ^ j) - j;
 575     i = dy < 0 ? -1 : 0;
 576     ay = (dy ^ i) - i;
 577
 578     if( ax > ay )
 579     {
 580         dx = ax;
 581         dy = (dy ^ j) - j;
 582         pt1.x ^= pt2.x & j;
 583         pt2.x ^= pt1.x & j;
 584         pt1.x ^= pt2.x & j;
 585         pt1.y ^= pt2.y & j;
 586         pt2.y ^= pt1.y & j;
 587         pt1.y ^= pt2.y & j;
 588
 589         x_step = XY_ONE;
 590         y_step = (int) (((int64) dy << XY_SHIFT) / (ax | 1));
 591         ecount = (pt2.x - pt1.x) >> XY_SHIFT;
 592     }
 593     else
 594     {
 595         dy = ay;
 596         dx = (dx ^ i) - i;
 597         pt1.x ^= pt2.x & i;
 598         pt2.x ^= pt1.x & i;
 599         pt1.x ^= pt2.x & i;
 600         pt1.y ^= pt2.y & i;
 601         pt2.y ^= pt1.y & i;
 602         pt1.y ^= pt2.y & i;
 603
 604         x_step = (int) (((int64) dx << XY_SHIFT) / (ay | 1));
 605         y_step = XY_ONE;
 606         ecount = (pt2.y - pt1.y) >> XY_SHIFT;
 607     }
 608
 609     pt1.x += (XY_ONE >> 1);
 610     pt1.y += (XY_ONE >> 1);
 611
 612     if( pix_size == 3 )
 613     {
 614         #define  ICV_PUT_POINT(_x,_y)   \
 615         x = (_x); y = (_y);             \
 616         if( 0 <= x && x < size.width && \
 617             0 <= y && y < size.height ) \
 618         {                               \
 619             tptr = ptr + y*step + x*3;  \
 620             tptr[0] = (uchar)cb;        \
 621             tptr[1] = (uchar)cg;        \
 622             tptr[2] = (uchar)cr;        \
 623         }
 624
 625         ICV_PUT_POINT((pt2.x + (XY_ONE >> 1)) >> XY_SHIFT,
 626                       (pt2.y + (XY_ONE >> 1)) >> XY_SHIFT);
 627
 628         if( ax > ay )
 629         {
 630             pt1.x >>= XY_SHIFT;
 631
 632             while( ecount >= 0 )
 633             {
 634                 ICV_PUT_POINT(pt1.x, pt1.y >> XY_SHIFT);
 635                 pt1.x++;
 636                 pt1.y += y_step;
 637                 ecount--;
 638             }
 639         }
 640         else
 641         {
 642             pt1.y >>= XY_SHIFT;
 643
 644             while( ecount >= 0 )
 645             {
 646                 ICV_PUT_POINT(pt1.x >> XY_SHIFT, pt1.y);
 647                 pt1.x += x_step;
 648                 pt1.y++;
 649                 ecount--;
 650             }
 651         }
 652
 653         #undef ICV_PUT_POINT
 654     }
 655     else if( pix_size == 1 )
 656     {
 657         #define  ICV_PUT_POINT(_x,_y) \
 658         x = (_x); y = (_y);           \
 659         if( 0 <= x && x < size.width && \
 660             0 <= y && y < size.height ) \
 661         {                           \
 662             tptr = ptr + y*step + x;\
 663             tptr[0] = (uchar)cb;    \
 664         }
 665
 666         ICV_PUT_POINT((pt2.x + (XY_ONE >> 1)) >> XY_SHIFT,
 667                       (pt2.y + (XY_ONE >> 1)) >> XY_SHIFT);
 668
 669         if( ax > ay )
 670         {
 671             pt1.x >>= XY_SHIFT;
 672
 673             while( ecount >= 0 )
 674             {
 675                 ICV_PUT_POINT(pt1.x, pt1.y >> XY_SHIFT);
 676                 pt1.x++;
 677                 pt1.y += y_step;
 678                 ecount--;
 679             }
 680         }
 681         else
 682         {
 683             pt1.y >>= XY_SHIFT;
 684
 685             while( ecount >= 0 )
 686             {
 687                 ICV_PUT_POINT(pt1.x >> XY_SHIFT, pt1.y);
 688                 pt1.x += x_step;
 689                 pt1.y++;
 690                 ecount--;
 691             }
 692         }
 693
 694         #undef ICV_PUT_POINT
 695     }
 696     else
 697     {
 698         #define  ICV_PUT_POINT(_x,_y)   \
 699         x = (_x); y = (_y);             \
 700         if( 0 <= x && x < size.width && \
 701             0 <= y && y < size.height ) \
 702         {                               \
 703             tptr = ptr + y*step + x*pix_size;\
 704             for( j = 0; j < pix_size; j++ ) \
 705                 tptr[j] = ((uchar*)color)[j]; \
 706         }
 707
 708         ICV_PUT_POINT((pt2.x + (XY_ONE >> 1)) >> XY_SHIFT,
 709                       (pt2.y + (XY_ONE >> 1)) >> XY_SHIFT);
 710
 711         if( ax > ay )
 712         {
 713             pt1.x >>= XY_SHIFT;
 714
 715             while( ecount >= 0 )
 716             {
 717                 ICV_PUT_POINT(pt1.x, pt1.y >> XY_SHIFT);
 718                 pt1.x++;
 719                 pt1.y += y_step;
 720                 ecount--;
 721             }
 722         }
 723         else
 724         {
 725             pt1.y >>= XY_SHIFT;
 726
 727             while( ecount >= 0 )
 728             {
 729                 ICV_PUT_POINT(pt1.x >> XY_SHIFT, pt1.y);
 730                 pt1.x += x_step;
 731                 pt1.y++;
 732                 ecount--;
 733             }
 734         }
 735
 736         #undef ICV_PUT_POINT
 737     }
 738 }
 739
 740
 741 /****************************************************************************************\
 742 *                   Antialiazed Elliptic Arcs via Antialiazed Lines                      *
 743 \****************************************************************************************/
 744
 745 static const float SinTable[] =
 746     { 0.0000000f, 0.0174524f, 0.0348995f, 0.0523360f, 0.0697565f, 0.0871557f,
 747     0.1045285f, 0.1218693f, 0.1391731f, 0.1564345f, 0.1736482f, 0.1908090f,
 748     0.2079117f, 0.2249511f, 0.2419219f, 0.2588190f, 0.2756374f, 0.2923717f,
 749     0.3090170f, 0.3255682f, 0.3420201f, 0.3583679f, 0.3746066f, 0.3907311f,
 750     0.4067366f, 0.4226183f, 0.4383711f, 0.4539905f, 0.4694716f, 0.4848096f,
 751     0.5000000f, 0.5150381f, 0.5299193f, 0.5446390f, 0.5591929f, 0.5735764f,
 752     0.5877853f, 0.6018150f, 0.6156615f, 0.6293204f, 0.6427876f, 0.6560590f,
 753     0.6691306f, 0.6819984f, 0.6946584f, 0.7071068f, 0.7193398f, 0.7313537f,
 754     0.7431448f, 0.7547096f, 0.7660444f, 0.7771460f, 0.7880108f, 0.7986355f,
 755     0.8090170f, 0.8191520f, 0.8290376f, 0.8386706f, 0.8480481f, 0.8571673f,
 756     0.8660254f, 0.8746197f, 0.8829476f, 0.8910065f, 0.8987940f, 0.9063078f,
 757     0.9135455f, 0.9205049f, 0.9271839f, 0.9335804f, 0.9396926f, 0.9455186f,
 758     0.9510565f, 0.9563048f, 0.9612617f, 0.9659258f, 0.9702957f, 0.9743701f,
 759     0.9781476f, 0.9816272f, 0.9848078f, 0.9876883f, 0.9902681f, 0.9925462f,
 760     0.9945219f, 0.9961947f, 0.9975641f, 0.9986295f, 0.9993908f, 0.9998477f,
 761     1.0000000f, 0.9998477f, 0.9993908f, 0.9986295f, 0.9975641f, 0.9961947f,
 762     0.9945219f, 0.9925462f, 0.9902681f, 0.9876883f, 0.9848078f, 0.9816272f,
 763     0.9781476f, 0.9743701f, 0.9702957f, 0.9659258f, 0.9612617f, 0.9563048f,
 764     0.9510565f, 0.9455186f, 0.9396926f, 0.9335804f, 0.9271839f, 0.9205049f,
 765     0.9135455f, 0.9063078f, 0.8987940f, 0.8910065f, 0.8829476f, 0.8746197f,
 766     0.8660254f, 0.8571673f, 0.8480481f, 0.8386706f, 0.8290376f, 0.8191520f,
 767     0.8090170f, 0.7986355f, 0.7880108f, 0.7771460f, 0.7660444f, 0.7547096f,
 768     0.7431448f, 0.7313537f, 0.7193398f, 0.7071068f, 0.6946584f, 0.6819984f,
 769     0.6691306f, 0.6560590f, 0.6427876f, 0.6293204f, 0.6156615f, 0.6018150f,
 770     0.5877853f, 0.5735764f, 0.5591929f, 0.5446390f, 0.5299193f, 0.5150381f,
 771     0.5000000f, 0.4848096f, 0.4694716f, 0.4539905f, 0.4383711f, 0.4226183f,
 772     0.4067366f, 0.3907311f, 0.3746066f, 0.3583679f, 0.3420201f, 0.3255682f,
 773     0.3090170f, 0.2923717f, 0.2756374f, 0.2588190f, 0.2419219f, 0.2249511f,
 774     0.2079117f, 0.1908090f, 0.1736482f, 0.1564345f, 0.1391731f, 0.1218693f,
 775     0.1045285f, 0.0871557f, 0.0697565f, 0.0523360f, 0.0348995f, 0.0174524f,
 776     0.0000000f, -0.0174524f, -0.0348995f, -0.0523360f, -0.0697565f, -0.0871557f,
 777     -0.1045285f, -0.1218693f, -0.1391731f, -0.1564345f, -0.1736482f, -0.1908090f,
 778     -0.2079117f, -0.2249511f, -0.2419219f, -0.2588190f, -0.2756374f, -0.2923717f,
 779     -0.3090170f, -0.3255682f, -0.3420201f, -0.3583679f, -0.3746066f, -0.3907311f,
 780     -0.4067366f, -0.4226183f, -0.4383711f, -0.4539905f, -0.4694716f, -0.4848096f,
 781     -0.5000000f, -0.5150381f, -0.5299193f, -0.5446390f, -0.5591929f, -0.5735764f,
 782     -0.5877853f, -0.6018150f, -0.6156615f, -0.6293204f, -0.6427876f, -0.6560590f,
 783     -0.6691306f, -0.6819984f, -0.6946584f, -0.7071068f, -0.7193398f, -0.7313537f,
 784     -0.7431448f, -0.7547096f, -0.7660444f, -0.7771460f, -0.7880108f, -0.7986355f,
 785     -0.8090170f, -0.8191520f, -0.8290376f, -0.8386706f, -0.8480481f, -0.8571673f,
 786     -0.8660254f, -0.8746197f, -0.8829476f, -0.8910065f, -0.8987940f, -0.9063078f,
 787     -0.9135455f, -0.9205049f, -0.9271839f, -0.9335804f, -0.9396926f, -0.9455186f,
 788     -0.9510565f, -0.9563048f, -0.9612617f, -0.9659258f, -0.9702957f, -0.9743701f,
 789     -0.9781476f, -0.9816272f, -0.9848078f, -0.9876883f, -0.9902681f, -0.9925462f,
 790     -0.9945219f, -0.9961947f, -0.9975641f, -0.9986295f, -0.9993908f, -0.9998477f,
 791     -1.0000000f, -0.9998477f, -0.9993908f, -0.9986295f, -0.9975641f, -0.9961947f,
 792     -0.9945219f, -0.9925462f, -0.9902681f, -0.9876883f, -0.9848078f, -0.9816272f,
 793     -0.9781476f, -0.9743701f, -0.9702957f, -0.9659258f, -0.9612617f, -0.9563048f,
 794     -0.9510565f, -0.9455186f, -0.9396926f, -0.9335804f, -0.9271839f, -0.9205049f,
 795     -0.9135455f, -0.9063078f, -0.8987940f, -0.8910065f, -0.8829476f, -0.8746197f,
 796     -0.8660254f, -0.8571673f, -0.8480481f, -0.8386706f, -0.8290376f, -0.8191520f,
 797     -0.8090170f, -0.7986355f, -0.7880108f, -0.7771460f, -0.7660444f, -0.7547096f,
 798     -0.7431448f, -0.7313537f, -0.7193398f, -0.7071068f, -0.6946584f, -0.6819984f,
 799     -0.6691306f, -0.6560590f, -0.6427876f, -0.6293204f, -0.6156615f, -0.6018150f,
 800     -0.5877853f, -0.5735764f, -0.5591929f, -0.5446390f, -0.5299193f, -0.5150381f,
 801     -0.5000000f, -0.4848096f, -0.4694716f, -0.4539905f, -0.4383711f, -0.4226183f,
 802     -0.4067366f, -0.3907311f, -0.3746066f, -0.3583679f, -0.3420201f, -0.3255682f,
 803     -0.3090170f, -0.2923717f, -0.2756374f, -0.2588190f, -0.2419219f, -0.2249511f,
 804     -0.2079117f, -0.1908090f, -0.1736482f, -0.1564345f, -0.1391731f, -0.1218693f,
 805     -0.1045285f, -0.0871557f, -0.0697565f, -0.0523360f, -0.0348995f, -0.0174524f,
 806     -0.0000000f, 0.0174524f, 0.0348995f, 0.0523360f, 0.0697565f, 0.0871557f,
 807     0.1045285f, 0.1218693f, 0.1391731f, 0.1564345f, 0.1736482f, 0.1908090f,
 808     0.2079117f, 0.2249511f, 0.2419219f, 0.2588190f, 0.2756374f, 0.2923717f,
 809     0.3090170f, 0.3255682f, 0.3420201f, 0.3583679f, 0.3746066f, 0.3907311f,
 810     0.4067366f, 0.4226183f, 0.4383711f, 0.4539905f, 0.4694716f, 0.4848096f,
 811     0.5000000f, 0.5150381f, 0.5299193f, 0.5446390f, 0.5591929f, 0.5735764f,
 812     0.5877853f, 0.6018150f, 0.6156615f, 0.6293204f, 0.6427876f, 0.6560590f,
 813     0.6691306f, 0.6819984f, 0.6946584f, 0.7071068f, 0.7193398f, 0.7313537f,
 814     0.7431448f, 0.7547096f, 0.7660444f, 0.7771460f, 0.7880108f, 0.7986355f,
 815     0.8090170f, 0.8191520f, 0.8290376f, 0.8386706f, 0.8480481f, 0.8571673f,
 816     0.8660254f, 0.8746197f, 0.8829476f, 0.8910065f, 0.8987940f, 0.9063078f,
 817     0.9135455f, 0.9205049f, 0.9271839f, 0.9335804f, 0.9396926f, 0.9455186f,
 818     0.9510565f, 0.9563048f, 0.9612617f, 0.9659258f, 0.9702957f, 0.9743701f,
 819     0.9781476f, 0.9816272f, 0.9848078f, 0.9876883f, 0.9902681f, 0.9925462f,
 820     0.9945219f, 0.9961947f, 0.9975641f, 0.9986295f, 0.9993908f, 0.9998477f,
 821     1.0000000f
 822 };
 823
 824
 825 static void
 826 sincos( int angle, float& cosval, float& sinval )
 827 {
 828     angle += (angle < 0 ? 360 : 0);
 829     sinval = SinTable[angle];
 830     cosval = SinTable[450 - angle];
 831 }
 832
 833 /*
 834    constructs polygon that represents elliptic arc.
 835 */
 836 void ellipse2Poly( Point center, Size axes, int angle,
 837                    int arc_start, int arc_end,
 838                    int delta, vector<Point>& pts )
 839 {
 840     float alpha, beta;
 841     double size_a = axes.width, size_b = axes.height;
 842     double cx = center.x, cy = center.y;
 843     Point prevPt(INT_MIN,INT_MIN);
 844     int i;
 845
 846     while( angle < 0 )
 847         angle += 360;
 848     while( angle > 360 )
 849         angle -= 360;
 850
 851     if( arc_start > arc_end )
 852     {
 853         i = arc_start;
 854         arc_start = arc_end;
 855         arc_end = i;
 856     }
 857     while( arc_start < 0 )
 858     {
 859         arc_start += 360;
 860         arc_end += 360;
 861     }
 862     while( arc_end > 360 )
 863     {
 864         arc_end -= 360;
 865         arc_start -= 360;
 866     }
 867     if( arc_end - arc_start > 360 )
 868     {
 869         arc_start = 0;
 870         arc_end = 360;
 871     }
 872     sincos( angle, alpha, beta );
 873     pts.resize(0);
 874
 875     for( i = arc_start; i < arc_end + delta; i += delta )
 876     {
 877         double x, y;
 878         angle = i;
 879         if( angle > arc_end )
 880             angle = arc_end;
 881         if( angle < 0 )
 882             angle += 360;
 883
 884         x = size_a * SinTable[450-angle];
 885         y = size_b * SinTable[angle];
 886         Point pt;
 887         pt.x = cvRound( cx + x * alpha - y * beta );
 888         pt.y = cvRound( cy + x * beta + y * alpha );
 889         if( pt != prevPt )
 890             pts.push_back(pt);
 891     }
 892
 893     if( pts.size() < 2 )
 894         pts.push_back(pts[0]);
 895 }
 896
 897
 898 static void
 899 EllipseEx( Mat& img, Point center, Size axes,
 900            int angle, int arc_start, int arc_end,
 901            const void* color, int thickness, int line_type )
 902 {
 903     axes.width = std::abs(axes.width), axes.height = std::abs(axes.height);
 904     int delta = (std::max(axes.width,axes.height)+(XY_ONE>>1))>>XY_SHIFT;
 905     delta = delta < 3 ? 90 : delta < 10 ? 30 : delta < 15 ? 18 : 5;
 906
 907     vector<Point> v;
 908     ellipse2Poly( center, axes, angle, arc_start, arc_end, delta, v );
 909
 910     if( thickness >= 0 )
 911         PolyLine( img, &v[0], (int)v.size(), false, color, thickness, line_type, XY_SHIFT );
 912     else if( arc_end - arc_start >= 360 )
 913         FillConvexPoly( img, &v[0], (int)v.size(), color, line_type, XY_SHIFT );
 914     else
 915     {
 916         v.push_back(center);
 917         vector<PolyEdge> edges;
 918         CollectPolyEdges( img,  &v[0], (int)v.size(), edges, color, line_type, XY_SHIFT );
 919         FillEdgeCollection( img, edges, color );
 920     }
 921 }
 922
 923
 924 /****************************************************************************************\
 925 *                                Polygons filling                                        *
 926 \****************************************************************************************/
 927
 928 /* helper macros: filling horizontal row */
 929 #define ICV_HLINE( ptr, xl, xr, color, pix_size )            \
 930 {                                                            \
 931     uchar* hline_ptr = (uchar*)(ptr) + (xl)*(pix_size);      \
 932     uchar* hline_max_ptr = (uchar*)(ptr) + (xr)*(pix_size);  \
 933                                                              \
 934     for( ; hline_ptr <= hline_max_ptr; hline_ptr += (pix_size))\
 935     {                                                        \
 936         int hline_j;                                         \
 937         for( hline_j = 0; hline_j < (pix_size); hline_j++ )  \
 938         {                                                    \
 939             hline_ptr[hline_j] = ((uchar*)color)[hline_j];   \
 940         }                                                    \
 941     }                                                        \
 942 }
 943
 944
 945 /* filling convex polygon. v - array of vertices, ntps - number of points */
 946 static void
 947 FillConvexPoly( Mat& img, const Point* v, int npts, const void* color, int line_type, int shift )
 948 {
 949     struct
 950     {
 951         int idx, di;
 952         int x, dx, ye;
 953     }
 954     edge[2];
 955
 956     int delta = shift ? 1 << (shift - 1) : 0;
 957     int i, y, imin = 0, left = 0, right = 1, x1, x2;
 958     int edges = npts;
 959     int xmin, xmax, ymin, ymax;
 960     uchar* ptr = img.data;
 961     Size size = img.size();
 962     int pix_size = (int)img.elemSize();
 963     Point p0;
 964     int delta1, delta2;
 965
 966     if( line_type < CV_AA )
 967         delta1 = delta2 = XY_ONE >> 1;
 968     else
 969         delta1 = XY_ONE - 1, delta2 = 0;
 970
 971     p0 = v[npts - 1];
 972     p0.x <<= XY_SHIFT - shift;
 973     p0.y <<= XY_SHIFT - shift;
 974
 975     assert( 0 <= shift && shift <= XY_SHIFT );
 976     xmin = xmax = v[0].x;
 977     ymin = ymax = v[0].y;
 978
 979     for( i = 0; i < npts; i++ )
 980     {
 981         Point p = v[i];
 982         if( p.y < ymin )
 983         {
 984             ymin = p.y;
 985             imin = i;
 986         }
 987
 988         ymax = std::max( ymax, p.y );
 989         xmax = std::max( xmax, p.x );
 990         xmin = MIN( xmin, p.x );
 991
 992         p.x <<= XY_SHIFT - shift;
 993         p.y <<= XY_SHIFT - shift;
 994
 995         if( line_type <= 8 )
 996         {
 997             if( shift == 0 )
 998             {
 999                 Point pt0, pt1;
1000                 pt0.x = p0.x >> XY_SHIFT;
1001                 pt0.y = p0.y >> XY_SHIFT;
1002                 pt1.x = p.x >> XY_SHIFT;
1003                 pt1.y = p.y >> XY_SHIFT;
1004                 Line( img, pt0, pt1, color, line_type );
1005             }
1006             else
1007                 Line2( img, p0, p, color );
1008         }
1009         else
1010             LineAA( img, p0, p, color );
1011         p0 = p;
1012     }
1013
1014     xmin = (xmin + delta) >> shift;
1015     xmax = (xmax + delta) >> shift;
1016     ymin = (ymin + delta) >> shift;
1017     ymax = (ymax + delta) >> shift;
1018
1019     if( npts < 3 || xmax < 0 || ymax < 0 || xmin >= size.width || ymin >= size.height )
1020         return;
1021
1022     ymax = MIN( ymax, size.height - 1 );
1023     edge[0].idx = edge[1].idx = imin;
1024
1025     edge[0].ye = edge[1].ye = y = ymin;
1026     edge[0].di = 1;
1027     edge[1].di = npts - 1;
1028
1029     ptr += img.step*y;
1030
1031     do
1032     {
1033         if( line_type < CV_AA || y < ymax || y == ymin )
1034         {
1035             for( i = 0; i < 2; i++ )
1036             {
1037                 if( y >= edge[i].ye )
1038                 {
1039                     int idx = edge[i].idx, di = edge[i].di;
1040                     int xs = 0, xe, ye, ty = 0;
1041
1042                     for(;;)
1043                     {
1044                         ty = (v[idx].y + delta) >> shift;
1045                         if( ty > y || edges == 0 )
1046                             break;
1047                         xs = v[idx].x;
1048                         idx += di;
1049                         idx -= ((idx < npts) - 1) & npts;   /* idx -= idx >= npts ? npts : 0 */
1050                         edges--;
1051                     }
1052
1053                     ye = ty;
1054                     xs <<= XY_SHIFT - shift;
1055                     xe = v[idx].x << (XY_SHIFT - shift);
1056
1057                     /* no more edges */
1058                     if( y >= ye )
1059                         return;
1060
1061                     edge[i].ye = ye;
1062                     edge[i].dx = ((xe - xs)*2 + (ye - y)) / (2 * (ye - y));
1063                     edge[i].x = xs;
1064                     edge[i].idx = idx;
1065                 }
1066             }
1067         }
1068
1069         if( edge[left].x > edge[right].x )
1070         {
1071             left ^= 1;
1072             right ^= 1;
1073         }
1074
1075         x1 = edge[left].x;
1076         x2 = edge[right].x;
1077
1078         if( y >= 0 )
1079         {
1080             int xx1 = (x1 + delta1) >> XY_SHIFT;
1081             int xx2 = (x2 + delta2) >> XY_SHIFT;
1082
1083             if( xx2 >= 0 && xx1 < size.width )
1084             {
1085                 if( xx1 < 0 )
1086                     xx1 = 0;
1087                 if( xx2 >= size.width )
1088                     xx2 = size.width - 1;
1089                 ICV_HLINE( ptr, xx1, xx2, color, pix_size );
1090             }
1091         }
1092
1093         x1 += edge[left].dx;
1094         x2 += edge[right].dx;
1095
1096         edge[left].x = x1;
1097         edge[right].x = x2;
1098         ptr += img.step;
1099     }
1100     while( ++y <= ymax );
1101 }
1102
1103
1104 /******** Arbitrary polygon **********/
1105
1106 static void
1107 CollectPolyEdges( Mat& img, const Point* v, int count, vector<PolyEdge>& edges,
1108                   const void* color, int line_type, int shift, Point offset )
1109 {
1110     int i, delta = offset.y + (shift ? 1 << (shift - 1) : 0);
1111     Point pt0 = v[count-1], pt1;
1112     pt0.x = (pt0.x + offset.x) << (XY_SHIFT - shift);
1113     pt0.y = (pt0.y + delta) >> shift;
1114
1115     edges.reserve( edges.size() + count );
1116
1117     for( i = 0; i < count; i++, pt0 = pt1 )
1118     {
1119         Point t0, t1;
1120         PolyEdge edge;
1121
1122         pt1 = v[i];
1123         pt1.x = (pt1.x + offset.x) << (XY_SHIFT - shift);
1124         pt1.y = (pt1.y + delta) >> shift;
1125
1126         if( line_type < CV_AA )
1127         {
1128             t0.y = pt0.y; t1.y = pt1.y;
1129             t0.x = (pt0.x + (XY_ONE >> 1)) >> XY_SHIFT;
1130             t1.x = (pt1.x + (XY_ONE >> 1)) >> XY_SHIFT;
1131             Line( img, t0, t1, color, line_type );
1132         }
1133         else
1134         {
1135             t0.x = pt0.x; t1.x = pt1.x;
1136             t0.y = pt0.y << XY_SHIFT;
1137             t1.y = pt1.y << XY_SHIFT;
1138             LineAA( img, t0, t1, color );
1139         }
1140
1141         if( pt0.y == pt1.y )
1142             continue;
1143
1144         if( pt0.y < pt1.y )
1145         {
1146             edge.y0 = pt0.y;
1147             edge.y1 = pt1.y;
1148             edge.x = pt0.x;
1149         }
1150         else
1151         {
1152             edge.y0 = pt1.y;
1153             edge.y1 = pt0.y;
1154             edge.x = pt1.x;
1155         }
1156         edge.dx = (pt1.x - pt0.x) / (pt1.y - pt0.y);
1157         edges.push_back(edge);
1158     }
1159 }
1160
1161 struct CmpEdges
1162 {
1163     bool operator ()(const PolyEdge& e1, const PolyEdge& e2)
1164     {
1165         return e1.y0 - e2.y0 ? e1.y0 < e2.y0 :
1166             e1.x - e2.x ? e1.x < e2.x : e1.dx < e2.dx;
1167     }
1168 };
1169
1170 /**************** helper macros and functions for sequence/contour processing ***********/
1171
1172 static void
1173 FillEdgeCollection( Mat& img, vector<PolyEdge>& edges, const void* color )
1174 {
1175     PolyEdge tmp;
1176     int i, y, total = (int)edges.size();
1177     Size size = img.size();
1178     PolyEdge* e;
1179     int y_max = INT_MIN, x_max = INT_MIN, y_min = INT_MAX, x_min = INT_MAX;
1180     int pix_size = (int)img.elemSize();
1181
1182     if( total < 2 )
1183         return;
1184
1185     for( i = 0; i < total; i++ )
1186     {
1187         PolyEdge& e1 = edges[i];
1188         assert( e1.y0 < e1.y1 );
1189         y_min = std::min( y_min, e1.y0 );
1190         y_max = std::max( y_max, e1.y1 );
1191         x_min = std::min( x_min, e1.x );
1192         x_max = std::max( x_max, e1.x );
1193     }
1194
1195     if( y_max < 0 || y_min >= size.height || x_max < 0 || x_min >= (size.width<<XY_SHIFT) )
1196         return;
1197
1198     std::sort( edges.begin(), edges.end(), CmpEdges() );
1199
1200     // start drawing
1201     tmp.y0 = INT_MAX;
1202     edges.push_back(tmp); // after this point we do not add
1203                           // any elements to edges, thus we can use pointers
1204     i = 0;
1205     tmp.next = 0;
1206     e = &edges[i];
1207     y_max = MIN( y_max, size.height );
1208
1209     for( y = e->y0; y < y_max; y++ )
1210     {
1211         PolyEdge *last, *prelast, *keep_prelast;
1212         int sort_flag = 0;
1213         int draw = 0;
1214         int clipline = y < 0;
1215
1216         prelast = &tmp;
1217         last = tmp.next;
1218         while( last || e->y0 == y )
1219         {
1220             if( last && last->y1 == y )
1221             {
1222                 // exclude edge if y reachs its lower point
1223                 prelast->next = last->next;
1224                 last = last->next;
1225                 continue;
1226             }
1227             keep_prelast = prelast;
1228             if( last && (e->y0 > y || last->x < e->x) )
1229             {
1230                 // go to the next edge in active list
1231                 prelast = last;
1232                 last = last->next;
1233             }
1234             else if( i < total )
1235             {
1236                 // insert new edge into active list if y reachs its upper point
1237                 prelast->next = e;
1238                 e->next = last;
1239                 prelast = e;
1240                 e = &edges[++i];
1241             }
1242             else
1243                 break;
1244
1245             if( draw )
1246             {
1247                 if( !clipline )
1248                 {
1249                     // convert x's from fixed-point to image coordinates
1250                     uchar *timg = img.data + y * img.step;
1251                     int x1 = keep_prelast->x;
1252                     int x2 = prelast->x;
1253
1254                     if( x1 > x2 )
1255                     {
1256                         int t = x1;
1257
1258                         x1 = x2;
1259                         x2 = t;
1260                     }
1261
1262                     x1 = (x1 + XY_ONE - 1) >> XY_SHIFT;
1263                     x2 = x2 >> XY_SHIFT;
1264
1265                     // clip and draw the line
1266                     if( x1 < size.width && x2 >= 0 )
1267                     {
1268                         if( x1 < 0 )
1269                             x1 = 0;
1270                         if( x2 >= size.width )
1271                             x2 = size.width - 1;
1272                         ICV_HLINE( timg, x1, x2, color, pix_size );
1273                     }
1274                 }
1275                 keep_prelast->x += keep_prelast->dx;
1276                 prelast->x += prelast->dx;
1277             }
1278             draw ^= 1;
1279         }
1280
1281         // sort edges (using bubble sort)
1282         keep_prelast = 0;
1283
1284         do
1285         {
1286             prelast = &tmp;
1287             last = tmp.next;
1288
1289             while( last != keep_prelast && last->next != 0 )
1290             {
1291                 PolyEdge *te = last->next;
1292
1293                 // swap edges
1294                 if( last->x > te->x )
1295                 {
1296                     prelast->next = te;
1297                     last->next = te->next;
1298                     te->next = last;
1299                     prelast = te;
1300                     sort_flag = 1;
1301                 }
1302                 else
1303                 {
1304                     prelast = last;
1305                     last = te;
1306                 }
1307             }
1308             keep_prelast = prelast;
1309         }
1310         while( sort_flag && keep_prelast != tmp.next && keep_prelast != &tmp );
1311     }
1312 }
1313
1314
1315 /* draws simple or filled circle */
1316 static void
1317 Circle( Mat& img, Point center, int radius, const void* color, int fill )
1318 {
1319     Size size = img.size();
1320     size_t step = img.step;
1321     int pix_size = (int)img.elemSize();
1322     uchar* ptr = img.data;
1323     int err = 0, dx = radius, dy = 0, plus = 1, minus = (radius << 1) - 1;
1324     int inside = center.x >= radius && center.x < size.width - radius &&
1325         center.y >= radius && center.y < size.height - radius;
1326
1327     #define ICV_PUT_POINT( ptr, x )     \
1328         memcpy( ptr + (x)*pix_size, color, pix_size );
1329
1330     while( dx >= dy )
1331     {
1332         int mask;
1333         int y11 = center.y - dy, y12 = center.y + dy, y21 = center.y - dx, y22 = center.y + dx;
1334         int x11 = center.x - dx, x12 = center.x + dx, x21 = center.x - dy, x22 = center.x + dy;
1335
1336         if( inside )
1337         {
1338             uchar *tptr0 = ptr + y11 * step;
1339             uchar *tptr1 = ptr + y12 * step;
1340
1341             if( !fill )
1342             {
1343                 ICV_PUT_POINT( tptr0, x11 );
1344                 ICV_PUT_POINT( tptr1, x11 );
1345                 ICV_PUT_POINT( tptr0, x12 );
1346                 ICV_PUT_POINT( tptr1, x12 );
1347             }
1348             else
1349             {
1350                 ICV_HLINE( tptr0, x11, x12, color, pix_size );
1351                 ICV_HLINE( tptr1, x11, x12, color, pix_size );
1352             }
1353
1354             tptr0 = ptr + y21 * step;
1355             tptr1 = ptr + y22 * step;
1356
1357             if( !fill )
1358             {
1359                 ICV_PUT_POINT( tptr0, x21 );
1360                 ICV_PUT_POINT( tptr1, x21 );
1361                 ICV_PUT_POINT( tptr0, x22 );
1362                 ICV_PUT_POINT( tptr1, x22 );
1363             }
1364             else
1365             {
1366                 ICV_HLINE( tptr0, x21, x22, color, pix_size );
1367                 ICV_HLINE( tptr1, x21, x22, color, pix_size );
1368             }
1369         }
1370         else if( x11 < size.width && x12 >= 0 && y21 < size.height && y22 >= 0 )
1371         {
1372             if( fill )
1373             {
1374                 x11 = std::max( x11, 0 );
1375                 x12 = MIN( x12, size.width - 1 );
1376             }
1377
1378             if( (unsigned)y11 < (unsigned)size.height )
1379             {
1380                 uchar *tptr = ptr + y11 * step;
1381
1382                 if( !fill )
1383                 {
1384                     if( x11 >= 0 )
1385                         ICV_PUT_POINT( tptr, x11 );
1386                     if( x12 < size.width )
1387                         ICV_PUT_POINT( tptr, x12 );
1388                 }
1389                 else
1390                     ICV_HLINE( tptr, x11, x12, color, pix_size );
1391             }
1392
1393             if( (unsigned)y12 < (unsigned)size.height )
1394             {
1395                 uchar *tptr = ptr + y12 * step;
1396
1397                 if( !fill )
1398                 {
1399                     if( x11 >= 0 )
1400                         ICV_PUT_POINT( tptr, x11 );
1401                     if( x12 < size.width )
1402                         ICV_PUT_POINT( tptr, x12 );
1403                 }
1404                 else
1405                     ICV_HLINE( tptr, x11, x12, color, pix_size );
1406             }
1407
1408             if( x21 < size.width && x22 >= 0 )
1409             {
1410                 if( fill )
1411                 {
1412                     x21 = std::max( x21, 0 );
1413                     x22 = MIN( x22, size.width - 1 );
1414                 }
1415
1416                 if( (unsigned)y21 < (unsigned)size.height )
1417                 {
1418                     uchar *tptr = ptr + y21 * step;
1419
1420                     if( !fill )
1421                     {
1422                         if( x21 >= 0 )
1423                             ICV_PUT_POINT( tptr, x21 );
1424                         if( x22 < size.width )
1425                             ICV_PUT_POINT( tptr, x22 );
1426                     }
1427                     else
1428                         ICV_HLINE( tptr, x21, x22, color, pix_size );
1429                 }
1430
1431                 if( (unsigned)y22 < (unsigned)size.height )
1432                 {
1433                     uchar *tptr = ptr + y22 * step;
1434
1435                     if( !fill )
1436                     {
1437                         if( x21 >= 0 )
1438                             ICV_PUT_POINT( tptr, x21 );
1439                         if( x22 < size.width )
1440                             ICV_PUT_POINT( tptr, x22 );
1441                     }
1442                     else
1443                         ICV_HLINE( tptr, x21, x22, color, pix_size );
1444                 }
1445             }
1446         }
1447         dy++;
1448         err += plus;
1449         plus += 2;
1450
1451         mask = (err <= 0) - 1;
1452
1453         err -= minus & mask;
1454         dx += mask;
1455         minus -= mask & 2;
1456     }
1457
1458     #undef  ICV_PUT_POINT
1459 }
1460
1461
1462 static void
1463 ThickLine( Mat& img, Point p0, Point p1, const void* color,
1464            int thickness, int line_type, int flags, int shift )
1465 {
1466     static const double INV_XY_ONE = 1./XY_ONE;
1467
1468     p0.x <<= XY_SHIFT - shift;
1469     p0.y <<= XY_SHIFT - shift;
1470     p1.x <<= XY_SHIFT - shift;
1471     p1.y <<= XY_SHIFT - shift;
1472
1473     if( thickness <= 1 )
1474     {
1475         if( line_type < CV_AA )
1476         {
1477             if( line_type == 1 || line_type == 4 || shift == 0 )
1478             {
1479                 p0.x = (p0.x + (XY_ONE>>1)) >> XY_SHIFT;
1480                 p0.y = (p0.y + (XY_ONE>>1)) >> XY_SHIFT;
1481                 p1.x = (p1.x + (XY_ONE>>1)) >> XY_SHIFT;
1482                 p1.y = (p1.y + (XY_ONE>>1)) >> XY_SHIFT;
1483                 Line( img, p0, p1, color, line_type );
1484             }
1485             else
1486                 Line2( img, p0, p1, color );
1487         }
1488         else
1489             LineAA( img, p0, p1, color );
1490     }
1491     else
1492     {
1493         Point pt[4], dp = Point(0,0);
1494         double dx = (p0.x - p1.x)*INV_XY_ONE, dy = (p1.y - p0.y)*INV_XY_ONE;
1495         double r = dx * dx + dy * dy;
1496         int i, oddThickness = thickness & 1;
1497         thickness <<= XY_SHIFT - 1;
1498
1499         if( fabs(r) > DBL_EPSILON )
1500         {
1501             r = (thickness + oddThickness*XY_ONE*0.5)/std::sqrt(r);
1502             dp.x = cvRound( dy * r );
1503             dp.y = cvRound( dx * r );
1504
1505             pt[0].x = p0.x + dp.x;
1506             pt[0].y = p0.y + dp.y;
1507             pt[1].x = p0.x - dp.x;
1508             pt[1].y = p0.y - dp.y;
1509             pt[2].x = p1.x - dp.x;
1510             pt[2].y = p1.y - dp.y;
1511             pt[3].x = p1.x + dp.x;
1512             pt[3].y = p1.y + dp.y;
1513
1514             FillConvexPoly( img, pt, 4, color, line_type, XY_SHIFT );
1515         }
1516
1517         for( i = 0; i < 2; i++ )
1518         {
1519             if( flags & (i+1) )
1520             {
1521                 if( line_type < CV_AA )
1522                 {
1523                     Point center;
1524                     center.x = (p0.x + (XY_ONE>>1)) >> XY_SHIFT;
1525                     center.y = (p0.y + (XY_ONE>>1)) >> XY_SHIFT;
1526                     Circle( img, center, (thickness + (XY_ONE>>1)) >> XY_SHIFT, color, 1 );
1527                 }
1528                 else
1529                 {
1530                     EllipseEx( img, p0, cvSize(thickness, thickness),
1531                                0, 0, 360, color, -1, line_type );
1532                 }
1533             }
1534             p0 = p1;
1535         }
1536     }
1537 }
1538
1539
1540 static void
1541 PolyLine( Mat& img, const Point* v, int count, bool is_closed,
1542           const void* color, int thickness,
1543           int line_type, int shift )
1544 {
1545     if( !v || count <= 0 )
1546         return;
1547
1548     int i = is_closed ? count - 1 : 0;
1549     int flags = 2 + !is_closed;
1550     Point p0;
1551     CV_Assert( 0 <= shift && shift <= XY_SHIFT && thickness >= 0 );
1552
1553     p0 = v[i];
1554     for( i = !is_closed; i < count; i++ )
1555     {
1556         Point p = v[i];
1557         ThickLine( img, p0, p, color, thickness, line_type, flags, shift );
1558         p0 = p;
1559         flags = 2;
1560     }
1561 }
1562
1563 /****************************************************************************************\
1564 *                              External functions                                        *
1565 \****************************************************************************************/
1566
1567 void line( Mat& img, Point pt1, Point pt2, const Scalar& color,
1568            int thickness, int line_type, int shift )
1569 {
1570     if( line_type == CV_AA && img.depth() != CV_8U )
1571         line_type = 8;
1572
1573     CV_Assert( 0 <= thickness && thickness <= 255 );
1574     CV_Assert( 0 <= shift && shift <= XY_SHIFT );
1575
1576     double buf[4];
1577     scalarToRawData( color, buf, img.type(), 0 );
1578     ThickLine( img, pt1, pt2, buf, thickness, line_type, 3, shift );
1579 }
1580
1581 void rectangle( Mat& img, Point pt1, Point pt2,
1582                 const Scalar& color, int thickness,
1583                 int lineType, int shift )
1584 {
1585     if( lineType == CV_AA && img.depth() != CV_8U )
1586         lineType = 8;
1587
1588     CV_Assert( thickness <= 255 );
1589     CV_Assert( 0 <= shift && shift <= XY_SHIFT );
1590
1591     double buf[4];
1592     scalarToRawData(color, buf, img.type(), 0);
1593
1594     Point pt[4];
1595
1596     pt[0] = pt1;
1597     pt[1].x = pt2.x;
1598     pt[1].y = pt1.y;
1599     pt[2] = pt2;
1600     pt[3].x = pt1.x;
1601     pt[3].y = pt2.y;
1602
1603     if( thickness >= 0 )
1604         PolyLine( img, pt, 4, true, buf, thickness, lineType, shift );
1605     else
1606         FillConvexPoly( img, pt, 4, buf, lineType, shift );
1607 }
1608
1609
1610 void rectangle( Mat& img, Rect rec,
1611                 const Scalar& color, int thickness,
1612                 int lineType, int shift )
1613 {
1614     CV_Assert( 0 <= shift && shift <= XY_SHIFT );
1615     if( rec.area() > 0 )
1616         rectangle( img, rec.tl(), rec.br() - Point(1<<shift,1<<shift),
1617                    color, thickness, lineType, shift );
1618 }
1619
1620
1621 void circle( Mat& img, Point center, int radius,
1622              const Scalar& color, int thickness, int line_type, int shift )
1623 {
1624     if( line_type == CV_AA && img.depth() != CV_8U )
1625         line_type = 8;
1626
1627     CV_Assert( radius >= 0 && thickness <= 255 &&
1628         0 <= shift && shift <= XY_SHIFT );
1629
1630     double buf[4];
1631     scalarToRawData(color, buf, img.type(), 0);
1632
1633     if( thickness > 1 || line_type >= CV_AA )
1634     {
1635         center.x <<= XY_SHIFT - shift;
1636         center.y <<= XY_SHIFT - shift;
1637         radius <<= XY_SHIFT - shift;
1638         EllipseEx( img, center, Size(radius, radius),
1639                    0, 0, 360, buf, thickness, line_type );
1640     }
1641     else
1642         Circle( img, center, radius, buf, thickness < 0 );
1643 }
1644
1645
1646 void ellipse( Mat& img, Point center, Size axes,
1647               double angle, double start_angle, double end_angle,
1648               const Scalar& color, int thickness, int line_type, int shift )
1649 {
1650     if( line_type == CV_AA && img.depth() != CV_8U )
1651         line_type = 8;
1652
1653     CV_Assert( axes.width >= 0 && axes.height >= 0 &&
1654         thickness <= 255 && 0 <= shift && shift <= XY_SHIFT );
1655
1656     double buf[4];
1657     scalarToRawData(color, buf, img.type(), 0);
1658
1659     int _angle = cvRound(angle);
1660     int _start_angle = cvRound(start_angle);
1661     int _end_angle = cvRound(end_angle);
1662     center.x <<= XY_SHIFT - shift;
1663     center.y <<= XY_SHIFT - shift;
1664     axes.width <<= XY_SHIFT - shift;
1665     axes.height <<= XY_SHIFT - shift;
1666
1667     EllipseEx( img, center, axes, _angle, _start_angle,
1668                _end_angle, buf, thickness, line_type );
1669 }
1670
1671 void ellipse(Mat& img, const RotatedRect& box, const Scalar& color,
1672              int thickness, int lineType)
1673 {
1674     if( lineType == CV_AA && img.depth() != CV_8U )
1675         lineType = 8;
1676
1677     CV_Assert( box.size.width >= 0 && box.size.height >= 0 &&
1678                thickness <= 255 );
1679
1680     double buf[4];
1681     scalarToRawData(color, buf, img.type(), 0);
1682
1683     int _angle = cvRound(box.angle);
1684     Point center(cvRound(box.center.x*(1 << XY_SHIFT)),
1685                  cvRound(box.center.y*(1 << XY_SHIFT)));
1686     Size axes(cvRound(box.size.width*(1 << (XY_SHIFT - 1))),
1687               cvRound(box.size.height*(1 << (XY_SHIFT - 1))));
1688     EllipseEx( img, center, axes, _angle, 0, 360, buf, thickness, lineType );
1689 }
1690
1691 void fillConvexPoly( Mat& img, const Point* pts, int npts,
1692                      const Scalar& color, int line_type, int shift )
1693 {
1694     if( !pts || npts <= 0 )
1695         return;
1696
1697     if( line_type == CV_AA && img.depth() != CV_8U )
1698         line_type = 8;
1699
1700     double buf[4];
1701     CV_Assert( 0 <= shift && shift <=  XY_SHIFT );
1702     scalarToRawData(color, buf, img.type(), 0);
1703     FillConvexPoly( img, pts, npts, buf, line_type, shift );
1704 }
1705
1706
1707 void fillPoly( Mat& img, const Point** pts, const int* npts, int ncontours,
1708                const Scalar& color, int line_type,
1709                int shift, Point offset )
1710 {
1711     if( line_type == CV_AA && img.depth() != CV_8U )
1712         line_type = 8;
1713
1714     CV_Assert( pts && npts && ncontours >= 0 && 0 <= shift && shift <= XY_SHIFT );
1715
1716     double buf[4];
1717     scalarToRawData(color, buf, img.type(), 0);
1718
1719     vector<PolyEdge> edges;
1720
1721     int i, total = 0;
1722     for( i = 0; i < ncontours; i++ )
1723         total += npts[i];
1724
1725     edges.reserve( total + 1 );
1726     for( i = 0; i < ncontours; i++ )
1727         CollectPolyEdges( img, pts[i], npts[i], edges, buf, line_type, shift, offset );
1728
1729     FillEdgeCollection(img, edges, buf);
1730 }
1731
1732
1733 void polylines( Mat& img, const Point** pts, const int* npts, int ncontours, bool isClosed,
1734                 const Scalar& color, int thickness, int line_type, int shift )
1735 {
1736     if( line_type == CV_AA && img.depth() != CV_8U )
1737         line_type = 8;
1738
1739     CV_Assert( pts && npts && ncontours >= 0 &&
1740                0 <= thickness && thickness <= 255 &&
1741                0 <= shift && shift <= XY_SHIFT );
1742
1743     double buf[4];
1744     scalarToRawData( color, buf, img.type(), 0 );
1745
1746     for( int i = 0; i < ncontours; i++ )
1747         PolyLine( img, pts[i], npts[i], isClosed, buf, thickness, line_type, shift );
1748 }
1749
1750
1751 enum { FONT_SIZE_SHIFT=8, FONT_ITALIC_ALPHA=(1 << 8),
1752        FONT_ITALIC_DIGIT=(2 << 8), FONT_ITALIC_PUNCT=(4 << 8),
1753        FONT_ITALIC_BRACES=(8 << 8), FONT_HAVE_GREEK=(16 << 8),
1754        FONT_HAVE_CYRILLIC=(32 << 8) };
1755
1756 static const int HersheyPlain[] = {
1757 (5 + 4*16) + FONT_HAVE_GREEK,
1758 199, 214, 217, 233, 219, 197, 234, 216, 221, 222, 228, 225, 211, 224, 210, 220,
1759 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 212, 213, 191, 226, 192,
1760 215, 190, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
1761 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 193, 84,
1762 194, 85, 86, 87, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
1763 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126,
1764 195, 223, 196, 88 };
1765
1766 static const int HersheyPlainItalic[] = {
1767 (5 + 4*16) + FONT_ITALIC_ALPHA + FONT_HAVE_GREEK,
1768 199, 214, 217, 233, 219, 197, 234, 216, 221, 222, 228, 225, 211, 224, 210, 220,
1769 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 212, 213, 191, 226, 192,
1770 215, 190, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
1771 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 193, 84,
1772 194, 85, 86, 87, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161,
1773 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176,
1774 195, 223, 196, 88 };
1775
1776 static const int HersheyComplexSmall[] = {
1777 (6 + 7*16) + FONT_HAVE_GREEK,
1778 1199, 1214, 1217, 1275, 1274, 1271, 1272, 1216, 1221, 1222, 1219, 1232, 1211, 1231, 1210, 1220,
1779 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208, 1209, 1212, 2213, 1241, 1238, 1242,
1780 1215, 1273, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 1012, 1013,
1781 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1024, 1025, 1026, 1223, 1084,
1782 1224, 1247, 586, 1249, 1101, 1102, 1103, 1104, 1105, 1106, 1107, 1108, 1109, 1110, 1111,
1783 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1120, 1121, 1122, 1123, 1124, 1125, 1126,
1784 1225, 1229, 1226, 1246 };
1785
1786 static const int HersheyComplexSmallItalic[] = {
1787 (6 + 7*16) + FONT_ITALIC_ALPHA + FONT_HAVE_GREEK,
1788 1199, 1214, 1217, 1275, 1274, 1271, 1272, 1216, 1221, 1222, 1219, 1232, 1211, 1231, 1210, 1220,
1789 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208, 1209, 1212, 1213, 1241, 1238, 1242,
1790 1215, 1273, 1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063,
1791 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076, 1223, 1084,
1792 1224, 1247, 586, 1249, 1151, 1152, 1153, 1154, 1155, 1156, 1157, 1158, 1159, 1160, 1161,
1793 1162, 1163, 1164, 1165, 1166, 1167, 1168, 1169, 1170, 1171, 1172, 1173, 1174, 1175, 1176,
1794 1225, 1229, 1226, 1246 };
1795
1796 static const int HersheySimplex[] = {
1797 (9 + 12*16) + FONT_HAVE_GREEK,
1798 2199, 714, 717, 733, 719, 697, 734, 716, 721, 722, 728, 725, 711, 724, 710, 720,
1799 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 712, 713, 691, 726, 692,
1800 715, 690, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513,
1801 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 693, 584,
1802 694, 2247, 586, 2249, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611,
1803 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626,
1804 695, 723, 696, 2246 };
1805
1806 static const int HersheyDuplex[] = {
1807 (9 + 12*16) + FONT_HAVE_GREEK,
1808 2199, 2714, 2728, 2732, 2719, 2733, 2718, 2727, 2721, 2722, 2723, 2725, 2711, 2724, 2710, 2720,
1809 2700, 2701, 2702, 2703, 2704, 2705, 2706, 2707, 2708, 2709, 2712, 2713, 2730, 2726, 2731,
1810 2715, 2734, 2501, 2502, 2503, 2504, 2505, 2506, 2507, 2508, 2509, 2510, 2511, 2512, 2513,
1811 2514, 2515, 2516, 2517, 2518, 2519, 2520, 2521, 2522, 2523, 2524, 2525, 2526, 2223, 2084,
1812 2224, 2247, 587, 2249, 2601, 2602, 2603, 2604, 2605, 2606, 2607, 2608, 2609, 2610, 2611,
1813 2612, 2613, 2614, 2615, 2616, 2617, 2618, 2619, 2620, 2621, 2622, 2623, 2624, 2625, 2626,
1814 2225, 2229, 2226, 2246 };
1815
1816 static const int HersheyComplex[] = {
1817 (9 + 12*16) + FONT_HAVE_GREEK + FONT_HAVE_CYRILLIC,
1818 2199, 2214, 2217, 2275, 2274, 2271, 2272, 2216, 2221, 2222, 2219, 2232, 2211, 2231, 2210, 2220,
1819 2200, 2201, 2202, 2203, 2204, 2205, 2206, 2207, 2208, 2209, 2212, 2213, 2241, 2238, 2242,
1820 2215, 2273, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013,
1821 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024, 2025, 2026, 2223, 2084,
1822 2224, 2247, 587, 2249, 2101, 2102, 2103, 2104, 2105, 2106, 2107, 2108, 2109, 2110, 2111,
1823 2112, 2113, 2114, 2115, 2116, 2117, 2118, 2119, 2120, 2121, 2122, 2123, 2124, 2125, 2126,
1824 2225, 2229, 2226, 2246 };
1825
1826 static const int HersheyComplexItalic[] = {
1827 (9 + 12*16) + FONT_ITALIC_ALPHA + FONT_ITALIC_DIGIT + FONT_ITALIC_PUNCT +
1828 FONT_HAVE_GREEK + FONT_HAVE_CYRILLIC,
1829 2199, 2764, 2778, 2782, 2769, 2783, 2768, 2777, 2771, 2772, 2219, 2232, 2211, 2231, 2210, 2220,
1830 2750, 2751, 2752, 2753, 2754, 2755, 2756, 2757, 2758, 2759, 2212, 2213, 2241, 2238, 2242,
1831 2765, 2273, 2051, 2052, 2053, 2054, 2055, 2056, 2057, 2058, 2059, 2060, 2061, 2062, 2063,
1832 2064, 2065, 2066, 2067, 2068, 2069, 2070, 2071, 2072, 2073, 2074, 2075, 2076, 2223, 2084,
1833 2224, 2247, 587, 2249, 2151, 2152, 2153, 2154, 2155, 2156, 2157, 2158, 2159, 2160, 2161,
1834 2162, 2163, 2164, 2165, 2166, 2167, 2168, 2169, 2170, 2171, 2172, 2173, 2174, 2175, 2176,
1835 2225, 2229, 2226, 2246 };
1836
1837 static const int HersheyTriplex[] = {
1838 (9 + 12*16) + FONT_HAVE_GREEK,
1839 2199, 3214, 3228, 3232, 3219, 3233, 3218, 3227, 3221, 3222, 3223, 3225, 3211, 3224, 3210, 3220,
1840 3200, 3201, 3202, 3203, 3204, 3205, 3206, 3207, 3208, 3209, 3212, 3213, 3230, 3226, 3231,
1841 3215, 3234, 3001, 3002, 3003, 3004, 3005, 3006, 3007, 3008, 3009, 3010, 3011, 3012, 3013,
1842 2014, 3015, 3016, 3017, 3018, 3019, 3020, 3021, 3022, 3023, 3024, 3025, 3026, 2223, 2084,
1843 2224, 2247, 587, 2249, 3101, 3102, 3103, 3104, 3105, 3106, 3107, 3108, 3109, 3110, 3111,
1844 3112, 3113, 3114, 3115, 3116, 3117, 3118, 3119, 3120, 3121, 3122, 3123, 3124, 3125, 3126,
1845 2225, 2229, 2226, 2246 };
1846
1847 static const int HersheyTriplexItalic[] = {
1848 (9 + 12*16) + FONT_ITALIC_ALPHA + FONT_ITALIC_DIGIT +
1849 FONT_ITALIC_PUNCT + FONT_HAVE_GREEK,
1850 2199, 3264, 3278, 3282, 3269, 3233, 3268, 3277, 3271, 3272, 3223, 3225, 3261, 3224, 3260, 3270,
1851 3250, 3251, 3252, 3253, 3254, 3255, 3256, 3257, 3258, 3259, 3262, 3263, 3230, 3226, 3231,
1852 3265, 3234, 3051, 3052, 3053, 3054, 3055, 3056, 3057, 3058, 3059, 3060, 3061, 3062, 3063,
1853 2064, 3065, 3066, 3067, 3068, 3069, 3070, 3071, 3072, 3073, 3074, 3075, 3076, 2223, 2084,
1854 2224, 2247, 587, 2249, 3151, 3152, 3153, 3154, 3155, 3156, 3157, 3158, 3159, 3160, 3161,
1855 3162, 3163, 3164, 3165, 3166, 3167, 3168, 3169, 3170, 3171, 3172, 3173, 3174, 3175, 3176,
1856 2225, 2229, 2226, 2246 };
1857
1858 static const int HersheyScriptSimplex[] = {
1859 (9 + 12*16) + FONT_ITALIC_ALPHA + FONT_HAVE_GREEK,
1860 2199, 714, 717, 733, 719, 697, 734, 716, 721, 722, 728, 725, 711, 724, 710, 720,
1861 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 712, 713, 691, 726, 692,
1862 715, 690, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563,
1863 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 693, 584,
1864 694, 2247, 586, 2249, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661,
1865 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676,
1866 695, 723, 696, 2246 };
1867
1868 static const int HersheyScriptComplex[] = {
1869 (9 + 12*16) + FONT_ITALIC_ALPHA + FONT_ITALIC_DIGIT + FONT_ITALIC_PUNCT + FONT_HAVE_GREEK,
1870 2199, 2764, 2778, 2782, 2769, 2783, 2768, 2777, 2771, 2772, 2219, 2232, 2211, 2231, 2210, 2220,
1871 2750, 2751, 2752, 2753, 2754, 2755, 2756, 2757, 2758, 2759, 2212, 2213, 2241, 2238, 2242,
1872 2215, 2273, 2551, 2552, 2553, 2554, 2555, 2556, 2557, 2558, 2559, 2560, 2561, 2562, 2563,
1873 2564, 2565, 2566, 2567, 2568, 2569, 2570, 2571, 2572, 2573, 2574, 2575, 2576, 2223, 2084,
1874 2224, 2247, 586, 2249, 2651, 2652, 2653, 2654, 2655, 2656, 2657, 2658, 2659, 2660, 2661,
1875 2662, 2663, 2664, 2665, 2666, 2667, 2668, 2669, 2670, 2671, 2672, 2673, 2674, 2675, 2676,
1876 2225, 2229, 2226, 2246 };
1877
1878
1879 static const int* getFontData(int fontFace)
1880 {
1881     bool isItalic = (fontFace & FONT_ITALIC) != 0;
1882     const int* ascii = 0;
1883
1884     switch( fontFace & 15 )
1885     {
1886     case FONT_HERSHEY_SIMPLEX:
1887         ascii = HersheySimplex;
1888         break;
1889     case FONT_HERSHEY_PLAIN:
1890         ascii = !isItalic ? HersheyPlain : HersheyPlainItalic;
1891         break;
1892     case FONT_HERSHEY_DUPLEX:
1893         ascii = HersheyDuplex;
1894         break;
1895     case FONT_HERSHEY_COMPLEX:
1896         ascii = !isItalic ? HersheyComplex : HersheyComplexItalic;
1897         break;
1898     case FONT_HERSHEY_TRIPLEX:
1899         ascii = !isItalic ? HersheyTriplex : HersheyTriplexItalic;
1900         break;
1901     case FONT_HERSHEY_COMPLEX_SMALL:
1902         ascii = !isItalic ? HersheyComplexSmall : HersheyComplexSmallItalic;
1903         break;
1904     case FONT_HERSHEY_SCRIPT_SIMPLEX:
1905         ascii = HersheyScriptSimplex;
1906         break;
1907     case FONT_HERSHEY_SCRIPT_COMPLEX:
1908         ascii = HersheyScriptComplex;
1909         break;
1910     default:
1911         CV_Error( CV_StsOutOfRange, "Unknown font type" );
1912     }
1913     return ascii;
1914 }
1915
1916
1917 void putText( Mat& img, const string& text, Point org,
1918               int fontFace, double fontScale, Scalar color,
1919               int thickness, int line_type, bool bottomLeftOrigin )
1920
1921 {
1922     const int* ascii = getFontData(fontFace);
1923
1924     double buf[4];
1925     scalarToRawData(color, buf, img.type(), 0);
1926
1927     int base_line = -(ascii[0] & 15);
1928     int hscale = cvRound(fontScale*XY_ONE), vscale = hscale;
1929
1930     if( line_type == CV_AA && img.depth() != CV_8U )
1931         line_type = 8;
1932
1933     if( bottomLeftOrigin )
1934         vscale = -vscale;
1935
1936     int view_x = org.x << XY_SHIFT;
1937     int view_y = (org.y << XY_SHIFT) + base_line*vscale;
1938     vector<Point> pts;
1939     pts.reserve(1 << 10);
1940     const char **faces = cv::g_HersheyGlyphs;
1941
1942     for( int i = 0; text[i] != '\0'; i++ )
1943     {
1944         int c = (uchar)text[i];
1945         Point p;
1946
1947         if( c >= 127 || c < ' ' )
1948             c = '?';
1949
1950         const char* ptr = faces[ascii[(c-' ')+1]];
1951         p.x = (uchar)ptr[0] - 'R';
1952         p.y = (uchar)ptr[1] - 'R';
1953         int dx = p.y*hscale;
1954         view_x -= p.x*hscale;
1955         pts.resize(0);
1956
1957         for( ptr += 2;; )
1958         {
1959             if( *ptr == ' ' || !*ptr )
1960             {
1961                 if( pts.size() > 1 )
1962                     PolyLine( img, &pts[0], (int)pts.size(), false, buf, thickness, line_type, XY_SHIFT );
1963                 if( !*ptr++ )
1964                     break;
1965                 pts.resize(0);
1966             }
1967             else
1968             {
1969                 p.x = (uchar)ptr[0] - 'R';
1970                 p.y = (uchar)ptr[1] - 'R';
1971                 ptr += 2;
1972                 pts.push_back(Point(p.x*hscale + view_x, p.y*vscale + view_y));
1973             }
1974         }
1975         view_x += dx;
1976     }
1977 }
1978
1979 Size getTextSize( const string& text, int fontFace, double fontScale, int thickness, int* _base_line)
1980 {
1981     Size size;
1982     double view_x = 0;
1983     const char **faces = cv::g_HersheyGlyphs;
1984     const int* ascii = getFontData(fontFace);
1985
1986     int base_line = (ascii[0] & 15);
1987     int cap_line = (ascii[0] >> 4) & 15;
1988     size.height = cvRound((cap_line + base_line)*fontScale + (thickness+1)/2);
1989
1990     for( int i = 0; text[i] != '\0'; i++ )
1991     {
1992         int c = (uchar)text[i];
1993         Point p;
1994
1995         if( c >= 127 || c < ' ' )
1996             c = '?';
1997
1998         const char* ptr = faces[ascii[(c-' ')+1]];
1999         p.x = (uchar)ptr[0] - 'R';
2000         p.y = (uchar)ptr[1] - 'R';
2001         view_x += (p.y - p.x)*fontScale;
2002     }
2003
2004     size.width = cvRound(view_x + thickness);
2005     if( _base_line )
2006         *_base_line = cvRound(base_line*fontScale + thickness*0.5);
2007     return size;
2008 }
2009
2010 }
2011
2012
2013 void cv::fillConvexPoly(InputOutputArray _img, InputArray _points,
2014                         const Scalar& color, int lineType, int shift)
2015 {
2016     Mat img = _img.getMat(), points = _points.getMat();
2017     CV_Assert(points.checkVector(2, CV_32S) >= 0);
2018     fillConvexPoly(img, (const Point*)points.data, points.rows*points.cols*points.channels()/2, color, lineType, shift);
2019 }
2020
2021
2022 void cv::fillPoly(InputOutputArray _img, InputArrayOfArrays pts,
2023                   const Scalar& color, int lineType, int shift, Point offset)
2024 {
2025     Mat img = _img.getMat();
2026     int i, ncontours = (int)pts.total();
2027     if( ncontours == 0 )
2028         return;
2029     AutoBuffer<Point*> _ptsptr(ncontours);
2030     AutoBuffer<int> _npts(ncontours);
2031     Point** ptsptr = _ptsptr;
2032     int* npts = _npts;
2033
2034     for( i = 0; i < ncontours; i++ )
2035     {
2036         Mat p = pts.getMat(i);
2037         CV_Assert(p.checkVector(2, CV_32S) >= 0);
2038         ptsptr[i] = (Point*)p.data;
2039         npts[i] = p.rows*p.cols*p.channels()/2;
2040     }
2041     fillPoly(img, (const Point**)ptsptr, npts, (int)ncontours, color, lineType, shift, offset);
2042 }
2043
2044
2045 void cv::polylines(InputOutputArray _img, InputArrayOfArrays pts,
2046                    bool isClosed, const Scalar& color,
2047                    int thickness, int lineType, int shift )
2048 {
2049     Mat img = _img.getMat();
2050     bool manyContours = pts.kind() == _InputArray::STD_VECTOR_VECTOR ||
2051                         pts.kind() == _InputArray::STD_VECTOR_MAT;
2052     int i, ncontours = manyContours ? (int)pts.total() : 1;
2053     if( ncontours == 0 )
2054         return;
2055     AutoBuffer<Point*> _ptsptr(ncontours);
2056     AutoBuffer<int> _npts(ncontours);
2057     Point** ptsptr = _ptsptr;
2058     int* npts = _npts;
2059
2060     for( i = 0; i < ncontours; i++ )
2061     {
2062         Mat p = pts.getMat(manyContours ? i : -1);
2063         if( p.total() == 0 )
2064             continue;
2065         CV_Assert(p.checkVector(2, CV_32S) >= 0);
2066         ptsptr[i] = (Point*)p.data;
2067         npts[i] = p.rows*p.cols*p.channels()/2;
2068     }
2069     polylines(img, (const Point**)ptsptr, npts, (int)ncontours, isClosed, color, thickness, lineType, shift);
2070 }
2071
2072 namespace
2073 {
2074 using namespace cv;
2075
2076 static void addChildContour(InputArrayOfArrays contours,
2077                             size_t ncontours,
2078                             const Vec4i* hierarchy,
2079                             int i, vector<CvSeq>& seq,
2080                             vector<CvSeqBlock>& block)
2081 {
2082     for( ; i >= 0; i = hierarchy[i][0] )
2083     {
2084         Mat ci = contours.getMat(i);
2085         cvMakeSeqHeaderForArray(CV_SEQ_POLYGON, sizeof(CvSeq), sizeof(Point),
2086                                 !ci.empty() ? (void*)ci.data : 0, (int)ci.total(),
2087                                 &seq[i], &block[i] );
2088
2089         int h_next = hierarchy[i][0], h_prev = hierarchy[i][1],
2090             v_next = hierarchy[i][2], v_prev = hierarchy[i][3];
2091         seq[i].h_next = (size_t)h_next < ncontours ? &seq[h_next] : 0;
2092         seq[i].h_prev = (size_t)h_prev < ncontours ? &seq[h_prev] : 0;
2093         seq[i].v_next = (size_t)v_next < ncontours ? &seq[v_next] : 0;
2094         seq[i].v_prev = (size_t)v_prev < ncontours ? &seq[v_prev] : 0;
2095
2096         if( v_next >= 0 )
2097             addChildContour(contours, ncontours, hierarchy, v_next, seq, block);
2098     }
2099 }
2100 }
2101
2102 void cv::drawContours( InputOutputArray _image, InputArrayOfArrays _contours,
2103                    int contourIdx, const Scalar& color, int thickness,
2104                    int lineType, InputArray _hierarchy,
2105                    int maxLevel, Point offset )
2106 {
2107     Mat image = _image.getMat(), hierarchy = _hierarchy.getMat();
2108     CvMat _cimage = image;
2109
2110     size_t ncontours = _contours.total();
2111     size_t i = 0, first = 0, last = ncontours;
2112     vector<CvSeq> seq;
2113     vector<CvSeqBlock> block;
2114
2115     if( !last )
2116         return;
2117
2118     seq.resize(last);
2119     block.resize(last);
2120
2121     for( i = first; i < last; i++ )
2122         seq[i].first = 0;
2123
2124     if( contourIdx >= 0 )
2125     {
2126         CV_Assert( 0 <= contourIdx && contourIdx < (int)last );
2127         first = contourIdx;
2128         last = contourIdx + 1;
2129     }
2130
2131     for( i = first; i < last; i++ )
2132     {
2133         Mat ci = _contours.getMat((int)i);
2134         if( ci.empty() )
2135             continue;
2136         int npoints = ci.checkVector(2, CV_32S);
2137         CV_Assert( npoints > 0 );
2138         cvMakeSeqHeaderForArray( CV_SEQ_POLYGON, sizeof(CvSeq), sizeof(Point),
2139                                  ci.data, npoints, &seq[i], &block[i] );
2140     }
2141
2142     if( hierarchy.empty() || maxLevel == 0 )
2143         for( i = first; i < last; i++ )
2144         {
2145             seq[i].h_next = i < last-1 ? &seq[i+1] : 0;
2146             seq[i].h_prev = i > first ? &seq[i-1] : 0;
2147         }
2148     else
2149     {
2150         size_t count = last - first;
2151         CV_Assert(hierarchy.total() == ncontours && hierarchy.type() == CV_32SC4 );
2152         const Vec4i* h = hierarchy.ptr<Vec4i>();
2153
2154         if( count == ncontours )
2155         {
2156             for( i = first; i < last; i++ )
2157             {
2158                 int h_next = h[i][0], h_prev = h[i][1],
2159                     v_next = h[i][2], v_prev = h[i][3];
2160                 seq[i].h_next = (size_t)h_next < count ? &seq[h_next] : 0;
2161                 seq[i].h_prev = (size_t)h_prev < count ? &seq[h_prev] : 0;
2162                 seq[i].v_next = (size_t)v_next < count ? &seq[v_next] : 0;
2163                 seq[i].v_prev = (size_t)v_prev < count ? &seq[v_prev] : 0;
2164             }
2165         }
2166         else
2167         {
2168             int child = h[first][2];
2169             if( child >= 0 )
2170             {
2171                 addChildContour(_contours, ncontours, h, child, seq, block);
2172                 seq[first].v_next = &seq[child];
2173             }
2174         }
2175     }
2176
2177     cvDrawContours( &_cimage, &seq[first], color, color, contourIdx >= 0 ?
2178                    -maxLevel : maxLevel, thickness, lineType, offset );
2179 }
2180
2181
2182
2183 static const int CodeDeltas[8][2] =
2184 { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };
2185
2186 #define CV_ADJUST_EDGE_COUNT( count, seq )  \
2187     ((count) -= ((count) == (seq)->total && !CV_IS_SEQ_CLOSED(seq)))
2188
2189 CV_IMPL void
2190 cvDrawContours( void* _img, CvSeq* contour,
2191                 CvScalar _externalColor, CvScalar _holeColor,
2192                 int  maxLevel, int thickness,
2193                 int line_type, CvPoint _offset )
2194 {
2195     CvSeq *contour0 = contour, *h_next = 0;
2196     CvTreeNodeIterator iterator;
2197     cv::vector<cv::PolyEdge> edges;
2198     cv::vector<cv::Point> pts;
2199     cv::Scalar externalColor = _externalColor, holeColor = _holeColor;
2200     cv::Mat img = cv::cvarrToMat(_img);
2201     cv::Point offset = _offset;
2202     double ext_buf[4], hole_buf[4];
2203
2204     if( line_type == CV_AA && img.depth() != CV_8U )
2205         line_type = 8;
2206
2207     if( !contour )
2208         return;
2209
2210     CV_Assert( thickness <= 255 );
2211
2212     scalarToRawData( externalColor, ext_buf, img.type(), 0 );
2213     scalarToRawData( holeColor, hole_buf, img.type(), 0 );
2214
2215     maxLevel = MAX(maxLevel, INT_MIN+2);
2216     maxLevel = MIN(maxLevel, INT_MAX-1);
2217
2218     if( maxLevel < 0 )
2219     {
2220         h_next = contour->h_next;
2221         contour->h_next = 0;
2222         maxLevel = -maxLevel+1;
2223     }
2224
2225     cvInitTreeNodeIterator( &iterator, contour, maxLevel );
2226     while( (contour = (CvSeq*)cvNextTreeNode( &iterator )) != 0 )
2227     {
2228         CvSeqReader reader;
2229         int i, count = contour->total;
2230         int elem_type = CV_MAT_TYPE(contour->flags);
2231         void* clr = (contour->flags & CV_SEQ_FLAG_HOLE) == 0 ? ext_buf : hole_buf;
2232
2233         cvStartReadSeq( contour, &reader, 0 );
2234         if( thickness < 0 )
2235             pts.resize(0);
2236
2237         if( CV_IS_SEQ_CHAIN_CONTOUR( contour ))
2238         {
2239             cv::Point pt = ((CvChain*)contour)->origin;
2240             cv::Point prev_pt = pt;
2241             char prev_code = reader.ptr ? reader.ptr[0] : '\0';
2242
2243             prev_pt += offset;
2244
2245             for( i = 0; i < count; i++ )
2246             {
2247                 char code;
2248                 CV_READ_SEQ_ELEM( code, reader );
2249
2250                 assert( (code & ~7) == 0 );
2251
2252                 if( code != prev_code )
2253                 {
2254                     prev_code = code;
2255                     if( thickness >= 0 )
2256                         cv::ThickLine( img, prev_pt, pt, clr, thickness, line_type, 2, 0 );
2257                     else
2258                         pts.push_back(pt);
2259                     prev_pt = pt;
2260                 }
2261
2262                 pt.x += CodeDeltas[(int)code][0];
2263                 pt.y += CodeDeltas[(int)code][1];
2264             }
2265
2266             if( thickness >= 0 )
2267                 cv::ThickLine( img, prev_pt,
2268                     cv::Point(((CvChain*)contour)->origin) + offset,
2269                     clr, thickness, line_type, 2, 0 );
2270             else
2271                 cv::CollectPolyEdges(img, &pts[0], (int)pts.size(),
2272                                      edges, ext_buf, line_type, 0, offset);
2273         }
2274         else if( CV_IS_SEQ_POLYLINE( contour ))
2275         {
2276             CV_Assert( elem_type == CV_32SC2 );
2277             cv::Point pt1, pt2;
2278             int shift = 0;
2279
2280             count -= !CV_IS_SEQ_CLOSED(contour);
2281             CV_READ_SEQ_ELEM( pt1, reader );
2282             pt1 += offset;
2283             if( thickness < 0 )
2284                 pts.push_back(pt1);
2285
2286             for( i = 0; i < count; i++ )
2287             {
2288                 CV_READ_SEQ_ELEM( pt2, reader );
2289                 pt2 += offset;
2290                 if( thickness >= 0 )
2291                     cv::ThickLine( img, pt1, pt2, clr, thickness, line_type, 2, shift );
2292                 else
2293                     pts.push_back(pt2);
2294                 pt1 = pt2;
2295             }
2296             if( thickness < 0 )
2297                 cv::CollectPolyEdges( img, &pts[0], (int)pts.size(),
2298                                       edges, ext_buf, line_type, 0, cv::Point() );
2299         }
2300     }
2301
2302     if( thickness < 0 )
2303         cv::FillEdgeCollection( img, edges, ext_buf );
2304
2305     if( h_next && contour0 )
2306         contour0->h_next = h_next;
2307 }
2308
2309 CV_IMPL int
2310 cvClipLine( CvSize size, CvPoint* pt1, CvPoint* pt2 )
2311 {
2312     CV_Assert( pt1 && pt2 );
2313     return cv::clipLine( size, *(cv::Point*)pt1, *(cv::Point*)pt2 );
2314 }
2315
2316
2317 CV_IMPL int
2318 cvEllipse2Poly( CvPoint center, CvSize axes, int angle,
2319                 int arc_start, int arc_end, CvPoint* _pts, int delta )
2320 {
2321     cv::vector<cv::Point> pts;
2322     cv::ellipse2Poly( center, axes, angle, arc_start, arc_end, delta, pts );
2323     memcpy( _pts, &pts[0], pts.size()*sizeof(_pts[0]) );
2324     return (int)pts.size();
2325 }
2326
2327 CV_IMPL CvScalar
2328 cvColorToScalar( double packed_color, int type )
2329 {
2330     CvScalar scalar;
2331
2332     if( CV_MAT_DEPTH( type ) == CV_8U )
2333     {
2334         int icolor = cvRound( packed_color );
2335         if( CV_MAT_CN( type ) > 1 )
2336         {
2337             scalar.val[0] = icolor & 255;
2338             scalar.val[1] = (icolor >> 8) & 255;
2339             scalar.val[2] = (icolor >> 16) & 255;
2340             scalar.val[3] = (icolor >> 24) & 255;
2341         }
2342         else
2343         {
2344             scalar.val[0] = CV_CAST_8U( icolor );
2345             scalar.val[1] = scalar.val[2] = scalar.val[3] = 0;
2346         }
2347     }
2348     else if( CV_MAT_DEPTH( type ) == CV_8S )
2349     {
2350         int icolor = cvRound( packed_color );
2351         if( CV_MAT_CN( type ) > 1 )
2352         {
2353             scalar.val[0] = (char)icolor;
2354             scalar.val[1] = (char)(icolor >> 8);
2355             scalar.val[2] = (char)(icolor >> 16);
2356             scalar.val[3] = (char)(icolor >> 24);
2357         }
2358         else
2359         {
2360             scalar.val[0] = CV_CAST_8S( icolor );
2361             scalar.val[1] = scalar.val[2] = scalar.val[3] = 0;
2362         }
2363     }
2364     else
2365     {
2366         int cn = CV_MAT_CN( type );
2367         switch( cn )
2368         {
2369         case 1:
2370             scalar.val[0] = packed_color;
2371             scalar.val[1] = scalar.val[2] = scalar.val[3] = 0;
2372             break;
2373         case 2:
2374             scalar.val[0] = scalar.val[1] = packed_color;
2375             scalar.val[2] = scalar.val[3] = 0;
2376             break;
2377         case 3:
2378             scalar.val[0] = scalar.val[1] = scalar.val[2] = packed_color;
2379             scalar.val[3] = 0;
2380             break;
2381         default:
2382             scalar.val[0] = scalar.val[1] =
2383                 scalar.val[2] = scalar.val[3] = packed_color;
2384             break;
2385         }
2386     }
2387
2388     return scalar;
2389 }
2390
2391 CV_IMPL int
2392 cvInitLineIterator( const CvArr* img, CvPoint pt1, CvPoint pt2,
2393                     CvLineIterator* iterator, int connectivity,
2394                     int left_to_right )
2395 {
2396     CV_Assert( iterator != 0 );
2397     cv::LineIterator li(cv::cvarrToMat(img), pt1, pt2, connectivity, left_to_right!=0);
2398
2399     iterator->err = li.err;
2400     iterator->minus_delta = li.minusDelta;
2401     iterator->plus_delta = li.plusDelta;
2402     iterator->minus_step = li.minusStep;
2403     iterator->plus_step = li.plusStep;
2404     iterator->ptr = li.ptr;
2405
2406     return li.count;
2407 }
2408
2409 CV_IMPL void
2410 cvLine( CvArr* _img, CvPoint pt1, CvPoint pt2, CvScalar color,
2411         int thickness, int line_type, int shift )
2412 {
2413     cv::Mat img = cv::cvarrToMat(_img);
2414     cv::line( img, pt1, pt2, color, thickness, line_type, shift );
2415 }
2416
2417 CV_IMPL void
2418 cvRectangle( CvArr* _img, CvPoint pt1, CvPoint pt2,
2419              CvScalar color, int thickness,
2420              int line_type, int shift )
2421 {
2422     cv::Mat img = cv::cvarrToMat(_img);
2423     cv::rectangle( img, pt1, pt2, color, thickness, line_type, shift );
2424 }
2425
2426 CV_IMPL void
2427 cvRectangleR( CvArr* _img, CvRect rec,
2428               CvScalar color, int thickness,
2429               int line_type, int shift )
2430 {
2431     cv::Mat img = cv::cvarrToMat(_img);
2432     cv::rectangle( img, rec, color, thickness, line_type, shift );
2433 }
2434
2435 CV_IMPL void
2436 cvCircle( CvArr* _img, CvPoint center, int radius,
2437           CvScalar color, int thickness, int line_type, int shift )
2438 {
2439     cv::Mat img = cv::cvarrToMat(_img);
2440     cv::circle( img, center, radius, color, thickness, line_type, shift );
2441 }
2442
2443 CV_IMPL void
2444 cvEllipse( CvArr* _img, CvPoint center, CvSize axes,
2445            double angle, double start_angle, double end_angle,
2446            CvScalar color, int thickness, int line_type, int shift )
2447 {
2448     cv::Mat img = cv::cvarrToMat(_img);
2449     cv::ellipse( img, center, axes, angle, start_angle, end_angle,
2450         color, thickness, line_type, shift );
2451 }
2452
2453 CV_IMPL void
2454 cvFillConvexPoly( CvArr* _img, const CvPoint *pts, int npts,
2455                   CvScalar color, int line_type, int shift )
2456 {
2457     cv::Mat img = cv::cvarrToMat(_img);
2458     cv::fillConvexPoly( img, (const cv::Point*)pts, npts,
2459                         color, line_type, shift );
2460 }
2461
2462 CV_IMPL void
2463 cvFillPoly( CvArr* _img, CvPoint **pts, const int *npts, int ncontours,
2464             CvScalar color, int line_type, int shift )
2465 {
2466     cv::Mat img = cv::cvarrToMat(_img);
2467
2468     cv::fillPoly( img, (const cv::Point**)pts, npts, ncontours, color, line_type, shift );
2469 }
2470
2471 CV_IMPL void
2472 cvPolyLine( CvArr* _img, CvPoint **pts, const int *npts,
2473             int ncontours, int closed, CvScalar color,
2474             int thickness, int line_type, int shift )
2475 {
2476     cv::Mat img = cv::cvarrToMat(_img);
2477
2478     cv::polylines( img, (const cv::Point**)pts, npts, ncontours,
2479                    closed != 0, color, thickness, line_type, shift );
2480 }
2481
2482 CV_IMPL void
2483 cvPutText( CvArr* _img, const char *text, CvPoint org, const CvFont *_font, CvScalar color )
2484 {
2485     cv::Mat img = cv::cvarrToMat(_img);
2486     CV_Assert( text != 0 && _font != 0);
2487     cv::putText( img, text, org, _font->font_face, (_font->hscale+_font->vscale)*0.5,
2488                 color, _font->thickness, _font->line_type,
2489                 CV_IS_IMAGE(_img) && ((IplImage*)_img)->origin != 0 );
2490 }
2491
2492
2493 CV_IMPL void
2494 cvInitFont( CvFont *font, int font_face, double hscale, double vscale,
2495             double shear, int thickness, int line_type )
2496 {
2497     CV_Assert( font != 0 && hscale > 0 && vscale > 0 && thickness >= 0 );
2498
2499     font->ascii = cv::getFontData(font_face);
2500     font->font_face = font_face;
2501     font->hscale = (float)hscale;
2502     font->vscale = (float)vscale;
2503     font->thickness = thickness;
2504     font->shear = (float)shear;
2505     font->greek = font->cyrillic = 0;
2506     font->line_type = line_type;
2507 }
2508
2509 CV_IMPL void
2510 cvGetTextSize( const char *text, const CvFont *_font, CvSize *_size, int *_base_line )
2511 {
2512     CV_Assert(text != 0 && _font != 0);
2513     cv::Size size = cv::getTextSize( text, _font->font_face, (_font->hscale + _font->vscale)*0.5,
2514                                      _font->thickness, _base_line );
2515     if( _size )
2516         *_size = size;
2517 }
2518
2519 /* End of file. */