KiCad PCB EDA Suite
Loading...
Searching...
No Matches
shape_line_chain.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2013-2017 CERN
5 * Copyright (C) 2013-2022 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
27#include <limits>
28#include <math.h> // for hypot
29#include <map>
30#include <string> // for basic_string
31
32#include <clipper.hpp>
33#include <clipper2/clipper.h>
34#include <core/kicad_algo.h> // for alg::run_on_pair
35#include <geometry/seg.h> // for SEG, OPT_VECTOR2I
38#include <math/box2.h> // for BOX2I
39#include <math/util.h> // for rescale
40#include <math/vector2d.h> // for VECTOR2, VECTOR2I
41#include <trigo.h> // for RotatePoint
42
43class SHAPE;
44
45const ssize_t SHAPE_LINE_CHAIN::SHAPE_IS_PT = -1;
46const std::pair<ssize_t, ssize_t> SHAPE_LINE_CHAIN::SHAPES_ARE_PT = { SHAPE_IS_PT, SHAPE_IS_PT };
47
48SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<int>& aV)
49 : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
50{
51 for(size_t i = 0; i < aV.size(); i+= 2 )
52 {
53 Append( aV[i], aV[i+1] );
54 }
55}
56
57
58SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath,
59 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
60 const std::vector<SHAPE_ARC>& aArcBuffer ) :
62 m_closed( true ), m_width( 0 )
63{
64 std::map<ssize_t, ssize_t> loadedArcs;
65 m_points.reserve( aPath.size() );
66 m_shapes.reserve( aPath.size() );
67
68 auto loadArc =
69 [&]( ssize_t aArcIndex ) -> ssize_t
70 {
71 if( aArcIndex == SHAPE_IS_PT )
72 {
73 return SHAPE_IS_PT;
74 }
75 else if( loadedArcs.count( aArcIndex ) == 0 )
76 {
77 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
78 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
79 }
80
81 return loadedArcs.at( aArcIndex );
82 };
83
84 for( size_t ii = 0; ii < aPath.size(); ++ii )
85 {
86 Append( aPath[ii].X, aPath[ii].Y );
87
88 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
89 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
90 }
91
92 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
93 // removed during Append() and we would have different number of shapes to points
94 wxASSERT( m_shapes.size() == m_points.size() );
95
96 // Clipper might mess up the rotation of the indices such that an arc can be split between
97 // the end point and wrap around to the start point. Lets fix the indices up now
99}
100
101
102SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const Clipper2Lib::Path64& aPath,
103 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
104 const std::vector<SHAPE_ARC>& aArcBuffer ) :
106 m_closed( true ), m_width( 0 )
107{
108 std::map<ssize_t, ssize_t> loadedArcs;
109 m_points.reserve( aPath.size() );
110 m_shapes.reserve( aPath.size() );
111
112 auto loadArc =
113 [&]( ssize_t aArcIndex ) -> ssize_t
114 {
115 if( aArcIndex == SHAPE_IS_PT )
116 {
117 return SHAPE_IS_PT;
118 }
119 else if( loadedArcs.count( aArcIndex ) == 0 )
120 {
121 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
122 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
123 }
124
125 return loadedArcs.at( aArcIndex );
126 };
127
128 for( size_t ii = 0; ii < aPath.size(); ++ii )
129 {
130 Append( aPath[ii].x, aPath[ii].y );
131
132 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].z].m_FirstArcIdx );
133 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].z].m_SecondArcIdx );
134 }
135
136 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
137 // removed during Append() and we would have different number of shapes to points
138 wxASSERT( m_shapes.size() == m_points.size() );
139
140 // Clipper might mess up the rotation of the indices such that an arc can be split between
141 // the end point and wrap around to the start point. Lets fix the indices up now
143}
144
145
146ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper( bool aRequiredOrientation,
147 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
148 std::vector<SHAPE_ARC>& aArcBuffer ) const
149{
150 ClipperLib::Path c_path;
151 SHAPE_LINE_CHAIN input;
152 bool orientation = Area( false ) >= 0;
153 ssize_t shape_offset = aArcBuffer.size();
154
155 if( orientation != aRequiredOrientation )
156 input = Reverse();
157 else
158 input = *this;
159
160 int pointCount = input.PointCount();
161 c_path.reserve( pointCount );
162
163 for( int i = 0; i < pointCount; i++ )
164 {
165 const VECTOR2I& vertex = input.CPoint( i );
166
167 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
168 size_t z_value_ptr = aZValueBuffer.size();
169 aZValueBuffer.push_back( z_value );
170
171 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
172 }
173
174 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
175
176 return c_path;
177}
178
179
180Clipper2Lib::Path64 SHAPE_LINE_CHAIN::convertToClipper2( bool aRequiredOrientation,
181 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
182 std::vector<SHAPE_ARC>& aArcBuffer ) const
183{
184 Clipper2Lib::Path64 c_path;
185 SHAPE_LINE_CHAIN input;
186 bool orientation = Area( false ) >= 0;
187 ssize_t shape_offset = aArcBuffer.size();
188
189 if( orientation != aRequiredOrientation )
190 input = Reverse();
191 else
192 input = *this;
193
194 int pointCount = input.PointCount();
195 c_path.reserve( pointCount );
196
197 for( int i = 0; i < pointCount; i++ )
198 {
199 const VECTOR2I& vertex = input.CPoint( i );
200
201 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
202 size_t z_value_ptr = aZValueBuffer.size();
203 aZValueBuffer.push_back( z_value );
204
205 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
206 }
207
208 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
209
210 return c_path;
211}
212
213
215{
216 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
217
218 if( m_shapes.size() <= 1 )
219 return;
220
221 size_t rotations = 0;
222 size_t numPoints = m_points.size();
223
224 while( ArcIndex( 0 ) != SHAPE_IS_PT
225 && ArcIndex( 0 ) == ArcIndex( numPoints - 1 )
226 && !IsSharedPt( 0 ) )
227 {
228 // Rotate right
229 std::rotate( m_points.rbegin(), m_points.rbegin() + 1, m_points.rend() );
230 std::rotate( m_shapes.rbegin(), m_shapes.rbegin() + 1, m_shapes.rend() );
231
232 // Sanity check - avoid infinite loops (NB: wxCHECK is not thread-safe)
233 if( rotations++ > m_shapes.size() )
234 return;
235 }
236}
237
238
240{
241 if( m_closed )
242 {
243 if( m_points.size() > 1 && m_points.front() == m_points.back() )
244 {
245 if( m_shapes.back() != SHAPES_ARE_PT )
246 {
247 m_shapes.front().second = m_shapes.front().first;
248 m_shapes.front().first = m_shapes.back().first;
249 }
250
251 m_points.pop_back();
252 m_shapes.pop_back();
253
255 }
256 }
257 else
258 {
259 if( m_points.size() > 1 && IsSharedPt( 0 ) )
260 {
261 // Create a duplicate point at the end
262 m_points.push_back( m_points.front() );
263 m_shapes.push_back( { m_shapes.front().first, SHAPE_IS_PT });
264 m_shapes.front().first = m_shapes.front().second;
265 m_shapes.front().second = SHAPE_IS_PT;
266 }
267 }
268}
269
270
271void SHAPE_LINE_CHAIN::convertArc( ssize_t aArcIndex )
272{
273 if( aArcIndex < 0 )
274 aArcIndex += m_arcs.size();
275
276 if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
277 return;
278
279 // Clear the shapes references
280 for( auto& sh : m_shapes )
281 {
283 [&]( ssize_t& aShapeIndex )
284 {
285 if( aShapeIndex == aArcIndex )
286 aShapeIndex = SHAPE_IS_PT;
287
288 if( aShapeIndex > aArcIndex )
289 --aShapeIndex;
290 } );
291
292 if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
293 std::swap( sh.first, sh.second );
294 }
295
296 m_arcs.erase( m_arcs.begin() + aArcIndex );
297}
298
299
300void SHAPE_LINE_CHAIN::amendArc( size_t aArcIndex, const VECTOR2I& aNewStart,
301 const VECTOR2I& aNewEnd )
302{
303 wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
304 wxT( "Invalid arc index requested." ) );
305
306 SHAPE_ARC& theArc = m_arcs[aArcIndex];
307
308 // Try to preseve the centre of the original arc
309 SHAPE_ARC newArc;
310 newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
311 theArc.IsClockwise() );
312
313 m_arcs[aArcIndex] = newArc;
314}
315
316
317void SHAPE_LINE_CHAIN::splitArc( ssize_t aPtIndex, bool aCoincident )
318{
319 if( aPtIndex < 0 )
320 aPtIndex += m_shapes.size();
321
322 if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
323 return; // Nothing to do
324
325 if( !IsPtOnArc( aPtIndex ) )
326 return; // Nothing to do
327
328 wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
329 wxT( "Invalid point index requested." ) );
330
331 if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
332 {
333 if( aCoincident || aPtIndex == 0 )
334 return; // nothing to do
335
336 ssize_t firstArcIndex = m_shapes[aPtIndex].first;
337
338 const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
339 const VECTOR2I& newEnd = m_points[aPtIndex - 1];
340 amendArc( firstArcIndex, newStart, newEnd );
341
342 if( IsSharedPt( aPtIndex ) )
343 {
344 m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
345 m_shapes[aPtIndex].second = SHAPE_IS_PT;
346 }
347 else
348 {
349 m_shapes[aPtIndex] = SHAPES_ARE_PT;
350 }
351
352 return;
353 }
354
355 ssize_t currArcIdx = ArcIndex( aPtIndex );
356 SHAPE_ARC& currentArc = m_arcs[currArcIdx];
357
358 SHAPE_ARC newArc1;
359 SHAPE_ARC newArc2;
360
361 VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
362 VECTOR2I arc2Start = m_points[aPtIndex];
363
364 newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
365 currentArc.IsClockwise() );
366
367 newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
368 currentArc.IsClockwise() );
369
370 if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
371 {
372 //Ignore newArc1 as it has zero points
373 m_arcs[currArcIdx] = newArc2;
374 }
375 else
376 {
377 m_arcs[currArcIdx] = newArc1;
378 m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
379
380 if( aCoincident )
381 {
382 m_shapes[aPtIndex].second = currArcIdx + 1;
383 aPtIndex++;
384 }
385
386 // Only change the arc indices for the second half of the point range
387 for( int i = aPtIndex; i < PointCount(); i++ )
388 {
389 alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
390 if( aIndex != SHAPE_IS_PT )
391 aIndex++;
392 } );
393 }
394 }
395}
396
397
398bool SHAPE_LINE_CHAIN_BASE::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
399 VECTOR2I* aLocation ) const
400{
401 if( IsClosed() && PointInside( aP, aClearance ) )
402 {
403 if( aLocation )
404 *aLocation = aP;
405
406 if( aActual )
407 *aActual = 0;
408
409 return true;
410 }
411
412 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
413 SEG::ecoord clearance_sq = SEG::Square( aClearance );
414 VECTOR2I nearest;
415
416 for( size_t i = 0; i < GetSegmentCount(); i++ )
417 {
418 const SEG& s = GetSegment( i );
419 VECTOR2I pn = s.NearestPoint( aP );
420 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
421
422 if( dist_sq < closest_dist_sq )
423 {
424 nearest = pn;
425 closest_dist_sq = dist_sq;
426
427 if( closest_dist_sq == 0 )
428 break;
429
430 // If we're not looking for aActual then any collision will do
431 if( closest_dist_sq < clearance_sq && !aActual )
432 break;
433 }
434 }
435
436 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
437 {
438 if( aLocation )
439 *aLocation = nearest;
440
441 if( aActual )
442 *aActual = sqrt( closest_dist_sq );
443
444 return true;
445 }
446
447 return false;
448}
449
450
451bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
452 VECTOR2I* aLocation ) const
453{
454 if( IsClosed() && PointInside( aP, aClearance ) )
455 {
456 if( aLocation )
457 *aLocation = aP;
458
459 if( aActual )
460 *aActual = 0;
461
462 return true;
463 }
464
465 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
466 SEG::ecoord clearance_sq = SEG::Square( aClearance );
467 VECTOR2I nearest;
468
469 // Collide line segments
470 for( size_t i = 0; i < GetSegmentCount(); i++ )
471 {
472 if( IsArcSegment( i ) )
473 continue;
474
475 const SEG& s = GetSegment( i );
476 VECTOR2I pn = s.NearestPoint( aP );
477 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
478
479 if( dist_sq < closest_dist_sq )
480 {
481 nearest = pn;
482 closest_dist_sq = dist_sq;
483
484 if( closest_dist_sq == 0 )
485 break;
486
487 // If we're not looking for aActual then any collision will do
488 if( closest_dist_sq < clearance_sq && !aActual )
489 break;
490 }
491 }
492
493 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
494 {
495 if( aLocation )
496 *aLocation = nearest;
497
498 if( aActual )
499 *aActual = sqrt( closest_dist_sq );
500
501 return true;
502 }
503
504 // Collide arc segments
505 for( size_t i = 0; i < ArcCount(); i++ )
506 {
507 const SHAPE_ARC& arc = Arc( i );
508
509 // The arcs in the chain should have zero width
510 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
511
512 if( arc.Collide( aP, aClearance, aActual, aLocation ) )
513 return true;
514 }
515
516 return false;
517}
518
519
520void SHAPE_LINE_CHAIN::Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter )
521{
522 for( VECTOR2I& pt : m_points )
523 RotatePoint( pt, aCenter, aAngle );
524
525 for( SHAPE_ARC& arc : m_arcs )
526 arc.Rotate( aAngle, aCenter );
527}
528
529
530bool SHAPE_LINE_CHAIN_BASE::Collide( const SEG& aSeg, int aClearance, int* aActual,
531 VECTOR2I* aLocation ) const
532{
533 if( IsClosed() && PointInside( aSeg.A ) )
534 {
535 if( aLocation )
536 *aLocation = aSeg.A;
537
538 if( aActual )
539 *aActual = 0;
540
541 return true;
542 }
543
544 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
545 SEG::ecoord clearance_sq = SEG::Square( aClearance );
546 VECTOR2I nearest;
547
548 for( size_t i = 0; i < GetSegmentCount(); i++ )
549 {
550 const SEG& s = GetSegment( i );
551 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
552
553 if( dist_sq < closest_dist_sq )
554 {
555 if( aLocation )
556 nearest = s.NearestPoint( aSeg );
557
558 closest_dist_sq = dist_sq;
559
560 if( closest_dist_sq == 0)
561 break;
562
563 // If we're not looking for aActual then any collision will do
564 if( closest_dist_sq < clearance_sq && !aActual )
565 break;
566 }
567 }
568
569 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
570 {
571 if( aLocation )
572 *aLocation = nearest;
573
574 if( aActual )
575 *aActual = sqrt( closest_dist_sq );
576
577 return true;
578 }
579
580 return false;
581}
582
583
584bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance, int* aActual,
585 VECTOR2I* aLocation ) const
586{
587 if( IsClosed() && PointInside( aSeg.A ) )
588 {
589 if( aLocation )
590 *aLocation = aSeg.A;
591
592 if( aActual )
593 *aActual = 0;
594
595 return true;
596 }
597
598 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
599 SEG::ecoord clearance_sq = SEG::Square( aClearance );
600 VECTOR2I nearest;
601
602 // Collide line segments
603 for( size_t i = 0; i < GetSegmentCount(); i++ )
604 {
605 if( IsArcSegment( i ) )
606 continue;
607
608 const SEG& s = GetSegment( i );
609 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
610
611 if( dist_sq < closest_dist_sq )
612 {
613 if( aLocation )
614 nearest = s.NearestPoint( aSeg );
615
616 closest_dist_sq = dist_sq;
617
618 if( closest_dist_sq == 0 )
619 break;
620
621 // If we're not looking for aActual then any collision will do
622 if( closest_dist_sq < clearance_sq && !aActual )
623 break;
624 }
625 }
626
627 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
628 {
629 if( aLocation )
630 *aLocation = nearest;
631
632 if( aActual )
633 *aActual = sqrt( closest_dist_sq );
634
635 return true;
636 }
637
638 // Collide arc segments
639 for( size_t i = 0; i < ArcCount(); i++ )
640 {
641 const SHAPE_ARC& arc = Arc( i );
642
643 // The arcs in the chain should have zero width
644 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
645
646 if( arc.Collide( aSeg, aClearance, aActual, aLocation ) )
647 return true;
648 }
649
650 return false;
651}
652
653
655{
656 SHAPE_LINE_CHAIN a( *this );
657
658 reverse( a.m_points.begin(), a.m_points.end() );
659 reverse( a.m_shapes.begin(), a.m_shapes.end() );
660 reverse( a.m_arcs.begin(), a.m_arcs.end() );
661
662 for( auto& sh : a.m_shapes )
663 {
664 if( sh != SHAPES_ARE_PT )
665 {
667 [&]( ssize_t& aShapeIndex )
668 {
669 if( aShapeIndex != SHAPE_IS_PT )
670 aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
671 } );
672
673 if( sh.second != SHAPE_IS_PT )
674 {
675 // If the second element is populated, the first one should be too!
676 assert( sh.first != SHAPE_IS_PT );
677
678 // Switch round first and second in shared points, as part of reversing the chain
679 std::swap( sh.first, sh.second );
680 }
681 }
682 }
683
684 for( SHAPE_ARC& arc : a.m_arcs )
685 arc.Reverse();
686
687 a.m_closed = m_closed;
688
689 return a;
690}
691
692
694{
695 for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
696 convertArc( arcIndex );
697}
698
699
700long long int SHAPE_LINE_CHAIN::Length() const
701{
702 long long int l = 0;
703
704 for( int i = 0; i < SegmentCount(); i++ )
705 {
706 // Only include segments that aren't part of arc shapes
707 if( !IsArcSegment(i) )
708 l += CSegment( i ).Length();
709 }
710
711 for( size_t i = 0; i < ArcCount(); i++ )
712 l += CArcs()[i].GetLength();
713
714 return l;
715}
716
717
718void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
719{
720 for( auto& pt : m_points )
721 {
722 if( aX )
723 pt.x = -pt.x + 2 * aRef.x;
724
725 if( aY )
726 pt.y = -pt.y + 2 * aRef.y;
727 }
728
729 for( auto& arc : m_arcs )
730 arc.Mirror( aX, aY, aRef );
731}
732
733
734void SHAPE_LINE_CHAIN::Mirror( const SEG& axis )
735{
736 for( auto& pt : m_points )
737 pt = axis.ReflectPoint( pt );
738
739 for( auto& arc : m_arcs )
740 arc.Mirror( axis );
741}
742
743
744void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
745{
746 Remove( aStartIndex, aEndIndex );
747 Insert( aStartIndex, aP );
748 assert( m_shapes.size() == m_points.size() );
749}
750
751
752void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
753{
754 if( aEndIndex < 0 )
755 aEndIndex += PointCount();
756
757 if( aStartIndex < 0 )
758 aStartIndex += PointCount();
759
760 // We only process lines in order in this house
761 wxASSERT( aStartIndex <= aEndIndex );
762 wxASSERT( aEndIndex < static_cast<int>( m_points.size() ) );
763
764 SHAPE_LINE_CHAIN newLine = aLine;
765
766 // Zero points to add?
767 if( newLine.PointCount() == 0 )
768 {
769 Remove( aStartIndex, aEndIndex );
770 return;
771 }
772
773 // Remove coincident points in the new line
774 if( newLine.m_points.front() == m_points[aStartIndex] )
775 {
776 aStartIndex++;
777 newLine.Remove( 0 );
778
779 // Zero points to add?
780 if( newLine.PointCount() == 0 )
781 {
782 Remove( aStartIndex, aEndIndex );
783 return;
784 }
785 }
786
787 if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
788 {
789 aEndIndex--;
790 newLine.Remove( -1 );
791 }
792
793 Remove( aStartIndex, aEndIndex );
794
795 // Zero points to add?
796 if( newLine.PointCount() == 0 )
797 return;
798
799 // The total new arcs index is added to the new arc indices
800 size_t prev_arc_count = m_arcs.size();
801 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
802
803 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
804 {
805 alg::run_on_pair( shape_pair,
806 [&]( ssize_t& aShape )
807 {
808 if( aShape != SHAPE_IS_PT )
809 aShape += prev_arc_count;
810 } );
811 }
812
813 m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
814 m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
815 newLine.m_points.end() );
816 m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
817
818 assert( m_shapes.size() == m_points.size() );
819}
820
821
822void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
823{
824 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
825
826 // Unwrap the chain first (correctly handling removing arc at
827 // end of chain coincident with start)
828 bool closedState = IsClosed();
829 SetClosed( false );
830
831 if( aEndIndex < 0 )
832 aEndIndex += PointCount();
833
834 if( aStartIndex < 0 )
835 aStartIndex += PointCount();
836
837 if( aStartIndex >= PointCount() || aEndIndex >= PointCount() || aStartIndex > aEndIndex)
838 {
839 SetClosed( closedState );
840 return;
841 }
842
843
844 // Split arcs, making arcs coincident
845 if( !IsArcStart( aStartIndex ) && IsPtOnArc( aStartIndex ) )
846 splitArc( aStartIndex, false );
847
848 if( IsSharedPt( aStartIndex ) ) // Don't delete the shared point
849 aStartIndex += 1;
850
851 if( !IsArcEnd( aEndIndex ) && IsPtOnArc( aEndIndex ) && aEndIndex < PointCount() - 1 )
852 splitArc( aEndIndex + 1, true );
853
854 if( IsSharedPt( aEndIndex ) ) // Don't delete the shared point
855 aEndIndex -= 1;
856
857 if( aStartIndex > aEndIndex )
858 {
859 SetClosed( closedState );
860 return;
861 }
862
863 std::set<size_t> extra_arcs;
864 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
865 {
866 if( aShapeIndex != SHAPE_IS_PT )
867 extra_arcs.insert( aShapeIndex );
868 };
869
870 // Remove any overlapping arcs in the point range
871 for( int i = aStartIndex; i <= aEndIndex; i++ )
872 {
873 if( IsSharedPt( i ) )
874 {
875 if( i == aStartIndex )
876 {
877 logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
878
879 // Ensure that m_shapes has been built correctly.
880 assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
881
882 continue;
883 }
884 else if( i == aEndIndex )
885 {
886 logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
887
888 // Ensure that m_shapes has been built correctly.
889 assert( i > aStartIndex || ( IsSharedPt( i - 1 )
890 ? m_shapes[i - 1].second == m_shapes[i].first
891 : m_shapes[i - 1].first == m_shapes[i].first ) );
892 continue;
893 }
894 }
895 else
896 {
897 alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
898 }
899 }
900
901 for( auto arc : extra_arcs )
902 convertArc( arc );
903
904 m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
905 m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
906 assert( m_shapes.size() == m_points.size() );
907
908 SetClosed( closedState );
909}
910
911
913{
915
916 if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
917 return 0;
918
919 for( size_t s = 0; s < GetSegmentCount(); s++ )
920 d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
921
922 return d;
923}
924
925
926int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP, bool aExact )
927{
928 int ii = -1;
929 int min_dist = 2;
930
931 int found_index = Find( aP );
932
933 if( found_index >= 0 && aExact )
934 return found_index;
935
936 for( int s = 0; s < SegmentCount(); s++ )
937 {
938 const SEG seg = CSegment( s );
939 int dist = seg.Distance( aP );
940
941 // make sure we are not producing a 'slightly concave' primitive. This might happen
942 // if aP lies very close to one of already existing points.
943 if( dist < min_dist && seg.A != aP && seg.B != aP )
944 {
945 min_dist = dist;
946 if( found_index < 0 )
947 ii = s;
948 else if( s < found_index )
949 ii = s;
950 }
951 }
952
953 if( ii < 0 )
954 ii = found_index;
955
956 if( ii >= 0 )
957 {
958 // Don't create duplicate points
959 if( GetPoint( ii ) == aP )
960 return ii;
961
962 size_t newIndex = static_cast<size_t>( ii ) + 1;
963
964 if( IsArcSegment( ii ) )
965 {
966 m_points.insert( m_points.begin() + newIndex, aP );
967 m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
968 splitArc( newIndex, true ); // Make the inserted point a shared point
969 }
970 else
971 {
972 Insert( newIndex, aP );
973 }
974
975 return newIndex;
976 }
977
978 return -1;
979}
980
981
982int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP, int aThreshold ) const
983{
984 for( int s = 0; s < PointCount(); s++ )
985 {
986 if( aThreshold == 0 )
987 {
988 if( CPoint( s ) == aP )
989 return s;
990 }
991 else
992 {
993 if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
994 return s;
995 }
996 }
997
998 return -1;
999}
1000
1001
1002int SHAPE_LINE_CHAIN::FindSegment( const VECTOR2I& aP, int aThreshold ) const
1003{
1004 for( int s = 0; s < SegmentCount(); s++ )
1005 {
1006 if( CSegment( s ).Distance( aP ) <= aThreshold )
1007 return s;
1008 }
1009
1010 return -1;
1011}
1012
1013
1015{
1016 wxCHECK2_MSG( m_points.size() == m_shapes.size(), return 0, "Invalid chain!" );
1017
1018 if( m_points.size() < 2 )
1019 return 0;
1020
1021 int numShapes = 1;
1022
1023 for( int i = NextShape( 0 ); i != -1; i = NextShape( i ) )
1024 numShapes++;
1025
1026 return numShapes;
1027}
1028
1029
1031{
1032 if( aIndex < 0 )
1033 aIndex += SegmentCount();
1034
1035 wxCHECK( aIndex < SegmentCount() && aIndex >= 0,
1036 m_points.size() > 0 ? SEG( m_points.back(), m_points.back() ) : SEG( 0, 0, 0, 0 ) );
1037
1038 if( aIndex == (int) ( m_points.size() - 1 ) && m_closed )
1039 return SEG( m_points[aIndex], m_points[0], aIndex );
1040 else
1041 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
1042}
1043
1044
1045int SHAPE_LINE_CHAIN::NextShape( int aPointIndex ) const
1046{
1047 if( aPointIndex < 0 )
1048 aPointIndex += PointCount();
1049
1050 if( aPointIndex < 0 )
1051 return -1;
1052
1053 int lastIndex = PointCount() - 1;
1054
1055 // Last point?
1056 if( aPointIndex >= lastIndex )
1057 return -1; // we don't want to wrap around
1058
1059 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1060 {
1061 if( aPointIndex == lastIndex - 1 )
1062 {
1063 if( m_closed )
1064 return lastIndex;
1065 else
1066 return -1;
1067 }
1068 else
1069 {
1070 return aPointIndex + 1;
1071 }
1072 }
1073
1074 int arcStart = aPointIndex;
1075
1076 // The second element should only get populated when the point is shared between two shapes.
1077 // If not a shared point, then the index should always go on the first element.
1078 wxCHECK2_MSG( m_shapes[aPointIndex].first != SHAPE_IS_PT, return -1, "malformed chain!" );
1079
1080 ssize_t currentArcIdx = ArcIndex( aPointIndex );
1081
1082 // Now skip the rest of the arc
1083 while( aPointIndex < lastIndex && ArcIndex( aPointIndex ) == currentArcIdx )
1084 aPointIndex += 1;
1085
1086 bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], currentArcIdx );
1087
1088 // We want the last vertex of the arc if the initial point was the start of one
1089 // Well-formed arcs should generate more than one point to travel above
1090 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1091 aPointIndex -= 1;
1092
1093 if( aPointIndex == lastIndex )
1094 {
1095 if( !m_closed || IsArcSegment( aPointIndex ) )
1096 return -1; //no shape
1097 else
1098 return lastIndex; // Segment between last point and the start of the chain
1099 }
1100
1101 return aPointIndex;
1102}
1103
1104
1105void SHAPE_LINE_CHAIN::SetPoint( int aIndex, const VECTOR2I& aPos )
1106{
1107 if( aIndex < 0 )
1108 aIndex += PointCount();
1109 else if( aIndex >= PointCount() )
1110 aIndex -= PointCount();
1111
1112 m_points[aIndex] = aPos;
1113
1114 alg::run_on_pair( m_shapes[aIndex],
1115 [&]( ssize_t& aIdx )
1116 {
1117 if( aIdx != SHAPE_IS_PT )
1118 convertArc( aIdx );
1119 } );
1120}
1121
1122
1123void SHAPE_LINE_CHAIN::RemoveShape( int aPointIndex )
1124{
1125 if( aPointIndex < 0 )
1126 aPointIndex += PointCount();
1127
1128 if( aPointIndex >= PointCount() || aPointIndex < 0 )
1129 return; // Invalid index, fail gracefully
1130
1131 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1132 {
1133 Remove( aPointIndex );
1134 return;
1135 }
1136
1137 int start = aPointIndex;
1138 int end = aPointIndex;
1139 int arcIdx = ArcIndex( aPointIndex );
1140
1141 if( !IsArcStart( start ) )
1142 {
1143 // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
1144 while( start > 0 && ArcIndex( static_cast<ssize_t>( start ) - 1 ) == arcIdx )
1145 start--;
1146 }
1147
1148 if( !IsArcEnd( end ) || start == end )
1149 end = NextShape( end ); // can be -1 to indicate end of chain
1150
1151 Remove( start, end );
1152}
1153
1154
1155const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
1156{
1158
1159 if( aEndIndex < 0 )
1160 aEndIndex += PointCount();
1161
1162 if( aStartIndex < 0 )
1163 aStartIndex += PointCount();
1164
1165 // Bad programmer checks
1166 wxCHECK( aStartIndex >= 0, SHAPE_LINE_CHAIN() );
1167 wxCHECK( aEndIndex >= 0, SHAPE_LINE_CHAIN() );
1168 wxCHECK( aStartIndex < PointCount(), SHAPE_LINE_CHAIN() );
1169 wxCHECK( aEndIndex < PointCount(), SHAPE_LINE_CHAIN() );
1170 wxCHECK( aEndIndex >= aStartIndex, SHAPE_LINE_CHAIN() );
1171
1172 int numPoints = static_cast<int>( m_points.size() );
1173
1174 if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
1175 {
1176 // Cutting in middle of an arc, lets split it
1177 ssize_t arcToSplitIndex = ArcIndex( aStartIndex );
1178 const SHAPE_ARC& arcToSplit = Arc( arcToSplitIndex );
1179
1180 // Copy the points as arc points
1181 for( size_t i = aStartIndex; arcToSplitIndex == ArcIndex( i ); i++ )
1182 {
1183 rv.m_points.push_back( m_points[i] );
1184 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1185 rv.m_bbox.Merge( m_points[i] );
1186 }
1187
1188 // Create a new arc from the existing one, with different start point.
1189 SHAPE_ARC newArc;
1190
1191 VECTOR2I newArcStart = m_points[aStartIndex];
1192
1193 newArc.ConstructFromStartEndCenter( newArcStart, arcToSplit.GetP1(),
1194 arcToSplit.GetCenter(),
1195 arcToSplit.IsClockwise() );
1196
1197
1198 rv.m_arcs.push_back( newArc );
1199
1200 aStartIndex += rv.PointCount();
1201 }
1202
1203 for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
1204 {
1205 if( i == -1 )
1206 return rv; // NextShape reached the end
1207
1208 int nextShape = NextShape( i );
1209 bool isLastShape = nextShape < 0;
1210
1211 if( IsArcStart( i ) )
1212 {
1213 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1214 || ( nextShape > aEndIndex ) )
1215 {
1216 if( i == aEndIndex )
1217 {
1218 // Single point on an arc, just append the single point
1219 rv.Append( m_points[i] );
1220 return rv;
1221 }
1222
1223 // Cutting in middle of an arc, lets split it
1224 ssize_t arcIndex = ArcIndex( i );
1225 const SHAPE_ARC& currentArc = Arc( arcIndex );
1226
1227 // Copy the points as arc points
1228 for( ; i <= aEndIndex && i < numPoints; i++ )
1229 {
1230 if( arcIndex != ArcIndex( i ) )
1231 break;
1232
1233 rv.m_points.push_back( m_points[i] );
1234 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1235 rv.m_bbox.Merge( m_points[i] );
1236 }
1237
1238 // Create a new arc from the existing one, with different end point.
1239 SHAPE_ARC newArc;
1240
1241 VECTOR2I newArcEnd = m_points[aEndIndex];
1242
1243 newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
1244 currentArc.GetCenter(),
1245 currentArc.IsClockwise() );
1246
1247
1248 rv.m_arcs.push_back( newArc );
1249
1250 return rv;
1251 }
1252 else
1253 {
1254 // append the whole arc
1255 const SHAPE_ARC& currentArc = Arc( ArcIndex( i ) );
1256 rv.Append( currentArc );
1257 }
1258
1259 if( isLastShape )
1260 return rv;
1261 }
1262 else
1263 {
1264 wxASSERT_MSG( !IsArcSegment( i ),
1265 wxT( "Still on an arc segment, we missed something..." ) );
1266
1267 if( i == aStartIndex )
1268 rv.Append( m_points[i] );
1269
1270 bool nextPointIsArc = isLastShape ? false : IsArcSegment( nextShape );
1271
1272 if( !nextPointIsArc && i < SegmentCount() && i < aEndIndex )
1273 rv.Append( GetSegment( i ).B );
1274 }
1275
1276 }
1277
1278 return rv;
1279}
1280
1281
1283{
1284 assert( m_shapes.size() == m_points.size() );
1285
1286 if( aOtherLine.PointCount() == 0 )
1287 {
1288 return;
1289 }
1290
1291 size_t num_arcs = m_arcs.size();
1292 m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
1293
1294 auto fixShapeIndices =
1295 [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1296 {
1297 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1298
1299 alg::run_on_pair( retval, [&]( ssize_t& aIndex )
1300 {
1301 if( aIndex != SHAPE_IS_PT )
1302 aIndex = aIndex + num_arcs;
1303 } );
1304
1305 return retval;
1306 };
1307
1308 if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
1309 {
1310 const VECTOR2I p = aOtherLine.CPoint( 0 );
1311 m_points.push_back( p );
1312 m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
1313 m_bbox.Merge( p );
1314 }
1315 else if( aOtherLine.IsArcSegment( 0 ) )
1316 {
1317 // Associate the new arc shape with the last point of this chain
1318 if( m_shapes.back() == SHAPES_ARE_PT )
1319 m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
1320 else
1321 m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
1322 }
1323
1324
1325 for( int i = 1; i < aOtherLine.PointCount(); i++ )
1326 {
1327 const VECTOR2I p = aOtherLine.CPoint( i );
1328 m_points.push_back( p );
1329
1330 ssize_t arcIndex = aOtherLine.ArcIndex( i );
1331
1332 if( arcIndex != ssize_t( SHAPE_IS_PT ) )
1333 {
1334 m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
1335 }
1336 else
1337 m_shapes.push_back( SHAPES_ARE_PT );
1338
1339 m_bbox.Merge( p );
1340 }
1341
1343
1344 assert( m_shapes.size() == m_points.size() );
1345}
1346
1347
1349{
1351}
1352
1353
1354void SHAPE_LINE_CHAIN::Append( const SHAPE_ARC& aArc, double aAccuracy )
1355{
1356 SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline( aAccuracy );
1357
1358 if( chain.PointCount() > 2 )
1359 {
1360 chain.m_arcs.push_back( aArc );
1361 chain.m_arcs.back().SetWidth( 0 );
1362
1363 for( auto& sh : chain.m_shapes )
1364 sh.first = 0;
1365 }
1366
1367 Append( chain );
1368
1369 assert( m_shapes.size() == m_points.size() );
1370}
1371
1372
1373void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
1374{
1375 if( aVertex == m_points.size() )
1376 {
1377 Append( aP );
1378 return;
1379 }
1380
1381 wxCHECK( aVertex < m_points.size(), /* void */ );
1382
1383 if( aVertex > 0 && IsPtOnArc( aVertex ) )
1384 splitArc( aVertex );
1385
1386 //@todo need to check we aren't creating duplicate points
1387 m_points.insert( m_points.begin() + aVertex, aP );
1388 m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
1389
1390 assert( m_shapes.size() == m_points.size() );
1391}
1392
1393
1394void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
1395{
1396 wxCHECK( aVertex < m_points.size(), /* void */ );
1397
1398 if( aVertex > 0 && IsPtOnArc( aVertex ) )
1399 splitArc( aVertex );
1400
1402 ssize_t arc_pos = m_arcs.size();
1403
1404 for( auto arc_it = m_shapes.rbegin() ;
1405 arc_it != m_shapes.rend() + aVertex;
1406 arc_it++ )
1407 {
1408 if( *arc_it != SHAPES_ARE_PT )
1409 {
1410 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1411 arc_pos++;
1412 }
1413 }
1414
1415 //Increment all arc indices before inserting the new arc
1416 for( auto& sh : m_shapes )
1417 {
1418 alg::run_on_pair( sh,
1419 [&]( ssize_t& aIndex )
1420 {
1421 if( aIndex >= arc_pos )
1422 aIndex++;
1423 } );
1424 }
1425
1426 SHAPE_ARC arcCopy( aArc );
1427 arcCopy.SetWidth( 0 );
1428 m_arcs.insert( m_arcs.begin() + arc_pos, arcCopy );
1429
1431 //@todo need to check we aren't creating duplicate points at start or end
1432 auto& chain = aArc.ConvertToPolyline();
1433 m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1434
1436 //@todo need to check we aren't creating duplicate points at start or end
1437 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1438 { arc_pos, SHAPE_IS_PT } );
1439
1440 m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1441 assert( m_shapes.size() == m_points.size() );
1442}
1443
1444
1446{
1448 m_origin( aOrigin ) {};
1449
1451 const SHAPE_LINE_CHAIN::INTERSECTION& aB ) const
1452 {
1453 return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
1454 }
1455
1457};
1458
1459
1460int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
1461{
1462 for( int s = 0; s < SegmentCount(); s++ )
1463 {
1464 OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
1465
1466 if( p )
1467 {
1468 INTERSECTION is;
1469 is.valid = true;
1470 is.index_our = s;
1471 is.index_their = -1;
1472 is.is_corner_our = is.is_corner_their = false;
1473 is.p = *p;
1474 aIp.push_back( is );
1475 }
1476 }
1477
1478 compareOriginDistance comp( aSeg.A );
1479 sort( aIp.begin(), aIp.end(), comp );
1480
1481 return aIp.size();
1482}
1483
1484
1485static inline void addIntersection( SHAPE_LINE_CHAIN::INTERSECTIONS& aIps, int aPc,
1487{
1488 if( aIps.size() == 0 )
1489 {
1490 aIps.push_back( aP );
1491 return;
1492 }
1493
1494 aIps.push_back( aP );
1495}
1496
1497
1499 bool aExcludeColinearAndTouching, BOX2I* aChainBBox ) const
1500{
1501 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.BBox();
1502
1503 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1504 {
1505 const SEG& a = CSegment( s1 );
1506 const BOX2I bb_cur( a.A, a.B - a.A );
1507
1508 if( !bb_other.Intersects( bb_cur ) )
1509 continue;
1510
1511 for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1512 {
1513 const SEG& b = aChain.CSegment( s2 );
1514 INTERSECTION is;
1515
1516 is.index_our = s1;
1517 is.index_their = s2;
1518 is.is_corner_our = false;
1519 is.is_corner_their = false;
1520 is.valid = true;
1521
1522 OPT_VECTOR2I p = a.Intersect( b );
1523
1524 bool coll = a.Collinear( b );
1525
1526 if( coll && ! aExcludeColinearAndTouching )
1527 {
1528 if( a.Contains( b.A ) )
1529 {
1530 is.p = b.A;
1531 is.is_corner_their = true;
1532 addIntersection(aIp, PointCount(), is);
1533 }
1534
1535 if( a.Contains( b.B ) )
1536 {
1537 is.p = b.B;
1538 is.index_their++;
1539 is.is_corner_their = true;
1540 addIntersection( aIp, PointCount(), is );
1541 }
1542
1543 if( b.Contains( a.A ) )
1544 {
1545 is.p = a.A;
1546 is.is_corner_our = true;
1547 addIntersection( aIp, PointCount(), is );
1548 }
1549
1550 if( b.Contains( a.B ) )
1551 {
1552 is.p = a.B;
1553 is.index_our++;
1554 is.is_corner_our = true;
1555 addIntersection( aIp, PointCount(), is );
1556 }
1557 }
1558 else if( p )
1559 {
1560 is.p = *p;
1561 is.is_corner_our = false;
1562 is.is_corner_their = false;
1563
1564 if( p == a.A )
1565 {
1566 is.is_corner_our = true;
1567 }
1568
1569 if( p == a.B )
1570 {
1571 is.is_corner_our = true;
1572 is.index_our++;
1573 }
1574
1575 if( p == b.A )
1576 {
1577 is.is_corner_their = true;
1578 }
1579
1580 if( p == b.B )
1581 {
1582 is.is_corner_their = true;
1583 is.index_their++;
1584 }
1585
1586 addIntersection( aIp, PointCount(), is );
1587 }
1588 }
1589 }
1590
1591 return aIp.size();
1592}
1593
1594
1595int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP, int aIndex ) const
1596{
1597 int sum = 0;
1598
1599 for( int i = 0; i < SegmentCount(); i++ )
1600 {
1601 const SEG seg = CSegment( i );
1602 bool indexMatch = true;
1603
1604 if( aIndex >= 0 )
1605 {
1606 if( aIndex == SegmentCount() )
1607 {
1608 indexMatch = ( i == SegmentCount() - 1 );
1609 }
1610 else
1611 {
1612 indexMatch = ( i == aIndex );
1613 }
1614 }
1615
1616 if( indexMatch )
1617 {
1618 sum += ( aP - seg.A ).EuclideanNorm();
1619 return sum;
1620 }
1621 else
1622 sum += seg.Length();
1623 }
1624
1625 return -1;
1626}
1627
1628
1629bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
1630 bool aUseBBoxCache ) const
1631{
1632 /*
1633 * Don't check the bounding box unless it's cached. Building it is about the same speed as
1634 * the rigorous test below and so just slows things down by doing potentially two tests.
1635 */
1636 if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1637 return false;
1638
1639 if( !IsClosed() || GetPointCount() < 3 )
1640 return false;
1641
1642 bool inside = false;
1643
1644 /*
1645 * To check for interior points, we draw a line in the positive x direction from
1646 * the point. If it intersects an even number of segments, the point is outside the
1647 * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1648 *
1649 * Note: slope might be denormal here in the case of a horizontal line but we require our
1650 * y to move from above to below the point (or vice versa)
1651 *
1652 * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1653 * vector number-of-points times. This has a non-trivial impact on zone fill times.
1654 */
1655 int pointCount = GetPointCount();
1656
1657 for( int i = 0; i < pointCount; )
1658 {
1659 const auto p1 = GetPoint( i++ );
1660 const auto p2 = GetPoint( i == pointCount ? 0 : i );
1661 const auto diff = p2 - p1;
1662
1663 if( diff.y != 0 )
1664 {
1665 const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1666
1667 if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1668 inside = !inside;
1669 }
1670 }
1671
1672 // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1673 // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1674 if( aAccuracy <= 1 )
1675 return inside;
1676 else
1677 return inside || PointOnEdge( aPt, aAccuracy );
1678}
1679
1680
1681bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
1682{
1683 return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1684}
1685
1686
1687int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
1688{
1689 if( !GetPointCount() )
1690 {
1691 return -1;
1692 }
1693 else if( GetPointCount() == 1 )
1694 {
1695 VECTOR2I dist = GetPoint(0) - aPt;
1696 return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1697 }
1698
1699 for( size_t i = 0; i < GetSegmentCount(); i++ )
1700 {
1701 const SEG s = GetSegment( i );
1702
1703 if( s.A == aPt || s.B == aPt )
1704 return i;
1705
1706 if( s.Distance( aPt ) <= aAccuracy + 1 )
1707 return i;
1708 }
1709
1710 return -1;
1711}
1712
1713
1714bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
1715{
1716 if( !PointCount() )
1717 return false;
1718 else if( PointCount() == 1 )
1719 return m_points[0] == aP;
1720
1721 for( int i = 0; i < SegmentCount(); i++ )
1722 {
1723 const SEG s = CSegment( i );
1724
1725 if( s.A == aP || s.B == aP )
1726 return true;
1727
1728 if( s.Distance( aP ) <= aDist )
1729 return true;
1730 }
1731
1732 return false;
1733}
1734
1735
1736const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
1737{
1738 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1739 {
1740 for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1741 {
1742 const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1743
1744 if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1745 {
1746 INTERSECTION is;
1747 is.index_our = s1;
1748 is.index_their = s2;
1749 is.p = s2a;
1750 return is;
1751 }
1752 else if( CSegment( s1 ).Contains( s2b ) &&
1753 // for closed polylines, the ending point of the
1754 // last segment == starting point of the first segment
1755 // this is a normal case, not self intersecting case
1756 !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1757 {
1758 INTERSECTION is;
1759 is.index_our = s1;
1760 is.index_their = s2;
1761 is.p = s2b;
1762 return is;
1763 }
1764 else
1765 {
1766 OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1767
1768 if( p )
1769 {
1770 INTERSECTION is;
1771 is.index_our = s1;
1772 is.index_their = s2;
1773 is.p = *p;
1774 return is;
1775 }
1776 }
1777 }
1778 }
1779
1780 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
1781}
1782
1783
1785{
1786 std::vector<VECTOR2I> pts_unique;
1787 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
1788
1789 // Always try to keep at least 2 points otherwise, we're not really a line
1790 if( PointCount() < 3 )
1791 {
1792 return *this;
1793 }
1794 else if( PointCount() == 3 )
1795 {
1796 if( m_points[0] == m_points[1] )
1797 Remove( 1 );
1798
1799 return *this;
1800 }
1801
1802 int i = 0;
1803 int np = PointCount();
1804
1805 // stage 1: eliminate duplicate vertices
1806 while( i < np )
1807 {
1808 int j = i + 1;
1809
1810 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
1811 // one of them is part of a shape and one is not.
1812 while( j < np && m_points[i] == m_points[j] &&
1813 ( m_shapes[i] == m_shapes[j] ||
1814 m_shapes[i] == SHAPES_ARE_PT ||
1815 m_shapes[j] == SHAPES_ARE_PT ) )
1816 {
1817 j++;
1818 }
1819
1820 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
1821
1822 if( shapeToKeep == SHAPES_ARE_PT )
1823 shapeToKeep = m_shapes[j - 1];
1824
1825 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
1826 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
1827
1828 pts_unique.push_back( CPoint( i ) );
1829 shapes_unique.push_back( shapeToKeep );
1830
1831 i = j;
1832 }
1833
1834 m_points.clear();
1835 m_shapes.clear();
1836 np = pts_unique.size();
1837
1838 i = 0;
1839
1840 // stage 2: eliminate colinear segments
1841 while( i < np - 2 )
1842 {
1843 const VECTOR2I p0 = pts_unique[i];
1844 int n = i;
1845
1846 if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
1847 && shapes_unique[i + 1] == SHAPES_ARE_PT )
1848 {
1849 while( n < np - 2
1850 && ( SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
1851 || SEG( p0, pts_unique[n + 2] ).Collinear( SEG( p0, pts_unique[n + 1] ) ) ) )
1852 n++;
1853 }
1854
1855 m_points.push_back( p0 );
1856 m_shapes.push_back( shapes_unique[i] );
1857
1858 if( n > i )
1859 i = n;
1860
1861 if( n == np - 2 )
1862 {
1863 m_points.push_back( pts_unique[np - 1] );
1864 m_shapes.push_back( shapes_unique[np - 1] );
1865 return *this;
1866 }
1867
1868 i++;
1869 }
1870
1871 if( np > 1 )
1872 {
1873 m_points.push_back( pts_unique[np - 2] );
1874 m_shapes.push_back( shapes_unique[np - 2] );
1875 }
1876
1877 m_points.push_back( pts_unique[np - 1] );
1878 m_shapes.push_back( shapes_unique[np - 1] );
1879
1880 assert( m_points.size() == m_shapes.size() );
1881
1882 return *this;
1883}
1884
1885
1887 bool aAllowInternalShapePoints ) const
1888{
1889 if( PointCount() == 0 )
1890 {
1891 // The only right answer here is "don't crash".
1892 return { 0, 0 };
1893 }
1894
1895 int min_d = std::numeric_limits<int>::max();
1896 int nearest = 0;
1897
1898 for( int i = 0; i < SegmentCount(); i++ )
1899 {
1900 int d = CSegment( i ).Distance( aP );
1901
1902 if( d < min_d )
1903 {
1904 min_d = d;
1905 nearest = i;
1906 }
1907 }
1908
1909 if( !aAllowInternalShapePoints )
1910 {
1911 //Snap to arc end points if the closest found segment is part of an arc segment
1912 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
1913 {
1914 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
1915 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
1916
1917 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
1918 nearest++;
1919
1920 // Is this the start or end of an arc? If so, return it directly
1921 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
1922 {
1923 return m_points[nearest];
1924 }
1925 else
1926 {
1927 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
1928 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
1929 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
1930
1931 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
1932 return nearestArc.GetP1();
1933 else
1934 return nearestArc.GetP0();
1935 }
1936
1937 }
1938 }
1939
1940 return CSegment( nearest ).NearestPoint( aP );
1941}
1942
1943
1944const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
1945{
1946 if( PointCount() == 0 )
1947 {
1948 // The only right answer here is "don't crash".
1949 return { 0, 0 };
1950 }
1951
1952 int nearest = 0;
1953
1954 dist = std::numeric_limits<int>::max();
1955
1956 for( int i = 0; i < PointCount(); i++ )
1957 {
1958 int d = aSeg.LineDistance( CPoint( i ) );
1959
1960 if( d < dist )
1961 {
1962 dist = d;
1963 nearest = i;
1964 }
1965 }
1966
1967 return CPoint( nearest );
1968}
1969
1970
1972{
1973 int min_d = std::numeric_limits<int>::max();
1974 int nearest = 0;
1975
1976 for( int i = 0; i < SegmentCount(); i++ )
1977 {
1978 int d = CSegment( i ).Distance( aP );
1979
1980 if( d < min_d )
1981 {
1982 min_d = d;
1983 nearest = i;
1984 }
1985 }
1986
1987 return nearest;
1988}
1989
1990
1991const std::string SHAPE_LINE_CHAIN::Format( bool aCplusPlus ) const
1992{
1993 std::stringstream ss;
1994
1995 ss << "SHAPE_LINE_CHAIN( { ";
1996
1997 for( int i = 0; i < PointCount(); i++ )
1998 {
1999 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
2000
2001 if( i != PointCount() -1 )
2002 ss << ", ";
2003 }
2004
2005 ss << "}, " << ( m_closed ? "true" : "false" );
2006 ss << " );";
2007
2008 return ss.str();
2009
2010 /* fixme: arcs
2011 for( size_t i = 0; i < m_arcs.size(); i++ )
2012 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
2013 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
2014 << m_arcs[i].GetCentralAngle().AsDegrees();
2015
2016 return ss.str();*/
2017}
2018
2019
2021{
2022 SHAPE_LINE_CHAIN a(*this), b( aOther );
2023 a.Simplify();
2024 b.Simplify();
2025
2026 if( a.m_points.size() != b.m_points.size() )
2027 return false;
2028
2029 for( int i = 0; i < a.PointCount(); i++ )
2030 {
2031 if( a.CPoint( i ) != b.CPoint( i ) )
2032 return false;
2033 }
2034
2035 return true;
2036}
2037
2038
2040{
2042 return Intersect( aChain, dummy ) != 0;
2043}
2044
2045
2047{
2048 return new SHAPE_LINE_CHAIN( *this );
2049}
2050
2051
2052bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
2053{
2054 size_t n_pts;
2055 size_t n_arcs;
2056
2057 m_points.clear();
2058 aStream >> n_pts;
2059
2060 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
2061 if( n_pts > aStream.str().size() )
2062 return false;
2063
2064 aStream >> m_closed;
2065 aStream >> n_arcs;
2066
2067 if( n_arcs > aStream.str().size() )
2068 return false;
2069
2070 for( size_t i = 0; i < n_pts; i++ )
2071 {
2072 int x, y;
2073 ssize_t ind;
2074 aStream >> x;
2075 aStream >> y;
2076 m_points.emplace_back( x, y );
2077
2078 aStream >> ind;
2079 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
2080 }
2081
2082 for( size_t i = 0; i < n_arcs; i++ )
2083 {
2084 VECTOR2I p0, pc;
2085 double angle;
2086
2087 aStream >> pc.x;
2088 aStream >> pc.y;
2089 aStream >> p0.x;
2090 aStream >> p0.y;
2091 aStream >> angle;
2092
2093 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
2094 }
2095
2096 return true;
2097}
2098
2099
2100const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
2101{
2102 int total = 0;
2103
2104 if( aPathLength == 0 )
2105 return CPoint( 0 );
2106
2107 for( int i = 0; i < SegmentCount(); i++ )
2108 {
2109 const SEG& s = CSegment( i );
2110 int l = s.Length();
2111
2112 if( total + l >= aPathLength )
2113 {
2114 VECTOR2I d( s.B - s.A );
2115 return s.A + d.Resize( aPathLength - total );
2116 }
2117
2118 total += l;
2119 }
2120
2121 return CPoint( -1 );
2122}
2123
2124
2125double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
2126{
2127 // see https://www.mathopenref.com/coordpolygonarea2.html
2128
2129 if( !m_closed )
2130 return 0.0;
2131
2132 double area = 0.0;
2133 int size = m_points.size();
2134
2135 for( int i = 0, j = size - 1; i < size; ++i )
2136 {
2137 area += ( (double) m_points[j].x + m_points[i].x ) *
2138 ( (double) m_points[j].y - m_points[i].y );
2139 j = i;
2140 }
2141
2142 if( aAbsolute )
2143 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2144 else
2145 return -area * 0.5; // The result would be negative if points are anti-clockwise
2146}
2147
2148
2149void SHAPE_LINE_CHAIN::Split( const VECTOR2I& aStart, const VECTOR2I& aEnd, SHAPE_LINE_CHAIN& aPre,
2150 SHAPE_LINE_CHAIN& aMid, SHAPE_LINE_CHAIN& aPost ) const
2151{
2152 VECTOR2I cp( aEnd );
2153
2154 VECTOR2I n = NearestPoint( cp, false );
2155 VECTOR2I m = NearestPoint( aStart, false );
2156
2157 SHAPE_LINE_CHAIN l( *this );
2158 l.Split( n, true );
2159 l.Split( m, true );
2160
2161 int i_start = l.Find( m );
2162 int i_end = l.Find( n );
2163
2164 if( i_start > i_end )
2165 {
2166 l = l.Reverse();
2167 i_start = l.Find( m );
2168 i_end = l.Find( n );
2169 }
2170
2171 aPre = l.Slice( 0, i_start );
2172 aPost = l.Slice( i_end, -1 );
2173 aMid = l.Slice( i_start, i_end );
2174}
2175
2176
2177bool SHAPE_LINE_CHAIN::OffsetLine( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
2178 SHAPE_LINE_CHAIN& aLeft, SHAPE_LINE_CHAIN& aRight,
2179 bool aSimplify ) const
2180{
2181 if( PointCount() < 2 )
2182 return false;
2183
2184 SHAPE_POLY_SET poly;
2185 poly.OffsetLineChain( *this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2186
2187 if( poly.OutlineCount() != 1 )
2188 return false;
2189
2190 if( poly.COutline( 0 ).PointCount() < 3 )
2191 return false;
2192
2193 if( poly.HasHoles() )
2194 return false;
2195
2196 SHAPE_LINE_CHAIN outline = poly.COutline( 0 );
2197
2198 wxASSERT( outline.IsClosed() );
2199
2200 const VECTOR2I& start = CPoint( 0 );
2201 const VECTOR2I& end = CPoint( -1 );
2202
2203 outline.Split( start, true );
2204 outline.Split( end, true );
2205
2206 const int idA = outline.Find( start );
2207 const int idB = outline.Find( end );
2208
2209 if( idA == -1 || idB == -1 )
2210 return false;
2211
2212 aLeft.Clear();
2213 aRight.Clear();
2214
2215 for( int i = idA;; )
2216 {
2217 aLeft.Append( outline.CPoint( i ) );
2218
2219 i = ( i + 1 ) % outline.PointCount();
2220
2221 if( i == idB )
2222 {
2223 aLeft.Append( outline.CPoint( i ) );
2224 break;
2225 }
2226
2227 if( i == idA )
2228 return false;
2229 }
2230
2231 if( aLeft.PointCount() < 2 )
2232 return false;
2233
2234 for( int i = idB;; )
2235 {
2236 aRight.Append( outline.CPoint( i ) );
2237
2238 i = ( i + 1 ) % outline.PointCount();
2239
2240 if( i == idA )
2241 {
2242 aRight.Append( outline.CPoint( i ) );
2243 break;
2244 }
2245
2246 if( i == idB )
2247 return false;
2248 }
2249
2250 if( aRight.PointCount() < 2 )
2251 return false;
2252
2253 if( aLeft.CPoint( 0 ) != start )
2254 {
2255 aLeft = aLeft.Reverse();
2256 wxASSERT( aLeft.CPoint( 0 ) == start );
2257 }
2258
2259 if( aRight.CPoint( 0 ) != start )
2260 {
2261 aRight = aRight.Reverse();
2262 wxASSERT( aRight.CPoint( 0 ) == start );
2263 }
2264
2265 SEG base( CPoint( 0 ), CPoint( 1 ) );
2266 int sideLeft = base.Side( aLeft.CPoint( 1 ) );
2267 int sideRight = base.Side( aRight.CPoint( 1 ) );
2268
2269 if( sideLeft == 0 || sideRight == 0 )
2270 return false;
2271
2272 if( sideLeft == sideRight )
2273 return false;
2274
2275 if( sideLeft > 0 && sideRight < 0 )
2276 std::swap( aLeft, aRight );
2277
2278 if( aLeft.PointCount() < 4 )
2279 return false;
2280
2281 if( aRight.PointCount() < 4 )
2282 return false;
2283
2284 aLeft.Remove( 0 );
2285 aLeft.Remove( aLeft.PointCount() - 1 );
2286
2287 aRight.Remove( 0 );
2288 aRight.Remove( aRight.PointCount() - 1 );
2289
2290 return true;
2291}
2292
2293
2295 ERROR_LOC aErrorLoc ) const
2296{
2297 aBuffer.AddOutline( *this );
2298}
2299
2300
2302 m_point( aPoint ),
2303 m_finished( false ),
2304 m_state( 0 ),
2305 m_count( 0 )
2306{
2307}
2308
2309
2311 const VECTOR2I& ip, const VECTOR2I& ipNext )
2312{
2313 if( ipNext.y == m_point.y )
2314 {
2315 if( ( ipNext.x == m_point.x )
2316 || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
2317 {
2318 m_finished = true;
2319 m_state = -1;
2320 return false;
2321 }
2322 }
2323
2324 if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
2325 {
2326 if( ip.x >= m_point.x )
2327 {
2328 if( ipNext.x > m_point.x )
2329 {
2330 m_state = 1 - m_state;
2331 }
2332 else
2333 {
2334 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2335 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2336
2337 if( !d )
2338 {
2339 m_finished = true;
2340 m_state = -1;
2341 return false;
2342 }
2343
2344 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2345 m_state = 1 - m_state;
2346 }
2347 }
2348 else
2349 {
2350 if( ipNext.x > m_point.x )
2351 {
2352 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2353 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2354
2355 if( !d )
2356 {
2357 m_finished = true;
2358 m_state = -1;
2359 return false;
2360 }
2361
2362 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2363 m_state = 1 - m_state;
2364 }
2365 }
2366 }
2367
2368 return true;
2369}
2370
2371
2373{
2374 if( !m_count )
2375 {
2376 m_lastPoint = aPolyline.CPoint( 0 );
2377 m_firstPoint = aPolyline.CPoint( 0 );
2378 }
2379
2380 m_count += aPolyline.PointCount();
2381
2382 for( int i = 1; i < aPolyline.PointCount(); i++ )
2383 {
2384 auto p = aPolyline.CPoint( i );
2385
2386 if( !processVertex( m_lastPoint, p ) )
2387 return;
2388
2389 m_lastPoint = p;
2390 }
2391
2392}
2393
2394
2396{
2397 processVertex( m_lastPoint, m_firstPoint );
2398 return m_state > 0;
2399}
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:270
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:589
Definition: seg.h:42
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:291
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:341
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:269
int Length() const
Return the length (this).
Definition: seg.h:326
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:196
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:329
bool Contains(const SEG &aSeg) const
Definition: seg.h:307
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
bool IsClockwise() const
Definition: shape_arc.cpp:370
int GetWidth() const
Definition: shape_arc.h:159
void SetWidth(int aWidth)
Definition: shape_arc.h:154
SHAPE_ARC & ConstructFromStartEndCenter(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aClockwise=false, double aWidth=0)
Constructs this arc from the given start, end and center.
Definition: shape_arc.cpp:210
const VECTOR2I & GetP1() const
Definition: shape_arc.h:113
bool Collide(const SEG &aSeg, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the segment aSeg than aClearance,...
Definition: shape_arc.cpp:242
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:497
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:223
void Reverse()
Definition: shape_arc.cpp:612
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:460
const VECTOR2I & GetP0() const
Definition: shape_arc.h:112
bool processVertex(const VECTOR2I &ip, const VECTOR2I &ipNext)
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
virtual size_t GetPointCount() const =0
virtual size_t GetSegmentCount() const =0
virtual const VECTOR2I GetPoint(int aIndex) const =0
virtual BOX2I * GetCachedBBox() const
Definition: shape.h:351
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
virtual bool IsClosed() const =0
virtual const SEG GetSegment(int aIndex) const =0
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const override
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
std::vector< std::pair< ssize_t, ssize_t > > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
bool IsPtOnArc(size_t aPtIndex) const
const SHAPE_ARC & Arc(size_t aArc) const
void splitArc(ssize_t aPtIndex, bool aCoincident=false)
Splits an arc into two arcs at aPtIndex.
const std::optional< INTERSECTION > SelfIntersecting() const
Check if the line chain is self-intersecting.
bool Parse(std::stringstream &aStream) override
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Check if point aP is closer to (or on) an edge or vertex of the line chain.
std::vector< SHAPE_ARC > m_arcs
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
ClipperLib::Path convertToClipper(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
const VECTOR2I PointAlong(int aPathLength) const
int Split(const VECTOR2I &aP, bool aExact=false)
Insert the point aP belonging to one of the our segments, splitting the adjacent segment in two.
void fixIndicesRotation()
Fix indices of this chain to ensure arcs are not split between the end and start indices.
std::vector< VECTOR2I > m_points
array of vertices
int FindSegment(const VECTOR2I &aP, int aThreshold=1) const
Search for segment containing point aP.
int ShapeCount() const
Return the number of shapes (line segments or arcs) in this line chain.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Find all intersection points between our line chain and the segment aSeg.
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
SHAPE_LINE_CHAIN()
Initialize an empty line chain.
int PointCount() const
Return the number of points (vertices) in this line chain.
bool IsArcEnd(size_t aIndex) const
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
void TransformToPolygon(SHAPE_POLY_SET &aBuffer, int aError, ERROR_LOC aErrorLoc) const override
Fills a SHAPE_POLY_SET with a polygon representation of this shape.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if point aP lies closer to us than aClearance.
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
void mergeFirstLastPointIfNeeded()
Merge the first and last point if they are the same and this chain is closed.
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
ssize_t ArcIndex(size_t aSegment) const
Return the arc index for the given segment index.
void Clear()
Remove all points from the line chain.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
BOX2I m_bbox
cached bounding box
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Return a subset of this line chain containing the [start_index, end_index] range of points.
bool m_closed
is the line chain closed?
const std::vector< SHAPE_ARC > & CArcs() const
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
int NextShape(int aPointIndex) const
Return the vertex index of the next shape in the chain, or -1 if aPointIndex is the last shape.
double Area(bool aAbsolute=true) const
Return the area of this chain.
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both).
void amendArc(size_t aArcIndex, const VECTOR2I &aNewStart, const VECTOR2I &aNewEnd)
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
void Rotate(const EDA_ANGLE &aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
virtual const SEG GetSegment(int aIndex) const override
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
const std::vector< std::pair< ssize_t, ssize_t > > & CShapes() const
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Find a point on the line chain that is closest to point aP.
int SegmentCount() const
Return the number of segments in this line chain.
int PathLength(const VECTOR2I &aP, int aIndex=-1) const
Compute the walk path length from the beginning of the line chain and the point aP belonging to our l...
const std::string Format(bool aCplusPlus=true) const override
Clipper2Lib::Path64 convertToClipper2(bool aRequiredOrientation, std::vector< CLIPPER_Z_VALUE > &aZValueBuffer, std::vector< SHAPE_ARC > &aArcBuffer) const
Create a new Clipper2 path from the SHAPE_LINE_CHAIN in a given orientation.
static const std::pair< ssize_t, ssize_t > SHAPES_ARE_PT
void convertArc(ssize_t aArcIndex)
Convert an arc to only a point chain by removing the arc and references.
virtual size_t GetSegmentCount() const override
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
size_t ArcCount() const
const SEG CSegment(int aIndex) const
Return a constant copy of the aIndex segment in the line chain.
bool IsArcSegment(size_t aSegment) const
void RemoveShape(int aPointIndex)
Remove the shape at the given index from the line chain.
void Insert(size_t aVertex, const VECTOR2I &aP)
bool IsArcStart(size_t aIndex) const
bool IsSharedPt(size_t aIndex) const
Test if a point is shared between multiple shapes.
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
static const ssize_t SHAPE_IS_PT
bool OffsetLine(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, SHAPE_LINE_CHAIN &aLeft, SHAPE_LINE_CHAIN &aRight, bool aSimplify=false) const
Creates line chains aLeft and aRight offset to this line chain.
Represent a set of closed polygons.
bool HasHoles() const
Return true if the polygon set has any holes.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
void OffsetLineChain(const SHAPE_LINE_CHAIN &aLine, int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify)
Perform offsetting of a line chain.
int OutlineCount() const
Return the number of outlines in the set.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
An abstract shape on 2D plane.
Definition: shape.h:126
VECTOR2I::extended_type ecoord
Definition: shape.h:284
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:75
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:265
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:350
CORNER_STRATEGY
define how inflate transform build inflated polygon
@ DEGREES_T
Definition: eda_angle.h:31
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
bool pair_contains(const std::pair< _Type, _Type > __pair, _Value __value)
Returns true if either of the elements in an std::pair contains the given value.
Definition: kicad_algo.h:113
void run_on_pair(std::pair< _Type, _Type > &__pair, _Function __f)
Apply a function to the first and second element of a std::pair.
Definition: kicad_algo.h:45
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
@ SH_LINE_CHAIN
line chain (polyline)
Definition: shape.h:49
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
std::vector< FAB_LAYER_COLOR > dummy
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
Represent an intersection between two line segments.
bool is_corner_their
When true, the corner [index_their] of the 'their' line lies exactly on 'our' line.
bool is_corner_our
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.
int index_our
Index of the intersecting corner/segment in the 'our' (== this) line.
VECTOR2I p
Point of intersection between our and their.
bool valid
Auxiliary flag to avoid copying intersection info to intersection refining code, used by the refining...
int index_their
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line.
bool operator()(const SHAPE_LINE_CHAIN::INTERSECTION &aA, const SHAPE_LINE_CHAIN::INTERSECTION &aB) const
compareOriginDistance(const VECTOR2I &aOrigin)
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
Definition: trigo.cpp:228
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:128
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:129