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