KiCad PCB EDA Suite
convert_shape_list_to_polygon.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2017 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 2015 SoftPLC Corporation, Dick Hollenbeck <[email protected]>
6  * Copyright (C) 1992-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>
38 
39 #include <wx/log.h>
40 
41 
49 const wxChar* traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" );
50 
60 bool close_enough( VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit )
61 {
62  return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
63 }
64 
74 bool closer_to_first( VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond )
75 {
76  return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
77 }
78 
79 
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 
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( wxT( "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  */
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 
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 
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, wxT( "Tested pad (%d, %d): outside" ),
961  padPos.x, padPos.y );
962  padOutside = true;
963  break;
964  }
965 
966  wxPoint padPos = pad->GetPosition();
967  wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ),
968  padPos.x, padPos.y );
969  }
970 
971  return padOutside;
972 }
973 
974 
975 VECTOR2I projectPointOnSegment( const VECTOR2I& aEndPoint, const SHAPE_POLY_SET& aOutline,
976  int aOutlineNum = 0 )
977 {
978  int minDistance = -1;
979  VECTOR2I projPoint;
980 
981  for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
982  {
983  auto seg = it.Get();
984  int dis = seg.Distance( aEndPoint );
985 
986  if( minDistance < 0 || ( dis < minDistance ) )
987  {
988  minDistance = dis;
989  projPoint = seg.NearestPoint( aEndPoint );
990  }
991  }
992 
993  return projPoint;
994 }
995 
996 
997 int findEndSegments( SHAPE_LINE_CHAIN& aChain, SEG& aStartSeg, SEG& aEndSeg )
998 {
999  int foundSegs = 0;
1000 
1001  for( int i = 0; i < aChain.SegmentCount(); i++ )
1002  {
1003  SEG seg = aChain.Segment( i );
1004 
1005  bool foundA = false;
1006  bool foundB = false;
1007 
1008  for( int j = 0; j < aChain.SegmentCount(); j++ )
1009  {
1010  // Don't test the segment against itself
1011  if( i == j )
1012  continue;
1013 
1014  SEG testSeg = aChain.Segment( j );
1015 
1016  if( testSeg.Contains( seg.A ) )
1017  foundA = true;
1018 
1019  if( testSeg.Contains( seg.B ) )
1020  foundB = true;
1021  }
1022 
1023  // This segment isn't a start or end
1024  if( foundA && foundB )
1025  continue;
1026 
1027  if( foundSegs == 0 )
1028  {
1029  // The first segment we encounter is the "start" segment
1030  wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
1031  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1032  aStartSeg = seg;
1033  foundSegs++;
1034  }
1035  else
1036  {
1037  // Once we find both start and end, we can stop
1038  wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
1039  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1040  aEndSeg = seg;
1041  foundSegs++;
1042  break;
1043  }
1044  }
1045 
1046  return foundSegs;
1047 }
1048 
1049 
1061 bool BuildFootprintPolygonOutlines( BOARD* aBoard, SHAPE_POLY_SET& aOutlines, int aErrorMax,
1062  int aChainingEpsilon, OUTLINE_ERROR_HANDLER* aErrorHandler )
1063 
1064 {
1065  FOOTPRINT* footprint = aBoard->GetFirstFootprint();
1066 
1067  // No footprint loaded
1068  if( !footprint )
1069  {
1070  wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
1071  return false;
1072  }
1073 
1074  PCB_TYPE_COLLECTOR items;
1075  SHAPE_POLY_SET outlines;
1076  bool success = false;
1077 
1078  // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
1079  static const KICAD_T scan_graphics[] = { PCB_SHAPE_T, PCB_FP_SHAPE_T, EOT };
1080  items.Collect( aBoard, scan_graphics );
1081 
1082  // Make a working copy of aSegList, because the list is modified during calculations
1083  std::vector<PCB_SHAPE*> segList;
1084 
1085  for( int ii = 0; ii < items.GetCount(); ii++ )
1086  {
1087  if( items[ii]->GetLayer() == Edge_Cuts )
1088  segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
1089  }
1090 
1091  if( !segList.empty() )
1092  {
1093  success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
1094  aErrorHandler );
1095  }
1096 
1097  // A closed outline was found on Edge_Cuts
1098  if( success )
1099  {
1100  wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
1101 
1102  // If copper is outside a closed polygon, treat it as a hole
1103  if( isCopperOutside( footprint, outlines ) )
1104  {
1105  wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
1106 
1107  buildBoardBoundingBoxPoly( aBoard, aOutlines );
1108 
1109  // Copy all outlines from the conversion as holes into the new outline
1110  for( int i = 0; i < outlines.OutlineCount(); i++ )
1111  {
1112  SHAPE_LINE_CHAIN& out = outlines.Outline( i );
1113 
1114  if( out.IsClosed() )
1115  aOutlines.AddHole( out, -1 );
1116 
1117  for( int j = 0; j < outlines.HoleCount( i ); j++ )
1118  {
1119  SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
1120 
1121  if( hole.IsClosed() )
1122  aOutlines.AddHole( hole, -1 );
1123  }
1124  }
1125  }
1126  // If all copper is inside, then the computed outline is the board outline
1127  else
1128  {
1129  wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
1130  aOutlines = outlines;
1131  }
1132 
1133  return true;
1134  }
1135  // No board outlines were found, so use the bounding box
1136  else if( outlines.OutlineCount() == 0 )
1137  {
1138  wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
1139  buildBoardBoundingBoxPoly( aBoard, aOutlines );
1140 
1141  return true;
1142  }
1143  // There is an outline present, but it is not closed
1144  else
1145  {
1146  wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
1147 
1148  std::vector<SHAPE_LINE_CHAIN> closedChains;
1149  std::vector<SHAPE_LINE_CHAIN> openChains;
1150 
1151  // The ConvertOutlineToPolygon function returns only one main outline and the rest as
1152  // holes, so we promote the holes and process them
1153  openChains.push_back( outlines.Outline( 0 ) );
1154 
1155  for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
1156  {
1157  SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
1158 
1159  if( hole.IsClosed() )
1160  {
1161  wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
1162  closedChains.push_back( hole );
1163  }
1164  else
1165  {
1166  wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
1167  openChains.push_back( hole );
1168  }
1169  }
1170 
1171  SHAPE_POLY_SET bbox;
1172  buildBoardBoundingBoxPoly( aBoard, bbox );
1173 
1174  // Treat the open polys as the board edge
1175  SHAPE_LINE_CHAIN chain = openChains[0];
1176  SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
1177 
1178  // We know the outline chain is open, so set to non-closed to get better segment count
1179  chain.SetClosed( false );
1180 
1181  SEG startSeg;
1182  SEG endSeg;
1183 
1184  // The two possible board outlines
1185  SHAPE_LINE_CHAIN upper;
1186  SHAPE_LINE_CHAIN lower;
1187 
1188  findEndSegments( chain, startSeg, endSeg );
1189 
1190  if( chain.SegmentCount() == 0 )
1191  {
1192  // Something is wrong, bail out with the overall footprint bounding box
1193  wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
1194  aOutlines = bbox;
1195  return true;
1196  }
1197  else if( chain.SegmentCount() == 1 )
1198  {
1199  // This case means there is only 1 line segment making up the edge cuts of the
1200  // footprint, so we just need to use it to cut the bounding box in half.
1201  wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
1202 
1203  startSeg = chain.Segment( 0 );
1204 
1205  // Intersect with all the sides of the rectangle
1206  OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
1207  OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
1208  OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1209  OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1210 
1211  if( inter0 && inter2 && !inter1 && !inter3 )
1212  {
1213  // Intersects the vertical rectangle sides only
1214  wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1215  "sides" ) );
1216 
1217  // The upper half
1218  upper.Append( *inter0 );
1219  upper.Append( rect.GetPoint( 1 ) );
1220  upper.Append( rect.GetPoint( 2 ) );
1221  upper.Append( *inter2 );
1222  upper.SetClosed( true );
1223 
1224  // The lower half
1225  lower.Append( *inter0 );
1226  lower.Append( rect.GetPoint( 0 ) );
1227  lower.Append( rect.GetPoint( 3 ) );
1228  lower.Append( *inter2 );
1229  lower.SetClosed( true );
1230  }
1231  else if( inter1 && inter3 && !inter0 && !inter2 )
1232  {
1233  // Intersects the horizontal rectangle sides only
1234  wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1235  "sides" ) );
1236 
1237  // The left half
1238  upper.Append( *inter1 );
1239  upper.Append( rect.GetPoint( 1 ) );
1240  upper.Append( rect.GetPoint( 0 ) );
1241  upper.Append( *inter3 );
1242  upper.SetClosed( true );
1243 
1244  // The right half
1245  lower.Append( *inter1 );
1246  lower.Append( rect.GetPoint( 2 ) );
1247  lower.Append( rect.GetPoint( 3 ) );
1248  lower.Append( *inter3 );
1249  lower.SetClosed( true );
1250  }
1251  else
1252  {
1253  // Angled line segment that cuts across a corner
1254  wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1255  "sides" ) );
1256 
1257  // Figure out which actual lines are intersected, since IntersectLines assumes
1258  // an infinite line
1259  bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1260  bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1261  bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1262  bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1263 
1264  if( hit0 && hit1 )
1265  {
1266  // Cut across the upper left corner
1267  wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1268 
1269  // The upper half
1270  upper.Append( *inter0 );
1271  upper.Append( rect.GetPoint( 1 ) );
1272  upper.Append( *inter1 );
1273  upper.SetClosed( true );
1274 
1275  // The lower half
1276  lower.Append( *inter0 );
1277  lower.Append( rect.GetPoint( 0 ) );
1278  lower.Append( rect.GetPoint( 3 ) );
1279  lower.Append( rect.GetPoint( 2 ) );
1280  lower.Append( *inter1 );
1281  lower.SetClosed( true );
1282  }
1283  else if( hit1 && hit2 )
1284  {
1285  // Cut across the upper right corner
1286  wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1287 
1288  // The upper half
1289  upper.Append( *inter1 );
1290  upper.Append( rect.GetPoint( 2 ) );
1291  upper.Append( *inter2 );
1292  upper.SetClosed( true );
1293 
1294  // The lower half
1295  lower.Append( *inter1 );
1296  lower.Append( rect.GetPoint( 1 ) );
1297  lower.Append( rect.GetPoint( 0 ) );
1298  lower.Append( rect.GetPoint( 3 ) );
1299  lower.Append( *inter2 );
1300  lower.SetClosed( true );
1301  }
1302  else if( hit2 && hit3 )
1303  {
1304  // Cut across the lower right corner
1305  wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1306 
1307  // The upper half
1308  upper.Append( *inter2 );
1309  upper.Append( rect.GetPoint( 2 ) );
1310  upper.Append( rect.GetPoint( 1 ) );
1311  upper.Append( rect.GetPoint( 0 ) );
1312  upper.Append( *inter3 );
1313  upper.SetClosed( true );
1314 
1315  // The bottom half
1316  lower.Append( *inter2 );
1317  lower.Append( rect.GetPoint( 3 ) );
1318  lower.Append( *inter3 );
1319  lower.SetClosed( true );
1320  }
1321  else
1322  {
1323  // Cut across the lower left corner
1324  wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1325 
1326  // The upper half
1327  upper.Append( *inter0 );
1328  upper.Append( rect.GetPoint( 1 ) );
1329  upper.Append( rect.GetPoint( 2 ) );
1330  upper.Append( rect.GetPoint( 3 ) );
1331  upper.Append( *inter3 );
1332  upper.SetClosed( true );
1333 
1334  // The bottom half
1335  lower.Append( *inter0 );
1336  lower.Append( rect.GetPoint( 0 ) );
1337  lower.Append( *inter3 );
1338  lower.SetClosed( true );
1339  }
1340  }
1341  }
1342  else
1343  {
1344  // More than 1 segment
1345  wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1346 
1347  // Just a temporary thing
1348  aOutlines = bbox;
1349  return true;
1350  }
1351 
1352  // Figure out which is the correct outline
1353  SHAPE_POLY_SET poly1;
1354  SHAPE_POLY_SET poly2;
1355 
1356  poly1.NewOutline();
1357  poly1.Append( upper );
1358 
1359  poly2.NewOutline();
1360  poly2.Append( lower );
1361 
1362  if( isCopperOutside( footprint, poly1 ) )
1363  {
1364  wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1365  aOutlines = poly2;
1366  }
1367  else
1368  {
1369  wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1370  aOutlines = poly1;
1371  }
1372 
1373  // Add all closed polys as holes to the main outline
1374  for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1375  {
1376  wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1377  aOutlines.AddHole( closedChain, -1 );
1378  }
1379 
1380  return true;
1381  }
1382 
1383  // We really shouldn't reach this point
1384  return false;
1385 }
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:724
const std::vector< wxPoint > & GetBezierPoints() const
Definition: eda_shape.h:210
int GetWidth() const
Definition: eda_shape.h:98
bool BuildFootprintPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
This function is used to extract a board outline for a footprint view.
int OutlineCount() const
Return the number of vertices in a given outline/hole.
static PCB_SHAPE * findNext(PCB_SHAPE *aShape, const wxPoint &aPoint, const std::vector< PCB_SHAPE * > &aList, unsigned aLimit)
Searches for a PCB_SHAPE matching a given end point or start point in a list.
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
Implementation of conversion functions that require both schematic and board internal units.
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:49
const wxPoint & GetStart() const
Return the starting point of the graphic.
Definition: eda_shape.h:106
const EDA_RECT GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:738
VECTOR2I::extended_type ecoord
Definition: seg.h:43
int GetWidth() const
Definition: eda_rect.h:118
double GetOrientation() const
Definition: footprint.h:191
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:152
double GetArcAngle() const
Definition: eda_shape.cpp:536
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
class FP_SHAPE, a footprint edge
Definition: typeinfo.h:93
bool closer_to_first(VECTOR2I aRef, VECTOR2I aFirst, VECTOR2I aSecond)
Function closer_to_first Local method which qualifies whether the start or end point of a segment is ...
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:229
VECTOR2< int > VECTOR2I
Definition: vector2d.h:622
static SEG::ecoord Square(int a)
Definition: seg.h:122
search types array terminator (End Of Types)
Definition: typeinfo.h:81
KICAD_T
The set of class identification values stored in EDA_ITEM::m_structType.
Definition: typeinfo.h:77
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
PADS & Pads()
Definition: footprint.h:169
This file contains miscellaneous commonly used macros and functions.
std::vector< wxPoint > GetRectCorners() const
Definition: eda_shape.cpp:981
int GetCount() const
Return the number of objects in the list.
Definition: collector.h:82
const wxPoint GetEnd() const
Definition: eda_rect.h:112
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
const wxPoint & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:131
bool BuildBoardPolygonOutlines(BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut ...
FOOTPRINT * GetFirstFootprint() const
Get the first footprint on the board or nullptr.
Definition: board.h:318
bool IsClosed() const override
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:38
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
const wxPoint GetOrigin() const
Definition: eda_rect.h:110
wxPoint GetCenter() const override
This defaults to the center of the bounding box if not overridden.
Definition: pcb_shape.h:79
void TransformCircleToPolygon(SHAPE_LINE_CHAIN &aCornerBuffer, const wxPoint &aCenter, int aRadius, int aError, ERROR_LOC aErrorLoc, int aMinSegCount=0)
Convert a circle to a polygon, using multiple straight lines.
#define UNIMPLEMENTED_FOR(type)
Definition: macros.h:120
#define _(s)
void ClearFlags(EDA_ITEM_FLAGS aMask=EDA_ITEM_ALL_FLAGS)
Definition: eda_item.h:153
a few functions useful in geometry calculations.
bool isCopperOutside(const FOOTPRINT *aMod, SHAPE_POLY_SET &aShape)
wxString SHAPE_T_asString() const
Definition: eda_shape.cpp:71
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
int NewOutline()
Creates a new hole in a given outline.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
int SegmentCount() const
Return the number of segments in this line chain.
VECTOR2I projectPointOnSegment(const VECTOR2I &aEndPoint, const SHAPE_POLY_SET &aOutline, int aOutlineNum=0)
virtual const VECTOR2I GetPoint(int aIndex) const override
void Collect(BOARD_ITEM *aBoard, const KICAD_T aScanList[])
Collect BOARD_ITEM objects using this class's Inspector method, which does the collection.
Definition: collectors.cpp:609
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
int GetHeight() const
Definition: eda_rect.h:119
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:227
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:154
Definition: seg.h:40
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
void RebuildBezierToSegmentsPointsList(int aMinSegLen)
Rebuild the m_bezierPoints vertex list that approximate the Bezier curve by a list of segments.
Definition: eda_shape.cpp:366
int findEndSegments(SHAPE_LINE_CHAIN &aChain, SEG &aStartSeg, SEG &aEndSeg)
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
bool close_enough(VECTOR2I aLeft, VECTOR2I aRight, unsigned aLimit)
Function close_enough is a local and tunable method of qualifying the proximity of two points.
#define SKIP_STRUCT
flag indicating that the structure should be ignored
FOOTPRINT * GetParentFootprint() const
Return the parent footprint or NULL if PCB_SHAPE does not belong to a footprint.
Definition: pcb_shape.cpp:123
Information pertinent to a Pcbnew printed circuit board.
Definition: board.h:191
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:48
Handle the component boundary box.
Definition: eda_rect.h:42
wxPoint GetPosition() const override
Definition: footprint.h:187
EDA_RECT ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1085
const std::function< void(const wxString &msg, BOARD_ITEM *itemA, BOARD_ITEM *itemB, const wxPoint &pt)> OUTLINE_ERROR_HANDLER
SHAPE_T GetShape() const
Definition: eda_shape.h:101
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
bool ConvertOutlineToPolygon(std::vector< PCB_SHAPE * > &aSegList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler)
Function ConvertOutlineToPolygon Build a polygon (with holes) from a PCB_SHAPE list,...
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
Definition: collectors.h:614
int GetRadius() const
Definition: eda_shape.cpp:472
Definition: pad.h:57
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:90
static constexpr int Millimeter2iu(double mm)
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
void buildBoardBoundingBoxPoly(const BOARD *aBoard, SHAPE_POLY_SET &aOutline)
Get the complete bounding box of the board (including all items).
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
VECTOR2I B
Definition: seg.h:49