KiCad PCB EDA Suite
rect_placement.cpp
Go to the documentation of this file.
1 // ----------------------------------------------------------------------------------------
2 // Name : rect_placement.cpp
3 // Description : A class that fits subrectangles into a power-of-2 rectangle
4 // (C) Copyright 2000-2002 by Javier Arevalo
5 // This code is free to use and modify for all purposes
6 // ----------------------------------------------------------------------------------------
7 
8 /*
9  * You have a bunch of rectangular pieces. You need to arrange them in a
10  * rectangular surface so that they don't overlap, keeping the total area of the
11  * rectangle as small as possible. This is fairly common when arranging characters
12  * in a bitmapped font, lightmaps for a 3D engine, and I guess other situations as
13  * well.
14  *
15  * The idea of this algorithm is that, as we add rectangles, we can pre-select
16  * "interesting" places where we can try to add the next rectangles. For optimal
17  * results, the rectangles should be added in order. I initially tried using area
18  * as a sorting criteria, but it didn't work well with very tall or very flat
19  * rectangles. I then tried using the longest dimension as a selector, and it
20  * worked much better. So much for intuition...
21  *
22  * These "interesting" places are just to the right and just below the currently
23  * added rectangle. The first rectangle, obviously, goes at the top left, the next
24  * one would go either to the right or below this one, and so on. It is a weird way
25  * to do it, but it seems to work very nicely.
26  *
27  * The way we search here is fairly brute-force, the fact being that for most off-
28  * line purposes the performance seems more than adequate. I have generated a
29  * japanese font with around 8500 characters and all the time was spent generating
30  * the bitmaps.
31  *
32  * Also, for all we care, we could grow the parent rectangle.
33  *
34  * I'd be interested in hearing of other approaches to this problem. Make sure
35  * to post them on http://www.flipcode.com
36  */
37 
38 #include "rect_placement.h"
39 
40 // --------------------------------------------------------------------------------
41 // Name :
42 // Description :
43 // --------------------------------------------------------------------------------
44 void CRectPlacement::Init( int w, int h )
45 {
46  End();
47  m_size = TRect( 0, 0, w, h );
48  m_vPositions.push_back( TPos( 0, 0 ) );
49  m_area = 0;
50 }
51 
52 
53 // --------------------------------------------------------------------------------
54 // Name :
55 // Description :
56 // --------------------------------------------------------------------------------
58 {
59  m_vPositions.clear();
60  m_vRects.clear();
61  m_size.w = 0;
62 }
63 
64 
65 // --------------------------------------------------------------------------------
66 // Name : IsFree
67 // Description : Check if the given rectangle is partially or totally used
68 // --------------------------------------------------------------------------------
69 bool CRectPlacement::IsFree( const TRect& r ) const
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 }
83 
84 
85 // --------------------------------------------------------------------------------
86 // Name : AddPosition
87 // Description : Add new anchor point
88 // --------------------------------------------------------------------------------
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 }
109 
110 
111 // --------------------------------------------------------------------------------
112 // Name : AddRect
113 // Description : Add the given rect and updates anchor points
114 // --------------------------------------------------------------------------------
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 }
124 
125 
126 // --------------------------------------------------------------------------------
127 // Name : AddAtEmptySpot
128 // Description : Add the given rectangle
129 // --------------------------------------------------------------------------------
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 }
182 
183 // --------------------------------------------------------------------------------
184 // Name : AddAtEmptySpotAutoGrow
185 // Description : Add a rectangle of the given size, growing our area if needed
186 // Area grows only until the max given.
187 // Returns the placement of the rect in the rect's x,y coords
188 // --------------------------------------------------------------------------------
189 bool CRectPlacement::AddAtEmptySpotAutoGrow( TRect* pRect, int maxW, int maxH )
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 Contains(const TPos &p) const
void Init(int w=1, int h=1)
bool AddAtEmptySpot(TRect &r)
CPosArray m_vPositions
CRectArray m_vRects
#define GROW(x)
void AddPosition(const TPos &p)
bool IsFree(const TRect &r) const
void AddRect(const TRect &r)
bool AddAtEmptySpotAutoGrow(TRect *pRect, int maxW, int maxH)