PolyLine.cpp 40 KB
Newer Older
1
// PolyLine.cpp ... implementation of CPolyLine class from FreePCB.
2

3
//
4
// implementation for kicad and kbool polygon clipping library
5
//
6
#include <cmath>
7
#include <vector>
8
#include <algorithm>
9

10
#include <fctsys.h>
11
#include <common.h>     // KiROUND
CHARRAS's avatar
CHARRAS committed
12

13 14 15
#include <PolyLine.h>
#include <bezier_curves.h>
#include <polygon_test_point_inside.h>
16
#include <math_for_graphics.h>
17 18
#include <polygon_test_point_inside.h>

19
CPolyLine::CPolyLine()
20
{
21 22
    m_hatchStyle    = NO_HATCH;
    m_hatchPitch    = 0;
23
    m_layer     = 0;
24
    m_utility   = 0;
25 26
}

27

28 29 30 31
// destructor, removes display elements
//
CPolyLine::~CPolyLine()
{
32
    UnHatch();
33 34
}

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
/* Removes corners which create a null segment edge
 * (i.e. when 2 successive corners are at the same location)
 * returns the count of removed corners.
 */
 int CPolyLine::RemoveNullSegments()
{
    int removed = 0;

    unsigned startcountour = 0;
    for( unsigned icnt = 1; icnt < m_CornersList.size(); icnt ++ )
    {
        unsigned last = icnt-1;
        if( m_CornersList[icnt].end_contour )
        {
            last = startcountour;
            startcountour = icnt+1;
        }

        if( ( m_CornersList[last].x == m_CornersList[icnt].x ) &&
            ( m_CornersList[last].y == m_CornersList[icnt].y ) )
        {
            DeleteCorner( icnt );
            icnt--;
            removed ++;
        }

        if( m_CornersList[icnt].end_contour )
        {
            startcountour = icnt+1;
            icnt++;
        }
    }

    return removed;
}

71

72
/**
73 74 75 76 77 78
 * Function NormalizeAreaOutlines
 * Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s)
 * @param aNewPolygonList = a std::vector<CPolyLine*> reference where to store new CPolyLine
 * needed by the normalization
 * @return the polygon count (always >= 1, because there is at least one polygon)
 * There are new polygons only if the polygon count  is > 1
79
 */
80 81
#include "clipper.hpp"
int CPolyLine::NormalizeAreaOutlines( std::vector<CPolyLine*>* aNewPolygonList )
82
{
83 84
    ClipperLib::Polygon raw_polygon;
    ClipperLib::Polygons normalized_polygons;
85

86
    unsigned corners_count = m_CornersList.size();
87

88 89 90 91 92
    KI_POLYGON_SET polysholes;
    KI_POLYGON_WITH_HOLES mainpoly;
    std::vector<KI_POLY_POINT> cornerslist;
    KI_POLYGON_WITH_HOLES_SET all_contours;
    KI_POLYGON poly_tmp;
93

94 95 96
    // Normalize first contour
    unsigned ic    = 0;
    while( ic < corners_count )
97
    {
98 99
        const CPolyPt& corner = m_CornersList[ic++];
        raw_polygon.push_back( ClipperLib::IntPoint( corner.x, corner.y ) );
100

101 102
        if( corner.end_contour )
            break;
103
    }
104

105
    ClipperLib::SimplifyPolygon( raw_polygon, normalized_polygons );
106

107 108
    // enter main outline
    for( unsigned ii = 0; ii < normalized_polygons.size(); ii++ )
109
    {
110 111 112 113 114 115
        ClipperLib::Polygon& polygon = normalized_polygons[ii];
        cornerslist.clear();
        for( unsigned jj = 0; jj < polygon.size(); jj++ )
            cornerslist.push_back( KI_POLY_POINT( (int)polygon[jj].X, (int)polygon[jj].Y ) );
        mainpoly.set( cornerslist.begin(), cornerslist.end() );
        all_contours.push_back(  mainpoly );
116
    }
117

118 119
    // Enter holes
    while( ic < corners_count )
120
    {
121 122 123
        cornerslist.clear();
        raw_polygon.clear();
        normalized_polygons.clear();
124

125 126
        // Normalize current hole and add it to hole list
        while( ic < corners_count )
127
        {
128 129 130 131
            const CPolyPt& corner = m_CornersList[ic++];
            raw_polygon.push_back( ClipperLib::IntPoint( corner.x, corner.y ) );

            if( corner.end_contour )
132
            {
133 134
                ClipperLib::SimplifyPolygon( raw_polygon, normalized_polygons );
                for( unsigned ii = 0; ii < normalized_polygons.size(); ii++ )
135
                {
136 137 138 139 140 141
                    ClipperLib::Polygon& polygon = normalized_polygons[ii];
                    cornerslist.clear();
                    for( unsigned jj = 0; jj < polygon.size(); jj++ )
                        cornerslist.push_back( KI_POLY_POINT( (int)polygon[jj].X, (int)polygon[jj].Y ) );
                    bpl::set_points( poly_tmp, cornerslist.begin(), cornerslist.end() );
                    polysholes.push_back( poly_tmp );
142
                }
143
                break;
144 145
            }
        }
146 147
    }
    all_contours -= polysholes;
148

149 150
    // copy polygon with holes to destination
    RemoveAllContours();
151

152
    #define outlines all_contours
153

154 155 156 157
    for( unsigned ii = 0; ii < outlines.size(); ii++ )
    {
        CPolyLine* polyline = this;
        if( ii > 0 )
158
        {
159 160 161
            polyline = new CPolyLine;
            polyline->ImportSettings( this );
            aNewPolygonList->push_back( polyline );
162
        }
163

164 165 166 167
        KI_POLYGON_WITH_HOLES& curr_poly = outlines[ii];
        KI_POLYGON_WITH_HOLES::iterator_type corner = curr_poly.begin();
        // enter main contour
        while( corner != curr_poly.end() )
168
        {
169 170
            polyline->AppendCorner( corner->x(), corner->y() );
            corner++;
171
        }
172 173 174 175 176
        polyline->CloseLastContour();

        // add holes (set of polygons)
        KI_POLYGON_WITH_HOLES::iterator_holes_type hole = curr_poly.begin_holes();
        while( hole != curr_poly.end_holes() )
177
        {
178 179 180 181 182 183 184 185 186
            KI_POLYGON::iterator_type hole_corner = hole->begin();
            // create area with external contour: Recreate only area edges, NOT holes
            while( hole_corner != hole->end() )
            {
                polyline->AppendCorner( hole_corner->x(), hole_corner->y() );
                hole_corner++;
            }
            polyline->CloseLastContour();
            hole++;
187
        }
188 189

        polyline->RemoveNullSegments();
190 191
    }

192
    return outlines.size();
193
}
194

195 196 197 198 199 200 201 202 203 204
/**
 * Function ImportSettings
 * Copy settings (layer, hatch styles) from aPoly
 */
void CPolyLine::ImportSettings( const CPolyLine * aPoly )
{
    SetLayer( aPoly->GetLayer() );
    SetHatchStyle( aPoly->GetHatchStyle() );
    SetHatchPitch( aPoly->GetHatchPitch() );
}
205

206 207 208
/* initialize a contour
 * set layer, hatch style, and starting point
 */
209
void CPolyLine::Start( int layer, int x, int y, int hatch )
210
{
211
    m_layer = layer;
212
    SetHatchStyle( (enum HATCH_STYLE) hatch );
213
    CPolyPt poly_pt( x, y );
214
    poly_pt.end_contour = false;
215

216
    m_CornersList.push_back( poly_pt );
217 218
}

219

220 221
// add a corner to unclosed polyline
//
222
void CPolyLine::AppendCorner( int x, int y )
223
{
224
    UnHatch();
225
    CPolyPt poly_pt( x, y );
226
    poly_pt.end_contour = false;
227

228
    // add entries for new corner
229
    m_CornersList.push_back( poly_pt );
230 231
}

232

233 234
// close last polyline contour
//
235
void CPolyLine::CloseLastContour()
236
{
237
    m_CornersList[m_CornersList.size() - 1].end_contour = true;
238 239
}

240

241 242 243 244
// move corner of polyline
//
void CPolyLine::MoveCorner( int ic, int x, int y )
{
245
    UnHatch();
246 247
    m_CornersList[ic].x = x;
    m_CornersList[ic].y = y;
248
    Hatch();
249 250
}

251

252 253
// delete corner and adjust arrays
//
254
void CPolyLine::DeleteCorner( int ic )
255
{
256
    UnHatch();
257 258
    int     icont   = GetContour( ic );
    int     iend    = GetContourEnd( icont );
259
    bool    closed = icont < GetContoursCount() - 1 || GetClosed();
260

261
    if( !closed )
262 263
    {
        // open contour, must be last contour
264
        m_CornersList.erase( m_CornersList.begin() + ic );
265 266 267 268
    }
    else
    {
        // closed contour
269
        m_CornersList.erase( m_CornersList.begin() + ic );
270

271
        if( ic == iend )
272
            m_CornersList[ic - 1].end_contour = true;
273
    }
274

275
    if( closed && GetContourSize( icont ) < 3 )
276 277 278 279
    {
        // delete the entire contour
        RemoveContour( icont );
    }
280 281
}

282

283
/******************************************/
284
void CPolyLine::RemoveContour( int icont )
285
/******************************************/
286

287 288 289 290 291
/**
 * Function RemoveContour
 * @param icont = contour number to remove
 * remove a contour only if there is more than 1 contour
 */
292
{
293
    UnHatch();
294 295
    int istart  = GetContourStart( icont );
    int iend    = GetContourEnd( icont );
296

297
    int polycount = GetContoursCount();
298

299
    if( icont == 0 && polycount == 1 )
300 301 302 303
    {
        // remove the only contour
        wxASSERT( 0 );
    }
304
    else if( icont == polycount - 1 )
305 306
    {
        // remove last contour
307
        m_CornersList.erase( m_CornersList.begin() + istart, m_CornersList.end() );
308 309 310 311 312 313
    }
    else
    {
        // remove closed contour
        for( int ic = iend; ic>=istart; ic-- )
        {
314
            m_CornersList.erase( m_CornersList.begin() + ic );
315 316
        }
    }
317

318
    Hatch();
319 320
}

321

322
CPolyLine* CPolyLine::Chamfer( unsigned int aDistance )
323
{
324
    CPolyLine* newPoly = new CPolyLine;
325 326 327

    if( !aDistance )
    {
328 329
        newPoly->Copy( this );
        return newPoly;
330 331
    }

332
    int polycount = GetContoursCount();
333

334
    for( int contour = 0; contour < polycount; contour++ )
335
    {
336 337
        unsigned int    startIndex  = GetContourStart( contour );
        unsigned int    endIndex    = GetContourEnd( contour );
338

339 340
        for( unsigned int index = startIndex; index <= endIndex; index++ )
        {
341 342
            int         x1, y1, nx, ny;
            long long   xa, ya, xb, yb;
343

344 345
            x1  = m_CornersList[index].x;
            y1  = m_CornersList[index].y;
346

347 348
            if( index == startIndex )
            {
349 350
                xa  = m_CornersList[endIndex].x - x1;
                ya  = m_CornersList[endIndex].y - y1;
351 352 353
            }
            else
            {
354 355
                xa  = m_CornersList[index - 1].x - x1;
                ya  = m_CornersList[index - 1].y - y1;
356
            }
357

358 359
            if( index == endIndex )
            {
360 361
                xb  = m_CornersList[startIndex].x - x1;
                yb  = m_CornersList[startIndex].y - y1;
362 363 364
            }
            else
            {
365 366
                xb  = m_CornersList[index + 1].x - x1;
                yb  = m_CornersList[index + 1].y - y1;
367
            }
368

369 370 371
            unsigned int    lena        = (unsigned int) sqrt( (double) (xa * xa + ya * ya) );
            unsigned int    lenb        = (unsigned int) sqrt( (double) (xb * xb + yb * yb) );
            unsigned int    distance    = aDistance;
372

373
            // Chamfer one half of an edge at most
374 375
            if( 0.5 * lena < distance )
                distance = (unsigned int) (0.5 * (double) lena);
376

377 378
            if( 0.5 * lenb < distance )
                distance = (unsigned int) (0.5 * (double) lenb);
379

380 381
            nx  = (int) ( (double) (distance * xa) / sqrt( (double) (xa * xa + ya * ya) ) );
            ny  = (int) ( (double) (distance * ya) / sqrt( (double) (xa * xa + ya * ya) ) );
382

383 384 385 386
            if( index == startIndex )
                newPoly->Start( GetLayer(), x1 + nx, y1 + ny, GetHatchStyle() );
            else
                newPoly->AppendCorner( x1 + nx, y1 + ny );
387

388 389
            nx  = (int) ( (double) (distance * xb) / sqrt( (double) (xb * xb + yb * yb) ) );
            ny  = (int) ( (double) (distance * yb) / sqrt( (double) (xb * xb + yb * yb) ) );
390 391
            newPoly->AppendCorner( x1 + nx, y1 + ny );
        }
392

393
        newPoly->CloseLastContour();
394 395 396 397 398 399
    }

    return newPoly;
}


400
CPolyLine* CPolyLine::Fillet( unsigned int aRadius, unsigned int aSegments )
401
{
402
    CPolyLine* newPoly = new CPolyLine;
403 404 405

    if( !aRadius )
    {
406 407
        newPoly->Copy( this );
        return newPoly;
408 409
    }

410
    int polycount = GetContoursCount();
411

412
    for( int contour = 0; contour < polycount; contour++ )
413
    {
414 415
        unsigned int    startIndex  = GetContourStart( contour );
        unsigned int    endIndex    = GetContourEnd( contour );
416

417 418
        for( unsigned int index = startIndex; index <= endIndex; index++ )
        {
419 420 421 422
            int         x1, y1; // Current vertex
            long long   xa, ya; // Previous vertex
            long long   xb, yb; // Next vertex
            double      nx, ny;
423

424 425
            x1  = m_CornersList[index].x;
            y1  = m_CornersList[index].y;
426

427 428
            if( index == startIndex )
            {
429 430
                xa  = m_CornersList[endIndex].x - x1;
                ya  = m_CornersList[endIndex].y - y1;
431 432 433
            }
            else
            {
434 435
                xa  = m_CornersList[index - 1].x - x1;
                ya  = m_CornersList[index - 1].y - y1;
436
            }
437

438 439
            if( index == endIndex )
            {
440 441
                xb  = m_CornersList[startIndex].x - x1;
                yb  = m_CornersList[startIndex].y - y1;
442 443 444
            }
            else
            {
445 446
                xb  = m_CornersList[index + 1].x - x1;
                yb  = m_CornersList[index + 1].y - y1;
447
            }
448

449 450 451
            double          lena    = sqrt( (double) (xa * xa + ya * ya) );
            double          lenb    = sqrt( (double) (xb * xb + yb * yb) );
            double          cosine  = ( xa * xb + ya * yb ) / ( lena * lenb );
452

453 454
            unsigned int    radius  = aRadius;
            double          denom   = sqrt( 2.0 / ( 1 + cosine ) - 1 );
455

456
            // Limit rounding distance to one half of an edge
457 458
            if( 0.5 * lena * denom < radius )
                radius = (unsigned int) (0.5 * lena * denom);
459

460 461
            if( 0.5 * lenb * denom < radius )
                radius = (unsigned int) (0.5 * lenb * denom);
462 463

            // Calculate fillet arc absolute center point (xc, yx)
464 465 466 467 468
            double  k       = radius / sqrt( .5 * ( 1 - cosine ) );
            double  lenab   = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
                                    ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
            double  xc  = x1 + k * ( xa / lena + xb / lenb ) / lenab;
            double  yc  = y1 + k * ( ya / lena + yb / lenb ) / lenab;
469 470

            // Calculate arc start and end vectors
471 472 473 474 475
            k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
            double  xs  = x1 + k * xa / lena - xc;
            double  ys  = y1 + k * ya / lena - yc;
            double  xe  = x1 + k * xb / lenb - xc;
            double  ye  = y1 + k * yb / lenb - yc;
476 477

            // Cosine of arc angle
478
            double  argument = ( xs * xe + ys * ye ) / ( radius * radius );
479 480 481 482 483 484

            if( argument < -1 ) // Just in case...
                argument = -1;
            else if( argument > 1 )
                argument = 1;

485
            double  arcAngle = acos( argument );
486

487
            // Calculate the number of segments
488
            double  tempSegments = (double) aSegments * ( arcAngle / ( 2 * M_PI ) );
489

490
            if( tempSegments - (int) tempSegments > 0 )
491 492
                tempSegments++;

493 494 495 496
            unsigned int    segments = (unsigned int) tempSegments;

            double          deltaAngle  = arcAngle / segments;
            double          startAngle  = atan2( -ys, xs );
497 498

            // Flip arc for inner corners
499
            if( xa * yb - ya * xb <= 0 )
500 501
                deltaAngle *= -1;

502 503 504
            nx  = xc + xs + 0.5;
            ny  = yc + ys + 0.5;

505
            if( index == startIndex )
506
                newPoly->Start( GetLayer(), (int) nx, (int) ny, GetHatchStyle() );
507
            else
508
                newPoly->AppendCorner( (int) nx, (int) ny );
509 510

            unsigned int nVertices = 0;
511

512 513
            for( unsigned int j = 0; j < segments; j++ )
            {
514 515 516
                nx  = xc + cos( startAngle + (j + 1) * deltaAngle ) * radius + 0.5;
                ny  = yc - sin( startAngle + (j + 1) * deltaAngle ) * radius + 0.5;
                newPoly->AppendCorner( (int) nx, (int) ny );
517 518 519
                nVertices++;
            }
        }
520

521
        newPoly->CloseLastContour();
522
    }
523

524 525 526 527
    return newPoly;
}


528
/******************************************/
529
void CPolyLine::RemoveAllContours( void )
530
/******************************************/
531

532 533 534 535 536 537
/**
 * function RemoveAllContours
 * removes all corners from the lists.
 * Others params are not chnaged
 */
{
538
    m_CornersList.clear();
539 540 541
}


542 543
/**
 * Function InsertCorner
544 545 546 547 548 549
 * insert a new corner between two existing corners
 * @param ic = index for the insertion point: the corner is inserted AFTER ic
 * @param x, y = coordinates corner to insert
 */
void CPolyLine::InsertCorner( int ic, int x, int y )
{
550
    UnHatch();
551

552
    if( (unsigned) (ic) >= m_CornersList.size() )
553
    {
554
        m_CornersList.push_back( CPolyPt( x, y ) );
555 556 557
    }
    else
    {
558
        m_CornersList.insert( m_CornersList.begin() + ic + 1, CPolyPt( x, y ) );
559 560
    }

561
    if( (unsigned) (ic + 1) < m_CornersList.size() )
562
    {
563
        if( m_CornersList[ic].end_contour )
564
        {
565 566
            m_CornersList[ic + 1].end_contour   = true;
            m_CornersList[ic].end_contour       = false;
567 568
        }
    }
569

570
    Hatch();
571 572
}

573

574 575
// undraw polyline by removing all graphic elements from display list
//
576
void CPolyLine::UnHatch()
577
{
578
    m_HatchLines.clear();
579 580 581
}


582 583
int CPolyLine::GetEndContour( int ic )
{
584
    return m_CornersList[ic].end_contour;
585 586
}

587

588 589
CRect CPolyLine::GetBounds()
{
590 591
    CRect r = GetCornerBounds();
    return r;
592 593
}

594

595 596
CRect CPolyLine::GetCornerBounds()
{
597 598 599 600
    CRect r;

    r.left  = r.bottom = INT_MAX;
    r.right = r.top = INT_MIN;
601

602
    for( unsigned i = 0; i<m_CornersList.size(); i++ )
603
    {
604 605 606 607
        r.left      = std::min( r.left, m_CornersList[i].x );
        r.right     = std::max( r.right, m_CornersList[i].x );
        r.bottom    = std::min( r.bottom, m_CornersList[i].y );
        r.top       = std::max( r.top, m_CornersList[i].y );
608 609 610
    }

    return r;
611 612
}

613

614 615
CRect CPolyLine::GetCornerBounds( int icont )
{
616 617 618 619
    CRect r;

    r.left  = r.bottom = INT_MAX;
    r.right = r.top = INT_MIN;
620 621 622
    int istart  = GetContourStart( icont );
    int iend    = GetContourEnd( icont );

623 624
    for( int i = istart; i<=iend; i++ )
    {
625 626 627 628
        r.left      = std::min( r.left, m_CornersList[i].x );
        r.right     = std::max( r.right, m_CornersList[i].x );
        r.bottom    = std::min( r.bottom, m_CornersList[i].y );
        r.top       = std::max( r.top, m_CornersList[i].y );
629 630 631
    }

    return r;
632 633
}

634 635 636

int CPolyLine::GetNumCorners()
{
637
    return m_CornersList.size();
638 639
}

640 641 642 643

int CPolyLine::GetNumSides()
{
    if( GetClosed() )
644
        return m_CornersList.size();
645
    else
646
        return m_CornersList.size() - 1;
647 648
}

649

650
int CPolyLine::GetContoursCount()
651
{
652 653
    int ncont = 0;

654
    if( !m_CornersList.size() )
655 656
        return 0;

657 658
    for( unsigned ic = 0; ic < m_CornersList.size(); ic++ )
        if( m_CornersList[ic].end_contour )
659 660
            ncont++;

661 662


663
    if( !m_CornersList[m_CornersList.size() - 1].end_contour )
664
        ncont++;
665

666
    return ncont;
667 668
}

669

670 671
int CPolyLine::GetContour( int ic )
{
672 673 674 675
    int ncont = 0;

    for( int i = 0; i<ic; i++ )
    {
676
        if( m_CornersList[i].end_contour )
677 678 679 680
            ncont++;
    }

    return ncont;
681 682
}

683

684 685
int CPolyLine::GetContourStart( int icont )
{
686 687 688 689
    if( icont == 0 )
        return 0;

    int ncont = 0;
690

691
    for( unsigned i = 0; i<m_CornersList.size(); i++ )
692
    {
693
        if( m_CornersList[i].end_contour )
694 695
        {
            ncont++;
696

697 698 699 700 701 702 703
            if( ncont == icont )
                return i + 1;
        }
    }

    wxASSERT( 0 );
    return 0;
704 705
}

706

707 708
int CPolyLine::GetContourEnd( int icont )
{
709 710 711
    if( icont < 0 )
        return 0;

712 713
    if( icont == GetContoursCount() - 1 )
        return m_CornersList.size() - 1;
714 715

    int ncont = 0;
716

717
    for( unsigned i = 0; i<m_CornersList.size(); i++ )
718
    {
719
        if( m_CornersList[i].end_contour )
720 721 722
        {
            if( ncont == icont )
                return i;
723

724 725 726 727 728 729
            ncont++;
        }
    }

    wxASSERT( 0 );
    return 0;
730 731
}

732

733 734
int CPolyLine::GetContourSize( int icont )
{
735
    return GetContourEnd( icont ) - GetContourStart( icont ) + 1;
736 737 738
}


739 740
int CPolyLine::GetClosed()
{
741
    if( m_CornersList.size() == 0 )
742 743
        return 0;
    else
744
        return m_CornersList[m_CornersList.size() - 1].end_contour;
745 746
}

747

748
// Creates hatch lines inside the outline of the complex polygon
749
//
750
// sort function used in ::Hatch to sort points by descending wxPoint.x values
751
bool sort_ends_by_descending_X( const wxPoint& ref, const wxPoint& tst )
752 753 754
{
    return tst.x < ref.x;
}
755 756


757 758
void CPolyLine::Hatch()
{
759
    m_HatchLines.clear();
760

761
    if( m_hatchStyle == NO_HATCH || m_hatchPitch == 0 )
762 763
        return;

764
    if( !GetClosed() ) // If not closed, the poly is beeing created and not finalised. Not not hatch
765 766 767
        return;

    // define range for hatch lines
768 769 770 771 772
    int min_x   = m_CornersList[0].x;
    int max_x   = m_CornersList[0].x;
    int min_y   = m_CornersList[0].y;
    int max_y   = m_CornersList[0].y;

773
    for( unsigned ic = 1; ic < m_CornersList.size(); ic++ )
774
    {
775 776
        if( m_CornersList[ic].x < min_x )
            min_x = m_CornersList[ic].x;
777

778 779
        if( m_CornersList[ic].x > max_x )
            max_x = m_CornersList[ic].x;
780

781 782
        if( m_CornersList[ic].y < min_y )
            min_y = m_CornersList[ic].y;
783

784 785
        if( m_CornersList[ic].y > max_y )
            max_y = m_CornersList[ic].y;
786
    }
787

788
    // Calculate spacing betwwen 2 hatch lines
789 790
    int spacing;

791 792
    if( m_hatchStyle == DIAGONAL_EDGE )
        spacing = m_hatchPitch;
793
    else
794
        spacing = m_hatchPitch * 2;
795

796
    // set the "lenght" of hatch lines (the lenght on horizontal axis)
797
    double  hatch_line_len = m_hatchPitch;
798 799

    // To have a better look, give a slope depending on the layer
800 801 802 803 804
    int     layer = GetLayer();
    int     slope_flag = (layer & 1) ? 1 : -1;  // 1 or -1
    double  slope = 0.707106 * slope_flag;      // 45 degrees slope
    int     max_a, min_a;

805 806
    if( slope_flag == 1 )
    {
807 808
        max_a   = (int) (max_y - slope * min_x);
        min_a   = (int) (min_y - slope * max_x);
809 810 811
    }
    else
    {
812 813
        max_a   = (int) (max_y - slope * max_x);
        min_a   = (int) (min_y - slope * min_x);
814
    }
815

816
    min_a = (min_a / spacing) * spacing;
817

818 819
    // calculate an offset depending on layer number,
    // for a better look of hatches on a multilayer board
820 821
    int offset = (layer * 7) / 8;
    min_a += offset;
822

823
    // now calculate and draw hatch lines
824
    int nc = m_CornersList.size();
825

826
    // loop through hatch lines
827
    #define MAXPTS 200      // Usually we store only few values per one hatch line
828
                            // depending on the compexity of the zone outline
829

830
    static std::vector <wxPoint> pointbuffer;
831
    pointbuffer.clear();
832
    pointbuffer.reserve( MAXPTS + 2 );
833

834
    for( int a = min_a; a < max_a; a += spacing )
835 836
    {
        // get intersection points for this hatch line
837

838
        // Note: because we should have an even number of intersections with the
839 840
        // current hatch line and the zone outline (a closed polygon,
        // or a set of closed polygons), if an odd count is found
841 842 843
        // we skip this line (should not occur)
        pointbuffer.clear();
        int i_start_contour = 0;
844

845
        for( int ic = 0; ic<nc; ic++ )
846
        {
847 848 849
            double  x, y, x2, y2;
            int     ok;

850
            if( m_CornersList[ic].end_contour || ( ic == (int) (m_CornersList.size() - 1) ) )
851
            {
852
                ok = FindLineSegmentIntersection( a, slope,
853 854 855 856
                                                  m_CornersList[ic].x, m_CornersList[ic].y,
                                                  m_CornersList[i_start_contour].x,
                                                  m_CornersList[i_start_contour].y,
                                                  &x, &y, &x2, &y2 );
857
                i_start_contour = ic + 1;
858
            }
859 860 861
            else
            {
                ok = FindLineSegmentIntersection( a, slope,
862 863 864
                                                  m_CornersList[ic].x, m_CornersList[ic].y,
                                                  m_CornersList[ic + 1].x, m_CornersList[ic + 1].y,
                                                  &x, &y, &x2, &y2 );
865
            }
866

867 868
            if( ok )
            {
869
                wxPoint point( (int) x, (int) y );
870 871
                pointbuffer.push_back( point );
            }
872

873 874
            if( ok == 2 )
            {
875
                wxPoint point( (int) x2, (int) y2 );
876 877
                pointbuffer.push_back( point );
            }
878

879 880 881 882 883 884
            if( pointbuffer.size() >= MAXPTS )    // overflow
            {
                wxASSERT( 0 );
                break;
            }
        }
885

886
        // ensure we have found an even intersection points count
887 888
        // because intersections are the ends of segments
        // inside the polygon(s) and a segment has 2 ends.
889 890 891
        // if not, this is a strange case (a bug ?) so skip this hatch
        if( pointbuffer.size() % 2 != 0 )
            continue;
892

893 894 895
        // sort points in order of descending x (if more than 2) to
        // ensure the starting point and the ending point of the same segment
        // are stored one just after the other.
896
        if( pointbuffer.size() > 2 )
897
            sort( pointbuffer.begin(), pointbuffer.end(), sort_ends_by_descending_X );
898

899
        // creates lines or short segments inside the complex polygon
900
        for( unsigned ip = 0; ip < pointbuffer.size(); ip += 2 )
901
        {
902
            double dx = pointbuffer[ip + 1].x - pointbuffer[ip].x;
903

904 905 906
            // Push only one line for diagonal hatch,
            // or for small lines < twice the line len
            // else push 2 small lines
907
            if( m_hatchStyle == DIAGONAL_FULL || fabs( dx ) < 2 * hatch_line_len )
908
            {
909
                m_HatchLines.push_back( CSegment( pointbuffer[ip], pointbuffer[ip + 1] ) );
910 911 912
            }
            else
            {
913 914
                double  dy      = pointbuffer[ip + 1].y - pointbuffer[ip].y;
                double  slope   = dy / dx;
915

916
                if( dx > 0 )
917
                    dx = hatch_line_len;
918
                else
919
                    dx = -hatch_line_len;
920

921 922 923 924
                double  x1  = pointbuffer[ip].x + dx;
                double  x2  = pointbuffer[ip + 1].x - dx;
                double  y1  = pointbuffer[ip].y + dx * slope;
                double  y2  = pointbuffer[ip + 1].y - dx * slope;
925

926 927
                m_HatchLines.push_back( CSegment( pointbuffer[ip].x,
                                                  pointbuffer[ip].y,
928
                                                  KiROUND( x1 ), KiROUND( y1 ) ) );
929

930 931
                m_HatchLines.push_back( CSegment( pointbuffer[ip + 1].x,
                                                  pointbuffer[ip + 1].y,
932
                                                  KiROUND( x2 ), KiROUND( y2 ) ) );
933
            }
934
        }
935
    }
936 937
}

938

939 940
// test to see if a point is inside polyline
//
941
bool CPolyLine::TestPointInside( int px, int py )
942
{
943
    if( !GetClosed() )
944
    {
945
        wxASSERT( 0 );
946
    }
947

948
    // Test all polygons.
949
    // Since the first is the main outline, and other are holes,
950 951 952
    // if the tested point is inside only one contour, it is inside the whole polygon
    // (in fact inside the main outline, and outside all holes).
    // if inside 2 contours (the main outline + an hole), it is outside the poly.
953 954 955
    int     polycount   = GetContoursCount();
    bool    inside      = false;

956
    for( int icont = 0; icont < polycount; icont++ )
957
    {
958 959
        int istart  = GetContourStart( icont );
        int iend    = GetContourEnd( icont );
960

961
        // Test this polygon:
962
        if( TestPointInsidePolygon( m_CornersList, istart, iend, px, py ) ) // test point inside the current polygon
963 964
            inside = not inside;
    }
965

966
    return inside;
967 968
}

969

970 971
// copy data from another poly, but don't draw it
//
972
void CPolyLine::Copy( CPolyLine* src )
973
{
974
    UnHatch();
975 976
    m_hatchStyle    = src->m_hatchStyle;
    m_hatchPitch    = src->m_hatchPitch;
977
    // copy corners, using vector copy
978
    m_CornersList = src->m_CornersList;
979 980
}

981 982 983 984

/*******************************************/
bool CPolyLine::IsCutoutContour( int icont )
/*******************************************/
985

986 987 988 989
/*
 * return true if the corner icont is inside the outline (i.e it is a hole)
 */
{
990 991
    int ncont = GetContour( icont );

992
    if( ncont == 0 ) // the first contour is the main outline, not an hole
993
        return false;
994

995
    return true;
996 997
}

998

999 1000
void CPolyLine::MoveOrigin( int x_off, int y_off )
{
1001
    UnHatch();
1002

1003 1004 1005 1006 1007 1008
    for( int ic = 0; ic < GetNumCorners(); ic++ )
    {
        SetX( ic, GetX( ic ) + x_off );
        SetY( ic, GetY( ic ) + y_off );
    }

1009
    Hatch();
1010 1011 1012 1013
}


// Set various parameters:
1014 1015
// the calling function should UnHatch() before calling them,
// and Draw() after
1016
//
1017 1018
void CPolyLine::SetX( int ic, int x )
{
1019
    m_CornersList[ic].x = x;
1020 1021 1022 1023 1024
}


void CPolyLine::SetY( int ic, int y )
{
1025
    m_CornersList[ic].y = y;
1026 1027
}

1028 1029 1030

void CPolyLine::SetEndContour( int ic, bool end_contour )
{
1031
    m_CornersList[ic].end_contour = end_contour;
1032
}
1033

1034
/*
1035 1036
 * AppendArc:
 * adds segments to current contour to approximate the given arc
1037
 */
1038
void CPolyLine::AppendArc( int xi, int yi, int xf, int yf, int xc, int yc, int num )
1039
{
1040
    // get radius
1041
    double  radius = hypot( (double) (xi - xc), (double) (yi - yc) );
1042 1043

    // get angles of start and finish
1044 1045 1046 1047
    double  th_i    = atan2( (double) (yi - yc), (double) (xi - xc) );
    double  th_f    = atan2( (double) (yf - yc), (double) (xf - xc) );
    double  th_d    = (th_f - th_i) / (num - 1);
    double  theta   = th_i;
1048 1049

    // generate arc
1050
    for( int ic = 0; ic < num; ic++ )
1051
    {
1052 1053
        int x   = KiROUND( xc + radius * cos( theta ) );
        int y   = KiROUND( yc + radius * sin( theta ) );
1054
        AppendCorner( x, y );
1055 1056 1057
        theta += th_d;
    }

1058
    CloseLastContour();
1059
}
charras's avatar
charras committed
1060

1061

charras's avatar
charras committed
1062
// Bezier Support
1063
void CPolyLine::AppendBezier( int x1, int y1, int x2, int y2, int x3, int y3 )
1064
{
charras's avatar
charras committed
1065 1066
    std::vector<wxPoint> bezier_points;

1067 1068 1069 1070
    bezier_points = Bezier2Poly( x1, y1, x2, y2, x3, y3 );

    for( unsigned int i = 0; i < bezier_points.size(); i++ )
        AppendCorner( bezier_points[i].x, bezier_points[i].y );
charras's avatar
charras committed
1071 1072
}

1073 1074

void CPolyLine::AppendBezier( int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4 )
1075
{
charras's avatar
charras committed
1076 1077
    std::vector<wxPoint> bezier_points;

1078 1079 1080 1081
    bezier_points = Bezier2Poly( x1, y1, x2, y2, x3, y3, x4, y4 );

    for( unsigned int i = 0; i < bezier_points.size(); i++ )
        AppendCorner( bezier_points[i].x, bezier_points[i].y );
charras's avatar
charras committed
1082
}
1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102


/*
 * Function Distance
 * Calculates the distance between a segment and a polygon (with holes):
 * param aStart is the starting point of the segment.
 * param aEnd is the ending point of the segment.
 * param aWidth is the width of the segment.
 * return distance between the segment and outline.
 *               0 if segment intersects or is inside
 */
int CPolyLine::Distance( wxPoint aStart, wxPoint aEnd, int aWidth )
{
    // We calculate the min dist between the segment and each outline segment
    // However, if the segment to test is inside the outline, and does not cross
    // any edge, it can be seen outside the polygon.
    // Therefore test if a segment end is inside ( testing only one end is enough )
    if( TestPointInside( aStart.x, aStart.y ) )
        return 0;

1103 1104
    int distance    = INT_MAX;
    int polycount   = GetContoursCount();
1105 1106 1107

    for( int icont = 0; icont < polycount; icont++ )
    {
1108 1109
        int ic_start    = GetContourStart( icont );
        int ic_end      = GetContourEnd( icont );
1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128

        // now test spacing between area outline and segment
        for( int ic2 = ic_start; ic2 <= ic_end; ic2++ )
        {
            int bx1 = GetX( ic2 );
            int by1 = GetY( ic2 );
            int bx2, by2;

            if( ic2 == ic_end )
            {
                bx2 = GetX( ic_start );
                by2 = GetY( ic_start );
            }
            else
            {
                bx2 = GetX( ic2 + 1 );
                by2 = GetY( ic2 + 1 );
            }

1129
            int d = GetClearanceBetweenSegments( bx1, by1, bx2, by2, 0,
1130
                                                 aStart.x, aStart.y, aEnd.x, aEnd.y,
1131
                                                 aWidth,
1132
                                                 1,    // min clearance, should be > 0
1133
                                                 NULL, NULL );
1134

1135 1136
            if( distance > d )
                distance = d;
1137

1138 1139 1140 1141 1142 1143 1144 1145
            if( distance <= 0 )
                return 0;
        }
    }

    return distance;
}

1146

1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160
/*
 * Function Distance
 * Calculates the distance between a point and polygon (with holes):
 * param aPoint is the coordinate of the point.
 * return distance between the point and outline.
 *               0 if the point is inside
 */
int CPolyLine::Distance( const wxPoint& aPoint )
{
    // We calculate the dist between the point and each outline segment
    // If the point is inside the outline, the dist is 0.
    if( TestPointInside( aPoint.x, aPoint.y ) )
        return 0;

1161 1162
    int distance    = INT_MAX;
    int polycount   = GetContoursCount();
1163 1164 1165

    for( int icont = 0; icont < polycount; icont++ )
    {
1166 1167
        int ic_start    = GetContourStart( icont );
        int ic_end      = GetContourEnd( icont );
1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187

        // now test spacing between area outline and segment
        for( int ic2 = ic_start; ic2 <= ic_end; ic2++ )
        {
            int bx1 = GetX( ic2 );
            int by1 = GetY( ic2 );
            int bx2, by2;

            if( ic2 == ic_end )
            {
                bx2 = GetX( ic_start );
                by2 = GetY( ic_start );
            }
            else
            {
                bx2 = GetX( ic2 + 1 );
                by2 = GetY( ic2 + 1 );
            }

            int d = KiROUND( GetPointToLineSegmentDistance( aPoint.x, aPoint.y,
1188
                                                            bx1, by1, bx2, by2 ) );
1189 1190 1191

            if( distance > d )
                distance = d;
1192

1193 1194 1195 1196 1197 1198 1199
            if( distance <= 0 )
                return 0;
        }
    }

    return distance;
}
1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270


/**
 * Function CopyPolysListToKiPolygonWithHole
 * converts the outline contours aPolysList to a KI_POLYGON_WITH_HOLES
 *
 * @param aPolysList = the list of corners of contours
 * @param aPolygoneWithHole = a KI_POLYGON_WITH_HOLES to populate
 */
void CopyPolysListToKiPolygonWithHole( const std::vector<CPolyPt>&  aPolysList,
                                       KI_POLYGON_WITH_HOLES&       aPolygoneWithHole )
{
    unsigned    corners_count = aPolysList.size();

    std::vector<KI_POLY_POINT> cornerslist;
    KI_POLYGON  poly;

    // Enter main outline: this is the first contour
    unsigned    ic = 0;

    while( ic < corners_count )
    {
        const CPolyPt& corner = aPolysList[ic++];
        cornerslist.push_back( KI_POLY_POINT( corner.x, corner.y ) );

        if( corner.end_contour )
            break;
    }

    aPolygoneWithHole.set( cornerslist.begin(), cornerslist.end() );

    // Enter holes: they are next contours (when exist)
    if( ic < corners_count )
    {
        KI_POLYGON_SET holePolyList;

        while( ic < corners_count )
        {
            cornerslist.clear();

            while( ic < corners_count )
            {
                const CPolyPt& corner = aPolysList[ic++];
                cornerslist.push_back( KI_POLY_POINT( corner.x, corner.y ) );

                if( corner.end_contour )
                    break;
            }

            bpl::set_points( poly, cornerslist.begin(), cornerslist.end() );
            holePolyList.push_back( poly );
        }

        aPolygoneWithHole.set_holes( holePolyList.begin(), holePolyList.end() );
    }
}

/**
 * Function ConvertPolysListWithHolesToOnePolygon
 * converts the outline contours aPolysListWithHoles with holes to one polygon
 * with no holes (only one contour)
 * holes are linked to main outlines by overlap segments, to give only one polygon
 *
 * @param aPolysListWithHoles = the list of corners of contours (haing holes
 * @param aOnePolyList = a polygon with no holes
 */
void ConvertPolysListWithHolesToOnePolygon( const std::vector<CPolyPt>&  aPolysListWithHoles,
                                            std::vector<CPolyPt>&  aOnePolyList )
{
    unsigned corners_count = aPolysListWithHoles.size();

1271
    int      polycount = 0;
1272 1273 1274 1275 1276 1277 1278 1279
    for( unsigned ii = 0; ii < corners_count; ii++ )
    {
        const CPolyPt& corner = aPolysListWithHoles[ii];

        if( corner.end_contour )
            polycount++;
    }

1280 1281
    // If polycount<= 1, there is no holes found, and therefore just copy the polygon.
    if( polycount <= 1 )
1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330
    {
        aOnePolyList = aPolysListWithHoles;
        return;
    }

    // Holes are found: convert them to only one polygon with overlap segments
    KI_POLYGON_SET polysholes;
    KI_POLYGON_SET mainpoly;
    KI_POLYGON poly_tmp;
    std::vector<KI_POLY_POINT> cornerslist;
    corners_count = aPolysListWithHoles.size();

    unsigned ic    = 0;
    // enter main outline
    while( ic < corners_count )
    {
        const CPolyPt& corner = aPolysListWithHoles[ic++];
        cornerslist.push_back( KI_POLY_POINT( corner.x, corner.y ) );

        if( corner.end_contour )
            break;
    }
    bpl::set_points( poly_tmp, cornerslist.begin(), cornerslist.end() );
    mainpoly.push_back( poly_tmp );

    while( ic < corners_count )
    {
        cornerslist.clear();
        {
            while( ic < corners_count )
            {
                const CPolyPt& corner = aPolysListWithHoles[ic++];
                cornerslist.push_back( KI_POLY_POINT( corner.x, corner.y ) );

                if( corner.end_contour )
                    break;
            }

            bpl::set_points( poly_tmp, cornerslist.begin(), cornerslist.end() );
            polysholes.push_back( poly_tmp );
        }
    }

    mainpoly -= polysholes;

    // copy polygon with no holes to destination
    // We should have only one polygon in list
    wxASSERT( mainpoly.size() != 1 );

1331 1332
    KI_POLYGON& poly_nohole = mainpoly[0];
    CPolyPt   corner( 0, 0, false );
1333

1334 1335 1336 1337 1338 1339
    for( unsigned jj = 0; jj < poly_nohole.size(); jj++ )
    {
        KI_POLY_POINT point = *(poly_nohole.begin() + jj);
        corner.x = point.x();
        corner.y = point.y();
        corner.end_contour = false;
1340 1341
        aOnePolyList.push_back( corner );
    }
1342 1343 1344 1345

    corner.end_contour = true;
    aOnePolyList.pop_back();
    aOnePolyList.push_back( corner );
1346
}
1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428

/**
 * Function IsPolygonSelfIntersecting
 * Test a CPolyLine for self-intersection of vertex (all contours).
 *
 * @return :
 *  false if no intersecting sides
 *  true if intersecting sides
 * When a CPolyLine is self intersectic, it need to be normalized.
 * (converted to non intersecting polygons)
 */
bool CPolyLine::IsPolygonSelfIntersecting()
{
    // first, check for sides intersecting other sides
    int                n_cont  = GetContoursCount();

    // make bounding rect for each contour
    std::vector<CRect> cr;
    cr.reserve( n_cont );

    for( int icont = 0; icont<n_cont; icont++ )
        cr.push_back( GetCornerBounds( icont ) );

    for( int icont = 0; icont<n_cont; icont++ )
    {
        int is_start = GetContourStart( icont );
        int is_end   = GetContourEnd( icont );

        for( int is = is_start; is<=is_end; is++ )
        {
            int is_prev = is - 1;

            if( is_prev < is_start )
                is_prev = is_end;

            int is_next = is + 1;

            if( is_next > is_end )
                is_next = is_start;

            int x1i   = GetX( is );
            int y1i   = GetY( is );
            int x1f   = GetX( is_next );
            int y1f   = GetY( is_next );

            // check for intersection with any other sides
            for( int icont2 = icont; icont2<n_cont; icont2++ )
            {
                if( cr[icont].left > cr[icont2].right
                    || cr[icont].bottom > cr[icont2].top
                    || cr[icont2].left > cr[icont].right
                    || cr[icont2].bottom > cr[icont].top )
                {
                    // rectangles don't overlap, do nothing
                }
                else
                {
                    int is2_start = GetContourStart( icont2 );
                    int is2_end   = GetContourEnd( icont2 );

                    for( int is2 = is2_start; is2<=is2_end; is2++ )
                    {
                        int is2_prev = is2 - 1;

                        if( is2_prev < is2_start )
                            is2_prev = is2_end;

                        int is2_next = is2 + 1;

                        if( is2_next > is2_end )
                            is2_next = is2_start;

                        if( icont != icont2
                           || ( is2 != is && is2 != is_prev && is2 != is_next &&
                                is != is2_prev && is != is2_next )
                          )
                        {
                            int x2i    = GetX( is2 );
                            int y2i    = GetY( is2 );
                            int x2f    = GetX( is2_next );
                            int y2f    = GetY( is2_next );
                            int ret    = FindSegmentIntersections( x1i, y1i, x1f, y1f,
1429
                                                                   x2i, y2i, x2f, y2f );
1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443
                            if( ret )
                            {
                                // intersection between non-adjacent sides
                                return true;
                            }
                        }
                    }
                }
            }
        }
    }

    return false;
}