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