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