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:301
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:207
std::optional< OBSTACLE > OPT_OBSTACLE
Definition: pns_node.h:217
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.
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.
void Simplify(int aMaxError=0)
Simplify the line chain by removing colinear adjacent segments and duplicate vertices.
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.
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.
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