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
398 // a good value is between (Bezier curve width / 2) and (Bezier curve width)
399 // ( and at least 0.05 mm to avoid very small segments)
400 int min_segm_length = std::max( pcbIUScale.mmToIU( 0.05 ),
401 graphic->GetWidth() );
402 graphic->RebuildBezierToSegmentsPointsList( min_segm_length );
403
404 if( reverse )
405 {
406 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
407 {
408 const VECTOR2I& pt = graphic->GetBezierPoints()[jj];
409
410 if( prevPt == pt )
411 continue;
412
413 currContour.Append( pt );
414 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
415 prevPt = pt;
416 }
417 }
418 else
419 {
420 for( const VECTOR2I& pt : graphic->GetBezierPoints() )
421 {
422 if( prevPt == pt )
423 continue;
424
425 currContour.Append( pt );
426 shapeOwners[ std::make_pair( prevPt, pt ) ] = graphic;
427 prevPt = pt;
428 }
429 }
430
431 prevPt = nextPt;
432 }
433 break;
434
435 default:
437 return false;
438 }
439
440 // Get next closest segment.
441 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aShapeList, aChainingEpsilon );
442
443 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
444 {
445 prevGraphic = graphic;
446 graphic = nextGraphic;
447 graphic->SetFlags( SKIP_STRUCT );
448 aCleaner.insert( graphic );
449 startCandidates.erase( graphic );
450 continue;
451 }
452
453 // Finished, or ran into trouble...
454 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
455 {
456 currContour.SetClosed( true );
457 break;
458 }
459 else if( nextGraphic ) // encountered already-used segment, but not at the start
460 {
461 if( aErrorHandler )
462 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic,
463 prevPt );
464
465 break;
466 }
467 else // encountered discontinuity
468 {
469 if( aErrorHandler )
470 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
471
472 break;
473 }
474 }
475 }
476 }
477
478 for( const SHAPE_LINE_CHAIN& contour : contours )
479 {
480 if( !contour.IsClosed() )
481 return false;
482 }
483
484 // First, collect the parents of each contour
485 std::map<int, std::vector<int>> contourToParentIndexesMap;
486
487 for( size_t ii = 0; ii < contours.size(); ++ii )
488 {
489 VECTOR2I firstPt = contours[ii].GetPoint( 0 );
490 std::vector<int> parents;
491
492 for( size_t jj = 0; jj < contours.size(); ++jj )
493 {
494 if( jj == ii )
495 continue;
496
497 const SHAPE_LINE_CHAIN& parentCandidate = contours[jj];
498
499 if( parentCandidate.PointInside( firstPt ) )
500 parents.push_back( jj );
501 }
502
503 contourToParentIndexesMap[ii] = std::move( parents );
504 }
505
506 // Next add those that are top-level outlines to the SHAPE_POLY_SET
507 std::map<int, int> contourToOutlineIdxMap;
508
509 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
510 {
511 if( parentIndexes.size() %2 == 0 )
512 {
513 // Even number of parents; top-level outline
514 if( !aAllowDisjoint && !aPolygons.IsEmpty() )
515 {
516 if( aErrorHandler )
517 {
518 BOARD_ITEM* a = fetchOwner( aPolygons.Outline( 0 ).GetSegment( 0 ) );
519 BOARD_ITEM* b = fetchOwner( contours[ contourIndex ].GetSegment( 0 ) );
520
521 if( a && b )
522 {
523 (*aErrorHandler)( _( "(multiple board outlines not supported)" ), a, b,
524 contours[ contourIndex ].GetPoint( 0 ) );
525
526 return false;
527 }
528 }
529 }
530
531 aPolygons.AddOutline( contours[ contourIndex ] );
532 contourToOutlineIdxMap[ contourIndex ] = aPolygons.OutlineCount() - 1;
533 }
534 }
535
536 // And finally add the holes
537 for( const auto& [ contourIndex, parentIndexes ] : contourToParentIndexesMap )
538 {
539 if( parentIndexes.size() %2 == 1 )
540 {
541 // Odd number of parents; we're a hole in the parent which has one fewer parents
542 // than we have.
543 const SHAPE_LINE_CHAIN& hole = contours[ contourIndex ];
544
545 for( int parentContourIdx : parentIndexes )
546 {
547 if( contourToParentIndexesMap[ parentContourIdx ].size() == parentIndexes.size() - 1 )
548 {
549 int outlineIdx = contourToOutlineIdxMap[ parentContourIdx ];
550 aPolygons.AddHole( hole, outlineIdx );
551 break;
552 }
553 }
554 }
555 }
556
557 // All of the silliness that follows is to work around the segment iterator while checking
558 // for collisions.
559 // TODO: Implement proper segment and point iterators that follow std
560 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
561 {
562 auto seg2 = seg1;
563
564 for( ++seg2; seg2; seg2++ )
565 {
566 // Check for exact overlapping segments.
567 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
568 {
569 if( aErrorHandler )
570 {
571 BOARD_ITEM* a = fetchOwner( *seg1 );
572 BOARD_ITEM* b = fetchOwner( *seg2 );
573 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, ( *seg1 ).A );
574 }
575
576 selfIntersecting = true;
577 }
578
579 if( OPT_VECTOR2I pt = seg1.Get().Intersect( seg2.Get(), true ) )
580 {
581 if( aErrorHandler )
582 {
583 BOARD_ITEM* a = fetchOwner( *seg1 );
584 BOARD_ITEM* b = fetchOwner( *seg2 );
585 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, *pt );
586 }
587
588 selfIntersecting = true;
589 }
590 }
591 }
592
593 return !selfIntersecting;
594}
595
596
597bool ConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aShapeList, SHAPE_POLY_SET& aPolygons,
598 int aErrorMax, int aChainingEpsilon, bool aAllowDisjoint,
599 OUTLINE_ERROR_HANDLER* aErrorHandler, bool aAllowUseArcsInPolygons )
600{
602
603 return doConvertOutlineToPolygon( aShapeList, aPolygons, aErrorMax, aChainingEpsilon,
604 aAllowDisjoint, aErrorHandler, aAllowUseArcsInPolygons,
605 cleaner );
606}
607
608
609bool TestBoardOutlinesGraphicItems( BOARD* aBoard, int aMinDist,
610 OUTLINE_ERROR_HANDLER* aErrorHandler )
611{
612 bool success = true;
613 PCB_TYPE_COLLECTOR items;
614 int min_dist = std::max( 0, aMinDist );
615
616 // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
617 items.Collect( aBoard, { PCB_SHAPE_T } );
618
619 std::vector<PCB_SHAPE*> segList;
620
621 for( int ii = 0; ii < items.GetCount(); ii++ )
622 {
623 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
624
625 if( seg->GetLayer() == Edge_Cuts )
626 segList.push_back( seg );
627 }
628
629 for( FOOTPRINT* fp : aBoard->Footprints() )
630 {
631 PCB_TYPE_COLLECTOR fpItems;
632 fpItems.Collect( fp, { PCB_SHAPE_T } );
633
634 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
635 {
636 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
637
638 if( fpSeg->GetLayer() == Edge_Cuts )
639 segList.push_back( fpSeg );
640 }
641 }
642
643 // Now Test validity of collected items
644 for( PCB_SHAPE* graphic : segList )
645 {
646 switch( graphic->GetShape() )
647 {
649 {
650 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
651 int dim = seg.EuclideanNorm();
652
653 if( dim <= min_dist )
654 {
655 success = false;
656
657 if( aErrorHandler )
658 {
659 (*aErrorHandler)( wxString::Format( _( "(Rectangle has null or very small "
660 "size: %d nm)" ),
661 dim ),
662 graphic, nullptr, graphic->GetStart() );
663 }
664 }
665 break;
666 }
667
668 case SHAPE_T::CIRCLE:
669 {
670 if( graphic->GetRadius() <= min_dist )
671 {
672 success = false;
673
674 if( aErrorHandler )
675 {
676 (*aErrorHandler)( wxString::Format( _( "(Circle has null or very small "
677 "radius: %d nm)" ),
678 (int)graphic->GetRadius() ),
679 graphic, nullptr, graphic->GetStart() );
680 }
681 }
682 break;
683 }
684
685 case SHAPE_T::SEGMENT:
686 {
687 VECTOR2I seg = graphic->GetEnd() - graphic->GetStart();
688 int dim = seg.EuclideanNorm();
689
690 if( dim <= min_dist )
691 {
692 success = false;
693
694 if( aErrorHandler )
695 {
696 (*aErrorHandler)( wxString::Format( _( "(Segment has null or very small "
697 "length: %d nm)" ), dim ),
698 graphic, nullptr, graphic->GetStart() );
699 }
700 }
701 break;
702 }
703
704 case SHAPE_T::ARC:
705 {
706 // Arc size can be evaluated from the distance between arc middle point and arc ends
707 // We do not need a precise value, just an idea of its size
708 VECTOR2I arcMiddle = graphic->GetArcMid();
709 VECTOR2I seg1 = arcMiddle - graphic->GetStart();
710 VECTOR2I seg2 = graphic->GetEnd() - arcMiddle;
711 int dim = seg1.EuclideanNorm() + seg2.EuclideanNorm();
712
713 if( dim <= min_dist )
714 {
715 success = false;
716
717 if( aErrorHandler )
718 {
719 (*aErrorHandler)( wxString::Format( _( "(Arc has null or very small size: %d nm)" ), dim ),
720 graphic, nullptr, graphic->GetStart() );
721 }
722 }
723 break;
724 }
725
726 case SHAPE_T::POLY:
727 break;
728
729 case SHAPE_T::BEZIER:
730 break;
731
732 default:
733 UNIMPLEMENTED_FOR( graphic->SHAPE_T_asString() );
734 return false;
735 }
736 }
737
738 return success;
739}
740
741
742bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
743 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler,
744 bool aAllowUseArcsInPolygons )
745{
746 PCB_TYPE_COLLECTOR items;
747 SHAPE_POLY_SET fpHoles;
748 bool success = false;
749
751
752 // Get all the shapes into 'items', then keep only those on layer == Edge_Cuts.
753 items.Collect( aBoard, { PCB_SHAPE_T } );
754
755 for( int ii = 0; ii < items.GetCount(); ++ii )
756 items[ii]->ClearFlags( SKIP_STRUCT );
757
758 for( FOOTPRINT* fp : aBoard->Footprints() )
759 {
760 PCB_TYPE_COLLECTOR fpItems;
761 fpItems.Collect( fp, { PCB_SHAPE_T } );
762
763 std::vector<PCB_SHAPE*> fpSegList;
764
765 for( int ii = 0; ii < fpItems.GetCount(); ii++ )
766 {
767 PCB_SHAPE* fpSeg = static_cast<PCB_SHAPE*>( fpItems[ii] );
768
769 if( fpSeg->GetLayer() == Edge_Cuts )
770 fpSegList.push_back( fpSeg );
771 }
772
773 if( !fpSegList.empty() )
774 {
775 SHAPE_POLY_SET fpOutlines;
776 success = doConvertOutlineToPolygon( fpSegList, fpOutlines, aErrorMax, aChainingEpsilon,
777 false,
778 // don't report errors here; the second pass also
779 // gets an opportunity to use these segments
780 nullptr, aAllowUseArcsInPolygons, cleaner );
781
782 // Test to see if we should make holes or outlines. Holes are made if the footprint
783 // has copper outside of a single, closed outline. If there are multiple outlines,
784 // we assume that the footprint edges represent holes as we do not support multiple
785 // boards. Similarly, if any of the footprint pads are located outside of the edges,
786 // then the edges are holes
787 if( success && ( isCopperOutside( fp, fpOutlines ) || fpOutlines.OutlineCount() > 1 ) )
788 {
789 fpHoles.Append( fpOutlines );
790 }
791 else
792 {
793 // If it wasn't a closed area, or wasn't a hole, the we want to keep the fpSegs
794 // in contention for the board outline builds.
795 for( int ii = 0; ii < fpItems.GetCount(); ++ii )
796 fpItems[ii]->ClearFlags( SKIP_STRUCT );
797 }
798 }
799 }
800
801 // Make a working copy of aSegList, because the list is modified during calculations
802 std::vector<PCB_SHAPE*> segList;
803
804 for( int ii = 0; ii < items.GetCount(); ii++ )
805 {
806 PCB_SHAPE* seg = static_cast<PCB_SHAPE*>( items[ii] );
807
808 // Skip anything already used to generate footprint holes (above)
809 if( seg->GetFlags() & SKIP_STRUCT )
810 continue;
811
812 if( seg->GetLayer() == Edge_Cuts )
813 segList.push_back( seg );
814 }
815
816 if( segList.size() )
817 {
818 success = doConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon, true,
819 aErrorHandler, aAllowUseArcsInPolygons, cleaner );
820 }
821
822 if( !success || !aOutlines.OutlineCount() )
823 {
824 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
825 // create a rectangular outline, or, failing that, the bounding box of the items on
826 // the board.
827 BOX2I bbbox = aBoard->GetBoardEdgesBoundingBox();
828
829 // If null area, uses the global bounding box.
830 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
831 bbbox = aBoard->ComputeBoundingBox( false, false );
832
833 // Ensure non null area. If happen, gives a minimal size.
834 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
835 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
836
837 aOutlines.RemoveAllContours();
838 aOutlines.NewOutline();
839
840 VECTOR2I corner;
841 aOutlines.Append( bbbox.GetOrigin() );
842
843 corner.x = bbbox.GetOrigin().x;
844 corner.y = bbbox.GetEnd().y;
845 aOutlines.Append( corner );
846
847 aOutlines.Append( bbbox.GetEnd() );
848
849 corner.x = bbbox.GetEnd().x;
850 corner.y = bbbox.GetOrigin().y;
851 aOutlines.Append( corner );
852 }
853
854 for( int ii = 0; ii < fpHoles.OutlineCount(); ++ii )
855 {
856 const VECTOR2I holePt = fpHoles.Outline( ii ).CPoint( 0 );
857
858 for( int jj = 0; jj < aOutlines.OutlineCount(); ++jj )
859 {
860 if( aOutlines.Outline( jj ).PointInside( holePt ) )
861 {
862 aOutlines.AddHole( fpHoles.Outline( ii ), jj );
863 break;
864 }
865 }
866 }
867
868 return success;
869}
870
871
884void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline )
885{
886 BOX2I bbbox = aBoard->GetBoundingBox();
887 SHAPE_LINE_CHAIN chain;
888
889 // If null area, uses the global bounding box.
890 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
891 bbbox = aBoard->ComputeBoundingBox( false, false );
892
893 // Ensure non null area. If happen, gives a minimal size.
894 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
895 bbbox.Inflate( pcbIUScale.mmToIU( 1.0 ) );
896
897 // Inflate slightly (by 1/10th the size of the box)
898 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
899
900 chain.Append( bbbox.GetOrigin() );
901 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
902 chain.Append( bbbox.GetEnd() );
903 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
904 chain.SetClosed( true );
905
906 aOutline.RemoveAllContours();
907 aOutline.AddOutline( chain );
908}
909
910
911VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
912 int aOutlineNum = 0 )
913{
914 int minDistance = -1;
915 VECTOR2I projPoint;
916
917 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
918 {
919 auto seg = it.Get();
920 int dis = seg.Distance( aEndPoint );
921
922 if( minDistance < 0 || ( dis < minDistance ) )
923 {
924 minDistance = dis;
925 projPoint = seg.NearestPoint( aEndPoint );
926 }
927 }
928
929 return projPoint;
930}
931
932
933int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
934{
935 int foundSegs = 0;
936
937 for( int i = 0; i < aChain.SegmentCount(); i++ )
938 {
939 SEG seg = aChain.Segment( i );
940
941 bool foundA = false;
942 bool foundB = false;
943
944 for( int j = 0; j < aChain.SegmentCount(); j++ )
945 {
946 // Don't test the segment against itself
947 if( i == j )
948 continue;
949
950 SEG testSeg = aChain.Segment( j );
951
952 if( testSeg.Contains( seg.A ) )
953 foundA = true;
954
955 if( testSeg.Contains( seg.B ) )
956 foundB = true;
957 }
958
959 // This segment isn't a start or end
960 if( foundA && foundB )
961 continue;
962
963 if( foundSegs == 0 )
964 {
965 // The first segment we encounter is the "start" segment
966 wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
967 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
968 aStartSeg = seg;
969 foundSegs++;
970 }
971 else
972 {
973 // Once we find both start and end, we can stop
974 wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
975 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
976 aEndSeg = seg;
977 foundSegs++;
978 break;
979 }
980 }
981
982 return foundSegs;
983}
984
985
986bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
987 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
988
989{
990 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
991
992 // No footprint loaded
993 if( !footprint )
994 {
995 wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
996 return false;
997 }
998
999 PCB_TYPE_COLLECTOR items;
1000 SHAPE_POLY_SET outlines;
1001 bool success = false;
1002
1004
1005 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
1006 items.Collect( aBoard, { PCB_SHAPE_T } );
1007
1008 // Make a working copy of aSegList, because the list is modified during calculations
1009 std::vector<PCB_SHAPE*> segList;
1010
1011 for( int ii = 0; ii < items.GetCount(); ii++ )
1012 {
1013 if( items[ii]->GetLayer() == Edge_Cuts )
1014 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
1015 }
1016
1017 if( !segList.empty() )
1018 {
1019 success = doConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon, true,
1020 aErrorHandler, false, cleaner );
1021 }
1022
1023 // A closed outline was found on Edge_Cuts
1024 if( success )
1025 {
1026 wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
1027
1028 // If copper is outside a closed polygon, treat it as a hole
1029 // If there are multiple outlines in the footprint, they are also holes
1030 if( isCopperOutside( footprint, outlines ) || outlines.OutlineCount() > 1 )
1031 {
1032 wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
1033
1034 buildBoardBoundingBoxPoly( aBoard, aOutlines );
1035
1036 // Copy all outlines from the conversion as holes into the new outline
1037 for( int i = 0; i < outlines.OutlineCount(); i++ )
1038 {
1039 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
1040
1041 if( out.IsClosed() )
1042 aOutlines.AddHole( out, -1 );
1043
1044 for( int j = 0; j < outlines.HoleCount( i ); j++ )
1045 {
1046 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
1047
1048 if( hole.IsClosed() )
1049 aOutlines.AddHole( hole, -1 );
1050 }
1051 }
1052 }
1053 // If all copper is inside, then the computed outline is the board outline
1054 else
1055 {
1056 wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
1057 aOutlines = outlines;
1058 }
1059
1060 return true;
1061 }
1062 // No board outlines were found, so use the bounding box
1063 else if( outlines.OutlineCount() == 0 )
1064 {
1065 wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
1066 buildBoardBoundingBoxPoly( aBoard, aOutlines );
1067
1068 return true;
1069 }
1070 // There is an outline present, but it is not closed
1071 else
1072 {
1073 wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
1074
1075 std::vector<SHAPE_LINE_CHAIN> closedChains;
1076 std::vector<SHAPE_LINE_CHAIN> openChains;
1077
1078 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
1079 // holes, so we promote the holes and process them
1080 openChains.push_back( outlines.Outline( 0 ) );
1081
1082 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
1083 {
1084 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
1085
1086 if( hole.IsClosed() )
1087 {
1088 wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
1089 closedChains.push_back( hole );
1090 }
1091 else
1092 {
1093 wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
1094 openChains.push_back( hole );
1095 }
1096 }
1097
1098 SHAPE_POLY_SET bbox;
1099 buildBoardBoundingBoxPoly( aBoard, bbox );
1100
1101 // Treat the open polys as the board edge
1102 SHAPE_LINE_CHAIN chain = openChains[0];
1103 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
1104
1105 // We know the outline chain is open, so set to non-closed to get better segment count
1106 chain.SetClosed( false );
1107
1108 SEG startSeg;
1109 SEG endSeg;
1110
1111 // The two possible board outlines
1112 SHAPE_LINE_CHAIN upper;
1113 SHAPE_LINE_CHAIN lower;
1114
1115 findEndSegments( chain, startSeg, endSeg );
1116
1117 if( chain.SegmentCount() == 0 )
1118 {
1119 // Something is wrong, bail out with the overall footprint bounding box
1120 wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
1121 aOutlines = bbox;
1122 return true;
1123 }
1124 else if( chain.SegmentCount() == 1 )
1125 {
1126 // This case means there is only 1 line segment making up the edge cuts of the
1127 // footprint, so we just need to use it to cut the bounding box in half.
1128 wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
1129
1130 startSeg = chain.Segment( 0 );
1131
1132 // Intersect with all the sides of the rectangle
1133 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
1134 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
1135 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1136 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1137
1138 if( inter0 && inter2 && !inter1 && !inter3 )
1139 {
1140 // Intersects the vertical rectangle sides only
1141 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1142 "sides" ) );
1143
1144 // The upper half
1145 upper.Append( *inter0 );
1146 upper.Append( rect.GetPoint( 1 ) );
1147 upper.Append( rect.GetPoint( 2 ) );
1148 upper.Append( *inter2 );
1149 upper.SetClosed( true );
1150
1151 // The lower half
1152 lower.Append( *inter0 );
1153 lower.Append( rect.GetPoint( 0 ) );
1154 lower.Append( rect.GetPoint( 3 ) );
1155 lower.Append( *inter2 );
1156 lower.SetClosed( true );
1157 }
1158 else if( inter1 && inter3 && !inter0 && !inter2 )
1159 {
1160 // Intersects the horizontal rectangle sides only
1161 wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1162 "sides" ) );
1163
1164 // The left half
1165 upper.Append( *inter1 );
1166 upper.Append( rect.GetPoint( 1 ) );
1167 upper.Append( rect.GetPoint( 0 ) );
1168 upper.Append( *inter3 );
1169 upper.SetClosed( true );
1170
1171 // The right half
1172 lower.Append( *inter1 );
1173 lower.Append( rect.GetPoint( 2 ) );
1174 lower.Append( rect.GetPoint( 3 ) );
1175 lower.Append( *inter3 );
1176 lower.SetClosed( true );
1177 }
1178 else
1179 {
1180 // Angled line segment that cuts across a corner
1181 wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1182 "sides" ) );
1183
1184 // Figure out which actual lines are intersected, since IntersectLines assumes
1185 // an infinite line
1186 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1187 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1188 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1189 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1190
1191 if( hit0 && hit1 )
1192 {
1193 // Cut across the upper left corner
1194 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1195
1196 // The upper half
1197 upper.Append( *inter0 );
1198 upper.Append( rect.GetPoint( 1 ) );
1199 upper.Append( *inter1 );
1200 upper.SetClosed( true );
1201
1202 // The lower half
1203 lower.Append( *inter0 );
1204 lower.Append( rect.GetPoint( 0 ) );
1205 lower.Append( rect.GetPoint( 3 ) );
1206 lower.Append( rect.GetPoint( 2 ) );
1207 lower.Append( *inter1 );
1208 lower.SetClosed( true );
1209 }
1210 else if( hit1 && hit2 )
1211 {
1212 // Cut across the upper right corner
1213 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1214
1215 // The upper half
1216 upper.Append( *inter1 );
1217 upper.Append( rect.GetPoint( 2 ) );
1218 upper.Append( *inter2 );
1219 upper.SetClosed( true );
1220
1221 // The lower half
1222 lower.Append( *inter1 );
1223 lower.Append( rect.GetPoint( 1 ) );
1224 lower.Append( rect.GetPoint( 0 ) );
1225 lower.Append( rect.GetPoint( 3 ) );
1226 lower.Append( *inter2 );
1227 lower.SetClosed( true );
1228 }
1229 else if( hit2 && hit3 )
1230 {
1231 // Cut across the lower right corner
1232 wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1233
1234 // The upper half
1235 upper.Append( *inter2 );
1236 upper.Append( rect.GetPoint( 2 ) );
1237 upper.Append( rect.GetPoint( 1 ) );
1238 upper.Append( rect.GetPoint( 0 ) );
1239 upper.Append( *inter3 );
1240 upper.SetClosed( true );
1241
1242 // The bottom half
1243 lower.Append( *inter2 );
1244 lower.Append( rect.GetPoint( 3 ) );
1245 lower.Append( *inter3 );
1246 lower.SetClosed( true );
1247 }
1248 else
1249 {
1250 // Cut across the lower left corner
1251 wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1252
1253 // The upper half
1254 upper.Append( *inter0 );
1255 upper.Append( rect.GetPoint( 1 ) );
1256 upper.Append( rect.GetPoint( 2 ) );
1257 upper.Append( rect.GetPoint( 3 ) );
1258 upper.Append( *inter3 );
1259 upper.SetClosed( true );
1260
1261 // The bottom half
1262 lower.Append( *inter0 );
1263 lower.Append( rect.GetPoint( 0 ) );
1264 lower.Append( *inter3 );
1265 lower.SetClosed( true );
1266 }
1267 }
1268 }
1269 else
1270 {
1271 // More than 1 segment
1272 wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1273
1274 // Just a temporary thing
1275 aOutlines = bbox;
1276 return true;
1277 }
1278
1279 // Figure out which is the correct outline
1280 SHAPE_POLY_SET poly1;
1281 SHAPE_POLY_SET poly2;
1282
1283 poly1.NewOutline();
1284 poly1.Append( upper );
1285
1286 poly2.NewOutline();
1287 poly2.Append( lower );
1288
1289 if( isCopperOutside( footprint, poly1 ) )
1290 {
1291 wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1292 aOutlines = poly2;
1293 }
1294 else
1295 {
1296 wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1297 aOutlines = poly1;
1298 }
1299
1300 // Add all closed polys as holes to the main outline
1301 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1302 {
1303 wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1304 aOutlines.AddHole( closedChain, -1 );
1305 }
1306
1307 return true;
1308 }
1309
1310 // We really shouldn't reach this point
1311 return false;
1312}
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:77
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:282
const BOX2I GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:911
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:897
BOX2I ComputeBoundingBox(bool aBoardEdgesOnly=false, bool aIncludeHiddenText=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1552
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:433
const FOOTPRINTS & Footprints() const
Definition: board.h:323
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:88
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:126
void ClearFlags(EDA_ITEM_FLAGS aMask=EDA_ITEM_ALL_FLAGS)
Definition: eda_item.h:128
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:129
void RebuildBezierToSegmentsPointsList(int aMinSegLen)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
Definition: eda_shape.cpp:506
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:279
int GetRadius() const
Definition: eda_shape.cpp:619
SHAPE_T GetShape() const
Definition: eda_shape.h:125
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:1161
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:589
PADS & Pads()
Definition: footprint.h:193
Definition: pad.h:53
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:367
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: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:518
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 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:515
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:278
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