KiCad PCB EDA Suite
convert_drawsegment_list_to_polygon.cpp File Reference
#include <trigo.h>
#include <macros.h>
#include <math/vector2d.h>
#include <pcb_shape.h>
#include <footprint.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_drawsegment_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 952 of file convert_drawsegment_list_to_polygon.cpp.

953 {
954  EDA_RECT bbbox = aBoard->GetBoundingBox();
955  SHAPE_LINE_CHAIN chain;
956 
957  // If null area, uses the global bounding box.
958  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
959  bbbox = aBoard->ComputeBoundingBox();
960 
961  // Ensure non null area. If happen, gives a minimal size.
962  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
963  bbbox.Inflate( Millimeter2iu( 1.0 ) );
964 
965  // Inflate slightly (by 1/10th the size of the box)
966  bbbox.Inflate( bbbox.GetWidth() / 10, bbbox.GetHeight() / 10 );
967 
968  chain.Append( bbbox.GetOrigin() );
969  chain.Append( bbbox.GetOrigin().x, bbbox.GetEnd().y );
970  chain.Append( bbbox.GetEnd() );
971  chain.Append( bbbox.GetEnd().x, bbbox.GetOrigin().y );
972  chain.SetClosed( true );
973 
974  aOutline.RemoveAllContours();
975  aOutline.AddOutline( chain );
976 }
const EDA_RECT GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: board.h:789
int GetWidth() const
Definition: eda_rect.h:114
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const wxPoint GetEnd() const
Definition: eda_rect.h:108
void SetClosed(bool aClosed)
Function SetClosed()
const wxPoint GetOrigin() const
Definition: eda_rect.h:106
int GetHeight() const
Definition: eda_rect.h:115
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
SHAPE_LINE_CHAIN.
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:1029
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:363

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 878 of file convert_drawsegment_list_to_polygon.cpp.

880 {
881  PCB_TYPE_COLLECTOR items;
882  bool success = false;
883 
884  // Get all the PCB and FP shapes into 'items', then keep only those on layer == Edge_Cuts.
885  static const KICAD_T scan_graphics[] = { PCB_SHAPE_T, PCB_FP_SHAPE_T, EOT };
886  items.Collect( aBoard, scan_graphics );
887 
888  // Make a working copy of aSegList, because the list is modified during calculations
889  std::vector<PCB_SHAPE*> segList;
890 
891  for( int ii = 0; ii < items.GetCount(); ii++ )
892  {
893  if( items[ii]->GetLayer() == Edge_Cuts )
894  segList.push_back( static_cast<PCB_SHAPE*>( items[ii] ) );
895  }
896 
897  if( segList.size() )
898  {
899  success = ConvertOutlineToPolygon( segList, aOutlines, aErrorMax, aChainingEpsilon,
900  aErrorHandler );
901  }
902 
903  if( !success || !aOutlines.OutlineCount() )
904  {
905  // Couldn't create a valid polygon outline. Use the board edge cuts bounding box to
906  // create a rectangular outline, or, failing that, the bounding box of the items on
907  // the board.
908 
909  EDA_RECT bbbox = aBoard->GetBoardEdgesBoundingBox();
910 
911  // If null area, uses the global bounding box.
912  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
913  bbbox = aBoard->ComputeBoundingBox();
914 
915  // Ensure non null area. If happen, gives a minimal size.
916  if( ( bbbox.GetWidth() ) == 0 || ( bbbox.GetHeight() == 0 ) )
917  bbbox.Inflate( Millimeter2iu( 1.0 ) );
918 
919  aOutlines.RemoveAllContours();
920  aOutlines.NewOutline();
921 
922  wxPoint corner;
923  aOutlines.Append( bbbox.GetOrigin() );
924 
925  corner.x = bbbox.GetOrigin().x;
926  corner.y = bbbox.GetEnd().y;
927  aOutlines.Append( corner );
928 
929  aOutlines.Append( bbbox.GetEnd() );
930 
931  corner.x = bbbox.GetEnd().x;
932  corner.y = bbbox.GetOrigin().y;
933  aOutlines.Append( corner );
934  }
935 
936  return success;
937 }
int OutlineCount() const
Return the number of vertices in a given outline/hole.
const EDA_RECT GetBoardEdgesBoundingBox() const
Returns the board bounding box calculated using exclusively the board edges (graphics on Edge....
Definition: board.h:803
int GetWidth() const
Definition: eda_rect.h:114
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:87
const wxPoint GetEnd() const
Definition: eda_rect.h:108
const wxPoint GetOrigin() const
Definition: eda_rect.h:106
int NewOutline()
Creates a new hole in a given outline.
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,...
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:605
int GetHeight() const
Definition: eda_rect.h:115
Handle the component boundary box.
Definition: eda_rect.h:42
static bool GetLayer(MODEL_VRML &aModel, LAYER_NUM layer, VRML_LAYER **vlayer)
EDA_RECT ComputeBoundingBox(bool aBoardEdgesOnly=false) const
Calculate the bounding box containing all board items (or board edge segments).
Definition: board.cpp:1029
Collect all BOARD_ITEM objects of a given set of KICAD_T type(s).
Definition: collectors.h:618
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:363
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(), GetLayer(), 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 1091 of file convert_drawsegment_list_to_polygon.cpp.

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

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

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 73 of file convert_drawsegment_list_to_polygon.cpp.

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

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 177 of file convert_drawsegment_list_to_polygon.cpp.

180 {
181  if( aSegList.size() == 0 )
182  return true;
183 
184  bool polygonComplete = false;
185  bool selfIntersecting = false;
186 
187  wxString msg;
188  PCB_SHAPE* graphic = nullptr;
189 
190  std::set<PCB_SHAPE*> startCandidates( aSegList.begin(), aSegList.end() );
191 
192  // Find edge point with minimum x, this should be in the outer polygon
193  // which will define the perimeter polygon polygon.
194  wxPoint xmin = wxPoint( INT_MAX, 0 );
195  int xmini = 0;
196 
197  for( size_t i = 0; i < aSegList.size(); i++ )
198  {
199  graphic = (PCB_SHAPE*) aSegList[i];
200  graphic->ClearFlags( SKIP_STRUCT );
201 
202  switch( graphic->GetShape() )
203  {
204  case S_RECT:
205  case S_SEGMENT:
206  {
207  if( graphic->GetStart().x < xmin.x )
208  {
209  xmin = graphic->GetStart();
210  xmini = i;
211  }
212 
213  if( graphic->GetEnd().x < xmin.x )
214  {
215  xmin = graphic->GetEnd();
216  xmini = i;
217  }
218  }
219  break;
220 
221  case S_ARC:
222  {
223  wxPoint pstart = graphic->GetArcStart();
224  wxPoint center = graphic->GetCenter();
225  double angle = -graphic->GetAngle();
226  double radius = graphic->GetRadius();
227  int steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
228  wxPoint pt;
229 
230  for( int step = 1; step<=steps; ++step )
231  {
232  double rotation = ( angle * step ) / steps;
233 
234  pt = pstart;
235 
236  RotatePoint( &pt, center, rotation );
237 
238  if( pt.x < xmin.x )
239  {
240  xmin = pt;
241  xmini = i;
242  }
243  }
244  }
245  break;
246 
247  case S_CIRCLE:
248  {
249  wxPoint pt = graphic->GetCenter();
250 
251  // pt has minimum x point
252  pt.x -= graphic->GetRadius();
253 
254  // when the radius <= 0, this is a mal-formed circle. Skip it
255  if( graphic->GetRadius() > 0 && pt.x < xmin.x )
256  {
257  xmin = pt;
258  xmini = i;
259  }
260  }
261  break;
262 
263  case S_CURVE:
264  {
265  graphic->RebuildBezierToSegmentsPointsList( graphic->GetWidth() );
266 
267  for( const wxPoint& pt : graphic->GetBezierPoints() )
268  {
269  if( pt.x < xmin.x )
270  {
271  xmin = pt;
272  xmini = i;
273  }
274  }
275  }
276  break;
277 
278  case S_POLYGON:
279  {
280  const SHAPE_POLY_SET poly = graphic->GetPolyShape();
281  double orientation = 0.0;
282  VECTOR2I offset = VECTOR2I( 0, 0 );
283 
284  if( graphic->GetParentFootprint() )
285  {
286  orientation = graphic->GetParentFootprint()->GetOrientation();
287  offset = graphic->GetParentFootprint()->GetPosition();
288  }
289 
290  for( auto iter = poly.CIterate(); iter; iter++ )
291  {
292  VECTOR2I pt = *iter;
293  RotatePoint( pt, orientation );
294  pt += offset;
295 
296  if( pt.x < xmin.x )
297  {
298  xmin.x = pt.x;
299  xmin.y = pt.y;
300  xmini = i;
301  }
302  }
303  }
304  break;
305 
306  default:
307  break;
308  }
309  }
310 
311  // Keep a list of where the various segments came from so after doing our combined-polygon
312  // tests we can still report errors against the individual graphic items.
313  std::map<std::pair<VECTOR2I, VECTOR2I>, PCB_SHAPE*> segOwners;
314 
315  auto fetchOwner =
316  [&]( const SEG& seg ) -> PCB_SHAPE*
317  {
318  auto it = segOwners.find( std::make_pair( seg.A, seg.B ) );
319  return it == segOwners.end() ? nullptr : it->second;
320  };
321 
322  // Grab the left most point, assume its on the board's perimeter, and see if we can put
323  // enough graphics together by matching endpoints to formulate a cohesive polygon.
324 
325  PCB_SHAPE* prevGraphic = nullptr;
326  wxPoint prevPt;
327 
328  graphic = (PCB_SHAPE*) aSegList[xmini];
329  graphic->SetFlags( SKIP_STRUCT );
330  startCandidates.erase( graphic );
331 
332  // Output the outline perimeter as polygon.
333  if( graphic->GetShape() == S_CIRCLE )
334  {
335  TransformCircleToPolygon( aPolygons, graphic->GetCenter(), graphic->GetRadius(),
336  ARC_LOW_DEF, ERROR_INSIDE );
337  polygonComplete = true;
338  }
339  else if( graphic->GetShape() == S_RECT )
340  {
341  std::vector<wxPoint> pts = graphic->GetRectCorners();
342 
343  aPolygons.NewOutline();
344 
345  for( const wxPoint& pt : pts )
346  aPolygons.Append( pt );
347 
348  segOwners[ std::make_pair( pts[0], pts[1] ) ] = graphic;
349  segOwners[ std::make_pair( pts[1], pts[2] ) ] = graphic;
350  segOwners[ std::make_pair( pts[2], pts[3] ) ] = graphic;
351  segOwners[ std::make_pair( pts[3], pts[0] ) ] = graphic;
352 
353  polygonComplete = true;
354  }
355  else if( graphic->GetShape() == S_POLYGON )
356  {
357  double orientation = 0.0;
358  VECTOR2I offset = VECTOR2I( 0, 0 );
359 
360  if( graphic->GetParentFootprint() )
361  {
362  orientation = graphic->GetParentFootprint()->GetOrientation();
363  offset = graphic->GetParentFootprint()->GetPosition();
364  }
365 
366  aPolygons.NewOutline();
367  bool first = true;
368 
369  for( auto it = graphic->GetPolyShape().CIterate( 0 ); it; it++ )
370  {
371  VECTOR2I pt = *it;
372  RotatePoint( pt, orientation );
373  pt += offset;
374  aPolygons.Append( pt );
375 
376  if( first )
377  first = false;
378  else
379  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
380 
381  prevPt = (wxPoint) pt;
382  }
383 
384  polygonComplete = true;
385  }
386  else
387  {
388  // Polygon start point. Arbitrarily chosen end of the
389  // segment and build the poly from here.
390 
391  wxPoint startPt = graphic->GetShape() == S_ARC ? graphic->GetArcEnd()
392  : graphic->GetEnd();
393 
394  prevPt = startPt;
395  aPolygons.NewOutline();
396  aPolygons.Append( prevPt );
397 
398  // Do not append the other end point yet of this 'graphic', this first
399  // 'graphic' might be an arc or a curve.
400 
401  for(;;)
402  {
403  switch( graphic->GetShape() )
404  {
405  case S_RECT:
406  case S_CIRCLE:
407  {
408  // As a non-first item, closed shapes can't be anything but self-intersecting
409 
410  if( aErrorHandler )
411  {
412  wxASSERT( prevGraphic );
413  (*aErrorHandler)( _( "(self-intersecting)" ), prevGraphic, graphic, prevPt );
414  }
415 
416  selfIntersecting = true;
417 
418  // A closed shape will finish where it started, so no point in updating prevPt
419  }
420  break;
421 
422  case S_SEGMENT:
423  {
424  wxPoint nextPt;
425 
426  // Use the line segment end point furthest away from prevPt as we assume
427  // the other end to be ON prevPt or very close to it.
428 
429  if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
430  nextPt = graphic->GetEnd();
431  else
432  nextPt = graphic->GetStart();
433 
434  aPolygons.Append( nextPt );
435  segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
436  prevPt = nextPt;
437  }
438  break;
439 
440  case S_ARC:
441  {
442  // We do not support arcs in polygons, so approximate an arc with a series of
443  // short lines and put those line segments into the !same! PATH.
444 
445  wxPoint pstart = graphic->GetArcStart();
446  wxPoint pend = graphic->GetArcEnd();
447  wxPoint pcenter = graphic->GetCenter();
448  double angle = -graphic->GetAngle();
449  double radius = graphic->GetRadius();
450  int steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
451 
452  if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
453  {
454  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(), aChainingEpsilon ) );
455 
456  angle = -angle;
457  std::swap( pstart, pend );
458  }
459 
460  // Create intermediate points between start and end:
461  for( int step = 1; step < steps; ++step )
462  {
463  double rotation = ( angle * step ) / steps;
464  wxPoint pt = pstart;
465  RotatePoint( &pt, pcenter, rotation );
466 
467  aPolygons.Append( pt );
468  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
469  prevPt = pt;
470  }
471 
472  // Append the last arc end point
473  aPolygons.Append( pend );
474  segOwners[ std::make_pair( prevPt, pend ) ] = graphic;
475  prevPt = pend;
476  }
477  break;
478 
479  case S_CURVE:
480  {
481  // We do not support Bezier curves in polygons, so approximate with a series
482  // of short lines and put those line segments into the !same! PATH.
483 
484  wxPoint nextPt;
485  bool first = true;
486  bool reverse = false;
487 
488  // Use the end point furthest away from
489  // prevPt as we assume the other end to be ON prevPt or
490  // very close to it.
491 
492  if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
493  {
494  nextPt = graphic->GetEnd();
495  }
496  else
497  {
498  nextPt = graphic->GetStart();
499  reverse = true;
500  }
501 
502  if( reverse )
503  {
504  for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
505  {
506  const wxPoint& pt = graphic->GetBezierPoints()[jj];
507  aPolygons.Append( pt );
508 
509  if( first )
510  first = false;
511  else
512  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
513 
514  prevPt = pt;
515  }
516  }
517  else
518  {
519  for( const wxPoint& pt : graphic->GetBezierPoints() )
520  {
521  aPolygons.Append( pt );
522 
523  if( first )
524  first = false;
525  else
526  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
527 
528  prevPt = pt;
529  }
530  }
531 
532  prevPt = nextPt;
533  }
534  break;
535 
536  default:
537  wxFAIL_MSG( "Unsupported PCB_SHAPE type "
538  + BOARD_ITEM::ShowShape( graphic->GetShape() ) );
539  return false;
540  }
541 
542  // Get next closest segment.
543 
544  PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, aChainingEpsilon );
545 
546  if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
547  {
548  prevGraphic = graphic;
549  graphic = nextGraphic;
550  graphic->SetFlags( SKIP_STRUCT );
551  startCandidates.erase( graphic );
552  continue;
553  }
554 
555  // Finished, or ran into trouble...
556 
557  if( close_enough( startPt, prevPt, aChainingEpsilon ) )
558  {
559  polygonComplete = true;
560  break;
561  }
562  else if( nextGraphic ) // encountered already-used segment, but not at the start
563  {
564  if( aErrorHandler )
565  (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
566 
567  polygonComplete = false;
568  break;
569  }
570  else // encountered discontinuity
571  {
572  if( aErrorHandler )
573  (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
574 
575  polygonComplete = false;
576  break;
577  }
578  }
579  }
580 
581  int holeNum = -1;
582 
583  while( startCandidates.size() )
584  {
585  int hole = aPolygons.NewHole();
586  bool firstPt = true;
587  holeNum++;
588 
589  graphic = (PCB_SHAPE*) *startCandidates.begin();
590  graphic->SetFlags( SKIP_STRUCT );
591  startCandidates.erase( startCandidates.begin() );
592 
593  // Both circles and polygons on the edge cuts layer are closed items that
594  // do not connect to other elements, so we process them independently
595  if( graphic->GetShape() == S_POLYGON )
596  {
597  double orientation = 0.0;
598  VECTOR2I offset = VECTOR2I( 0, 0 );
599 
600  if( graphic->GetParentFootprint() )
601  {
602  orientation = graphic->GetParentFootprint()->GetOrientation();
603  offset = graphic->GetParentFootprint()->GetPosition();
604  }
605 
606  for( auto it = graphic->GetPolyShape().CIterate(); it; it++ )
607  {
608  VECTOR2I pt = *it;
609  RotatePoint( pt, orientation );
610  pt += offset;
611 
612  aPolygons.Append( pt, -1, hole );
613 
614  if( firstPt )
615  firstPt = false;
616  else
617  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
618 
619  prevPt = (wxPoint) pt;
620  }
621  }
622  else if( graphic->GetShape() == S_CIRCLE )
623  {
624  // make a circle by segments;
625  wxPoint center = graphic->GetCenter();
626  double angle = 3600.0;
627  wxPoint start = center;
628  int radius = graphic->GetRadius();
629  int steps = GetArcToSegmentCount( radius, aErrorMax, 360.0 );
630  wxPoint nextPt;
631 
632  start.x += radius;
633 
634  for( int step = 0; step < steps; ++step )
635  {
636  double rotation = ( angle * step ) / steps;
637  nextPt = start;
638  RotatePoint( &nextPt.x, &nextPt.y, center.x, center.y, rotation );
639  aPolygons.Append( nextPt, -1, hole );
640 
641  if( firstPt )
642  firstPt = false;
643  else
644  segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
645 
646  prevPt = nextPt;
647  }
648  }
649  else if( graphic->GetShape() == S_RECT )
650  {
651  std::vector<wxPoint> pts = graphic->GetRectCorners();
652 
653  for( const wxPoint& pt : pts )
654  {
655  aPolygons.Append( pt, -1, hole );
656 
657  if( firstPt )
658  firstPt = false;
659  else
660  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
661 
662  prevPt = (wxPoint) pt;
663  }
664  }
665  else
666  {
667  // Polygon start point. Arbitrarily chosen end of the segment and build the poly
668  // from here.
669 
670  wxPoint startPt( graphic->GetEnd() );
671  prevPt = graphic->GetEnd();
672  aPolygons.Append( prevPt, -1, hole );
673 
674  // do not append the other end point yet, this first 'graphic' might be an arc
675  for(;;)
676  {
677  switch( graphic->GetShape() )
678  {
679  case S_SEGMENT:
680  {
681  wxPoint nextPt;
682 
683  // Use the line segment end point furthest away from
684  // prevPt as we assume the other end to be ON prevPt or
685  // very close to it.
686 
687  if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
688  nextPt = graphic->GetEnd();
689  else
690  nextPt = graphic->GetStart();
691 
692  aPolygons.Append( nextPt, -1, hole );
693  segOwners[ std::make_pair( prevPt, nextPt ) ] = graphic;
694  prevPt = nextPt;
695  }
696  break;
697 
698  case S_ARC:
699  // We do not support arcs in polygons, so approximate an arc with a series of
700  // short lines and put those line segments into the !same! PATH.
701  {
702  wxPoint pstart = graphic->GetArcStart();
703  wxPoint pend = graphic->GetArcEnd();
704  wxPoint pcenter = graphic->GetCenter();
705  double angle = -graphic->GetAngle();
706  int radius = graphic->GetRadius();
707  int steps = GetArcToSegmentCount( radius, aErrorMax, angle / 10.0 );
708 
709  if( !close_enough( prevPt, pstart, aChainingEpsilon ) )
710  {
711  wxASSERT( close_enough( prevPt, graphic->GetArcEnd(),
712  aChainingEpsilon ) );
713 
714  angle = -angle;
715  std::swap( pstart, pend );
716  }
717 
718  // Create intermediate points between start and end:
719  for( int step = 1; step < steps; ++step )
720  {
721  double rotation = ( angle * step ) / steps;
722  wxPoint pt = pstart;
723  RotatePoint( &pt, pcenter, rotation );
724 
725  aPolygons.Append( pt, -1, hole );
726  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
727  prevPt = pt;
728  }
729 
730  // Append the last arc end point
731  aPolygons.Append( pend, -1, hole );
732  segOwners[ std::make_pair( prevPt, pend ) ] = graphic;
733  prevPt = pend;
734  }
735  break;
736 
737  case S_CURVE:
738  // We do not support Bezier curves in polygons, so approximate with a series
739  // of short lines and put those line segments into the !same! PATH.
740  {
741  wxPoint nextPt;
742  bool reverse = false;
743 
744  // Use the end point furthest away from
745  // prevPt as we assume the other end to be ON prevPt or
746  // very close to it.
747 
748  if( closer_to_first( prevPt, graphic->GetStart(), graphic->GetEnd()) )
749  {
750  nextPt = graphic->GetEnd();
751  }
752  else
753  {
754  nextPt = graphic->GetStart();
755  reverse = true;
756  }
757 
758  if( reverse )
759  {
760  for( int jj = graphic->GetBezierPoints().size()-1; jj >= 0; jj-- )
761  {
762  const wxPoint& pt = graphic->GetBezierPoints()[jj];
763  aPolygons.Append( pt, -1, hole );
764  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
765  prevPt = pt;
766  }
767  }
768  else
769  {
770  for( const wxPoint& pt : graphic->GetBezierPoints() )
771  {
772  aPolygons.Append( pt, -1, hole );
773  segOwners[ std::make_pair( prevPt, pt ) ] = graphic;
774  prevPt = pt;
775  }
776  }
777 
778  prevPt = nextPt;
779  }
780  break;
781 
782  default:
783  wxFAIL_MSG( "Unsupported PCB_SHAPE type "
784  + BOARD_ITEM::ShowShape( graphic->GetShape() ) );
785 
786  return false;
787  }
788 
789  // Get next closest segment.
790 
791  PCB_SHAPE* nextGraphic = findNext( graphic, prevPt, aSegList, aChainingEpsilon );
792 
793  if( nextGraphic && !( nextGraphic->GetFlags() & SKIP_STRUCT ) )
794  {
795  graphic = nextGraphic;
796  graphic->SetFlags( SKIP_STRUCT );
797  startCandidates.erase( graphic );
798  continue;
799  }
800 
801  // Finished, or ran into trouble...
802 
803  if( close_enough( startPt, prevPt, aChainingEpsilon ) )
804  {
805  break;
806  }
807  else if( nextGraphic ) // encountered already-used segment, but not at the start
808  {
809  if( aErrorHandler )
810  (*aErrorHandler)( _( "(self-intersecting)" ), graphic, nextGraphic, prevPt );
811 
812  polygonComplete = false;
813  break;
814  }
815  else // encountered discontinuity
816  {
817  if( aErrorHandler )
818  (*aErrorHandler)( _( "(not a closed shape)" ), graphic, nullptr, prevPt );
819 
820  polygonComplete = false;
821  break;
822  }
823  }
824  }
825  }
826 
827  if( !polygonComplete )
828  return false;
829 
830  // All of the silliness that follows is to work around the segment iterator while checking
831  // for collisions.
832  // TODO: Implement proper segment and point iterators that follow std
833 
834  for( auto seg1 = aPolygons.IterateSegmentsWithHoles(); seg1; seg1++ )
835  {
836  auto seg2 = seg1;
837 
838  for( ++seg2; seg2; seg2++ )
839  {
840  // Check for exact overlapping segments.
841  if( *seg1 == *seg2 || ( ( *seg1 ).A == ( *seg2 ).B && ( *seg1 ).B == ( *seg2 ).A ) )
842  {
843  if( aErrorHandler )
844  {
845  BOARD_ITEM* a = fetchOwner( *seg1 );
846  BOARD_ITEM* b = fetchOwner( *seg2 );
847  (*aErrorHandler)( _( "(self-intersecting)" ), a, b, (wxPoint) ( *seg1 ).A );
848  }
849 
850  selfIntersecting = true;
851  }
852 
853  if( boost::optional<VECTOR2I> pt = seg1.Get().Intersect( seg2.Get(), true ) )
854  {
855  if( aErrorHandler )
856  {
857  BOARD_ITEM* a = fetchOwner( *seg1 );
858  BOARD_ITEM* b = fetchOwner( *seg2 );
859  (*aErrorHandler)( _( "(self-intersecting)" ), a, b, (wxPoint) pt.get() );
860  }
861 
862  selfIntersecting = true;
863  }
864  }
865  }
866 
867  return !selfIntersecting;
868 }
wxPoint GetArcEnd() const
Definition: pcb_shape.cpp:373
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
SHAPE_POLY_SET & GetPolyShape()
Definition: pcb_shape.h:268
const wxPoint & GetEnd() const
Function GetEnd returns the ending point of the graphic.
Definition: pcb_shape.h:156
A base class for any item which can be embedded within the BOARD container class, and therefore insta...
Definition: board_item.h:82
int GetRadius() const
Function GetRadius returns the radius of this item Has meaning only for arc and circle.
Definition: pcb_shape.h:201
std::vector< wxPoint > GetRectCorners() const
Definition: pcb_shape.cpp:970
int GetWidth() const
Definition: pcb_shape.h:118
polygon (not yet used for tracks, but could be in microwave apps)
Definition: board_item.h:54
double GetOrientation() const
Definition: footprint.h:186
static wxString ShowShape(PCB_SHAPE_TYPE_T aShape)
Convert the enum PCB_SHAPE_TYPE_T integer value to a wxString.
Definition: board_item.cpp:31
usual segment : line with rounded ends
Definition: board_item.h:50
Arcs (with rounded ends)
Definition: board_item.h:52
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:228
segment with non rounded ends
Definition: board_item.h:51
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
wxPoint GetArcStart() const
Definition: pcb_shape.h:179
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 SetFlags(STATUS_FLAGS aMask)
Definition: eda_item.h:202
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.cpp:341
const wxPoint & GetStart() const
Function GetStart returns the starting point of the graphic.
Definition: pcb_shape.h:145
const std::vector< wxPoint > & GetBezierPoints() const
Definition: pcb_shape.h:253
int NewOutline()
Creates a new hole in a given outline.
CONST_ITERATOR CIterate(int aFirst, int aLast, bool aIterateHoles=false) const
Definition: seg.h:41
FOOTPRINT * GetParentFootprint() const
Function GetParentFootprint returns a pointer to the parent footprint, or NULL if PCB_SHAPE does not ...
Definition: pcb_shape.cpp:478
#define _(s)
Definition: 3d_actions.cpp:33
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
double GetAngle() const
Definition: pcb_shape.h:127
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.
void TransformCircleToPolygon(SHAPE_LINE_CHAIN &aCornerBuffer, wxPoint aCenter, int aRadius, int aError, ERROR_LOC aErrorLoc)
Function TransformCircleToPolygon convert a circle to a polygon, using multiple straight lines.
wxPoint GetPosition() const override
Definition: footprint.h:182
void RebuildBezierToSegmentsPointsList(int aMinSegLen)
Rebuild the m_BezierPoints vertex list that approximate the Bezier curve by a list of segments Has me...
Definition: pcb_shape.cpp:315
void ClearFlags(STATUS_FLAGS aMask=EDA_ITEM_ALL_FLAGS)
Definition: eda_item.h:203
ring
Definition: board_item.h:53
PCB_SHAPE_TYPE_T GetShape() const
Definition: pcb_shape.h:130
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.
#define SKIP_STRUCT
flag indicating that the structure should be ignored
Definition: eda_item.h:117
STATUS_FLAGS GetFlags() const
Definition: eda_item.h:204
Bezier Curve.
Definition: board_item.h:55
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(), SHAPE_POLY_SET::CIterate(), EDA_ITEM::ClearFlags(), close_enough(), closer_to_first(), ERROR_INSIDE, findNext(), PCB_SHAPE::GetAngle(), PCB_SHAPE::GetArcEnd(), PCB_SHAPE::GetArcStart(), GetArcToSegmentCount(), PCB_SHAPE::GetBezierPoints(), PCB_SHAPE::GetCenter(), PCB_SHAPE::GetEnd(), EDA_ITEM::GetFlags(), FOOTPRINT::GetOrientation(), PCB_SHAPE::GetParentFootprint(), PCB_SHAPE::GetPolyShape(), FOOTPRINT::GetPosition(), PCB_SHAPE::GetRadius(), PCB_SHAPE::GetRectCorners(), PCB_SHAPE::GetShape(), PCB_SHAPE::GetStart(), PCB_SHAPE::GetWidth(), SHAPE_POLY_SET::IterateSegmentsWithHoles(), SHAPE_POLY_SET::NewHole(), SHAPE_POLY_SET::NewOutline(), PCB_SHAPE::RebuildBezierToSegmentsPointsList(), RotatePoint(), S_ARC, S_CIRCLE, S_CURVE, S_POLYGON, S_RECT, S_SEGMENT, EDA_ITEM::SetFlags(), BOARD_ITEM::ShowShape(), SKIP_STRUCT, TransformCircleToPolygon(), 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 1027 of file convert_drawsegment_list_to_polygon.cpp.

1028 {
1029  int foundSegs = 0;
1030 
1031  for( int i = 0; i < aChain.SegmentCount(); i++ )
1032  {
1033  SEG seg = aChain.Segment( i );
1034 
1035  bool foundA = false;
1036  bool foundB = false;
1037 
1038  for( int j = 0; j < aChain.SegmentCount(); j++ )
1039  {
1040  // Don't test the segment against itself
1041  if( i == j )
1042  continue;
1043 
1044  SEG testSeg = aChain.Segment( j );
1045 
1046  if( testSeg.Contains( seg.A ) )
1047  foundA = true;
1048 
1049  if( testSeg.Contains( seg.B ) )
1050  foundB = true;
1051  }
1052 
1053  // This segment isn't a start or end
1054  if( foundA && foundB )
1055  continue;
1056 
1057  if( foundSegs == 0 )
1058  {
1059  // The first segment we encounter is the "start" segment
1060  wxLogTrace( traceBoardOutline, "Found start segment: (%d, %d)-(%d, %d)",
1061  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1062  aStartSeg = seg;
1063  foundSegs++;
1064  }
1065  else
1066  {
1067  // Once we find both start and end, we can stop
1068  wxLogTrace( traceBoardOutline, "Found end segment: (%d, %d)-(%d, %d)",
1069  seg.A.x, seg.A.y, seg.B.x, seg.B.y );
1070  aEndSeg = seg;
1071  foundSegs++;
1072  break;
1073  }
1074  }
1075 
1076  return foundSegs;
1077 }
const wxChar * traceBoardOutline
Flag to enable debug tracing for the board outline creation.
int SegmentCount() const
Function SegmentCount()
Definition: seg.h:41
SEG Segment(int aIndex)
Function Segment()
VECTOR2I A
Definition: seg.h:49
bool Contains(const SEG &aSeg) const
Definition: seg.h:321
VECTOR2I B
Definition: seg.h:50

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 88 of file convert_drawsegment_list_to_polygon.cpp.

90 {
91  // Look for an unused, exact hit
92  for( PCB_SHAPE* graphic : aList )
93  {
94  if( graphic == aShape || ( graphic->GetFlags() & SKIP_STRUCT ) != 0 )
95  continue;
96 
97  switch( graphic->GetShape() )
98  {
99  case S_ARC:
100  if( aPoint == graphic->GetArcStart() || aPoint == graphic->GetArcEnd() )
101  return graphic;
102 
103  break;
104 
105  default:
106  if( aPoint == graphic->GetStart() || aPoint == graphic->GetEnd() )
107  return graphic;
108  }
109  }
110 
111  // Search again for anything that's close, even something already used. (The latter is
112  // important for error reporting.)
113  VECTOR2I pt( aPoint );
114  SEG::ecoord closest_dist_sq = SEG::Square( aLimit );
115  PCB_SHAPE* closest_graphic = nullptr;
116  SEG::ecoord d_sq;
117 
118  for( PCB_SHAPE* graphic : aList )
119  {
120  if( graphic == aShape )
121  continue;
122 
123  switch( graphic->GetShape() )
124  {
125  case S_ARC:
126  d_sq = ( pt - graphic->GetArcStart() ).SquaredEuclideanNorm();
127 
128  if( d_sq < closest_dist_sq )
129  {
130  closest_dist_sq = d_sq;
131  closest_graphic = graphic;
132  }
133 
134  d_sq = ( pt - graphic->GetArcEnd() ).SquaredEuclideanNorm();
135 
136  if( d_sq < closest_dist_sq )
137  {
138  closest_dist_sq = d_sq;
139  closest_graphic = graphic;
140  }
141  break;
142 
143  default:
144  d_sq = ( pt - graphic->GetStart() ).SquaredEuclideanNorm();
145 
146  if( d_sq < closest_dist_sq )
147  {
148  closest_dist_sq = d_sq;
149  closest_graphic = graphic;
150  }
151 
152  d_sq = ( pt - graphic->GetEnd() ).SquaredEuclideanNorm();
153 
154  if( d_sq < closest_dist_sq )
155  {
156  closest_dist_sq = d_sq;
157  closest_graphic = graphic;
158  }
159  }
160  }
161 
162  return closest_graphic; // Note: will be nullptr if nothing within aLimit
163 }
VECTOR2I::extended_type ecoord
Definition: seg.h:44
Arcs (with rounded ends)
Definition: board_item.h:52
static SEG::ecoord Square(int a)
Definition: seg.h:123
#define SKIP_STRUCT
flag indicating that the structure should be ignored
Definition: eda_item.h:117

References S_ARC, 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 979 of file convert_drawsegment_list_to_polygon.cpp.

980 {
981  bool padOutside = false;
982 
983  for( PAD* pad : aMod->Pads() )
984  {
985  SHAPE_POLY_SET poly = aShape;
986 
987  poly.BooleanIntersection( *pad->GetEffectivePolygon(), SHAPE_POLY_SET::PM_FAST );
988 
989  if( poly.OutlineCount() == 0 )
990  {
991  wxPoint padPos = pad->GetPosition();
992  wxLogTrace( traceBoardOutline, "Tested pad (%d, %d): outside", padPos.x, padPos.y );
993  padOutside = true;
994  break;
995  }
996 
997  wxPoint padPos = pad->GetPosition();
998  wxLogTrace( traceBoardOutline, "Tested pad (%d, %d): not outside", padPos.x, padPos.y );
999  }
1000 
1001  return padOutside;
1002 }
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:164
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:60

References SHAPE_POLY_SET::BooleanIntersection(), SHAPE_POLY_SET::OutlineCount(), 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 1005 of file convert_drawsegment_list_to_polygon.cpp.

1007 {
1008  int minDistance = -1;
1009  VECTOR2I projPoint;
1010 
1011  for( auto it = aOutline.CIterateSegments( aOutlineNum ); it; it++ )
1012  {
1013  auto seg = it.Get();
1014  int dis = seg.Distance( aEndPoint );
1015 
1016  if( minDistance < 0 || ( dis < minDistance ) )
1017  {
1018  minDistance = dis;
1019  projPoint = seg.NearestPoint( aEndPoint );
1020  }
1021  }
1022 
1023  return projPoint;
1024 }
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().