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