KiCad PCB EDA Suite
convert_shape_list_to_polygon.cpp File Reference
#include <trigo.h>
#include <macros.h>
#include <math/vector2d.h>
#include <pcb_shape.h>
#include <footprint.h>
#include <pad.h>
#include <base_units.h>
#include <convert_basic_shapes_to_polygon.h>
#include <geometry/shape_poly_set.h>
#include <geometry/geometry_utils.h>
#include <convert_shape_list_to_polygon.h>
#include <wx/log.h>
#include <board.h>
#include <collectors.h>

Go to the source code of this file.

Functions

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. More...
 
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 closest to a point. More...
 
static PCB_SHAPEfindNext (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. More...
 
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 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)
 Extracts the board outlines and build a closed polygon from lines, arcs and circle items on edge cut layer. More...
 
void buildBoardBoundingBoxPoly (const BOARD *aBoard, SHAPE_POLY_SET &aOutline)
 Get the complete bounding box of the board (including all items). More...
 
bool isCopperOutside (const FOOTPRINT *aMod, SHAPE_POLY_SET &aShape)
 
VECTOR2I projectPointOnSegment (const VECTOR2I &aEndPoint, const SHAPE_POLY_SET &aOutline, int aOutlineNum=0)
 
int findEndSegments (SHAPE_LINE_CHAIN &aChain, SEG &aStartSeg, SEG &aEndSeg)
 
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. More...
 

Variables

const wxChar * traceBoardOutline = wxT( "KICAD_BOARD_OUTLINE" )
 Flag to enable debug tracing for the board outline creation. More...
 

Function Documentation

◆ buildBoardBoundingBoxPoly()

void buildBoardBoundingBoxPoly ( const BOARD aBoard,
SHAPE_POLY_SET aOutline 
)

Get the complete bounding box of the board (including all items).

The vertex numbers and segment numbers of the rectangle returned. 1 ------------— |1 2| 0| |2 |0 3| ------------— 3

Definition at line 920 of file convert_shape_list_to_polygon.cpp.

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 }
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:724
int GetWidth() const
Definition: eda_rect.h:118
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
const wxPoint GetEnd() const
Definition: eda_rect.h:112
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
const wxPoint GetOrigin() const
Definition: eda_rect.h:110
int GetHeight() const
Definition: eda_rect.h:119
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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:1085
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

References SHAPE_POLY_SET::AddOutline(), SHAPE_LINE_CHAIN::Append(), BOARD::ComputeBoundingBox(), BOARD::GetBoundingBox(), EDA_RECT::GetEnd(), EDA_RECT::GetHeight(), EDA_RECT::GetOrigin(), EDA_RECT::GetWidth(), EDA_RECT::Inflate(), Millimeter2iu(), SHAPE_POLY_SET::RemoveAllContours(), and SHAPE_LINE_CHAIN::SetClosed().

Referenced by BuildFootprintPolygonOutlines(), and RENDER_3D_RAYTRACE::Reload().

◆ 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:118
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:112
const wxPoint GetOrigin() const
Definition: eda_rect.h:110
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:119
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:1085
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().

◆ BuildFootprintPolygonOutlines()

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.

Notes:

  • Incomplete outlines will be closed by joining the end of the outline onto the bounding box (by simply projecting the end points) and then take the area that contains the copper.
  • If all copper lies inside a closed outline, than that outline will be treated as an external board outline.
  • If copper is located outside a closed outline, then that outline will be treated as a hole, and the outer edge will be formed using the bounding box.

Definition at line 1061 of file convert_shape_list_to_polygon.cpp.

1064 {
1065  FOOTPRINT* footprint = aBoard->GetFirstFootprint();
1066 
1067  // No footprint loaded
1068  if( !footprint )
1069  {
1070  wxLogTrace( traceBoardOutline, wxT( "No footprint found on board" ) );
1071  return false;
1072  }
1073 
1074  PCB_TYPE_COLLECTOR items;
1075  SHAPE_POLY_SET outlines;
1076  bool success = false;
1077 
1078  // Get all the SHAPEs into 'items', then keep only those on layer == Edge_Cuts.
1079  static const KICAD_T scan_graphics[] = { PCB_SHAPE_T, PCB_FP_SHAPE_T, EOT };
1080  items.Collect( aBoard, scan_graphics );
1081 
1082  // Make a working copy of aSegList, because the list is modified during calculations
1083  std::vector<PCB_SHAPE*> segList;
1084 
1085  for( int ii = 0; ii < items.GetCount(); ii++ )
1086  {
1087  if( items[ii]->GetLayer() == Edge_Cuts )
1088  segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
1089  }
1090 
1091  if( !segList.empty() )
1092  {
1093  success = ConvertOutlineToPolygon( segList, outlines, aErrorMax, aChainingEpsilon,
1094  aErrorHandler );
1095  }
1096 
1097  // A closed outline was found on Edge_Cuts
1098  if( success )
1099  {
1100  wxLogTrace( traceBoardOutline, wxT( "Closed outline found" ) );
1101 
1102  // If copper is outside a closed polygon, treat it as a hole
1103  if( isCopperOutside( footprint, outlines ) )
1104  {
1105  wxLogTrace( traceBoardOutline, wxT( "Treating outline as a hole" ) );
1106 
1107  buildBoardBoundingBoxPoly( aBoard, aOutlines );
1108 
1109  // Copy all outlines from the conversion as holes into the new outline
1110  for( int i = 0; i < outlines.OutlineCount(); i++ )
1111  {
1112  SHAPE_LINE_CHAIN& out = outlines.Outline( i );
1113 
1114  if( out.IsClosed() )
1115  aOutlines.AddHole( out, -1 );
1116 
1117  for( int j = 0; j < outlines.HoleCount( i ); j++ )
1118  {
1119  SHAPE_LINE_CHAIN& hole = outlines.Hole( i, j );
1120 
1121  if( hole.IsClosed() )
1122  aOutlines.AddHole( hole, -1 );
1123  }
1124  }
1125  }
1126  // If all copper is inside, then the computed outline is the board outline
1127  else
1128  {
1129  wxLogTrace( traceBoardOutline, wxT( "Treating outline as board edge" ) );
1130  aOutlines = outlines;
1131  }
1132 
1133  return true;
1134  }
1135  // No board outlines were found, so use the bounding box
1136  else if( outlines.OutlineCount() == 0 )
1137  {
1138  wxLogTrace( traceBoardOutline, wxT( "Using footprint bounding box" ) );
1139  buildBoardBoundingBoxPoly( aBoard, aOutlines );
1140 
1141  return true;
1142  }
1143  // There is an outline present, but it is not closed
1144  else
1145  {
1146  wxLogTrace( traceBoardOutline, wxT( "Trying to build outline" ) );
1147 
1148  std::vector<SHAPE_LINE_CHAIN> closedChains;
1149  std::vector<SHAPE_LINE_CHAIN> openChains;
1150 
1151  // The ConvertOutlineToPolygon function returns only one main outline and the rest as
1152  // holes, so we promote the holes and process them
1153  openChains.push_back( outlines.Outline( 0 ) );
1154 
1155  for( int j = 0; j < outlines.HoleCount( 0 ); j++ )
1156  {
1157  SHAPE_LINE_CHAIN hole = outlines.Hole( 0, j );
1158 
1159  if( hole.IsClosed() )
1160  {
1161  wxLogTrace( traceBoardOutline, wxT( "Found closed hole" ) );
1162  closedChains.push_back( hole );
1163  }
1164  else
1165  {
1166  wxLogTrace( traceBoardOutline, wxT( "Found open hole" ) );
1167  openChains.push_back( hole );
1168  }
1169  }
1170 
1171  SHAPE_POLY_SET bbox;
1172  buildBoardBoundingBoxPoly( aBoard, bbox );
1173 
1174  // Treat the open polys as the board edge
1175  SHAPE_LINE_CHAIN chain = openChains[0];
1176  SHAPE_LINE_CHAIN rect = bbox.Outline( 0 );
1177 
1178  // We know the outline chain is open, so set to non-closed to get better segment count
1179  chain.SetClosed( false );
1180 
1181  SEG startSeg;
1182  SEG endSeg;
1183 
1184  // The two possible board outlines
1185  SHAPE_LINE_CHAIN upper;
1186  SHAPE_LINE_CHAIN lower;
1187 
1188  findEndSegments( chain, startSeg, endSeg );
1189 
1190  if( chain.SegmentCount() == 0 )
1191  {
1192  // Something is wrong, bail out with the overall footprint bounding box
1193  wxLogTrace( traceBoardOutline, wxT( "No line segments in provided outline" ) );
1194  aOutlines = bbox;
1195  return true;
1196  }
1197  else if( chain.SegmentCount() == 1 )
1198  {
1199  // This case means there is only 1 line segment making up the edge cuts of the
1200  // footprint, so we just need to use it to cut the bounding box in half.
1201  wxLogTrace( traceBoardOutline, wxT( "Only 1 line segment in provided outline" ) );
1202 
1203  startSeg = chain.Segment( 0 );
1204 
1205  // Intersect with all the sides of the rectangle
1206  OPT_VECTOR2I inter0 = startSeg.IntersectLines( rect.Segment( 0 ) );
1207  OPT_VECTOR2I inter1 = startSeg.IntersectLines( rect.Segment( 1 ) );
1208  OPT_VECTOR2I inter2 = startSeg.IntersectLines( rect.Segment( 2 ) );
1209  OPT_VECTOR2I inter3 = startSeg.IntersectLines( rect.Segment( 3 ) );
1210 
1211  if( inter0 && inter2 && !inter1 && !inter3 )
1212  {
1213  // Intersects the vertical rectangle sides only
1214  wxLogTrace( traceBoardOutline, wxT( "Segment intersects only vertical bbox "
1215  "sides" ) );
1216 
1217  // The upper half
1218  upper.Append( *inter0 );
1219  upper.Append( rect.GetPoint( 1 ) );
1220  upper.Append( rect.GetPoint( 2 ) );
1221  upper.Append( *inter2 );
1222  upper.SetClosed( true );
1223 
1224  // The lower half
1225  lower.Append( *inter0 );
1226  lower.Append( rect.GetPoint( 0 ) );
1227  lower.Append( rect.GetPoint( 3 ) );
1228  lower.Append( *inter2 );
1229  lower.SetClosed( true );
1230  }
1231  else if( inter1 && inter3 && !inter0 && !inter2 )
1232  {
1233  // Intersects the horizontal rectangle sides only
1234  wxLogTrace( traceBoardOutline, wxT( "Segment intersects only horizontal bbox "
1235  "sides" ) );
1236 
1237  // The left half
1238  upper.Append( *inter1 );
1239  upper.Append( rect.GetPoint( 1 ) );
1240  upper.Append( rect.GetPoint( 0 ) );
1241  upper.Append( *inter3 );
1242  upper.SetClosed( true );
1243 
1244  // The right half
1245  lower.Append( *inter1 );
1246  lower.Append( rect.GetPoint( 2 ) );
1247  lower.Append( rect.GetPoint( 3 ) );
1248  lower.Append( *inter3 );
1249  lower.SetClosed( true );
1250  }
1251  else
1252  {
1253  // Angled line segment that cuts across a corner
1254  wxLogTrace( traceBoardOutline, wxT( "Segment intersects two perpendicular bbox "
1255  "sides" ) );
1256 
1257  // Figure out which actual lines are intersected, since IntersectLines assumes
1258  // an infinite line
1259  bool hit0 = rect.Segment( 0 ).Contains( *inter0 );
1260  bool hit1 = rect.Segment( 1 ).Contains( *inter1 );
1261  bool hit2 = rect.Segment( 2 ).Contains( *inter2 );
1262  bool hit3 = rect.Segment( 3 ).Contains( *inter3 );
1263 
1264  if( hit0 && hit1 )
1265  {
1266  // Cut across the upper left corner
1267  wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1268 
1269  // The upper half
1270  upper.Append( *inter0 );
1271  upper.Append( rect.GetPoint( 1 ) );
1272  upper.Append( *inter1 );
1273  upper.SetClosed( true );
1274 
1275  // The lower half
1276  lower.Append( *inter0 );
1277  lower.Append( rect.GetPoint( 0 ) );
1278  lower.Append( rect.GetPoint( 3 ) );
1279  lower.Append( rect.GetPoint( 2 ) );
1280  lower.Append( *inter1 );
1281  lower.SetClosed( true );
1282  }
1283  else if( hit1 && hit2 )
1284  {
1285  // Cut across the upper right corner
1286  wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper right corner" ) );
1287 
1288  // The upper half
1289  upper.Append( *inter1 );
1290  upper.Append( rect.GetPoint( 2 ) );
1291  upper.Append( *inter2 );
1292  upper.SetClosed( true );
1293 
1294  // The lower half
1295  lower.Append( *inter1 );
1296  lower.Append( rect.GetPoint( 1 ) );
1297  lower.Append( rect.GetPoint( 0 ) );
1298  lower.Append( rect.GetPoint( 3 ) );
1299  lower.Append( *inter2 );
1300  lower.SetClosed( true );
1301  }
1302  else if( hit2 && hit3 )
1303  {
1304  // Cut across the lower right corner
1305  wxLogTrace( traceBoardOutline, wxT( "Segment cuts lower right corner" ) );
1306 
1307  // The upper half
1308  upper.Append( *inter2 );
1309  upper.Append( rect.GetPoint( 2 ) );
1310  upper.Append( rect.GetPoint( 1 ) );
1311  upper.Append( rect.GetPoint( 0 ) );
1312  upper.Append( *inter3 );
1313  upper.SetClosed( true );
1314 
1315  // The bottom half
1316  lower.Append( *inter2 );
1317  lower.Append( rect.GetPoint( 3 ) );
1318  lower.Append( *inter3 );
1319  lower.SetClosed( true );
1320  }
1321  else
1322  {
1323  // Cut across the lower left corner
1324  wxLogTrace( traceBoardOutline, wxT( "Segment cuts upper left corner" ) );
1325 
1326  // The upper half
1327  upper.Append( *inter0 );
1328  upper.Append( rect.GetPoint( 1 ) );
1329  upper.Append( rect.GetPoint( 2 ) );
1330  upper.Append( rect.GetPoint( 3 ) );
1331  upper.Append( *inter3 );
1332  upper.SetClosed( true );
1333 
1334  // The bottom half
1335  lower.Append( *inter0 );
1336  lower.Append( rect.GetPoint( 0 ) );
1337  lower.Append( *inter3 );
1338  lower.SetClosed( true );
1339  }
1340  }
1341  }
1342  else
1343  {
1344  // More than 1 segment
1345  wxLogTrace( traceBoardOutline, wxT( "Multiple segments in outline" ) );
1346 
1347  // Just a temporary thing
1348  aOutlines = bbox;
1349  return true;
1350  }
1351 
1352  // Figure out which is the correct outline
1353  SHAPE_POLY_SET poly1;
1354  SHAPE_POLY_SET poly2;
1355 
1356  poly1.NewOutline();
1357  poly1.Append( upper );
1358 
1359  poly2.NewOutline();
1360  poly2.Append( lower );
1361 
1362  if( isCopperOutside( footprint, poly1 ) )
1363  {
1364  wxLogTrace( traceBoardOutline, wxT( "Using lower shape" ) );
1365  aOutlines = poly2;
1366  }
1367  else
1368  {
1369  wxLogTrace( traceBoardOutline, wxT( "Using upper shape" ) );
1370  aOutlines = poly1;
1371  }
1372 
1373  // Add all closed polys as holes to the main outline
1374  for( SHAPE_LINE_CHAIN& closedChain : closedChains )
1375  {
1376  wxLogTrace( traceBoardOutline, wxT( "Adding hole to main outline" ) );
1377  aOutlines.AddHole( closedChain, -1 );
1378  }
1379 
1380  return true;
1381  }
1382 
1383  // We really shouldn't reach this point
1384  return false;
1385 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
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
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
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.
int GetCount() const
Return the number of objects in the list.
Definition: collector.h:82
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
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)
bool isCopperOutside(const FOOTPRINT *aMod, SHAPE_POLY_SET &aShape)
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.
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.
Definition: seg.h:40
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.
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
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
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...

References SHAPE_POLY_SET::AddHole(), SHAPE_LINE_CHAIN::Append(), SHAPE_POLY_SET::Append(), buildBoardBoundingBoxPoly(), PCB_TYPE_COLLECTOR::Collect(), SEG::Contains(), ConvertOutlineToPolygon(), Edge_Cuts, EOT, findEndSegments(), COLLECTOR::GetCount(), BOARD::GetFirstFootprint(), SHAPE_LINE_CHAIN::GetPoint(), SHAPE_POLY_SET::Hole(), SHAPE_POLY_SET::HoleCount(), SEG::IntersectLines(), SHAPE_LINE_CHAIN::IsClosed(), isCopperOutside(), SHAPE_POLY_SET::NewOutline(), SHAPE_POLY_SET::Outline(), SHAPE_POLY_SET::OutlineCount(), PCB_FP_SHAPE_T, PCB_SHAPE_T, SHAPE_LINE_CHAIN::Segment(), SHAPE_LINE_CHAIN::SegmentCount(), SHAPE_LINE_CHAIN::SetClosed(), and traceBoardOutline.

Referenced by BOARD_ADAPTER::createBoardPolygon().

◆ close_enough()

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.

Parameters
aLeftis the first point
aRightis the second point
aLimitis a measure of proximity that the caller knows about.
Returns
bool - true if the two points are close enough, else false.

Definition at line 60 of file convert_shape_list_to_polygon.cpp.

61 {
62  return ( aLeft - aRight ).SquaredEuclideanNorm() <= SEG::Square( aLimit );
63 }
static SEG::ecoord Square(int a)
Definition: seg.h:122

References SEG::Square().

Referenced by ConvertOutlineToPolygon().

◆ closer_to_first()

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 closest to a point.

Parameters
aRefis the reference point
aFirstis the first point
aSecondis the second point
Returns
bool - true if the first point is closest to the reference, otherwise false.

Definition at line 74 of file convert_shape_list_to_polygon.cpp.

75 {
76  return ( aRef - aFirst ).SquaredEuclideanNorm() < ( aRef - aSecond ).SquaredEuclideanNorm();
77 }

Referenced by ConvertOutlineToPolygon().

◆ 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 closed main outline with perhaps closed inner outlines.

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( wxT( "ConvertOutlineToPolygon not implemented for " )
749  + graphic->SHAPE_T_asString() );
750  return false;
751  }
752 
753  // Get next closest segment.
754 
755  PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, aChainingEpsilon );
756 
757  if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
758  {
759  graphic = nextGraphic;
760  graphic->SetFlags( SKIP_STRUCT );
761  startCandidates.erase( graphic );
762  continue;
763  }
764 
765  // Finished, or ran into trouble...
766 
767  if( close_enough( startPt, prevPt, aChainingEpsilon ) )
768  {
769  break;
770  }
771  else if( nextGraphic ) // encountered already-used segment, but not at the start
772  {
773  if( aErrorHandler )
774  (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
775 
776  polygonComplete = false;
777  break;
778  }
779  else // encountered discontinuity
780  {
781  if( aErrorHandler )
782  (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
783 
784  polygonComplete = false;
785  break;
786  }
787  }
788  }
789  }
790 
791  if( !polygonComplete )
792  return false;
793 
794  // All of the silliness that follows is to work around the segment iterator while checking
795  // for collisions.
796  // TODO: Implement proper segment and point iterators that follow std
797 
798  for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
799  {
800  auto seg2 = seg1;
801 
802  for( ++seg2; seg2; seg2++ )
803  {
804  // Check for exact overlapping segments.
805  if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
806  {
807  if( aErrorHandler )
808  {
809  BOARD_ITEM* a = fetchOwner( *seg1 );
810  BOARD_ITEM* b = fetchOwner( *seg2 );
811 
812  if( a && b )
813  (*aErrorHandler)( _( "(self-intersecting)" ), a, b, (wxPoint) ( *seg1 ).A );
814  }
815 
816  selfIntersecting = true;
817  }
818 
819  if( boost::optional<VECTOR2I> pt = seg1.Get().Intersect( seg2.Get(), true ) )
820  {
821  if( aErrorHandler )
822  {
823  BOARD_ITEM* a = fetchOwner( *seg1 );
824  BOARD_ITEM* b = fetchOwner( *seg2 );
825 
826  if( a && b )
827  (*aErrorHandler)( _( "(self-intersecting)" ), a, b, (wxPoint) pt.get() );
828  }
829 
830  selfIntersecting = true;
831  }
832  }
833  }
834 
835  return !selfIntersecting;
836 }
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:210
int GetWidth() const
Definition: eda_shape.h:98
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:106
double GetOrientation() const
Definition: footprint.h:191
void SetFlags(EDA_ITEM_FLAGS aMask)
Definition: eda_item.h:152
double GetArcAngle() const
Definition: eda_shape.cpp:536
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:622
std::vector< wxPoint > GetRectCorners() const
Definition: eda_shape.cpp:981
const wxPoint & GetEnd() const
Return the ending point of the graphic.
Definition: eda_shape.h:131
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:227
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:187
SHAPE_T GetShape() const
Definition: eda_shape.h:101
int GetRadius() const
Definition: eda_shape.cpp:472
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().

◆ findEndSegments()

int findEndSegments ( SHAPE_LINE_CHAIN aChain,
SEG aStartSeg,
SEG aEndSeg 
)

Definition at line 997 of file convert_shape_list_to_polygon.cpp.

998 {
999  int foundSegs = 0;
1000 
1001  for( int i = 0; i < aChain.SegmentCount(); i++ )
1002  {
1003  SEG seg = aChain.Segment( i );
1004 
1005  bool foundA = false;
1006  bool foundB = false;
1007 
1008  for( int j = 0; j < aChain.SegmentCount(); j++ )
1009  {
1010  // Don't test the segment against itself
1011  if( i == j )
1012  continue;
1013 
1014  SEG testSeg = aChain.Segment( j );
1015 
1016  if( testSeg.Contains( seg.A ) )
1017  foundA = true;
1018 
1019  if( testSeg.Contains( seg.B ) )
1020  foundB = true;
1021  }
1022 
1023  // This segment isn't a start or end
1024  if( foundA && foundB )
1025  continue;
1026 
1027  if( foundSegs == 0 )
1028  {
1029  // The first segment we encounter is the "start" segment
1030  wxLogTrace( traceBoardOutline, wxT( "Found start segment: (%d, %d)-(%d, %d)" ),
1031  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1032  aStartSeg = seg;
1033  foundSegs++;
1034  }
1035  else
1036  {
1037  // Once we find both start and end, we can stop
1038  wxLogTrace( traceBoardOutline, wxT( "Found end segment: (%d, %d)-(%d, %d)" ),
1039  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1040  aEndSeg = seg;
1041  foundSegs++;
1042  break;
1043  }
1044  }
1045 
1046  return foundSegs;
1047 }
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
int SegmentCount() const
Return the number of segments in this line chain.
Definition: seg.h:40
SEG Segment(int aIndex)
Return a copy of the aIndex-th segment in the line chain.
VECTOR2I A
Definition: seg.h:48
bool Contains(const SEG &aSeg) const
Definition: seg.h:331
VECTOR2I B
Definition: seg.h:49

References SEG::A, SEG::B, SEG::Contains(), SHAPE_LINE_CHAIN::Segment(), SHAPE_LINE_CHAIN::SegmentCount(), traceBoardOutline, VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by BuildFootprintPolygonOutlines().

◆ findNext()

static PCB_SHAPE* findNext ( PCB_SHAPE aShape,
const wxPoint &  aPoint,
const std::vector< PCB_SHAPE * > &  aList,
unsigned  aLimit 
)
static

Searches for a PCB_SHAPE matching a given end point or start point in a list.

Parameters
aShapeThe starting shape.
aPointThe starting or ending point to search for.
aListThe list to remove from.
aLimitis the distance from aPoint that still constitutes a valid find.
Returns
PCB_SHAPE* - The first PCB_SHAPE that has a start or end point matching aPoint, otherwise NULL if none.

Definition at line 89 of file convert_shape_list_to_polygon.cpp.

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 }
VECTOR2I::extended_type ecoord
Definition: seg.h:43
static SEG::ecoord Square(int a)
Definition: seg.h:122
#define SKIP_STRUCT
flag indicating that the structure should be ignored

References SKIP_STRUCT, and SEG::Square().

Referenced by ConvertOutlineToPolygon(), and PAD_TOOL::recombinePad().

◆ isCopperOutside()

bool isCopperOutside ( const FOOTPRINT aMod,
SHAPE_POLY_SET aShape 
)

Definition at line 947 of file convert_shape_list_to_polygon.cpp.

948 {
949  bool padOutside = false;
950 
951  for( PAD* pad : aMod->Pads() )
952  {
953  SHAPE_POLY_SET poly = aShape;
954 
955  poly.BooleanIntersection( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
956 
957  if( poly.OutlineCount() == 0 )
958  {
959  wxPoint padPos = pad->GetPosition();
960  wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): outside" ),
961  padPos.x, padPos.y );
962  padOutside = true;
963  break;
964  }
965 
966  wxPoint padPos = pad->GetPosition();
967  wxLogTrace( traceBoardOutline, wxT( "Tested pad (%d, %d): not outside" ),
968  padPos.x, padPos.y );
969  }
970 
971  return padOutside;
972 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
PADS & Pads()
Definition: footprint.h:169
Represent a set of closed polygons.
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,...
Definition: pad.h:57

References SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::OutlineCount(), pad, FOOTPRINT::Pads(), SHAPE_POLY_SET::PM_FAST, and traceBoardOutline.

Referenced by BuildFootprintPolygonOutlines().

◆ projectPointOnSegment()

VECTOR2I projectPointOnSegment ( const VECTOR2I aEndPoint,
const SHAPE_POLY_SET aOutline,
int  aOutlineNum = 0 
)

Definition at line 975 of file convert_shape_list_to_polygon.cpp.

977 {
978  int minDistance = -1;
979  VECTOR2I projPoint;
980 
981  for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
982  {
983  auto seg = it.Get();
984  int dis = seg.Distance( aEndPoint );
985 
986  if( minDistance < 0 || ( dis < minDistance ) )
987  {
988  minDistance = dis;
989  projPoint = seg.NearestPoint( aEndPoint );
990  }
991  }
992 
993  return projPoint;
994 }
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.

References SHAPE_POLY_SET::CIterateSegments().