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