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
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;
497 VECTOR2I center;
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 if( !GetPointCount() )
1922 {
1923 return -1;
1924 }
1925 else if( GetPointCount() == 1 )
1926 {
1927 VECTOR2I dist = GetPoint(0) - aPt;
1928 return ( hypot( dist.x, dist.y ) <= aAccuracy + 1 ) ? 0 : -1;
1929 }
1930
1931 for( size_t i = 0; i < GetSegmentCount(); i++ )
1932 {
1933 const SEG s = GetSegment( i );
1934
1935 if( s.A == aPt || s.B == aPt )
1936 return i;
1937
1938 if( s.Distance( aPt ) <= aAccuracy + 1 )
1939 return i;
1940 }
1941
1942 return -1;
1943}
1944
1945
1946bool SHAPE_LINE_CHAIN::CheckClearance( const VECTOR2I& aP, const int aDist ) const
1947{
1948 if( !PointCount() )
1949 return false;
1950 else if( PointCount() == 1 )
1951 return m_points[0] == aP;
1952
1953 for( int i = 0; i < SegmentCount(); i++ )
1954 {
1955 const SEG s = CSegment( i );
1956
1957 if( s.A == aP || s.B == aP )
1958 return true;
1959
1960 if( s.Distance( aP ) <= aDist )
1961 return true;
1962 }
1963
1964 return false;
1965}
1966
1967
1968const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> SHAPE_LINE_CHAIN::SelfIntersecting() const
1969{
1970 for( int s1 = 0; s1 < SegmentCount(); s1++ )
1971 {
1972 for( int s2 = s1 + 1; s2 < SegmentCount(); s2++ )
1973 {
1974 const VECTOR2I s2a = CSegment( s2 ).A, s2b = CSegment( s2 ).B;
1975
1976 if( s1 + 1 != s2 && CSegment( s1 ).Contains( s2a ) )
1977 {
1978 INTERSECTION is;
1979 is.index_our = s1;
1980 is.index_their = s2;
1981 is.p = s2a;
1982 return is;
1983 }
1984 else if( CSegment( s1 ).Contains( s2b ) &&
1985 // for closed polylines, the ending point of the
1986 // last segment == starting point of the first segment
1987 // this is a normal case, not self intersecting case
1988 !( IsClosed() && s1 == 0 && s2 == SegmentCount()-1 ) )
1989 {
1990 INTERSECTION is;
1991 is.index_our = s1;
1992 is.index_their = s2;
1993 is.p = s2b;
1994 return is;
1995 }
1996 else
1997 {
1998 OPT_VECTOR2I p = CSegment( s1 ).Intersect( CSegment( s2 ), true );
1999
2000 if( p )
2001 {
2002 INTERSECTION is;
2003 is.index_our = s1;
2004 is.index_their = s2;
2005 is.p = *p;
2006 return is;
2007 }
2008 }
2009 }
2010 }
2011
2012 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2013}
2014
2015
2017{
2018 SHAPE_KEY( int aFirstIdx, int aArcIdx, const BOX2I_MINMAX& aBBox ) :
2019 m_FirstIdx( aFirstIdx ), m_ArcIdx( aArcIdx ), m_BBox( aBBox )
2020 {
2021 }
2022
2026};
2027
2028
2029const std::optional<SHAPE_LINE_CHAIN::INTERSECTION>
2031{
2032 auto pointsClose = []( const VECTOR2I& aPt1, const VECTOR2I& aPt2 ) -> bool
2033 {
2034 return ( VECTOR2D( aPt1 ) - aPt2 ).SquaredEuclideanNorm() <= 2.0;
2035 };
2036
2037 auto collideArcSeg = [&pointsClose]( const SHAPE_ARC& aArc, const SEG& aSeg, int aClearance = 0,
2038 VECTOR2I* aLocation = nullptr )
2039 {
2040 VECTOR2I center = aArc.GetCenter();
2041 CIRCLE circle( center, aArc.GetRadius() );
2042
2043 std::vector<VECTOR2I> candidatePts = circle.Intersect( aSeg );
2044
2045 for( const VECTOR2I& candidate : candidatePts )
2046 {
2047 // Skip shared points
2048 if( aArc.GetP1() == aSeg.A && pointsClose( candidate, aSeg.A ) )
2049 continue;
2050
2051 if( aSeg.B == aArc.GetP0() && pointsClose( candidate, aSeg.B ) )
2052 continue;
2053
2054 bool collides = aArc.Collide( candidate, aClearance, nullptr, aLocation );
2055
2056 if( collides )
2057 return true;
2058 }
2059
2060 return false;
2061 };
2062
2063 auto collideArcArc = [&pointsClose]( const SHAPE_ARC& aArc1, const SHAPE_ARC& aArc2,
2064 VECTOR2I* aLocation = nullptr )
2065 {
2066 std::vector<VECTOR2I> candidatePts;
2067
2068 aArc1.Intersect( aArc2, &candidatePts );
2069
2070 for( const VECTOR2I& candidate : candidatePts )
2071 {
2072 // Skip shared points
2073 if( aArc1.GetP1() == aArc2.GetP0() && pointsClose( candidate, aArc1.GetP1() ) )
2074 continue;
2075
2076 if( aArc2.GetP1() == aArc1.GetP0() && pointsClose( candidate, aArc2.GetP1() ) )
2077 continue;
2078
2079 if( aLocation )
2080 *aLocation = candidate;
2081
2082 return true;
2083 }
2084
2085 return false;
2086 };
2087
2088 auto collideSegSeg = [this]( int s1, int s2, INTERSECTION& is )
2089 {
2090 SEG seg1 = CSegment( s1 );
2091 SEG seg2 = CSegment( s2 );
2092
2093 const VECTOR2I s2a = seg2.A, s2b = seg2.B;
2094
2095 if( s1 + 1 != s2 && seg1.Contains( s2a ) )
2096 {
2097 is.index_our = s1;
2098 is.index_their = s2;
2099 is.p = s2a;
2100 return true;
2101 }
2102 else if( seg1.Contains( s2b ) &&
2103 // for closed polylines, the ending point of the
2104 // last segment == starting point of the first segment
2105 // this is a normal case, not self intersecting case
2106 !( IsClosed() && s1 == 0 && s2 == SegmentCount() - 1 ) )
2107 {
2108 is.index_our = s1;
2109 is.index_their = s2;
2110 is.p = s2b;
2111 return true;
2112 }
2113 else
2114 {
2115 OPT_VECTOR2I p = seg1.Intersect( seg2, true );
2116
2117 if( p )
2118 {
2119 is.index_our = s1;
2120 is.index_their = s2;
2121 is.p = *p;
2122 return true;
2123 }
2124 }
2125
2126 return false;
2127 };
2128
2129 INTERSECTION is;
2130
2131 std::vector<SHAPE_KEY> shapeCache;
2132 for( int si = 0; si != -1; si = NextShape( si ) )
2133 {
2134 int arci = ArcIndex( si );
2135
2136 shapeCache.emplace_back( si, arci,
2137 arci == -1 ? BOX2I_MINMAX( CSegment( si ) )
2138 : BOX2I_MINMAX( Arc( arci ) ) );
2139 }
2140
2141 for( size_t sk1 = 0; sk1 < shapeCache.size(); sk1++ )
2142 {
2143 for( size_t sk2 = sk1 + 1; sk2 < shapeCache.size(); sk2++ )
2144 {
2145 VECTOR2I loc;
2146 const SHAPE_KEY& k1 = shapeCache[sk1];
2147 const SHAPE_KEY& k2 = shapeCache[sk2];
2148
2149 if( !k1.m_BBox.Intersects( k2.m_BBox ) )
2150 continue;
2151
2152 if( k1.m_ArcIdx == -1 && k2.m_ArcIdx == -1 )
2153 {
2154 if( collideSegSeg( k1.m_FirstIdx, k2.m_FirstIdx, is ) )
2155 {
2156 return is;
2157 }
2158 }
2159 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx == -1 )
2160 {
2161 if( collideArcSeg( Arc( k1.m_ArcIdx ), CSegment( k2.m_FirstIdx ), 0, &loc ) )
2162 {
2163 is.index_our = k1.m_FirstIdx;
2164 is.index_their = k2.m_FirstIdx;
2165 is.p = loc;
2166 return is;
2167 }
2168 }
2169 else if( k1.m_ArcIdx == -1 && k2.m_ArcIdx != -1 )
2170 {
2171 if( collideArcSeg( Arc( k2.m_ArcIdx ), CSegment( k1.m_FirstIdx ), 0, &loc ) )
2172 {
2173 is.index_our = k1.m_FirstIdx;
2174 is.index_their = k2.m_FirstIdx;
2175 is.p = loc;
2176 return is;
2177 }
2178 }
2179 else if( k1.m_ArcIdx != -1 && k2.m_ArcIdx != -1 )
2180 {
2181 if( collideArcArc( Arc( k1.m_ArcIdx ), Arc( k2.m_ArcIdx ), &loc ) )
2182 {
2183 is.index_our = k1.m_FirstIdx;
2184 is.index_their = k2.m_FirstIdx;
2185 is.p = loc;
2186 return is;
2187 }
2188 }
2189 }
2190 }
2191
2192 return std::optional<SHAPE_LINE_CHAIN::INTERSECTION>();
2193}
2194
2195
2197 bool aAllowInternalShapePoints ) const
2198{
2199 if( PointCount() == 0 )
2200 {
2201 // The only right answer here is "don't crash".
2202 return { 0, 0 };
2203 }
2204
2205 int min_d = std::numeric_limits<int>::max();
2206 int nearest = 0;
2207
2208 for( int i = 0; i < SegmentCount(); i++ )
2209 {
2210 int d = CSegment( i ).Distance( aP );
2211
2212 if( d < min_d )
2213 {
2214 min_d = d;
2215 nearest = i;
2216 }
2217 }
2218
2219 if( !aAllowInternalShapePoints )
2220 {
2221 //Snap to arc end points if the closest found segment is part of an arc segment
2222 if( nearest > 0 && nearest < PointCount() && IsArcSegment( nearest ) )
2223 {
2224 VECTOR2I ptToSegStart = CSegment( nearest ).A - aP;
2225 VECTOR2I ptToSegEnd = CSegment( nearest ).B - aP;
2226
2227 if( ptToSegStart.EuclideanNorm() > ptToSegEnd.EuclideanNorm() )
2228 nearest++;
2229
2230 // Is this the start or end of an arc? If so, return it directly
2231 if( IsArcStart( nearest ) || IsArcEnd( nearest ) )
2232 {
2233 return m_points[nearest];
2234 }
2235 else
2236 {
2237 const SHAPE_ARC& nearestArc = Arc( ArcIndex( nearest ) );
2238 VECTOR2I ptToArcStart = nearestArc.GetP0() - aP;
2239 VECTOR2I ptToArcEnd = nearestArc.GetP1() - aP;
2240
2241 if( ptToArcStart.EuclideanNorm() > ptToArcEnd.EuclideanNorm() )
2242 return nearestArc.GetP1();
2243 else
2244 return nearestArc.GetP0();
2245 }
2246
2247 }
2248 }
2249
2250 return CSegment( nearest ).NearestPoint( aP );
2251}
2252
2253
2254const VECTOR2I SHAPE_LINE_CHAIN::NearestPoint( const SEG& aSeg, int& dist ) 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 nearest = 0;
2263
2264 dist = std::numeric_limits<int>::max();
2265
2266 for( int i = 0; i < PointCount(); i++ )
2267 {
2268 int d = aSeg.LineDistance( CPoint( i ) );
2269
2270 if( d < dist )
2271 {
2272 dist = d;
2273 nearest = i;
2274 }
2275 }
2276
2277 return CPoint( nearest );
2278}
2279
2280
2282{
2283 int min_d = std::numeric_limits<int>::max();
2284 int nearest = 0;
2285
2286 for( int i = 0; i < SegmentCount(); i++ )
2287 {
2288 int d = CSegment( i ).Distance( aP );
2289
2290 if( d < min_d )
2291 {
2292 min_d = d;
2293 nearest = i;
2294 }
2295 }
2296
2297 return nearest;
2298}
2299
2300
2301const std::string SHAPE_LINE_CHAIN::Format( bool aCplusPlus ) const
2302{
2303 std::stringstream ss;
2304
2305 ss << "SHAPE_LINE_CHAIN( { ";
2306
2307 for( int i = 0; i < PointCount(); i++ )
2308 {
2309 ss << "VECTOR2I( " << m_points[i].x << ", " << m_points[i].y << ")";
2310
2311 if( i != PointCount() -1 )
2312 ss << ", ";
2313 }
2314
2315 ss << "}, " << ( m_closed ? "true" : "false" );
2316 ss << " );";
2317
2318 return ss.str();
2319
2320 /* fixme: arcs
2321 for( size_t i = 0; i < m_arcs.size(); i++ )
2322 ss << m_arcs[i].GetCenter().x << " " << m_arcs[i].GetCenter().y << " "
2323 << m_arcs[i].GetP0().x << " " << m_arcs[i].GetP0().y << " "
2324 << m_arcs[i].GetCentralAngle().AsDegrees();
2325
2326 return ss.str();*/
2327}
2328
2329
2331{
2332 SHAPE_LINE_CHAIN a(*this), b( aOther );
2333 a.Simplify();
2334 b.Simplify();
2335
2336 if( a.m_points.size() != b.m_points.size() )
2337 return false;
2338
2339 for( int i = 0; i < a.PointCount(); i++ )
2340 {
2341 if( a.CPoint( i ) != b.CPoint( i ) )
2342 return false;
2343 }
2344
2345 return true;
2346}
2347
2348
2350{
2352 return Intersect( aChain, dummy ) != 0;
2353}
2354
2355
2357{
2358 return new SHAPE_LINE_CHAIN( *this );
2359}
2360
2361
2362bool SHAPE_LINE_CHAIN::Parse( std::stringstream& aStream )
2363{
2364 size_t n_pts;
2365 size_t n_arcs;
2366
2367 m_points.clear();
2368 aStream >> n_pts;
2369
2370 // Rough sanity check, just make sure the loop bounds aren't absolutely outlandish
2371 if( n_pts > aStream.str().size() )
2372 return false;
2373
2374 aStream >> m_closed;
2375 aStream >> n_arcs;
2376
2377 if( n_arcs > aStream.str().size() )
2378 return false;
2379
2380 for( size_t i = 0; i < n_pts; i++ )
2381 {
2382 int x, y;
2383 ssize_t ind;
2384 aStream >> x;
2385 aStream >> y;
2386 m_points.emplace_back( x, y );
2387
2388 aStream >> ind;
2389 m_shapes.emplace_back( std::make_pair( ind, SHAPE_IS_PT ) );
2390 }
2391
2392 for( size_t i = 0; i < n_arcs; i++ )
2393 {
2394 VECTOR2I p0, pc;
2395 double angle;
2396
2397 aStream >> pc.x;
2398 aStream >> pc.y;
2399 aStream >> p0.x;
2400 aStream >> p0.y;
2401 aStream >> angle;
2402
2403 m_arcs.emplace_back( pc, p0, EDA_ANGLE( angle, DEGREES_T ) );
2404 }
2405
2406 return true;
2407}
2408
2409
2410const VECTOR2I SHAPE_LINE_CHAIN::PointAlong( int aPathLength ) const
2411{
2412 int total = 0;
2413
2414 if( aPathLength == 0 )
2415 return CPoint( 0 );
2416
2417 for( int i = 0; i < SegmentCount(); i++ )
2418 {
2419 const SEG& s = CSegment( i );
2420 int l = s.Length();
2421
2422 if( total + l >= aPathLength )
2423 {
2424 VECTOR2I d( s.B - s.A );
2425 return s.A + d.Resize( aPathLength - total );
2426 }
2427
2428 total += l;
2429 }
2430
2431 return CPoint( -1 );
2432}
2433
2434
2435double SHAPE_LINE_CHAIN::Area( bool aAbsolute ) const
2436{
2437 // see https://www.mathopenref.com/coordpolygonarea2.html
2438
2439 if( !m_closed )
2440 return 0.0;
2441
2442 double area = 0.0;
2443 int size = m_points.size();
2444
2445 for( int i = 0, j = size - 1; i < size; ++i )
2446 {
2447 area += ( (double) m_points[j].x + m_points[i].x ) *
2448 ( (double) m_points[j].y - m_points[i].y );
2449 j = i;
2450 }
2451
2452 if( aAbsolute )
2453 return std::fabs( area * 0.5 ); // The result would be negative if points are anti-clockwise
2454 else
2455 return -area * 0.5; // The result would be negative if points are anti-clockwise
2456}
2457
2458
2460{
2461 std::vector<VECTOR2I> pts_unique;
2462 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2463
2464 // Always try to keep at least 2 points otherwise, we're not really a line
2465 if( PointCount() < 3 )
2466 {
2467 return;
2468 }
2469 else if( PointCount() == 3 )
2470 {
2471 if( m_points[0] == m_points[1] )
2472 Remove( 1 );
2473
2474 return;
2475 }
2476
2477 int i = 0;
2478
2479 while( i < PointCount() )
2480 {
2481 int j = i + 1;
2482
2483 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
2484 // one of them is part of a shape and one is not.
2485 while( j < PointCount() && m_points[i] == m_points[j] &&
2486 ( m_shapes[i] == m_shapes[j] ||
2487 m_shapes[i] == SHAPES_ARE_PT ||
2488 m_shapes[j] == SHAPES_ARE_PT ) )
2489 {
2490 j++;
2491 }
2492
2493 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
2494
2495 if( shapeToKeep == SHAPES_ARE_PT )
2496 shapeToKeep = m_shapes[j - 1];
2497
2498 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
2499 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
2500
2501 pts_unique.push_back( CPoint( i ) );
2502 shapes_unique.push_back( shapeToKeep );
2503
2504 i = j;
2505 }
2506
2507 m_points.clear();
2508 m_shapes.clear();
2509
2510 for( size_t ii = 0; ii < pts_unique.size(); ++ii )
2511 {
2512 const VECTOR2I p0 = pts_unique[ii];
2513
2514 m_points.push_back( p0 );
2515 m_shapes.push_back( shapes_unique[ii] );
2516 }
2517}
2518
2519
2520
2521void SHAPE_LINE_CHAIN::Simplify( int aMaxError )
2522{
2523 if( PointCount() < 3 )
2524 return;
2525
2526 std::vector<VECTOR2I> new_points;
2527 std::vector<std::pair<ssize_t, ssize_t>> new_shapes;
2528
2529 new_points.reserve( m_points.size() );
2530 new_shapes.reserve( m_shapes.size() );
2531
2532 for( size_t start_idx = 0; start_idx < m_points.size(); )
2533 {
2534 new_points.push_back( m_points[start_idx] );
2535 new_shapes.push_back( m_shapes[start_idx] );
2536
2537 // If the line is not closed, we need at least 3 points before simplifying
2538 if( !m_closed && start_idx == m_points.size() - 2 )
2539 break;
2540
2541 // Initialize the end index to be two points ahead of start
2542 size_t end_idx = ( start_idx + 2 ) % m_points.size();
2543 bool can_simplify = true;
2544
2545 while( can_simplify && end_idx != start_idx && ( end_idx > start_idx || m_closed ) )
2546 {
2547 // Test all points between start_idx and end_idx
2548 for( size_t test_idx = ( start_idx + 1 ) % m_points.size();
2549 test_idx != end_idx;
2550 test_idx = ( test_idx + 1 ) % m_points.size() )
2551 {
2552 // Check if all points are regular points (not arcs)
2553 if( m_shapes[start_idx].first != SHAPE_IS_PT ||
2554 m_shapes[test_idx].first != SHAPE_IS_PT ||
2555 m_shapes[end_idx].first != SHAPE_IS_PT )
2556 {
2557 can_simplify = false;
2558 break;
2559 }
2560
2561 // Test if the point is within the allowed error
2562 if( !TestSegmentHit( m_points[test_idx], m_points[start_idx], m_points[end_idx], aMaxError ) )
2563 {
2564 can_simplify = false;
2565 break;
2566 }
2567 }
2568
2569 if( can_simplify )
2570 {
2571 // If we can simplify, move end_idx one further
2572 end_idx = ( end_idx + 1 ) % m_points.size();
2573 }
2574 }
2575
2576 // If we couldn't simplify at all, move to the next point
2577 if( end_idx == ( start_idx + 2 ) % m_points.size() )
2578 {
2579 ++start_idx;
2580 }
2581 else
2582 {
2583 // Otherwise, jump to the last point we could include in the simplification
2584 size_t new_start_idx = ( end_idx + m_points.size() - 1 ) % m_points.size();
2585
2586 // If we looped all the way around, we're done
2587 if( new_start_idx <= start_idx )
2588 break;
2589
2590 start_idx = new_start_idx;
2591 }
2592 }
2593
2594 // If we have only one point, we need to add a second point to make a line
2595 if( new_points.size() == 1 )
2596 {
2597 new_points.push_back( m_points.back() );
2598 new_shapes.push_back( m_shapes.back() );
2599 }
2600
2601 // If we are not closed, then the start and end points of the original line need to
2602 // be the start and end points of the new line.
2603 if( !m_closed && m_points.back() != new_points.back() )
2604 {
2605 new_points.push_back( m_points.back() );
2606 new_shapes.push_back( m_shapes.back() );
2607 }
2608
2609 m_points.clear();
2610 m_shapes.clear();
2611 m_points = new_points;
2612 m_shapes = new_shapes;
2613}
2614
2615
2616void SHAPE_LINE_CHAIN::Split( const VECTOR2I& aStart, const VECTOR2I& aEnd, SHAPE_LINE_CHAIN& aPre,
2617 SHAPE_LINE_CHAIN& aMid, SHAPE_LINE_CHAIN& aPost ) const
2618{
2619 VECTOR2I cp( aEnd );
2620
2621 VECTOR2I n = NearestPoint( cp, false );
2622 VECTOR2I m = NearestPoint( aStart, false );
2623
2624 SHAPE_LINE_CHAIN l( *this );
2625 l.Split( n, true );
2626 l.Split( m, true );
2627
2628 int i_start = l.Find( m );
2629 int i_end = l.Find( n );
2630
2631 if( i_start > i_end )
2632 {
2633 l = l.Reverse();
2634 i_start = l.Find( m );
2635 i_end = l.Find( n );
2636 }
2637
2638 aPre = l.Slice( 0, i_start );
2639 aPost = l.Slice( i_end, -1 );
2640 aMid = l.Slice( i_start, i_end );
2641}
2642
2643
2644
2646{
2647 std::vector<VECTOR2I> pts_unique;
2648 std::vector<std::pair<ssize_t, ssize_t>> shapes_unique;
2649
2650 // Always try to keep at least 2 points otherwise, we're not really a line
2651 if( PointCount() < 3 )
2652 {
2653 return *this;
2654 }
2655 else if( PointCount() == 3 )
2656 {
2657 if( m_points[0] == m_points[1] )
2658 Remove( 1 );
2659
2660 return *this;
2661 }
2662
2663 int i = 0;
2664 int np = PointCount();
2665
2666 // stage 1: eliminate duplicate vertices
2667 while( i < np )
2668 {
2669 int j = i + 1;
2670
2671 // We can eliminate duplicate vertices as long as they are part of the same shape, OR if
2672 // one of them is part of a shape and one is not.
2673 while( j < np && m_points[i] == m_points[j] &&
2674 ( m_shapes[i] == m_shapes[j] ||
2675 m_shapes[i] == SHAPES_ARE_PT ||
2676 m_shapes[j] == SHAPES_ARE_PT ) )
2677 {
2678 j++;
2679 }
2680
2681 std::pair<ssize_t,ssize_t> shapeToKeep = m_shapes[i];
2682
2683 if( shapeToKeep == SHAPES_ARE_PT )
2684 shapeToKeep = m_shapes[j - 1];
2685
2686 assert( shapeToKeep.first < static_cast<int>( m_arcs.size() ) );
2687 assert( shapeToKeep.second < static_cast<int>( m_arcs.size() ) );
2688
2689 pts_unique.push_back( CPoint( i ) );
2690 shapes_unique.push_back( shapeToKeep );
2691
2692 i = j;
2693 }
2694
2695 m_points.clear();
2696 m_shapes.clear();
2697 np = pts_unique.size();
2698
2699 i = 0;
2700
2701 // stage 2: eliminate colinear segments
2702 while( i < np - 2 )
2703 {
2704 const VECTOR2I p0 = pts_unique[i];
2705 int n = i;
2706
2707 if( aRemoveColinear && shapes_unique[i] == SHAPES_ARE_PT
2708 && shapes_unique[i + 1] == SHAPES_ARE_PT )
2709 {
2710 while( n < np - 2
2711 && ( SEG( p0, pts_unique[n + 2] ).LineDistance( pts_unique[n + 1] ) <= 1
2712 || SEG( p0, pts_unique[n + 2] ).Collinear( SEG( p0, pts_unique[n + 1] ) ) ) )
2713 n++;
2714 }
2715
2716 m_points.push_back( p0 );
2717 m_shapes.push_back( shapes_unique[i] );
2718
2719 if( n > i )
2720 i = n;
2721
2722 if( n == np - 2 )
2723 {
2724 m_points.push_back( pts_unique[np - 1] );
2725 m_shapes.push_back( shapes_unique[np - 1] );
2726 return *this;
2727 }
2728
2729 i++;
2730 }
2731
2732 if( np > 1 )
2733 {
2734 m_points.push_back( pts_unique[np - 2] );
2735 m_shapes.push_back( shapes_unique[np - 2] );
2736 }
2737
2738 m_points.push_back( pts_unique[np - 1] );
2739 m_shapes.push_back( shapes_unique[np - 1] );
2740
2741 assert( m_points.size() == m_shapes.size() );
2742
2743 return *this;
2744}
2745
2746bool SHAPE_LINE_CHAIN::OffsetLine( int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError,
2747 SHAPE_LINE_CHAIN& aLeft, SHAPE_LINE_CHAIN& aRight,
2748 bool aSimplify ) const
2749{
2750 if( PointCount() < 2 )
2751 return false;
2752
2753 SHAPE_POLY_SET poly;
2754 poly.OffsetLineChain( *this, aAmount, aCornerStrategy, aMaxError, aSimplify );
2755
2756 if( poly.OutlineCount() != 1 )
2757 return false;
2758
2759 if( poly.COutline( 0 ).PointCount() < 3 )
2760 return false;
2761
2762 if( poly.HasHoles() )
2763 return false;
2764
2765 SHAPE_LINE_CHAIN outline = poly.COutline( 0 );
2766
2767 wxASSERT( outline.IsClosed() );
2768
2769 const VECTOR2I& start = CPoint( 0 );
2770 const VECTOR2I& end = CPoint( -1 );
2771
2772 outline.Split( start, true );
2773 outline.Split( end, true );
2774
2775 const int idA = outline.Find( start );
2776 const int idB = outline.Find( end );
2777
2778 if( idA == -1 || idB == -1 )
2779 return false;
2780
2781 aLeft.Clear();
2782 aRight.Clear();
2783
2784 for( int i = idA;; )
2785 {
2786 aLeft.Append( outline.CPoint( i ) );
2787
2788 i = ( i + 1 ) % outline.PointCount();
2789
2790 if( i == idB )
2791 {
2792 aLeft.Append( outline.CPoint( i ) );
2793 break;
2794 }
2795
2796 if( i == idA )
2797 return false;
2798 }
2799
2800 if( aLeft.PointCount() < 2 )
2801 return false;
2802
2803 for( int i = idB;; )
2804 {
2805 aRight.Append( outline.CPoint( i ) );
2806
2807 i = ( i + 1 ) % outline.PointCount();
2808
2809 if( i == idA )
2810 {
2811 aRight.Append( outline.CPoint( i ) );
2812 break;
2813 }
2814
2815 if( i == idB )
2816 return false;
2817 }
2818
2819 if( aRight.PointCount() < 2 )
2820 return false;
2821
2822 if( aLeft.CPoint( 0 ) != start )
2823 {
2824 aLeft = aLeft.Reverse();
2825 wxASSERT( aLeft.CPoint( 0 ) == start );
2826 }
2827
2828 if( aRight.CPoint( 0 ) != start )
2829 {
2830 aRight = aRight.Reverse();
2831 wxASSERT( aRight.CPoint( 0 ) == start );
2832 }
2833
2834 SEG base( CPoint( 0 ), CPoint( 1 ) );
2835 int sideLeft = base.Side( aLeft.CPoint( 1 ) );
2836 int sideRight = base.Side( aRight.CPoint( 1 ) );
2837
2838 if( sideLeft == 0 || sideRight == 0 )
2839 return false;
2840
2841 if( sideLeft == sideRight )
2842 return false;
2843
2844 if( sideLeft > 0 && sideRight < 0 )
2845 std::swap( aLeft, aRight );
2846
2847 if( aLeft.PointCount() < 4 )
2848 return false;
2849
2850 if( aRight.PointCount() < 4 )
2851 return false;
2852
2853 aLeft.Remove( 0 );
2854 aLeft.Remove( aLeft.PointCount() - 1 );
2855
2856 aRight.Remove( 0 );
2857 aRight.Remove( aRight.PointCount() - 1 );
2858
2859 return true;
2860}
2861
2862
2864 ERROR_LOC aErrorLoc ) const
2865{
2866 aBuffer.AddOutline( *this );
2867}
2868
2869
2871 m_point( aPoint ),
2872 m_finished( false ),
2873 m_state( 0 ),
2874 m_count( 0 )
2875{
2876}
2877
2878
2880 const VECTOR2I& ip, const VECTOR2I& ipNext )
2881{
2882 if( ipNext.y == m_point.y )
2883 {
2884 if( ( ipNext.x == m_point.x )
2885 || ( ip.y == m_point.y && ( ( ipNext.x > m_point.x ) == ( ip.x < m_point.x ) ) ) )
2886 {
2887 m_finished = true;
2888 m_state = -1;
2889 return false;
2890 }
2891 }
2892
2893 if( ( ip.y < m_point.y ) != ( ipNext.y < m_point.y ) )
2894 {
2895 if( ip.x >= m_point.x )
2896 {
2897 if( ipNext.x > m_point.x )
2898 {
2899 m_state = 1 - m_state;
2900 }
2901 else
2902 {
2903 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2904 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2905
2906 if( !d )
2907 {
2908 m_finished = true;
2909 m_state = -1;
2910 return false;
2911 }
2912
2913 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2914 m_state = 1 - m_state;
2915 }
2916 }
2917 else
2918 {
2919 if( ipNext.x > m_point.x )
2920 {
2921 double d = (double) ( ip.x - m_point.x ) * ( ipNext.y - m_point.y )
2922 - (double) ( ipNext.x - m_point.x ) * ( ip.y - m_point.y );
2923
2924 if( !d )
2925 {
2926 m_finished = true;
2927 m_state = -1;
2928 return false;
2929 }
2930
2931 if( ( d > 0 ) == ( ipNext.y > ip.y ) )
2932 m_state = 1 - m_state;
2933 }
2934 }
2935 }
2936
2937 return true;
2938}
2939
2940
2942{
2943 if( !m_count )
2944 {
2945 m_lastPoint = aPolyline.CPoint( 0 );
2946 m_firstPoint = aPolyline.CPoint( 0 );
2947 }
2948
2949 m_count += aPolyline.PointCount();
2950
2951 for( int i = 1; i < aPolyline.PointCount(); i++ )
2952 {
2953 auto p = aPolyline.CPoint( i );
2954
2955 if( !processVertex( m_lastPoint, p ) )
2956 return;
2957
2958 m_lastPoint = p;
2959 }
2960
2961}
2962
2963
2965{
2966 processVertex( m_lastPoint, m_firstPoint );
2967 return m_state > 0;
2968}
2969
2970
2971bool SHAPE_LINE_CHAIN::IsSharedPt( size_t aIndex ) const
2972{
2973 return aIndex < m_shapes.size()
2974 && m_shapes[aIndex].first != SHAPE_IS_PT
2975 && m_shapes[aIndex].second != SHAPE_IS_PT;
2976}
2977
2978
2979bool SHAPE_LINE_CHAIN::IsPtOnArc( size_t aPtIndex ) const
2980{
2981 return aPtIndex < m_shapes.size() && m_shapes[aPtIndex] != SHAPES_ARE_PT;
2982}
2983
2984
2985bool SHAPE_LINE_CHAIN::IsArcSegment( size_t aSegment ) const
2986{
2987 /*
2988 * A segment is part of an arc except in the special case of two arcs next to each other
2989 * but without a shared vertex. Here there is a segment between the end of the first arc
2990 * and the start of the second arc.
2991 */
2992 size_t nextIdx = aSegment + 1;
2993
2994 if( nextIdx > m_shapes.size() - 1 )
2995 {
2996 if( nextIdx == m_shapes.size() && m_closed && IsSharedPt( 0 ) )
2997 nextIdx = 0; // segment between end point and first point
2998 else
2999 return false;
3000 }
3001
3002 return ( IsPtOnArc( aSegment )
3003 && ( ArcIndex( aSegment ) == m_shapes[nextIdx].first ) );
3004}
3005
3006
3007bool SHAPE_LINE_CHAIN::IsArcStart( size_t aIndex ) const
3008{
3009 if( !IsArcSegment( aIndex ) ) // also does bound checking
3010 return false;
3011
3012 if( IsSharedPt( aIndex ) )
3013 return true;
3014
3015 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
3016
3017 return arc.GetP0() == m_points[aIndex];
3018}
3019
3020
3021bool SHAPE_LINE_CHAIN::IsArcEnd( size_t aIndex ) const
3022{
3023 size_t prevIndex = aIndex - 1;
3024
3025 if( aIndex == 0 )
3026 prevIndex = m_points.size() - 1;
3027 else if( aIndex > m_points.size() -1 )
3028 return false; // invalid index requested
3029
3030 if( !IsArcSegment( prevIndex ) )
3031 return false;
3032
3033 if( IsSharedPt( aIndex ) )
3034 return true;
3035
3036 const SHAPE_ARC& arc = Arc( ArcIndex( aIndex ) );
3037
3038 return arc.GetP1() == m_points[aIndex];
3039}
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
std::vector< VECTOR2I > Intersect(const CIRCLE &aCircle) const
Compute the intersection points between this circle and aCircle.
Definition: circle.cpp:221
Definition: seg.h:42
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:350
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp: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 BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
std::vector< VECTOR2I >::const_iterator point_citer
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
static const ssize_t SHAPE_IS_PT
bool OffsetLine(int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, SHAPE_LINE_CHAIN &aLeft, SHAPE_LINE_CHAIN &aRight, bool aSimplify=false) const
Creates line chains aLeft and aRight offset to this line chain.
Represent a set of closed polygons.
bool HasHoles() const
Return true if the polygon set has any holes.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
void OffsetLineChain(const SHAPE_LINE_CHAIN &aLine, int aAmount, CORNER_STRATEGY aCornerStrategy, int aMaxError, bool aSimplify)
Perform offsetting of a line chain.
int OutlineCount() const
Return the number of outlines in the set.
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
An abstract shape on 2D plane.
Definition: shape.h:126
VECTOR2I::extended_type ecoord
Definition: shape.h:284
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:76
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h: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)
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