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