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( "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, "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 
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 
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 
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 }
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:190
int GetWidth() const
Definition: eda_shape.h:89
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:97
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:109
double GetOrientation() const
Definition: footprint.h:190
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:152
double GetArcAngle() const
Definition: eda_shape.cpp:498
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:623
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:168
This file contains miscellaneous commonly used macros and functions.
std::vector< wxPoint > GetRectCorners() const
Definition: eda_shape.cpp:943
int GetCount() const
Return the number of objects in the list.
Definition: collector.h:82
const wxPoint GetEnd() const
Definition: eda_rect.h:103
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:122
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:101
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:110
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:207
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:186
EDA_RECT ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1082
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:92
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:466
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