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-2024 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/circle.h>
36#include <geometry/seg.h> // for SEG, OPT_VECTOR2I
39#include <math/box2.h> // for BOX2I
40#include <math/util.h> // for rescale
41#include <math/vector2d.h> // for VECTOR2, VECTOR2I
42#include <trigo.h> // for RotatePoint
43
44class SHAPE;
45
46const ssize_t SHAPE_LINE_CHAIN::SHAPE_IS_PT = -1;
47const std::pair<ssize_t, ssize_t> SHAPE_LINE_CHAIN::SHAPES_ARE_PT = { SHAPE_IS_PT, SHAPE_IS_PT };
48
49
50SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<int>& aV)
51 : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
52{
53 for(size_t i = 0; i < aV.size(); i+= 2 )
54 {
55 Append( aV[i], aV[i+1] );
56 }
57}
58
59
60SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const std::vector<VECTOR2I>& aV, bool aClosed ) :
62 m_closed( false ),
63 m_width( 0 )
64{
65 m_points = aV;
66 m_shapes = std::vector<std::pair<ssize_t, ssize_t>>( aV.size(), SHAPES_ARE_PT );
67 SetClosed( aClosed );
68}
69
70
71SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const SHAPE_ARC& aArc, bool aClosed ) :
73 m_closed( false ),
74 m_width( aArc.GetWidth() )
75{
76 Append( aArc );
77 SetClosed( aClosed );
78}
79
80
81SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath,
82 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
83 const std::vector<SHAPE_ARC>& aArcBuffer ) :
85 m_closed( true ), m_width( 0 )
86{
87 std::map<ssize_t, ssize_t> loadedArcs;
88 m_points.reserve( aPath.size() );
89 m_shapes.reserve( aPath.size() );
90
91 auto loadArc =
92 [&]( ssize_t aArcIndex ) -> ssize_t
93 {
94 if( aArcIndex == SHAPE_IS_PT )
95 {
96 return SHAPE_IS_PT;
97 }
98 else if( loadedArcs.count( aArcIndex ) == 0 )
99 {
100 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
101 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
102 }
103
104 return loadedArcs.at( aArcIndex );
105 };
106
107 for( size_t ii = 0; ii < aPath.size(); ++ii )
108 {
109 Append( aPath[ii].X, aPath[ii].Y );
110
111 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].Z].m_FirstArcIdx );
112 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].Z].m_SecondArcIdx );
113 }
114
115 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
116 // removed during Append() and we would have different number of shapes to points
117 wxASSERT( m_shapes.size() == m_points.size() );
118
119 // Clipper might mess up the rotation of the indices such that an arc can be split between
120 // the end point and wrap around to the start point. Lets fix the indices up now
122}
123
124
125SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN( const Clipper2Lib::Path64& aPath,
126 const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
127 const std::vector<SHAPE_ARC>& aArcBuffer ) :
129 m_closed( true ), m_width( 0 )
130{
131 std::map<ssize_t, ssize_t> loadedArcs;
132 m_points.reserve( aPath.size() );
133 m_shapes.reserve( aPath.size() );
134
135 auto loadArc =
136 [&]( ssize_t aArcIndex ) -> ssize_t
137 {
138 if( aArcIndex == SHAPE_IS_PT )
139 {
140 return SHAPE_IS_PT;
141 }
142 else if( loadedArcs.count( aArcIndex ) == 0 )
143 {
144 loadedArcs.insert( { aArcIndex, m_arcs.size() } );
145 m_arcs.push_back( aArcBuffer.at( aArcIndex ) );
146 }
147
148 return loadedArcs.at( aArcIndex );
149 };
150
151 for( size_t ii = 0; ii < aPath.size(); ++ii )
152 {
153 Append( aPath[ii].x, aPath[ii].y );
154
155 m_shapes[ii].first = loadArc( aZValueBuffer[aPath[ii].z].m_FirstArcIdx );
156 m_shapes[ii].second = loadArc( aZValueBuffer[aPath[ii].z].m_SecondArcIdx );
157 }
158
159 // Clipper shouldn't return duplicate contiguous points. if it did, these would be
160 // removed during Append() and we would have different number of shapes to points
161 wxASSERT( m_shapes.size() == m_points.size() );
162
163 // Clipper might mess up the rotation of the indices such that an arc can be split between
164 // the end point and wrap around to the start point. Lets fix the indices up now
166}
167
168
169ClipperLib::Path SHAPE_LINE_CHAIN::convertToClipper( bool aRequiredOrientation,
170 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
171 std::vector<SHAPE_ARC>& aArcBuffer ) const
172{
173 ClipperLib::Path c_path;
174 SHAPE_LINE_CHAIN input;
175 bool orientation = Area( false ) >= 0;
176 ssize_t shape_offset = aArcBuffer.size();
177
178 if( orientation != aRequiredOrientation )
179 input = Reverse();
180 else
181 input = *this;
182
183 int pointCount = input.PointCount();
184 c_path.reserve( pointCount );
185
186 for( int i = 0; i < pointCount; i++ )
187 {
188 const VECTOR2I& vertex = input.CPoint( i );
189
190 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
191 size_t z_value_ptr = aZValueBuffer.size();
192 aZValueBuffer.push_back( z_value );
193
194 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
195 }
196
197 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
198
199 return c_path;
200}
201
202
203Clipper2Lib::Path64 SHAPE_LINE_CHAIN::convertToClipper2( bool aRequiredOrientation,
204 std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
205 std::vector<SHAPE_ARC>& aArcBuffer ) const
206{
207 Clipper2Lib::Path64 c_path;
208 SHAPE_LINE_CHAIN input;
209 bool orientation = Area( false ) >= 0;
210 ssize_t shape_offset = aArcBuffer.size();
211
212 if( orientation != aRequiredOrientation )
213 input = Reverse();
214 else
215 input = *this;
216
217 int pointCount = input.PointCount();
218 c_path.reserve( pointCount );
219
220 for( int i = 0; i < pointCount; i++ )
221 {
222 const VECTOR2I& vertex = input.CPoint( i );
223
224 CLIPPER_Z_VALUE z_value( input.m_shapes[i], shape_offset );
225 size_t z_value_ptr = aZValueBuffer.size();
226 aZValueBuffer.push_back( z_value );
227
228 c_path.emplace_back( vertex.x, vertex.y, z_value_ptr );
229 }
230
231 aArcBuffer.insert( aArcBuffer.end(), input.m_arcs.begin(), input.m_arcs.end() );
232
233 return c_path;
234}
235
236
238{
239 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
240
241 if( m_shapes.size() <= 1 )
242 return;
243
244 size_t rotations = 0;
245
246 while( ArcIndex( 0 ) != SHAPE_IS_PT
247 && !IsArcStart( 0 ) )
248 {
249 // Rotate right
250 std::rotate( m_points.rbegin(), m_points.rbegin() + 1, m_points.rend() );
251 std::rotate( m_shapes.rbegin(), m_shapes.rbegin() + 1, m_shapes.rend() );
252
253 // Sanity check - avoid infinite loops (NB: wxCHECK is not thread-safe)
254 if( rotations++ > m_shapes.size() )
255 return;
256 }
257}
258
259
261{
262 if( m_closed )
263 {
264 if( m_points.size() > 1 && m_points.front() == m_points.back() )
265 {
266 if( ArcIndex( m_shapes.size() - 1 ) != SHAPE_IS_PT )
267 {
268 m_shapes.front().second = m_shapes.front().first;
269 m_shapes.front().first = ArcIndex( m_shapes.size() - 1 ) ;
270 }
271
272 m_points.pop_back();
273 m_shapes.pop_back();
274
276 }
277 }
278 else
279 {
280 if( m_points.size() > 1 && IsSharedPt( 0 ) )
281 {
282 // Create a duplicate point at the end
283 m_points.push_back( m_points.front() );
284 m_shapes.push_back( { m_shapes.front().first, SHAPE_IS_PT });
285 m_shapes.front().first = m_shapes.front().second;
286 m_shapes.front().second = SHAPE_IS_PT;
287 }
288 }
289}
290
291
292void SHAPE_LINE_CHAIN::convertArc( ssize_t aArcIndex )
293{
294 if( aArcIndex < 0 )
295 aArcIndex += m_arcs.size();
296
297 if( aArcIndex >= static_cast<ssize_t>( m_arcs.size() ) )
298 return;
299
300 // Clear the shapes references
301 for( auto& sh : m_shapes )
302 {
304 [&]( ssize_t& aShapeIndex )
305 {
306 if( aShapeIndex == aArcIndex )
307 aShapeIndex = SHAPE_IS_PT;
308
309 if( aShapeIndex > aArcIndex )
310 --aShapeIndex;
311 } );
312
313 if( sh.second != SHAPE_IS_PT && sh.first == SHAPE_IS_PT )
314 std::swap( sh.first, sh.second );
315 }
316
317 m_arcs.erase( m_arcs.begin() + aArcIndex );
318}
319
320
321void SHAPE_LINE_CHAIN::amendArc( size_t aArcIndex, const VECTOR2I& aNewStart,
322 const VECTOR2I& aNewEnd )
323{
324 wxCHECK_MSG( aArcIndex < m_arcs.size(), /* void */,
325 wxT( "Invalid arc index requested." ) );
326
327 SHAPE_ARC& theArc = m_arcs[aArcIndex];
328
329 // Try to preseve the centre of the original arc
330 SHAPE_ARC newArc;
331 newArc.ConstructFromStartEndCenter( aNewStart, aNewEnd, theArc.GetCenter(),
332 theArc.IsClockwise() );
333
334 m_arcs[aArcIndex] = newArc;
335}
336
337
338void SHAPE_LINE_CHAIN::splitArc( ssize_t aPtIndex, bool aCoincident )
339{
340 if( aPtIndex < 0 )
341 aPtIndex += m_shapes.size();
342
343 if( !IsSharedPt( aPtIndex ) && IsArcStart( aPtIndex ) )
344 return; // Nothing to do
345
346 if( !IsPtOnArc( aPtIndex ) )
347 return; // Nothing to do
348
349 wxCHECK_MSG( aPtIndex < static_cast<ssize_t>( m_shapes.size() ), /* void */,
350 wxT( "Invalid point index requested." ) );
351
352 if( IsSharedPt( aPtIndex ) || IsArcEnd( aPtIndex ) )
353 {
354 if( aCoincident || aPtIndex == 0 )
355 return; // nothing to do
356
357 ssize_t firstArcIndex = m_shapes[aPtIndex].first;
358
359 const VECTOR2I& newStart = m_arcs[firstArcIndex].GetP0(); // don't amend the start
360 const VECTOR2I& newEnd = m_points[aPtIndex - 1];
361 amendArc( firstArcIndex, newStart, newEnd );
362
363 if( IsSharedPt( aPtIndex ) )
364 {
365 m_shapes[aPtIndex].first = m_shapes[aPtIndex].second;
366 m_shapes[aPtIndex].second = SHAPE_IS_PT;
367 }
368 else
369 {
370 m_shapes[aPtIndex] = SHAPES_ARE_PT;
371 }
372
373 return;
374 }
375
376 ssize_t currArcIdx = ArcIndex( aPtIndex );
377 SHAPE_ARC& currentArc = m_arcs[currArcIdx];
378
379 SHAPE_ARC newArc1;
380 SHAPE_ARC newArc2;
381
382 VECTOR2I arc1End = ( aCoincident ) ? m_points[aPtIndex] : m_points[aPtIndex - 1];
383 VECTOR2I arc2Start = m_points[aPtIndex];
384
385 newArc1.ConstructFromStartEndCenter( currentArc.GetP0(), arc1End, currentArc.GetCenter(),
386 currentArc.IsClockwise() );
387
388 newArc2.ConstructFromStartEndCenter( arc2Start, currentArc.GetP1(), currentArc.GetCenter(),
389 currentArc.IsClockwise() );
390
391 if( !aCoincident && ArcIndex( aPtIndex - 1 ) != currArcIdx )
392 {
393 //Ignore newArc1 as it has zero points
394 m_arcs[currArcIdx] = newArc2;
395 }
396 else
397 {
398 m_arcs[currArcIdx] = newArc1;
399 m_arcs.insert( m_arcs.begin() + currArcIdx + 1, newArc2 );
400
401 if( aCoincident )
402 {
403 m_shapes[aPtIndex].second = currArcIdx + 1;
404 aPtIndex++;
405 }
406
407 // Only change the arc indices for the second half of the point range
408 for( int i = aPtIndex; i < PointCount(); i++ )
409 {
410 alg::run_on_pair( m_shapes[i], [&]( ssize_t& aIndex ) {
411 if( aIndex != SHAPE_IS_PT )
412 aIndex++;
413 } );
414 }
415 }
416}
417
418
419bool SHAPE_LINE_CHAIN_BASE::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
420 VECTOR2I* aLocation ) const
421{
422 if( IsClosed() && PointInside( aP, aClearance ) )
423 {
424 if( aLocation )
425 *aLocation = aP;
426
427 if( aActual )
428 *aActual = 0;
429
430 return true;
431 }
432
433 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
434 SEG::ecoord clearance_sq = SEG::Square( aClearance );
435 VECTOR2I nearest;
436
437 for( size_t i = 0; i < GetSegmentCount(); i++ )
438 {
439 const SEG& s = GetSegment( i );
440 VECTOR2I pn = s.NearestPoint( aP );
441 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
442
443 if( dist_sq < closest_dist_sq )
444 {
445 nearest = pn;
446 closest_dist_sq = dist_sq;
447
448 if( closest_dist_sq == 0 )
449 break;
450
451 // If we're not looking for aActual then any collision will do
452 if( closest_dist_sq < clearance_sq && !aActual )
453 break;
454 }
455 }
456
457 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
458 {
459 if( aLocation )
460 *aLocation = nearest;
461
462 if( aActual )
463 *aActual = sqrt( closest_dist_sq );
464
465 return true;
466 }
467
468 return false;
469}
470
471
472bool SHAPE_LINE_CHAIN::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
473 VECTOR2I* aLocation ) const
474{
475 if( IsClosed() && PointInside( aP, aClearance ) )
476 {
477 if( aLocation )
478 *aLocation = aP;
479
480 if( aActual )
481 *aActual = 0;
482
483 return true;
484 }
485
486 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
487 SEG::ecoord clearance_sq = SEG::Square( aClearance );
488 VECTOR2I nearest;
489
490 // Collide line segments
491 for( size_t i = 0; i < GetSegmentCount(); i++ )
492 {
493 if( IsArcSegment( i ) )
494 continue;
495
496 const SEG& s = GetSegment( i );
497 VECTOR2I pn = s.NearestPoint( aP );
498 SEG::ecoord dist_sq = ( pn - aP ).SquaredEuclideanNorm();
499
500 if( dist_sq < closest_dist_sq )
501 {
502 nearest = pn;
503 closest_dist_sq = dist_sq;
504
505 if( closest_dist_sq == 0 )
506 break;
507
508 // If we're not looking for aActual then any collision will do
509 if( closest_dist_sq < clearance_sq && !aActual )
510 break;
511 }
512 }
513
514 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
515 {
516 if( aLocation )
517 *aLocation = nearest;
518
519 if( aActual )
520 *aActual = sqrt( closest_dist_sq );
521
522 return true;
523 }
524
525 // Collide arc segments
526 for( size_t i = 0; i < ArcCount(); i++ )
527 {
528 const SHAPE_ARC& arc = Arc( i );
529
530 // The arcs in the chain should have zero width
531 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
532
533 if( arc.Collide( aP, aClearance, aActual, aLocation ) )
534 return true;
535 }
536
537 return false;
538}
539
540
541void SHAPE_LINE_CHAIN::Rotate( const EDA_ANGLE& aAngle, const VECTOR2I& aCenter )
542{
543 for( VECTOR2I& pt : m_points )
544 RotatePoint( pt, aCenter, aAngle );
545
546 for( SHAPE_ARC& arc : m_arcs )
547 arc.Rotate( aAngle, aCenter );
548}
549
550
551bool SHAPE_LINE_CHAIN_BASE::Collide( const SEG& aSeg, int aClearance, int* aActual,
552 VECTOR2I* aLocation ) const
553{
554 if( IsClosed() && PointInside( aSeg.A ) )
555 {
556 if( aLocation )
557 *aLocation = aSeg.A;
558
559 if( aActual )
560 *aActual = 0;
561
562 return true;
563 }
564
565 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
566 SEG::ecoord clearance_sq = SEG::Square( aClearance );
567 VECTOR2I nearest;
568
569 for( size_t i = 0; i < GetSegmentCount(); i++ )
570 {
571 const SEG& s = GetSegment( i );
572 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
573
574 if( dist_sq < closest_dist_sq )
575 {
576 if( aLocation )
577 nearest = s.NearestPoint( aSeg );
578
579 closest_dist_sq = dist_sq;
580
581 if( closest_dist_sq == 0)
582 break;
583
584 // If we're not looking for aActual then any collision will do
585 if( closest_dist_sq < clearance_sq && !aActual )
586 break;
587 }
588 }
589
590 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
591 {
592 if( aLocation )
593 *aLocation = nearest;
594
595 if( aActual )
596 *aActual = sqrt( closest_dist_sq );
597
598 return true;
599 }
600
601 return false;
602}
603
604
605bool SHAPE_LINE_CHAIN::Collide( const SEG& aSeg, int aClearance, int* aActual,
606 VECTOR2I* aLocation ) const
607{
608 if( IsClosed() && PointInside( aSeg.A ) )
609 {
610 if( aLocation )
611 *aLocation = aSeg.A;
612
613 if( aActual )
614 *aActual = 0;
615
616 return true;
617 }
618
619 SEG::ecoord closest_dist_sq = VECTOR2I::ECOORD_MAX;
620 SEG::ecoord clearance_sq = SEG::Square( aClearance );
621 VECTOR2I nearest;
622
623 // Collide line segments
624 for( size_t i = 0; i < GetSegmentCount(); i++ )
625 {
626 if( IsArcSegment( i ) )
627 continue;
628
629 const SEG& s = GetSegment( i );
630 SEG::ecoord dist_sq = s.SquaredDistance( aSeg );
631
632 if( dist_sq < closest_dist_sq )
633 {
634 if( aLocation )
635 nearest = s.NearestPoint( aSeg );
636
637 closest_dist_sq = dist_sq;
638
639 if( closest_dist_sq == 0 )
640 break;
641
642 // If we're not looking for aActual then any collision will do
643 if( closest_dist_sq < clearance_sq && !aActual )
644 break;
645 }
646 }
647
648 if( closest_dist_sq == 0 || closest_dist_sq < clearance_sq )
649 {
650 if( aLocation )
651 *aLocation = nearest;
652
653 if( aActual )
654 *aActual = sqrt( closest_dist_sq );
655
656 return true;
657 }
658
659 int dist = std::numeric_limits<int>::max();
660 SEG::ecoord closest_dist = sqrt( closest_dist_sq );
661
662 // Collide arc segments
663 for( size_t i = 0; i < ArcCount(); i++ )
664 {
665 const SHAPE_ARC& arc = Arc( i );
666 VECTOR2I pos;
667
668 // The arcs in the chain should have zero width
669 wxASSERT_MSG( arc.GetWidth() == 0, wxT( "Invalid arc width - should be zero" ) );
670
671 if( arc.Collide( aSeg, aClearance, aActual || aLocation ? &dist : nullptr,
672 aLocation ? &pos : nullptr ) )
673 {
674 if( !aActual )
675 return true;
676
677 if( dist < closest_dist )
678 {
679 closest_dist = dist;
680 nearest = pos;
681 }
682 }
683 }
684
685 if( closest_dist == 0 || closest_dist < aClearance )
686 {
687 if( aLocation )
688 *aLocation = nearest;
689
690 if( aActual )
691 *aActual = closest_dist;
692
693 return true;
694 }
695
696 return false;
697}
698
699
701{
702 SHAPE_LINE_CHAIN a( *this );
703
704 reverse( a.m_points.begin(), a.m_points.end() );
705 reverse( a.m_shapes.begin(), a.m_shapes.end() );
706 reverse( a.m_arcs.begin(), a.m_arcs.end() );
707
708 for( auto& sh : a.m_shapes )
709 {
710 if( sh != SHAPES_ARE_PT )
711 {
713 [&]( ssize_t& aShapeIndex )
714 {
715 if( aShapeIndex != SHAPE_IS_PT )
716 aShapeIndex = a.m_arcs.size() - aShapeIndex - 1;
717 } );
718
719 if( sh.second != SHAPE_IS_PT )
720 {
721 // If the second element is populated, the first one should be too!
722 assert( sh.first != SHAPE_IS_PT );
723
724 // Switch round first and second in shared points, as part of reversing the chain
725 std::swap( sh.first, sh.second );
726 }
727 }
728 }
729
730 for( SHAPE_ARC& arc : a.m_arcs )
731 arc.Reverse();
732
733 a.m_closed = m_closed;
734
735 return a;
736}
737
738
740{
741 for( ssize_t arcIndex = m_arcs.size() - 1; arcIndex >= 0; --arcIndex )
742 convertArc( arcIndex );
743}
744
745
746long long int SHAPE_LINE_CHAIN::Length() const
747{
748 long long int l = 0;
749
750 for( int i = 0; i < SegmentCount(); i++ )
751 {
752 // Only include segments that aren't part of arc shapes
753 if( !IsArcSegment(i) )
754 l += CSegment( i ).Length();
755 }
756
757 for( size_t i = 0; i < ArcCount(); i++ )
758 l += CArcs()[i].GetLength();
759
760 return l;
761}
762
763
764void SHAPE_LINE_CHAIN::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
765{
766 for( auto& pt : m_points )
767 {
768 if( aX )
769 pt.x = -pt.x + 2 * aRef.x;
770
771 if( aY )
772 pt.y = -pt.y + 2 * aRef.y;
773 }
774
775 for( auto& arc : m_arcs )
776 arc.Mirror( aX, aY, aRef );
777}
778
779
780void SHAPE_LINE_CHAIN::Mirror( const SEG& axis )
781{
782 for( auto& pt : m_points )
783 pt = axis.ReflectPoint( pt );
784
785 for( auto& arc : m_arcs )
786 arc.Mirror( axis );
787}
788
789
790void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP )
791{
792 Remove( aStartIndex, aEndIndex );
793 Insert( aStartIndex, aP );
794 assert( m_shapes.size() == m_points.size() );
795}
796
797
798void SHAPE_LINE_CHAIN::Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine )
799{
800 if( aEndIndex < 0 )
801 aEndIndex += PointCount();
802
803 if( aStartIndex < 0 )
804 aStartIndex += PointCount();
805
806 // We only process lines in order in this house
807 wxASSERT( aStartIndex <= aEndIndex );
808 wxASSERT( aEndIndex < static_cast<int>( m_points.size() ) );
809
810 SHAPE_LINE_CHAIN newLine = aLine;
811
812 // Zero points to add?
813 if( newLine.PointCount() == 0 )
814 {
815 Remove( aStartIndex, aEndIndex );
816 return;
817 }
818
819 // Remove coincident points in the new line
820 if( newLine.m_points.front() == m_points[aStartIndex] )
821 {
822 aStartIndex++;
823 newLine.Remove( 0 );
824
825 // Zero points to add?
826 if( newLine.PointCount() == 0 )
827 {
828 Remove( aStartIndex, aEndIndex );
829 return;
830 }
831 }
832
833 if( newLine.m_points.back() == m_points[aEndIndex] && aEndIndex > 0 )
834 {
835 aEndIndex--;
836 newLine.Remove( -1 );
837 }
838
839 Remove( aStartIndex, aEndIndex );
840
841 // Zero points to add?
842 if( newLine.PointCount() == 0 )
843 return;
844
845 // The total new arcs index is added to the new arc indices
846 size_t prev_arc_count = m_arcs.size();
847 std::vector<std::pair<ssize_t, ssize_t>> new_shapes = newLine.m_shapes;
848
849 for( std::pair<ssize_t, ssize_t>& shape_pair : new_shapes )
850 {
851 alg::run_on_pair( shape_pair,
852 [&]( ssize_t& aShape )
853 {
854 if( aShape != SHAPE_IS_PT )
855 aShape += prev_arc_count;
856 } );
857 }
858
859 m_shapes.insert( m_shapes.begin() + aStartIndex, new_shapes.begin(), new_shapes.end() );
860 m_points.insert( m_points.begin() + aStartIndex, newLine.m_points.begin(),
861 newLine.m_points.end() );
862 m_arcs.insert( m_arcs.end(), newLine.m_arcs.begin(), newLine.m_arcs.end() );
863
864 assert( m_shapes.size() == m_points.size() );
865}
866
867
868void SHAPE_LINE_CHAIN::Remove( int aStartIndex, int aEndIndex )
869{
870 wxCHECK( m_shapes.size() == m_points.size(), /*void*/ );
871
872 // Unwrap the chain first (correctly handling removing arc at
873 // end of chain coincident with start)
874 bool closedState = IsClosed();
875 SetClosed( false );
876
877 if( aEndIndex < 0 )
878 aEndIndex += PointCount();
879
880 if( aStartIndex < 0 )
881 aStartIndex += PointCount();
882
883 if( aStartIndex >= PointCount() || aEndIndex >= PointCount() || aStartIndex > aEndIndex)
884 {
885 SetClosed( closedState );
886 return;
887 }
888
889
890 // Split arcs, making arcs coincident
891 if( !IsArcStart( aStartIndex ) && IsPtOnArc( aStartIndex ) )
892 splitArc( aStartIndex, false );
893
894 if( IsSharedPt( aStartIndex ) ) // Don't delete the shared point
895 aStartIndex += 1;
896
897 if( !IsArcEnd( aEndIndex ) && IsPtOnArc( aEndIndex ) && aEndIndex < PointCount() - 1 )
898 splitArc( aEndIndex + 1, true );
899
900 if( IsSharedPt( aEndIndex ) ) // Don't delete the shared point
901 aEndIndex -= 1;
902
903 if( aStartIndex > aEndIndex )
904 {
905 SetClosed( closedState );
906 return;
907 }
908
909 std::set<size_t> extra_arcs;
910 auto logArcIdxRemoval = [&]( ssize_t& aShapeIndex )
911 {
912 if( aShapeIndex != SHAPE_IS_PT )
913 extra_arcs.insert( aShapeIndex );
914 };
915
916 // Remove any overlapping arcs in the point range
917 for( int i = aStartIndex; i <= aEndIndex; i++ )
918 {
919 if( IsSharedPt( i ) )
920 {
921 if( i == aStartIndex )
922 {
923 logArcIdxRemoval( m_shapes[i].second ); // Only remove the arc on the second index
924
925 // Ensure that m_shapes has been built correctly.
926 assert( i < aEndIndex || m_shapes[i + 1].first == m_shapes[i].second );
927
928 continue;
929 }
930 else if( i == aEndIndex )
931 {
932 logArcIdxRemoval( m_shapes[i].first ); // Only remove the arc on the first index
933
934 // Ensure that m_shapes has been built correctly.
935 assert( i > aStartIndex || ( IsSharedPt( i - 1 )
936 ? m_shapes[i - 1].second == m_shapes[i].first
937 : m_shapes[i - 1].first == m_shapes[i].first ) );
938 continue;
939 }
940 }
941 else
942 {
943 alg::run_on_pair( m_shapes[i], logArcIdxRemoval );
944 }
945 }
946
947 for( auto arc : extra_arcs )
948 convertArc( arc );
949
950 m_shapes.erase( m_shapes.begin() + aStartIndex, m_shapes.begin() + aEndIndex + 1 );
951 m_points.erase( m_points.begin() + aStartIndex, m_points.begin() + aEndIndex + 1 );
952 assert( m_shapes.size() == m_points.size() );
953
954 SetClosed( closedState );
955}
956
957
959{
961
962 if( IsClosed() && PointInside( aP ) && !aOutlineOnly )
963 return 0;
964
965 for( size_t s = 0; s < GetSegmentCount(); s++ )
966 d = std::min( d, GetSegment( s ).SquaredDistance( aP ) );
967
968 return d;
969}
970
971
972int SHAPE_LINE_CHAIN::Split( const VECTOR2I& aP, bool aExact )
973{
974 int ii = -1;
975 int min_dist = 2;
976
977 int found_index = Find( aP );
978
979 if( found_index >= 0 && aExact )
980 return found_index;
981
982 for( int s = 0; s < SegmentCount(); s++ )
983 {
984 const SEG seg = CSegment( s );
985 int dist = seg.Distance( aP );
986
987 // make sure we are not producing a 'slightly concave' primitive. This might happen
988 // if aP lies very close to one of already existing points.
989 if( dist < min_dist && seg.A != aP && seg.B != aP )
990 {
991 min_dist = dist;
992 if( found_index < 0 )
993 ii = s;
994 else if( s < found_index )
995 ii = s;
996 }
997 }
998
999 if( ii < 0 )
1000 ii = found_index;
1001
1002 if( ii >= 0 )
1003 {
1004 // Don't create duplicate points
1005 if( GetPoint( ii ) == aP )
1006 return ii;
1007
1008 size_t newIndex = static_cast<size_t>( ii ) + 1;
1009
1010 if( IsArcSegment( ii ) )
1011 {
1012 m_points.insert( m_points.begin() + newIndex, aP );
1013 m_shapes.insert( m_shapes.begin() + newIndex, { ArcIndex( ii ), SHAPE_IS_PT } );
1014 splitArc( newIndex, true ); // Make the inserted point a shared point
1015 }
1016 else
1017 {
1018 Insert( newIndex, aP );
1019 }
1020
1021 return newIndex;
1022 }
1023
1024 return -1;
1025}
1026
1027
1028int SHAPE_LINE_CHAIN::Find( const VECTOR2I& aP, int aThreshold ) const
1029{
1030 for( int s = 0; s < PointCount(); s++ )
1031 {
1032 if( aThreshold == 0 )
1033 {
1034 if( CPoint( s ) == aP )
1035 return s;
1036 }
1037 else
1038 {
1039 if( (CPoint( s ) - aP).EuclideanNorm() <= aThreshold )
1040 return s;
1041 }
1042 }
1043
1044 return -1;
1045}
1046
1047
1048int SHAPE_LINE_CHAIN::FindSegment( const VECTOR2I& aP, int aThreshold ) const
1049{
1050 for( int s = 0; s < SegmentCount(); s++ )
1051 {
1052 if( CSegment( s ).Distance( aP ) <= aThreshold )
1053 return s;
1054 }
1055
1056 return -1;
1057}
1058
1059
1061{
1062 wxCHECK2_MSG( m_points.size() == m_shapes.size(), return 0, "Invalid chain!" );
1063
1064 if( m_points.size() < 2 )
1065 return 0;
1066
1067 int numShapes = 1;
1068
1069 for( int i = NextShape( 0 ); i != -1; i = NextShape( i ) )
1070 numShapes++;
1071
1072 return numShapes;
1073}
1074
1075
1077{
1078 if( aIndex < 0 )
1079 aIndex += SegmentCount();
1080
1081 wxCHECK( aIndex < SegmentCount() && aIndex >= 0,
1082 m_points.size() > 0 ? SEG( m_points.back(), m_points.back() ) : SEG( 0, 0, 0, 0 ) );
1083
1084 if( aIndex == (int) ( m_points.size() - 1 ) && m_closed )
1085 return SEG( m_points[aIndex], m_points[0], aIndex );
1086 else
1087 return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
1088}
1089
1090
1091int SHAPE_LINE_CHAIN::NextShape( int aPointIndex ) const
1092{
1093 if( aPointIndex < 0 )
1094 aPointIndex += PointCount();
1095
1096 if( aPointIndex < 0 )
1097 return -1;
1098
1099 int lastIndex = PointCount() - 1;
1100
1101 // Last point?
1102 if( aPointIndex >= lastIndex )
1103 return -1; // we don't want to wrap around
1104
1105 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1106 {
1107 if( aPointIndex == lastIndex - 1 )
1108 {
1109 if( m_closed )
1110 return lastIndex;
1111 else
1112 return -1;
1113 }
1114 else
1115 {
1116 return aPointIndex + 1;
1117 }
1118 }
1119
1120 int arcStart = aPointIndex;
1121
1122 // The second element should only get populated when the point is shared between two shapes.
1123 // If not a shared point, then the index should always go on the first element.
1124 wxCHECK2_MSG( m_shapes[aPointIndex].first != SHAPE_IS_PT, return -1, "malformed chain!" );
1125
1126 ssize_t currentArcIdx = ArcIndex( aPointIndex );
1127
1128 // Now skip the rest of the arc
1129 while( aPointIndex < lastIndex && ArcIndex( aPointIndex ) == currentArcIdx )
1130 aPointIndex += 1;
1131
1132 bool indexStillOnArc = alg::pair_contains( m_shapes[aPointIndex], currentArcIdx );
1133
1134 // We want the last vertex of the arc if the initial point was the start of one
1135 // Well-formed arcs should generate more than one point to travel above
1136 if( aPointIndex - arcStart > 1 && !indexStillOnArc )
1137 aPointIndex -= 1;
1138
1139 if( aPointIndex == lastIndex )
1140 {
1141 if( !m_closed || IsArcSegment( aPointIndex ) )
1142 return -1; //no shape
1143 else
1144 return lastIndex; // Segment between last point and the start of the chain
1145 }
1146
1147 return aPointIndex;
1148}
1149
1150
1151void SHAPE_LINE_CHAIN::SetPoint( int aIndex, const VECTOR2I& aPos )
1152{
1153 if( aIndex < 0 )
1154 aIndex += PointCount();
1155 else if( aIndex >= PointCount() )
1156 aIndex -= PointCount();
1157
1158 m_points[aIndex] = aPos;
1159
1160 alg::run_on_pair( m_shapes[aIndex],
1161 [&]( ssize_t& aIdx )
1162 {
1163 if( aIdx != SHAPE_IS_PT )
1164 convertArc( aIdx );
1165 } );
1166}
1167
1168
1169void SHAPE_LINE_CHAIN::RemoveShape( int aPointIndex )
1170{
1171 if( aPointIndex < 0 )
1172 aPointIndex += PointCount();
1173
1174 if( aPointIndex >= PointCount() || aPointIndex < 0 )
1175 return; // Invalid index, fail gracefully
1176
1177 if( m_shapes[aPointIndex] == SHAPES_ARE_PT )
1178 {
1179 Remove( aPointIndex );
1180 return;
1181 }
1182
1183 int start = aPointIndex;
1184 int end = aPointIndex;
1185 int arcIdx = ArcIndex( aPointIndex );
1186
1187 if( !IsArcStart( start ) )
1188 {
1189 // aPointIndex is not a shared point, so iterate backwards to find the start of the arc
1190 while( start > 0 && ArcIndex( static_cast<ssize_t>( start ) - 1 ) == arcIdx )
1191 start--;
1192 }
1193
1194 if( !IsArcEnd( end ) || start == end )
1195 end = NextShape( end ); // can be -1 to indicate end of chain
1196
1197 Remove( start, end );
1198}
1199
1200
1201const SHAPE_LINE_CHAIN SHAPE_LINE_CHAIN::Slice( int aStartIndex, int aEndIndex ) const
1202{
1204
1205 if( aEndIndex < 0 )
1206 aEndIndex += PointCount();
1207
1208 if( aStartIndex < 0 )
1209 aStartIndex += PointCount();
1210
1211 // Bad programmer checks
1212 wxCHECK( aStartIndex >= 0, SHAPE_LINE_CHAIN() );
1213 wxCHECK( aEndIndex >= 0, SHAPE_LINE_CHAIN() );
1214 wxCHECK( aStartIndex < PointCount(), SHAPE_LINE_CHAIN() );
1215 wxCHECK( aEndIndex < PointCount(), SHAPE_LINE_CHAIN() );
1216 wxCHECK( aEndIndex >= aStartIndex, SHAPE_LINE_CHAIN() );
1217
1218 int numPoints = static_cast<int>( m_points.size() );
1219
1220 if( IsArcSegment( aStartIndex ) && !IsArcStart( aStartIndex ) )
1221 {
1222 // Cutting in middle of an arc, lets split it
1223 ssize_t arcToSplitIndex = ArcIndex( aStartIndex );
1224 const SHAPE_ARC& arcToSplit = Arc( arcToSplitIndex );
1225
1226 // Copy the points as arc points
1227 for( size_t i = aStartIndex; arcToSplitIndex == ArcIndex( i ); i++ )
1228 {
1229 rv.m_points.push_back( m_points[i] );
1230 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1231 rv.m_bbox.Merge( m_points[i] );
1232 }
1233
1234 // Create a new arc from the existing one, with different start point.
1235 SHAPE_ARC newArc;
1236
1237 VECTOR2I newArcStart = m_points[aStartIndex];
1238
1239 newArc.ConstructFromStartEndCenter( newArcStart, arcToSplit.GetP1(),
1240 arcToSplit.GetCenter(),
1241 arcToSplit.IsClockwise() );
1242
1243
1244 rv.m_arcs.push_back( newArc );
1245
1246 aStartIndex += rv.PointCount();
1247 }
1248
1249 for( int i = aStartIndex; i <= aEndIndex && i < numPoints; i = NextShape( i ) )
1250 {
1251 if( i == -1 )
1252 return rv; // NextShape reached the end
1253
1254 int nextShape = NextShape( i );
1255 bool isLastShape = nextShape < 0;
1256
1257 if( IsArcStart( i ) )
1258 {
1259 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1260 || ( nextShape > aEndIndex ) )
1261 {
1262 if( i == aEndIndex )
1263 {
1264 // Single point on an arc, just append the single point
1265 rv.Append( m_points[i] );
1266 return rv;
1267 }
1268
1269 // Cutting in middle of an arc, lets split it
1270 ssize_t arcIndex = ArcIndex( i );
1271 const SHAPE_ARC& currentArc = Arc( arcIndex );
1272
1273 // Copy the points as arc points
1274 for( ; i <= aEndIndex && i < numPoints; i++ )
1275 {
1276 if( arcIndex != ArcIndex( i ) )
1277 break;
1278
1279 rv.m_points.push_back( m_points[i] );
1280 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1281 rv.m_bbox.Merge( m_points[i] );
1282 }
1283
1284 // Create a new arc from the existing one, with different end point.
1285 SHAPE_ARC newArc;
1286
1287 VECTOR2I newArcEnd = m_points[aEndIndex];
1288
1289 newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
1290 currentArc.GetCenter(),
1291 currentArc.IsClockwise() );
1292
1293
1294 rv.m_arcs.push_back( newArc );
1295
1296 return rv;
1297 }
1298 else
1299 {
1300 // append the whole arc
1301 const SHAPE_ARC& currentArc = Arc( ArcIndex( i ) );
1302 rv.Append( currentArc );
1303 }
1304
1305 if( isLastShape )
1306 return rv;
1307 }
1308 else
1309 {
1310 wxASSERT_MSG( !IsArcSegment( i ),
1311 wxT( "Still on an arc segment, we missed something..." ) );
1312
1313 if( i == aStartIndex )
1314 rv.Append( m_points[i] );
1315
1316 bool nextPointIsArc = isLastShape ? false : IsArcSegment( nextShape );
1317
1318 if( !nextPointIsArc && i < SegmentCount() && i < aEndIndex )
1319 rv.Append( GetSegment( i ).B );
1320 }
1321
1322 }
1323
1324 return rv;
1325}
1326
1327
1329{
1330 assert( m_shapes.size() == m_points.size() );
1331
1332 if( aOtherLine.PointCount() == 0 )
1333 {
1334 return;
1335 }
1336
1337 size_t num_arcs = m_arcs.size();
1338 m_arcs.insert( m_arcs.end(), aOtherLine.m_arcs.begin(), aOtherLine.m_arcs.end() );
1339
1340 auto fixShapeIndices =
1341 [&]( const std::pair<ssize_t, ssize_t>& aShapeIndices ) -> std::pair<ssize_t, ssize_t>
1342 {
1343 std::pair<ssize_t, ssize_t> retval = aShapeIndices;
1344
1345 alg::run_on_pair( retval, [&]( ssize_t& aIndex )
1346 {
1347 if( aIndex != SHAPE_IS_PT )
1348 aIndex = aIndex + num_arcs;
1349 } );
1350
1351 return retval;
1352 };
1353
1354 if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
1355 {
1356 const VECTOR2I p = aOtherLine.CPoint( 0 );
1357 m_points.push_back( p );
1358 m_shapes.push_back( fixShapeIndices( aOtherLine.CShapes()[0] ) );
1359 m_bbox.Merge( p );
1360 }
1361 else if( aOtherLine.IsArcSegment( 0 ) )
1362 {
1363 // Associate the new arc shape with the last point of this chain
1364 if( m_shapes.back() == SHAPES_ARE_PT )
1365 m_shapes.back().first = aOtherLine.CShapes()[0].first + num_arcs;
1366 else
1367 m_shapes.back().second = aOtherLine.CShapes()[0].first + num_arcs;
1368 }
1369
1370
1371 for( int i = 1; i < aOtherLine.PointCount(); i++ )
1372 {
1373 const VECTOR2I p = aOtherLine.CPoint( i );
1374 m_points.push_back( p );
1375
1376 ssize_t arcIndex = aOtherLine.ArcIndex( i );
1377
1378 if( arcIndex != ssize_t( SHAPE_IS_PT ) )
1379 {
1380 m_shapes.push_back( fixShapeIndices( aOtherLine.m_shapes[i] ) );
1381 }
1382 else
1383 m_shapes.push_back( SHAPES_ARE_PT );
1384
1385 m_bbox.Merge( p );
1386 }
1387
1389
1390 assert( m_shapes.size() == m_points.size() );
1391}
1392
1393
1395{
1397}
1398
1399
1400void SHAPE_LINE_CHAIN::Append( const SHAPE_ARC& aArc, double aAccuracy )
1401{
1402 SHAPE_LINE_CHAIN chain = aArc.ConvertToPolyline( aAccuracy );
1403
1404 if( chain.PointCount() > 2 )
1405 {
1406 chain.m_arcs.push_back( aArc );
1407 chain.m_arcs.back().SetWidth( 0 );
1408
1409 for( auto& sh : chain.m_shapes )
1410 sh.first = 0;
1411 }
1412
1413 Append( chain );
1414
1415 assert( m_shapes.size() == m_points.size() );
1416}
1417
1418
1419void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const VECTOR2I& aP )
1420{
1421 if( aVertex == m_points.size() )
1422 {
1423 Append( aP );
1424 return;
1425 }
1426
1427 wxCHECK( aVertex < m_points.size(), /* void */ );
1428
1429 if( aVertex > 0 && IsPtOnArc( aVertex ) )
1430 splitArc( aVertex );
1431
1432 //@todo need to check we aren't creating duplicate points
1433 m_points.insert( m_points.begin() + aVertex, aP );
1434 m_shapes.insert( m_shapes.begin() + aVertex, SHAPES_ARE_PT );
1435
1436 assert( m_shapes.size() == m_points.size() );
1437}
1438
1439
1440void SHAPE_LINE_CHAIN::Insert( size_t aVertex, const SHAPE_ARC& aArc )
1441{
1442 wxCHECK( aVertex < m_points.size(), /* void */ );
1443
1444 if( aVertex > 0 && IsPtOnArc( aVertex ) )
1445 splitArc( aVertex );
1446
1448 ssize_t arc_pos = m_arcs.size();
1449
1450 for( auto arc_it = m_shapes.rbegin() ;
1451 arc_it != m_shapes.rend() + aVertex;
1452 arc_it++ )
1453 {
1454 if( *arc_it != SHAPES_ARE_PT )
1455 {
1456 arc_pos = std::max( ( *arc_it ).first, ( *arc_it ).second );
1457 arc_pos++;
1458 }
1459 }
1460
1461 //Increment all arc indices before inserting the new arc
1462 for( auto& sh : m_shapes )
1463 {
1464 alg::run_on_pair( sh,
1465 [&]( ssize_t& aIndex )
1466 {
1467 if( aIndex >= arc_pos )
1468 aIndex++;
1469 } );
1470 }
1471
1472 SHAPE_ARC arcCopy( aArc );
1473 arcCopy.SetWidth( 0 );
1474 m_arcs.insert( m_arcs.begin() + arc_pos, arcCopy );
1475
1477 //@todo need to check we aren't creating duplicate points at start or end
1478 auto& chain = aArc.ConvertToPolyline();
1479 m_points.insert( m_points.begin() + aVertex, chain.CPoints().begin(), chain.CPoints().end() );
1480
1482 //@todo need to check we aren't creating duplicate points at start or end
1483 std::vector<std::pair<ssize_t, ssize_t>> new_points( chain.PointCount(),
1484 { arc_pos, SHAPE_IS_PT } );
1485
1486 m_shapes.insert( m_shapes.begin() + aVertex, new_points.begin(), new_points.end() );
1487 assert( m_shapes.size() == m_points.size() );
1488}
1489
1490
1492{
1494 m_origin( aOrigin ) {};
1495
1497 const SHAPE_LINE_CHAIN::INTERSECTION& aB ) const
1498 {
1499 return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
1500 }
1501
1503};
1504
1505
1506int SHAPE_LINE_CHAIN::Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const
1507{
1508 for( int s = 0; s < SegmentCount(); s++ )
1509 {
1510 OPT_VECTOR2I p = CSegment( s ).Intersect( aSeg );
1511
1512 if( p )
1513 {
1514 INTERSECTION is;
1515 is.valid = true;
1516 is.index_our = s;
1517 is.index_their = -1;
1518 is.is_corner_our = is.is_corner_their = false;
1519 is.p = *p;
1520 aIp.push_back( is );
1521 }
1522 }
1523
1524 compareOriginDistance comp( aSeg.A );
1525 sort( aIp.begin(), aIp.end(), comp );
1526
1527 return aIp.size();
1528}
1529
1530
1531static inline void addIntersection( SHAPE_LINE_CHAIN::INTERSECTIONS& aIps, int aPc,
1533{
1534 if( aIps.size() == 0 )
1535 {
1536 aIps.push_back( aP );
1537 return;
1538 }
1539
1540 aIps.push_back( aP );
1541}
1542
1543
1545 bool aExcludeColinearAndTouching, BOX2I* aChainBBox ) const
1546{
1547 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.BBox();
1548
1549 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1550 {
1551 const SEG& a = CSegment( s1 );
1552 const BOX2I bb_cur( a.A, a.B - a.A );
1553
1554 if( !bb_other.Intersects( bb_cur ) )
1555 continue;
1556
1557 for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1558 {
1559 const SEG& b = aChain.CSegment( s2 );
1560 INTERSECTION is;
1561
1562 is.index_our = s1;
1563 is.index_their = s2;
1564 is.is_corner_our = false;
1565 is.is_corner_their = false;
1566 is.valid = true;
1567
1568 OPT_VECTOR2I p = a.Intersect( b );
1569
1570 bool coll = a.Collinear( b );
1571
1572 if( coll && ! aExcludeColinearAndTouching )
1573 {
1574 if( a.Contains( b.A ) )
1575 {
1576 is.p = b.A;
1577 is.is_corner_their = true;
1578 addIntersection(aIp, PointCount(), is);
1579 }
1580
1581 if( a.Contains( b.B ) )
1582 {
1583 is.p = b.B;
1584 is.index_their++;
1585 is.is_corner_their = true;
1586 addIntersection( aIp, PointCount(), is );
1587 }
1588
1589 if( b.Contains( a.A ) )
1590 {
1591 is.p = a.A;
1592 is.is_corner_our = true;
1593 addIntersection( aIp, PointCount(), is );
1594 }
1595
1596 if( b.Contains( a.B ) )
1597 {
1598 is.p = a.B;
1599 is.index_our++;
1600 is.is_corner_our = true;
1601 addIntersection( aIp, PointCount(), is );
1602 }
1603 }
1604 else if( p )
1605 {
1606 is.p = *p;
1607 is.is_corner_our = false;
1608 is.is_corner_their = false;
1609
1610 if( p == a.A )
1611 {
1612 is.is_corner_our = true;
1613 }
1614
1615 if( p == a.B )
1616 {
1617 is.is_corner_our = true;
1618 is.index_our++;
1619 }
1620
1621 if( p == b.A )
1622 {
1623 is.is_corner_their = true;
1624 }
1625
1626 if( p == b.B )
1627 {
1628 is.is_corner_their = true;
1629 is.index_their++;
1630 }
1631
1632 addIntersection( aIp, PointCount(), is );
1633 }
1634 }
1635 }
1636
1637 return aIp.size();
1638}
1639
1640
1641int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP, int aIndex ) const
1642{
1643 int sum = 0;
1644
1645 for( int i = 0; i < SegmentCount(); i++ )
1646 {
1647 const SEG seg = CSegment( i );
1648 bool indexMatch = true;
1649
1650 if( aIndex >= 0 )
1651 {
1652 if( aIndex == SegmentCount() )
1653 {
1654 indexMatch = ( i == SegmentCount() - 1 );
1655 }
1656 else
1657 {
1658 indexMatch = ( i == aIndex );
1659 }
1660 }
1661
1662 if( indexMatch )
1663 {
1664 sum += ( aP - seg.A ).EuclideanNorm();
1665 return sum;
1666 }
1667 else
1668 sum += seg.Length();
1669 }
1670
1671 return -1;
1672}
1673
1674
1675bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
1676 bool aUseBBoxCache ) const
1677{
1678 /*
1679 * Don't check the bounding box unless it's cached. Building it is about the same speed as
1680 * the rigorous test below and so just slows things down by doing potentially two tests.
1681 */
1682 if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1683 return false;
1684
1685 if( !IsClosed() || GetPointCount() < 3 )
1686 return false;
1687
1688 bool inside = false;
1689
1690 /*
1691 * To check for interior points, we draw a line in the positive x direction from
1692 * the point. If it intersects an even number of segments, the point is outside the
1693 * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1694 *
1695 * Note: slope might be denormal here in the case of a horizontal line but we require our
1696 * y to move from above to below the point (or vice versa)
1697 *
1698 * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1699 * vector number-of-points times. This has a non-trivial impact on zone fill times.
1700 */
1701 int pointCount = GetPointCount();
1702
1703 for( int i = 0; i < pointCount; )
1704 {
1705 const auto p1 = GetPoint( i++ );
1706 const auto p2 = GetPoint( i == pointCount ? 0 : i );
1707 const auto diff = p2 - p1;
1708
1709 if( diff.y != 0 )
1710 {
1711 const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1712
1713 if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1714 inside = !inside;
1715 }
1716 }
1717
1718 // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1719 // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1720 if( aAccuracy <= 1 )
1721 return inside;
1722 else
1723 return inside || PointOnEdge( aPt, aAccuracy );
1724}
1725
1726
1727bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
1728{
1729 return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1730}
1731
1732
1733int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
1734{
1735 if( !GetPointCount() )
1736 {
1737 return -1;
1738 }
1739 else if( GetPointCount() == 1 )
1740 {
1741 VECTOR2I dist = GetPoint(0) - aPt;
1742 return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1743 }
1744
1745 for( size_t i = 0; i < GetSegmentCount(); i++ )
1746 {
1747 const SEG s = GetSegment( i );
1748
1749 if( s.A == aPt || s.B == aPt )
1750 return i;
1751
1752 if( s.Distance( aPt ) <= aAccuracy + 1 )
1753 return i;
1754 }
1755
1756 return -1;
1757}
1758
1759
1760bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
1761{
1762 if( !PointCount() )
1763 return false;
1764 else if( PointCount() == 1 )
1765 return m_points[0] == aP;
1766
1767 for( int i = 0; i < SegmentCount(); i++ )
1768 {
1769 const SEG s = CSegment( i );
1770
1771 if( s.A == aP || s.B == aP )
1772 return true;
1773
1774 if( s.Distance( aP ) <= aDist )
1775 return true;
1776 }
1777
1778 return false;
1779}
1780
1781
1782const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
1783{
1784 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1785 {
1786 for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1787 {
1788 const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1789
1790 if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1791 {
1792 INTERSECTION is;
1793 is.index_our = s1;
1794 is.index_their = s2;
1795 is.p = s2a;
1796 return is;
1797 }
1798 else if( CSegment( s1 ).Contains( s2b ) &&
1799 // for closed polylines, the ending point of the
1800 // last segment == starting point of the first segment
1801 // this is a normal case, not self intersecting case
1802 !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1803 {
1804 INTERSECTION is;
1805 is.index_our = s1;
1806 is.index_their = s2;
1807 is.p = s2b;
1808 return is;
1809 }
1810 else
1811 {
1812 OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1813
1814 if( p )
1815 {
1816 INTERSECTION is;
1817 is.index_our = s1;
1818 is.index_their = s2;
1819 is.p = *p;
1820 return is;
1821 }
1822 }
1823 }
1824 }
1825
1826 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
1827}
1828
1829
1831{
1832 BOX2I_MINMAX() : m_Left( 0 ), m_Top( 0 ), m_Right( 0 ), m_Bottom( 0 ) {}
1833
1834 BOX2I_MINMAX( int aLeft, int aTop, int aRight, int aBottom ) :
1835 m_Left( aLeft ), m_Top( aTop ), m_Right( aRight ), m_Bottom( aBottom )
1836 {
1837 }
1838
1839 BOX2I_MINMAX( const BOX2I& aBox ) :
1840 m_Left( aBox.GetLeft() ), m_Top( aBox.GetTop() ), m_Right( aBox.GetRight() ),
1841 m_Bottom( aBox.GetBottom() )
1842 {
1843 }
1844
1845 BOX2I_MINMAX( const SHAPE_ARC& aArc ) : BOX2I_MINMAX( aArc.BBox() ) {}
1846
1847 BOX2I_MINMAX( const SEG& aSeg )
1848 {
1849 m_Left = std::min( aSeg.A.x, aSeg.B.x );
1850 m_Right = std::max( aSeg.A.x, aSeg.B.x );
1851 m_Top = std::min( aSeg.A.y, aSeg.B.y );
1852 m_Bottom = std::max( aSeg.A.y, aSeg.B.y );
1853 }
1854
1855 inline bool Intersects( const BOX2I_MINMAX& aOther ) const
1856 {
1857 // calculate the left common area coordinate:
1858 int left = std::max( m_Left, aOther.m_Left );
1859 // calculate the right common area coordinate:
1860 int right = std::min( m_Right, aOther.m_Right );
1861 // calculate the upper common area coordinate:
1862 int top = std::max( m_Top, aOther.m_Top );
1863 // calculate the lower common area coordinate:
1864 int bottom = std::min( m_Bottom, aOther.m_Bottom );
1865
1866 // if a common area exists, it must have a positive (null accepted) size
1867 return left <= right && top <= bottom;
1868 }
1869
1874};
1875
1876
1878{
1879 SHAPE_KEY( int aFirstIdx, int aArcIdx, const BOX2I_MINMAX& aBBox ) :
1880 m_FirstIdx( aFirstIdx ), m_ArcIdx( aArcIdx ), m_BBox( aBBox )
1881 {
1882 }
1883
1887};
1888
1889
1890const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
1892{
1893 auto pointsClose = []( const VECTOR2I& aPt1, const VECTOR2I& aPt2 ) -> bool
1894 {
1895 return ( VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
1896 };
1897
1898 auto collideArcSeg = [&pointsClose]( const SHAPE_ARC& aArc, const SEG& aSeg, int aClearance = 0,
1899 VECTOR2I* aLocation = nullptr )
1900 {
1901 VECTOR2I center = aArc.GetCenter();
1902 CIRCLE circle( center, aArc.GetRadius() );
1903
1904 std::vector<VECTOR2I> candidatePts = circle.Intersect( aSeg );
1905
1906 for( const VECTOR2I& candidate : candidatePts )
1907 {
1908 // Skip shared points
1909 if( aArc.GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
1910 continue;
1911
1912 if( aSeg.B == aArc.GetP0() && pointsClose( candidate, aSeg.B ) )
1913 continue;
1914
1915 bool collides = aArc.Collide( candidate, aClearance, nullptr, aLocation );
1916
1917 if( collides )
1918 return true;
1919 }
1920
1921 return false;
1922 };
1923
1924 auto collideArcArc = [&pointsClose]( const SHAPE_ARC& aArc1, const SHAPE_ARC& aArc2,
1925 VECTOR2I* aLocation = nullptr )
1926 {
1927 std::vector<VECTOR2I> candidatePts;
1928
1929 aArc1.Intersect( aArc2, &candidatePts );
1930
1931 for( const VECTOR2I& candidate : candidatePts )
1932 {
1933 // Skip shared points
1934 if( aArc1.GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.GetP1() ) )
1935 continue;
1936
1937 if( aArc2.GetP1() == aArc1.GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
1938 continue;
1939
1940 if( aLocation )
1941 *aLocation = candidate;
1942
1943 return true;
1944 }
1945
1946 return false;
1947 };
1948
1949 auto collideSegSeg = [this]( int s1, int s2, INTERSECTION& is )
1950 {
1951 SEG seg1 = CSegment( s1 );
1952 SEG seg2 = CSegment( s2 );
1953
1954 const VECTOR2I s2a = seg2.A, s2b = seg2.B;
1955
1956 if( s1 + 1 != s2 && seg1.Contains( s2a ) )
1957 {
1958 is.index_our = s1;
1959 is.index_their = s2;
1960 is.p = s2a;
1961 return true;
1962 }
1963 else if( seg1.Contains( s2b ) &&
1964 // for closed polylines, the ending point of the
1965 // last segment == starting point of the first segment
1966 // this is a normal case, not self intersecting case
1967 !( IsClosed() && s1 == 0 && s2 == SegmentCount() - 1 ) )
1968 {
1969 is.index_our = s1;
1970 is.index_their = s2;
1971 is.p = s2b;
1972 return true;
1973 }
1974 else
1975 {
1976 OPT_VECTOR2I p = seg1.Intersect( seg2, true );
1977
1978 if( p )
1979 {
1980 is.index_our = s1;
1981 is.index_their = s2;
1982 is.p = *p;
1983 return true;
1984 }
1985 }
1986
1987 return false;
1988 };
1989
1990 INTERSECTION is;
1991
1992 std::vector<SHAPE_KEY> shapeCache;
1993 for( int si = 0; si != -1; si = NextShape( si ) )
1994 {
1995 int arci = ArcIndex( si );
1996
1997 shapeCache.emplace_back( si, arci,
1998 arci == -1 ? BOX2I_MINMAX( CSegment( si ) )
1999 : BOX2I_MINMAX( Arc( arci ) ) );
2000 }
2001
2002 for( size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2003 {
2004 for( size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2005 {
2006 VECTOR2I loc;
2007 const SHAPE_KEY& k1 = shapeCache[sk1];
2008 const SHAPE_KEY& k2 = shapeCache[sk2];
2009
2010 if( !k1.m_BBox.Intersects( k2.m_BBox ) )
2011 continue;
2012
2013 if( k1.m_ArcIdx == -1 && k2.m_ArcIdx == -1 )
2014 {
2015 if( collideSegSeg( k1.m_FirstIdx, k2.m_FirstIdx, is ) )
2016 {
2017 return is;
2018 }
2019 }
2020 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx == -1 )
2021 {
2022 if( collideArcSeg( Arc( k1.m_ArcIdx ), CSegment( k2.m_FirstIdx ), 0, &loc ) )
2023 {
2024 is.index_our = k1.m_FirstIdx;
2025 is.index_their = k2.m_FirstIdx;
2026 is.p = loc;
2027 return is;
2028 }
2029 }
2030 else if( k1.m_ArcIdx == -1 && k2.m_ArcIdx != -1 )
2031 {
2032 if( collideArcSeg( Arc( k2.m_ArcIdx ), CSegment( k1.m_FirstIdx ), 0, &loc ) )
2033 {
2034 is.index_our = k1.m_FirstIdx;
2035 is.index_their = k2.m_FirstIdx;
2036 is.p = loc;
2037 return is;
2038 }
2039 }
2040 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx != -1 )
2041 {
2042 if( collideArcArc( Arc( k1.m_ArcIdx ), Arc( k2.m_ArcIdx ), &loc ) )
2043 {
2044 is.index_our = k1.m_FirstIdx;
2045 is.index_their = k2.m_FirstIdx;
2046 is.p = loc;
2047 return is;
2048 }
2049 }
2050 }
2051 }
2052
2053 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2054}
2055
2056
2058 bool aAllowInternalShapePoints ) const
2059{
2060 if( PointCount() == 0 )
2061 {
2062 // The only right answer here is "don't crash".
2063 return { 0, 0 };
2064 }
2065
2066 int min_d = std::numeric_limits<int>::max();
2067 int nearest = 0;
2068
2069 for( int i = 0; i < SegmentCount(); i++ )
2070 {
2071 int d = CSegment( i ).Distance( aP );
2072
2073 if( d < min_d )
2074 {
2075 min_d = d;
2076 nearest = i;
2077 }
2078 }
2079
2080 if( !aAllowInternalShapePoints )
2081 {
2082 //Snap to arc end points if the closest found segment is part of an arc segment
2083 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
2084 {
2085 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
2086 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
2087
2088 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
2089 nearest++;
2090
2091 // Is this the start or end of an arc? If so, return it directly
2092 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
2093 {
2094 return m_points[nearest];
2095 }
2096 else
2097 {
2098 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
2099 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
2100 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
2101
2102 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
2103 return nearestArc.GetP1();
2104 else
2105 return nearestArc.GetP0();
2106 }
2107
2108 }
2109 }
2110
2111 return CSegment( nearest ).NearestPoint( aP );
2112}
2113
2114
2115const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
2116{
2117 if( PointCount() == 0 )
2118 {
2119 // The only right answer here is "don't crash".
2120 return { 0, 0 };
2121 }
2122
2123 int nearest = 0;
2124
2125 dist = std::numeric_limits<int>::max();
2126
2127 for( int i = 0; i < PointCount(); i++ )
2128 {
2129 int d = aSeg.LineDistance( CPoint( i ) );
2130
2131 if( d < dist )
2132 {
2133 dist = d;
2134 nearest = i;
2135 }
2136 }
2137
2138 return CPoint( nearest );
2139}
2140
2141
2143{
2144 int min_d = std::numeric_limits<int>::max();
2145 int nearest = 0;
2146
2147 for( int i = 0; i < SegmentCount(); i++ )
2148 {
2149 int d = CSegment( i ).Distance( aP );
2150
2151 if( d < min_d )
2152 {
2153 min_d = d;
2154 nearest = i;
2155 }
2156 }
2157
2158 return nearest;
2159}
2160
2161
2162const std::string SHAPE_LINE_CHAIN::Format( bool aCplusPlus ) const
2163{
2164 std::stringstream ss;
2165
2166 ss << "SHAPE_LINE_CHAIN( { ";
2167
2168 for( int i = 0; i < PointCount(); i++ )
2169 {
2170 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
2171
2172 if( i != PointCount() -1 )
2173 ss << ", ";
2174 }
2175
2176 ss << "}, " << ( m_closed ? "true" : "false" );
2177 ss << " );";
2178
2179 return ss.str();
2180
2181 /* fixme: arcs
2182 for( size_t i = 0; i < m_arcs.size(); i++ )
2183 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
2184 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
2185 << m_arcs[i].GetCentralAngle().AsDegrees();
2186
2187 return ss.str();*/
2188}
2189
2190
2192{
2193 SHAPE_LINE_CHAIN a(*this), b( aOther );
2194 a.Simplify();
2195 b.Simplify();
2196
2197 if( a.m_points.size() != b.m_points.size() )
2198 return false;
2199
2200 for( int i = 0; i < a.PointCount(); i++ )
2201 {
2202 if( a.CPoint( i ) != b.CPoint( i ) )
2203 return false;
2204 }
2205
2206 return true;
2207}
2208
2209
2211{
2213 return Intersect( aChain, dummy ) != 0;
2214}
2215
2216
2218{
2219 return new SHAPE_LINE_CHAIN( *this );
2220}
2221
2222
2223bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
2224{
2225 size_t n_pts;
2226 size_t n_arcs;
2227
2228 m_points.clear();
2229 aStream >> n_pts;
2230
2231 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
2232 if( n_pts > aStream.str().size() )
2233 return false;
2234
2235 aStream >> m_closed;
2236 aStream >> n_arcs;
2237
2238 if( n_arcs > aStream.str().size() )
2239 return false;
2240
2241 for( size_t i = 0; i < n_pts; i++ )
2242 {
2243 int x, y;
2244 ssize_t ind;
2245 aStream >> x;
2246 aStream >> y;
2247 m_points.emplace_back( x, y );
2248
2249 aStream >> ind;
2250 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
2251 }
2252
2253 for( size_t i = 0; i < n_arcs; i++ )
2254 {
2255 VECTOR2I p0, pc;
2256 double angle;
2257
2258 aStream >> pc.x;
2259 aStream >> pc.y;
2260 aStream >> p0.x;
2261 aStream >> p0.y;
2262 aStream >> angle;
2263
2264 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
2265 }
2266
2267 return true;
2268}
2269
2270
2271const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
2272{
2273 int total = 0;
2274
2275 if( aPathLength == 0 )
2276 return CPoint( 0 );
2277
2278 for( int i = 0; i < SegmentCount(); i++ )
2279 {
2280 const SEG& s = CSegment( i );
2281 int l = s.Length();
2282
2283 if( total + l >= aPathLength )
2284 {
2285 VECTOR2I d( s.B - s.A );
2286 return s.A + d.Resize( aPathLength - total );
2287 }
2288
2289 total += l;
2290 }
2291
2292 return CPoint( -1 );
2293}
2294
2295
2296double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
2297{
2298 // see https://www.mathopenref.com/coordpolygonarea2.html
2299
2300 if( !m_closed )
2301 return 0.0;
2302
2303 double area = 0.0;
2304 int size = m_points.size();
2305
2306 for( int i = 0, j = size - 1; i < size; ++i )
2307 {
2308 area += ( (double) m_points[j].x + m_points[i].x ) *
2309 ( (double) m_points[j].y - m_points[i].y );
2310 j = i;
2311 }
2312
2313 if( aAbsolute )
2314 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2315 else
2316 return -area * 0.5; // The result would be negative if points are anti-clockwise
2317}
2318
2319
2321{
2322 std::vector<VECTOR2I> pts_unique;
2323 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2324
2325 // Always try to keep at least 2 points otherwise, we're not really a line
2326 if( PointCount() < 3 )
2327 {
2328 return;
2329 }
2330 else if( PointCount() == 3 )
2331 {
2332 if( m_points[0] == m_points[1] )
2333 Remove( 1 );
2334
2335 return;
2336 }
2337
2338 int i = 0;
2339
2340 while( i < PointCount() )
2341 {
2342 int j = i + 1;
2343
2344 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
2345 // one of them is part of a shape and one is not.
2346 while( j < PointCount() && m_points[i] == m_points[j] &&
2347 ( m_shapes[i] == m_shapes[j] ||
2348 m_shapes[i] == SHAPES_ARE_PT ||
2349 m_shapes[j] == SHAPES_ARE_PT ) )
2350 {
2351 j++;
2352 }
2353
2354 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
2355
2356 if( shapeToKeep == SHAPES_ARE_PT )
2357 shapeToKeep = m_shapes[j - 1];
2358
2359 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
2360 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
2361
2362 pts_unique.push_back( CPoint( i ) );
2363 shapes_unique.push_back( shapeToKeep );
2364
2365 i = j;
2366 }
2367
2368 m_points.clear();
2369 m_shapes.clear();
2370
2371 for( size_t ii = 0; ii < pts_unique.size(); ++ii )
2372 {
2373 const VECTOR2I p0 = pts_unique[ii];
2374
2375 m_points.push_back( p0 );
2376 m_shapes.push_back( shapes_unique[ii] );
2377 }
2378}
2379
2380
2381
2382void SHAPE_LINE_CHAIN::Simplify( int aMaxError )
2383{
2384 if( PointCount() < 3 )
2385 return;
2386
2387 std::vector<VECTOR2I> new_points;
2388 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2389
2390 new_points.reserve( m_points.size() );
2391 new_shapes.reserve( m_shapes.size() );
2392
2393 auto is_skip = [this]( size_t i, size_t j, size_t k )
2394 {
2395 return ( ( m_points[i].x == m_points[j].x // First two points on same vertical line
2396 && m_points[i].y != m_points[j].y // and not on same horizontal line
2397 && m_points[i].x != m_points[k].x ) // and not on same vertical line as third point
2398 || ( m_points[i].y == m_points[j].y
2399 && m_points[i].x != m_points[j].x
2400 && m_points[i].y != m_points[k].y ) );
2401 };
2402
2403 for( size_t ii = 0; ii < m_points.size(); )
2404 {
2405 new_points.push_back( m_points[ii] );
2406 new_shapes.push_back( m_shapes[ii] );
2407 size_t jj = ( ii + 1 ) % m_points.size();
2408 size_t kk = ( ii + 2 ) % m_points.size();
2409
2410 if( m_shapes[ii].first != SHAPE_IS_PT || m_shapes[jj].first != SHAPE_IS_PT
2411 || m_shapes[kk].first != SHAPE_IS_PT
2412 || is_skip( ii, jj, kk ) )
2413 {
2414 ++ii;
2415 continue;
2416 }
2417
2418 while( ii != kk && jj > ii && !( kk < ii && !m_closed ) )
2419 {
2420 bool too_far = false;
2421
2422 for( size_t ll = ( ii + 1 ) % m_points.size(); ll != kk;
2423 ll = ( ll + 1 ) % m_points.size() )
2424 {
2425 if( !TestSegmentHitFast( m_points[ll], m_points[ii], m_points[kk], aMaxError ) )
2426 {
2427 too_far = true;
2428 break;
2429 }
2430 }
2431
2432 if( too_far || is_skip( ii, jj, kk ) )
2433 break;
2434
2435 jj = ( jj + 1 ) % m_points.size();
2436 kk = ( kk + 1 ) % m_points.size();
2437 }
2438
2439 if( ii == kk || jj <= ii )
2440 break;
2441
2442 ii = jj;
2443 }
2444
2445 // If we have only one point, we need to add a second point to make a line
2446 if( new_points.size() == 1 )
2447 {
2448 new_points.push_back( m_points.back() );
2449 new_shapes.push_back( m_shapes.back() );
2450 }
2451
2452 m_points.clear();
2453 m_shapes.clear();
2454 m_points = new_points;
2455 m_shapes = new_shapes;
2456}
2457
2458
2459void SHAPE_LINE_CHAIN::Split( const VECTOR2I& aStart, const VECTOR2I& aEnd, SHAPE_LINE_CHAIN& aPre,
2460 SHAPE_LINE_CHAIN& aMid, SHAPE_LINE_CHAIN& aPost ) const
2461{
2462 VECTOR2I cp( aEnd );
2463
2464 VECTOR2I n = NearestPoint( cp, false );
2465 VECTOR2I m = NearestPoint( aStart, false );
2466
2467 SHAPE_LINE_CHAIN l( *this );
2468 l.Split( n, true );
2469 l.Split( m, true );
2470
2471 int i_start = l.Find( m );
2472 int i_end = l.Find( n );
2473
2474 if( i_start > i_end )
2475 {
2476 l = l.Reverse();
2477 i_start = l.Find( m );
2478 i_end = l.Find( n );
2479 }
2480
2481 aPre = l.Slice( 0, i_start );
2482 aPost = l.Slice( i_end, -1 );
2483 aMid = l.Slice( i_start, i_end );
2484}
2485
2486
2487bool SHAPE_LINE_CHAIN::OffsetLine( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
2488 SHAPE_LINE_CHAIN& aLeft, SHAPE_LINE_CHAIN& aRight,
2489 bool aSimplify ) const
2490{
2491 if( PointCount() < 2 )
2492 return false;
2493
2494 SHAPE_POLY_SET poly;
2495 poly.OffsetLineChain( *this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2496
2497 if( poly.OutlineCount() != 1 )
2498 return false;
2499
2500 if( poly.COutline( 0 ).PointCount() < 3 )
2501 return false;
2502
2503 if( poly.HasHoles() )
2504 return false;
2505
2506 SHAPE_LINE_CHAIN outline = poly.COutline( 0 );
2507
2508 wxASSERT( outline.IsClosed() );
2509
2510 const VECTOR2I& start = CPoint( 0 );
2511 const VECTOR2I& end = CPoint( -1 );
2512
2513 outline.Split( start, true );
2514 outline.Split( end, true );
2515
2516 const int idA = outline.Find( start );
2517 const int idB = outline.Find( end );
2518
2519 if( idA == -1 || idB == -1 )
2520 return false;
2521
2522 aLeft.Clear();
2523 aRight.Clear();
2524
2525 for( int i = idA;; )
2526 {
2527 aLeft.Append( outline.CPoint( i ) );
2528
2529 i = ( i + 1 ) % outline.PointCount();
2530
2531 if( i == idB )
2532 {
2533 aLeft.Append( outline.CPoint( i ) );
2534 break;
2535 }
2536
2537 if( i == idA )
2538 return false;
2539 }
2540
2541 if( aLeft.PointCount() < 2 )
2542 return false;
2543
2544 for( int i = idB;; )
2545 {
2546 aRight.Append( outline.CPoint( i ) );
2547
2548 i = ( i + 1 ) % outline.PointCount();
2549
2550 if( i == idA )
2551 {
2552 aRight.Append( outline.CPoint( i ) );
2553 break;
2554 }
2555
2556 if( i == idB )
2557 return false;
2558 }
2559
2560 if( aRight.PointCount() < 2 )
2561 return false;
2562
2563 if( aLeft.CPoint( 0 ) != start )
2564 {
2565 aLeft = aLeft.Reverse();
2566 wxASSERT( aLeft.CPoint( 0 ) == start );
2567 }
2568
2569 if( aRight.CPoint( 0 ) != start )
2570 {
2571 aRight = aRight.Reverse();
2572 wxASSERT( aRight.CPoint( 0 ) == start );
2573 }
2574
2575 SEG base( CPoint( 0 ), CPoint( 1 ) );
2576 int sideLeft = base.Side( aLeft.CPoint( 1 ) );
2577 int sideRight = base.Side( aRight.CPoint( 1 ) );
2578
2579 if( sideLeft == 0 || sideRight == 0 )
2580 return false;
2581
2582 if( sideLeft == sideRight )
2583 return false;
2584
2585 if( sideLeft > 0 && sideRight < 0 )
2586 std::swap( aLeft, aRight );
2587
2588 if( aLeft.PointCount() < 4 )
2589 return false;
2590
2591 if( aRight.PointCount() < 4 )
2592 return false;
2593
2594 aLeft.Remove( 0 );
2595 aLeft.Remove( aLeft.PointCount() - 1 );
2596
2597 aRight.Remove( 0 );
2598 aRight.Remove( aRight.PointCount() - 1 );
2599
2600 return true;
2601}
2602
2603
2605 ERROR_LOC aErrorLoc ) const
2606{
2607 aBuffer.AddOutline( *this );
2608}
2609
2610
2612 m_point( aPoint ),
2613 m_finished( false ),
2614 m_state( 0 ),
2615 m_count( 0 )
2616{
2617}
2618
2619
2621 const VECTOR2I& ip, const VECTOR2I& ipNext )
2622{
2623 if( ipNext.y == m_point.y )
2624 {
2625 if( ( ipNext.x == m_point.x )
2626 || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
2627 {
2628 m_finished = true;
2629 m_state = -1;
2630 return false;
2631 }
2632 }
2633
2634 if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
2635 {
2636 if( ip.x >= m_point.x )
2637 {
2638 if( ipNext.x > m_point.x )
2639 {
2640 m_state = 1 - m_state;
2641 }
2642 else
2643 {
2644 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2645 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2646
2647 if( !d )
2648 {
2649 m_finished = true;
2650 m_state = -1;
2651 return false;
2652 }
2653
2654 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2655 m_state = 1 - m_state;
2656 }
2657 }
2658 else
2659 {
2660 if( ipNext.x > m_point.x )
2661 {
2662 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2663 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2664
2665 if( !d )
2666 {
2667 m_finished = true;
2668 m_state = -1;
2669 return false;
2670 }
2671
2672 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2673 m_state = 1 - m_state;
2674 }
2675 }
2676 }
2677
2678 return true;
2679}
2680
2681
2683{
2684 if( !m_count )
2685 {
2686 m_lastPoint = aPolyline.CPoint( 0 );
2687 m_firstPoint = aPolyline.CPoint( 0 );
2688 }
2689
2690 m_count += aPolyline.PointCount();
2691
2692 for( int i = 1; i < aPolyline.PointCount(); i++ )
2693 {
2694 auto p = aPolyline.CPoint( i );
2695
2696 if( !processVertex( m_lastPoint, p ) )
2697 return;
2698
2699 m_lastPoint = p;
2700 }
2701
2702}
2703
2704
2706{
2707 processVertex( m_lastPoint, m_firstPoint );
2708 return m_state > 0;
2709}
2710
2711
2712bool SHAPE_LINE_CHAIN::IsSharedPt( size_t aIndex ) const
2713{
2714 return aIndex < m_shapes.size()
2715 && m_shapes[aIndex].first != SHAPE_IS_PT
2716 && m_shapes[aIndex].second != SHAPE_IS_PT;
2717}
2718
2719
2720bool SHAPE_LINE_CHAIN::IsPtOnArc( size_t aPtIndex ) const
2721{
2722 return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
2723}
2724
2725
2726bool SHAPE_LINE_CHAIN::IsArcSegment( size_t aSegment ) const
2727{
2728 /*
2729 * A segment is part of an arc except in the special case of two arcs next to each other
2730 * but without a shared vertex. Here there is a segment between the end of the first arc
2731 * and the start of the second arc.
2732 */
2733 size_t nextIdx = aSegment + 1;
2734
2735 if( nextIdx > m_shapes.size() - 1 )
2736 {
2737 if( nextIdx == m_shapes.size() && m_closed && IsSharedPt( 0 ) )
2738 nextIdx = 0; // segment between end point and first point
2739 else
2740 return false;
2741 }
2742
2743 return ( IsPtOnArc( aSegment )
2744 && ( ArcIndex( aSegment ) == m_shapes[nextIdx].first ) );
2745}
2746
2747
2748bool SHAPE_LINE_CHAIN::IsArcStart( size_t aIndex ) const
2749{
2750 if( !IsArcSegment( aIndex ) ) // also does bound checking
2751 return false;
2752
2753 if( IsSharedPt( aIndex ) )
2754 return true;
2755
2756 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
2757
2758 return arc.GetP0() == m_points[aIndex];
2759}
2760
2761
2762bool SHAPE_LINE_CHAIN::IsArcEnd( size_t aIndex ) const
2763{
2764 size_t prevIndex = aIndex - 1;
2765
2766 if( aIndex == 0 )
2767 prevIndex = m_points.size() - 1;
2768 else if( aIndex > m_points.size() -1 )
2769 return false; // invalid index requested
2770
2771 if( !IsArcSegment( prevIndex ) )
2772 return false;
2773
2774 if( IsSharedPt( aIndex ) )
2775 return true;
2776
2777 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
2778
2779 return arc.GetP1() == m_points[aIndex];
2780}
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:294
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:623
Represent basic circle geometry with utility geometry functions.
Definition: circle.h:33
std::vector< VECTOR2I > Intersect(const CIRCLE &aCircle) const
Compute the intersection points between this circle and aCircle.
Definition: circle.cpp:221
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.h:263
int GetWidth() const
Definition: shape_arc.h:158
void SetWidth(int aWidth)
Definition: shape_arc.h:153
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:212
const VECTOR2I & GetP1() const
Definition: shape_arc.h:114
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:244
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:542
int Intersect(const SHAPE_ARC &aArc, std::vector< VECTOR2I > *aIpsBuffer) const
Find intersection points between this arc and aArc.
Definition: shape_arc.cpp:316
double GetRadius() const
Definition: shape_arc.cpp:536
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:222
void Reverse()
Definition: shape_arc.cpp:657
const VECTOR2I & GetP0() const
Definition: shape_arc.h:113
const VECTOR2I & GetCenter() const
Definition: shape_arc.cpp:505
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
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
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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
const std::optional< INTERSECTION > SelfIntersectingWithArcs() const
Check if the line chain is self-intersecting.
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.
void RemoveDuplicatePoints()
Remove the duplicate points 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:278
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:380
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
BOX2I_MINMAX(const SEG &aSeg)
bool Intersects(const BOX2I_MINMAX &aOther) const
BOX2I_MINMAX(const SHAPE_ARC &aArc)
BOX2I_MINMAX(const BOX2I &aBox)
BOX2I_MINMAX(int aLeft, int aTop, int aRight, int aBottom)
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
SHAPE_KEY(int aFirstIdx, int aArcIdx, const BOX2I_MINMAX &aBBox)
BOX2I_MINMAX m_BBox
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
bool TestSegmentHitFast(const VECTOR2I &aRefPoint, const VECTOR2I &aStart, const VECTOR2I &aEnd, int aDist)
Test if a point hits a line segment within a given distance.
Definition: trigo.cpp:541
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:162
VECTOR2< double > VECTOR2D
Definition: vector2d.h:637