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