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 <dick@softplc.com>
6 * Copyright (C) 1992-2020 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 <trigo.h>
27 #include <macros.h>
28
29 #include <math/vector2d.h>
30 #include <pcb_shape.h>
31 #include <footprint.h>
32 #include <pad.h>
33 #include <base_units.h>
34 #include <convert_basic_shapes_to_polygon.h>
35 #include <geometry/shape_poly_set.h>
36 #include <geometry/geometry_utils.h>
37 #include <convert_shape_list_to_polygon.h>
38
39 #include <wx/log.h>
40
41
42 /**
43 * Flag to enable debug tracing for the board outline creation
44 *
45 * Use "KICAD_BOARD_OUTLINE" to enable.
46 *
47 * @ingroup trace_env_vars
48 */
49 const wxChar* traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" );
50
51 /**
52 * Function close_enough
53 * is a local and tunable method of qualifying the proximity of two points.
54 *
55 * @param aLeft is the first point
56 * @param aRight is the second point
57 * @param aLimit is a measure of proximity that the caller knows about.
58 * @return bool - true if the two points are close enough, else false.
59 */
close_enough(VECTOR2I aLeft,VECTOR2I aRight,unsigned aLimit)60 bool close_enough( VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit )
61 {
62 return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
63 }
64
65 /**
66 * Function closer_to_first
67 * Local method which qualifies whether the start or end point of a segment is closest to a point.
68 *
69 * @param aRef is the reference point
70 * @param aFirst is the first point
71 * @param aSecond is the second point
72 * @return bool - true if the first point is closest to the reference, otherwise false.
73 */
closer_to_first(VECTOR2I aRef,VECTOR2I aFirst,VECTOR2I aSecond)74 bool closer_to_first( VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond )
75 {
76 return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
77 }
78
79
80 /**
81 * Searches for a PCB_SHAPE matching a given end point or start point in a list.
82 * @param aShape The starting shape.
83 * @param aPoint The starting or ending point to search for.
84 * @param aList The list to remove from.
85 * @param aLimit is the distance from \a aPoint that still constitutes a valid find.
86 * @return PCB_SHAPE* - The first PCB_SHAPE that has a start or end point matching
87 * aPoint, otherwise NULL if none.
88 */
findNext(PCB_SHAPE * aShape,const wxPoint & aPoint,const std::vector<PCB_SHAPE * > & aList,unsigned aLimit)89 static PCB_SHAPE* findNext( PCB_SHAPE* aShape, const wxPoint& aPoint,
90 const std::vector<PCB_SHAPE*>& aList, unsigned aLimit )
91 {
92 // Look for an unused, exact hit
93 for( PCB_SHAPE* graphic : aList )
94 {
95 if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
96 continue;
97
98 if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
99 return graphic;
100 }
101
102 // Search again for anything that's close, even something already used. (The latter is
103 // important for error reporting.)
104 VECTOR2I pt( aPoint );
105 SEG::ecoord closest_dist_sq = SEG::Square( aLimit );
106 PCB_SHAPE* closest_graphic = nullptr;
107 SEG::ecoord d_sq;
108
109 for( PCB_SHAPE* graphic : aList )
110 {
111 if( graphic == aShape )
112 continue;
113
114 d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
115
116 if( d_sq < closest_dist_sq )
117 {
118 closest_dist_sq = d_sq;
119 closest_graphic = graphic;
120 }
121
122 d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
123
124 if( d_sq < closest_dist_sq )
125 {
126 closest_dist_sq = d_sq;
127 closest_graphic = graphic;
128 }
129 }
130
131 return closest_graphic; // Note: will be nullptr if nothing within aLimit
132 }
133
134
135 /**
136 * Function ConvertOutlineToPolygon
137 * Build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a closed main
138 * outline with perhaps closed inner outlines. These closed inner outlines are considered as
139 * holes in the main outline.
140 * @param aSegList the initial list of drawsegments (only lines, circles and arcs).
141 * @param aPolygons will contain the complex polygon.
142 * @param aErrorMax is the max error distance when polygonizing a curve (internal units)
143 * @param aChainingEpsilon is the max error distance when polygonizing a curve (internal units)
144 * @param aErrorHandler = an optional error handler
145 */
ConvertOutlineToPolygon(std::vector<PCB_SHAPE * > & aSegList,SHAPE_POLY_SET & aPolygons,int aErrorMax,int aChainingEpsilon,OUTLINE_ERROR_HANDLER * aErrorHandler)146 bool ConvertOutlineToPolygon( std::vector<PCB_SHAPE*>& aSegList, SHAPE_POLY_SET& aPolygons,
147 int aErrorMax, int aChainingEpsilon,
148 OUTLINE_ERROR_HANDLER* aErrorHandler )
149 {
150 if( aSegList.size() == 0 )
151 return true;
152
153 bool polygonComplete = false;
154 bool selfIntersecting = false;
155
156 wxString msg;
157 PCB_SHAPE* graphic = nullptr;
158
159 std::set<PCB_SHAPE*> startCandidates( aSegList.begin(), aSegList.end() );
160
161 // Find edge point with minimum x, this should be in the outer polygon
162 // which will define the perimeter polygon polygon.
163 wxPoint xmin = wxPoint( INT_MAX, 0 );
164 int xmini = 0;
165
166 for( size_t i = 0; i < aSegList.size(); i++ )
167 {
168 graphic = (PCB_SHAPE*) aSegList[i];
169 graphic->ClearFlags( SKIP_STRUCT );
170
171 switch( graphic->GetShape() )
172 {
173 case SHAPE_T::RECT:
174 case SHAPE_T::SEGMENT:
175 {
176 if( graphic->GetStart().x < xmin.x )
177 {
178 xmin = graphic->GetStart();
179 xmini = i;
180 }
181
182 if( graphic->GetEnd().x < xmin.x )
183 {
184 xmin = graphic->GetEnd();
185 xmini = i;
186 }
187 }
188 break;
189
190 case SHAPE_T::ARC:
191 {
192 wxPoint pstart = graphic->GetStart();
193 wxPoint center = graphic->GetCenter();
194 double angle = -graphic->GetArcAngle();
195 double radius = graphic->GetRadius();
196 int steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
197 wxPoint pt;
198
199 for( int step = 1; step<=steps; ++step )
200 {
201 double rotation = ( angle * step ) / steps;
202
203 pt = pstart;
204
205 RotatePoint( &pt, center, rotation );
206
207 if( pt.x < xmin.x )
208 {
209 xmin = pt;
210 xmini = i;
211 }
212 }
213 }
214 break;
215
216 case SHAPE_T::CIRCLE:
217 {
218 wxPoint pt = graphic->GetCenter();
219
220 // pt has minimum x point
221 pt.x -= graphic->GetRadius();
222
223 // when the radius <= 0, this is a mal-formed circle. Skip it
224 if( graphic->GetRadius() > 0 && pt.x < xmin.x )
225 {
226 xmin = pt;
227 xmini = i;
228 }
229 }
230 break;
231
232 case SHAPE_T::BEZIER:
233 {
234 graphic->RebuildBezierToSegmentsPointsList( graphic->GetWidth() );
235
236 for( const wxPoint& pt : graphic->GetBezierPoints() )
237 {
238 if( pt.x < xmin.x )
239 {
240 xmin = pt;
241 xmini = i;
242 }
243 }
244 }
245 break;
246
247 case SHAPE_T::POLY:
248 {
249 const SHAPE_POLY_SET poly = graphic->GetPolyShape();
250 double orientation = 0.0;
251 VECTOR2I offset = VECTOR2I( 0, 0 );
252
253 if( graphic->GetParentFootprint() )
254 {
255 orientation = graphic->GetParentFootprint()->GetOrientation();
256 offset = graphic->GetParentFootprint()->GetPosition();
257 }
258
259 for( auto iter = poly.CIterate(); iter; iter++ )
260 {
261 VECTOR2I pt = *iter;
262 RotatePoint( pt, orientation );
263 pt += offset;
264
265 if( pt.x < xmin.x )
266 {
267 xmin.x = pt.x;
268 xmin.y = pt.y;
269 xmini = i;
270 }
271 }
272 }
273 break;
274
275 default:
276 break;
277 }
278 }
279
280 // Keep a list of where the various segments came from so after doing our combined-polygon
281 // tests we can still report errors against the individual graphic items.
282 std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> segOwners;
283
284 auto fetchOwner =
285 [&]( const SEG& seg ) -> PCB_SHAPE*
286 {
287 auto it = segOwners.find( std::make_pair( seg.A, seg.B ) );
288 return it == segOwners.end() ? nullptr : it->second;
289 };
290
291 // Grab the left most point, assume its on the board's perimeter, and see if we can put
292 // enough graphics together by matching endpoints to formulate a cohesive polygon.
293
294 PCB_SHAPE* prevGraphic = nullptr;
295 wxPoint prevPt;
296
297 graphic = (PCB_SHAPE*) aSegList[xmini];
298 graphic->SetFlags( SKIP_STRUCT );
299 startCandidates.erase( graphic );
300
301 // Output the outline perimeter as polygon.
302 if( graphic->GetShape() == SHAPE_T::CIRCLE )
303 {
304 TransformCircleToPolygon( aPolygons, graphic->GetCenter(), graphic->GetRadius(),
305 ARC_LOW_DEF, ERROR_INSIDE );
306 polygonComplete = true;
307 }
308 else if( graphic->GetShape() == SHAPE_T::RECT )
309 {
310 std::vector<wxPoint> pts = graphic->GetRectCorners();
311
312 aPolygons.NewOutline();
313
314 for( const wxPoint& pt : pts )
315 aPolygons.Append( pt );
316
317 segOwners[ std::make_pair( pts[0], pts[1] ) ] = graphic;
318 segOwners[ std::make_pair( pts[1], pts[2] ) ] = graphic;
319 segOwners[ std::make_pair( pts[2], pts[3] ) ] = graphic;
320 segOwners[ std::make_pair( pts[3], pts[0] ) ] = graphic;
321
322 polygonComplete = true;
323 }
324 else if( graphic->GetShape() == SHAPE_T::POLY )
325 {
326 double orientation = 0.0;
327 VECTOR2I offset = VECTOR2I( 0, 0 );
328
329 if( graphic->GetParentFootprint() )
330 {
331 orientation = graphic->GetParentFootprint()->GetOrientation();
332 offset = graphic->GetParentFootprint()->GetPosition();
333 }
334
335 aPolygons.NewOutline();
336 bool first = true;
337
338 for( auto it = graphic->GetPolyShape().CIterate( 0 ); it; it++ )
339 {
340 VECTOR2I pt = *it;
341 RotatePoint( pt, orientation );
342 pt += offset;
343 aPolygons.Append( pt );
344
345 if( first )
346 first = false;
347 else
348 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
349
350 prevPt = (wxPoint) pt;
351 }
352
353 polygonComplete = true;
354 }
355 else
356 {
357 // Polygon start point. Arbitrarily choose an end of the segment and build the polygon
358 // from there.
359
360 wxPoint startPt = graphic->GetEnd();
361
362 prevPt = startPt;
363 aPolygons.NewOutline();
364 aPolygons.Append( prevPt );
365
366 // Do not append the other end point yet of this 'graphic', this first 'graphic' might
367 // be an arc or a curve.
368
369 for(;;)
370 {
371 switch( graphic->GetShape() )
372 {
373 case SHAPE_T::RECT:
374 case SHAPE_T::CIRCLE:
375 {
376 // As a non-first item, closed shapes can't be anything but self-intersecting
377
378 if( aErrorHandler )
379 {
380 wxASSERT( prevGraphic );
381 (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
382 }
383
384 selfIntersecting = true;
385
386 // A closed shape will finish where it started, so no point in updating prevPt
387 }
388 break;
389
390 case SHAPE_T::SEGMENT:
391 {
392 wxPoint nextPt;
393
394 // Use the line segment end point furthest away from prevPt as we assume the
395 // other end to be ON prevPt or very close to it.
396
397 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
398 nextPt = graphic->GetEnd();
399 else
400 nextPt = graphic->GetStart();
401
402 aPolygons.Append( nextPt );
403 segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
404 prevPt = nextPt;
405 }
406 break;
407
408 case SHAPE_T::ARC:
409 {
410 // We do not support arcs in polygons, so approximate an arc with a series of
411 // short lines and put those line segments into the !same! PATH.
412
413 wxPoint pstart = graphic->GetStart();
414 wxPoint pend = graphic->GetEnd();
415 wxPoint pcenter = graphic->GetCenter();
416 double angle = -graphic->GetArcAngle();
417 double radius = graphic->GetRadius();
418 int steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
419
420 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
421 {
422 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
423
424 angle = -angle;
425 std::swap( pstart, pend );
426 }
427
428 // Create intermediate points between start and end:
429 for( int step = 1; step < steps; ++step )
430 {
431 double rotation = ( angle * step ) / steps;
432 wxPoint pt = pstart;
433 RotatePoint( &pt, pcenter, rotation );
434
435 aPolygons.Append( pt );
436 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
437 prevPt = pt;
438 }
439
440 // Append the last arc end point
441 aPolygons.Append( pend );
442 segOwners[ std::make_pair( prevPt, pend ) ] = graphic;
443 prevPt = pend;
444 }
445 break;
446
447 case SHAPE_T::BEZIER:
448 {
449 // We do not support Bezier curves in polygons, so approximate with a series
450 // of short lines and put those line segments into the !same! PATH.
451
452 wxPoint nextPt;
453 bool first = true;
454 bool reverse = false;
455
456 // Use the end point furthest away from
457 // prevPt as we assume the other end to be ON prevPt or
458 // very close to it.
459
460 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
461 {
462 nextPt = graphic->GetEnd();
463 }
464 else
465 {
466 nextPt = graphic->GetStart();
467 reverse = true;
468 }
469
470 if( reverse )
471 {
472 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
473 {
474 const wxPoint& pt = graphic->GetBezierPoints()[jj];
475 aPolygons.Append( pt );
476
477 if( first )
478 first = false;
479 else
480 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
481
482 prevPt = pt;
483 }
484 }
485 else
486 {
487 for( const wxPoint& pt : graphic->GetBezierPoints() )
488 {
489 aPolygons.Append( pt );
490
491 if( first )
492 first = false;
493 else
494 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
495
496 prevPt = pt;
497 }
498 }
499
500 prevPt = nextPt;
501 }
502 break;
503
504 default:
505 UNIMPLEMENTED_FOR( graphic->SHAPE_T_asString() );
506 return false;
507 }
508
509 // Get next closest segment.
510
511 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, aChainingEpsilon );
512
513 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
514 {
515 prevGraphic = graphic;
516 graphic = nextGraphic;
517 graphic->SetFlags( SKIP_STRUCT );
518 startCandidates.erase( graphic );
519 continue;
520 }
521
522 // Finished, or ran into trouble...
523
524 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
525 {
526 polygonComplete = true;
527 break;
528 }
529 else if( nextGraphic ) // encountered already-used segment, but not at the start
530 {
531 if( aErrorHandler )
532 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
533
534 polygonComplete = false;
535 break;
536 }
537 else // encountered discontinuity
538 {
539 if( aErrorHandler )
540 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
541
542 polygonComplete = false;
543 break;
544 }
545 }
546 }
547
548 int holeNum = -1;
549
550 while( startCandidates.size() )
551 {
552 int hole = aPolygons.NewHole();
553 bool firstPt = true;
554 holeNum++;
555
556 graphic = (PCB_SHAPE*) *startCandidates.begin();
557 graphic->SetFlags( SKIP_STRUCT );
558 startCandidates.erase( startCandidates.begin() );
559
560 // Both circles and polygons on the edge cuts layer are closed items that do not
561 // connect to other elements, so we process them independently
562 if( graphic->GetShape() == SHAPE_T::POLY )
563 {
564 double orientation = 0.0;
565 VECTOR2I offset = VECTOR2I( 0, 0 );
566
567 if( graphic->GetParentFootprint() )
568 {
569 orientation = graphic->GetParentFootprint()->GetOrientation();
570 offset = graphic->GetParentFootprint()->GetPosition();
571 }
572
573 for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
574 {
575 VECTOR2I pt = *it;
576 RotatePoint( pt, orientation );
577 pt += offset;
578
579 aPolygons.Append( pt, -1, hole );
580
581 if( firstPt )
582 firstPt = false;
583 else
584 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
585
586 prevPt = (wxPoint) pt;
587 }
588 }
589 else if( graphic->GetShape() == SHAPE_T::CIRCLE )
590 {
591 // make a circle by segments;
592 wxPoint center = graphic->GetCenter();
593 double angle = 3600.0;
594 wxPoint start = center;
595 int radius = graphic->GetRadius();
596 int steps = GetArcToSegmentCount( radius, aErrorMax, 360.0 );
597 wxPoint nextPt;
598
599 start.x += radius;
600
601 for( int step = 0; step < steps; ++step )
602 {
603 double rotation = ( angle * step ) / steps;
604 nextPt = start;
605 RotatePoint( &nextPt.x, &nextPt.y, center.x, center.y, rotation );
606 aPolygons.Append( nextPt, -1, hole );
607
608 if( firstPt )
609 firstPt = false;
610 else
611 segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
612
613 prevPt = nextPt;
614 }
615 }
616 else if( graphic->GetShape() == SHAPE_T::RECT )
617 {
618 std::vector<wxPoint> pts = graphic->GetRectCorners();
619
620 for( const wxPoint& pt : pts )
621 {
622 aPolygons.Append( pt, -1, hole );
623
624 if( firstPt )
625 firstPt = false;
626 else
627 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
628
629 prevPt = (wxPoint) pt;
630 }
631 }
632 else
633 {
634 // Polygon start point. Arbitrarily chosen end of the segment and build the poly
635 // from here.
636
637 wxPoint startPt = graphic->GetEnd();
638 prevPt = startPt;
639 aPolygons.Append( prevPt, -1, hole );
640
641 // do not append the other end point yet, this first 'graphic' might be an arc
642 for(;;)
643 {
644 switch( graphic->GetShape() )
645 {
646 case SHAPE_T::SEGMENT:
647 {
648 wxPoint nextPt;
649
650 // Use the line segment end point furthest away from prevPt as we assume
651 // the other end to be ON prevPt or very close to it.
652
653 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
654 nextPt = graphic->GetEnd();
655 else
656 nextPt = graphic->GetStart();
657
658 aPolygons.Append( nextPt, -1, hole );
659 segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
660 prevPt = nextPt;
661 }
662 break;
663
664 case SHAPE_T::ARC:
665 // We do not support arcs in polygons, so approximate an arc with a series of
666 // short lines and put those line segments into the !same! PATH.
667 {
668 wxPoint pstart = graphic->GetStart();
669 wxPoint pend = graphic->GetEnd();
670 wxPoint pcenter = graphic->GetCenter();
671 double angle = -graphic->GetArcAngle();
672 int radius = graphic->GetRadius();
673 int steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
674
675 if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
676 {
677 wxASSERT( close_enough( prevPt, graphic->GetEnd(), aChainingEpsilon ) );
678
679 angle = -angle;
680 std::swap( pstart, pend );
681 }
682
683 // Create intermediate points between start and end:
684 for( int step = 1; step < steps; ++step )
685 {
686 double rotation = ( angle * step ) / steps;
687 wxPoint pt = pstart;
688
689 RotatePoint( &pt, pcenter, rotation );
690
691 aPolygons.Append( pt, -1, hole );
692 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
693 prevPt = pt;
694 }
695
696 // Append the last arc end point
697 aPolygons.Append( pend, -1, hole );
698 segOwners[ std::make_pair( prevPt, pend ) ] = graphic;
699 prevPt = pend;
700 }
701 break;
702
703 case SHAPE_T::BEZIER:
704 // We do not support Bezier curves in polygons, so approximate with a series
705 // of short lines and put those line segments into the !same! PATH.
706 {
707 wxPoint nextPt;
708 bool reverse = false;
709
710 // Use the end point furthest away from prevPt as we assume the other
711 // end to be ON prevPt or very close to it.
712
713 if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
714 {
715 nextPt = graphic->GetEnd();
716 }
717 else
718 {
719 nextPt = graphic->GetStart();
720 reverse = true;
721 }
722
723 if( reverse )
724 {
725 for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
726 {
727 const wxPoint& pt = graphic->GetBezierPoints()[jj];
728 aPolygons.Append( pt, -1, hole );
729 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
730 prevPt = pt;
731 }
732 }
733 else
734 {
735 for( const wxPoint& pt : graphic->GetBezierPoints() )
736 {
737 aPolygons.Append( pt, -1, hole );
738 segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
739 prevPt = pt;
740 }
741 }
742
743 prevPt = nextPt;
744 }
745 break;
746
747 default:
748 wxFAIL_MSG( "ConvertOutlineToPolygon not implemented for "
749 + graphic->SHAPE_T_asString() );
750 return false;
751 }
752
753 // Get next closest segment.
754
755 PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, aChainingEpsilon );
756
757 if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
758 {
759 graphic = nextGraphic;
760 graphic->SetFlags( SKIP_STRUCT );
761 startCandidates.erase( graphic );
762 continue;
763 }
764
765 // Finished, or ran into trouble...
766
767 if( close_enough( startPt, prevPt, aChainingEpsilon ) )
768 {
769 break;
770 }
771 else if( nextGraphic ) // encountered already-used segment, but not at the start
772 {
773 if( aErrorHandler )
774 (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
775
776 polygonComplete = false;
777 break;
778 }
779 else // encountered discontinuity
780 {
781 if( aErrorHandler )
782 (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
783
784 polygonComplete = false;
785 break;
786 }
787 }
788 }
789 }
790
791 if( !polygonComplete )
792 return false;
793
794 // All of the silliness that follows is to work around the segment iterator while checking
795 // for collisions.
796 // TODO: Implement proper segment and point iterators that follow std
797
798 for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
799 {
800 auto seg2 = seg1;
801
802 for( ++seg2; seg2; seg2++ )
803 {
804 // Check for exact overlapping segments.
805 if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
806 {
807 if( aErrorHandler )
808 {
809 BOARD_ITEM* a = fetchOwner( *seg1 );
810 BOARD_ITEM* b = fetchOwner( *seg2 );
811
812 if( a && b )
813 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, (wxPoint) ( *seg1 ).A );
814 }
815
816 selfIntersecting = true;
817 }
818
819 if( boost::optional<VECTOR2I> pt = seg1.Get().Intersect( seg2.Get(), true ) )
820 {
821 if( aErrorHandler )
822 {
823 BOARD_ITEM* a = fetchOwner( *seg1 );
824 BOARD_ITEM* b = fetchOwner( *seg2 );
825
826 if( a && b )
827 (*aErrorHandler)( _( "(self-intersecting)" ), a, b, (wxPoint) pt.get() );
828 }
829
830 selfIntersecting = true;
831 }
832 }
833 }
834
835 return !selfIntersecting;
836 }
837
838
839 #include <board.h>
840 #include <collectors.h>
841
842 /* This function is used to extract a board outlines (3D view, automatic zones build ...)
843 * Any closed outline inside the main outline is a hole
844 * All contours should be closed, i.e. valid closed polygon vertices
845 */
BuildBoardPolygonOutlines(BOARD * aBoard,SHAPE_POLY_SET & aOutlines,int aErrorMax,int aChainingEpsilon,OUTLINE_ERROR_HANDLER * aErrorHandler)846 bool BuildBoardPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
847 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
848 {
849 PCB_TYPE_COLLECTOR items;
850 bool success = false;
851
852 // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
853 static const KICAD_T scan_graphics[] = { PCB_SHAPE_T, PCB_FP_SHAPE_T, EOT };
854 items.Collect( aBoard, scan_graphics );
855
856 // Make a working copy of aSegList, because the list is modified during calculations
857 std::vector<PCB_SHAPE*> segList;
858
859 for( int ii = 0; ii < items.GetCount(); ii++ )
860 {
861 if( items[ii]->GetLayer() == Edge_Cuts )
862 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
863 }
864
865 if( segList.size() )
866 {
867 success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
868 aErrorHandler );
869 }
870
871 if( !success || !aOutlines.OutlineCount() )
872 {
873 // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
874 // create a rectangular outline, or, failing that, the bounding box of the items on
875 // the board.
876
877 EDA_RECT bbbox = aBoard->GetBoardEdgesBoundingBox();
878
879 // If null area, uses the global bounding box.
880 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
881 bbbox = aBoard->ComputeBoundingBox();
882
883 // Ensure non null area. If happen, gives a minimal size.
884 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
885 bbbox.Inflate( Millimeter2iu( 1.0 ) );
886
887 aOutlines.RemoveAllContours();
888 aOutlines.NewOutline();
889
890 wxPoint corner;
891 aOutlines.Append( bbbox.GetOrigin() );
892
893 corner.x = bbbox.GetOrigin().x;
894 corner.y = bbbox.GetEnd().y;
895 aOutlines.Append( corner );
896
897 aOutlines.Append( bbbox.GetEnd() );
898
899 corner.x = bbbox.GetEnd().x;
900 corner.y = bbbox.GetOrigin().y;
901 aOutlines.Append( corner );
902 }
903
904 return success;
905 }
906
907
908 /**
909 * Get the complete bounding box of the board (including all items).
910 *
911 * The vertex numbers and segment numbers of the rectangle returned.
912 * 1
913 * *---------------*
914 * |1 2|
915 * 0| |2
916 * |0 3|
917 * *---------------*
918 * 3
919 */
buildBoardBoundingBoxPoly(const BOARD * aBoard,SHAPE_POLY_SET & aOutline)920 void buildBoardBoundingBoxPoly( const BOARD* aBoard, SHAPE_POLY_SET& aOutline )
921 {
922 EDA_RECT bbbox = aBoard->GetBoundingBox();
923 SHAPE_LINE_CHAIN chain;
924
925 // If null area, uses the global bounding box.
926 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
927 bbbox = aBoard->ComputeBoundingBox();
928
929 // Ensure non null area. If happen, gives a minimal size.
930 if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
931 bbbox.Inflate( Millimeter2iu( 1.0 ) );
932
933 // Inflate slightly (by 1/10th the size of the box)
934 bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
935
936 chain.Append( bbbox.GetOrigin() );
937 chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
938 chain.Append( bbbox.GetEnd() );
939 chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
940 chain.SetClosed( true );
941
942 aOutline.RemoveAllContours();
943 aOutline.AddOutline( chain );
944 }
945
946
isCopperOutside(const FOOTPRINT * aMod,SHAPE_POLY_SET & aShape)947 bool isCopperOutside( const FOOTPRINT* aMod, SHAPE_POLY_SET& aShape )
948 {
949 bool padOutside = false;
950
951 for( PAD* pad : aMod->Pads() )
952 {
953 SHAPE_POLY_SET poly = aShape;
954
955 poly.BooleanIntersection( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
956
957 if( poly.OutlineCount() == 0 )
958 {
959 wxPoint padPos = pad->GetPosition();
960 wxLogTrace( traceBoardOutline, "Tested pad (%d, %d): outside", padPos.x, padPos.y );
961 padOutside = true;
962 break;
963 }
964
965 wxPoint padPos = pad->GetPosition();
966 wxLogTrace( traceBoardOutline, "Tested pad (%d, %d): not outside", padPos.x, padPos.y );
967 }
968
969 return padOutside;
970 }
971
972
projectPointOnSegment(const VECTOR2I & aEndPoint,const SHAPE_POLY_SET & aOutline,int aOutlineNum=0)973 VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
974 int aOutlineNum = 0 )
975 {
976 int minDistance = -1;
977 VECTOR2I projPoint;
978
979 for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
980 {
981 auto seg = it.Get();
982 int dis = seg.Distance( aEndPoint );
983
984 if( minDistance < 0 || ( dis < minDistance ) )
985 {
986 minDistance = dis;
987 projPoint = seg.NearestPoint( aEndPoint );
988 }
989 }
990
991 return projPoint;
992 }
993
994
findEndSegments(SHAPE_LINE_CHAIN & aChain,SEG & aStartSeg,SEG & aEndSeg)995 int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
996 {
997 int foundSegs = 0;
998
999 for( int i = 0; i < aChain.SegmentCount(); i++ )
1000 {
1001 SEG seg = aChain.Segment( i );
1002
1003 bool foundA = false;
1004 bool foundB = false;
1005
1006 for( int j = 0; j < aChain.SegmentCount(); j++ )
1007 {
1008 // Don't test the segment against itself
1009 if( i == j )
1010 continue;
1011
1012 SEG testSeg = aChain.Segment( j );
1013
1014 if( testSeg.Contains( seg.A ) )
1015 foundA = true;
1016
1017 if( testSeg.Contains( seg.B ) )
1018 foundB = true;
1019 }
1020
1021 // This segment isn't a start or end
1022 if( foundA && foundB )
1023 continue;
1024
1025 if( foundSegs == 0 )
1026 {
1027 // The first segment we encounter is the "start" segment
1028 wxLogTrace( traceBoardOutline, "Found start segment: (%d, %d)-(%d, %d)",
1029 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1030 aStartSeg = seg;
1031 foundSegs++;
1032 }
1033 else
1034 {
1035 // Once we find both start and end, we can stop
1036 wxLogTrace( traceBoardOutline, "Found end segment: (%d, %d)-(%d, %d)",
1037 seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1038 aEndSeg = seg;
1039 foundSegs++;
1040 break;
1041 }
1042 }
1043
1044 return foundSegs;
1045 }
1046
1047
1048 /**
1049 * This function is used to extract a board outline for a footprint view.
1050 *
1051 * Notes:
1052 * * Incomplete outlines will be closed by joining the end of the outline onto the bounding box
1053 * (by simply projecting the end points) and then take the area that contains the copper.
1054 * * If all copper lies inside a closed outline, than that outline will be treated as an external
1055 * board outline.
1056 * * If copper is located outside a closed outline, then that outline will be treated as a hole,
1057 * and the outer edge will be formed using the bounding box.
1058 */
BuildFootprintPolygonOutlines(BOARD * aBoard,SHAPE_POLY_SET & aOutlines,int aErrorMax,int aChainingEpsilon,OUTLINE_ERROR_HANDLER * aErrorHandler)1059 bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
1060 int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
1061
1062 {
1063 FOOTPRINT* footprint = aBoard->GetFirstFootprint();
1064
1065 // No footprint loaded
1066 if( !footprint )
1067 {
1068 wxLogTrace( traceBoardOutline, "No footprint found on board" );
1069 return false;
1070 }
1071
1072 PCB_TYPE_COLLECTOR items;
1073 SHAPE_POLY_SET outlines;
1074 bool success = false;
1075
1076 // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
1077 static const KICAD_T scan_graphics[] = { PCB_SHAPE_T, PCB_FP_SHAPE_T, EOT };
1078 items.Collect( aBoard, scan_graphics );
1079
1080 // Make a working copy of aSegList, because the list is modified during calculations
1081 std::vector<PCB_SHAPE*> segList;
1082
1083 for( int ii = 0; ii < items.GetCount(); ii++ )
1084 {
1085 if( items[ii]->GetLayer() == Edge_Cuts )
1086 segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
1087 }
1088
1089 if( !segList.empty() )
1090 {
1091 success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
1092 aErrorHandler );
1093 }
1094
1095 // A closed outline was found on Edge_Cuts
1096 if( success )
1097 {
1098 wxLogTrace( traceBoardOutline, "Closed outline found" );
1099
1100 // If copper is outside a closed polygon, treat it as a hole
1101 if( isCopperOutside( footprint, outlines ) )
1102 {
1103 wxLogTrace( traceBoardOutline, "Treating outline as a hole" );
1104
1105 buildBoardBoundingBoxPoly( aBoard, aOutlines );
1106
1107 // Copy all outlines from the conversion as holes into the new outline
1108 for( int i = 0; i < outlines.OutlineCount(); i++ )
1109 {
1110 SHAPE_LINE_CHAIN& out = outlines.Outline( i );
1111
1112 if( out.IsClosed() )
1113 aOutlines.AddHole( out, -1 );
1114
1115 for( int j = 0; j < outlines.HoleCount( i ); j++ )
1116 {
1117 SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
1118
1119 if( hole.IsClosed() )
1120 aOutlines.AddHole( hole, -1 );
1121 }
1122 }
1123 }
1124 // If all copper is inside, then the computed outline is the board outline
1125 else
1126 {
1127 wxLogTrace( traceBoardOutline, "Treating outline as board edge" );
1128 aOutlines = outlines;
1129 }
1130
1131 return true;
1132 }
1133 // No board outlines were found, so use the bounding box
1134 else if( outlines.OutlineCount() == 0 )
1135 {
1136 wxLogTrace( traceBoardOutline, "Using footprint bounding box" );
1137 buildBoardBoundingBoxPoly( aBoard, aOutlines );
1138
1139 return true;
1140 }
1141 // There is an outline present, but it is not closed
1142 else
1143 {
1144 wxLogTrace( traceBoardOutline, "Trying to build outline" );
1145
1146 std::vector<SHAPE_LINE_CHAIN> closedChains;
1147 std::vector<SHAPE_LINE_CHAIN> openChains;
1148
1149 // The ConvertOutlineToPolygon function returns only one main outline and the rest as
1150 // holes, so we promote the holes and process them
1151 openChains.push_back( outlines.Outline( 0 ) );
1152
1153 for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
1154 {
1155 SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
1156
1157 if( hole.IsClosed() )
1158 {
1159 wxLogTrace( traceBoardOutline, "Found closed hole" );
1160 closedChains.push_back( hole );
1161 }
1162 else
1163 {
1164 wxLogTrace( traceBoardOutline, "Found open hole" );
1165 openChains.push_back( hole );
1166 }
1167 }
1168
1169 SHAPE_POLY_SET bbox;
1170 buildBoardBoundingBoxPoly( aBoard, bbox );
1171
1172 // Treat the open polys as the board edge
1173 SHAPE_LINE_CHAIN chain = openChains[0];
1174 SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
1175
1176 // We know the outline chain is open, so set to non-closed to get better segment count
1177 chain.SetClosed( false );
1178
1179 SEG startSeg;
1180 SEG endSeg;
1181
1182 // The two possible board outlines
1183 SHAPE_LINE_CHAIN upper;
1184 SHAPE_LINE_CHAIN lower;
1185
1186 findEndSegments( chain, startSeg, endSeg );
1187
1188 if( chain.SegmentCount() == 0 )
1189 {
1190 // Something is wrong, bail out with the overall footprint bounding box
1191 wxLogTrace( traceBoardOutline, "No line segments in provided outline" );
1192 aOutlines = bbox;
1193 return true;
1194 }
1195 else if( chain.SegmentCount() == 1 )
1196 {
1197 // This case means there is only 1 line segment making up the edge cuts of the
1198 // footprint, so we just need to use it to cut the bounding box in half.
1199 wxLogTrace( traceBoardOutline, "Only 1 line segment in provided outline" );
1200
1201 startSeg = chain.Segment( 0 );
1202
1203 // Intersect with all the sides of the rectangle
1204 OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
1205 OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
1206 OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1207 OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1208
1209 if( inter0 && inter2 && !inter1 && !inter3 )
1210 {
1211 // Intersects the vertical rectangle sides only
1212 wxLogTrace( traceBoardOutline, "Segment intersects only vertical bbox sides" );
1213
1214 // The upper half
1215 upper.Append( *inter0 );
1216 upper.Append( rect.GetPoint( 1 ) );
1217 upper.Append( rect.GetPoint( 2 ) );
1218 upper.Append( *inter2 );
1219 upper.SetClosed( true );
1220
1221 // The lower half
1222 lower.Append( *inter0 );
1223 lower.Append( rect.GetPoint( 0 ) );
1224 lower.Append( rect.GetPoint( 3 ) );
1225 lower.Append( *inter2 );
1226 lower.SetClosed( true );
1227 }
1228 else if( inter1 && inter3 && !inter0 && !inter2 )
1229 {
1230 // Intersects the horizontal rectangle sides only
1231 wxLogTrace( traceBoardOutline, "Segment intersects only horizontal bbox sides" );
1232
1233 // The left half
1234 upper.Append( *inter1 );
1235 upper.Append( rect.GetPoint( 1 ) );
1236 upper.Append( rect.GetPoint( 0 ) );
1237 upper.Append( *inter3 );
1238 upper.SetClosed( true );
1239
1240 // The right half
1241 lower.Append( *inter1 );
1242 lower.Append( rect.GetPoint( 2 ) );
1243 lower.Append( rect.GetPoint( 3 ) );
1244 lower.Append( *inter3 );
1245 lower.SetClosed( true );
1246 }
1247 else
1248 {
1249 // Angled line segment that cuts across a corner
1250 wxLogTrace( traceBoardOutline, "Segment intersects two perpendicular bbox sides" );
1251
1252 // Figure out which actual lines are intersected, since IntersectLines assumes
1253 // an infinite line
1254 bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1255 bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1256 bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1257 bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1258
1259 if( hit0 && hit1 )
1260 {
1261 // Cut across the upper left corner
1262 wxLogTrace( traceBoardOutline, "Segment cuts upper left corner" );
1263
1264 // The upper half
1265 upper.Append( *inter0 );
1266 upper.Append( rect.GetPoint( 1 ) );
1267 upper.Append( *inter1 );
1268 upper.SetClosed( true );
1269
1270 // The lower half
1271 lower.Append( *inter0 );
1272 lower.Append( rect.GetPoint( 0 ) );
1273 lower.Append( rect.GetPoint( 3 ) );
1274 lower.Append( rect.GetPoint( 2 ) );
1275 lower.Append( *inter1 );
1276 lower.SetClosed( true );
1277 }
1278 else if( hit1 && hit2 )
1279 {
1280 // Cut across the upper right corner
1281 wxLogTrace( traceBoardOutline, "Segment cuts upper right corner" );
1282
1283 // The upper half
1284 upper.Append( *inter1 );
1285 upper.Append( rect.GetPoint( 2 ) );
1286 upper.Append( *inter2 );
1287 upper.SetClosed( true );
1288
1289 // The lower half
1290 lower.Append( *inter1 );
1291 lower.Append( rect.GetPoint( 1 ) );
1292 lower.Append( rect.GetPoint( 0 ) );
1293 lower.Append( rect.GetPoint( 3 ) );
1294 lower.Append( *inter2 );
1295 lower.SetClosed( true );
1296 }
1297 else if( hit2 && hit3 )
1298 {
1299 // Cut across the lower right corner
1300 wxLogTrace( traceBoardOutline, "Segment cuts lower right corner" );
1301
1302 // The upper half
1303 upper.Append( *inter2 );
1304 upper.Append( rect.GetPoint( 2 ) );
1305 upper.Append( rect.GetPoint( 1 ) );
1306 upper.Append( rect.GetPoint( 0 ) );
1307 upper.Append( *inter3 );
1308 upper.SetClosed( true );
1309
1310 // The bottom half
1311 lower.Append( *inter2 );
1312 lower.Append( rect.GetPoint( 3 ) );
1313 lower.Append( *inter3 );
1314 lower.SetClosed( true );
1315 }
1316 else
1317 {
1318 // Cut across the lower left corner
1319 wxLogTrace( traceBoardOutline, "Segment cuts upper left corner" );
1320
1321 // The upper half
1322 upper.Append( *inter0 );
1323 upper.Append( rect.GetPoint( 1 ) );
1324 upper.Append( rect.GetPoint( 2 ) );
1325 upper.Append( rect.GetPoint( 3 ) );
1326 upper.Append( *inter3 );
1327 upper.SetClosed( true );
1328
1329 // The bottom half
1330 lower.Append( *inter0 );
1331 lower.Append( rect.GetPoint( 0 ) );
1332 lower.Append( *inter3 );
1333 lower.SetClosed( true );
1334 }
1335 }
1336 }
1337 else
1338 {
1339 // More than 1 segment
1340 wxLogTrace( traceBoardOutline, "Multiple segments in outline" );
1341
1342 // Just a temporary thing
1343 aOutlines = bbox;
1344 return true;
1345 }
1346
1347 // Figure out which is the correct outline
1348 SHAPE_POLY_SET poly1;
1349 SHAPE_POLY_SET poly2;
1350
1351 poly1.NewOutline();
1352 poly1.Append( upper );
1353
1354 poly2.NewOutline();
1355 poly2.Append( lower );
1356
1357 if( isCopperOutside( footprint, poly1 ) )
1358 {
1359 wxLogTrace( traceBoardOutline, "Using lower shape" );
1360 aOutlines = poly2;
1361 }
1362 else
1363 {
1364 wxLogTrace( traceBoardOutline, "Using upper shape" );
1365 aOutlines = poly1;
1366 }
1367
1368 // Add all closed polys as holes to the main outline
1369 for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1370 {
1371 wxLogTrace( traceBoardOutline, "Adding hole to main outline" );
1372 aOutlines.AddHole( closedChain, -1 );
1373 }
1374
1375 return true;
1376 }
1377
1378 // We really shouldn't reach this point
1379 return false;
1380 }
1381