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:109
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:103
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
const wxPoint GetOrigin() const
Definition: eda_rect.h:101
int GetHeight() const
Definition: eda_rect.h:110
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:1082
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: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().

◆ 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 1059 of file convert_shape_list_to_polygon.cpp.

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

◆ findEndSegments()

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

Definition at line 995 of file convert_shape_list_to_polygon.cpp.

996 {
997  int foundSegs = 0;
998 
999  for( int i = 0; i < aChain.SegmentCount(); i++ )
1000  {
1001  SEG seg = aChain.Segment( i );
1002 
1003  bool foundA = false;
1004  bool foundB = false;
1005 
1006  for( int j = 0; j < aChain.SegmentCount(); j++ )
1007  {
1008  // Don't test the segment against itself
1009  if( i == j )
1010  continue;
1011 
1012  SEG testSeg = aChain.Segment( j );
1013 
1014  if( testSeg.Contains( seg.A ) )
1015  foundA = true;
1016 
1017  if( testSeg.Contains( seg.B ) )
1018  foundB = true;
1019  }
1020 
1021  // This segment isn't a start or end
1022  if( foundA && foundB )
1023  continue;
1024 
1025  if( foundSegs == 0 )
1026  {
1027  // The first segment we encounter is the "start" segment
1028  wxLogTrace( traceBoardOutline, "Found start segment: (%d, %d)-(%d, %d)",
1029  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1030  aStartSeg = seg;
1031  foundSegs++;
1032  }
1033  else
1034  {
1035  // Once we find both start and end, we can stop
1036  wxLogTrace( traceBoardOutline, "Found end segment: (%d, %d)-(%d, %d)",
1037  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1038  aEndSeg = seg;
1039  foundSegs++;
1040  break;
1041  }
1042  }
1043 
1044  return foundSegs;
1045 }
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, "Tested pad (%d, %d): outside", padPos.x, padPos.y );
961  padOutside = true;
962  break;
963  }
964 
965  wxPoint padPos = pad->GetPosition();
966  wxLogTrace( traceBoardOutline, "Tested pad (%d, %d): not outside", padPos.x, padPos.y );
967  }
968 
969  return padOutside;
970 }
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:168
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 973 of file convert_shape_list_to_polygon.cpp.

975 {
976  int minDistance = -1;
977  VECTOR2I projPoint;
978 
979  for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
980  {
981  auto seg = it.Get();
982  int dis = seg.Distance( aEndPoint );
983 
984  if( minDistance < 0 || ( dis < minDistance ) )
985  {
986  minDistance = dis;
987  projPoint = seg.NearestPoint( aEndPoint );
988  }
989  }
990 
991  return projPoint;
992 }
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().