KiCad PCB EDA Suite
CRectPlacement Class Reference

#include <rect_placement.h>

Classes

struct  TPos
 
struct  TRect
 

Public Types

typedef std::vector< TPosCPosArray
 
typedef std::vector< TRectCRectArray
 

Public Member Functions

 CRectPlacement ()
 
 ~CRectPlacement ()
 
void Init (int w=1, int h=1)
 
void End ()
 
bool IsOk () const
 
int GetW () const
 
int GetH () const
 
double GetArea () const
 
double GetTotalArea () const
 
bool AddAtEmptySpotAutoGrow (TRect *pRect, int maxW, int maxH)
 

Private Member Functions

bool IsFree (const TRect &r) const
 
void AddPosition (const TPos &p)
 
void AddRect (const TRect &r)
 
bool AddAtEmptySpot (TRect &r)
 

Private Attributes

TRect m_size
 
CRectArray m_vRects
 
CPosArray m_vPositions
 
double m_area
 

Detailed Description

Definition at line 20 of file rect_placement.h.

Member Typedef Documentation

typedef std::vector<TPos> CRectPlacement::CPosArray

Definition at line 70 of file rect_placement.h.

typedef std::vector<TRect> CRectPlacement::CRectArray

Definition at line 71 of file rect_placement.h.

Constructor & Destructor Documentation

CRectPlacement::CRectPlacement ( )
inline

Definition at line 75 of file rect_placement.h.

References Init().

75 { Init(); }
void Init(int w=1, int h=1)
CRectPlacement::~CRectPlacement ( )
inline

Definition at line 76 of file rect_placement.h.

References End().

76 { End(); }

Member Function Documentation

bool CRectPlacement::AddAtEmptySpot ( TRect r)
private

Definition at line 130 of file rect_placement.cpp.

References AddRect(), CRectPlacement::TRect::h, IsFree(), m_vPositions, CRectPlacement::TRect::w, CRectPlacement::TPos::x, and CRectPlacement::TPos::y.

Referenced by AddAtEmptySpotAutoGrow().

131 {
132  // Find a valid spot among available anchors.
133  bool bFound = false;
134  CPosArray::iterator it;
135 
136  for( it = m_vPositions.begin();
137  !bFound && it != m_vPositions.end();
138  ++it )
139  {
140  TRect Rect( it->x, it->y, r.w, r.h );
141 
142  if( IsFree( Rect ) )
143  {
144  r = Rect;
145  bFound = true;
146  break; // Don't let the loop increase the iterator.
147  }
148  }
149 
150  if( bFound )
151  {
152  int x, y;
153 
154  // Remove the used anchor point
155  m_vPositions.erase( it );
156 
157  // Sometimes, anchors end up displaced from the optimal position
158  // due to irregular sizes of the subrects.
159  // So, try to adjut it up & left as much as possible.
160  for( x = 1; x <= r.x; x++ )
161  {
162  if( !IsFree( TRect( r.x - x, r.y, r.w, r.h ) ) )
163  break;
164  }
165 
166  for( y = 1; y <= r.y; y++ )
167  {
168  if( !IsFree( TRect( r.x, r.y - y, r.w, r.h ) ) )
169  break;
170  }
171 
172  if( y > x )
173  r.y -= y - 1;
174  else
175  r.x -= x - 1;
176 
177  AddRect( r );
178  }
179 
180  return bFound;
181 }
CPosArray m_vPositions
bool IsFree(const TRect &r) const
void AddRect(const TRect &r)
bool CRectPlacement::AddAtEmptySpotAutoGrow ( TRect pRect,
int  maxW,
int  maxH 
)

Definition at line 189 of file rect_placement.cpp.

References AddAtEmptySpot(), GROW, CRectPlacement::TRect::h, m_size, and CRectPlacement::TRect::w.

Referenced by spreadRectangles().

190 {
191  double growing_factor = 1.2; // Must be > 1.0, and event > 1.1 for fast optimization
192 
193  #define GROW(x) ((x * growing_factor) + 1)
194 
195  if( pRect->w <= 0 )
196  return true;
197 
198  int orgW = m_size.w;
199  int orgH = m_size.h;
200 
201  // Try to add it in the existing space
202  while( !AddAtEmptySpot( *pRect ) )
203  {
204  int pw = m_size.w;
205  int ph = m_size.h;
206 
207  // Sanity check - if area is complete.
208  if( pw >= maxW && ph >= maxH )
209  {
210  m_size.w = orgW;
211  m_size.h = orgH;
212  return false;
213  }
214 
215  // Try growing the smallest dim
216  if( pw < maxW && ( pw < ph || ( (pw == ph) && (pRect->w >= pRect->h) ) ) )
217  m_size.w = GROW( pw );
218  else
219  m_size.h = GROW( ph );
220 
221  if( AddAtEmptySpot( *pRect ) )
222  break;
223 
224  // Try growing the other dim instead
225  if( pw != m_size.w )
226  {
227  m_size.w = pw;
228 
229  if( ph < maxW )
230  m_size.h = GROW( ph );
231  }
232  else
233  {
234  m_size.h = ph;
235 
236  if( pw < maxW )
237  m_size.w = GROW( pw );
238  }
239 
240  if( pw != m_size.w || ph != m_size.h )
241  if( AddAtEmptySpot( *pRect ) )
242  break;
243 
244 
245 
246  // Grow both if possible, and reloop.
247  m_size.w = pw;
248  m_size.h = ph;
249 
250  if( pw < maxW )
251  m_size.w = GROW( pw );
252 
253  if( ph < maxH )
254  m_size.h = GROW( ph );
255  }
256 
257  return true;
258 }
bool AddAtEmptySpot(TRect &r)
#define GROW(x)
void CRectPlacement::AddPosition ( const TPos p)
private

Definition at line 89 of file rect_placement.cpp.

References m_vPositions, CRectPlacement::TPos::x, and CRectPlacement::TPos::y.

Referenced by AddRect().

90 {
91  // Try to insert anchor as close as possible to the top left corner
92  // So it will be tried first
93  bool bFound = false;
94  CPosArray::iterator it;
95 
96  for( it = m_vPositions.begin();
97  !bFound && it != m_vPositions.end();
98  ++it )
99  {
100  if( p.x + p.y < it->x + it->y )
101  bFound = true;
102  }
103 
104  if( bFound )
105  m_vPositions.insert( it, p );
106  else
107  m_vPositions.push_back( p );
108 }
CPosArray m_vPositions
void CRectPlacement::AddRect ( const TRect r)
private

Definition at line 115 of file rect_placement.cpp.

References AddPosition(), CRectPlacement::TRect::h, m_area, m_vRects, CRectPlacement::TRect::w, CRectPlacement::TPos::x, and CRectPlacement::TPos::y.

Referenced by AddAtEmptySpot().

116 {
117  m_vRects.push_back( r );
118  m_area += r.w * r.h;
119 
120  // Add two new anchor points
121  AddPosition( TPos( r.x, r.y + r.h ) );
122  AddPosition( TPos( r.x + r.w, r.y ) );
123 }
CRectArray m_vRects
void AddPosition(const TPos &p)
void CRectPlacement::End ( )

Definition at line 57 of file rect_placement.cpp.

References m_size, m_vPositions, m_vRects, and CRectPlacement::TRect::w.

Referenced by Init(), and ~CRectPlacement().

58 {
59  m_vPositions.clear();
60  m_vRects.clear();
61  m_size.w = 0;
62 }
CPosArray m_vPositions
CRectArray m_vRects
double CRectPlacement::GetArea ( ) const
inline

Definition at line 85 of file rect_placement.h.

References m_area.

85 { return m_area; }
int CRectPlacement::GetH ( ) const
inline

Definition at line 84 of file rect_placement.h.

References CRectPlacement::TRect::h, and m_size.

Referenced by PCB_EDIT_FRAME::SpreadFootprints().

84 { return m_size.h; }
double CRectPlacement::GetTotalArea ( ) const
inline

Definition at line 86 of file rect_placement.h.

References CRectPlacement::TRect::h, m_size, and CRectPlacement::TRect::w.

int CRectPlacement::GetW ( ) const
inline

Definition at line 83 of file rect_placement.h.

References m_size, and CRectPlacement::TRect::w.

Referenced by PCB_EDIT_FRAME::SpreadFootprints().

83 { return m_size.w; }
void CRectPlacement::Init ( int  w = 1,
int  h = 1 
)

Definition at line 44 of file rect_placement.cpp.

References End(), m_area, m_size, and m_vPositions.

Referenced by CRectPlacement(), and spreadRectangles().

45 {
46  End();
47  m_size = TRect( 0, 0, w, h );
48  m_vPositions.push_back( TPos( 0, 0 ) );
49  m_area = 0;
50 }
CPosArray m_vPositions
bool CRectPlacement::IsFree ( const TRect r) const
private

Definition at line 69 of file rect_placement.cpp.

References CRectPlacement::TRect::Contains(), m_size, and m_vRects.

Referenced by AddAtEmptySpot().

70 {
71  if( !m_size.Contains( r ) )
72  return false;
73 
74  for( CRectArray::const_iterator it = m_vRects.begin();
75  it != m_vRects.end(); ++it )
76  {
77  if( it->Intersects( r ) )
78  return false;
79  }
80 
81  return true;
82 }
bool Contains(const TPos &p) const
CRectArray m_vRects
bool CRectPlacement::IsOk ( ) const
inline

Definition at line 81 of file rect_placement.h.

References m_size, and CRectPlacement::TRect::w.

81 { return m_size.w > 0; }

Member Data Documentation

double CRectPlacement::m_area
private

Definition at line 94 of file rect_placement.h.

Referenced by AddRect(), GetArea(), and Init().

TRect CRectPlacement::m_size
private

Definition at line 91 of file rect_placement.h.

Referenced by AddAtEmptySpotAutoGrow(), End(), GetH(), GetTotalArea(), GetW(), Init(), IsFree(), and IsOk().

CPosArray CRectPlacement::m_vPositions
private

Definition at line 93 of file rect_placement.h.

Referenced by AddAtEmptySpot(), AddPosition(), End(), and Init().

CRectArray CRectPlacement::m_vRects
private

Definition at line 92 of file rect_placement.h.

Referenced by AddRect(), End(), and IsFree().


The documentation for this class was generated from the following files: