KiCad PCB EDA Suite
convert_shape_list_to_polygon.h File Reference

Go to the source code of this file.

Typedefs

typedef const std::function< void(const wxString &msg, BOARD_ITEM *itemA, BOARD_ITEM *itemB, const wxPoint &pt)> OUTLINE_ERROR_HANDLER
 

Functions

bool ConvertOutlineToPolygon (std::vector< PCB_SHAPE * > &aSegList, SHAPE_POLY_SET &aPolygons, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
 Function ConvertOutlineToPolygon build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a outline, therefore a closed main outline with perhaps closed inner outlines. More...
 
bool BuildBoardPolygonOutlines (BOARD *aBoard, SHAPE_POLY_SET &aOutlines, int aErrorMax, int aChainingEpsilon, OUTLINE_ERROR_HANDLER *aErrorHandler=nullptr)
 Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut layer. More...
 

Typedef Documentation

◆ OUTLINE_ERROR_HANDLER

typedef const std::function<void( const wxString& msg, BOARD_ITEM* itemA, BOARD_ITEM* itemB, const wxPoint& pt )> OUTLINE_ERROR_HANDLER

Definition at line 29 of file convert_shape_list_to_polygon.h.

Function Documentation

◆ BuildBoardPolygonOutlines()

bool BuildBoardPolygonOutlines ( BOARD aBoard,
SHAPE_POLY_SET aOutlines,
int  aErrorMax,
int  aChainingEpsilon,
OUTLINE_ERROR_HANDLER aErrorHandler = nullptr 
)

Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut layer.

Any closed outline inside the main outline is a hole. All contours should be closed, i.e. are valid vertices for a closed polygon.

Returns
true if success, false if a contour is not valid

Definition at line 846 of file convert_shape_list_to_polygon.cpp.

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 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const EDA_RECT GetBoardEdgesBoundingBox() const
Return the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:738
int GetWidth() const
Definition: eda_rect.h:109
class FP_SHAPE, a footprint edge
Definition: typeinfo.h:93
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
int GetCount() const
Return the number of objects in the list.
Definition: collector.h:82
const wxPoint GetEnd() const
Definition: eda_rect.h:103
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
int NewOutline()
Creates a new hole in a given outline.
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 GetHeight() const
Definition: eda_rect.h:110
Handle the component boundary box.
Definition: eda_rect.h:42
EDA_RECT ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1082
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
class PCB_SHAPE, a segment not on copper layers
Definition: typeinfo.h:90
static constexpr int Millimeter2iu(double mm)
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Inflate the rectangle horizontally by dx and vertically by dy.
Definition: eda_rect.cpp:364
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...

References SHAPE_POLY_SET::Append(), PCB_TYPE_COLLECTOR::Collect(), BOARD::ComputeBoundingBox(), ConvertOutlineToPolygon(), Edge_Cuts, EOT, BOARD::GetBoardEdgesBoundingBox(), COLLECTOR::GetCount(), EDA_RECT::GetEnd(), EDA_RECT::GetHeight(), EDA_RECT::GetOrigin(), EDA_RECT::GetWidth(), EDA_RECT::Inflate(), Millimeter2iu(), SHAPE_POLY_SET::NewOutline(), SHAPE_POLY_SET::OutlineCount(), PCB_FP_SHAPE_T, PCB_SHAPE_T, and SHAPE_POLY_SET::RemoveAllContours().

Referenced by BOARD::GetBoardPolygonOutlines(), DIALOG_EXPORT_STEP::onExportButton(), and DRC_TEST_PROVIDER_MISC::testOutline().

◆ ConvertOutlineToPolygon()

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, which is expected to be a outline, therefore a closed main outline with perhaps closed inner outlines.

These closed inner outlines are considered as holes in the main outline

Parameters
aSegListthe initial list of drawsegments (only lines, circles and arcs).
aPolygonswill contain the complex polygon.
aErrorMaxis the max error distance when polygonizing a curve (internal units)
aChainingEpsilonis the max distance from one endPt to the next startPt (internal units)
aErrorHandler= an optional error handler

Function ConvertOutlineToPolygon build a polygon (with holes) from a PCB_SHAPE list, which is expected to be a outline, therefore a closed main outline with perhaps closed inner outlines.

These closed inner outlines are considered as holes in the main outline.

Parameters
aSegListthe initial list of drawsegments (only lines, circles and arcs).
aPolygonswill contain the complex polygon.
aErrorMaxis the max error distance when polygonizing a curve (internal units)
aChainingEpsilonis the max error distance when polygonizing a curve (internal units)
aErrorHandler= an optional error handler

Definition at line 146 of file convert_shape_list_to_polygon.cpp.

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 }
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
const std::vector< wxPoint > & GetBezierPoints() const
Definition: eda_shape.h:190
int GetWidth() const
Definition: eda_shape.h:89
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).
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
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
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 ...
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:229
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
std::vector< wxPoint > GetRectCorners() const
Definition: eda_shape.cpp:943
const wxPoint & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:122
Represent a set of closed polygons.
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
wxString SHAPE_T_asString() const
Definition: eda_shape.cpp:71
int NewOutline()
Creates a new hole in a given outline.
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
SHAPE_POLY_SET & GetPolyShape()
Definition: eda_shape.h:207
EDA_ITEM_FLAGS GetFlags() const
Definition: eda_item.h:154
Definition: seg.h:40
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
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
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
wxPoint GetPosition() const override
Definition: footprint.h:186
SHAPE_T GetShape() const
Definition: eda_shape.h:92
int GetRadius() const
Definition: eda_shape.cpp:466
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
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...

References _, PNS::angle(), SHAPE_POLY_SET::Append(), ARC, BEZIER, CIRCLE, SHAPE_POLY_SET::CIterate(), EDA_ITEM::ClearFlags(), close_enough(), closer_to_first(), ERROR_INSIDE, findNext(), EDA_SHAPE::GetArcAngle(), GetArcToSegmentCount(), EDA_SHAPE::GetBezierPoints(), PCB_SHAPE::GetCenter(), EDA_SHAPE::GetEnd(), EDA_ITEM::GetFlags(), FOOTPRINT::GetOrientation(), PCB_SHAPE::GetParentFootprint(), EDA_SHAPE::GetPolyShape(), FOOTPRINT::GetPosition(), EDA_SHAPE::GetRadius(), EDA_SHAPE::GetRectCorners(), EDA_SHAPE::GetShape(), EDA_SHAPE::GetStart(), EDA_SHAPE::GetWidth(), SHAPE_POLY_SET::IterateSegmentsWithHoles(), SHAPE_POLY_SET::NewHole(), SHAPE_POLY_SET::NewOutline(), POLY, EDA_SHAPE::RebuildBezierToSegmentsPointsList(), RECT, RotatePoint(), SEGMENT, EDA_ITEM::SetFlags(), EDA_SHAPE::SHAPE_T_asString(), SKIP_STRUCT, TransformCircleToPolygon(), UNIMPLEMENTED_FOR, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BuildBoardPolygonOutlines(), BuildFootprintPolygonOutlines(), and FOOTPRINT::BuildPolyCourtyards().