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