KiCad PCB EDA Suite
Loading...
Searching...
No Matches
shape_line_chain.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2013-2017 CERN
5 * Copyright (C) 2013-2022 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
27#include <limits>
28#include <math.h> // for hypot
29#include <map>
30#include <string> // for basic_string
31
32#include <clipper.hpp>
33#include <clipper2/clipper.h>
34#include <core/kicad_algo.h> // for alg::run_on_pair
35#include <geometry/seg.h> // for SEG, OPT_VECTOR2I
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( size_t 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 < static_cast<int>( 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 < static_cast<int>( 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 arcToSplitIndex = ArcIndex( aStartIndex );
1163 const SHAPE_ARC& arcToSplit = Arc( arcToSplitIndex );
1164
1165 // Copy the points as arc points
1166 for( size_t i = aStartIndex; arcToSplitIndex == 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, arcToSplit.GetP1(),
1179 arcToSplit.GetCenter(),
1180 arcToSplit.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 int nextShape = NextShape( i );
1196 bool isLastShape = nextShape < 0;
1197
1198 if( ( isLastShape && aEndIndex != ( numPoints - 1 ) )
1199 || ( nextShape > aEndIndex ) )
1200 {
1201 if( i == aEndIndex )
1202 {
1203 // Single point on an arc, just append the single point
1204 rv.Append( m_points[i] );
1205 return rv;
1206 }
1207
1208 // Cutting in middle of an arc, lets split it
1209 ssize_t arcIndex = ArcIndex( i );
1210 const SHAPE_ARC& currentArc = Arc( arcIndex );
1211
1212 // Copy the points as arc points
1213 for( ; i <= aEndIndex && i < numPoints; i++ )
1214 {
1215 if( arcIndex != ArcIndex( i ) )
1216 break;
1217
1218 rv.m_points.push_back( m_points[i] );
1219 rv.m_shapes.push_back( { rv.m_arcs.size(), SHAPE_IS_PT } );
1220 rv.m_bbox.Merge( m_points[i] );
1221 }
1222
1223 // Create a new arc from the existing one, with different end point.
1224 SHAPE_ARC newArc;
1225
1226 VECTOR2I newArcEnd = m_points[aEndIndex];
1227
1228 newArc.ConstructFromStartEndCenter( currentArc.GetP0(), newArcEnd,
1229 currentArc.GetCenter(),
1230 currentArc.IsClockwise() );
1231
1232
1233 rv.m_arcs.push_back( newArc );
1234
1235 return rv;
1236 }
1237 else
1238 {
1239 // append the whole arc
1240 const SHAPE_ARC& currentArc = Arc( ArcIndex( i ) );
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 aIps.push_back( aP );
1482}
1483
1484
1486 bool aExcludeColinearAndTouching, BOX2I* aChainBBox ) const
1487{
1488 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.BBox();
1489
1490 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1491 {
1492 const SEG& a = CSegment( s1 );
1493 const BOX2I bb_cur( a.A, a.B - a.A );
1494
1495 if( !bb_other.Intersects( bb_cur ) )
1496 continue;
1497
1498 for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1499 {
1500 const SEG& b = aChain.CSegment( s2 );
1501 INTERSECTION is;
1502
1503 is.index_our = s1;
1504 is.index_their = s2;
1505 is.is_corner_our = false;
1506 is.is_corner_their = false;
1507 is.valid = true;
1508
1509 OPT_VECTOR2I p = a.Intersect( b );
1510
1511 bool coll = a.Collinear( b );
1512
1513 if( coll && ! aExcludeColinearAndTouching )
1514 {
1515 if( a.Contains( b.A ) )
1516 {
1517 is.p = b.A;
1518 is.is_corner_their = true;
1519 addIntersection(aIp, PointCount(), is);
1520 }
1521
1522 if( a.Contains( b.B ) )
1523 {
1524 is.p = b.B;
1525 is.index_their++;
1526 is.is_corner_their = true;
1527 addIntersection( aIp, PointCount(), is );
1528 }
1529
1530 if( b.Contains( a.A ) )
1531 {
1532 is.p = a.A;
1533 is.is_corner_our = true;
1534 addIntersection( aIp, PointCount(), is );
1535 }
1536
1537 if( b.Contains( a.B ) )
1538 {
1539 is.p = a.B;
1540 is.index_our++;
1541 is.is_corner_our = true;
1542 addIntersection( aIp, PointCount(), is );
1543 }
1544 }
1545 else if( p )
1546 {
1547 is.p = *p;
1548 is.is_corner_our = false;
1549 is.is_corner_their = false;
1550
1551 if( p == a.A )
1552 {
1553 is.is_corner_our = true;
1554 }
1555
1556 if( p == a.B )
1557 {
1558 is.is_corner_our = true;
1559 is.index_our++;
1560 }
1561
1562 if( p == b.A )
1563 {
1564 is.is_corner_their = true;
1565 }
1566
1567 if( p == b.B )
1568 {
1569 is.is_corner_their = true;
1570 is.index_their++;
1571 }
1572
1573 addIntersection( aIp, PointCount(), is );
1574 }
1575 }
1576 }
1577
1578 return aIp.size();
1579}
1580
1581
1582int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP, int aIndex ) const
1583{
1584 int sum = 0;
1585
1586 for( int i = 0; i < SegmentCount(); i++ )
1587 {
1588 const SEG seg = CSegment( i );
1589 bool indexMatch = true;
1590
1591 if( aIndex >= 0 )
1592 {
1593 if( aIndex == SegmentCount() )
1594 {
1595 indexMatch = ( i == SegmentCount() - 1 );
1596 }
1597 else
1598 {
1599 indexMatch = ( i == aIndex );
1600 }
1601 }
1602
1603 if( indexMatch )
1604 {
1605 sum += ( aP - seg.A ).EuclideanNorm();
1606 return sum;
1607 }
1608 else
1609 sum += seg.Length();
1610 }
1611
1612 return -1;
1613}
1614
1615
1616bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
1617 bool aUseBBoxCache ) const
1618{
1619 /*
1620 * Don't check the bounding box unless it's cached. Building it is about the same speed as
1621 * the rigorous test below and so just slows things down by doing potentially two tests.
1622 */
1623 if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1624 return false;
1625
1626 if( !IsClosed() || GetPointCount() < 3 )
1627 return false;
1628
1629 bool inside = false;
1630
1631 /*
1632 * To check for interior points, we draw a line in the positive x direction from
1633 * the point. If it intersects an even number of segments, the point is outside the
1634 * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1635 *
1636 * Note: slope might be denormal here in the case of a horizontal line but we require our
1637 * y to move from above to below the point (or vice versa)
1638 *
1639 * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1640 * vector number-of-points times. This has a non-trivial impact on zone fill times.
1641 */
1642 int pointCount = GetPointCount();
1643
1644 for( int i = 0; i < pointCount; )
1645 {
1646 const auto p1 = GetPoint( i++ );
1647 const auto p2 = GetPoint( i == pointCount ? 0 : i );
1648 const auto diff = p2 - p1;
1649
1650 if( diff.y != 0 )
1651 {
1652 const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1653
1654 if( ( ( p1.y > aPt.y ) != ( p2.y > aPt.y ) ) && ( aPt.x - p1.x < d ) )
1655 inside = !inside;
1656 }
1657 }
1658
1659 // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1660 // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1661 if( aAccuracy <= 1 )
1662 return inside;
1663 else
1664 return inside || PointOnEdge( aPt, aAccuracy );
1665}
1666
1667
1668bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
1669{
1670 return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1671}
1672
1673
1674int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
1675{
1676 if( !GetPointCount() )
1677 {
1678 return -1;
1679 }
1680 else if( GetPointCount() == 1 )
1681 {
1682 VECTOR2I dist = GetPoint(0) - aPt;
1683 return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1684 }
1685
1686 for( size_t i = 0; i < GetSegmentCount(); i++ )
1687 {
1688 const SEG s = GetSegment( i );
1689
1690 if( s.A == aPt || s.B == aPt )
1691 return i;
1692
1693 if( s.Distance( aPt ) <= aAccuracy + 1 )
1694 return i;
1695 }
1696
1697 return -1;
1698}
1699
1700
1701bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
1702{
1703 if( !PointCount() )
1704 return false;
1705 else if( PointCount() == 1 )
1706 return m_points[0] == aP;
1707
1708 for( int i = 0; i < SegmentCount(); i++ )
1709 {
1710 const SEG s = CSegment( i );
1711
1712 if( s.A == aP || s.B == aP )
1713 return true;
1714
1715 if( s.Distance( aP ) <= aDist )
1716 return true;
1717 }
1718
1719 return false;
1720}
1721
1722
1723const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
1724{
1725 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1726 {
1727 for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1728 {
1729 const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1730
1731 if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1732 {
1733 INTERSECTION is;
1734 is.index_our = s1;
1735 is.index_their = s2;
1736 is.p = s2a;
1737 return is;
1738 }
1739 else if( CSegment( s1 ).Contains( s2b ) &&
1740 // for closed polylines, the ending point of the
1741 // last segment == starting point of the first segment
1742 // this is a normal case, not self intersecting case
1743 !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1744 {
1745 INTERSECTION is;
1746 is.index_our = s1;
1747 is.index_their = s2;
1748 is.p = s2b;
1749 return is;
1750 }
1751 else
1752 {
1753 OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1754
1755 if( p )
1756 {
1757 INTERSECTION is;
1758 is.index_our = s1;
1759 is.index_their = s2;
1760 is.p = *p;
1761 return is;
1762 }
1763 }
1764 }
1765 }
1766
1767 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
1768}
1769
1770
1772{
1773 std::vector<VECTOR2I> pts_unique;
1774 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
1775
1776 // Always try to keep at least 2 points otherwise, we're not really a line
1777 if( PointCount() < 3 )
1778 {
1779 return *this;
1780 }
1781 else if( PointCount() == 3 )
1782 {
1783 if( m_points[0] == m_points[1] )
1784 Remove( 1 );
1785
1786 return *this;
1787 }
1788
1789 int i = 0;
1790 int np = PointCount();
1791
1792 // stage 1: eliminate duplicate vertices
1793 while( i < np )
1794 {
1795 int j = i + 1;
1796
1797 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
1798 // one of them is part of a shape and one is not.
1799 while( j < np && m_points[i] == m_points[j] &&
1800 ( m_shapes[i] == m_shapes[j] ||
1801 m_shapes[i] == SHAPES_ARE_PT ||
1802 m_shapes[j] == SHAPES_ARE_PT ) )
1803 {
1804 j++;
1805 }
1806
1807 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
1808
1809 if( shapeToKeep == SHAPES_ARE_PT )
1810 shapeToKeep = m_shapes[j - 1];
1811
1812 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
1813 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
1814
1815 pts_unique.push_back( CPoint( i ) );
1816 shapes_unique.push_back( shapeToKeep );
1817
1818 i = j;
1819 }
1820
1821 m_points.clear();
1822 m_shapes.clear();
1823 np = pts_unique.size();
1824
1825 i = 0;
1826
1827 // stage 2: eliminate colinear segments
1828 while( i < np - 2 )
1829 {
1830 const VECTOR2I p0 = pts_unique[i];
1831 int n = i;
1832
1833 if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
1834 && shapes_unique[i + 1] == SHAPES_ARE_PT )
1835 {
1836 while( n < np - 2
1837 && ( SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
1838 || SEG( p0, pts_unique[n + 2] ).Collinear( SEG( p0, pts_unique[n + 1] ) ) ) )
1839 n++;
1840 }
1841
1842 m_points.push_back( p0 );
1843 m_shapes.push_back( shapes_unique[i] );
1844
1845 if( n > i )
1846 i = n;
1847
1848 if( n == np - 2 )
1849 {
1850 m_points.push_back( pts_unique[np - 1] );
1851 m_shapes.push_back( shapes_unique[np - 1] );
1852 return *this;
1853 }
1854
1855 i++;
1856 }
1857
1858 if( np > 1 )
1859 {
1860 m_points.push_back( pts_unique[np - 2] );
1861 m_shapes.push_back( shapes_unique[np - 2] );
1862 }
1863
1864 m_points.push_back( pts_unique[np - 1] );
1865 m_shapes.push_back( shapes_unique[np - 1] );
1866
1867 assert( m_points.size() == m_shapes.size() );
1868
1869 return *this;
1870}
1871
1872
1874 bool aAllowInternalShapePoints ) const
1875{
1876 if( PointCount() == 0 )
1877 {
1878 // The only right answer here is "don't crash".
1879 return { 0, 0 };
1880 }
1881
1882 int min_d = std::numeric_limits<int>::max();
1883 int nearest = 0;
1884
1885 for( int i = 0; i < SegmentCount(); i++ )
1886 {
1887 int d = CSegment( i ).Distance( aP );
1888
1889 if( d < min_d )
1890 {
1891 min_d = d;
1892 nearest = i;
1893 }
1894 }
1895
1896 if( !aAllowInternalShapePoints )
1897 {
1898 //Snap to arc end points if the closest found segment is part of an arc segment
1899 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
1900 {
1901 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
1902 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
1903
1904 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
1905 nearest++;
1906
1907 // Is this the start or end of an arc? If so, return it directly
1908 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
1909 {
1910 return m_points[nearest];
1911 }
1912 else
1913 {
1914 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
1915 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
1916 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
1917
1918 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
1919 return nearestArc.GetP1();
1920 else
1921 return nearestArc.GetP0();
1922 }
1923
1924 }
1925 }
1926
1927 return CSegment( nearest ).NearestPoint( aP );
1928}
1929
1930
1931const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
1932{
1933 if( PointCount() == 0 )
1934 {
1935 // The only right answer here is "don't crash".
1936 return { 0, 0 };
1937 }
1938
1939 int nearest = 0;
1940
1941 dist = std::numeric_limits<int>::max();
1942
1943 for( int i = 0; i < PointCount(); i++ )
1944 {
1945 int d = aSeg.LineDistance( CPoint( i ) );
1946
1947 if( d < dist )
1948 {
1949 dist = d;
1950 nearest = i;
1951 }
1952 }
1953
1954 return CPoint( nearest );
1955}
1956
1957
1959{
1960 int min_d = std::numeric_limits<int>::max();
1961 int nearest = 0;
1962
1963 for( int i = 0; i < SegmentCount(); i++ )
1964 {
1965 int d = CSegment( i ).Distance( aP );
1966
1967 if( d < min_d )
1968 {
1969 min_d = d;
1970 nearest = i;
1971 }
1972 }
1973
1974 return nearest;
1975}
1976
1977
1978const std::string SHAPE_LINE_CHAIN::Format( bool aCplusPlus ) const
1979{
1980 std::stringstream ss;
1981
1982 ss << "SHAPE_LINE_CHAIN( { ";
1983
1984 for( int i = 0; i < PointCount(); i++ )
1985 {
1986 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
1987
1988 if( i != PointCount() -1 )
1989 ss << ", ";
1990 }
1991
1992 ss << "}, " << ( m_closed ? "true" : "false" );
1993 ss << " );";
1994
1995 return ss.str();
1996
1997 /* fixme: arcs
1998 for( size_t i = 0; i < m_arcs.size(); i++ )
1999 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
2000 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
2001 << m_arcs[i].GetCentralAngle().AsDegrees();
2002
2003 return ss.str();*/
2004}
2005
2006
2008{
2009 SHAPE_LINE_CHAIN a(*this), b( aOther );
2010 a.Simplify();
2011 b.Simplify();
2012
2013 if( a.m_points.size() != b.m_points.size() )
2014 return false;
2015
2016 for( int i = 0; i < a.PointCount(); i++ )
2017 {
2018 if( a.CPoint( i ) != b.CPoint( i ) )
2019 return false;
2020 }
2021
2022 return true;
2023}
2024
2025
2027{
2029 return Intersect( aChain, dummy ) != 0;
2030}
2031
2032
2034{
2035 return new SHAPE_LINE_CHAIN( *this );
2036}
2037
2038
2039bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
2040{
2041 size_t n_pts;
2042 size_t n_arcs;
2043
2044 m_points.clear();
2045 aStream >> n_pts;
2046
2047 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
2048 if( n_pts > aStream.str().size() )
2049 return false;
2050
2051 aStream >> m_closed;
2052 aStream >> n_arcs;
2053
2054 if( n_arcs > aStream.str().size() )
2055 return false;
2056
2057 for( size_t i = 0; i < n_pts; i++ )
2058 {
2059 int x, y;
2060 ssize_t ind;
2061 aStream >> x;
2062 aStream >> y;
2063 m_points.emplace_back( x, y );
2064
2065 aStream >> ind;
2066 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
2067 }
2068
2069 for( size_t i = 0; i < n_arcs; i++ )
2070 {
2071 VECTOR2I p0, pc;
2072 double angle;
2073
2074 aStream >> pc.x;
2075 aStream >> pc.y;
2076 aStream >> p0.x;
2077 aStream >> p0.y;
2078 aStream >> angle;
2079
2080 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
2081 }
2082
2083 return true;
2084}
2085
2086
2087const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
2088{
2089 int total = 0;
2090
2091 if( aPathLength == 0 )
2092 return CPoint( 0 );
2093
2094 for( int i = 0; i < SegmentCount(); i++ )
2095 {
2096 const SEG& s = CSegment( i );
2097 int l = s.Length();
2098
2099 if( total + l >= aPathLength )
2100 {
2101 VECTOR2I d( s.B - s.A );
2102 return s.A + d.Resize( aPathLength - total );
2103 }
2104
2105 total += l;
2106 }
2107
2108 return CPoint( -1 );
2109}
2110
2111
2112double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
2113{
2114 // see https://www.mathopenref.com/coordpolygonarea2.html
2115
2116 if( !m_closed )
2117 return 0.0;
2118
2119 double area = 0.0;
2120 int size = m_points.size();
2121
2122 for( int i = 0, j = size - 1; i < size; ++i )
2123 {
2124 area += ( (double) m_points[j].x + m_points[i].x ) *
2125 ( (double) m_points[j].y - m_points[i].y );
2126 j = i;
2127 }
2128
2129 if( aAbsolute )
2130 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2131 else
2132 return -area * 0.5; // The result would be negative if points are anti-clockwise
2133}
2134
2135
2137 m_point( aPoint ),
2138 m_finished( false ),
2139 m_state( 0 ),
2140 m_count( 0 )
2141{
2142}
2143
2144
2146 const VECTOR2I& ip, const VECTOR2I& ipNext )
2147{
2148 if( ipNext.y == m_point.y )
2149 {
2150 if( ( ipNext.x == m_point.x )
2151 || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
2152 {
2153 m_finished = true;
2154 m_state = -1;
2155 return false;
2156 }
2157 }
2158
2159 if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
2160 {
2161 if( ip.x >= m_point.x )
2162 {
2163 if( ipNext.x > m_point.x )
2164 {
2165 m_state = 1 - m_state;
2166 }
2167 else
2168 {
2169 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2170 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2171
2172 if( !d )
2173 {
2174 m_finished = true;
2175 m_state = -1;
2176 return false;
2177 }
2178
2179 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2180 m_state = 1 - m_state;
2181 }
2182 }
2183 else
2184 {
2185 if( ipNext.x > m_point.x )
2186 {
2187 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2188 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2189
2190 if( !d )
2191 {
2192 m_finished = true;
2193 m_state = -1;
2194 return false;
2195 }
2196
2197 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2198 m_state = 1 - m_state;
2199 }
2200 }
2201 }
2202
2203 return true;
2204}
2205
2206
2208{
2209 if( !m_count )
2210 {
2211 m_lastPoint = aPolyline.CPoint( 0 );
2212 m_firstPoint = aPolyline.CPoint( 0 );
2213 }
2214
2215 m_count += aPolyline.PointCount();
2216
2217 for( int i = 1; i < aPolyline.PointCount(); i++ )
2218 {
2219 auto p = aPolyline.CPoint( i );
2220
2221 if( !processVertex( m_lastPoint, p ) )
2222 return;
2223
2224 m_lastPoint = p;
2225 }
2226
2227}
2228
2229
2231{
2232 processVertex( m_lastPoint, m_firstPoint );
2233 return m_state > 0;
2234}
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:270
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:589
Definition: seg.h:42
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:291
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:341
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:269
int Length() const
Return the length (this).
Definition: seg.h:326
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:196
static SEG::ecoord Square(int a)
Definition: seg.h:123
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:329
bool Contains(const SEG &aSeg) const
Definition: seg.h:307
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:326
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:124
VECTOR2I::extended_type ecoord
Definition: shape.h:250
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:75
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:265
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:350
@ DEGREES_T
Definition: eda_angle.h:31
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:47
static void addIntersection(SHAPE_LINE_CHAIN::INTERSECTIONS &aIps, int aPc, const SHAPE_LINE_CHAIN::INTERSECTION &aP)
std::vector< FAB_LAYER_COLOR > dummy
Holds information on each point of a SHAPE_LINE_CHAIN that is retrievable after an operation with Cli...
Represent an intersection between two line segments.
bool is_corner_their
When true, the corner [index_their] of the 'their' line lies exactly on 'our' line.
bool is_corner_our
When true, the corner [index_our] of the 'our' line lies exactly on 'their' line.
int index_our
Index of the intersecting corner/segment in the 'our' (== this) line.
VECTOR2I p
Point of intersection between our and their.
bool valid
Auxiliary flag to avoid copying intersection info to intersection refining code, used by the refining...
int index_their
index of the intersecting corner/segment in the 'their' (Intersect() method parameter) line.
bool operator()(const SHAPE_LINE_CHAIN::INTERSECTION &aA, const SHAPE_LINE_CHAIN::INTERSECTION &aB) const
compareOriginDistance(const VECTOR2I &aOrigin)
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