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 <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)
 
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 51 of file spread_footprints.cpp.

◆ rect_type

using rect_type = rectpack2D::output_rect_t<spaces_type>

Definition at line 50 of file spread_footprints.cpp.

◆ rect_vector

using rect_vector = std::vector<rect_type>

Definition at line 52 of file spread_footprints.cpp.

◆ spaces_type

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

Definition at line 49 of file spread_footprints.cpp.

Function Documentation

◆ compareFootprintsbyRef()

static bool compareFootprintsbyRef ( FOOTPRINT ref,
FOOTPRINT compare 
)
static

Definition at line 58 of file spread_footprints.cpp.

59{
60 const wxString& refPrefix = UTIL::GetRefDesPrefix( ref->GetReference() );
61 const wxString& cmpPrefix = UTIL::GetRefDesPrefix( compare->GetReference() );
62
63 if( refPrefix != cmpPrefix )
64 {
65 return refPrefix < cmpPrefix;
66 }
67 else
68 {
69 const int refInt = GetTrailingInt( ref->GetReference() );
70 const int cmpInt = GetTrailingInt( compare->GetReference() );
71
72 return refInt < cmpInt;
73 }
74
75 return false;
76}
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 123 of file spread_footprints.cpp.

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

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

◆ spreadRectangles()

rectpack2D::rect_wh spreadRectangles ( rect_vector vecSubRects,
int  areaSizeX,
int  areaSizeY 
)

Definition at line 80 of file spread_footprints.cpp.

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

References r, and scale.

Referenced by SpreadFootprints().

Variable Documentation

◆ allow_flip

constexpr bool allow_flip = true
constexpr

Definition at line 47 of file spread_footprints.cpp.

◆ scale

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

Definition at line 55 of file spread_footprints.cpp.

Referenced by ACTION_TOOLBAR::AddScaledSeparator(), GRID_MENU::BuildChoiceList(), Clamp_Text_PenSize(), KIGFX::GAL::ComputeWorldScreenMatrix(), KIGFX::CAIRO_PRINT_GAL::ComputeWorldScreenMatrix(), SCH_PLOTTER::createPSFiles(), EDA_3D_CANVAS::DoRePaint(), 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(), DXF_IMPORT_PLUGIN::getCurrentUnitScale(), 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(), RENDER_3D_OPENGL::renderFootprint(), COMMON_TOOLS::Reset(), 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(), 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().