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