KiCad PCB EDA Suite
spread_footprints.cpp File Reference

functions to spread footprints on free areas outside a board. More...

#include <spread_footprints.h>
#include <optional>
#include <algorithm>
#include <refdes_utils.h>
#include <string_utils.h>
#include <confirm.h>
#include <pcb_edit_frame.h>
#include <board.h>
#include <rectpack2d/finders_interface.h>

Go to the source code of this file.

Typedefs

using spaces_type = rectpack2D::empty_spaces< allow_flip, rectpack2D::default_empty_spaces >
 
using rect_type = rectpack2D::output_rect_t< spaces_type >
 
using rect_ptr = rect_type *
 
using rect_vector = std::vector< rect_type >
 

Functions

static bool compareFootprintsbyRef (FOOTPRINT *ref, FOOTPRINT *compare)
 
std::optional< rectpack2D::rect_wh > spreadRectangles (rect_vector &vecSubRects, int areaSizeX, int areaSizeY)
 
void SpreadFootprints (std::vector< FOOTPRINT * > *aFootprints, VECTOR2I aTargetBoxPosition, bool aGroupBySheet, int aComponentGap, int aGroupGap)
 Footprints (after loaded by reading a netlist for instance) are moved to be in a small free area (outside the current board) without overlapping. More...
 

Variables

constexpr bool allow_flip = true
 
const int scale = (int) ( 0.01 * pcbIUScale.IU_PER_MM )
 

Detailed Description

functions to spread footprints on free areas outside a board.

this is useful after reading a netlist, when new footprints are loaded and stacked at 0,0 coordinate. Often, spread them on a free area near the board being edited make more easy their selection.

Definition in file spread_footprints.cpp.

Typedef Documentation

◆ rect_ptr

using rect_ptr = rect_type*

Definition at line 52 of file spread_footprints.cpp.

◆ rect_type

using rect_type = rectpack2D::output_rect_t<spaces_type>

Definition at line 51 of file spread_footprints.cpp.

◆ rect_vector

using rect_vector = std::vector<rect_type>

Definition at line 53 of file spread_footprints.cpp.

◆ spaces_type

using spaces_type = rectpack2D::empty_spaces<allow_flip, rectpack2D::default_empty_spaces>

Definition at line 50 of file spread_footprints.cpp.

Function Documentation

◆ compareFootprintsbyRef()

static bool compareFootprintsbyRef ( FOOTPRINT ref,
FOOTPRINT compare 
)
static

Definition at line 59 of file spread_footprints.cpp.

60{
61 const wxString& refPrefix = UTIL::GetRefDesPrefix( ref->GetReference() );
62 const wxString& cmpPrefix = UTIL::GetRefDesPrefix( compare->GetReference() );
63
64 if( refPrefix != cmpPrefix )
65 {
66 return refPrefix < cmpPrefix;
67 }
68 else
69 {
70 const int refInt = GetTrailingInt( ref->GetReference() );
71 const int cmpInt = GetTrailingInt( compare->GetReference() );
72
73 return refInt < cmpInt;
74 }
75
76 return false;
77}
const wxString & GetReference() const
Definition: footprint.h:519
wxString GetRefDesPrefix(const wxString &aRefDes)
Get the (non-numeric) prefix from a refdes - e.g.
int GetTrailingInt(const wxString &aStr)
Gets the trailing int, if any, from a string.

References UTIL::GetRefDesPrefix(), FOOTPRINT::GetReference(), and GetTrailingInt().

Referenced by SpreadFootprints().

◆ SpreadFootprints()

void SpreadFootprints ( std::vector< FOOTPRINT * > *  aFootprints,
VECTOR2I  aTargetBoxPosition,
bool  aGroupBySheet = true,
int  aComponentGap = pcbIUScale.mmToIU(1),
int  aGroupGap = pcbIUScale.mmToIU(1.5) 
)

Footprints (after loaded by reading a netlist for instance) are moved to be in a small free area (outside the current board) without overlapping.

Parameters
aBoardis the board to edit.
aFootprintsa list of footprints to be spread out.
aTargetBoxPositionthe position of the upper left corner of the area allowed to spread footprints

Definition at line 125 of file spread_footprints.cpp.

127{
128 using FpBBoxToFootprintsPair = std::pair<BOX2I, std::vector<FOOTPRINT*>>;
129 using SheetBBoxToFootprintsMapPair =
130 std::pair<BOX2I, std::map<VECTOR2I, FpBBoxToFootprintsPair>>;
131
132 std::map<wxString, SheetBBoxToFootprintsMapPair> sheetsMap;
133
134 // Fill in the maps
135 for( FOOTPRINT* footprint : *aFootprints )
136 {
137 wxString path =
138 aGroupBySheet ? footprint->GetPath().AsString().BeforeLast( '/' ) : wxString( wxS( "" ) );
139
140 VECTOR2I size = footprint->GetBoundingBox( false, false ).GetSize();
141 size.x += aComponentGap;
142 size.y += aComponentGap;
143
144 sheetsMap[path].second[size].second.push_back( footprint );
145 }
146
147 for( auto& [sheetPath, sheetPair] : sheetsMap )
148 {
149 auto& [sheet_bbox, sizeToFpMap] = sheetPair;
150
151 for( auto& [fpSize, fpPair] : sizeToFpMap )
152 {
153 auto& [block_bbox, footprints] = fpPair;
154
155 // Find optimal arrangement of same-size footprints
156
157 double blockEstimateArea = (double) fpSize.x * fpSize.y * footprints.size();
158 double initialSide = std::sqrt( blockEstimateArea );
159 bool vertical = fpSize.x >= fpSize.y;
160
161 int initialCountPerLine = footprints.size();
162
163 const int singleLineRatio = 5;
164
165 // Wrap the line if the ratio is not satisfied
166 if( vertical )
167 {
168 if( ( fpSize.y * footprints.size() / fpSize.x ) > singleLineRatio )
169 initialCountPerLine = initialSide / fpSize.y;
170 }
171 else
172 {
173 if( ( fpSize.x * footprints.size() / fpSize.y ) > singleLineRatio )
174 initialCountPerLine = initialSide / fpSize.x;
175 }
176
177 int optimalCountPerLine = initialCountPerLine;
178 int optimalRemainder = footprints.size() % optimalCountPerLine;
179
180 if( optimalRemainder != 0 )
181 {
182 for( int i = std::max( 2, initialCountPerLine - 2 );
183 i <= std::min( (int) footprints.size() - 2, initialCountPerLine + 2 ); i++ )
184 {
185 int r = footprints.size() % i;
186
187 if( r == 0 || r >= optimalRemainder )
188 {
189 optimalCountPerLine = i;
190 optimalRemainder = r;
191 }
192 }
193 }
194
195 std::sort( footprints.begin(), footprints.end(), compareFootprintsbyRef );
196
197 // Arrange footprints in rows or columns (blocks)
198 for( unsigned i = 0; i < footprints.size(); i++ )
199 {
200 FOOTPRINT* footprint = footprints[i];
201
202 VECTOR2I position = fpSize / 2;
203
204 if( vertical )
205 {
206 position.x += fpSize.x * ( i / optimalCountPerLine );
207 position.y += fpSize.y * ( i % optimalCountPerLine );
208 }
209 else
210 {
211 position.x += fpSize.x * ( i % optimalCountPerLine );
212 position.y += fpSize.y * ( i / optimalCountPerLine );
213 }
214
215 BOX2I old_fp_bbox = footprint->GetBoundingBox( false, false );
216 footprint->Move( position - old_fp_bbox.GetOrigin() );
217
218 BOX2I new_fp_bbox = footprint->GetBoundingBox( false, false );
219 new_fp_bbox.Inflate( aComponentGap / 2 );
220 block_bbox.Merge( new_fp_bbox );
221 }
222 }
223
224 rect_vector vecSubRects;
225 long long blocksArea = 0;
226
227 // Fill in arrays for packing of blocks
228 for( auto& [fpSize, fpPair] : sizeToFpMap )
229 {
230 auto& [block_bbox, footprints] = fpPair;
231
232 vecSubRects.emplace_back( 0, 0, block_bbox.GetWidth() / scale,
233 block_bbox.GetHeight() / scale, false );
234
235 blocksArea += block_bbox.GetArea();
236 }
237
238 // Pack the blocks
239 int areaSide = std::sqrt( blocksArea );
240 spreadRectangles( vecSubRects, areaSide, areaSide );
241
242 unsigned block_i = 0;
243
244 // Move footprints to the new block locations
245 for( auto& [fpSize, pair] : sizeToFpMap )
246 {
247 auto& [src_bbox, footprints] = pair;
248
249 rect_type srect = vecSubRects[block_i];
250
251 VECTOR2I target_pos( srect.x * scale, srect.y * scale );
252 VECTOR2I target_size( srect.w * scale, srect.h * scale );
253
254 // Avoid too large coordinates: Overlapping components
255 // are better than out of screen components
256 if( (uint64_t) target_pos.x + (uint64_t) target_size.x > INT_MAX / 2 )
257 target_pos.x -= INT_MAX / 2;
258
259 if( (uint64_t) target_pos.y + (uint64_t) target_size.y > INT_MAX / 2 )
260 target_pos.y -= INT_MAX / 2;
261
262 for( FOOTPRINT* footprint : footprints )
263 {
264 footprint->Move( target_pos - src_bbox.GetPosition() );
265 sheet_bbox.Merge( footprint->GetBoundingBox( false, false ) );
266 }
267
268 block_i++;
269 }
270 }
271
272 rect_vector vecSubRects;
273 long long sheetsArea = 0;
274
275 // Fill in arrays for packing of hierarchical sheet groups
276 for( auto& [sheetPath, sheetPair] : sheetsMap )
277 {
278 auto& [sheet_bbox, sizeToFpMap] = sheetPair;
279 BOX2I rect = sheet_bbox;
280
281 // Add a margin around the sheet placement area:
282 rect.Inflate( aGroupGap );
283
284 vecSubRects.emplace_back( 0, 0, rect.GetWidth() / scale, rect.GetHeight() / scale, false );
285
286 sheetsArea += sheet_bbox.GetArea();
287 }
288
289 // Pack the hierarchical sheet groups
290 int areaSide = std::sqrt( sheetsArea );
291 spreadRectangles( vecSubRects, areaSide, areaSide );
292
293 unsigned srect_i = 0;
294
295 // Move footprints to the new hierarchical sheet group locations
296 for( auto& [sheetPath, sheetPair] : sheetsMap )
297 {
298 auto& [src_bbox, sizeToFpMap] = sheetPair;
299
300 rect_type srect = vecSubRects[srect_i];
301
302 VECTOR2I target_pos( srect.x * scale + aTargetBoxPosition.x,
303 srect.y * scale + aTargetBoxPosition.y );
304 VECTOR2I target_size( srect.w * scale, srect.h * scale );
305
306 // Avoid too large coordinates: Overlapping components
307 // are better than out of screen components
308 if( (uint64_t) target_pos.x + (uint64_t) target_size.x > INT_MAX / 2 )
309 target_pos.x -= INT_MAX / 2;
310
311 if( (uint64_t) target_pos.y + (uint64_t) target_size.y > INT_MAX / 2 )
312 target_pos.y -= INT_MAX / 2;
313
314 for( auto& [fpSize, fpPair] : sizeToFpMap )
315 {
316 auto& [block_bbox, footprints] = fpPair;
317 for( FOOTPRINT* footprint : footprints )
318 {
319 footprint->Move( target_pos - src_bbox.GetPosition() );
320 }
321 }
322
323 srect_i++;
324 }
325}
const Vec & GetOrigin() const
Definition: box2.h:183
coord_type GetHeight() const
Definition: box2.h:188
coord_type GetWidth() const
Definition: box2.h:187
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:506
ecoord_type GetArea() const
Return the area of the rectangle.
Definition: box2.h:701
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:588
void Move(const VECTOR2I &aMoveVector) override
Move this object.
Definition: footprint.cpp:1558
const BOX2I GetBoundingBox() const override
Return the orthogonal bounding box of this object for display purposes.
Definition: footprint.cpp:806
std::vector< rect_type > rect_vector
const int scale
std::optional< rectpack2D::rect_wh > spreadRectangles(rect_vector &vecSubRects, int areaSizeX, int areaSizeY)
rectpack2D::output_rect_t< spaces_type > rect_type
static bool compareFootprintsbyRef(FOOTPRINT *ref, FOOTPRINT *compare)

References compareFootprintsbyRef(), BOX2< Vec >::GetArea(), FOOTPRINT::GetBoundingBox(), BOX2< Vec >::GetHeight(), BOX2< Vec >::GetOrigin(), BOX2< Vec >::GetWidth(), BOX2< Vec >::Inflate(), BOX2< Vec >::Merge(), FOOTPRINT::Move(), path, scale, spreadRectangles(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by PCB_EDIT_FRAME::OnNetlistChanged(), and EDIT_TOOL::PackAndMoveFootprints().

◆ spreadRectangles()

std::optional< rectpack2D::rect_wh > spreadRectangles ( rect_vector vecSubRects,
int  areaSizeX,
int  areaSizeY 
)

Definition at line 81 of file spread_footprints.cpp.

83{
84 areaSizeX /= scale;
85 areaSizeY /= scale;
86
87 std::optional<rectpack2D::rect_wh> result;
88
89 int max_side = std::max( areaSizeX, areaSizeY );
90
91 for( int i = 0; i < 2000; i++ )
92 {
93 bool anyUnsuccessful = false;
94 const int discard_step = 1;
95
96 auto report_successful = [&]( rect_type& )
97 {
98 return rectpack2D::callback_result::CONTINUE_PACKING;
99 };
100
101 auto report_unsuccessful = [&]( rect_type& r )
102 {
103 anyUnsuccessful = true;
104 return rectpack2D::callback_result::ABORT_PACKING;
105 };
106
107 result = rectpack2D::find_best_packing<spaces_type>(
108 vecSubRects,
109 make_finder_input( max_side, discard_step, report_successful, report_unsuccessful,
110 rectpack2D::flipping_option::DISABLED ) );
111
112 if( !result || anyUnsuccessful )
113 {
114 max_side = (int) ( max_side * 1.2 );
115 continue;
116 }
117
118 break;
119 }
120
121 return result;
122}

References scale.

Referenced by SpreadFootprints().

Variable Documentation

◆ allow_flip

constexpr bool allow_flip = true
constexpr

Definition at line 48 of file spread_footprints.cpp.

◆ scale

const int scale = (int) ( 0.01 * pcbIUScale.IU_PER_MM )

Definition at line 56 of file spread_footprints.cpp.

Referenced by DXF_IMPORT_PLUGIN::addInsert(), ACTION_TOOLBAR::AddScaledSeparator(), GRID_MENU::BuildChoiceList(), Clamp_Text_PenSize(), KIGFX::GAL::ComputeWorldScreenMatrix(), KIGFX::CAIRO_PRINT_GAL::ComputeWorldScreenMatrix(), SCH_PLOTTER::createPSFiles(), EDA_3D_CANVAS::DoRePaint(), EESCHEMA_JOBS_HANDLER::doSymExportSvg(), COMMON_TOOLS::doZoomFit(), COMMON_TOOLS::doZoomToPreset(), KIGFX::CAIRO_GAL_BASE::DrawBitmap(), KIGFX::OPENGL_GAL::DrawBitmap(), BITMAP_BASE::DrawBitmap(), SCH_EDIT_FRAME::DrawCurrentSheetToClipboard(), PCB_EDIT_FRAME::Export_IDF3(), PCB_SELECTION_TOOL::FindItem(), SYMBOL_PREVIEW_WIDGET::fitOnDrawArea(), GENDRILL_WRITER_BASE::genDrillMapFile(), RENDER_3D_OPENGL::generate3dGrid(), RENDER_3D_OPENGL::get3dModelsFromFootprint(), DXF_IMPORT_PLUGIN::getCurrentUnitScale(), KIUI::GetDockedPaneFont(), getEnvironmentScale(), getKiCadConfiguredScale(), DIALOG_PRINT_GENERIC::getScaleValue(), KIUI::GetStatusFont(), NL_SCHEMATIC_PLUGIN_IMPL::GetViewExtents(), NL_PCBNEW_PLUGIN_IMPL::GetViewExtents(), idf_export_footprint(), idf_export_outline(), WRL1STATUS::Init(), KiScaledBitmap(), RENDER_3D_RAYTRACE::load3DModels(), KIGFX::WX_VIEW_CONTROLS::LoadSettings(), PCB_EDIT_FRAME::OnExportVRML(), KIGFX::WX_VIEW_CONTROLS::onMotion(), DIALOG_PAD_PRIMITIVE_POLY_PROPS::onPaintPolyPanel(), DIALOG_PIN_PROPERTIES::OnPaintShowPanel(), PANEL_IMAGE_EDITOR::OnRedrawPanel(), std::hash< SCALED_BITMAP_ID >::operator()(), SCH_PLOTTER::plotOneSheetSVG(), SCENEGRAPH::Prepare(), PCB_EDIT_FRAME::PrepareLayerIndicator(), PCB_EDIT_FRAME::redrawNetnames(), COMMON_TOOLS::Reset(), SCH_SEXPR_PLUGIN::saveBitmap(), KIGFX::VERTEX_MANAGER::Scale(), ZOOM_TOOL::selectRegion(), UNIT_BINDER::setPrecision(), SCH_PLOTTER::setupPlotPagePDF(), NL_SCHEMATIC_PLUGIN_IMPL::SetViewExtents(), NL_PCBNEW_PLUGIN_IMPL::SetViewExtents(), GERBVIEW_INSPECTION_TOOL::ShowDCodes(), SpreadFootprints(), spreadRectangles(), SYMBOL_EDIT_FRAME::SVGPlotSymbol(), SPICE_VALUE::ToString(), DIALOG_IMPORT_GFX::TransferDataFromWindow(), PANEL_IMAGE_EDITOR::TransferToImage(), DIALOG_PAD_PRIMITIVES_TRANSFORM::Transform(), WRL1TRANSFORM::TranslateToSG(), PANEL_TRACK_WIDTH::TWCalculateCurrent(), PANEL_TRACK_WIDTH::TWCalculateWidth(), GERBVIEW_FRAME::updateDCodeSelectBox(), DIALOG_PAGES_SETTINGS::UpdateDrawingSheetExample(), PANEL_EESCHEMA_COLOR_SETTINGS::zoomFitPreview(), PANEL_PCBNEW_COLOR_SETTINGS::zoomFitPreview(), and PCB_SELECTION_TOOL::zoomFitSelection().