KiCad PCB EDA Suite
spread_footprints.h File Reference
#include <vector>
#include <footprint.h>
#include <base_units.h>
#include <math/vector2d.h>
#include <board.h>

Go to the source code of this file.

Functions

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. More...
 

Function Documentation

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

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