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 ) != CLastPoint() )
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
1748bool SHAPE_LINE_CHAIN::Intersects( const SEG& aSeg ) const
1749{
1750 for( int s = 0; s < SegmentCount(); s++ )
1751 {
1752 if( CSegment( s ).Intersects( aSeg ) )
1753 return true;
1754 }
1755
1756 return false;
1757}
1758
1759
1760static inline void addIntersection( SHAPE_LINE_CHAIN::INTERSECTIONS& aIps, int aPc,
1762{
1763 if( aIps.size() == 0 )
1764 {
1765 aIps.push_back( aP );
1766 return;
1767 }
1768
1769 aIps.push_back( aP );
1770}
1771
1772
1774 bool aExcludeColinearAndTouching, BOX2I* aChainBBox ) const
1775{
1776 BOX2I bb_other = aChainBBox ? *aChainBBox : aChain.BBox();
1777
1778 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1779 {
1780 const SEG& a = CSegment( s1 );
1781 const BOX2I bb_cur( a.A, a.B - a.A );
1782
1783 if( !bb_other.Intersects( bb_cur ) )
1784 continue;
1785
1786 for( int s2 = 0; s2 < aChain.SegmentCount(); s2++ )
1787 {
1788 const SEG& b = aChain.CSegment( s2 );
1789 INTERSECTION is;
1790
1791 is.index_our = s1;
1792 is.index_their = s2;
1793 is.is_corner_our = false;
1794 is.is_corner_their = false;
1795 is.valid = true;
1796
1797 OPT_VECTOR2I p = a.Intersect( b );
1798
1799 bool coll = a.Collinear( b );
1800
1801 if( coll && ! aExcludeColinearAndTouching )
1802 {
1803 if( a.Contains( b.A ) )
1804 {
1805 is.p = b.A;
1806 is.is_corner_their = true;
1807 addIntersection(aIp, PointCount(), is);
1808 }
1809
1810 if( a.Contains( b.B ) )
1811 {
1812 is.p = b.B;
1813 is.index_their++;
1814 is.is_corner_their = true;
1815 addIntersection( aIp, PointCount(), is );
1816 }
1817
1818 if( b.Contains( a.A ) )
1819 {
1820 is.p = a.A;
1821 is.is_corner_our = true;
1822 addIntersection( aIp, PointCount(), is );
1823 }
1824
1825 if( b.Contains( a.B ) )
1826 {
1827 is.p = a.B;
1828 is.index_our++;
1829 is.is_corner_our = true;
1830 addIntersection( aIp, PointCount(), is );
1831 }
1832 }
1833 else if( p )
1834 {
1835 is.p = *p;
1836 is.is_corner_our = false;
1837 is.is_corner_their = false;
1838
1839 if( p == a.A )
1840 {
1841 is.is_corner_our = true;
1842 }
1843
1844 if( p == a.B )
1845 {
1846 is.is_corner_our = true;
1847 is.index_our++;
1848 }
1849
1850 if( p == b.A )
1851 {
1852 is.is_corner_their = true;
1853 }
1854
1855 if( p == b.B )
1856 {
1857 is.is_corner_their = true;
1858 is.index_their++;
1859 }
1860
1861 addIntersection( aIp, PointCount(), is );
1862 }
1863 }
1864 }
1865
1866 return aIp.size();
1867}
1868
1869
1870int SHAPE_LINE_CHAIN::PathLength( const VECTOR2I& aP, int aIndex ) const
1871{
1872 int sum = 0;
1873
1874 for( int i = 0; i < SegmentCount(); i++ )
1875 {
1876 const SEG seg = CSegment( i );
1877 bool indexMatch = true;
1878
1879 if( aIndex >= 0 )
1880 {
1881 if( aIndex == SegmentCount() )
1882 {
1883 indexMatch = ( i == SegmentCount() - 1 );
1884 }
1885 else
1886 {
1887 indexMatch = ( i == aIndex );
1888 }
1889 }
1890
1891 if( indexMatch )
1892 {
1893 sum += ( aP - seg.A ).EuclideanNorm();
1894 return sum;
1895 }
1896 else
1897 sum += seg.Length();
1898 }
1899
1900 return -1;
1901}
1902
1903
1904bool SHAPE_LINE_CHAIN_BASE::PointInside( const VECTOR2I& aPt, int aAccuracy,
1905 bool aUseBBoxCache ) const
1906{
1907 /*
1908 * Don't check the bounding box unless it's cached. Building it is about the same speed as
1909 * the rigorous test below and so just slows things down by doing potentially two tests.
1910 */
1911 if( aUseBBoxCache && GetCachedBBox() && !GetCachedBBox()->Contains( aPt ) )
1912 return false;
1913
1914 if( !IsClosed() || GetPointCount() < 3 )
1915 return false;
1916
1917 /*
1918 * To check for interior points, we draw a line in the positive x direction from
1919 * the point. If it intersects an even number of segments, the point is outside the
1920 * line chain (it had to first enter and then exit). Otherwise, it is inside the chain.
1921 *
1922 * Note: slope might be denormal here in the case of a horizontal line but we require our
1923 * y to move from above to below the point (or vice versa)
1924 *
1925 * Note: we open-code CPoint() here so that we don't end up calculating the size of the
1926 * vector number-of-points times. This has a non-trivial impact on zone fill times.
1927 */
1928 int pointCount = GetPointCount();
1929 bool inside = false;
1930
1931 for( int i = 0; i < pointCount; )
1932 {
1933 const VECTOR2I p1 = GetPoint( i++ );
1934 const VECTOR2I p2 = GetPoint( i == pointCount ? 0 : i );
1935 const VECTOR2I diff = p2 - p1;
1936
1937 if( diff.y == 0 )
1938 continue;
1939
1940 const int d = rescale( diff.x, ( aPt.y - p1.y ), diff.y );
1941
1942 if( ( ( p1.y >= aPt.y ) != ( p2.y >= aPt.y ) ) && ( aPt.x - p1.x < d ) )
1943 inside = !inside;
1944 }
1945
1946 // If accuracy is <= 1 (nm) then we skip the accuracy test for performance. Otherwise
1947 // we use "OnEdge(accuracy)" as a proxy for "Inside(accuracy)".
1948 if( aAccuracy <= 1 )
1949 return inside;
1950 else
1951 return inside || PointOnEdge( aPt, aAccuracy );
1952}
1953
1954
1955bool SHAPE_LINE_CHAIN_BASE::PointOnEdge( const VECTOR2I& aPt, int aAccuracy ) const
1956{
1957 return EdgeContainingPoint( aPt, aAccuracy ) >= 0;
1958}
1959
1960
1961int SHAPE_LINE_CHAIN_BASE::EdgeContainingPoint( const VECTOR2I& aPt, int aAccuracy ) const
1962{
1963 const int threshold = aAccuracy + 1;
1964 const int64_t thresholdSq = int64_t( threshold ) * threshold;
1965 const size_t pointCount = GetPointCount();
1966
1967 if( !pointCount )
1968 {
1969 return -1;
1970 }
1971 else if( pointCount == 1 )
1972 {
1973 SEG::ecoord distSq = GetPoint( 0 ).SquaredDistance( aPt );
1974 return distSq <= thresholdSq ? 0 : -1;
1975 }
1976
1977 const size_t segCount = GetSegmentCount();
1978
1979 for( size_t i = 0; i < segCount; i++ )
1980 {
1981 const SEG s = GetSegment( i );
1982
1983 if( s.A == aPt || s.B == aPt )
1984 return i;
1985
1986 if( s.SquaredDistance( aPt ) <= thresholdSq )
1987 return i;
1988 }
1989
1990 return -1;
1991}
1992
1993
1994bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
1995{
1996 if( !PointCount() )
1997 return false;
1998 else if( PointCount() == 1 )
1999 return m_points[0] == aP;
2000
2001 for( int i = 0; i < SegmentCount(); i++ )
2002 {
2003 const SEG s = CSegment( i );
2004
2005 if( s.A == aP || s.B == aP )
2006 return true;
2007
2008 if( s.Distance( aP ) <= aDist )
2009 return true;
2010 }
2011
2012 return false;
2013}
2014
2015
2016const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
2017{
2018 const size_t segCount = SegmentCount();
2019 std::vector<SEG> segments( segCount );
2020
2021 for( size_t s = 0; s < segCount; s++ )
2022 segments[s] = CSegment( s );
2023
2024 for( size_t s1 = 0; s1 < segCount; s1++ )
2025 {
2026 const SEG& cs1 = segments[s1];
2027
2028 for( size_t s2 = s1 + 1; s2 < segCount; s2++ )
2029 {
2030 const SEG& cs2 = segments[s2];
2031 const VECTOR2I s2a = cs2.A, s2b = cs2.B;
2032
2033 if( s1 + 1 != s2 && cs1.Contains( s2a ) )
2034 {
2035 INTERSECTION is;
2036 is.index_our = s1;
2037 is.index_their = s2;
2038 is.p = s2a;
2039 return is;
2040 }
2041 else if( cs1.Contains( s2b ) &&
2042 // for closed polylines, the ending point of the
2043 // last segment == starting point of the first segment
2044 // this is a normal case, not self intersecting case
2045 !( IsClosed() && s1 == 0 && s2 == segCount - 1 ) )
2046 {
2047 INTERSECTION is;
2048 is.index_our = s1;
2049 is.index_their = s2;
2050 is.p = s2b;
2051 return is;
2052 }
2053 else
2054 {
2055 OPT_VECTOR2I p = cs1.Intersect( cs2, true );
2056
2057 if( p )
2058 {
2059 INTERSECTION is;
2060 is.index_our = s1;
2061 is.index_their = s2;
2062 is.p = *p;
2063 return is;
2064 }
2065 }
2066 }
2067 }
2068
2069 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2070}
2071
2072
2074{
2075 SHAPE_KEY( int aFirstIdx, int aArcIdx, const BOX2I_MINMAX& aBBox ) :
2076 m_FirstIdx( aFirstIdx ), m_ArcIdx( aArcIdx ), m_BBox( aBBox )
2077 {
2078 }
2079
2083};
2084
2085
2086const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2088{
2089 auto pointsClose = []( const VECTOR2I& aPt1, const VECTOR2I& aPt2 ) -> bool
2090 {
2091 return ( VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2092 };
2093
2094 auto collideArcSeg = [&pointsClose]( const SHAPE_ARC& aArc, const SEG& aSeg, int aClearance = 0,
2095 VECTOR2I* aLocation = nullptr )
2096 {
2097 VECTOR2I center = aArc.GetCenter();
2098 CIRCLE circle( center, aArc.GetRadius() );
2099
2100 std::vector<VECTOR2I> candidatePts = circle.Intersect( aSeg );
2101
2102 for( const VECTOR2I& candidate : candidatePts )
2103 {
2104 // Skip shared points
2105 if( aArc.GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2106 continue;
2107
2108 if( aSeg.B == aArc.GetP0() && pointsClose( candidate, aSeg.B ) )
2109 continue;
2110
2111 bool collides = aArc.Collide( candidate, aClearance, nullptr, aLocation );
2112
2113 if( collides )
2114 return true;
2115 }
2116
2117 return false;
2118 };
2119
2120 auto collideArcArc = [&pointsClose]( const SHAPE_ARC& aArc1, const SHAPE_ARC& aArc2,
2121 VECTOR2I* aLocation = nullptr )
2122 {
2123 std::vector<VECTOR2I> candidatePts;
2124
2125 aArc1.Intersect( aArc2, &candidatePts );
2126
2127 for( const VECTOR2I& candidate : candidatePts )
2128 {
2129 // Skip shared points
2130 if( aArc1.GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.GetP1() ) )
2131 continue;
2132
2133 if( aArc2.GetP1() == aArc1.GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2134 continue;
2135
2136 if( aLocation )
2137 *aLocation = candidate;
2138
2139 return true;
2140 }
2141
2142 return false;
2143 };
2144
2145 auto collideSegSeg = [this]( int s1, int s2, INTERSECTION& is )
2146 {
2147 SEG seg1 = CSegment( s1 );
2148 SEG seg2 = CSegment( s2 );
2149
2150 const VECTOR2I s2a = seg2.A, s2b = seg2.B;
2151
2152 if( s1 + 1 != s2 && seg1.Contains( s2a ) )
2153 {
2154 is.index_our = s1;
2155 is.index_their = s2;
2156 is.p = s2a;
2157 return true;
2158 }
2159 else if( seg1.Contains( s2b ) &&
2160 // for closed polylines, the ending point of the
2161 // last segment == starting point of the first segment
2162 // this is a normal case, not self intersecting case
2163 !( IsClosed() && s1 == 0 && s2 == SegmentCount() - 1 ) )
2164 {
2165 is.index_our = s1;
2166 is.index_their = s2;
2167 is.p = s2b;
2168 return true;
2169 }
2170 else
2171 {
2172 OPT_VECTOR2I p = seg1.Intersect( seg2, true );
2173
2174 if( p )
2175 {
2176 is.index_our = s1;
2177 is.index_their = s2;
2178 is.p = *p;
2179 return true;
2180 }
2181 }
2182
2183 return false;
2184 };
2185
2186 INTERSECTION is;
2187
2188 std::vector<SHAPE_KEY> shapeCache;
2189 for( int si = 0; si != -1; si = NextShape( si ) )
2190 {
2191 int arci = ArcIndex( si );
2192
2193 shapeCache.emplace_back( si, arci,
2194 arci == -1 ? BOX2I_MINMAX( CSegment( si ) )
2195 : BOX2I_MINMAX( Arc( arci ) ) );
2196 }
2197
2198 for( size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2199 {
2200 for( size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2201 {
2202 VECTOR2I loc;
2203 const SHAPE_KEY& k1 = shapeCache[sk1];
2204 const SHAPE_KEY& k2 = shapeCache[sk2];
2205
2206 if( !k1.m_BBox.Intersects( k2.m_BBox ) )
2207 continue;
2208
2209 if( k1.m_ArcIdx == -1 && k2.m_ArcIdx == -1 )
2210 {
2211 if( collideSegSeg( k1.m_FirstIdx, k2.m_FirstIdx, is ) )
2212 {
2213 return is;
2214 }
2215 }
2216 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx == -1 )
2217 {
2218 if( collideArcSeg( Arc( k1.m_ArcIdx ), CSegment( k2.m_FirstIdx ), 0, &loc ) )
2219 {
2220 is.index_our = k1.m_FirstIdx;
2221 is.index_their = k2.m_FirstIdx;
2222 is.p = loc;
2223 return is;
2224 }
2225 }
2226 else if( k1.m_ArcIdx == -1 && k2.m_ArcIdx != -1 )
2227 {
2228 if( collideArcSeg( Arc( k2.m_ArcIdx ), CSegment( k1.m_FirstIdx ), 0, &loc ) )
2229 {
2230 is.index_our = k1.m_FirstIdx;
2231 is.index_their = k2.m_FirstIdx;
2232 is.p = loc;
2233 return is;
2234 }
2235 }
2236 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx != -1 )
2237 {
2238 if( collideArcArc( Arc( k1.m_ArcIdx ), Arc( k2.m_ArcIdx ), &loc ) )
2239 {
2240 is.index_our = k1.m_FirstIdx;
2241 is.index_their = k2.m_FirstIdx;
2242 is.p = loc;
2243 return is;
2244 }
2245 }
2246 }
2247 }
2248
2249 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2250}
2251
2252
2254 bool aAllowInternalShapePoints ) const
2255{
2256 if( PointCount() == 0 )
2257 {
2258 // The only right answer here is "don't crash".
2259 return { 0, 0 };
2260 }
2261
2262 int min_d = std::numeric_limits<int>::max();
2263 int nearest = 0;
2264
2265 for( int i = 0; i < SegmentCount(); i++ )
2266 {
2267 int d = CSegment( i ).Distance( aP );
2268
2269 if( d < min_d )
2270 {
2271 min_d = d;
2272 nearest = i;
2273 }
2274 }
2275
2276 if( !aAllowInternalShapePoints )
2277 {
2278 //Snap to arc end points if the closest found segment is part of an arc segment
2279 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
2280 {
2281 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
2282 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
2283
2284 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
2285 nearest++;
2286
2287 // Is this the start or end of an arc? If so, return it directly
2288 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
2289 {
2290 return m_points[nearest];
2291 }
2292 else
2293 {
2294 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
2295 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
2296 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
2297
2298 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
2299 return nearestArc.GetP1();
2300 else
2301 return nearestArc.GetP0();
2302 }
2303
2304 }
2305 }
2306
2307 return CSegment( nearest ).NearestPoint( aP );
2308}
2309
2310
2311const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) const
2312{
2313 if( PointCount() == 0 )
2314 {
2315 // The only right answer here is "don't crash".
2316 return { 0, 0 };
2317 }
2318
2319 int nearest = 0;
2320
2321 dist = std::numeric_limits<int>::max();
2322
2323 for( int i = 0; i < PointCount(); i++ )
2324 {
2325 int d = aSeg.LineDistance( CPoint( i ) );
2326
2327 if( d < dist )
2328 {
2329 dist = d;
2330 nearest = i;
2331 }
2332 }
2333
2334 return CPoint( nearest );
2335}
2336
2337
2339{
2340 int min_d = std::numeric_limits<int>::max();
2341 int nearest = 0;
2342
2343 for( int i = 0; i < SegmentCount(); i++ )
2344 {
2345 int d = CSegment( i ).Distance( aP );
2346
2347 if( d < min_d )
2348 {
2349 min_d = d;
2350 nearest = i;
2351 }
2352 }
2353
2354 return nearest;
2355}
2356
2357
2358const std::string SHAPE_LINE_CHAIN::Format( bool aCplusPlus ) const
2359{
2360 std::stringstream ss;
2361
2362 ss << "SHAPE_LINE_CHAIN( { ";
2363
2364 for( int i = 0; i < PointCount(); i++ )
2365 {
2366 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
2367
2368 if( i != PointCount() -1 )
2369 ss << ", ";
2370 }
2371
2372 ss << "}, " << ( m_closed ? "true" : "false" );
2373 ss << " );";
2374
2375 return ss.str();
2376
2377 /* fixme: arcs
2378 for( size_t i = 0; i < m_arcs.size(); i++ )
2379 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
2380 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
2381 << m_arcs[i].GetCentralAngle().AsDegrees();
2382
2383 return ss.str();*/
2384}
2385
2386
2388{
2389 SHAPE_LINE_CHAIN a(*this), b( aOther );
2390 a.Simplify();
2391 b.Simplify();
2392
2393 if( a.m_points.size() != b.m_points.size() )
2394 return false;
2395
2396 for( int i = 0; i < a.PointCount(); i++ )
2397 {
2398 if( a.CPoint( i ) != b.CPoint( i ) )
2399 return false;
2400 }
2401
2402 return true;
2403}
2404
2405
2407{
2409 return Intersect( aChain, dummy ) != 0;
2410}
2411
2412
2414{
2415 return new SHAPE_LINE_CHAIN( *this );
2416}
2417
2418
2419bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
2420{
2421 size_t n_pts;
2422 size_t n_arcs;
2423
2424 m_points.clear();
2425 aStream >> n_pts;
2426
2427 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
2428 if( n_pts > aStream.str().size() )
2429 return false;
2430
2431 aStream >> m_closed;
2432 aStream >> n_arcs;
2433
2434 if( n_arcs > aStream.str().size() )
2435 return false;
2436
2437 for( size_t i = 0; i < n_pts; i++ )
2438 {
2439 int x, y;
2440 ssize_t ind;
2441 aStream >> x;
2442 aStream >> y;
2443 m_points.emplace_back( x, y );
2444
2445 aStream >> ind;
2446 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
2447 }
2448
2449 for( size_t i = 0; i < n_arcs; i++ )
2450 {
2451 VECTOR2I p0, pc;
2452 double angle;
2453
2454 aStream >> pc.x;
2455 aStream >> pc.y;
2456 aStream >> p0.x;
2457 aStream >> p0.y;
2458 aStream >> angle;
2459
2460 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
2461 }
2462
2463 return true;
2464}
2465
2466
2467const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
2468{
2469 int total = 0;
2470
2471 if( aPathLength == 0 )
2472 return CPoint( 0 );
2473
2474 for( int i = 0; i < SegmentCount(); i++ )
2475 {
2476 const SEG& s = CSegment( i );
2477 int l = s.Length();
2478
2479 if( total + l >= aPathLength )
2480 {
2481 VECTOR2I d( s.B - s.A );
2482 return s.A + d.Resize( aPathLength - total );
2483 }
2484
2485 total += l;
2486 }
2487
2488 return CLastPoint();
2489}
2490
2491
2492double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
2493{
2494 // see https://www.mathopenref.com/coordpolygonarea2.html
2495
2496 if( !m_closed )
2497 return 0.0;
2498
2499 double area = 0.0;
2500 int size = m_points.size();
2501
2502 for( int i = 0, j = size - 1; i < size; ++i )
2503 {
2504 area += ( (double) m_points[j].x + m_points[i].x ) *
2505 ( (double) m_points[j].y - m_points[i].y );
2506 j = i;
2507 }
2508
2509 if( aAbsolute )
2510 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2511 else
2512 return -area * 0.5; // The result would be negative if points are anti-clockwise
2513}
2514
2515
2517{
2518 std::vector<VECTOR2I> pts_unique;
2519 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2520
2521 // Always try to keep at least 2 points otherwise, we're not really a line
2522 if( PointCount() < 3 )
2523 {
2524 return;
2525 }
2526 else if( PointCount() == 3 )
2527 {
2528 if( m_points[0] == m_points[1] )
2529 Remove( 1 );
2530
2531 return;
2532 }
2533
2534 int i = 0;
2535
2536 while( i < PointCount() )
2537 {
2538 int j = i + 1;
2539
2540 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
2541 // one of them is part of a shape and one is not.
2542 while( j < PointCount() && m_points[i] == m_points[j] &&
2543 ( m_shapes[i] == m_shapes[j] ||
2544 m_shapes[i] == SHAPES_ARE_PT ||
2545 m_shapes[j] == SHAPES_ARE_PT ) )
2546 {
2547 j++;
2548 }
2549
2550 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
2551
2552 if( shapeToKeep == SHAPES_ARE_PT )
2553 shapeToKeep = m_shapes[j - 1];
2554
2555 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
2556 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
2557
2558 pts_unique.push_back( CPoint( i ) );
2559 shapes_unique.push_back( shapeToKeep );
2560
2561 i = j;
2562 }
2563
2564 m_points.clear();
2565 m_shapes.clear();
2566
2567 for( size_t ii = 0; ii < pts_unique.size(); ++ii )
2568 {
2569 const VECTOR2I p0 = pts_unique[ii];
2570
2571 m_points.push_back( p0 );
2572 m_shapes.push_back( shapes_unique[ii] );
2573 }
2574}
2575
2576
2577
2578void SHAPE_LINE_CHAIN::Simplify( int aTolerance )
2579{
2580 if( PointCount() < 3 )
2581 return;
2582
2583 std::vector<VECTOR2I> new_points;
2584 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2585
2586 new_points.reserve( m_points.size() );
2587 new_shapes.reserve( m_shapes.size() );
2588
2589 for( size_t start_idx = 0; start_idx < m_points.size(); )
2590 {
2591 new_points.push_back( m_points[start_idx] );
2592 new_shapes.push_back( m_shapes[start_idx] );
2593
2594 // If the line is not closed, we need at least 3 points before simplifying
2595 if( !m_closed && start_idx == m_points.size() - 2 )
2596 break;
2597
2598 // Initialize the end index to be two points ahead of start
2599 size_t end_idx = ( start_idx + 2 ) % m_points.size();
2600 bool can_simplify = true;
2601
2602 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx || m_closed ) )
2603 {
2604 // Test all points between start_idx and end_idx
2605 for( size_t test_idx = ( start_idx + 1 ) % m_points.size();
2606 test_idx != end_idx;
2607 test_idx = ( test_idx + 1 ) % m_points.size() )
2608 {
2609 // Check if all points are regular points (not arcs)
2610 if( m_shapes[start_idx].first != SHAPE_IS_PT ||
2611 m_shapes[test_idx].first != SHAPE_IS_PT ||
2612 m_shapes[end_idx].first != SHAPE_IS_PT )
2613 {
2614 can_simplify = false;
2615 break;
2616 }
2617
2618 // Test if the point is within the allowed error
2619 if( !TestSegmentHit( m_points[test_idx], m_points[start_idx], m_points[end_idx], aTolerance ) )
2620 {
2621 can_simplify = false;
2622 break;
2623 }
2624 }
2625
2626 if( can_simplify )
2627 {
2628 // If we can simplify, move end_idx one further
2629 end_idx = ( end_idx + 1 ) % m_points.size();
2630 }
2631 }
2632
2633 // If we couldn't simplify at all, move to the next point
2634 if( end_idx == ( start_idx + 2 ) % m_points.size() )
2635 {
2636 ++start_idx;
2637 }
2638 else
2639 {
2640 // Otherwise, jump to the last point we could include in the simplification
2641 size_t new_start_idx = ( end_idx + m_points.size() - 1 ) % m_points.size();
2642
2643 // If we looped all the way around, we're done
2644 if( new_start_idx <= start_idx )
2645 break;
2646
2647 start_idx = new_start_idx;
2648 }
2649 }
2650
2651 // If we have only one point, we need to add a second point to make a line
2652 if( new_points.size() == 1 )
2653 {
2654 new_points.push_back( m_points.back() );
2655 new_shapes.push_back( m_shapes.back() );
2656 }
2657
2658 // If we are not closed, then the start and end points of the original line need to
2659 // be the start and end points of the new line.
2660 if( !m_closed && m_points.back() != new_points.back() )
2661 {
2662 new_points.push_back( m_points.back() );
2663 new_shapes.push_back( m_shapes.back() );
2664 }
2665
2666 m_points.clear();
2667 m_shapes.clear();
2668 m_points = std::move( new_points );
2669 m_shapes = std::move( new_shapes );
2670}
2671
2672
2673void SHAPE_LINE_CHAIN::Split( const VECTOR2I& aStart, const VECTOR2I& aEnd, SHAPE_LINE_CHAIN& aPre,
2674 SHAPE_LINE_CHAIN& aMid, SHAPE_LINE_CHAIN& aPost ) const
2675{
2676 VECTOR2I cp( aEnd );
2677
2678 VECTOR2I n = NearestPoint( cp, false );
2679 VECTOR2I m = NearestPoint( aStart, false );
2680
2681 SHAPE_LINE_CHAIN l( *this );
2682 l.Split( n, true );
2683 l.Split( m, true );
2684
2685 int i_start = l.Find( m );
2686 int i_end = l.Find( n );
2687
2688 if( i_start > i_end )
2689 {
2690 l = l.Reverse();
2691 i_start = l.Find( m );
2692 i_end = l.Find( n );
2693 }
2694
2695 aPre = l.Slice( 0, i_start );
2696 aPost = l.Slice( i_end, -1 );
2697 aMid = l.Slice( i_start, i_end );
2698}
2699
2700
2701
2703{
2704 std::vector<VECTOR2I> pts_unique;
2705 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2706
2707 // Always try to keep at least 2 points otherwise, we're not really a line
2708 if( PointCount() < 3 )
2709 {
2710 return *this;
2711 }
2712 else if( PointCount() == 3 )
2713 {
2714 if( m_points[0] == m_points[1] )
2715 Remove( 1 );
2716
2717 return *this;
2718 }
2719
2720 int i = 0;
2721 int np = PointCount();
2722
2723 // stage 1: eliminate duplicate vertices
2724 while( i < np )
2725 {
2726 int j = i + 1;
2727
2728 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
2729 // one of them is part of a shape and one is not.
2730 while( j < np && m_points[i] == m_points[j] &&
2731 ( m_shapes[i] == m_shapes[j] ||
2732 m_shapes[i] == SHAPES_ARE_PT ||
2733 m_shapes[j] == SHAPES_ARE_PT ) )
2734 {
2735 j++;
2736 }
2737
2738 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
2739
2740 if( shapeToKeep == SHAPES_ARE_PT )
2741 shapeToKeep = m_shapes[j - 1];
2742
2743 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
2744 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
2745
2746 pts_unique.push_back( CPoint( i ) );
2747 shapes_unique.push_back( shapeToKeep );
2748
2749 i = j;
2750 }
2751
2752 m_points.clear();
2753 m_shapes.clear();
2754 np = pts_unique.size();
2755
2756 i = 0;
2757
2758 // stage 2: eliminate colinear segments
2759 while( i < np - 2 )
2760 {
2761 const VECTOR2I p0 = pts_unique[i];
2762 int n = i;
2763
2764 if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
2765 && shapes_unique[i + 1] == SHAPES_ARE_PT )
2766 {
2767 while( n < np - 2
2768 && ( SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
2769 || SEG( p0, pts_unique[n + 2] ).Collinear( SEG( p0, pts_unique[n + 1] ) ) ) )
2770 n++;
2771 }
2772
2773 m_points.push_back( p0 );
2774 m_shapes.push_back( shapes_unique[i] );
2775
2776 if( n > i )
2777 i = n;
2778
2779 if( n == np - 2 )
2780 {
2781 m_points.push_back( pts_unique[np - 1] );
2782 m_shapes.push_back( shapes_unique[np - 1] );
2783 return *this;
2784 }
2785
2786 i++;
2787 }
2788
2789 if( np > 1 )
2790 {
2791 m_points.push_back( pts_unique[np - 2] );
2792 m_shapes.push_back( shapes_unique[np - 2] );
2793 }
2794
2795 m_points.push_back( pts_unique[np - 1] );
2796 m_shapes.push_back( shapes_unique[np - 1] );
2797
2798 assert( m_points.size() == m_shapes.size() );
2799
2800 return *this;
2801}
2802
2803bool SHAPE_LINE_CHAIN::OffsetLine( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
2804 SHAPE_LINE_CHAIN& aLeft, SHAPE_LINE_CHAIN& aRight,
2805 bool aSimplify ) const
2806{
2807 if( PointCount() < 2 )
2808 return false;
2809
2810 SHAPE_POLY_SET poly;
2811 poly.OffsetLineChain( *this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2812
2813 if( poly.OutlineCount() != 1 )
2814 return false;
2815
2816 if( poly.COutline( 0 ).PointCount() < 3 )
2817 return false;
2818
2819 if( poly.HasHoles() )
2820 return false;
2821
2822 SHAPE_LINE_CHAIN outline = poly.COutline( 0 );
2823
2824 wxASSERT( outline.IsClosed() );
2825
2826 const VECTOR2I& start = CPoint( 0 );
2827 const VECTOR2I& end = CLastPoint();
2828
2829 outline.Split( start, true );
2830 outline.Split( end, true );
2831
2832 const int idA = outline.Find( start );
2833 const int idB = outline.Find( end );
2834
2835 if( idA == -1 || idB == -1 )
2836 return false;
2837
2838 aLeft.Clear();
2839 aRight.Clear();
2840
2841 for( int i = idA;; )
2842 {
2843 aLeft.Append( outline.CPoint( i ) );
2844
2845 i = ( i + 1 ) % outline.PointCount();
2846
2847 if( i == idB )
2848 {
2849 aLeft.Append( outline.CPoint( i ) );
2850 break;
2851 }
2852
2853 if( i == idA )
2854 return false;
2855 }
2856
2857 if( aLeft.PointCount() < 2 )
2858 return false;
2859
2860 for( int i = idB;; )
2861 {
2862 aRight.Append( outline.CPoint( i ) );
2863
2864 i = ( i + 1 ) % outline.PointCount();
2865
2866 if( i == idA )
2867 {
2868 aRight.Append( outline.CPoint( i ) );
2869 break;
2870 }
2871
2872 if( i == idB )
2873 return false;
2874 }
2875
2876 if( aRight.PointCount() < 2 )
2877 return false;
2878
2879 if( aLeft.CPoint( 0 ) != start )
2880 {
2881 aLeft = aLeft.Reverse();
2882 wxASSERT( aLeft.CPoint( 0 ) == start );
2883 }
2884
2885 if( aRight.CPoint( 0 ) != start )
2886 {
2887 aRight = aRight.Reverse();
2888 wxASSERT( aRight.CPoint( 0 ) == start );
2889 }
2890
2891 SEG base( CPoint( 0 ), CPoint( 1 ) );
2892 int sideLeft = base.Side( aLeft.CPoint( 1 ) );
2893 int sideRight = base.Side( aRight.CPoint( 1 ) );
2894
2895 if( sideLeft == 0 || sideRight == 0 )
2896 return false;
2897
2898 if( sideLeft == sideRight )
2899 return false;
2900
2901 if( sideLeft > 0 && sideRight < 0 )
2902 std::swap( aLeft, aRight );
2903
2904 if( aLeft.PointCount() < 4 )
2905 return false;
2906
2907 if( aRight.PointCount() < 4 )
2908 return false;
2909
2910 aLeft.Remove( 0 );
2911 aLeft.Remove( aLeft.PointCount() - 1 );
2912
2913 aRight.Remove( 0 );
2914 aRight.Remove( aRight.PointCount() - 1 );
2915
2916 return true;
2917}
2918
2919
2921 ERROR_LOC aErrorLoc ) const
2922{
2923 aBuffer.AddOutline( *this );
2924}
2925
2926
2928 m_point( aPoint ),
2929 m_finished( false ),
2930 m_state( 0 ),
2931 m_count( 0 )
2932{
2933}
2934
2935
2937 const VECTOR2I& ip, const VECTOR2I& ipNext )
2938{
2939 if( ipNext.y == m_point.y )
2940 {
2941 if( ( ipNext.x == m_point.x )
2942 || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
2943 {
2944 m_finished = true;
2945 m_state = -1;
2946 return false;
2947 }
2948 }
2949
2950 if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
2951 {
2952 if( ip.x >= m_point.x )
2953 {
2954 if( ipNext.x > m_point.x )
2955 {
2956 m_state = 1 - m_state;
2957 }
2958 else
2959 {
2960 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2961 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2962
2963 if( !d )
2964 {
2965 m_finished = true;
2966 m_state = -1;
2967 return false;
2968 }
2969
2970 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2971 m_state = 1 - m_state;
2972 }
2973 }
2974 else
2975 {
2976 if( ipNext.x > m_point.x )
2977 {
2978 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2979 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2980
2981 if( !d )
2982 {
2983 m_finished = true;
2984 m_state = -1;
2985 return false;
2986 }
2987
2988 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2989 m_state = 1 - m_state;
2990 }
2991 }
2992 }
2993
2994 return true;
2995}
2996
2997
2999{
3000 if( !m_count )
3001 {
3002 m_lastPoint = aPolyline.CPoint( 0 );
3003 m_firstPoint = aPolyline.CPoint( 0 );
3004 }
3005
3006 m_count += aPolyline.PointCount();
3007
3008 for( int i = 1; i < aPolyline.PointCount(); i++ )
3009 {
3010 auto p = aPolyline.CPoint( i );
3011
3012 if( !processVertex( m_lastPoint, p ) )
3013 return;
3014
3015 m_lastPoint = p;
3016 }
3017
3018}
3019
3020
3022{
3023 processVertex( m_lastPoint, m_firstPoint );
3024 return m_state > 0;
3025}
3026
3027
3028bool SHAPE_LINE_CHAIN::IsSharedPt( size_t aIndex ) const
3029{
3030 return aIndex < m_shapes.size()
3031 && m_shapes[aIndex].first != SHAPE_IS_PT
3032 && m_shapes[aIndex].second != SHAPE_IS_PT;
3033}
3034
3035
3036bool SHAPE_LINE_CHAIN::IsPtOnArc( size_t aPtIndex ) const
3037{
3038 return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
3039}
3040
3041
3042bool SHAPE_LINE_CHAIN::IsArcSegment( size_t aSegment ) const
3043{
3044 /*
3045 * A segment is part of an arc except in the special case of two arcs next to each other
3046 * but without a shared vertex. Here there is a segment between the end of the first arc
3047 * and the start of the second arc.
3048 */
3049 size_t nextIdx = aSegment + 1;
3050
3051 if( nextIdx > m_shapes.size() - 1 )
3052 {
3053 if( nextIdx == m_shapes.size() && m_closed && IsSharedPt( 0 ) )
3054 nextIdx = 0; // segment between end point and first point
3055 else
3056 return false;
3057 }
3058
3059 return ( IsPtOnArc( aSegment )
3060 && ( ArcIndex( aSegment ) == m_shapes[nextIdx].first ) );
3061}
3062
3063
3064bool SHAPE_LINE_CHAIN::IsArcStart( size_t aIndex ) const
3065{
3066 if( !IsArcSegment( aIndex ) ) // also does bound checking
3067 return false;
3068
3069 if( IsSharedPt( aIndex ) )
3070 return true;
3071
3072 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
3073
3074 return arc.GetP0() == m_points[aIndex];
3075}
3076
3077
3078bool SHAPE_LINE_CHAIN::IsArcEnd( size_t aIndex ) const
3079{
3080 size_t prevIndex = aIndex - 1;
3081
3082 if( aIndex == 0 )
3083 prevIndex = m_points.size() - 1;
3084 else if( aIndex > m_points.size() -1 )
3085 return false; // invalid index requested
3086
3087 if( !IsArcSegment( prevIndex ) )
3088 return false;
3089
3090 if( IsSharedPt( aIndex ) )
3091 return true;
3092
3093 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
3094
3095 return arc.GetP1() == m_points[aIndex];
3096}
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:637
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:719
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:606
bool Intersects(const SEG &aSeg) const
Definition: seg.cpp:433
int Length() const
Return the length (this).
Definition: seg.h:343
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:439
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:286
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:675
bool Contains(const SEG &aSeg) const
Definition: seg.h:324
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:362
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.
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.
bool Intersects(const SEG &aSeg) const
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...
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
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:295
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:139
VECTOR2< double > VECTOR2D
Definition: vector2d.h:694