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 <unordered_set>
27
28#include <trigo.h>
29#include <macros.h>
30
31#include <math/vector2d.h>
32#include <pcb_shape.h>
33#include <footprint.h>
34#include <pad.h>
35#include <base_units.h>
40#include <board.h>
41#include <collectors.h>
42
43#include <wx/log.h>
44
45
53const wxChar* traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" );
54
55
56class SCOPED_FLAGS_CLEANER : public std::unordered_set<EDA_ITEM*>
57{
59
60public:
61 SCOPED_FLAGS_CLEANER( const EDA_ITEM_FLAGS& aFlagsToClear ) : m_flagsToClear( aFlagsToClear ) {}
62
64 {
65 for( EDA_ITEM* item : *this )
67 }
68};
69
70
79static bool close_enough( VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit )
80{
81 return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
82}
83
84
93static bool closer_to_first( VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond )
94{
95 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
96}
97
98
108static PCB_SHAPE* findNext( PCB_SHAPE* aShape, const VECTOR2I& aPoint,
109 const std::vector<PCB_SHAPE*>& aList, unsigned aLimit )
110{
111 // Look for an unused, exact hit
112 for( PCB_SHAPE* graphic : aList )
113 {
114 if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
115 continue;
116
117 if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
118 return graphic;
119 }
120
121 // Search again for anything that's close, even something already used. (The latter is
122 // important for error reporting.)
123 VECTOR2I pt( aPoint );
124 SEG::ecoord closest_dist_sq = SEG::Square( aLimit );
125 PCB_SHAPE* closest_graphic = nullptr;
126 SEG::ecoord d_sq;
127
128 for( PCB_SHAPE* graphic : aList )
129 {
130 if( graphic == aShape )
131 continue;
132
133 d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
134
135 if( d_sq < closest_dist_sq )
136 {
137 closest_dist_sq = d_sq;
138 closest_graphic = graphic;
139 }
140
141 d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
142
143 if( d_sq < closest_dist_sq )
144 {
145 closest_dist_sq = d_sq;
146 closest_graphic = graphic;
147 }
148 }
149
150 return closest_graphic; // Note: will be nullptr if nothing within aLimit
151}
152
153
154static bool isCopperOutside( const FOOTPRINT* aFootprint, SHAPE_POLY_SET& aShape )
155{
156 bool padOutside = false;
157
158 for( PAD* pad : aFootprint->Pads() )
159 {
161
162 poly.BooleanIntersection( *pad->GetEffectivePolygon( ERROR_INSIDE ),
164
165 if( poly.OutlineCount() == 0 )
166 {
167 VECTOR2I padPos = pad->GetPosition();
168 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): outside" ),
169 padPos.x, padPos.y );
170 padOutside = true;
171 break;
172 }
173
174 VECTOR2I padPos = pad->GetPosition();
175 wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ),
176 padPos.x, padPos.y );
177 }
178
179 return padOutside;
180}
181
182
183bool doConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aShapeList, SHAPE_POLY_SET& aPolygons,
184 int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint,
185 OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons,
186 SCOPED_FLAGS_CLEANER& aCleaner )
187{
188 if( aShapeList.size() == 0 )
189 return true;
190
191 bool selfIntersecting = false;
192
193 wxString msg;
194 PCB_SHAPE* graphic = nullptr;
195
196 std::set<PCB_SHAPE*> startCandidates( aShapeList.begin(), aShapeList.end() );
197
198 // Keep a list of where the various shapes came from so after doing our combined-polygon
199 // tests we can still report errors against the individual graphic items.
200 std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> shapeOwners;
201
202 auto fetchOwner =
203 [&]( const SEG& seg ) -> PCB_SHAPE*
204 {
205 auto it = shapeOwners.find( std::make_pair( seg.A, seg.B ) );
206 return it == shapeOwners.end() ? nullptr : it->second;
207 };
208
209 PCB_SHAPE* prevGraphic = nullptr;
210 VECTOR2I prevPt;
211
212 std::vector<SHAPE_LINE_CHAIN> contours;
213
214 for( PCB_SHAPE* shape : startCandidates )
215 shape->ClearFlags( SKIP_STRUCT );
216
217 while( startCandidates.size() )
218 {
219 graphic = (PCB_SHAPE*) *startCandidates.begin();
220 graphic->SetFlags( SKIP_STRUCT );
221 aCleaner.insert( graphic );
222 startCandidates.erase( startCandidates.begin() );
223
224 contours.emplace_back();
225
226 SHAPE_LINE_CHAIN& currContour = contours.back();
227 currContour.SetWidth( graphic->GetWidth() );
228 bool firstPt = true;
229
230 // Circles, rects and polygons are closed shapes unto themselves (and do not combine
231 // with other shapes), so process them separately.
232 if( graphic->GetShape() == SHAPE_T::POLY )
233 {
234 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
235 {
236 VECTOR2I pt = *it;
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 VECTOR2I center = graphic->GetCenter();
253 int radius = graphic->GetRadius();
254 VECTOR2I start = center;
255 start.x += radius;
256
257 // Add 360 deg Arc in currContour
258 SHAPE_ARC arc360( center, start, ANGLE_360, 0 );
259 currContour.Append( arc360, aErrorMax );
260 currContour.SetClosed( true );
261
262 // set shapeOwners for currContour points created by appending the arc360:
263 for( int ii = 1; ii < currContour.PointCount(); ++ii )
264 {
265 shapeOwners[ std::make_pair( currContour.CPoint( ii-1 ),
266 currContour.CPoint( ii ) ) ] = graphic;
267 }
268
269 if( !aAllowUseArcsInPolygons )
270 currContour.ClearArcs();
271 }
272 else if( graphic->GetShape() == SHAPE_T::RECTANGLE )
273 {
274 std::vector<VECTOR2I> pts = graphic->GetRectCorners();
275
276 for( const VECTOR2I& pt : pts )
277 {
278 currContour.Append( pt );
279
280 if( firstPt )
281 firstPt = false;
282 else
283 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
284
285 prevPt = pt;
286 }
287
288 currContour.SetClosed( true );
289 }
290 else
291 {
292 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
293 // from here.
294 VECTOR2I startPt = graphic->GetEnd();
295 prevPt = startPt;
296 currContour.Append( prevPt );
297
298 // do not append the other end point yet, this first 'graphic' might be an arc
299 for(;;)
300 {
301 switch( graphic->GetShape() )
302 {
304 case SHAPE_T::CIRCLE:
305 {
306 // As a non-first item, closed shapes can't be anything but self-intersecting
307 if( aErrorHandler )
308 {
309 wxASSERT( prevGraphic );
310 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic,
311 prevPt );
312 }
313
314 selfIntersecting = true;
315
316 // A closed shape will finish where it started, so no point in updating prevPt
317 break;
318 }
319
320 case SHAPE_T::SEGMENT:
321 {
322 VECTOR2I nextPt;
323
324 // Use the line segment end point furthest away from prevPt as we assume
325 // the other end to be ON prevPt or very close to it.
326 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
327 nextPt = graphic->GetEnd();
328 else
329 nextPt = graphic->GetStart();
330
331 currContour.Append( nextPt );
332 shapeOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
333 prevPt = nextPt;
334 }
335 break;
336
337 case SHAPE_T::ARC:
338 {
339 VECTOR2I pstart = graphic->GetStart();
340 VECTOR2I pmid = graphic->GetArcMid();
341 VECTOR2I pend = graphic->GetEnd();
342
343 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
344 {
345 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
346
347 std::swap( pstart, pend );
348 }
349
350 SHAPE_ARC sarc( pstart, pmid, pend, 0 );
351
352 SHAPE_LINE_CHAIN arcChain;
353 arcChain.Append( sarc, aErrorMax );
354
355 if( !aAllowUseArcsInPolygons )
356 arcChain.ClearArcs();
357
358 // set shapeOwners for arcChain points created by appending the sarc:
359 for( int ii = 1; ii < arcChain.PointCount(); ++ii )
360 {
361 shapeOwners[std::make_pair( arcChain.CPoint( ii - 1 ),
362 arcChain.CPoint( ii ) )] = graphic;
363 }
364
365 currContour.Append( arcChain );
366
367 prevPt = pend;
368 }
369 break;
370
371 case SHAPE_T::BEZIER:
372 {
373 // We do not support Bezier curves in polygons, so approximate with a series
374 // of short lines and put those line segments into the !same! PATH.
375 VECTOR2I nextPt;
376 bool reverse = false;
377
378 // Use the end point furthest away from prevPt as we assume the other
379 // end to be ON prevPt or very close to it.
380 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
381 {
382 nextPt = graphic->GetEnd();
383 }
384 else
385 {
386 nextPt = graphic->GetStart();
387 reverse = true;
388 }
389
390 // Ensure the approximated Bezier shape is built
391 // a good value is between (Bezier curve width / 2) and (Bezier curve width)
392 // ( and at least 0.05 mm to avoid very small segments)
393 int min_segm_length = std::max( pcbIUScale.mmToIU( 0.05 ),
394 graphic->GetWidth() );
395 graphic->RebuildBezierToSegmentsPointsList( min_segm_length );
396
397 if( reverse )
398 {
399 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
400 {
401 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
402
403 if( prevPt == pt )
404 continue;
405
406 currContour.Append( pt );
407 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
408 prevPt = pt;
409 }
410 }
411 else
412 {
413 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
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
424 prevPt = nextPt;
425 }
426 break;
427
428 default:
430 return false;
431 }
432
433 // Get next closest segment.
434 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
435
436 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
437 {
438 prevGraphic = graphic;
439 graphic = nextGraphic;
440 graphic->SetFlags( SKIP_STRUCT );
441 aCleaner.insert( graphic );
442 startCandidates.erase( graphic );
443 continue;
444 }
445
446 // Finished, or ran into trouble...
447 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
448 {
449 currContour.SetClosed( true );
450 break;
451 }
452 else if( nextGraphic ) // encountered already-used segment, but not at the start
453 {
454 if( aErrorHandler )
455 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic,
456 prevPt );
457
458 break;
459 }
460 else // encountered discontinuity
461 {
462 if( aErrorHandler )
463 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
464
465 break;
466 }
467 }
468 }
469 }
470
471 for( const SHAPE_LINE_CHAIN& contour : contours )
472 {
473 if( !contour.IsClosed() )
474 return false;
475 }
476
477 // First, collect the parents of each contour
478 std::map<int, std::vector<int>> contourToParentIndexesMap;
479
480 for( size_t ii = 0; ii < contours.size(); ++ii )
481 {
482 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
483 std::vector<int> parents;
484
485 for( size_t jj = 0; jj < contours.size(); ++jj )
486 {
487 if( jj == ii )
488 continue;
489
490 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
491
492 if( parentCandidate.PointInside( firstPt ) )
493 parents.push_back( jj );
494 }
495
496 contourToParentIndexesMap[ii] = std::move( parents );
497 }
498
499 // Next add those that are top-level outlines to the SHAPE_POLY_SET
500 std::map<int, int> contourToOutlineIdxMap;
501
502 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
503 {
504 if( parentIndexes.size() %2 == 0 )
505 {
506 // Even number of parents; top-level outline
507 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
508 {
509 if( aErrorHandler )
510 {
511 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
512 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
513
514 if( a && b )
515 {
516 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
517 contours[ contourIndex ].GetPoint( 0 ) );
518
519 return false;
520 }
521 }
522 }
523
524 aPolygons.AddOutline( contours[ contourIndex ] );
525 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
526 }
527 }
528
529 // And finally add the holes
530 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
531 {
532 if( parentIndexes.size() %2 == 1 )
533 {
534 // Odd number of parents; we're a hole in the parent which has one fewer parents
535 // than we have.
536 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
537
538 for( int parentContourIdx : parentIndexes )
539 {
540 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
541 {
542 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
543 aPolygons.AddHole( hole, outlineIdx );
544 break;
545 }
546 }
547 }
548 }
549
550 // All of the silliness that follows is to work around the segment iterator while checking
551 // for collisions.
552 // TODO: Implement proper segment and point iterators that follow std
553 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
554 {
555 auto seg2 = seg1;
556
557 for( ++seg2; seg2; seg2++ )
558 {
559 // Check for exact overlapping segments.
560 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
561 {
562 if( aErrorHandler )
563 {
564 BOARD_ITEM* a = fetchOwner( *seg1 );
565 BOARD_ITEM* b = fetchOwner( *seg2 );
566 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
567 }
568
569 selfIntersecting = true;
570 }
571
572 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
573 {
574 if( aErrorHandler )
575 {
576 BOARD_ITEM* a = fetchOwner( *seg1 );
577 BOARD_ITEM* b = fetchOwner( *seg2 );
578 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
579 }
580
581 selfIntersecting = true;
582 }
583 }
584 }
585
586 return !selfIntersecting;
587}
588
589
590bool ConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aShapeList, SHAPE_POLY_SET& aPolygons,
591 int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint,
592 OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons )
593{
595
596 return doConvertOutlineToPolygon( aShapeList, aPolygons, aErrorMax, aChainingEpsilon,
597 aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons,
598 cleaner );
599}
600
601
602bool TestBoardOutlinesGraphicItems( BOARD* aBoard, int aMinDist,
603 OUTLINE_ERROR_HANDLER* aErrorHandler )
604{
605 bool success = true;
606 PCB_TYPE_COLLECTOR items;
607 int min_dist = std::max( 0, aMinDist );
608
609 // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
610 items.Collect( aBoard, { PCB_SHAPE_T } );
611
612 std::vector<PCB_SHAPE*> segList;
613
614 for( int ii = 0; ii < items.GetCount(); ii++ )
615 {
616 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
617
618 if( seg->GetLayer() == Edge_Cuts )
619 segList.push_back( seg );
620 }
621
622 for( FOOTPRINT* fp : aBoard->Footprints() )
623 {
624 PCB_TYPE_COLLECTOR fpItems;
625 fpItems.Collect( fp, { PCB_SHAPE_T } );
626
627 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
628 {
629 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
630
631 if( fpSeg->GetLayer() == Edge_Cuts )
632 segList.push_back( fpSeg );
633 }
634 }
635
636 // Now Test validity of collected items
637 for( PCB_SHAPE* graphic : segList )
638 {
639 switch( graphic->GetShape() )
640 {
642 {
643 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
644 int dim = seg.EuclideanNorm();
645
646 if( dim <= min_dist )
647 {
648 success = false;
649
650 if( aErrorHandler )
651 {
652 (*aErrorHandler)( wxString::Format( _( "(Rectangle has null or very small "
653 "size: %d nm)" ),
654 dim ),
655 graphic, nullptr, graphic->GetStart() );
656 }
657 }
658 break;
659 }
660
661 case SHAPE_T::CIRCLE:
662 {
663 if( graphic->GetRadius() <= min_dist )
664 {
665 success = false;
666
667 if( aErrorHandler )
668 {
669 (*aErrorHandler)( wxString::Format( _( "(Circle has null or very small "
670 "radius: %d nm)" ),
671 (int)graphic->GetRadius() ),
672 graphic, nullptr, graphic->GetStart() );
673 }
674 }
675 break;
676 }
677
678 case SHAPE_T::SEGMENT:
679 {
680 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
681 int dim = seg.EuclideanNorm();
682
683 if( dim <= min_dist )
684 {
685 success = false;
686
687 if( aErrorHandler )
688 {
689 (*aErrorHandler)( wxString::Format( _( "(Segment has null or very small "
690 "length: %d nm)" ), dim ),
691 graphic, nullptr, graphic->GetStart() );
692 }
693 }
694 break;
695 }
696
697 case SHAPE_T::ARC:
698 {
699 // Arc size can be evaluated from the distance between arc middle point and arc ends
700 // We do not need a precise value, just an idea of its size
701 VECTOR2I arcMiddle = graphic->GetArcMid();
702 VECTOR2I seg1 = arcMiddle - graphic->GetStart();
703 VECTOR2I seg2 = graphic->GetEnd() - arcMiddle;
704 int dim = seg1.EuclideanNorm() + seg2.EuclideanNorm();
705
706 if( dim <= min_dist )
707 {
708 success = false;
709
710 if( aErrorHandler )
711 {
712 (*aErrorHandler)( wxString::Format( _( "(Arc has null or very small size: %d nm)" ), dim ),
713 graphic, nullptr, graphic->GetStart() );
714 }
715 }
716 break;
717 }
718
719 case SHAPE_T::POLY:
720 break;
721
722 case SHAPE_T::BEZIER:
723 break;
724
725 default:
726 UNIMPLEMENTED_FOR( graphic->SHAPE_T_asString() );
727 return false;
728 }
729 }
730
731 return success;
732}
733
734
735bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
736 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler,
737 bool aAllowUseArcsInPolygons )
738{
739 PCB_TYPE_COLLECTOR items;
740 SHAPE_POLY_SET fpHoles;
741 bool success = false;
742
744
745 // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
746 items.Collect( aBoard, { PCB_SHAPE_T } );
747
748 for( int ii = 0; ii < items.GetCount(); ++ii )
749 items[ii]->ClearFlags( SKIP_STRUCT );
750
751 for( FOOTPRINT* fp : aBoard->Footprints() )
752 {
753 PCB_TYPE_COLLECTOR fpItems;
754 fpItems.Collect( fp, { PCB_SHAPE_T } );
755
756 std::vector<PCB_SHAPE*> fpSegList;
757
758 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
759 {
760 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
761
762 if( fpSeg->GetLayer() == Edge_Cuts )
763 fpSegList.push_back( fpSeg );
764 }
765
766 if( !fpSegList.empty() )
767 {
768 SHAPE_POLY_SET fpOutlines;
769 success = doConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon,
770 false,
771 // don't report errors here; the second pass also
772 // gets an opportunity to use these segments
773 nullptr, aAllowUseArcsInPolygons, cleaner );
774
775 // Test to see if we should make holes or outlines. Holes are made if the footprint
776 // has copper outside of a single, closed outline. If there are multiple outlines,
777 // we assume that the footprint edges represent holes as we do not support multiple
778 // boards. Similarly, if any of the footprint pads are located outside of the edges,
779 // then the edges are holes
780 if( success && ( isCopperOutside( fp, fpOutlines ) || fpOutlines.OutlineCount() > 1 ) )
781 {
782 fpHoles.Append( fpOutlines );
783 }
784 else
785 {
786 // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
787 // in contention for the board outline builds.
788 for( int ii = 0; ii < fpItems.GetCount(); ++ii )
789 fpItems[ii]->ClearFlags( SKIP_STRUCT );
790 }
791 }
792 }
793
794 // Make a working copy of aSegList, because the list is modified during calculations
795 std::vector<PCB_SHAPE*> segList;
796
797 for( int ii = 0; ii < items.GetCount(); ii++ )
798 {
799 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
800
801 // Skip anything already used to generate footprint holes (above)
802 if( seg->GetFlags() & SKIP_STRUCT )
803 continue;
804
805 if( seg->GetLayer() == Edge_Cuts )
806 segList.push_back( seg );
807 }
808
809 if( segList.size() )
810 {
811 success = doConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon, true,
812 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
813 }
814
815 if( !success || !aOutlines.OutlineCount() )
816 {
817 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
818 // create a rectangular outline, or, failing that, the bounding box of the items on
819 // the board.
820 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
821
822 // If null area, uses the global bounding box.
823 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
824 bbbox = aBoard->ComputeBoundingBox();
825
826 // Ensure non null area. If happen, gives a minimal size.
827 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
828 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
829
830 aOutlines.RemoveAllContours();
831 aOutlines.NewOutline();
832
833 VECTOR2I corner;
834 aOutlines.Append( bbbox.GetOrigin() );
835
836 corner.x = bbbox.GetOrigin().x;
837 corner.y = bbbox.GetEnd().y;
838 aOutlines.Append( corner );
839
840 aOutlines.Append( bbbox.GetEnd() );
841
842 corner.x = bbbox.GetEnd().x;
843 corner.y = bbbox.GetOrigin().y;
844 aOutlines.Append( corner );
845 }
846
847 for( int ii = 0; ii < fpHoles.OutlineCount(); ++ii )
848 {
849 const VECTOR2I holePt = fpHoles.Outline( ii ).CPoint( 0 );
850
851 for( int jj = 0; jj < aOutlines.OutlineCount(); ++jj )
852 {
853 if( aOutlines.Outline( jj ).PointInside( holePt ) )
854 {
855 aOutlines.AddHole( fpHoles.Outline( ii ), jj );
856 break;
857 }
858 }
859 }
860
861 return success;
862}
863
864
877void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline )
878{
879 BOX2I bbbox = aBoard->GetBoundingBox();
880 SHAPE_LINE_CHAIN chain;
881
882 // If null area, uses the global bounding box.
883 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
884 bbbox = aBoard->ComputeBoundingBox();
885
886 // Ensure non null area. If happen, gives a minimal size.
887 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
888 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
889
890 // Inflate slightly (by 1/10th the size of the box)
891 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
892
893 chain.Append( bbbox.GetOrigin() );
894 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
895 chain.Append( bbbox.GetEnd() );
896 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
897 chain.SetClosed( true );
898
899 aOutline.RemoveAllContours();
900 aOutline.AddOutline( chain );
901}
902
903
904VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
905 int aOutlineNum = 0 )
906{
907 int minDistance = -1;
908 VECTOR2I projPoint;
909
910 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
911 {
912 auto seg = it.Get();
913 int dis = seg.Distance( aEndPoint );
914
915 if( minDistance < 0 || ( dis < minDistance ) )
916 {
917 minDistance = dis;
918 projPoint = seg.NearestPoint( aEndPoint );
919 }
920 }
921
922 return projPoint;
923}
924
925
926int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
927{
928 int foundSegs = 0;
929
930 for( int i = 0; i < aChain.SegmentCount(); i++ )
931 {
932 SEG seg = aChain.Segment( i );
933
934 bool foundA = false;
935 bool foundB = false;
936
937 for( int j = 0; j < aChain.SegmentCount(); j++ )
938 {
939 // Don't test the segment against itself
940 if( i == j )
941 continue;
942
943 SEG testSeg = aChain.Segment( j );
944
945 if( testSeg.Contains( seg.A ) )
946 foundA = true;
947
948 if( testSeg.Contains( seg.B ) )
949 foundB = true;
950 }
951
952 // This segment isn't a start or end
953 if( foundA && foundB )
954 continue;
955
956 if( foundSegs == 0 )
957 {
958 // The first segment we encounter is the "start" segment
959 wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
960 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
961 aStartSeg = seg;
962 foundSegs++;
963 }
964 else
965 {
966 // Once we find both start and end, we can stop
967 wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
968 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
969 aEndSeg = seg;
970 foundSegs++;
971 break;
972 }
973 }
974
975 return foundSegs;
976}
977
978
979bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
980 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
981
982{
983 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
984
985 // No footprint loaded
986 if( !footprint )
987 {
988 wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
989 return false;
990 }
991
992 PCB_TYPE_COLLECTOR items;
993 SHAPE_POLY_SET outlines;
994 bool success = false;
995
997
998 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
999 items.Collect( aBoard, { PCB_SHAPE_T } );
1000
1001 // Make a working copy of aSegList, because the list is modified during calculations
1002 std::vector<PCB_SHAPE*> segList;
1003
1004 for( int ii = 0; ii < items.GetCount(); ii++ )
1005 {
1006 if( items[ii]->GetLayer() == Edge_Cuts )
1007 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
1008 }
1009
1010 if( !segList.empty() )
1011 {
1012 success = doConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon, true,
1013 aErrorHandler, false, cleaner );
1014 }
1015
1016 // A closed outline was found on Edge_Cuts
1017 if( success )
1018 {
1019 wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
1020
1021 // If copper is outside a closed polygon, treat it as a hole
1022 // If there are multiple outlines in the footprint, they are also holes
1023 if( isCopperOutside( footprint, outlines ) || outlines.OutlineCount() > 1 )
1024 {
1025 wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
1026
1027 buildBoardBoundingBoxPoly( aBoard, aOutlines );
1028
1029 // Copy all outlines from the conversion as holes into the new outline
1030 for( int i = 0; i < outlines.OutlineCount(); i++ )
1031 {
1032 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
1033
1034 if( out.IsClosed() )
1035 aOutlines.AddHole( out, -1 );
1036
1037 for( int j = 0; j < outlines.HoleCount( i ); j++ )
1038 {
1039 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
1040
1041 if( hole.IsClosed() )
1042 aOutlines.AddHole( hole, -1 );
1043 }
1044 }
1045 }
1046 // If all copper is inside, then the computed outline is the board outline
1047 else
1048 {
1049 wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
1050 aOutlines = outlines;
1051 }
1052
1053 return true;
1054 }
1055 // No board outlines were found, so use the bounding box
1056 else if( outlines.OutlineCount() == 0 )
1057 {
1058 wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
1059 buildBoardBoundingBoxPoly( aBoard, aOutlines );
1060
1061 return true;
1062 }
1063 // There is an outline present, but it is not closed
1064 else
1065 {
1066 wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
1067
1068 std::vector<SHAPE_LINE_CHAIN> closedChains;
1069 std::vector<SHAPE_LINE_CHAIN> openChains;
1070
1071 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
1072 // holes, so we promote the holes and process them
1073 openChains.push_back( outlines.Outline( 0 ) );
1074
1075 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
1076 {
1077 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
1078
1079 if( hole.IsClosed() )
1080 {
1081 wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
1082 closedChains.push_back( hole );
1083 }
1084 else
1085 {
1086 wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
1087 openChains.push_back( hole );
1088 }
1089 }
1090
1091 SHAPE_POLY_SET bbox;
1092 buildBoardBoundingBoxPoly( aBoard, bbox );
1093
1094 // Treat the open polys as the board edge
1095 SHAPE_LINE_CHAIN chain = openChains[0];
1096 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
1097
1098 // We know the outline chain is open, so set to non-closed to get better segment count
1099 chain.SetClosed( false );
1100
1101 SEG startSeg;
1102 SEG endSeg;
1103
1104 // The two possible board outlines
1105 SHAPE_LINE_CHAIN upper;
1106 SHAPE_LINE_CHAIN lower;
1107
1108 findEndSegments( chain, startSeg, endSeg );
1109
1110 if( chain.SegmentCount() == 0 )
1111 {
1112 // Something is wrong, bail out with the overall footprint bounding box
1113 wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
1114 aOutlines = bbox;
1115 return true;
1116 }
1117 else if( chain.SegmentCount() == 1 )
1118 {
1119 // This case means there is only 1 line segment making up the edge cuts of the
1120 // footprint, so we just need to use it to cut the bounding box in half.
1121 wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
1122
1123 startSeg = chain.Segment( 0 );
1124
1125 // Intersect with all the sides of the rectangle
1126 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
1127 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
1128 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1129 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1130
1131 if( inter0 && inter2 && !inter1 && !inter3 )
1132 {
1133 // Intersects the vertical rectangle sides only
1134 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1135 "sides" ) );
1136
1137 // The upper half
1138 upper.Append( *inter0 );
1139 upper.Append( rect.GetPoint( 1 ) );
1140 upper.Append( rect.GetPoint( 2 ) );
1141 upper.Append( *inter2 );
1142 upper.SetClosed( true );
1143
1144 // The lower half
1145 lower.Append( *inter0 );
1146 lower.Append( rect.GetPoint( 0 ) );
1147 lower.Append( rect.GetPoint( 3 ) );
1148 lower.Append( *inter2 );
1149 lower.SetClosed( true );
1150 }
1151 else if( inter1 && inter3 && !inter0 && !inter2 )
1152 {
1153 // Intersects the horizontal rectangle sides only
1154 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1155 "sides" ) );
1156
1157 // The left half
1158 upper.Append( *inter1 );
1159 upper.Append( rect.GetPoint( 1 ) );
1160 upper.Append( rect.GetPoint( 0 ) );
1161 upper.Append( *inter3 );
1162 upper.SetClosed( true );
1163
1164 // The right half
1165 lower.Append( *inter1 );
1166 lower.Append( rect.GetPoint( 2 ) );
1167 lower.Append( rect.GetPoint( 3 ) );
1168 lower.Append( *inter3 );
1169 lower.SetClosed( true );
1170 }
1171 else
1172 {
1173 // Angled line segment that cuts across a corner
1174 wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1175 "sides" ) );
1176
1177 // Figure out which actual lines are intersected, since IntersectLines assumes
1178 // an infinite line
1179 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1180 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1181 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1182 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1183
1184 if( hit0 && hit1 )
1185 {
1186 // Cut across the upper left corner
1187 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1188
1189 // The upper half
1190 upper.Append( *inter0 );
1191 upper.Append( rect.GetPoint( 1 ) );
1192 upper.Append( *inter1 );
1193 upper.SetClosed( true );
1194
1195 // The lower half
1196 lower.Append( *inter0 );
1197 lower.Append( rect.GetPoint( 0 ) );
1198 lower.Append( rect.GetPoint( 3 ) );
1199 lower.Append( rect.GetPoint( 2 ) );
1200 lower.Append( *inter1 );
1201 lower.SetClosed( true );
1202 }
1203 else if( hit1 && hit2 )
1204 {
1205 // Cut across the upper right corner
1206 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1207
1208 // The upper half
1209 upper.Append( *inter1 );
1210 upper.Append( rect.GetPoint( 2 ) );
1211 upper.Append( *inter2 );
1212 upper.SetClosed( true );
1213
1214 // The lower half
1215 lower.Append( *inter1 );
1216 lower.Append( rect.GetPoint( 1 ) );
1217 lower.Append( rect.GetPoint( 0 ) );
1218 lower.Append( rect.GetPoint( 3 ) );
1219 lower.Append( *inter2 );
1220 lower.SetClosed( true );
1221 }
1222 else if( hit2 && hit3 )
1223 {
1224 // Cut across the lower right corner
1225 wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1226
1227 // The upper half
1228 upper.Append( *inter2 );
1229 upper.Append( rect.GetPoint( 2 ) );
1230 upper.Append( rect.GetPoint( 1 ) );
1231 upper.Append( rect.GetPoint( 0 ) );
1232 upper.Append( *inter3 );
1233 upper.SetClosed( true );
1234
1235 // The bottom half
1236 lower.Append( *inter2 );
1237 lower.Append( rect.GetPoint( 3 ) );
1238 lower.Append( *inter3 );
1239 lower.SetClosed( true );
1240 }
1241 else
1242 {
1243 // Cut across the lower left corner
1244 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1245
1246 // The upper half
1247 upper.Append( *inter0 );
1248 upper.Append( rect.GetPoint( 1 ) );
1249 upper.Append( rect.GetPoint( 2 ) );
1250 upper.Append( rect.GetPoint( 3 ) );
1251 upper.Append( *inter3 );
1252 upper.SetClosed( true );
1253
1254 // The bottom half
1255 lower.Append( *inter0 );
1256 lower.Append( rect.GetPoint( 0 ) );
1257 lower.Append( *inter3 );
1258 lower.SetClosed( true );
1259 }
1260 }
1261 }
1262 else
1263 {
1264 // More than 1 segment
1265 wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1266
1267 // Just a temporary thing
1268 aOutlines = bbox;
1269 return true;
1270 }
1271
1272 // Figure out which is the correct outline
1273 SHAPE_POLY_SET poly1;
1274 SHAPE_POLY_SET poly2;
1275
1276 poly1.NewOutline();
1277 poly1.Append( upper );
1278
1279 poly2.NewOutline();
1280 poly2.Append( lower );
1281
1282 if( isCopperOutside( footprint, poly1 ) )
1283 {
1284 wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1285 aOutlines = poly2;
1286 }
1287 else
1288 {
1289 wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1290 aOutlines = poly1;
1291 }
1292
1293 // Add all closed polys as holes to the main outline
1294 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1295 {
1296 wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1297 aOutlines.AddHole( closedChain, -1 );
1298 }
1299
1300 return true;
1301 }
1302
1303 // We really shouldn't reach this point
1304 return false;
1305}
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:276
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:890
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:876
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:414
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1365
FOOTPRINTS & Footprints()
Definition: board.h:318
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
A base class for most all the KiCad significant classes used in schematics and boards.
Definition: eda_item.h:85
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:123
void ClearFlags(EDA_ITEM_FLAGS aMask=EDA_ITEM_ALL_FLAGS)
Definition: eda_item.h:125
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:473
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:263
int GetRadius() const
Definition: eda_shape.cpp:586
SHAPE_T GetShape() const
Definition: eda_shape.h:119
const VECTOR2I & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:151
const VECTOR2I & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:126
std::vector< VECTOR2I > GetRectCorners() const
Definition: eda_shape.cpp:1132
const std::vector< VECTOR2I > & GetBezierPoints() const
Definition: eda_shape.h:246
wxString SHAPE_T_asString() const
Definition: eda_shape.cpp:87
VECTOR2I GetArcMid() const
Definition: eda_shape.cpp:556
PADS & Pads()
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: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:523
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:509
SCOPED_FLAGS_CLEANER(const EDA_ITEM_FLAGS &aFlagsToClear)
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.
SEG Segment(int aIndex) const
Return a copy of the aIndex-th segment in the line chain.
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.
void SetWidth(int aWidth)
Set the width of all segments in the 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)
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:265
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)
Search 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)
Build a polygon set with holes from a PCB_SHAPE list.
bool TestBoardOutlinesGraphicItems(BOARD *aBoard, int aMinDist, OUTLINE_ERROR_HANDLER *aErrorHandler)
Test a board graphic items on edge cut layer for validity.
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)
Extract the board outlines and build a closed polygon from lines, arcs and circle items on edge cut l...
static bool close_enough(VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
Local and tunable method of qualifying the proximity of two points.
static bool closer_to_first(VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
Local method which qualifies whether the start or end point of a segment is closest to a point.
bool BuildFootprintPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
Extract a board outline for a footprint view.
bool doConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aShapeList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint, OUTLINE_ERROR_HANDLER *aErrorHandler, bool aAllowUseArcsInPolygons, SCOPED_FLAGS_CLEANER &aCleaner)
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:441
#define SKIP_STRUCT
flag indicating that the structure should be ignored
std::uint32_t EDA_ITEM_FLAGS
@ ARC
use RECTANGLE instead of RECT to avoid collision in a Windows header
a few functions useful in geometry calculations.
@ ERROR_INSIDE
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