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