KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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
60static bool close_enough( VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit )
61{
62 return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
63}
64
74static bool 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
135static bool 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
163/* Build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a closed main
164 * outline with perhaps closed inner outlines. These closed inner outlines are considered as
165 * holes in the main outline.
166 * @param aShapeList the initial list of SHAPEs (only lines, circles and arcs).
167 * @param aPolygons will contain the complex polygon.
168 * @param aErrorMax is the max error distance when polygonizing a curve (internal units)
169 * @param aChainingEpsilon is the max error distance when polygonizing a curve (internal units)
170 * @param aAllowDisjoint indicates multiple top-level outlines are allowed
171 * @param aErrorHandler = an optional error handler
172 * @param aAllowUseArcsInPolygons = an optional option to allow adding arcs in
173 * SHAPE_LINE_CHAIN polylines/polygons when building outlines from aShapeList
174 */
175bool ConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aShapeList, SHAPE_POLY_SET& aPolygons,
176 int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint,
177 OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons )
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 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
224 {
225 VECTOR2I pt = *it;
226
227 currContour.Append( pt );
228
229 if( firstPt )
230 firstPt = false;
231 else
232 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
233
234 prevPt = pt;
235 }
236
237 currContour.SetClosed( true );
238 }
239 else if( graphic->GetShape() == SHAPE_T::CIRCLE )
240 {
241 VECTOR2I center = graphic->GetCenter();
242 int radius = graphic->GetRadius();
243 VECTOR2I start = center;
244 start.x += radius;
245
246 // Add 360 deg Arc in currContour
247 SHAPE_ARC arc360( center, start, ANGLE_360, 0 );
248 currContour.Append( arc360, aErrorMax );
249 currContour.SetClosed( true );
250
251 // set shapeOwners for currContour points created by appending the arc360:
252 for( int ii = 1; ii < currContour.PointCount(); ++ii )
253 {
254 shapeOwners[ std::make_pair( currContour.CPoint( ii-1 ),
255 currContour.CPoint( ii ) ) ] = graphic;
256 }
257
258 if( !aAllowUseArcsInPolygons )
259 currContour.ClearArcs();
260 }
261 else if( graphic->GetShape() == SHAPE_T::RECTANGLE )
262 {
263 std::vector<VECTOR2I> pts = graphic->GetRectCorners();
264
265 for( const VECTOR2I& pt : pts )
266 {
267 currContour.Append( pt );
268
269 if( firstPt )
270 firstPt = false;
271 else
272 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
273
274 prevPt = pt;
275 }
276
277 currContour.SetClosed( true );
278 }
279 else
280 {
281 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
282 // from here.
283
284 VECTOR2I startPt = graphic->GetEnd();
285 prevPt = startPt;
286 currContour.Append( prevPt );
287
288 // do not append the other end point yet, this first 'graphic' might be an arc
289 for(;;)
290 {
291 switch( graphic->GetShape() )
292 {
294 case SHAPE_T::CIRCLE:
295 {
296 // As a non-first item, closed shapes can't be anything but self-intersecting
297
298 if( aErrorHandler )
299 {
300 wxASSERT( prevGraphic );
301 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
302 }
303
304 selfIntersecting = true;
305
306 // A closed shape will finish where it started, so no point in updating prevPt
307 break;
308 }
309
310 case SHAPE_T::SEGMENT:
311 {
312 VECTOR2I nextPt;
313
314 // Use the line segment end point furthest away from prevPt as we assume
315 // the other end to be ON prevPt or very close to it.
316
317 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
318 nextPt = graphic->GetEnd();
319 else
320 nextPt = graphic->GetStart();
321
322 currContour.Append( nextPt );
323 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
324 prevPt = nextPt;
325 }
326 break;
327
328 case SHAPE_T::ARC:
329 {
330 VECTOR2I pstart = graphic->GetStart();
331 VECTOR2I pmid = graphic->GetArcMid();
332 VECTOR2I pend = graphic->GetEnd();
333
334 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
335 {
336 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
337
338 std::swap( pstart, pend );
339 }
340
341 SHAPE_ARC sarc( pstart, pmid, pend, 0 );
342
343 SHAPE_LINE_CHAIN arcChain;
344 arcChain.Append( sarc, aErrorMax );
345
346 if( !aAllowUseArcsInPolygons )
347 arcChain.ClearArcs();
348
349 // set shapeOwners for arcChain points created by appending the sarc:
350 for( int ii = 1; ii < arcChain.PointCount(); ++ii )
351 {
352 shapeOwners[std::make_pair( arcChain.CPoint( ii - 1 ),
353 arcChain.CPoint( ii ) )] = graphic;
354 }
355
356 currContour.Append( arcChain );
357
358 prevPt = pend;
359 }
360 break;
361
362 case SHAPE_T::BEZIER:
363 // We do not support Bezier curves in polygons, so approximate with a series
364 // of short lines and put those line segments into the !same! PATH.
365 {
366 VECTOR2I nextPt;
367 bool reverse = false;
368
369 // Use the end point furthest away from prevPt as we assume the other
370 // end to be ON prevPt or very close to it.
371
372 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
373 {
374 nextPt = graphic->GetEnd();
375 }
376 else
377 {
378 nextPt = graphic->GetStart();
379 reverse = true;
380 }
381
382 // Ensure the approximated Bezier shape is built
383 // a good value is between (Bezier curve width / 2) and (Bezier curve width)
384 // ( and at least 0.05 mm to avoid very small segments)
385 int min_segm_length = std::max( pcbIUScale.mmToIU( 0.05 ), graphic->GetWidth() );
386 graphic->RebuildBezierToSegmentsPointsList( min_segm_length );
387
388 if( reverse )
389 {
390 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
391 {
392 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
393
394 if( prevPt == pt )
395 continue;
396
397 currContour.Append( pt );
398 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
399 prevPt = pt;
400 }
401 }
402 else
403 {
404 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
405 {
406 if( prevPt == pt )
407 continue;
408
409 currContour.Append( pt );
410 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
411 prevPt = pt;
412 }
413 }
414
415 prevPt = nextPt;
416 }
417 break;
418
419 default:
421 return false;
422 }
423
424 // Get next closest segment.
425
426 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
427
428 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
429 {
430 prevGraphic = graphic;
431 graphic = nextGraphic;
432 graphic->SetFlags( SKIP_STRUCT );
433 startCandidates.erase( graphic );
434 continue;
435 }
436
437 // Finished, or ran into trouble...
438
439 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
440 {
441 currContour.SetClosed( true );
442 break;
443 }
444 else if( nextGraphic ) // encountered already-used segment, but not at the start
445 {
446 if( aErrorHandler )
447 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
448
449 break;
450 }
451 else // encountered discontinuity
452 {
453 if( aErrorHandler )
454 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
455
456 break;
457 }
458 }
459 }
460 }
461
462 for( const SHAPE_LINE_CHAIN& contour : contours )
463 {
464 if( !contour.IsClosed() )
465 return false;
466 }
467
468 // First, collect the parents of each contour
469 //
470 std::map<int, std::vector<int>> contourToParentIndexesMap;
471
472 for( size_t ii = 0; ii < contours.size(); ++ii )
473 {
474 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
475 std::vector<int> parents;
476
477 for( size_t jj = 0; jj < contours.size(); ++jj )
478 {
479 if( jj == ii )
480 continue;
481
482 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
483
484 if( parentCandidate.PointInside( firstPt ) )
485 parents.push_back( jj );
486 }
487
488 contourToParentIndexesMap[ii] = parents;
489 }
490
491 // Next add those that are top-level outlines to the SHAPE_POLY_SET
492 //
493 std::map<int, int> contourToOutlineIdxMap;
494
495 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
496 {
497 if( parentIndexes.size() %2 == 0 )
498 {
499 // Even number of parents; top-level outline
500 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
501 {
502 if( aErrorHandler )
503 {
504 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
505 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
506
507 if( a && b )
508 {
509 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
510 contours[ contourIndex ].GetPoint( 0 ) );
511
512 return false;
513 }
514 }
515 }
516
517 aPolygons.AddOutline( contours[ contourIndex ] );
518 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
519 }
520 }
521
522 // And finally add the holes
523 //
524 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
525 {
526 if( parentIndexes.size() %2 == 1 )
527 {
528 // Odd number of parents; we're a hole in the parent which has one fewer parents
529 // than we have.
530 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
531
532 for( int parentContourIdx : parentIndexes )
533 {
534 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
535 {
536 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
537 aPolygons.AddHole( hole, outlineIdx );
538 break;
539 }
540 }
541 }
542 }
543
544 // All of the silliness that follows is to work around the segment iterator while checking
545 // for collisions.
546 // TODO: Implement proper segment and point iterators that follow std
547
548 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
549 {
550 auto seg2 = seg1;
551
552 for( ++seg2; seg2; seg2++ )
553 {
554 // Check for exact overlapping segments.
555 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
556 {
557 if( aErrorHandler )
558 {
559 BOARD_ITEM* a = fetchOwner( *seg1 );
560 BOARD_ITEM* b = fetchOwner( *seg2 );
561 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
562 }
563
564 selfIntersecting = true;
565 }
566
567 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
568 {
569 if( aErrorHandler )
570 {
571 BOARD_ITEM* a = fetchOwner( *seg1 );
572 BOARD_ITEM* b = fetchOwner( *seg2 );
573 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
574 }
575
576 selfIntersecting = true;
577 }
578 }
579 }
580
581 return !selfIntersecting;
582}
583
584
585#include <board.h>
586#include <collectors.h>
587
588/* This function is used to extract a board outlines (3D view, automatic zones build ...)
589 * Any closed outline inside the main outline is a hole
590 * All contours should be closed, i.e. valid closed polygon vertices
591 */
592bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
593 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler,
594 bool aAllowUseArcsInPolygons )
595{
596 PCB_TYPE_COLLECTOR items;
597 bool success = false;
598
599 SHAPE_POLY_SET fpHoles;
600
601 // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
602 items.Collect( aBoard, { PCB_SHAPE_T } );
603
604 for( int ii = 0; ii < items.GetCount(); ++ii )
605 items[ii]->ClearFlags( SKIP_STRUCT );
606
607 for( FOOTPRINT* fp : aBoard->Footprints() )
608 {
609 PCB_TYPE_COLLECTOR fpItems;
610 fpItems.Collect( fp, { PCB_SHAPE_T } );
611
612 std::vector<PCB_SHAPE*> fpSegList;
613
614 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
615 {
616 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
617
618 if( fpSeg->GetLayer() == Edge_Cuts )
619 fpSegList.push_back( fpSeg );
620 }
621
622 if( !fpSegList.empty() )
623 {
624 SHAPE_POLY_SET fpOutlines;
625 success = ConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon,
626 false,
627 // don't report errors here; the second pass also
628 // gets an opportunity to use these segments
629 nullptr, aAllowUseArcsInPolygons );
630
631 // Here, we test to see if we should make holes or outlines. Holes are made if the footprint
632 // has copper outside of a single, closed outline. If there are multiple outlines, we assume
633 // that the footprint edges represent holes as we do not support multiple boards. Similarly, if
634 // any of the footprint pads are located outside of the edges, then the edges are holes
635 if( success && ( isCopperOutside( fp, fpOutlines ) || fpOutlines.OutlineCount() > 1 ) )
636 {
637 fpHoles.Append( fpOutlines );
638 }
639 else
640 {
641 // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
642 // in contention for the board outline builds.
643 for( int ii = 0; ii < fpItems.GetCount(); ++ii )
644 fpItems[ii]->ClearFlags( SKIP_STRUCT );
645 }
646 }
647 }
648
649 // Make a working copy of aSegList, because the list is modified during calculations
650 std::vector<PCB_SHAPE*> segList;
651
652 for( int ii = 0; ii < items.GetCount(); ii++ )
653 {
654 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
655
656 // Skip anything already used to generate footprint holes (above)
657 if( seg->GetFlags() & SKIP_STRUCT )
658 continue;
659
660 if( seg->GetLayer() == Edge_Cuts )
661 segList.push_back( seg );
662 }
663
664 if( segList.size() )
665 {
666 success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
667 true, aErrorHandler, aAllowUseArcsInPolygons );
668 }
669
670 if( !success || !aOutlines.OutlineCount() )
671 {
672 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
673 // create a rectangular outline, or, failing that, the bounding box of the items on
674 // the board.
675
676 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
677
678 // If null area, uses the global bounding box.
679 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
680 bbbox = aBoard->ComputeBoundingBox();
681
682 // Ensure non null area. If happen, gives a minimal size.
683 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
684 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
685
686 aOutlines.RemoveAllContours();
687 aOutlines.NewOutline();
688
689 VECTOR2I corner;
690 aOutlines.Append( bbbox.GetOrigin() );
691
692 corner.x = bbbox.GetOrigin().x;
693 corner.y = bbbox.GetEnd().y;
694 aOutlines.Append( corner );
695
696 aOutlines.Append( bbbox.GetEnd() );
697
698 corner.x = bbbox.GetEnd().x;
699 corner.y = bbbox.GetOrigin().y;
700 aOutlines.Append( corner );
701 }
702
703 for( int ii = 0; ii < fpHoles.OutlineCount(); ++ii )
704 {
705 const VECTOR2I holePt = fpHoles.Outline( ii ).CPoint( 0 );
706
707 for( int jj = 0; jj < aOutlines.OutlineCount(); ++jj )
708 {
709 if( aOutlines.Outline( jj ).PointInside( holePt ) )
710 {
711 aOutlines.AddHole( fpHoles.Outline( ii ), jj );
712 break;
713 }
714 }
715 }
716
717 return success;
718}
719
720
733void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline )
734{
735 BOX2I bbbox = aBoard->GetBoundingBox();
736 SHAPE_LINE_CHAIN chain;
737
738 // If null area, uses the global bounding box.
739 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
740 bbbox = aBoard->ComputeBoundingBox();
741
742 // Ensure non null area. If happen, gives a minimal size.
743 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
744 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
745
746 // Inflate slightly (by 1/10th the size of the box)
747 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
748
749 chain.Append( bbbox.GetOrigin() );
750 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
751 chain.Append( bbbox.GetEnd() );
752 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
753 chain.SetClosed( true );
754
755 aOutline.RemoveAllContours();
756 aOutline.AddOutline( chain );
757}
758
759
760VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
761 int aOutlineNum = 0 )
762{
763 int minDistance = -1;
764 VECTOR2I projPoint;
765
766 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
767 {
768 auto seg = it.Get();
769 int dis = seg.Distance( aEndPoint );
770
771 if( minDistance < 0 || ( dis < minDistance ) )
772 {
773 minDistance = dis;
774 projPoint = seg.NearestPoint( aEndPoint );
775 }
776 }
777
778 return projPoint;
779}
780
781
782int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
783{
784 int foundSegs = 0;
785
786 for( int i = 0; i < aChain.SegmentCount(); i++ )
787 {
788 SEG seg = aChain.Segment( i );
789
790 bool foundA = false;
791 bool foundB = false;
792
793 for( int j = 0; j < aChain.SegmentCount(); j++ )
794 {
795 // Don't test the segment against itself
796 if( i == j )
797 continue;
798
799 SEG testSeg = aChain.Segment( j );
800
801 if( testSeg.Contains( seg.A ) )
802 foundA = true;
803
804 if( testSeg.Contains( seg.B ) )
805 foundB = true;
806 }
807
808 // This segment isn't a start or end
809 if( foundA && foundB )
810 continue;
811
812 if( foundSegs == 0 )
813 {
814 // The first segment we encounter is the "start" segment
815 wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
816 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
817 aStartSeg = seg;
818 foundSegs++;
819 }
820 else
821 {
822 // Once we find both start and end, we can stop
823 wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
824 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
825 aEndSeg = seg;
826 foundSegs++;
827 break;
828 }
829 }
830
831 return foundSegs;
832}
833
834
846bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
847 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
848
849{
850 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
851
852 // No footprint loaded
853 if( !footprint )
854 {
855 wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
856 return false;
857 }
858
859 PCB_TYPE_COLLECTOR items;
860 SHAPE_POLY_SET outlines;
861 bool success = false;
862
863 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
864 items.Collect( aBoard, { PCB_SHAPE_T } );
865
866 // Make a working copy of aSegList, because the list is modified during calculations
867 std::vector<PCB_SHAPE*> segList;
868
869 for( int ii = 0; ii < items.GetCount(); ii++ )
870 {
871 if( items[ii]->GetLayer() == Edge_Cuts )
872 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
873 }
874
875 if( !segList.empty() )
876 {
877 success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
878 true, aErrorHandler );
879 }
880
881 // A closed outline was found on Edge_Cuts
882 if( success )
883 {
884 wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
885
886 // If copper is outside a closed polygon, treat it as a hole
887 // If there are multiple outlines in the footprint, they are also holes
888 if( isCopperOutside( footprint, outlines ) || outlines.OutlineCount() > 1 )
889 {
890 wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
891
892 buildBoardBoundingBoxPoly( aBoard, aOutlines );
893
894 // Copy all outlines from the conversion as holes into the new outline
895 for( int i = 0; i < outlines.OutlineCount(); i++ )
896 {
897 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
898
899 if( out.IsClosed() )
900 aOutlines.AddHole( out, -1 );
901
902 for( int j = 0; j < outlines.HoleCount( i ); j++ )
903 {
904 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
905
906 if( hole.IsClosed() )
907 aOutlines.AddHole( hole, -1 );
908 }
909 }
910 }
911 // If all copper is inside, then the computed outline is the board outline
912 else
913 {
914 wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
915 aOutlines = outlines;
916 }
917
918 return true;
919 }
920 // No board outlines were found, so use the bounding box
921 else if( outlines.OutlineCount() == 0 )
922 {
923 wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
924 buildBoardBoundingBoxPoly( aBoard, aOutlines );
925
926 return true;
927 }
928 // There is an outline present, but it is not closed
929 else
930 {
931 wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
932
933 std::vector<SHAPE_LINE_CHAIN> closedChains;
934 std::vector<SHAPE_LINE_CHAIN> openChains;
935
936 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
937 // holes, so we promote the holes and process them
938 openChains.push_back( outlines.Outline( 0 ) );
939
940 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
941 {
942 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
943
944 if( hole.IsClosed() )
945 {
946 wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
947 closedChains.push_back( hole );
948 }
949 else
950 {
951 wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
952 openChains.push_back( hole );
953 }
954 }
955
956 SHAPE_POLY_SET bbox;
957 buildBoardBoundingBoxPoly( aBoard, bbox );
958
959 // Treat the open polys as the board edge
960 SHAPE_LINE_CHAIN chain = openChains[0];
961 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
962
963 // We know the outline chain is open, so set to non-closed to get better segment count
964 chain.SetClosed( false );
965
966 SEG startSeg;
967 SEG endSeg;
968
969 // The two possible board outlines
970 SHAPE_LINE_CHAIN upper;
971 SHAPE_LINE_CHAIN lower;
972
973 findEndSegments( chain, startSeg, endSeg );
974
975 if( chain.SegmentCount() == 0 )
976 {
977 // Something is wrong, bail out with the overall footprint bounding box
978 wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
979 aOutlines = bbox;
980 return true;
981 }
982 else if( chain.SegmentCount() == 1 )
983 {
984 // This case means there is only 1 line segment making up the edge cuts of the
985 // footprint, so we just need to use it to cut the bounding box in half.
986 wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
987
988 startSeg = chain.Segment( 0 );
989
990 // Intersect with all the sides of the rectangle
991 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
992 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
993 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
994 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
995
996 if( inter0 && inter2 && !inter1 && !inter3 )
997 {
998 // Intersects the vertical rectangle sides only
999 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1000 "sides" ) );
1001
1002 // The upper half
1003 upper.Append( *inter0 );
1004 upper.Append( rect.GetPoint( 1 ) );
1005 upper.Append( rect.GetPoint( 2 ) );
1006 upper.Append( *inter2 );
1007 upper.SetClosed( true );
1008
1009 // The lower half
1010 lower.Append( *inter0 );
1011 lower.Append( rect.GetPoint( 0 ) );
1012 lower.Append( rect.GetPoint( 3 ) );
1013 lower.Append( *inter2 );
1014 lower.SetClosed( true );
1015 }
1016 else if( inter1 && inter3 && !inter0 && !inter2 )
1017 {
1018 // Intersects the horizontal rectangle sides only
1019 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1020 "sides" ) );
1021
1022 // The left half
1023 upper.Append( *inter1 );
1024 upper.Append( rect.GetPoint( 1 ) );
1025 upper.Append( rect.GetPoint( 0 ) );
1026 upper.Append( *inter3 );
1027 upper.SetClosed( true );
1028
1029 // The right half
1030 lower.Append( *inter1 );
1031 lower.Append( rect.GetPoint( 2 ) );
1032 lower.Append( rect.GetPoint( 3 ) );
1033 lower.Append( *inter3 );
1034 lower.SetClosed( true );
1035 }
1036 else
1037 {
1038 // Angled line segment that cuts across a corner
1039 wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1040 "sides" ) );
1041
1042 // Figure out which actual lines are intersected, since IntersectLines assumes
1043 // an infinite line
1044 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1045 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1046 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1047 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1048
1049 if( hit0 && hit1 )
1050 {
1051 // Cut across the upper 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( *inter1 );
1058 upper.SetClosed( true );
1059
1060 // The lower half
1061 lower.Append( *inter0 );
1062 lower.Append( rect.GetPoint( 0 ) );
1063 lower.Append( rect.GetPoint( 3 ) );
1064 lower.Append( rect.GetPoint( 2 ) );
1065 lower.Append( *inter1 );
1066 lower.SetClosed( true );
1067 }
1068 else if( hit1 && hit2 )
1069 {
1070 // Cut across the upper right corner
1071 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1072
1073 // The upper half
1074 upper.Append( *inter1 );
1075 upper.Append( rect.GetPoint( 2 ) );
1076 upper.Append( *inter2 );
1077 upper.SetClosed( true );
1078
1079 // The lower half
1080 lower.Append( *inter1 );
1081 lower.Append( rect.GetPoint( 1 ) );
1082 lower.Append( rect.GetPoint( 0 ) );
1083 lower.Append( rect.GetPoint( 3 ) );
1084 lower.Append( *inter2 );
1085 lower.SetClosed( true );
1086 }
1087 else if( hit2 && hit3 )
1088 {
1089 // Cut across the lower right corner
1090 wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1091
1092 // The upper half
1093 upper.Append( *inter2 );
1094 upper.Append( rect.GetPoint( 2 ) );
1095 upper.Append( rect.GetPoint( 1 ) );
1096 upper.Append( rect.GetPoint( 0 ) );
1097 upper.Append( *inter3 );
1098 upper.SetClosed( true );
1099
1100 // The bottom half
1101 lower.Append( *inter2 );
1102 lower.Append( rect.GetPoint( 3 ) );
1103 lower.Append( *inter3 );
1104 lower.SetClosed( true );
1105 }
1106 else
1107 {
1108 // Cut across the lower left corner
1109 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1110
1111 // The upper half
1112 upper.Append( *inter0 );
1113 upper.Append( rect.GetPoint( 1 ) );
1114 upper.Append( rect.GetPoint( 2 ) );
1115 upper.Append( rect.GetPoint( 3 ) );
1116 upper.Append( *inter3 );
1117 upper.SetClosed( true );
1118
1119 // The bottom half
1120 lower.Append( *inter0 );
1121 lower.Append( rect.GetPoint( 0 ) );
1122 lower.Append( *inter3 );
1123 lower.SetClosed( true );
1124 }
1125 }
1126 }
1127 else
1128 {
1129 // More than 1 segment
1130 wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1131
1132 // Just a temporary thing
1133 aOutlines = bbox;
1134 return true;
1135 }
1136
1137 // Figure out which is the correct outline
1138 SHAPE_POLY_SET poly1;
1139 SHAPE_POLY_SET poly2;
1140
1141 poly1.NewOutline();
1142 poly1.Append( upper );
1143
1144 poly2.NewOutline();
1145 poly2.Append( lower );
1146
1147 if( isCopperOutside( footprint, poly1 ) )
1148 {
1149 wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1150 aOutlines = poly2;
1151 }
1152 else
1153 {
1154 wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1155 aOutlines = poly1;
1156 }
1157
1158 // Add all closed polys as holes to the main outline
1159 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1160 {
1161 wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1162 aOutlines.AddHole( closedChain, -1 );
1163 }
1164
1165 return true;
1166 }
1167
1168 // We really shouldn't reach this point
1169 return false;
1170}
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:77
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:271
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:861
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:847
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:406
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1329
FOOTPRINTS & Footprints()
Definition: board.h:313
const Vec & GetOrigin() const
Definition: box2.h:184
coord_type GetHeight() const
Definition: box2.h:189
coord_type GetWidth() const
Definition: box2.h:188
const Vec GetEnd() const
Definition: box2.h:186
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:507
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:123
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:126
void RebuildBezierToSegmentsPointsList(int aMinSegLen)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
Definition: eda_shape.cpp:475
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:256
int GetRadius() const
Definition: eda_shape.cpp:588
SHAPE_T GetShape() const
Definition: eda_shape.h:117
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:149
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:124
std::vector< VECTOR2I > GetRectCorners() const
Definition: eda_shape.cpp:1105
const std::vector< VECTOR2I > & GetBezierPoints() const
Definition: eda_shape.h:239
wxString SHAPE_T_asString() const
Definition: eda_shape.cpp:87
VECTOR2I GetArcMid() const
Definition: eda_shape.cpp:558
PADS & Pads()
Definition: footprint.h:188
Definition: pad.h:58
VECTOR2I GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition: pcb_shape.h:72
int GetWidth() const override
Definition: pcb_shape.cpp:149
PCB_LAYER_ID GetLayer() const override
Return the primary layer this item is on.
Definition: pcb_shape.h:67
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
Definition: collectors.h:517
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:507
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 override
Check if point aP lies inside a closed shape.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
bool IsClosed() const override
virtual const VECTOR2I GetPoint(int aIndex) const override
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
int PointCount() const
Return the number of points (vertices) in this line chain.
void ClearArcs()
Remove all arc references in the line chain, resulting in a chain formed only of straight segments.
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.
void RemoveAllContours()
Remove all outlines & holes (clears) the polygon set.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index.
bool IsEmpty() const
Return true if the set is empty (no polygons at all)
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
int HoleCount(int aOutline) const
Returns the number of holes in a given outline.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Return the reference to aIndex-th outline in the set.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the reference to aHole-th hole in the aIndex-th outline.
int NewOutline()
Creates a new empty polygon in the set and returns its index.
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
int OutlineCount() const
Return the number of outlines in the set.
SHAPE_POLY_SET CloneDropTriangulation() const
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines 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.
static bool isCopperOutside(const FOOTPRINT *aFootprint, SHAPE_POLY_SET &aShape)
bool ConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aShapeList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER *aErrorHandler, bool aAllowUseArcsInPolygons)
Function ConvertOutlineToPolygon build a polygon set (with holes) from a PCB_SHAPE list,...
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, bool aAllowUseArcsInPolygons)
Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut ...
static 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.
static 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 ...
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.
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:443
#define SKIP_STRUCT
flag indicating that the structure should be ignored
@ ARC
use RECTANGLE instead of RECT to avoid collision in a Windows header
a few functions useful in geometry calculations.
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
@ Edge_Cuts
Definition: layer_ids.h:114
This file contains miscellaneous commonly used macros and functions.
#define UNIMPLEMENTED_FOR(type)
Definition: macros.h:96
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
constexpr int mmToIU(double mm) const
Definition: base_units.h:89
@ PCB_SHAPE_T
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:88