KiCad PCB EDA Suite
Loading...
Searching...
No Matches
pns_line.cpp
Go to the documentation of this file.
1/*
2 * KiRouter - a push-and-(sometimes-)shove PCB router
3 *
4 * Copyright (C) 2013-2017 CERN
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * Author: Tomasz Wlostowski <[email protected]>
7 *
8 * This program is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation, either version 3 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program. If not, see <http://www.gnu.org/licenses/>.
20 */
21
22#include <optional>
23
24#include <math/box2.h>
25#include <math/vector2d.h>
26
27#include "pns_line.h"
28#include "pns_node.h"
29#include "pns_via.h"
30#include "pns_utils.h"
31#include "pns_router.h"
32#include "pns_debug_decorator.h"
33
34#include <geometry/shape_rect.h>
35
36namespace PNS {
37
38LINE::LINE( const LINE& aOther ) :
39 LINK_HOLDER( aOther ),
40 m_line( aOther.m_line ),
41 m_width( aOther.m_width ),
42 m_snapThreshhold( aOther.m_snapThreshhold )
43{
44 m_net = aOther.m_net;
45 m_movable = aOther.m_movable;
46 m_layers = aOther.m_layers;
47
48 m_via = nullptr;
49
50 if( aOther.m_via )
51 {
52 if( aOther.m_via->BelongsTo( &aOther ) )
53 {
54 m_via = aOther.m_via->Clone();
55 m_via->SetOwner( this );
56 m_via->SetNet( m_net );
57 }
58 else
59 {
60 m_via = aOther.m_via;
61 }
62 }
63
64 m_marker = aOther.m_marker;
65 m_rank = aOther.m_rank;
67
68 copyLinks( &aOther );
69}
70
71
73{
74 if( m_via && m_via->BelongsTo( this ) )
75 delete m_via;
76}
77
78
79LINE& LINE::operator=( const LINE& aOther )
80{
81 m_parent = aOther.m_parent;
83
84 m_line = aOther.m_line;
85 m_width = aOther.m_width;
86 m_net = aOther.m_net;
87 m_movable = aOther.m_movable;
88 m_layers = aOther.m_layers;
89
90 m_via = nullptr;
91
92 if( aOther.m_via )
93 {
94 if( aOther.m_via->BelongsTo( &aOther ) )
95 {
96 m_via = aOther.m_via->Clone();
97 m_via->SetOwner( this );
98 m_via->SetNet( m_net );
99 }
100 else
101 {
102 m_via = aOther.m_via;
103 }
104 }
105
106 m_marker = aOther.m_marker;
107 m_rank = aOther.m_rank;
108 m_routable = aOther.m_routable;
109 m_owner = aOther.m_owner;
112
113 copyLinks( &aOther );
114
115 return *this;
116}
117
118
120{
121 LINE* l = new LINE( *this );
122
123 return l;
124}
125
126
127void LINE::Mark( int aMarker ) const
128{
129 m_marker = aMarker;
130
131 for( const LINKED_ITEM* s : m_links )
132 s->Mark( aMarker );
133
134}
135
136
137void LINE::Unmark( int aMarker ) const
138{
139 for( const LINKED_ITEM* s : m_links )
140 s->Unmark( aMarker );
141
142 m_marker = 0;
143}
144
145
146int LINE::Marker() const
147{
148 int marker = m_marker;
149
150 for( LINKED_ITEM* s : m_links )
151 marker |= s->Marker();
152
153 return marker;
154}
155
156
158{
159 SEGMENT* s = new SEGMENT( *this );
160
161 s->m_seg = m_seg;
162 s->m_net = m_net;
163 s->m_layers = m_layers;
164 s->m_marker = m_marker;
165 s->m_rank = m_rank;
166
167 return s;
168}
169
170
171int LINE::CountCorners( int aAngles ) const
172{
173 int count = 0;
174
175 for( int i = 0; i < m_line.SegmentCount() - 1; i++ )
176 {
177 const SEG seg1 = m_line.CSegment( i );
178 const SEG seg2 = m_line.CSegment( i + 1 );
179
180 const DIRECTION_45 dir1( seg1 );
181 const DIRECTION_45 dir2( seg2 );
182
183 DIRECTION_45::AngleType a = dir1.Angle( dir2 );
184
185 if( a & aAngles )
186 count++;
187 }
188
189 return count;
190}
191
192static int areNeighbours( int x, int y, int max = 0 )
193{
194 if( x > 0 && x - 1 == y )
195 return true;
196
197 if( x < max - 1 && x + 1 == y )
198 return true;
199
200 return false;
201}
202
203#ifdef TOM_EXTRA_DEBUG
204SHAPE_LINE_CHAIN g_pnew, g_hnew;
205#endif
206
207bool LINE::Walkaround( const SHAPE_LINE_CHAIN& aObstacle, SHAPE_LINE_CHAIN& aPath, bool aCw ) const
208{
209 const SHAPE_LINE_CHAIN& line( CLine() );
210
211 if( line.SegmentCount() < 1 )
212 {
213 return false;
214 }
215
216 const VECTOR2I pFirst = line.CPoint(0);
217
218 bool inFirst = aObstacle.PointInside( pFirst ) && !aObstacle.PointOnEdge( pFirst );
219
220 // We can't really walk around if the beginning of the path lies inside the obstacle hull.
221 // Double check if it's not on the hull itself as this triggers many unroutable corner cases.
222 if( inFirst )
223 {
224 return false;
225 }
226
227 enum VERTEX_TYPE { INSIDE = 0, OUTSIDE, ON_EDGE };
228
229 // Represents an entry in directed graph of hull/path vertices. Scanning this graph
230 // starting from the path's first point results (if possible) with a correct walkaround path
231 struct VERTEX
232 {
233 // vertex classification (inside/outside/exactly on the hull)
234 VERTEX_TYPE type;
235 // true = vertex coming from the hull primitive
236 bool isHull;
237 // position
238 VECTOR2I pos;
239 // list of neighboring vertices
240 std::vector<VERTEX*> neighbours;
241 // index of this vertex in path (pnew)
242 int indexp = -1;
243 // index of this vertex in the hull (hnew)
244 int indexh = -1;
245 // visited indicator (for BFS search)
246 bool visited = false;
247 };
248
250
251 HullIntersection( aObstacle, line, ips );
252
253 SHAPE_LINE_CHAIN pnew( CLine() ), hnew( aObstacle );
254
255 std::vector<VERTEX> vts;
256
257 auto findVertex =
258 [&]( const VECTOR2I& pos ) -> VERTEX*
259 {
260 for( VERTEX& v : vts )
261 {
262 if( v.pos == pos )
263 return &v;
264 }
265
266 return nullptr;
267 };
268
269 // corner case for loopy tracks: insert the end loop point back into the hull
270 if( const std::optional<SHAPE_LINE_CHAIN::INTERSECTION> isect = pnew.SelfIntersecting() )
271 {
272 if( isect->p != pnew.CLastPoint() )
273 pnew.Split( isect->p );
274 }
275
276 // insert all intersections found into the new hull/path SLCs
277 for( SHAPE_LINE_CHAIN::INTERSECTION& ip : ips )
278 {
279 if( pnew.Find( ip.p, 1 ) < 0)
280 pnew.Split(ip.p);
281
282 if( hnew.Find( ip.p, 1 ) < 0 )
283 hnew.Split(ip.p);
284 }
285
286 for( int i = 0; i < pnew.PointCount(); i++ )
287 {
288 const VECTOR2I& p = pnew.CPoint( i );
289 bool onEdge = hnew.PointOnEdge( p );
290
291 if ( !onEdge )
292 continue;
293
294 int idx = hnew.Find( p );
295
296 if(idx < 0 )
297 hnew.Split( p );
298 }
299
300 #ifdef TOM_EXTRA_DEBUG
301 for( auto& ip : ips )
302 {
303 printf("Chk: %d %d\n", pnew.Find( ip.p ), hnew.Find(ip.p) );
304 }
305 #endif
306
307 // we assume the default orientation of the hulls is clockwise, so just reverse the vertex
308 // order if the caller wants a counter-clockwise walkaround
309 if ( !aCw )
310 hnew = hnew.Reverse();
311
312 vts.reserve( 2 * ( hnew.PointCount() + pnew.PointCount() ) );
313
314 // create a graph of hull/path vertices and classify them (inside/on edge/outside the hull)
315 for( int i = 0; i < pnew.PointCount(); i++ )
316 {
317 const VECTOR2I& p = pnew.CPoint(i);
318 bool onEdge = hnew.PointOnEdge( p );
319 bool inside = hnew.PointInside( p );
320
321 #ifdef TOM_EXTRA_DEBUG
322 printf("pnew %d inside %d onedge %d\n", i, !!inside, !!onEdge );
323 #endif
324
325 VERTEX v;
326
327 v.indexp = i;
328 v.isHull = false;
329 v.pos = p;
330 v.type = inside && !onEdge ? INSIDE : onEdge ? ON_EDGE : OUTSIDE;
331 vts.push_back( v );
332 }
333
334 #ifdef TOM_EXTRA_DEBUG
335 g_pnew = pnew;
336 g_hnew = hnew;
337 #endif
338
339 // each path vertex neighbour list points for sure to the next vertex in the path
340 for( int i = 0; i < pnew.PointCount() - 1; i++ )
341 {
342 vts[i].neighbours.push_back( &vts[ i+1 ] );
343 }
344
345 // each path vertex neighbour list points for sure to the next vertex in the path
346 for( int i = 1; i < pnew.PointCount() ; i++ )
347 {
348 vts[i].neighbours.push_back( &vts[ i-1 ] );
349 }
350
351 // insert hull vertices into the graph
352 for( int i = 0; i < hnew.PointCount(); i++ )
353 {
354 const VECTOR2I& hp = hnew.CPoint( i );
355 VERTEX* vn = findVertex( hp );
356
357 // if vertex already present (it's very likely that in recursive shoving hull and path vertices will overlap)
358 // just mark it as a path vertex that also belongs to the hull
359 if( vn )
360 {
361 vn->isHull = true;
362 vn->indexh = i;
363 }
364 else // new hull vertex
365 {
366 VERTEX v;
367 v.pos = hp;
368 v.type = ON_EDGE;
369 v.indexh = i;
370 v.isHull = true;
371 vts.push_back( v );
372 }
373 }
374
375 // go around the hull and fix up the neighbour link lists
376 for( int i = 0; i < hnew.PointCount(); i++ )
377 {
378 VERTEX* vc = findVertex( hnew.CPoint( i ) );
379 VERTEX* vnext = findVertex( hnew.CPoint( i+1 ) );
380
381 if( vc && vnext )
382 vc->neighbours.push_back( vnext );
383 }
384
385 // In the case that the initial path ends *inside* the current obstacle (i.e. the mouse cursor
386 // is somewhere inside the hull for the current obstacle) we want to end the walkaround at the
387 // point closest to the cursor
388 bool inLast = aObstacle.PointInside( CLastPoint() ) && !aObstacle.PointOnEdge( CLastPoint() );
389 bool appendV = true;
390 int lastDst = INT_MAX;
391
392 int i = 0;
393#ifdef TOM_EXTRA_DEBUG
394 for( VERTEX* &v: vts )
395 {
396 if( v.indexh < 0 && v.type == ON_EDGE )
397 v.type = OUTSIDE; // hack
398
399 printf("V %d pos %d %d ip %d ih %d type %d\n", i++, v.pos.x, v.pos.y, v.indexp, v.indexh, v.type );
400 }
401#endif
402 // vts[0] = start point
403 VERTEX* v = &vts[0];
404 VERTEX* v_prev = nullptr;
406
407 int iterLimit = 1000;
408
409 // keep scanning the graph until we reach the end point of the path
410 while( v->indexp != ( pnew.PointCount() - 1 ) )
411 {
412 iterLimit--;
413
414 // I'm not 100% sure this algorithm doesn't have bugs that may cause it to freeze,
415 // so here's a temporary iteration limit
416 if( iterLimit == 0 )
417 return false;
418
419 if( v->visited )
420 {
421 // loop found? stop walking
422 break;
423 }
424
425#ifdef TOM_EXTRA_DEBUG
426 printf("---\nvisit ip %d ih %d type %d outs %d neig %d\n", v->indexp, v->indexh, v->type, out.PointCount(), v->neighbours.size() );
427#endif
428 out.Append( v->pos );
429
430 VERTEX* v_next = nullptr;
431
432 if( v->type == OUTSIDE )
433 {
434 // current vertex is outside? first look for any vertex further down the path
435 // that is not inside the hull
436 out.Append( v->pos );
437 VERTEX* v_next_fallback = nullptr;
438
439 for( VERTEX* vn : v->neighbours )
440 {
441 if( areNeighbours( vn->indexp , v->indexp, pnew.PointCount() )
442 && vn->type != INSIDE )
443 {
444 if( !vn->visited )
445 {
446 v_next = vn;
447 break;
448 }
449 else if( vn != v_prev )
450 {
451 v_next_fallback = vn;
452 }
453 }
454 }
455
456 if( !v_next )
457 v_next = v_next_fallback;
458
459 // such a vertex must always be present, if not, bummer.
460 if( !v_next )
461 {
462 #ifdef TOM_EXTRA_DEBUG
463 printf("FAIL VN fallback %p\n", v_next_fallback );
464 #endif
465 return false;
466 }
467 }
468 else if( v->type == ON_EDGE )
469 {
470 // look first for the first vertex outside the hull
471 for( VERTEX* vn : v->neighbours )
472 {
473#ifdef TOM_EXTRA_DEBUG
474 printf( "- OUT scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
475#endif
476
477 if( vn->type == OUTSIDE && !vn->visited )
478 {
479 v_next = vn;
480 break;
481 }
482 }
483
484 // no outside vertices found? continue traversing the hull
485 if( !v_next )
486 {
487 for( VERTEX* vn : v->neighbours )
488 {
489 #ifdef TOM_EXTRA_DEBUG
490 printf("- scan ip %d ih %d type %d\n", vn->indexp, vn->indexh, vn->type );
491 #endif
492 if( vn->type == ON_EDGE && !vn->isHull &&
493 areNeighbours( vn->indexp, v->indexp, pnew.PointCount() ) &&
494 ( vn->indexh == ( ( v->indexh + 1 ) % hnew.PointCount() ) ) )
495 {
496 v_next = vn;
497 break;
498 }
499 }
500 }
501
502 // still nothing found? try to find the next (index-wise) point on the hull. I guess
503 // we should never reach this part of the code, but who really knows?
504 if( !v_next )
505 {
506#ifdef TOM_EXTRA_DEBUG
507 printf("still no v_next\n");
508#endif
509 for( VERTEX* vn : v->neighbours )
510 {
511 if( vn->type == ON_EDGE )
512 {
513 if( vn->indexh == ( ( v->indexh + 1 ) % hnew.PointCount() ) )
514 {
515 v_next = vn;
516 break;
517 }
518 }
519 }
520
521 if( v_next )
522 {
523 for( VERTEX &vt : vts )
524 {
525 if( vt.isHull )
526 vt.visited = false;
527 }
528 }
529
530#ifdef TOM_EXTRA_DEBUG
531 printf("v_next %p\n", v_next);
532#endif
533
534 // Did we get the next hull point but the end of the line is inside? Instead of walking
535 // around the hull some more (which will just end up taking us back to the start), lets
536 // just project the normal of the endpoint onto this next segment and call it quits.
537 if( inLast && v_next )
538 {
539 int d = ( v_next->pos - CLastPoint() ).SquaredEuclideanNorm();
540
541 if( d < lastDst )
542 {
543 lastDst = d;
544 }
545 else
546 {
547 VECTOR2I proj = SEG( v->pos, v_next->pos ).NearestPoint( CLastPoint() );
548 out.Append( proj );
549 appendV = false;
550 break;
551 }
552 }
553 }
554 }
555
556 v->visited = true;
557 v_prev = v;
558 v = v_next;
559
560 if( !v )
561 return false;
562 }
563
564 if( appendV )
565 out.Append( v->pos );
566
567 aPath = std::move( out );
568 return true;
569}
570
571
572const SHAPE_LINE_CHAIN SEGMENT::Hull( int aClearance, int aWalkaroundThickness, int aLayer ) const
573{
574 /*DEBUG_DECORATOR* debugDecorator = ROUTER::GetInstance()->GetInterface()->GetDebugDecorator();
575
576 PNS_DBG( debugDecorator, Message, wxString::Format( wxT( "seghull %d %d" ), aWalkaroundThickness, aClearance ) );
577 PNS_DBG(debugDecorator, AddShape, &m_seg, RED, 0, wxT("theseg") );
578 */
579
580 return SegmentHull( m_seg, aClearance, aWalkaroundThickness );
581}
582
584{
585 const int IterationLimit = 5;
586 int i;
587 LINE l( *this );
588
589 for( i = 0; i < IterationLimit; i++ )
590 {
591 NODE::OPT_OBSTACLE obs = aNode->NearestObstacle( &l );
592
593 if( obs )
594 {
595 l.RemoveVia();
596 VECTOR2I collisionPoint = obs->m_ipFirst;
597 int segIdx = l.Line().NearestSegment( collisionPoint );
598
599 if( l.Line().IsArcSegment( segIdx ) )
600 {
601 // Don't clip at arcs, start again
602 l.Line().Clear();
603 }
604 else
605 {
606 SEG nearestSegment = l.Line().CSegment( segIdx );
607 VECTOR2I nearestPt = nearestSegment.NearestPoint( collisionPoint );
608 int p = l.Line().Split( nearestPt );
609 l.Line().Remove( p + 1, -1 );
610 }
611 }
612 else
613 {
614 break;
615 }
616 }
617
618 if( i == IterationLimit )
619 l.Line().Clear();
620
621 return l;
622}
623
624
625
626SHAPE_LINE_CHAIN dragCornerInternal( const SHAPE_LINE_CHAIN& aOrigin, const VECTOR2I& aP, DIRECTION_45 aPreferredEndingDirection = DIRECTION_45() )
627{
628 std::optional<SHAPE_LINE_CHAIN> picked;
629 int i;
630 int d = 2;
631
632 wxASSERT( aOrigin.PointCount() > 0 );
633
634 if( aOrigin.PointCount() == 1 )
635 {
636 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP );
637 }
638 else if( aOrigin.SegmentCount() == 1 )
639 {
640 DIRECTION_45 dir( aOrigin.CPoint( 0 ) - aOrigin.CPoint( 1 ) );
641
642 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
643 }
644
645
646 //if( aOrigin.CSegment( -1 ).Length() > 100000 * 30 ) // fixme: constant/parameter?
647 d = 1;
648
649 for( i = aOrigin.SegmentCount() - d; i >= 0; i-- )
650 {
651 DIRECTION_45 d_start( aOrigin.CSegment( i ) );
652 const VECTOR2I& p_start = aOrigin.CPoint( i );
653 SHAPE_LINE_CHAIN paths[2];
654 DIRECTION_45 dirs[2];
655 DIRECTION_45 d_prev = ( i > 0 ? DIRECTION_45( aOrigin.CSegment( i-1 ) )
656 : DIRECTION_45() );
657 int dirCount = 0;
658
659 for( int j = 0; j < 2; j++ )
660 {
661 paths[j] = d_start.BuildInitialTrace( p_start, aP, j );
662
663 if( paths[j].SegmentCount() < 1 )
664 continue;
665
666 assert( dirCount < int( sizeof( dirs ) / sizeof( dirs[0] ) ) );
667
668 dirs[dirCount] = DIRECTION_45( paths[j].CSegment( 0 ) );
669 ++dirCount;
670 }
671
672 if( aPreferredEndingDirection != DIRECTION_45::UNDEFINED )
673 {
674 for( int j = 0; j < dirCount; j++ )
675 {
676 DIRECTION_45 endingDir( paths[j].CSegment(-1) );
677 if( endingDir == aPreferredEndingDirection )
678 {
679 picked = paths[j];
680 break;
681 }
682 }
683 }
684
685 if( !picked )
686 {
687 for( int j = 0; j < dirCount; j++ )
688 {
689 if( dirs[j] == d_start )
690 {
691 picked = paths[j];
692 break;
693 }
694 }
695 }
696
697 if( picked )
698 break;
699
700 for( int j = 0; j < dirCount; j++ )
701 {
702 if( dirs[j].IsObtuse( d_prev ) )
703 {
704 picked = paths[j];
705 break;
706 }
707 }
708
709 if( picked )
710 break;
711 }
712
713 if( picked )
714 {
715 SHAPE_LINE_CHAIN path = aOrigin.Slice( 0, i );
716 path.Append( *picked );
717
718 return path;
719 }
720
721 DIRECTION_45 dir( aOrigin.CLastPoint() - aOrigin.CPoints()[ aOrigin.PointCount() - 2 ] );
722
723 return DIRECTION_45().BuildInitialTrace( aOrigin.CPoint( 0 ), aP, dir.IsDiagonal() );
724}
725
726
727void LINE::dragCorner45( const VECTOR2I& aP, int aIndex, DIRECTION_45 aPreferredEndingDirection )
728{
730
731 int width = m_line.Width();
732 VECTOR2I snapped = snapDraggedCorner( m_line, aP, aIndex );
733
734 if( aIndex == 0 )
735 {
736 path = dragCornerInternal( m_line.Reverse(), snapped, aPreferredEndingDirection ).Reverse();
737 }
738 else if( aIndex == m_line.SegmentCount() )
739 {
740 path = dragCornerInternal( m_line, snapped, aPreferredEndingDirection );
741 }
742 else
743 {
744 // Are we next to an arc? Insert a new point so we slice correctly
745 if( m_line.IsPtOnArc( static_cast<size_t>( aIndex ) + 1 ) )
746 m_line.Insert( aIndex + 1, m_line.CPoint( aIndex + 1 ) );
747
748 // fixme: awkward behaviour for "outwards" drags
749 path = dragCornerInternal( m_line.Slice( 0, aIndex ), snapped, aPreferredEndingDirection );
750 SHAPE_LINE_CHAIN path_rev =
751 dragCornerInternal( m_line.Slice( aIndex, -1 ).Reverse(), snapped, aPreferredEndingDirection ).Reverse();
752 path.Append( path_rev );
753 }
754
755 path.Simplify();
756 path.SetWidth( width );
757 m_line = std::move( path );
758}
759
760
761void LINE::dragCornerFree( const VECTOR2I& aP, int aIndex )
762{
763 ssize_t idx = static_cast<ssize_t>( aIndex );
764 ssize_t numpts = static_cast<ssize_t>( m_line.PointCount() );
765
766 // If we're asked to drag the end of an arc, insert a new vertex to drag instead
767 if( m_line.IsPtOnArc( idx ) )
768 {
769 if( idx == 0 || ( idx > 0 && !m_line.IsPtOnArc( idx - 1 ) ) )
770 {
771 m_line.Insert( idx, m_line.GetPoint( idx ) );
772 }
773 else if( ( idx == numpts - 1 ) || ( idx < numpts - 1 && !m_line.IsArcSegment( idx ) ) )
774 {
775 idx++;
776 m_line.Insert( idx, m_line.GetPoint( idx ) );
777 }
778 else
779 {
780 wxASSERT_MSG( false, wxT( "Attempt to dragCornerFree in the middle of an arc!" ) );
781 }
782 }
783
784 m_line.SetPoint( idx, aP );
786}
787
788void LINE::DragCorner( const VECTOR2I& aP, int aIndex, bool aFreeAngle, DIRECTION_45 aPreferredEndingDirection )
789{
790 wxCHECK_RET( aIndex >= 0, wxT( "Negative index passed to LINE::DragCorner" ) );
791
792 if( aFreeAngle )
793 {
794 dragCornerFree( aP, aIndex );
795 }
796 else
797 {
798 dragCorner45( aP, aIndex, aPreferredEndingDirection );
799 }
800}
801
802void LINE::DragSegment( const VECTOR2I& aP, int aIndex, bool aFreeAngle )
803{
804 if( aFreeAngle )
805 {
806 assert( false );
807 }
808 else
809 {
810 dragSegment45( aP, aIndex );
811 }
812}
813
815 const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
816{
817 int s_start = std::max( aIndex - 2, 0 );
818 int s_end = std::min( aIndex + 2, aPath.SegmentCount() - 1 );
819
820 int i, j;
821 int best_dist = INT_MAX;
822 VECTOR2I best_snap = aP;
823
824 if( m_snapThreshhold <= 0 )
825 return aP;
826
827 for( i = s_start; i <= s_end; i++ )
828 {
829 const SEG& a = aPath.CSegment( i );
830
831 for( j = s_start; j < i; j++ )
832 {
833 const SEG& b = aPath.CSegment( j );
834
835 if( !( DIRECTION_45( a ).IsObtuse( DIRECTION_45( b ) ) ) )
836 continue;
837
838 OPT_VECTOR2I ip = a.IntersectLines( b );
839
840 if( ip )
841 {
842 int dist = ( *ip - aP ).EuclideanNorm();
843
844 if( dist < m_snapThreshhold && dist < best_dist )
845 {
846 best_dist = dist;
847 best_snap = *ip;
848 }
849 }
850 }
851 }
852
853 return best_snap;
854}
855
857 const SHAPE_LINE_CHAIN& aPath, const VECTOR2I& aP, int aIndex ) const
858{
859 VECTOR2I snap_p[2];
860 DIRECTION_45 dragDir( aPath.CSegment( aIndex ) );
861 int snap_d[2] = { -1, -1 };
862
863 if( m_snapThreshhold == 0 )
864 return aP;
865
866 if( aIndex >= 2 )
867 {
868 SEG s = aPath.CSegment( aIndex - 2 );
869
870 if( DIRECTION_45( s ) == dragDir )
871 snap_d[0] = s.LineDistance( aP );
872
873 snap_p[0] = s.A;
874 }
875
876 if( aIndex < aPath.SegmentCount() - 2 )
877 {
878 SEG s = aPath.CSegment( aIndex + 2 );
879
880 if( DIRECTION_45( s ) == dragDir )
881 snap_d[1] = s.LineDistance( aP );
882
883 snap_p[1] = s.A;
884 }
885
886 VECTOR2I best = aP;
887 int minDist = INT_MAX;
888
889 for( int i = 0; i < 2; i++ )
890 {
891 if( snap_d[i] >= 0 && snap_d[i] < minDist && snap_d[i] <= m_snapThreshhold )
892 {
893 minDist = snap_d[i];
894 best = snap_p[i];
895 }
896 }
897
898 return best;
899}
900
901void LINE::dragSegment45( const VECTOR2I& aP, int aIndex )
902{
904 VECTOR2I target( aP );
905
906 wxASSERT( aIndex < m_line.PointCount() );
907
908 SEG guideA[2], guideB[2];
909 int index = aIndex;
910
911 target = snapToNeighbourSegments( path, aP, aIndex );
912
913 // We require a valid s_prev and s_next. If we are at the start or end of the line, we insert
914 // a new point at the start or end so there is a zero-length segment for prev or next (we will
915 // resize it as part of the drag operation). If we are next to an arc, we do this also, as we
916 // cannot drag away one of the arc's points.
917
918 if( index == 0 || path.IsPtOnArc( index ) )
919 {
920 path.Insert( index > 0 ? index + 1 : 0, path.CPoint( index ) );
921 index++;
922 }
923
924 if( index == path.SegmentCount() - 1 )
925 {
926 path.Insert( path.PointCount() - 1, path.CLastPoint() );
927 }
928 else if( path.IsPtOnArc( index + 1 ) )
929 {
930 path.Insert( index + 1, path.CPoint( index + 1 ) );
931 }
932
933 SEG dragged = path.CSegment( index );
934 DIRECTION_45 drag_dir( dragged );
935
936 SEG s_prev = path.CSegment( index - 1 );
937 SEG s_next = path.CSegment( index + 1 );
938
939 DIRECTION_45 dir_prev( s_prev );
940 DIRECTION_45 dir_next( s_next );
941
942 if( dir_prev == drag_dir )
943 {
944 dir_prev = dir_prev.Left();
945 path.Insert( index, path.CPoint( index ) );
946 index++;
947 }
948 else if( dir_prev == DIRECTION_45::UNDEFINED )
949 {
950 dir_prev = drag_dir.Left();
951 }
952
953 if( dir_next == drag_dir )
954 {
955 dir_next = dir_next.Right();
956 path.Insert( index + 1, path.CPoint( index + 1 ) );
957 }
958 else if( dir_next == DIRECTION_45::UNDEFINED )
959 {
960 dir_next = drag_dir.Right();
961 }
962
963 s_prev = path.CSegment( index - 1 );
964 s_next = path.CSegment( index + 1 );
965 dragged = path.CSegment( index );
966
967 if( aIndex == 0 )
968 {
969 guideA[0] = SEG( dragged.A, dragged.A + drag_dir.Right().ToVector() );
970 guideA[1] = SEG( dragged.A, dragged.A + drag_dir.Left().ToVector() );
971 }
972 else
973 {
974 if( dir_prev.Angle( drag_dir )
976 {
977 guideA[0] = SEG( s_prev.A, s_prev.A + drag_dir.Left().ToVector() );
978 guideA[1] = SEG( s_prev.A, s_prev.A + drag_dir.Right().ToVector() );
979 }
980 else
981 guideA[0] = guideA[1] = SEG( dragged.A, dragged.A + dir_prev.ToVector() );
982 }
983
984 if( aIndex == m_line.SegmentCount() - 1 )
985 {
986 guideB[0] = SEG( dragged.B, dragged.B + drag_dir.Right().ToVector() );
987 guideB[1] = SEG( dragged.B, dragged.B + drag_dir.Left().ToVector() );
988 }
989 else
990 {
991 if( dir_next.Angle( drag_dir )
993 {
994 guideB[0] = SEG( s_next.B, s_next.B + drag_dir.Left().ToVector() );
995 guideB[1] = SEG( s_next.B, s_next.B + drag_dir.Right().ToVector() );
996 }
997 else
998 guideB[0] = guideB[1] = SEG( dragged.B, dragged.B + dir_next.ToVector() );
999 }
1000
1001 SEG s_current( target, target + drag_dir.ToVector() );
1002
1003 int best_len = INT_MAX;
1004 SHAPE_LINE_CHAIN best;
1005
1006 for( int i = 0; i < 2; i++ )
1007 {
1008 for( int j = 0; j < 2; j++ )
1009 {
1010 OPT_VECTOR2I ip1 = s_current.IntersectLines( guideA[i] );
1011 OPT_VECTOR2I ip2 = s_current.IntersectLines( guideB[j] );
1012
1014
1015 if( !ip1 || !ip2 )
1016 continue;
1017
1018 SEG s1( s_prev.A, *ip1 );
1019 SEG s2( *ip1, *ip2 );
1020 SEG s3( *ip2, s_next.B );
1021
1022 OPT_VECTOR2I ip;
1023
1024 if( ( ip = s1.Intersect( s_next ) ) )
1025 {
1026 np.Append( s1.A );
1027 np.Append( *ip );
1028 np.Append( s_next.B );
1029 }
1030 else if( ( ip = s3.Intersect( s_prev ) ) )
1031 {
1032 np.Append( s_prev.A );
1033 np.Append( *ip );
1034 np.Append( s3.B );
1035 }
1036 else if( ( ip = s1.Intersect( s3 ) ) )
1037 {
1038 np.Append( s_prev.A );
1039 np.Append( *ip );
1040 np.Append( s_next.B );
1041 }
1042 else
1043 {
1044 np.Append( s_prev.A );
1045 np.Append( *ip1 );
1046 np.Append( *ip2 );
1047 np.Append( s_next.B );
1048 }
1049
1050 if( np.Length() < best_len )
1051 {
1052 best_len = np.Length();
1053 best = std::move( np );
1054 }
1055 }
1056 }
1057
1058 if( m_line.PointCount() == 1 )
1059 m_line = best;
1060 else if( aIndex == 0 )
1061 m_line.Replace( 0, 1, best );
1062 else if( aIndex == m_line.SegmentCount() - 1 )
1063 m_line.Replace( -2, -1, best );
1064 else
1065 m_line.Replace( aIndex, aIndex + 1, best );
1066
1067 m_line.Simplify();
1068}
1069
1070
1071bool LINE::CompareGeometry( const LINE& aOther )
1072{
1073 return m_line.CompareGeometry( aOther.m_line );
1074}
1075
1076
1078{
1079 m_line = m_line.Reverse();
1080
1081 std::reverse( m_links.begin(), m_links.end() );
1082}
1083
1084
1085void LINE::AppendVia( const VIA& aVia )
1086{
1087 if( m_line.PointCount() > 1 && aVia.Pos() == m_line.CPoint( 0 ) )
1088 {
1089 Reverse();
1090 }
1091
1092 m_via = aVia.Clone();
1093 m_via->SetOwner( this );
1094 m_via->SetNet( m_net );
1095}
1096
1097
1098void LINE::LinkVia( VIA* aVia )
1099{
1100 if( m_line.PointCount() > 1 && aVia->Pos() == m_line.CPoint( 0 ) )
1101 {
1102 Reverse();
1103 }
1104
1105 m_via = aVia;
1106 Link( aVia );
1107}
1108
1109
1110void LINE::SetRank( int aRank )
1111{
1112 m_rank = aRank;
1113
1114 for( auto s : m_links )
1115 s->SetRank( aRank );
1116
1117}
1118
1119
1120int LINE::Rank() const
1121{
1122 int min_rank = INT_MAX;
1123
1124 if( IsLinked() )
1125 {
1126 for( const LINKED_ITEM* item : m_links )
1127 min_rank = std::min( min_rank, item->Rank() );
1128 }
1129 else
1130 {
1131 min_rank = m_rank;
1132 }
1133
1134 int rank = ( min_rank == INT_MAX ) ? -1 : min_rank;
1135
1136 return rank;
1137}
1138
1139
1140void LINE::ClipVertexRange( int aStart, int aEnd )
1141{
1148 int firstLink = 0;
1149 int lastLink = std::max( 0, static_cast<int>( m_links.size() ) - 1 );
1150 int linkIdx = 0;
1151
1152 int numPoints = static_cast<int>( m_line.PointCount() );
1153
1154 for( int i = 0; i >= 0 && i < m_line.PointCount(); i = m_line.NextShape( i ) )
1155 {
1156 if( i <= aStart )
1157 firstLink = linkIdx;
1158
1159 if( i < 0 || i >= aEnd - 1 || linkIdx >= lastLink )
1160 {
1161 lastLink = linkIdx;
1162 break;
1163 }
1164
1165 linkIdx++;
1166 }
1167
1168 wxASSERT( lastLink >= firstLink );
1169
1170 m_line = m_line.Slice( aStart, aEnd );
1171
1172 if( IsLinked() )
1173 {
1174 wxASSERT( m_links.size() < INT_MAX );
1175 wxASSERT( static_cast<int>( m_links.size() ) >= ( lastLink - firstLink ) );
1176
1177 // Note: The range includes aEnd, but we have n-1 segments.
1178 std::rotate(
1179 m_links.begin(),
1180 m_links.begin() + firstLink,
1181 m_links.begin() + lastLink
1182 );
1183
1184 m_links.resize( lastLink - firstLink + 1 );
1185 }
1186}
1187
1188
1189bool LINE::HasLoops() const
1190{
1191 for( int i = 0; i < PointCount(); i++ )
1192 {
1193 for( int j = i + 2; j < PointCount(); j++ )
1194 {
1195 if( CPoint( i ) == CPoint( j ) )
1196 return true;
1197 }
1198 }
1199
1200 return false;
1201}
1202
1203
1204static void extendBox( BOX2I& aBox, bool& aDefined, const VECTOR2I& aP )
1205{
1206 if( aDefined )
1207 {
1208 aBox.Merge( aP );
1209 }
1210 else
1211 {
1212 aBox = BOX2I( aP, VECTOR2I( 0, 0 ) );
1213 aDefined = true;
1214 }
1215}
1216
1217
1218OPT_BOX2I LINE::ChangedArea( const LINE* aOther ) const
1219{
1220 BOX2I area;
1221 bool areaDefined = false;
1222
1223 int i_start = -1;
1224 int i_end_self = -1, i_end_other = -1;
1225
1226 SHAPE_LINE_CHAIN self( m_line );
1227 self.Simplify();
1228 SHAPE_LINE_CHAIN other( aOther->m_line );
1229 other.Simplify();
1230
1231 int np_self = self.PointCount();
1232 int np_other = other.PointCount();
1233
1234 int n = std::min( np_self, np_other );
1235
1236 for( int i = 0; i < n; i++ )
1237 {
1238 const VECTOR2I p1 = self.CPoint( i );
1239 const VECTOR2I p2 = other.CPoint( i );
1240
1241 if( p1 != p2 )
1242 {
1243 if( i != n - 1 )
1244 {
1245 SEG s = self.CSegment( i );
1246
1247 if( !s.Contains( p2 ) )
1248 {
1249 i_start = i;
1250 break;
1251 }
1252 }
1253 else
1254 {
1255 i_start = i;
1256 break;
1257 }
1258 }
1259 }
1260
1261 for( int i = 0; i < n; i++ )
1262 {
1263 const VECTOR2I p1 = self.CPoint( np_self - 1 - i );
1264 const VECTOR2I p2 = other.CPoint( np_other - 1 - i );
1265
1266 if( p1 != p2 )
1267 {
1268 i_end_self = np_self - 1 - i;
1269 i_end_other = np_other - 1 - i;
1270 break;
1271 }
1272 }
1273
1274 if( i_start < 0 )
1275 i_start = n;
1276
1277 if( i_end_self < 0 )
1278 i_end_self = np_self - 1;
1279
1280 if( i_end_other < 0 )
1281 i_end_other = np_other - 1;
1282
1283 for( int i = i_start; i <= i_end_self; i++ )
1284 extendBox( area, areaDefined, self.CPoint( i ) );
1285
1286 for( int i = i_start; i <= i_end_other; i++ )
1287 extendBox( area, areaDefined, other.CPoint( i ) );
1288
1289 if( areaDefined )
1290 {
1291 area.Inflate( std::max( Width(), aOther->Width() ) );
1292 return area;
1293 }
1294
1295 return OPT_BOX2I();
1296}
1297
1298
1300{
1301 for( const auto seg : m_links )
1302 {
1303 if( seg->Marker() & MK_LOCKED )
1304 return true;
1305 }
1306 return false;
1307}
1308
1309
1311{
1312 ClearLinks();
1313 RemoveVia();
1314 m_line.Clear();
1315}
1316
1317
1319{
1320 if( m_via )
1321 {
1322 if( ContainsLink( m_via ) )
1323 Unlink( m_via );
1324 if( m_via->BelongsTo( this ) )
1325 delete m_via;
1326 }
1327
1328 m_via = nullptr;
1329}
1330
1331
1332const std::string SEGMENT::Format( ) const
1333{
1334 std::stringstream ss;
1335 ss << ITEM::Format() << " ";
1336 ss << m_seg.Format( false );
1337 return ss.str();
1338}
1339
1340
1341int LINE::FindSegment( const SEGMENT* aSeg ) const
1342{
1343 for( int i = 0; i < m_line.SegmentCount(); i++)
1344 {
1345 const SEG&s = m_line.CSegment(i);
1346 if( s == aSeg->Seg() )
1347 return i;
1348 }
1349
1350 return -1;
1351}
1352
1353}
1354
1355
BOX2< VECTOR2I > BOX2I
Definition: box2.h:922
std::optional< BOX2I > OPT_BOX2I
Definition: box2.h:926
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:558
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:658
Represent route directions & corner angles in a 45-degree metric.
Definition: direction45.h:37
const SHAPE_LINE_CHAIN BuildInitialTrace(const VECTOR2I &aP0, const VECTOR2I &aP1, bool aStartDiagonal=false, CORNER_MODE aMode=CORNER_MODE::MITERED_45) const
Build a 2-segment line chain between points aP0 and aP1 and following 45-degree routing regime.
AngleType Angle(const DIRECTION_45 &aOther) const
Return the type of angle between directions (this) and aOther.
Definition: direction45.h:181
const DIRECTION_45 Left() const
Return the direction on the left side of this (i.e.
Definition: direction45.h:269
const VECTOR2I ToVector() const
Definition: direction45.h:287
AngleType
Represent kind of angle formed by vectors heading in two DIRECTION_45s.
Definition: direction45.h:78
bool IsDiagonal() const
Returns true if the direction is diagonal (e.g.
Definition: direction45.h:213
const DIRECTION_45 Right() const
Return the direction on the right side of this (i.e.
Definition: direction45.h:251
BOARD_ITEM * m_sourceItem
Definition: pns_item.h:319
virtual const std::string Format() const
Definition: pns_item.cpp:338
bool m_movable
Definition: pns_item.h:325
PNS_LAYER_RANGE m_layers
Definition: pns_item.h:323
bool m_routable
Definition: pns_item.h:329
void SetNet(NET_HANDLE aNet)
Definition: pns_item.h:209
NET_HANDLE m_net
Definition: pns_item.h:326
int m_marker
Definition: pns_item.h:327
BOARD_ITEM * m_parent
Definition: pns_item.h:317
int m_rank
Definition: pns_item.h:328
Represents a track on a PCB, connecting two non-trivial joints (that is, vias, pads,...
Definition: pns_line.h:62
VECTOR2I snapToNeighbourSegments(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:856
void ClipVertexRange(int aStart, int aEnd)
Return the number of corners of angles specified by mask aAngles.
Definition: pns_line.cpp:1140
int FindSegment(const SEGMENT *aSeg) const
Definition: pns_line.cpp:1341
const VECTOR2I & CPoint(int aIdx) const
Definition: pns_line.h:146
bool HasLoops() const
Definition: pns_line.cpp:1189
OPT_BOX2I ChangedArea(const LINE *aOther) const
Definition: pns_line.cpp:1218
bool HasLockedSegments() const
Definition: pns_line.cpp:1299
int Rank() const override
Definition: pns_line.cpp:1120
void dragCorner45(const VECTOR2I &aP, int aIndex, DIRECTION_45 aPreferredEndingDirection)
Definition: pns_line.cpp:727
const LINE ClipToNearestObstacle(NODE *aNode) const
Clip the line to a given range of vertices.
Definition: pns_line.cpp:583
VIA * m_via
Definition: pns_line.h:261
virtual void Mark(int aMarker) const override
Definition: pns_line.cpp:127
int m_width
Our width.
Definition: pns_line.h:256
bool CompareGeometry(const LINE &aOther)
Reverse the point/vertex order.
Definition: pns_line.cpp:1071
void LinkVia(VIA *aVia)
Definition: pns_line.cpp:1098
ITEM * m_blockingObstacle
For mark obstacle mode.
Definition: pns_line.h:262
const SHAPE_LINE_CHAIN & CLine() const
Definition: pns_line.h:138
VECTOR2I snapDraggedCorner(const SHAPE_LINE_CHAIN &aPath, const VECTOR2I &aP, int aIndex) const
Definition: pns_line.cpp:814
LINE & operator=(const LINE &aOther)
Definition: pns_line.cpp:79
void dragSegment45(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:901
const VECTOR2I & CLastPoint() const
Definition: pns_line.h:147
void RemoveVia()
Definition: pns_line.cpp:1318
int CountCorners(int aAngles) const
Definition: pns_line.cpp:171
void SetRank(int aRank) override
Definition: pns_line.cpp:1110
LINE()
Makes an empty line.
Definition: pns_line.h:67
SHAPE_LINE_CHAIN & Line()
Definition: pns_line.h:137
void DragCorner(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false, DIRECTION_45 aPreferredEndingDirection=DIRECTION_45())
Definition: pns_line.cpp:788
virtual int Marker() const override
Definition: pns_line.cpp:146
void AppendVia(const VIA &aVia)
Definition: pns_line.cpp:1085
virtual void Unmark(int aMarker=-1) const override
Definition: pns_line.cpp:137
int PointCount() const
Definition: pns_line.h:141
int m_snapThreshhold
Width to smooth out jagged segments.
Definition: pns_line.h:259
SHAPE_LINE_CHAIN m_line
The actual shape of the line.
Definition: pns_line.h:255
void DragSegment(const VECTOR2I &aP, int aIndex, bool aFreeAngle=false)
Definition: pns_line.cpp:802
bool Walkaround(SHAPE_LINE_CHAIN aObstacle, SHAPE_LINE_CHAIN &aPre, SHAPE_LINE_CHAIN &aWalk, SHAPE_LINE_CHAIN &aPost, bool aCw) const
Calculate a line tightly wrapping a convex hull of an obstacle object (aObstacle).
void Reverse()
Clip the line to the nearest obstacle, traversing from the line's start vertex (0).
Definition: pns_line.cpp:1077
void dragCornerFree(const VECTOR2I &aP, int aIndex)
Definition: pns_line.cpp:761
virtual LINE * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:119
int Width() const
Return true if the line is geometrically identical as line aOther.
Definition: pns_line.h:158
void Clear()
Definition: pns_line.cpp:1310
Keep the router "world" - i.e.
Definition: pns_node.h:232
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:242
OPT_OBSTACLE NearestObstacle(const LINE *aLine, const COLLISION_SEARCH_OPTIONS &aOpts=COLLISION_SEARCH_OPTIONS())
Follow the line in search of an obstacle that is nearest to the starting to the line's starting point...
Definition: pns_node.cpp:286
void SetOwner(const ITEM_OWNER *aOwner)
Set the node that owns this item.
Definition: pns_item.h:77
const ITEM_OWNER * m_owner
Definition: pns_item.h:88
bool BelongsTo(const ITEM_OWNER *aNode) const
Definition: pns_item.h:82
virtual const std::string Format() const override
Definition: pns_line.cpp:1332
const SEG & Seg() const
Definition: pns_segment.h:93
SEGMENT * Clone() const override
Return a deep copy of the item.
Definition: pns_line.cpp:157
const SHAPE_LINE_CHAIN Hull(int aClearance, int aWalkaroundThickness, int aLayer=-1) const override
Definition: pns_line.cpp:572
SHAPE_SEGMENT m_seg
Definition: pns_segment.h:138
const VECTOR2I & Pos() const
Definition: pns_via.h:184
VIA * Clone() const override
Return a deep copy of the item.
Definition: pns_via.cpp:244
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:719
VECTOR2I B
Definition: seg.h:50
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:606
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:439
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:220
bool Contains(const SEG &aSeg) const
Definition: seg.h:324
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Check if point aP lies on an edge or vertex of the line chain.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
const SHAPE_LINE_CHAIN Reverse() const
Reverse point order in the line chain.
bool IsPtOnArc(size_t aPtIndex) const
int Width() const
Get the current width of the segments in the chain.
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetPoint(int aIndex, const VECTOR2I &aPos)
Move a point to a specific location.
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.
int PointCount() const
Return the number of points (vertices) in this line chain.
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Replace points with indices in range [start_index, end_index] with a single point aP.
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
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.
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.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const VECTOR2I & CPoint(int aIndex) const
Return a reference to a given point in the line chain.
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.
const VECTOR2I & CLastPoint() const
Return the last point in the line chain.
void Remove(int aStartIndex, int aEndIndex)
Remove the range of points [start_index, end_index] from the line chain.
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 Insert(size_t aVertex, const VECTOR2I &aP)
std::vector< INTERSECTION > INTERSECTIONS
long long int Length() const
Return length of the line chain in Euclidean metric.
int Find(const VECTOR2I &aP, int aThreshold=0) const
Search for point aP.
const std::vector< VECTOR2I > & CPoints() const
virtual const std::string Format(bool aCplusPlus=true) const override
Push and Shove diff pair dimensions (gap) settings dialog.
static void extendBox(BOX2I &aBox, bool &aDefined, const VECTOR2I &aP)
Definition: pns_line.cpp:1204
void HullIntersection(const SHAPE_LINE_CHAIN &hull, const SHAPE_LINE_CHAIN &line, SHAPE_LINE_CHAIN::INTERSECTIONS &ips)
Definition: pns_utils.cpp:395
static int areNeighbours(int x, int y, int max=0)
Definition: pns_line.cpp:192
SHAPE_LINE_CHAIN dragCornerInternal(const SHAPE_LINE_CHAIN &aOrigin, const VECTOR2I &aP, DIRECTION_45 aPreferredEndingDirection=DIRECTION_45())
Definition: pns_line.cpp:626
const SHAPE_LINE_CHAIN SegmentHull(const SHAPE_SEGMENT &aSeg, int aClearance, int aWalkaroundThickness)
Definition: pns_utils.cpp:180
@ MK_LOCKED
Definition: pns_item.h:45
@ OUTSIDE
Text appears outside the dimension line (default)
static std::pair< bool, SHAPE_POLY_SET::VERTEX_INDEX > findVertex(SHAPE_POLY_SET &aPolySet, const EDIT_POINT &aPoint)
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
Represent an intersection between two line segments.
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:695