KiCad PCB EDA Suite
spread_footprints.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2013 Jean-Pierre Charras, jean-pierre.charras@ujf-grenoble.fr
5  * Copyright (C) 2013 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
6  * Copyright (C) 2013 Wayne Stambaugh <stambaughw@verizon.net>
7  *
8  * Copyright (C) 1992-2016 KiCad Developers, see AUTHORS.txt for contributors.
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
37 #include <algorithm>
38 
39 #include <fctsys.h>
40 #include <convert_to_biu.h>
41 #include <class_drawpanel.h>
42 #include <confirm.h>
43 #include <pcbnew.h>
44 #include <pcb_edit_frame.h>
45 #include <class_board.h>
46 #include <class_module.h>
47 
49 
51 {
52  int n; // Original index of this subrect, before sorting
53 
54  TSubRect() : TRect(),
55  n( 0 )
56  {
57  }
58 
59  TSubRect( int _w, int _h, int _n ) :
60  TRect( 0, 0, _w, _h ), n( _n ) { }
61 };
62 
63 typedef std::vector<TSubRect> CSubRectArray;
64 
65 // Use 0.01 mm units to calculate placement, to avoid long calculation time
66 const int scale = (int)(0.01 * IU_PER_MM);
67 
68 const int PADDING = (int)(1 * IU_PER_MM);
69 
70 // Populates a list of rectangles, from a list of modules
71 void fillRectList( CSubRectArray& vecSubRects, std::vector <MODULE*>& aModuleList )
72 {
73  vecSubRects.clear();
74 
75  for( unsigned ii = 0; ii < aModuleList.size(); ii++ )
76  {
77  EDA_RECT fpBox = aModuleList[ii]->GetFootprintRect();
78  TSubRect fpRect( ( fpBox.GetWidth() + PADDING ) / scale,
79  ( fpBox.GetHeight() + PADDING ) / scale, ii );
80  vecSubRects.push_back( fpRect );
81  }
82 }
83 
84 // Populates a list of rectangles, from a list of EDA_RECT
85 void fillRectList( CSubRectArray& vecSubRects, std::vector <EDA_RECT>& aRectList )
86 {
87  vecSubRects.clear();
88 
89  for( unsigned ii = 0; ii < aRectList.size(); ii++ )
90  {
91  EDA_RECT& rect = aRectList[ii];
92  TSubRect fpRect( rect.GetWidth()/scale, rect.GetHeight()/scale, ii );
93  vecSubRects.push_back( fpRect );
94  }
95 }
96 
97 
98 
99 // Spread a list of rectangles inside a placement area
100 void spreadRectangles( CRectPlacement& aPlacementArea,
101  CSubRectArray& vecSubRects,
102  int areaSizeX, int areaSizeY )
103 {
104  areaSizeX/= scale;
105  areaSizeY/= scale;
106 
107  // Sort the subRects based on dimensions, larger dimension goes first.
108  std::sort( vecSubRects.begin(), vecSubRects.end(), CRectPlacement::TRect::Greater );
109 
110  // gives the initial size to the area
111  aPlacementArea.Init( areaSizeX, areaSizeY );
112 
113  // Add all subrects
114  CSubRectArray::iterator it;
115  for( it = vecSubRects.begin(); it != vecSubRects.end(); )
116  {
117  CRectPlacement::TRect r( 0, 0, it->w, it->h );
118 
119  bool bPlaced = aPlacementArea.AddAtEmptySpotAutoGrow( &r, areaSizeX, areaSizeY );
120 
121  if( !bPlaced ) // No room to place the rectangle: enlarge area and retry
122  {
123  areaSizeX = ceil(areaSizeX * 1.1);
124  areaSizeY = ceil(areaSizeY * 1.1);
125  aPlacementArea.Init( areaSizeX, areaSizeY );
126  it = vecSubRects.begin();
127  continue;
128  }
129 
130  // When correctly placed in a placement area, the coords are returned in r.x and r.y
131  // Store them.
132  it->x = r.x;
133  it->y = r.y;
134 
135  it++;
136  }
137 }
138 
139 
140 void moveFootprintsInArea( CRectPlacement& aPlacementArea,
141  std::vector <MODULE*>& aModuleList,
142  EDA_RECT& aFreeArea,
143  bool aFindAreaOnly )
144 {
145  CSubRectArray vecSubRects;
146 
147  fillRectList( vecSubRects, aModuleList );
148  spreadRectangles( aPlacementArea, vecSubRects,
149  aFreeArea.GetWidth(), aFreeArea.GetHeight() );
150 
151  if( aFindAreaOnly )
152  return;
153 
154  for( unsigned it = 0; it < vecSubRects.size(); ++it )
155  {
156  wxPoint pos( vecSubRects[it].x, vecSubRects[it].y );
157  pos.x *= scale;
158  pos.y *= scale;
159 
160  MODULE * module = aModuleList[vecSubRects[it].n];
161 
162  EDA_RECT fpBBox = module->GetFootprintRect();
163  wxPoint mod_pos = pos + ( module->GetPosition() - fpBBox.GetOrigin() )
164  + aFreeArea.GetOrigin();
165 
166  module->Move( mod_pos - module->GetPosition() );
167  }
168 }
169 
170 static bool sortFootprintsbySheetPath( MODULE* ref, MODULE* compare );
171 
172 /* Function to move components in a rectangular area format 4 / 3,
173  * starting from the mouse cursor.
174  * Footprints are grouped by sheet.
175  * Components with the LOCKED status set are not moved
176  */
177 void PCB_EDIT_FRAME::SpreadFootprints( std::vector<MODULE*>* aFootprints,
178  bool aMoveFootprintsOutsideBoardOnly,
179  bool aCheckForBoardEdges,
180  wxPoint aSpreadAreaPosition,
181  bool aPrepareUndoCommand )
182 {
184  bool edgesExist = bbox.GetWidth() || bbox.GetHeight();
185  // if aFootprintsOutsideBoardOnly is true, and if board outline exists,
186  // we have to filter footprints to move:
187  bool outsideBrdFilter = aMoveFootprintsOutsideBoardOnly && edgesExist;
188 
189  // no edges exist
190  if( aMoveFootprintsOutsideBoardOnly && !edgesExist )
191  {
192  DisplayError( this,
193  _( "Could not automatically place footprints. No board outlines detected." ) );
194  return;
195  }
196 
197 
198  // Build candidate list
199  // calculate also the area needed by these footprints
200  std::vector <MODULE*> footprintList;
201 
202  for( MODULE* footprint : *aFootprints )
203  {
204  footprint->CalculateBoundingBox();
205 
206  if( outsideBrdFilter )
207  {
208  if( bbox.Contains( footprint->GetPosition() ) )
209  continue;
210  }
211 
212  if( footprint->IsLocked() )
213  continue;
214 
215  footprintList.push_back( footprint );
216  }
217 
218  if( footprintList.empty() )
219  return;
220 
221  // sort footprints by sheet path. we group them later by sheet
222  sort( footprintList.begin(), footprintList.end(), sortFootprintsbySheetPath );
223 
224  // Undo command: init undo list. If aPrepareUndoCommand == false
225  // no undo command will be initialized.
226  // Useful when a undo command is already initialized by the caller
227  PICKED_ITEMS_LIST undoList;
228 
229  if( aPrepareUndoCommand )
230  {
231  undoList.m_Status = UR_CHANGED;
232  ITEM_PICKER picker( NULL, UR_CHANGED );
233 
234  for( MODULE* footprint : footprintList )
235  {
236  // Undo: add copy of the footprint to undo list
237  picker.SetItem( footprint );
238  picker.SetLink( footprint->Clone() );
239  undoList.PushItem( picker );
240  }
241  }
242 
243  // Extract and place footprints by sheet
244  std::vector <MODULE*> footprintListBySheet;
245  std::vector <EDA_RECT> placementSheetAreas;
246  double subsurface;
247  double placementsurface = 0.0;
248 
249  // put the placement area position on mouse cursor.
250  // this position will be adjusted later
251  wxPoint placementAreaPosition = aSpreadAreaPosition;
252 
253  // We sometimes do not want to move footprints inside an existing board.
254  // Therefore, move the placement area position outside the board bounding box
255  // to the left of the board
256  if( aCheckForBoardEdges && edgesExist )
257  {
258  if( placementAreaPosition.x < bbox.GetEnd().x &&
259  placementAreaPosition.y < bbox.GetEnd().y )
260  {
261  // the placement area could overlap the board
262  // move its position to a safe location
263  placementAreaPosition.x = bbox.GetEnd().x;
264  placementAreaPosition.y = bbox.GetOrigin().y;
265  }
266  }
267 
268  // The placement uses 2 passes:
269  // the first pass creates the rectangular areas to place footprints
270  // each sheet in schematic creates one rectangular area.
271  // the second pass moves footprints inside these areas
272  MODULE* footprint;
273  for( int pass = 0; pass < 2; pass++ )
274  {
275  int subareaIdx = 0;
276  footprintListBySheet.clear();
277  subsurface = 0.0;
278 
279  for( unsigned ii = 0; ii < footprintList.size(); ii++ )
280  {
281  footprint = footprintList[ii];
282  bool islastItem = false;
283 
284  if( ii == footprintList.size() - 1 ||
285  ( footprintList[ii]->GetPath().BeforeLast( '/' ) !=
286  footprintList[ii+1]->GetPath().BeforeLast( '/' ) ) )
287  islastItem = true;
288 
289  footprintListBySheet.push_back( footprint );
290  subsurface += footprint->GetArea( PADDING );
291 
292  if( islastItem )
293  {
294  // end of the footprint sublist relative to the same sheet path
295  // calculate placement of the current sublist
296  EDA_RECT freeArea;
297  int Xsize_allowed = (int) ( sqrt( subsurface ) * 4.0 / 3.0 );
298  int Ysize_allowed = (int) ( subsurface / Xsize_allowed );
299 
300  freeArea.SetWidth( Xsize_allowed );
301  freeArea.SetHeight( Ysize_allowed );
302  CRectPlacement placementArea;
303 
304  if( pass == 1 )
305  {
306  wxPoint areapos = placementSheetAreas[subareaIdx].GetOrigin()
307  + placementAreaPosition;
308  freeArea.SetOrigin( areapos );
309  }
310 
311  bool findAreaOnly = pass == 0;
312  moveFootprintsInArea( placementArea, footprintListBySheet,
313  freeArea, findAreaOnly );
314 
315  if( pass == 0 )
316  {
317  // Populate sheet placement areas list
318  EDA_RECT sub_area;
319  sub_area.SetWidth( placementArea.GetW()*scale );
320  sub_area.SetHeight( placementArea.GetH()*scale );
321  // Add a margin around the sheet placement area:
322  sub_area.Inflate( Millimeter2iu( 1.5 ) );
323 
324  placementSheetAreas.push_back( sub_area );
325 
326  placementsurface += (double) sub_area.GetWidth()*
327  sub_area.GetHeight();
328  }
329 
330  // Prepare buffers for next sheet
331  subsurface = 0.0;
332  footprintListBySheet.clear();
333  subareaIdx++;
334  }
335  }
336 
337  // End of pass:
338  // At the end of the first pass, we have to find position of each sheet
339  // placement area
340  if( pass == 0 )
341  {
342  int Xsize_allowed = (int) ( sqrt( placementsurface ) * 4.0 / 3.0 );
343  int Ysize_allowed = (int) ( placementsurface / Xsize_allowed );
344  CRectPlacement placementArea;
345  CSubRectArray vecSubRects;
346 
347  fillRectList( vecSubRects, placementSheetAreas );
348  spreadRectangles( placementArea, vecSubRects, Xsize_allowed, Ysize_allowed );
349 
350  for( unsigned it = 0; it < vecSubRects.size(); ++it )
351  {
352  TSubRect& srect = vecSubRects[it];
353  wxPoint pos( srect.x*scale, srect.y*scale );
354  wxSize size( srect.w*scale, srect.h*scale );
355  placementSheetAreas[srect.n].SetOrigin( pos );
356  placementSheetAreas[srect.n].SetSize( size );
357  }
358  }
359  } // End pass
360 
361  // Undo: commit list
362  if( aPrepareUndoCommand )
363  SaveCopyInUndoList( undoList, UR_CHANGED );
364 
365  OnModify();
366 
367  m_canvas->Refresh();
368 }
369 
370 
371 // Sort function, used to group footprints by sheet.
372 // Footprints are sorted by their sheet path.
373 // (the full sheet path restricted to the time stamp of the sheet itself,
374 // without the time stamp of the footprint ).
375 static bool sortFootprintsbySheetPath( MODULE* ref, MODULE* compare )
376 {
377  if( ref->GetPath().Length() == compare->GetPath().Length() )
378  return ref->GetPath().BeforeLast( '/' ).Cmp( compare->GetPath().BeforeLast( '/' ) ) < 0;
379 
380  return ref->GetPath().Length() < compare->GetPath().Length();
381 }
int GetH() const
const wxPoint GetOrigin() const
Definition: eda_rect.h:112
void SpreadFootprints(std::vector< MODULE * > *aFootprints, bool aMoveFootprintsOutsideBoardOnly, bool aCheckForBoardEdges, wxPoint aSpreadAreaPosition, bool aPrepareUndoCommand=true)
Function SpreadFootprints Footprints (after loaded by reading a netlist for instance) are moved to be...
void Init(int w=1, int h=1)
This file is part of the common library.
bool Contains(const wxPoint &aPoint) const
Function Contains.
Class BOARD to handle a board.
int GetHeight() const
Definition: eda_rect.h:118
void SetOrigin(const wxPoint &pos)
Definition: eda_rect.h:124
void fillRectList(CSubRectArray &vecSubRects, std::vector< MODULE * > &aModuleList)
static bool Greater(const TRect &a, const TRect &b)
void SetLink(EDA_ITEM *aItem)
const EDA_RECT GetBoardEdgesBoundingBox() const
Function GetBoardEdgesBoundingBox Returns the board bounding box calculated using exclusively the boa...
Definition: class_board.h:804
const int PADDING
void SetHeight(int val)
Definition: eda_rect.h:133
EDA_RECT GetFootprintRect() const
Function GetFootprintRect() Returns the area of the module footprint excluding any text...
int GetW() const
static bool sortFootprintsbySheetPath(MODULE *ref, MODULE *compare)
std::vector< TSubRect > CSubRectArray
Class PICKED_ITEMS_LIST is a holder to handle information on schematic or board items.
void SetItem(EDA_ITEM *aItem)
void SetWidth(int val)
Definition: eda_rect.h:132
const wxPoint GetEnd() const
Definition: eda_rect.h:114
BOARD * GetBoard()
TSubRect(int _w, int _h, int _n)
const int scale
void Move(const wxPoint &aMoveVector) override
Function Move move this object.
Class EDA_RECT handles the component boundary box.
Definition: eda_rect.h:44
int GetWidth() const
Definition: eda_rect.h:117
bool AddAtEmptySpotAutoGrow(TRect *pRect, int maxW, int maxH)
Module description (excepted pads)
const wxString & GetPath() const
Definition: class_module.h:202
void moveFootprintsInArea(CRectPlacement &aPlacementArea, std::vector< MODULE * > &aModuleList, EDA_RECT &aFreeArea, bool aFindAreaOnly)
void DisplayError(wxWindow *parent, const wxString &text, int displaytime)
Function DisplayError displays an error or warning message box with aMessage.
Definition: confirm.cpp:245
const wxPoint GetPosition() const override
Definition: class_module.h:184
void spreadRectangles(CRectPlacement &aPlacementArea, CSubRectArray &vecSubRects, int areaSizeX, int areaSizeY)
EDA_RECT & Inflate(wxCoord dx, wxCoord dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
double GetArea(int aPadding=0) const