shape_line_chain.cpp 12.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2013 CERN
 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 */

#include <geometry/shape_line_chain.h>
#include <geometry/shape_circle.h>

using namespace std;
using boost::optional;

31
bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance ) const
32
{
33
    assert( false );
Maciej Suminski's avatar
Maciej Suminski committed
34

35
    return false;
36 37
}

38 39

bool SHAPE_LINE_CHAIN::Collide( const BOX2I& aBox, int aClearance ) const
40
{
41
    assert( false );
Maciej Suminski's avatar
Maciej Suminski committed
42

43
    return false;
44 45
}

46 47

bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance ) const
48
{
Maciej Suminski's avatar
Maciej Suminski committed
49
    BOX2I box_a( aSeg.A, aSeg.B - aSeg.A );
50 51
    BOX2I::ecoord_type dist_sq = (BOX2I::ecoord_type) aClearance * aClearance;

52
    for( int i = 0; i < SegmentCount(); i++ )
53 54
    {
        const SEG& s = CSegment( i );
Maciej Suminski's avatar
Maciej Suminski committed
55
        BOX2I box_b( s.A, s.B - s.A );
56

57
        BOX2I::ecoord_type d = box_a.SquaredDistance( box_b );
58 59 60 61 62 63 64 65 66

        if( d < dist_sq )
        {
            if( s.Collide( aSeg, aClearance ) )
                return true;
        }
    }

    return false;
67 68
}

69

70
const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Reverse() const
71
{
72
    SHAPE_LINE_CHAIN a( *this );
73

74 75
    reverse( a.m_points.begin(), a.m_points.end() );
    a.m_closed = m_closed;
76

77
    return a;
78 79
}

80

81 82
int SHAPE_LINE_CHAIN::Length() const
{
83
    int l = 0;
84

85 86
    for( int i = 0; i < SegmentCount(); i++ )
        l += CSegment( i ).Length();
87

88
    return l;
89 90
}

91 92

void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
93
{
94 95
    if( aEndIndex < 0 )
        aEndIndex += PointCount();
96

97 98 99 100
    if( aStartIndex < 0 )
        aStartIndex += PointCount();

    if( aStartIndex == aEndIndex )
101
        m_points[aStartIndex] = aP;
102 103 104 105 106
    else
    {
        m_points.erase( m_points.begin() + aStartIndex + 1, m_points.begin() + aEndIndex + 1 );
        m_points[aStartIndex] = aP;
    }
107 108
}

109 110

void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
111
{
112 113
    if( aEndIndex < 0 )
        aEndIndex += PointCount();
114

115 116
    if( aStartIndex < 0 )
        aStartIndex += PointCount();
117

118 119
    m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
    m_points.insert( m_points.begin() + aStartIndex, aLine.m_points.begin(), aLine.m_points.end() );
120 121
}

122 123

void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
124
{
125
    if( aEndIndex < 0 )
126
        aEndIndex += PointCount();
127 128

    if( aStartIndex < 0 )
129
        aStartIndex += PointCount();
130

131
    m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
132 133
}

134 135

int SHAPE_LINE_CHAIN::Distance( const VECTOR2I& aP ) const
136
{
137
    int d = INT_MAX;
138

139 140
    for( int s = 0; s < SegmentCount(); s++ )
        d = min( d, CSegment( s ).Distance( aP ) );
141

142
    return d;
143
}
144 145 146


int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP )
147
{
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162
    int ii = -1;
    int min_dist = 2;

    ii = Find( aP );

    if( ii >= 0 )
        return ii;

    for( int s = 0; s < SegmentCount(); s++ )
    {
        const SEG seg = CSegment( s );
        int dist = seg.Distance( aP );

        // make sure we are not producing a 'slightly concave' primitive. This might happen
        // if aP lies very close to one of already existing points.
Maciej Suminski's avatar
Maciej Suminski committed
163
        if( dist < min_dist && seg.A != aP && seg.B != aP )
164 165 166 167 168
        {
            min_dist = dist;
            ii = s;
        }
    }
169

170 171 172
    if( ii >= 0 )
    {
        m_points.insert( m_points.begin() + ii + 1, aP );
173

174 175
        return ii + 1;
    }
176

177
    return -1;
178 179
}

180 181

int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP ) const
182
{
183 184 185
    for( int s = 0; s< PointCount(); s++ )
        if( CPoint( s ) == aP )
            return s;
186

187
    return -1;
188 189
}

190 191

const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
192
{
193 194 195 196
    SHAPE_LINE_CHAIN rv;

    if( aEndIndex < 0 )
        aEndIndex += PointCount();
197

198 199
    if( aStartIndex < 0 )
        aStartIndex += PointCount();
200

201 202
    for( int i = aStartIndex; i <= aEndIndex; i++ )
        rv.Append( m_points[i] );
203

204
    return rv;
205 206
}

207 208 209

struct compareOriginDistance
{
210
    compareOriginDistance( VECTOR2I& aOrigin ) :
211
        m_origin( aOrigin ) {};
212

Maciej Suminski's avatar
Maciej Suminski committed
213 214
    bool operator()( const SHAPE_LINE_CHAIN::INTERSECTION& aA,
                     const SHAPE_LINE_CHAIN::INTERSECTION& aB )
215 216 217
    {
        return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
    }
218

219
    VECTOR2I m_origin;
220 221
};

222

Maciej Suminski's avatar
Maciej Suminski committed
223
int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
224
{
225 226 227
    for( int s = 0; s < SegmentCount(); s++ )
    {
        OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
228

229 230
        if( p )
        {
Maciej Suminski's avatar
Maciej Suminski committed
231
            INTERSECTION is;
232 233 234 235 236 237 238
            is.our = CSegment( s );
            is.their = aSeg;
            is.p = *p;
            aIp.push_back( is );
        }
    }

Maciej Suminski's avatar
Maciej Suminski committed
239
    compareOriginDistance comp( aSeg.A );
240 241 242
    sort( aIp.begin(), aIp.end(), comp );

    return aIp.size();
243
}
244

245

Maciej Suminski's avatar
Maciej Suminski committed
246
int SHAPE_LINE_CHAIN::Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const
247
{
248
    BOX2I bb_other = aChain.BBox();
249

250
    for( int s1 = 0; s1 < SegmentCount(); s1++ )
251 252
    {
        const SEG& a = CSegment( s1 );
Maciej Suminski's avatar
Maciej Suminski committed
253
        const BOX2I bb_cur( a.A, a.B - a.A );
254 255 256 257 258 259 260

        if( !bb_other.Intersects( bb_cur ) )
            continue;

        for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
        {
            const SEG& b = aChain.CSegment( s2 );
Maciej Suminski's avatar
Maciej Suminski committed
261
            INTERSECTION is;
262 263 264

            if( a.Collinear( b ) )
            {
Maciej Suminski's avatar
Maciej Suminski committed
265 266 267 268
                if( a.Contains( b.A ) ) { is.p = b.A; aIp.push_back( is ); }
                if( a.Contains( b.B ) ) { is.p = b.B; aIp.push_back( is ); }
                if( b.Contains( a.A ) ) { is.p = a.A; aIp.push_back( is ); }
                if( b.Contains( a.B ) ) { is.p = a.B; aIp.push_back( is ); }
269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293
            }
            else
            {
                OPT_VECTOR2I p = a.Intersect( b );

                if( p )
                {
                    is.p = *p;
                    is.our = a;
                    is.their = b;
                    aIp.push_back( is );
                }
            }
        }
    }

    return aIp.size();

    for( int s1 = 0; s1 < SegmentCount(); s1++ )
    {
        for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
        {
            const SEG& a = CSegment( s1 );
            const SEG& b = aChain.CSegment( s2 );
            OPT_VECTOR2I p = a.Intersect( b );
Maciej Suminski's avatar
Maciej Suminski committed
294
            INTERSECTION is;
295 296 297 298 299 300 301 302 303 304

            if( p )
            {
                is.p = *p;
                is.our = a;
                is.their = b;
                aIp.push_back( is );
            }
            else if( a.Collinear( b ) )
            {
Maciej Suminski's avatar
Maciej Suminski committed
305
                if( a.A != b.A && a.A != b.B && b.Contains( a.A ) )
306
                {
Maciej Suminski's avatar
Maciej Suminski committed
307
                    is.p = a.A;
308 309 310 311
                    is.our = a;
                    is.their = b;
                    aIp.push_back( is );
                }
Maciej Suminski's avatar
Maciej Suminski committed
312
                else if( a.B != b.A && a.B != b.B && b.Contains( a.B ) )
313
                {
Maciej Suminski's avatar
Maciej Suminski committed
314
                    is.p = a.B;
315 316 317 318 319 320 321 322 323
                    is.our = a;
                    is.their = b;
                    aIp.push_back( is );
                }
            }
        }
    }

    return aIp.size();
324
}
325 326 327


int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP ) const
328
{
329
    int sum = 0;
330

331 332 333 334 335 336 337
    for( int i = 0; i < SegmentCount(); i++ )
    {
        const SEG seg = CSegment( i );
        int d = seg.Distance( aP );

        if( d <= 1 )
        {
Maciej Suminski's avatar
Maciej Suminski committed
338
            sum += ( aP - seg.A ).EuclideanNorm();
339 340 341 342 343 344 345
            return sum;
        }
        else
            sum += seg.Length();
    }

    return -1;
346
}
347 348 349


bool SHAPE_LINE_CHAIN::PointInside( const VECTOR2I& aP ) const
350
{
351 352
    if( !m_closed || SegmentCount() < 3 )
        return false;
353

354
    int cur = CSegment( 0 ).Side( aP );
355

356 357
    if( cur == 0 )
        return false;
358

359 360 361
    for( int i = 1; i < SegmentCount(); i++ )
    {
        const SEG s = CSegment( i );
362

Maciej Suminski's avatar
Maciej Suminski committed
363
        if( aP == s.A || aP == s.B ) // edge does not belong to the interior!
364
            return false;
365

366
        if( s.Side( aP ) != cur )
367
            return false;
368 369
    }

370
    return true;
371
}
372

373 374

bool SHAPE_LINE_CHAIN::PointOnEdge( const VECTOR2I& aP ) const
375
{
376 377
    if( SegmentCount() < 1 )
        return m_points[0] == aP;
378

379 380 381
    for( int i = 1; i < SegmentCount(); i++ )
    {
        const SEG s = CSegment( i );
382

Maciej Suminski's avatar
Maciej Suminski committed
383
        if( s.A == aP || s.B == aP )
384
            return true;
385

386
        if( s.Distance( aP ) <= 1 )
387 388 389 390
            return true;
    }

    return false;
391 392
}

393

Maciej Suminski's avatar
Maciej Suminski committed
394
const optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
395
{
396 397 398 399
    for( int s1 = 0; s1 < SegmentCount(); s1++ )
    {
        for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
        {
Maciej Suminski's avatar
Maciej Suminski committed
400
            const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
401

402 403
            if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
            {
Maciej Suminski's avatar
Maciej Suminski committed
404
                INTERSECTION is;
405 406 407 408 409
                is.our = CSegment( s1 );
                is.their = CSegment( s2 );
                is.p = s2a;
                return is;
            }
410
            else if( CSegment( s1 ).Contains( s2b ) )
411
            {
Maciej Suminski's avatar
Maciej Suminski committed
412
                INTERSECTION is;
413 414 415 416 417 418 419 420 421 422 423
                is.our = CSegment( s1 );
                is.their = CSegment( s2 );
                is.p = s2b;
                return is;
            }
            else
            {
                OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );

                if( p )
                {
Maciej Suminski's avatar
Maciej Suminski committed
424
                    INTERSECTION is;
425 426 427 428 429 430 431 432 433
                    is.our = CSegment( s1 );
                    is.their = CSegment( s2 );
                    is.p = *p;
                    return is;
                }
            }
        }
    }

Maciej Suminski's avatar
Maciej Suminski committed
434
    return optional<INTERSECTION>();
435
}
436

437 438 439

SHAPE_LINE_CHAIN& SHAPE_LINE_CHAIN::Simplify()
{
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
    vector<VECTOR2I> pts_unique;

    if( PointCount() < 2 )
    {
        return *this;
    }
    else if( PointCount() == 2 )
    {
        if( m_points[0] == m_points[1] )
            m_points.erase( m_points.end() );

        return *this;
    }

    int i = 0;
    int np = PointCount();

    // stage 1: eliminate duplicate vertices
458
    while( i < np )
459 460
    {
        int j = i + 1;
461 462

        while( j < np && CPoint( i ) == CPoint( j ) )
463 464 465 466 467 468 469 470 471 472
            j++;

        pts_unique.push_back( CPoint( i ) );
        i = j;
    }

    m_points.clear();
    np = pts_unique.size();

    i = 0;
473

474 475 476 477
    // stage 1: eliminate collinear segments
    while( i < np - 2 )
    {
        const VECTOR2I p0 = pts_unique[i];
478
        const VECTOR2I p1 = pts_unique[i + 1];
479 480 481 482 483 484
        int n = i;

        while( n < np - 2 && SEG( p0, p1 ).LineDistance( pts_unique[n + 2] ) <= 1 )
            n++;

        m_points.push_back( p0 );
485

486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
        if( n > i )
            i = n;

        if( n == np )
        {
            m_points.push_back( pts_unique[n - 1] );
            return *this;
        }

        i++;
    }

    if( np > 1 )
        m_points.push_back( pts_unique[np - 2] );

    m_points.push_back( pts_unique[np - 1] );

    return *this;
504 505
}

506 507

const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const VECTOR2I& aP ) const
508
{
509 510
    int min_d = INT_MAX;
    int nearest = 0;
511 512

    for( int i = 0; i < SegmentCount(); i++ )
513 514
    {
        int d = CSegment( i ).Distance( aP );
515

516 517 518 519 520 521 522 523
        if( d < min_d )
        {
            min_d = d;
            nearest = i;
        }
    }

    return CSegment( nearest ).NearestPoint( aP );
524
}
525 526


527 528
const string SHAPE_LINE_CHAIN::Format() const
{
529 530
    stringstream ss;

531
    ss << m_points.size() << " " << ( m_closed ? 1 : 0 ) << " ";
532

533
    for( int i = 0; i < PointCount(); i++ )
534
        ss << m_points[i].x << " " << m_points[i].y << " "; // Format() << " ";
535

536
    return ss.str();
537
}