KiCad PCB EDA Suite
convert_shape_list_to_polygon.cpp
Go to the documentation of this file.
1/*
2 * This program source code file is part of KiCad, a free EDA CAD application.
3 *
4 * Copyright (C) 2017 Jean-Pierre Charras, jp.charras at wanadoo.fr
5 * Copyright (C) 2015 SoftPLC Corporation, Dick Hollenbeck <[email protected]>
6 * Copyright (C) 1992-2023 KiCad Developers, see AUTHORS.txt for contributors.
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License
10 * as published by the Free Software Foundation; either version 2
11 * of the License, or (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, you may find one here:
20 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21 * or you may search the http://www.gnu.org website for the version 2 license,
22 * or you may write to the Free Software Foundation, Inc.,
23 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24 */
25
26#include <trigo.h>
27#include <macros.h>
28
29#include <math/vector2d.h>
30#include <pcb_shape.h>
31#include <footprint.h>
32#include <pad.h>
33#include <base_units.h>
38
39#include <wx/log.h>
40
41
49const wxChar* traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" );
50
60bool close_enough( VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit )
61{
62 return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
63}
64
74bool closer_to_first( VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond )
75{
76 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
77}
78
79
89static PCB_SHAPE* findNext( PCB_SHAPE* aShape, const VECTOR2I& aPoint,
90 const std::vector<PCB_SHAPE*>& aList, unsigned aLimit )
91{
92 // Look for an unused, exact hit
93 for( PCB_SHAPE* graphic : aList )
94 {
95 if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
96 continue;
97
98 if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
99 return graphic;
100 }
101
102 // Search again for anything that's close, even something already used. (The latter is
103 // important for error reporting.)
104 VECTOR2I pt( aPoint );
105 SEG::ecoord closest_dist_sq = SEG::Square( aLimit );
106 PCB_SHAPE* closest_graphic = nullptr;
107 SEG::ecoord d_sq;
108
109 for( PCB_SHAPE* graphic : aList )
110 {
111 if( graphic == aShape )
112 continue;
113
114 d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
115
116 if( d_sq < closest_dist_sq )
117 {
118 closest_dist_sq = d_sq;
119 closest_graphic = graphic;
120 }
121
122 d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
123
124 if( d_sq < closest_dist_sq )
125 {
126 closest_dist_sq = d_sq;
127 closest_graphic = graphic;
128 }
129 }
130
131 return closest_graphic; // Note: will be nullptr if nothing within aLimit
132}
133
134
135bool isCopperOutside( const FOOTPRINT* aFootprint, SHAPE_POLY_SET& aShape )
136{
137 bool padOutside = false;
138
139 for( PAD* pad : aFootprint->Pads() )
140 {
142
143 poly.BooleanIntersection( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
144
145 if( poly.OutlineCount() == 0 )
146 {
147 VECTOR2I padPos = pad->GetPosition();
148 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): outside" ),
149 padPos.x, padPos.y );
150 padOutside = true;
151 break;
152 }
153
154 VECTOR2I padPos = pad->GetPosition();
155 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ),
156 padPos.x, padPos.y );
157 }
158
159 return padOutside;
160}
161
162
175bool ConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aShapeList, SHAPE_POLY_SET& aPolygons,
176 int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint,
177 OUTLINE_ERROR_HANDLER* aErrorHandler )
178{
179 if( aShapeList.size() == 0 )
180 return true;
181
182 bool selfIntersecting = false;
183
184 wxString msg;
185 PCB_SHAPE* graphic = nullptr;
186
187 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
188
189 // Keep a list of where the various shapes came from so after doing our combined-polygon
190 // tests we can still report errors against the individual graphic items.
191 std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> shapeOwners;
192
193 auto fetchOwner =
194 [&]( const SEG& seg ) -> PCB_SHAPE*
195 {
196 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
197 return it == shapeOwners.end() ? nullptr : it->second;
198 };
199
200 PCB_SHAPE* prevGraphic = nullptr;
201 VECTOR2I prevPt;
202
203 std::vector<SHAPE_LINE_CHAIN> contours;
204
205 for( PCB_SHAPE* shape : startCandidates )
206 shape->ClearFlags( SKIP_STRUCT );
207
208 while( startCandidates.size() )
209 {
210 graphic = (PCB_SHAPE*) *startCandidates.begin();
211 graphic->SetFlags( SKIP_STRUCT );
212 startCandidates.erase( startCandidates.begin() );
213
214 contours.emplace_back();
215
216 SHAPE_LINE_CHAIN& currContour = contours.back();
217 bool firstPt = true;
218
219 // Circles, rects and polygons are closed shapes unto themselves (and do not combine
220 // with other shapes), so process them separately.
221 if( graphic->GetShape() == SHAPE_T::POLY )
222 {
223 EDA_ANGLE orientation = ANGLE_0;
224 VECTOR2I offset = VECTOR2I( 0, 0 );
225
226 if( graphic->GetParentFootprint() )
227 {
228 orientation = graphic->GetParentFootprint()->GetOrientation();
229 offset = graphic->GetParentFootprint()->GetPosition();
230 }
231
232 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
233 {
234 VECTOR2I pt = *it;
235 RotatePoint( pt, orientation );
236 pt += offset;
237
238 currContour.Append( pt );
239
240 if( firstPt )
241 firstPt = false;
242 else
243 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
244
245 prevPt = pt;
246 }
247
248 currContour.SetClosed( true );
249 }
250 else if( graphic->GetShape() == SHAPE_T::CIRCLE )
251 {
252 // make a circle by segments;
253 VECTOR2I center = graphic->GetCenter();
254 VECTOR2I start = center;
255 int radius = graphic->GetRadius();
256 int steps = GetArcToSegmentCount( radius, aErrorMax, FULL_CIRCLE );
257 VECTOR2I nextPt;
258
259 start.x += radius;
260
261 for( int step = 0; step < steps; ++step )
262 {
263 nextPt = start;
264 RotatePoint( nextPt, center, ANGLE_360 * step / steps );
265 currContour.Append( nextPt );
266
267 if( firstPt )
268 firstPt = false;
269 else
270 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
271
272 prevPt = nextPt;
273 }
274
275 currContour.SetClosed( true );
276 }
277 else if( graphic->GetShape() == SHAPE_T::RECT )
278 {
279 std::vector<VECTOR2I> pts = graphic->GetRectCorners();
280
281 for( const VECTOR2I& pt : pts )
282 {
283 currContour.Append( pt );
284
285 if( firstPt )
286 firstPt = false;
287 else
288 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
289
290 prevPt = pt;
291 }
292
293 currContour.SetClosed( true );
294 }
295 else
296 {
297 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
298 // from here.
299
300 VECTOR2I startPt = graphic->GetEnd();
301 prevPt = startPt;
302 currContour.Append( prevPt );
303
304 // do not append the other end point yet, this first 'graphic' might be an arc
305 for(;;)
306 {
307 switch( graphic->GetShape() )
308 {
309 case SHAPE_T::RECT:
310 case SHAPE_T::CIRCLE:
311 {
312 // As a non-first item, closed shapes can't be anything but self-intersecting
313
314 if( aErrorHandler )
315 {
316 wxASSERT( prevGraphic );
317 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
318 }
319
320 selfIntersecting = true;
321
322 // A closed shape will finish where it started, so no point in updating prevPt
323 break;
324 }
325
326 case SHAPE_T::SEGMENT:
327 {
328 VECTOR2I nextPt;
329
330 // Use the line segment end point furthest away from prevPt as we assume
331 // the other end to be ON prevPt or very close to it.
332
333 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
334 nextPt = graphic->GetEnd();
335 else
336 nextPt = graphic->GetStart();
337
338 currContour.Append( nextPt );
339 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
340 prevPt = nextPt;
341 }
342 break;
343
344 case SHAPE_T::ARC:
345 // We do not support arcs in polygons, so approximate an arc with a series of
346 // short lines and put those line segments into the !same! PATH.
347 {
348 VECTOR2I pstart = graphic->GetStart();
349 VECTOR2I pend = graphic->GetEnd();
350 VECTOR2I pcenter = graphic->GetCenter();
351 EDA_ANGLE angle = -graphic->GetArcAngle();
352 int radius = graphic->GetRadius();
353 int steps = GetArcToSegmentCount( radius, aErrorMax, angle );
354
355 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
356 {
357 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
358
359 angle = -angle;
360 std::swap( pstart, pend );
361 }
362
363 // Create intermediate points between start and end:
364 for( int step = 1; step < steps; ++step )
365 {
366 EDA_ANGLE rotation = ( angle * step ) / steps;
367 VECTOR2I pt = pstart;
368
369 RotatePoint( pt, pcenter, rotation );
370
371 currContour.Append( pt );
372 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
373 prevPt = pt;
374 }
375
376 // Append the last arc end point
377 currContour.Append( pend );
378 shapeOwners[ std::make_pair( prevPt, pend ) ] = graphic;
379 prevPt = pend;
380 }
381 break;
382
383 case SHAPE_T::BEZIER:
384 // We do not support Bezier curves in polygons, so approximate with a series
385 // of short lines and put those line segments into the !same! PATH.
386 {
387 VECTOR2I nextPt;
388 bool reverse = false;
389
390 // Use the end point furthest away from prevPt as we assume the other
391 // end to be ON prevPt or very close to it.
392
393 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
394 {
395 nextPt = graphic->GetEnd();
396 }
397 else
398 {
399 nextPt = graphic->GetStart();
400 reverse = true;
401 }
402
403 // Ensure the approximated Bezier shape is built
404 // a good value is between (Bezier curve width / 2) and (Bezier curve width)
405 // ( and at least 0.05 mm to avoid very small segments)
406 int min_segm_lenght = std::max( pcbIUScale.mmToIU( 0.05 ), graphic->GetWidth() );
407 graphic->RebuildBezierToSegmentsPointsList( min_segm_lenght );
408
409 if( reverse )
410 {
411 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
412 {
413 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
414
415 if( prevPt == pt )
416 continue;
417
418 currContour.Append( pt );
419 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
420 prevPt = pt;
421 }
422 }
423 else
424 {
425 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
426 {
427 if( prevPt == pt )
428 continue;
429
430 currContour.Append( pt );
431 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
432 prevPt = pt;
433 }
434 }
435
436 prevPt = nextPt;
437 }
438 break;
439
440 default:
442 return false;
443 }
444
445 // Get next closest segment.
446
447 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
448
449 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
450 {
451 prevGraphic = graphic;
452 graphic = nextGraphic;
453 graphic->SetFlags( SKIP_STRUCT );
454 startCandidates.erase( graphic );
455 continue;
456 }
457
458 // Finished, or ran into trouble...
459
460 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
461 {
462 currContour.SetClosed( true );
463 break;
464 }
465 else if( nextGraphic ) // encountered already-used segment, but not at the start
466 {
467 if( aErrorHandler )
468 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
469
470 break;
471 }
472 else // encountered discontinuity
473 {
474 if( aErrorHandler )
475 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
476
477 break;
478 }
479 }
480 }
481 }
482
483 for( const SHAPE_LINE_CHAIN& contour : contours )
484 {
485 if( !contour.IsClosed() )
486 return false;
487 }
488
489 // First, collect the parents of each contour
490 //
491 std::map<int, std::vector<int>> contourToParentIndexesMap;
492
493 for( size_t ii = 0; ii < contours.size(); ++ii )
494 {
495 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
496 std::vector<int> parents;
497
498 for( size_t jj = 0; jj < contours.size(); ++jj )
499 {
500 if( jj == ii )
501 continue;
502
503 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
504
505 if( parentCandidate.PointInside( firstPt ) )
506 parents.push_back( jj );
507 }
508
509 contourToParentIndexesMap[ii] = parents;
510 }
511
512 // Next add those that are top-level outlines to the SHAPE_POLY_SET
513 //
514 std::map<int, int> contourToOutlineIdxMap;
515
516 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
517 {
518 if( parentIndexes.size() %2 == 0 )
519 {
520 // Even number of parents; top-level outline
521 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
522 {
523 if( aErrorHandler )
524 {
525 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
526 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
527
528 if( a && b )
529 {
530 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
531 contours[ contourIndex ].GetPoint( 0 ) );
532 }
533 }
534
535 return false;
536 }
537
538 aPolygons.AddOutline( contours[ contourIndex ] );
539 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
540 }
541 }
542
543 // And finally add the holes
544 //
545 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
546 {
547 if( parentIndexes.size() %2 == 1 )
548 {
549 // Odd number of parents; we're a hole in the parent which has one fewer parents
550 // than we have.
551 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
552
553 for( int parentContourIdx : parentIndexes )
554 {
555 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
556 {
557 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
558 aPolygons.AddHole( hole, outlineIdx );
559 break;
560 }
561 }
562 }
563 }
564
565 // All of the silliness that follows is to work around the segment iterator while checking
566 // for collisions.
567 // TODO: Implement proper segment and point iterators that follow std
568
569 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
570 {
571 auto seg2 = seg1;
572
573 for( ++seg2; seg2; seg2++ )
574 {
575 // Check for exact overlapping segments.
576 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
577 {
578 if( aErrorHandler )
579 {
580 BOARD_ITEM* a = fetchOwner( *seg1 );
581 BOARD_ITEM* b = fetchOwner( *seg2 );
582
583 if( a && b )
584 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
585 }
586
587 selfIntersecting = true;
588 }
589
590 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
591 {
592 if( aErrorHandler )
593 {
594 BOARD_ITEM* a = fetchOwner( *seg1 );
595 BOARD_ITEM* b = fetchOwner( *seg2 );
596
597 if( a && b )
598 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
599 }
600
601 selfIntersecting = true;
602 }
603 }
604 }
605
606 return !selfIntersecting;
607}
608
609
610#include <board.h>
611#include <collectors.h>
612
613/* This function is used to extract a board outlines (3D view, automatic zones build ...)
614 * Any closed outline inside the main outline is a hole
615 * All contours should be closed, i.e. valid closed polygon vertices
616 */
617bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
618 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
619{
620 PCB_TYPE_COLLECTOR items;
621 bool success = false;
622
623 SHAPE_POLY_SET fpHoles;
624
625 // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
626 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
627
628 for( int ii = 0; ii < items.GetCount(); ++ii )
629 items[ii]->ClearFlags( SKIP_STRUCT );
630
631 for( FOOTPRINT* fp : aBoard->Footprints() )
632 {
633 PCB_TYPE_COLLECTOR fpItems;
634 fpItems.Collect( fp, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
635
636 std::vector<PCB_SHAPE*> fpSegList;
637
638 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
639 {
640 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
641
642 if( fpSeg->GetLayer() == Edge_Cuts )
643 fpSegList.push_back( fpSeg );
644 }
645
646 if( !fpSegList.empty() )
647 {
648 SHAPE_POLY_SET fpOutlines;
649 success = ConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon,
650 false,
651 // don't report errors here; the second pass also
652 // gets an opportunity to use these segments
653 nullptr );
654
655 if( success && isCopperOutside( fp, fpOutlines ) )
656 {
657 fpHoles.Append( fpOutlines );
658 }
659 else
660 {
661 // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
662 // in contention for the board outline builds.
663 for( int ii = 0; ii < fpItems.GetCount(); ++ii )
664 fpItems[ii]->ClearFlags( SKIP_STRUCT );
665 }
666 }
667 }
668
669 // Make a working copy of aSegList, because the list is modified during calculations
670 std::vector<PCB_SHAPE*> segList;
671
672 for( int ii = 0; ii < items.GetCount(); ii++ )
673 {
674 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
675
676 // Skip anything already used to generate footprint holes (above)
677 if( seg->GetFlags() & SKIP_STRUCT )
678 continue;
679
680 if( seg->GetLayer() == Edge_Cuts )
681 segList.push_back( seg );
682 }
683
684 if( segList.size() )
685 {
686 success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
687 true, aErrorHandler );
688 }
689
690 if( !success || !aOutlines.OutlineCount() )
691 {
692 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
693 // create a rectangular outline, or, failing that, the bounding box of the items on
694 // the board.
695
696 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
697
698 // If null area, uses the global bounding box.
699 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
700 bbbox = aBoard->ComputeBoundingBox();
701
702 // Ensure non null area. If happen, gives a minimal size.
703 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
704 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
705
706 aOutlines.RemoveAllContours();
707 aOutlines.NewOutline();
708
709 VECTOR2I corner;
710 aOutlines.Append( bbbox.GetOrigin() );
711
712 corner.x = bbbox.GetOrigin().x;
713 corner.y = bbbox.GetEnd().y;
714 aOutlines.Append( corner );
715
716 aOutlines.Append( bbbox.GetEnd() );
717
718 corner.x = bbbox.GetEnd().x;
719 corner.y = bbbox.GetOrigin().y;
720 aOutlines.Append( corner );
721 }
722
723 for( int ii = 0; ii < fpHoles.OutlineCount(); ++ii )
724 {
725 const VECTOR2I holePt = fpHoles.Outline( ii ).CPoint( 0 );
726
727 for( int jj = 0; jj < aOutlines.OutlineCount(); ++jj )
728 {
729 if( aOutlines.Outline( jj ).PointInside( holePt ) )
730 {
731 aOutlines.AddHole( fpHoles.Outline( ii ), jj );
732 break;
733 }
734 }
735 }
736
737 return success;
738}
739
740
753void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline )
754{
755 BOX2I bbbox = aBoard->GetBoundingBox();
756 SHAPE_LINE_CHAIN chain;
757
758 // If null area, uses the global bounding box.
759 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
760 bbbox = aBoard->ComputeBoundingBox();
761
762 // Ensure non null area. If happen, gives a minimal size.
763 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
764 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
765
766 // Inflate slightly (by 1/10th the size of the box)
767 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
768
769 chain.Append( bbbox.GetOrigin() );
770 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
771 chain.Append( bbbox.GetEnd() );
772 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
773 chain.SetClosed( true );
774
775 aOutline.RemoveAllContours();
776 aOutline.AddOutline( chain );
777}
778
779
780VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
781 int aOutlineNum = 0 )
782{
783 int minDistance = -1;
784 VECTOR2I projPoint;
785
786 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
787 {
788 auto seg = it.Get();
789 int dis = seg.Distance( aEndPoint );
790
791 if( minDistance < 0 || ( dis < minDistance ) )
792 {
793 minDistance = dis;
794 projPoint = seg.NearestPoint( aEndPoint );
795 }
796 }
797
798 return projPoint;
799}
800
801
802int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
803{
804 int foundSegs = 0;
805
806 for( int i = 0; i < aChain.SegmentCount(); i++ )
807 {
808 SEG seg = aChain.Segment( i );
809
810 bool foundA = false;
811 bool foundB = false;
812
813 for( int j = 0; j < aChain.SegmentCount(); j++ )
814 {
815 // Don't test the segment against itself
816 if( i == j )
817 continue;
818
819 SEG testSeg = aChain.Segment( j );
820
821 if( testSeg.Contains( seg.A ) )
822 foundA = true;
823
824 if( testSeg.Contains( seg.B ) )
825 foundB = true;
826 }
827
828 // This segment isn't a start or end
829 if( foundA && foundB )
830 continue;
831
832 if( foundSegs == 0 )
833 {
834 // The first segment we encounter is the "start" segment
835 wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
836 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
837 aStartSeg = seg;
838 foundSegs++;
839 }
840 else
841 {
842 // Once we find both start and end, we can stop
843 wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
844 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
845 aEndSeg = seg;
846 foundSegs++;
847 break;
848 }
849 }
850
851 return foundSegs;
852}
853
854
866bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
867 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
868
869{
870 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
871
872 // No footprint loaded
873 if( !footprint )
874 {
875 wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
876 return false;
877 }
878
879 PCB_TYPE_COLLECTOR items;
880 SHAPE_POLY_SET outlines;
881 bool success = false;
882
883 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
884 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
885
886 // Make a working copy of aSegList, because the list is modified during calculations
887 std::vector<PCB_SHAPE*> segList;
888
889 for( int ii = 0; ii < items.GetCount(); ii++ )
890 {
891 if( items[ii]->GetLayer() == Edge_Cuts )
892 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
893 }
894
895 if( !segList.empty() )
896 {
897 success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
898 true, aErrorHandler );
899 }
900
901 // A closed outline was found on Edge_Cuts
902 if( success )
903 {
904 wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
905
906 // If copper is outside a closed polygon, treat it as a hole
907 if( isCopperOutside( footprint, outlines ) )
908 {
909 wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
910
911 buildBoardBoundingBoxPoly( aBoard, aOutlines );
912
913 // Copy all outlines from the conversion as holes into the new outline
914 for( int i = 0; i < outlines.OutlineCount(); i++ )
915 {
916 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
917
918 if( out.IsClosed() )
919 aOutlines.AddHole( out, -1 );
920
921 for( int j = 0; j < outlines.HoleCount( i ); j++ )
922 {
923 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
924
925 if( hole.IsClosed() )
926 aOutlines.AddHole( hole, -1 );
927 }
928 }
929 }
930 // If all copper is inside, then the computed outline is the board outline
931 else
932 {
933 wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
934 aOutlines = outlines;
935 }
936
937 return true;
938 }
939 // No board outlines were found, so use the bounding box
940 else if( outlines.OutlineCount() == 0 )
941 {
942 wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
943 buildBoardBoundingBoxPoly( aBoard, aOutlines );
944
945 return true;
946 }
947 // There is an outline present, but it is not closed
948 else
949 {
950 wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
951
952 std::vector<SHAPE_LINE_CHAIN> closedChains;
953 std::vector<SHAPE_LINE_CHAIN> openChains;
954
955 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
956 // holes, so we promote the holes and process them
957 openChains.push_back( outlines.Outline( 0 ) );
958
959 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
960 {
961 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
962
963 if( hole.IsClosed() )
964 {
965 wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
966 closedChains.push_back( hole );
967 }
968 else
969 {
970 wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
971 openChains.push_back( hole );
972 }
973 }
974
975 SHAPE_POLY_SET bbox;
976 buildBoardBoundingBoxPoly( aBoard, bbox );
977
978 // Treat the open polys as the board edge
979 SHAPE_LINE_CHAIN chain = openChains[0];
980 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
981
982 // We know the outline chain is open, so set to non-closed to get better segment count
983 chain.SetClosed( false );
984
985 SEG startSeg;
986 SEG endSeg;
987
988 // The two possible board outlines
989 SHAPE_LINE_CHAIN upper;
990 SHAPE_LINE_CHAIN lower;
991
992 findEndSegments( chain, startSeg, endSeg );
993
994 if( chain.SegmentCount() == 0 )
995 {
996 // Something is wrong, bail out with the overall footprint bounding box
997 wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
998 aOutlines = bbox;
999 return true;
1000 }
1001 else if( chain.SegmentCount() == 1 )
1002 {
1003 // This case means there is only 1 line segment making up the edge cuts of the
1004 // footprint, so we just need to use it to cut the bounding box in half.
1005 wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
1006
1007 startSeg = chain.Segment( 0 );
1008
1009 // Intersect with all the sides of the rectangle
1010 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
1011 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
1012 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1013 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1014
1015 if( inter0 && inter2 && !inter1 && !inter3 )
1016 {
1017 // Intersects the vertical rectangle sides only
1018 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1019 "sides" ) );
1020
1021 // The upper half
1022 upper.Append( *inter0 );
1023 upper.Append( rect.GetPoint( 1 ) );
1024 upper.Append( rect.GetPoint( 2 ) );
1025 upper.Append( *inter2 );
1026 upper.SetClosed( true );
1027
1028 // The lower half
1029 lower.Append( *inter0 );
1030 lower.Append( rect.GetPoint( 0 ) );
1031 lower.Append( rect.GetPoint( 3 ) );
1032 lower.Append( *inter2 );
1033 lower.SetClosed( true );
1034 }
1035 else if( inter1 && inter3 && !inter0 && !inter2 )
1036 {
1037 // Intersects the horizontal rectangle sides only
1038 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1039 "sides" ) );
1040
1041 // The left half
1042 upper.Append( *inter1 );
1043 upper.Append( rect.GetPoint( 1 ) );
1044 upper.Append( rect.GetPoint( 0 ) );
1045 upper.Append( *inter3 );
1046 upper.SetClosed( true );
1047
1048 // The right half
1049 lower.Append( *inter1 );
1050 lower.Append( rect.GetPoint( 2 ) );
1051 lower.Append( rect.GetPoint( 3 ) );
1052 lower.Append( *inter3 );
1053 lower.SetClosed( true );
1054 }
1055 else
1056 {
1057 // Angled line segment that cuts across a corner
1058 wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1059 "sides" ) );
1060
1061 // Figure out which actual lines are intersected, since IntersectLines assumes
1062 // an infinite line
1063 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1064 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1065 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1066 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1067
1068 if( hit0 && hit1 )
1069 {
1070 // Cut across the upper left corner
1071 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1072
1073 // The upper half
1074 upper.Append( *inter0 );
1075 upper.Append( rect.GetPoint( 1 ) );
1076 upper.Append( *inter1 );
1077 upper.SetClosed( true );
1078
1079 // The lower half
1080 lower.Append( *inter0 );
1081 lower.Append( rect.GetPoint( 0 ) );
1082 lower.Append( rect.GetPoint( 3 ) );
1083 lower.Append( rect.GetPoint( 2 ) );
1084 lower.Append( *inter1 );
1085 lower.SetClosed( true );
1086 }
1087 else if( hit1 && hit2 )
1088 {
1089 // Cut across the upper right corner
1090 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1091
1092 // The upper half
1093 upper.Append( *inter1 );
1094 upper.Append( rect.GetPoint( 2 ) );
1095 upper.Append( *inter2 );
1096 upper.SetClosed( true );
1097
1098 // The lower half
1099 lower.Append( *inter1 );
1100 lower.Append( rect.GetPoint( 1 ) );
1101 lower.Append( rect.GetPoint( 0 ) );
1102 lower.Append( rect.GetPoint( 3 ) );
1103 lower.Append( *inter2 );
1104 lower.SetClosed( true );
1105 }
1106 else if( hit2 && hit3 )
1107 {
1108 // Cut across the lower right corner
1109 wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1110
1111 // The upper half
1112 upper.Append( *inter2 );
1113 upper.Append( rect.GetPoint( 2 ) );
1114 upper.Append( rect.GetPoint( 1 ) );
1115 upper.Append( rect.GetPoint( 0 ) );
1116 upper.Append( *inter3 );
1117 upper.SetClosed( true );
1118
1119 // The bottom half
1120 lower.Append( *inter2 );
1121 lower.Append( rect.GetPoint( 3 ) );
1122 lower.Append( *inter3 );
1123 lower.SetClosed( true );
1124 }
1125 else
1126 {
1127 // Cut across the lower left corner
1128 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1129
1130 // The upper half
1131 upper.Append( *inter0 );
1132 upper.Append( rect.GetPoint( 1 ) );
1133 upper.Append( rect.GetPoint( 2 ) );
1134 upper.Append( rect.GetPoint( 3 ) );
1135 upper.Append( *inter3 );
1136 upper.SetClosed( true );
1137
1138 // The bottom half
1139 lower.Append( *inter0 );
1140 lower.Append( rect.GetPoint( 0 ) );
1141 lower.Append( *inter3 );
1142 lower.SetClosed( true );
1143 }
1144 }
1145 }
1146 else
1147 {
1148 // More than 1 segment
1149 wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1150
1151 // Just a temporary thing
1152 aOutlines = bbox;
1153 return true;
1154 }
1155
1156 // Figure out which is the correct outline
1157 SHAPE_POLY_SET poly1;
1158 SHAPE_POLY_SET poly2;
1159
1160 poly1.NewOutline();
1161 poly1.Append( upper );
1162
1163 poly2.NewOutline();
1164 poly2.Append( lower );
1165
1166 if( isCopperOutside( footprint, poly1 ) )
1167 {
1168 wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1169 aOutlines = poly2;
1170 }
1171 else
1172 {
1173 wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1174 aOutlines = poly1;
1175 }
1176
1177 // Add all closed polys as holes to the main outline
1178 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1179 {
1180 wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1181 aOutlines.AddHole( closedChain, -1 );
1182 }
1183
1184 return true;
1185 }
1186
1187 // We really shouldn't reach this point
1188 return false;
1189}
constexpr EDA_IU_SCALE pcbIUScale
Definition: base_units.h:109
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:70
virtual PCB_LAYER_ID GetLayer() const
Return the primary layer this item is on.
Definition: board_item.h:192
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:269
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:842
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:828
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:403
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1253
FOOTPRINTS & Footprints()
Definition: board.h:311
const Vec & GetOrigin() const
Definition: box2.h:183
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
const Vec GetEnd() const
Definition: box2.h:185
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
int GetCount() const
Return the number of objects in the list.
Definition: collector.h:81
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:139
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:142
EDA_ANGLE GetArcAngle() const
Definition: eda_shape.cpp:585
void RebuildBezierToSegmentsPointsList(int aMinSegLen)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
Definition: eda_shape.cpp:405
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:247
int GetRadius() const
Definition: eda_shape.cpp:523
SHAPE_T GetShape() const
Definition: eda_shape.h:113
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:145
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:120
std::vector< VECTOR2I > GetRectCorners() const
Definition: eda_shape.cpp:1035
int GetWidth() const
Definition: eda_shape.h:109
const std::vector< VECTOR2I > & GetBezierPoints() const
Definition: eda_shape.h:230
wxString SHAPE_T_asString() const
Definition: eda_shape.cpp:75
EDA_ANGLE GetOrientation() const
Definition: footprint.h:191
PADS & Pads()
Definition: footprint.h:170
VECTOR2I GetPosition() const override
Definition: footprint.h:188
Definition: pad.h:60
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition: pcb_shape.h:67
FOOTPRINT * GetParentFootprint() const
Return the parent footprint or NULL if PCB_SHAPE does not belong to a footprint.
Definition: pcb_shape.cpp:252
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
Definition: collectors.h:522
void Collect(BOARD_ITEM *aBoard, const std::vector< KICAD_T > &aTypes)
Collect BOARD_ITEM objects using this class's Inspector method, which does the collection.
Definition: collectors.cpp:631
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
VECTOR2I::extended_type ecoord
Definition: seg.h:44
VECTOR2I B
Definition: seg.h:50
static SEG::ecoord Square(int a)
Definition: seg.h:123
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.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
virtual const SEG GetSegment(int aIndex) const override
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.
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
Represent a set of closed polygons.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
bool IsEmpty() const
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
SHAPE_LINE_CHAIN & Outline(int aIndex)
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
int NewOutline()
Creates a new hole in a given outline.
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
SHAPE_POLY_SET CloneDropTriangulation() const
Creates a new empty polygon in the set and returns its index.
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
VECTOR2I projectPointOnSegment(const VECTOR2I &aEndPoint, const SHAPE_POLY_SET &aOutline, int aOutlineNum=0)
static PCB_SHAPE * findNext(PCB_SHAPE *aShape, const VECTOR2I &aPoint, const std::vector< PCB_SHAPE * > &aList, unsigned aLimit)
Searches for a PCB_SHAPE matching a given end point or start point in a list.
bool close_enough(VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
Function close_enough is a local and tunable method of qualifying the proximity of two points.
void buildBoardBoundingBoxPoly(const BOARD *aBoard, SHAPE_POLY_SET &aOutline)
Get the complete bounding box of the board (including all items).
int findEndSegments(SHAPE_LINE_CHAIN &aChain, SEG &aStartSeg, SEG &aEndSeg)
bool BuildBoardPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut ...
bool ConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aShapeList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER *aErrorHandler)
Function ConvertOutlineToPolygon Build a polygon (with holes) from a PCB_SHAPE list,...
bool BuildFootprintPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
This function is used to extract a board outline for a footprint view.
bool isCopperOutside(const FOOTPRINT *aFootprint, SHAPE_POLY_SET &aShape)
bool closer_to_first(VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
Function closer_to_first Local method which qualifies whether the start or end point of a segment is ...
const std::function< void(const wxString &msg, BOARD_ITEM *itemA, BOARD_ITEM *itemB, const VECTOR2I &pt)> OUTLINE_ERROR_HANDLER
#define _(s)
static constexpr EDA_ANGLE & ANGLE_360
Definition: eda_angle.h:435
static constexpr EDA_ANGLE & FULL_CIRCLE
Definition: eda_angle.h:427
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:429
#define SKIP_STRUCT
flag indicating that the structure should be ignored
a few functions useful in geometry calculations.
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
@ Edge_Cuts
Definition: layer_ids.h:113
This file contains miscellaneous commonly used macros and functions.
#define UNIMPLEMENTED_FOR(type)
Definition: macros.h:120
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
constexpr int mmToIU(double mm) const
Definition: base_units.h:89
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:88
@ PCB_FP_SHAPE_T
class FP_SHAPE, a footprint edge
Definition: typeinfo.h:94
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590