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