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