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-2022 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
147bool ConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aShapeList, SHAPE_POLY_SET& aPolygons,
148 int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint,
149 OUTLINE_ERROR_HANDLER* aErrorHandler )
150{
151 if( aShapeList.size() == 0 )
152 return true;
153
154 bool selfIntersecting = false;
155
156 wxString msg;
157 PCB_SHAPE* graphic = nullptr;
158
159 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
160
161 // Keep a list of where the various shapes came from so after doing our combined-polygon
162 // tests we can still report errors against the individual graphic items.
163 std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> shapeOwners;
164
165 auto fetchOwner =
166 [&]( const SEG& seg ) -> PCB_SHAPE*
167 {
168 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
169 return it == shapeOwners.end() ? nullptr : it->second;
170 };
171
172 PCB_SHAPE* prevGraphic = nullptr;
173 VECTOR2I prevPt;
174
175 std::vector<SHAPE_LINE_CHAIN> contours;
176
177 for( PCB_SHAPE* shape : startCandidates )
178 shape->ClearFlags( SKIP_STRUCT );
179
180 while( startCandidates.size() )
181 {
182 graphic = (PCB_SHAPE*) *startCandidates.begin();
183 graphic->SetFlags( SKIP_STRUCT );
184 startCandidates.erase( startCandidates.begin() );
185
186 contours.emplace_back();
187
188 int ii = contours.size() - 1;
189 bool firstPt = true;
190
191 // Circles, rects and polygons are closed shapes unto themselves (and do not combine
192 // with other shapes), so process them separately.
193 if( graphic->GetShape() == SHAPE_T::POLY )
194 {
195 EDA_ANGLE orientation = ANGLE_0;
196 VECTOR2I offset = VECTOR2I( 0, 0 );
197
198 if( graphic->GetParentFootprint() )
199 {
200 orientation = graphic->GetParentFootprint()->GetOrientation();
201 offset = graphic->GetParentFootprint()->GetPosition();
202 }
203
204 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
205 {
206 VECTOR2I pt = *it;
207 RotatePoint( pt, orientation );
208 pt += offset;
209
210 contours[ ii ].Append( pt );
211
212 if( firstPt )
213 firstPt = false;
214 else
215 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
216
217 prevPt = pt;
218 }
219
220 contours[ ii ].SetClosed( true );
221 }
222 else if( graphic->GetShape() == SHAPE_T::CIRCLE )
223 {
224 // make a circle by segments;
225 VECTOR2I center = graphic->GetCenter();
226 VECTOR2I start = center;
227 int radius = graphic->GetRadius();
228 int steps = GetArcToSegmentCount( radius, aErrorMax, FULL_CIRCLE );
229 VECTOR2I nextPt;
230
231 start.x += radius;
232
233 for( int step = 0; step < steps; ++step )
234 {
235 nextPt = start;
236 RotatePoint( nextPt, center, ANGLE_360 * step / steps );
237 contours[ ii ].Append( nextPt );
238
239 if( firstPt )
240 firstPt = false;
241 else
242 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
243
244 prevPt = nextPt;
245 }
246
247 contours[ ii ].SetClosed( true );
248 }
249 else if( graphic->GetShape() == SHAPE_T::RECT )
250 {
251 std::vector<VECTOR2I> pts = graphic->GetRectCorners();
252
253 for( const VECTOR2I& pt : pts )
254 {
255 contours[ ii ].Append( pt );
256
257 if( firstPt )
258 firstPt = false;
259 else
260 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
261
262 prevPt = pt;
263 }
264
265 contours[ ii ].SetClosed( true );
266 }
267 else
268 {
269 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
270 // from here.
271
272 VECTOR2I startPt = graphic->GetEnd();
273 prevPt = startPt;
274 contours[ ii ].Append( prevPt );
275
276 // do not append the other end point yet, this first 'graphic' might be an arc
277 for(;;)
278 {
279 switch( graphic->GetShape() )
280 {
281 case SHAPE_T::RECT:
282 case SHAPE_T::CIRCLE:
283 {
284 // As a non-first item, closed shapes can't be anything but self-intersecting
285
286 if( aErrorHandler )
287 {
288 wxASSERT( prevGraphic );
289 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
290 }
291
292 selfIntersecting = true;
293
294 // A closed shape will finish where it started, so no point in updating prevPt
295 break;
296 }
297
298 case SHAPE_T::SEGMENT:
299 {
300 VECTOR2I nextPt;
301
302 // Use the line segment end point furthest away from prevPt as we assume
303 // the other end to be ON prevPt or very close to it.
304
305 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
306 nextPt = graphic->GetEnd();
307 else
308 nextPt = graphic->GetStart();
309
310 contours[ ii ].Append( nextPt );
311 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
312 prevPt = nextPt;
313 }
314 break;
315
316 case SHAPE_T::ARC:
317 // We do not support arcs in polygons, so approximate an arc with a series of
318 // short lines and put those line segments into the !same! PATH.
319 {
320 VECTOR2I pstart = graphic->GetStart();
321 VECTOR2I pend = graphic->GetEnd();
322 VECTOR2I pcenter = graphic->GetCenter();
323 EDA_ANGLE angle = -graphic->GetArcAngle();
324 int radius = graphic->GetRadius();
325 int steps = GetArcToSegmentCount( radius, aErrorMax, angle );
326
327 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
328 {
329 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
330
331 angle = -angle;
332 std::swap( pstart, pend );
333 }
334
335 // Create intermediate points between start and end:
336 for( int step = 1; step < steps; ++step )
337 {
338 EDA_ANGLE rotation = ( angle * step ) / steps;
339 VECTOR2I pt = pstart;
340
341 RotatePoint( pt, pcenter, rotation );
342
343 contours[ ii ].Append( pt );
344 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
345 prevPt = pt;
346 }
347
348 // Append the last arc end point
349 contours[ ii ].Append( pend );
350 shapeOwners[ std::make_pair( prevPt, pend ) ] = graphic;
351 prevPt = pend;
352 }
353 break;
354
355 case SHAPE_T::BEZIER:
356 // We do not support Bezier curves in polygons, so approximate with a series
357 // of short lines and put those line segments into the !same! PATH.
358 {
359 VECTOR2I nextPt;
360 bool reverse = false;
361
362 // Use the end point furthest away from prevPt as we assume the other
363 // end to be ON prevPt or very close to it.
364
365 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
366 {
367 nextPt = graphic->GetEnd();
368 }
369 else
370 {
371 nextPt = graphic->GetStart();
372 reverse = true;
373 }
374
375 if( reverse )
376 {
377 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
378 {
379 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
380 contours[ ii ].Append( pt );
381 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
382 prevPt = pt;
383 }
384 }
385 else
386 {
387 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
388 {
389 contours[ ii ].Append( pt );
390 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
391 prevPt = pt;
392 }
393 }
394
395 prevPt = nextPt;
396 }
397 break;
398
399 default:
401 return false;
402 }
403
404 // Get next closest segment.
405
406 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
407
408 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
409 {
410 prevGraphic = graphic;
411 graphic = nextGraphic;
412 graphic->SetFlags( SKIP_STRUCT );
413 startCandidates.erase( graphic );
414 continue;
415 }
416
417 // Finished, or ran into trouble...
418
419 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
420 {
421 contours[ ii ].SetClosed( true );
422 break;
423 }
424 else if( nextGraphic ) // encountered already-used segment, but not at the start
425 {
426 if( aErrorHandler )
427 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
428
429 break;
430 }
431 else // encountered discontinuity
432 {
433 if( aErrorHandler )
434 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
435
436 break;
437 }
438 }
439 }
440 }
441
442 for( const SHAPE_LINE_CHAIN& contour : contours )
443 {
444 if( !contour.IsClosed() )
445 return false;
446 }
447
448 // First, collect the parents of each contour
449 //
450 std::map<int, std::vector<int>> contourToParentIndexesMap;
451
452 for( size_t ii = 0; ii < contours.size(); ++ii )
453 {
454 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
455 std::vector<int> parents;
456
457 for( size_t jj = 0; jj < contours.size(); ++jj )
458 {
459 if( jj == ii )
460 continue;
461
462 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
463
464 if( parentCandidate.PointInside( firstPt ) )
465 parents.push_back( jj );
466 }
467
468 contourToParentIndexesMap[ii] = parents;
469 }
470
471 // Next add those that are top-level outlines to the SHAPE_POLY_SET
472 //
473 std::map<int, int> contourToOutlineIdxMap;
474
475 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
476 {
477 if( parentIndexes.size() %2 == 0 )
478 {
479 // Even number of parents; top-level outline
480 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
481 {
482 if( aErrorHandler )
483 {
484 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
485 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
486
487 if( a && b )
488 {
489 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
490 contours[ contourIndex ].GetPoint( 0 ) );
491 }
492 }
493
494 return false;
495 }
496
497 aPolygons.AddOutline( contours[ contourIndex ] );
498 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
499 }
500 }
501
502 // And finally add the holes
503 //
504 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
505 {
506 if( parentIndexes.size() %2 == 1 )
507 {
508 // Odd number of parents; we're a hole in the parent which has one fewer parents
509 // than we have.
510 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
511
512 for( int parentContourIdx : parentIndexes )
513 {
514 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
515 {
516 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
517 aPolygons.AddHole( hole, outlineIdx );
518 break;
519 }
520 }
521 }
522 }
523
524 // All of the silliness that follows is to work around the segment iterator while checking
525 // for collisions.
526 // TODO: Implement proper segment and point iterators that follow std
527
528 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
529 {
530 auto seg2 = seg1;
531
532 for( ++seg2; seg2; seg2++ )
533 {
534 // Check for exact overlapping segments.
535 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
536 {
537 if( aErrorHandler )
538 {
539 BOARD_ITEM* a = fetchOwner( *seg1 );
540 BOARD_ITEM* b = fetchOwner( *seg2 );
541
542 if( a && b )
543 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
544 }
545
546 selfIntersecting = true;
547 }
548
549 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
550 {
551 if( aErrorHandler )
552 {
553 BOARD_ITEM* a = fetchOwner( *seg1 );
554 BOARD_ITEM* b = fetchOwner( *seg2 );
555
556 if( a && b )
557 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
558 }
559
560 selfIntersecting = true;
561 }
562 }
563 }
564
565 return !selfIntersecting;
566}
567
568
569#include <board.h>
570#include <collectors.h>
571
572/* This function is used to extract a board outlines (3D view, automatic zones build ...)
573 * Any closed outline inside the main outline is a hole
574 * All contours should be closed, i.e. valid closed polygon vertices
575 */
576bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
577 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
578{
579 PCB_TYPE_COLLECTOR items;
580 bool success = false;
581
582 // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
583 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
584
585 // Make a working copy of aSegList, because the list is modified during calculations
586 std::vector<PCB_SHAPE*> segList;
587
588 for( int ii = 0; ii < items.GetCount(); ii++ )
589 {
590 if( items[ii]->GetLayer() == Edge_Cuts )
591 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
592 }
593
594 if( segList.size() )
595 {
596 success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
597 true, aErrorHandler );
598 }
599
600 if( !success || !aOutlines.OutlineCount() )
601 {
602 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
603 // create a rectangular outline, or, failing that, the bounding box of the items on
604 // the board.
605
606 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
607
608 // If null area, uses the global bounding box.
609 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
610 bbbox = aBoard->ComputeBoundingBox();
611
612 // Ensure non null area. If happen, gives a minimal size.
613 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
614 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
615
616 aOutlines.RemoveAllContours();
617 aOutlines.NewOutline();
618
619 wxPoint corner;
620 aOutlines.Append( bbbox.GetOrigin() );
621
622 corner.x = bbbox.GetOrigin().x;
623 corner.y = bbbox.GetEnd().y;
624 aOutlines.Append( corner );
625
626 aOutlines.Append( bbbox.GetEnd() );
627
628 corner.x = bbbox.GetEnd().x;
629 corner.y = bbbox.GetOrigin().y;
630 aOutlines.Append( corner );
631 }
632
633 return success;
634}
635
636
649void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline )
650{
651 BOX2I bbbox = aBoard->GetBoundingBox();
652 SHAPE_LINE_CHAIN chain;
653
654 // If null area, uses the global bounding box.
655 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
656 bbbox = aBoard->ComputeBoundingBox();
657
658 // Ensure non null area. If happen, gives a minimal size.
659 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
660 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
661
662 // Inflate slightly (by 1/10th the size of the box)
663 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
664
665 chain.Append( bbbox.GetOrigin() );
666 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
667 chain.Append( bbbox.GetEnd() );
668 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
669 chain.SetClosed( true );
670
671 aOutline.RemoveAllContours();
672 aOutline.AddOutline( chain );
673}
674
675
676bool isCopperOutside( const FOOTPRINT* aMod, SHAPE_POLY_SET& aShape )
677{
678 bool padOutside = false;
679
680 for( PAD* pad : aMod->Pads() )
681 {
683
684 poly.BooleanIntersection( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
685
686 if( poly.OutlineCount() == 0 )
687 {
688 VECTOR2I padPos = pad->GetPosition();
689 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): outside" ),
690 padPos.x, padPos.y );
691 padOutside = true;
692 break;
693 }
694
695 VECTOR2I padPos = pad->GetPosition();
696 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ),
697 padPos.x, padPos.y );
698 }
699
700 return padOutside;
701}
702
703
704VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
705 int aOutlineNum = 0 )
706{
707 int minDistance = -1;
708 VECTOR2I projPoint;
709
710 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
711 {
712 auto seg = it.Get();
713 int dis = seg.Distance( aEndPoint );
714
715 if( minDistance < 0 || ( dis < minDistance ) )
716 {
717 minDistance = dis;
718 projPoint = seg.NearestPoint( aEndPoint );
719 }
720 }
721
722 return projPoint;
723}
724
725
726int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
727{
728 int foundSegs = 0;
729
730 for( int i = 0; i < aChain.SegmentCount(); i++ )
731 {
732 SEG seg = aChain.Segment( i );
733
734 bool foundA = false;
735 bool foundB = false;
736
737 for( int j = 0; j < aChain.SegmentCount(); j++ )
738 {
739 // Don't test the segment against itself
740 if( i == j )
741 continue;
742
743 SEG testSeg = aChain.Segment( j );
744
745 if( testSeg.Contains( seg.A ) )
746 foundA = true;
747
748 if( testSeg.Contains( seg.B ) )
749 foundB = true;
750 }
751
752 // This segment isn't a start or end
753 if( foundA && foundB )
754 continue;
755
756 if( foundSegs == 0 )
757 {
758 // The first segment we encounter is the "start" segment
759 wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
760 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
761 aStartSeg = seg;
762 foundSegs++;
763 }
764 else
765 {
766 // Once we find both start and end, we can stop
767 wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
768 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
769 aEndSeg = seg;
770 foundSegs++;
771 break;
772 }
773 }
774
775 return foundSegs;
776}
777
778
790bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
791 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
792
793{
794 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
795
796 // No footprint loaded
797 if( !footprint )
798 {
799 wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
800 return false;
801 }
802
803 PCB_TYPE_COLLECTOR items;
804 SHAPE_POLY_SET outlines;
805 bool success = false;
806
807 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
808 items.Collect( aBoard, { PCB_SHAPE_T, PCB_FP_SHAPE_T } );
809
810 // Make a working copy of aSegList, because the list is modified during calculations
811 std::vector<PCB_SHAPE*> segList;
812
813 for( int ii = 0; ii < items.GetCount(); ii++ )
814 {
815 if( items[ii]->GetLayer() == Edge_Cuts )
816 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
817 }
818
819 if( !segList.empty() )
820 {
821 success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
822 false, aErrorHandler );
823 }
824
825 // A closed outline was found on Edge_Cuts
826 if( success )
827 {
828 wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
829
830 // If copper is outside a closed polygon, treat it as a hole
831 if( isCopperOutside( footprint, outlines ) )
832 {
833 wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
834
835 buildBoardBoundingBoxPoly( aBoard, aOutlines );
836
837 // Copy all outlines from the conversion as holes into the new outline
838 for( int i = 0; i < outlines.OutlineCount(); i++ )
839 {
840 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
841
842 if( out.IsClosed() )
843 aOutlines.AddHole( out, -1 );
844
845 for( int j = 0; j < outlines.HoleCount( i ); j++ )
846 {
847 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
848
849 if( hole.IsClosed() )
850 aOutlines.AddHole( hole, -1 );
851 }
852 }
853 }
854 // If all copper is inside, then the computed outline is the board outline
855 else
856 {
857 wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
858 aOutlines = outlines;
859 }
860
861 return true;
862 }
863 // No board outlines were found, so use the bounding box
864 else if( outlines.OutlineCount() == 0 )
865 {
866 wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
867 buildBoardBoundingBoxPoly( aBoard, aOutlines );
868
869 return true;
870 }
871 // There is an outline present, but it is not closed
872 else
873 {
874 wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
875
876 std::vector<SHAPE_LINE_CHAIN> closedChains;
877 std::vector<SHAPE_LINE_CHAIN> openChains;
878
879 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
880 // holes, so we promote the holes and process them
881 openChains.push_back( outlines.Outline( 0 ) );
882
883 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
884 {
885 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
886
887 if( hole.IsClosed() )
888 {
889 wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
890 closedChains.push_back( hole );
891 }
892 else
893 {
894 wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
895 openChains.push_back( hole );
896 }
897 }
898
899 SHAPE_POLY_SET bbox;
900 buildBoardBoundingBoxPoly( aBoard, bbox );
901
902 // Treat the open polys as the board edge
903 SHAPE_LINE_CHAIN chain = openChains[0];
904 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
905
906 // We know the outline chain is open, so set to non-closed to get better segment count
907 chain.SetClosed( false );
908
909 SEG startSeg;
910 SEG endSeg;
911
912 // The two possible board outlines
913 SHAPE_LINE_CHAIN upper;
914 SHAPE_LINE_CHAIN lower;
915
916 findEndSegments( chain, startSeg, endSeg );
917
918 if( chain.SegmentCount() == 0 )
919 {
920 // Something is wrong, bail out with the overall footprint bounding box
921 wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
922 aOutlines = bbox;
923 return true;
924 }
925 else if( chain.SegmentCount() == 1 )
926 {
927 // This case means there is only 1 line segment making up the edge cuts of the
928 // footprint, so we just need to use it to cut the bounding box in half.
929 wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
930
931 startSeg = chain.Segment( 0 );
932
933 // Intersect with all the sides of the rectangle
934 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
935 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
936 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
937 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
938
939 if( inter0 && inter2 && !inter1 && !inter3 )
940 {
941 // Intersects the vertical rectangle sides only
942 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
943 "sides" ) );
944
945 // The upper half
946 upper.Append( *inter0 );
947 upper.Append( rect.GetPoint( 1 ) );
948 upper.Append( rect.GetPoint( 2 ) );
949 upper.Append( *inter2 );
950 upper.SetClosed( true );
951
952 // The lower half
953 lower.Append( *inter0 );
954 lower.Append( rect.GetPoint( 0 ) );
955 lower.Append( rect.GetPoint( 3 ) );
956 lower.Append( *inter2 );
957 lower.SetClosed( true );
958 }
959 else if( inter1 && inter3 && !inter0 && !inter2 )
960 {
961 // Intersects the horizontal rectangle sides only
962 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
963 "sides" ) );
964
965 // The left half
966 upper.Append( *inter1 );
967 upper.Append( rect.GetPoint( 1 ) );
968 upper.Append( rect.GetPoint( 0 ) );
969 upper.Append( *inter3 );
970 upper.SetClosed( true );
971
972 // The right half
973 lower.Append( *inter1 );
974 lower.Append( rect.GetPoint( 2 ) );
975 lower.Append( rect.GetPoint( 3 ) );
976 lower.Append( *inter3 );
977 lower.SetClosed( true );
978 }
979 else
980 {
981 // Angled line segment that cuts across a corner
982 wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
983 "sides" ) );
984
985 // Figure out which actual lines are intersected, since IntersectLines assumes
986 // an infinite line
987 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
988 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
989 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
990 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
991
992 if( hit0 && hit1 )
993 {
994 // Cut across the upper left corner
995 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
996
997 // The upper half
998 upper.Append( *inter0 );
999 upper.Append( rect.GetPoint( 1 ) );
1000 upper.Append( *inter1 );
1001 upper.SetClosed( true );
1002
1003 // The lower half
1004 lower.Append( *inter0 );
1005 lower.Append( rect.GetPoint( 0 ) );
1006 lower.Append( rect.GetPoint( 3 ) );
1007 lower.Append( rect.GetPoint( 2 ) );
1008 lower.Append( *inter1 );
1009 lower.SetClosed( true );
1010 }
1011 else if( hit1 && hit2 )
1012 {
1013 // Cut across the upper right corner
1014 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1015
1016 // The upper half
1017 upper.Append( *inter1 );
1018 upper.Append( rect.GetPoint( 2 ) );
1019 upper.Append( *inter2 );
1020 upper.SetClosed( true );
1021
1022 // The lower half
1023 lower.Append( *inter1 );
1024 lower.Append( rect.GetPoint( 1 ) );
1025 lower.Append( rect.GetPoint( 0 ) );
1026 lower.Append( rect.GetPoint( 3 ) );
1027 lower.Append( *inter2 );
1028 lower.SetClosed( true );
1029 }
1030 else if( hit2 && hit3 )
1031 {
1032 // Cut across the lower right corner
1033 wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1034
1035 // The upper half
1036 upper.Append( *inter2 );
1037 upper.Append( rect.GetPoint( 2 ) );
1038 upper.Append( rect.GetPoint( 1 ) );
1039 upper.Append( rect.GetPoint( 0 ) );
1040 upper.Append( *inter3 );
1041 upper.SetClosed( true );
1042
1043 // The bottom half
1044 lower.Append( *inter2 );
1045 lower.Append( rect.GetPoint( 3 ) );
1046 lower.Append( *inter3 );
1047 lower.SetClosed( true );
1048 }
1049 else
1050 {
1051 // Cut across the lower left corner
1052 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1053
1054 // The upper half
1055 upper.Append( *inter0 );
1056 upper.Append( rect.GetPoint( 1 ) );
1057 upper.Append( rect.GetPoint( 2 ) );
1058 upper.Append( rect.GetPoint( 3 ) );
1059 upper.Append( *inter3 );
1060 upper.SetClosed( true );
1061
1062 // The bottom half
1063 lower.Append( *inter0 );
1064 lower.Append( rect.GetPoint( 0 ) );
1065 lower.Append( *inter3 );
1066 lower.SetClosed( true );
1067 }
1068 }
1069 }
1070 else
1071 {
1072 // More than 1 segment
1073 wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1074
1075 // Just a temporary thing
1076 aOutlines = bbox;
1077 return true;
1078 }
1079
1080 // Figure out which is the correct outline
1081 SHAPE_POLY_SET poly1;
1082 SHAPE_POLY_SET poly2;
1083
1084 poly1.NewOutline();
1085 poly1.Append( upper );
1086
1087 poly2.NewOutline();
1088 poly2.Append( lower );
1089
1090 if( isCopperOutside( footprint, poly1 ) )
1091 {
1092 wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1093 aOutlines = poly2;
1094 }
1095 else
1096 {
1097 wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1098 aOutlines = poly1;
1099 }
1100
1101 // Add all closed polys as holes to the main outline
1102 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1103 {
1104 wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1105 aOutlines.AddHole( closedChain, -1 );
1106 }
1107
1108 return true;
1109 }
1110
1111 // We really shouldn't reach this point
1112 return false;
1113}
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:58
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:265
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:821
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:807
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:397
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1177
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:142
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:144
EDA_ANGLE GetArcAngle() const
Definition: eda_shape.cpp:541
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:243
int GetRadius() const
Definition: eda_shape.cpp:479
SHAPE_T GetShape() const
Definition: eda_shape.h:111
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:141
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:116
std::vector< VECTOR2I > GetRectCorners() const
Definition: eda_shape.cpp:989
const std::vector< VECTOR2I > & GetBezierPoints() const
Definition: eda_shape.h:226
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:59
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition: pcb_shape.h:65
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
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 isCopperOutside(const FOOTPRINT *aMod, SHAPE_POLY_SET &aShape)
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 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:418
static constexpr EDA_ANGLE & FULL_CIRCLE
Definition: eda_angle.h:410
static constexpr EDA_ANGLE & ANGLE_0
Definition: eda_angle.h:412
#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:618