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