KiCad PCB EDA Suite
box2.h
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) 2012 SoftPLC Corporation, Dick Hollenbeck <dick@softplc.com>
5  * Copyright (C) 2012 Kicad Developers, see change_log.txt for contributors.
6  * Copyright (C) 2013 CERN
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  *
9  * This program is free software; you can redistribute it and/or
10  * modify it under the terms of the GNU General Public License
11  * as published by the Free Software Foundation; either version 2
12  * of the License, or (at your option) any later version.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, you may find one here:
21  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22  * or you may search the http://www.gnu.org website for the version 2 license,
23  * or you may write to the Free Software Foundation, Inc.,
24  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25  */
26 
27 #ifndef __BOX2_H
28 #define __BOX2_H
29 
30 #include <math/vector2d.h>
31 #include <limits>
32 
33 #include <boost/optional.hpp>
34 
40 template <class Vec>
41 class BOX2
42 {
43 private:
44  Vec m_Pos; // Rectangle Origin
45  Vec m_Size; // Rectangle Size
46 
47 public:
48  typedef typename Vec::coord_type coord_type;
49  typedef typename Vec::extended_type ecoord_type;
50  typedef typename std::numeric_limits<coord_type> coord_limits;
51 
52  BOX2() {};
53 
54  BOX2( const Vec& aPos, const Vec& aSize ) :
55  m_Pos( aPos ),
56  m_Size( aSize )
57  {
58  Normalize();
59  }
60 
61  void SetMaximum()
62  {
63  m_Pos.x = m_Pos.y = coord_limits::min() / 2 + coord_limits::epsilon();
64  m_Size.x = m_Size.y = coord_limits::max() - coord_limits::epsilon();
65  }
66 
67  Vec Centre() const
68  {
69  return Vec( m_Pos.x + ( m_Size.x / 2 ),
70  m_Pos.y + ( m_Size.y / 2 ) );
71  }
72 
78  template <class Container>
79  void Compute( const Container& aPointList )
80  {
81  Vec vmin, vmax;
82 
83  typename Container::const_iterator i;
84 
85  if( !aPointList.size() )
86  return;
87 
88  vmin = vmax = aPointList[0];
89 
90  for( i = aPointList.begin(); i != aPointList.end(); ++i )
91  {
92  Vec p( *i );
93  vmin.x = std::min( vmin.x, p.x );
94  vmin.y = std::min( vmin.y, p.y );
95  vmax.x = std::max( vmax.x, p.x );
96  vmax.y = std::max( vmax.y, p.y );
97  }
98 
99  SetOrigin( vmin );
100  SetSize( vmax - vmin );
101  }
102 
108  void Move( const Vec& aMoveVector )
109  {
110  m_Pos += aMoveVector;
111  }
112 
118  {
119  if( m_Size.y < 0 )
120  {
121  m_Size.y = -m_Size.y;
122  m_Pos.y -= m_Size.y;
123  }
124 
125  if( m_Size.x < 0 )
126  {
127  m_Size.x = -m_Size.x;
128  m_Pos.x -= m_Size.x;
129  }
130 
131  return *this;
132  }
133 
139  bool Contains( const Vec& aPoint ) const
140  {
141  Vec rel_pos = aPoint - m_Pos;
142  Vec size = m_Size;
143 
144  if( size.x < 0 )
145  {
146  size.x = -size.x;
147  rel_pos.x += size.x;
148  }
149 
150  if( size.y < 0 )
151  {
152  size.y = -size.y;
153  rel_pos.y += size.y;
154  }
155 
156  return ( rel_pos.x >= 0 ) && ( rel_pos.y >= 0 ) && ( rel_pos.y <= size.y) && ( rel_pos.x <= size.x);
157  }
158 
165  bool Contains( coord_type x, coord_type y ) const { return Contains( Vec( x, y ) ); }
166 
172  bool Contains( const BOX2<Vec>& aRect ) const
173  {
174  return Contains( aRect.GetOrigin() ) && Contains( aRect.GetEnd() );
175  }
176 
177  const Vec& GetSize() const { return m_Size; }
178  coord_type GetX() const { return m_Pos.x; }
179  coord_type GetY() const { return m_Pos.y; }
180 
181  const Vec& GetOrigin() const { return m_Pos; }
182  const Vec& GetPosition() const { return m_Pos; }
183  const Vec GetEnd() const { return Vec( GetRight(), GetBottom() ); }
184 
185  coord_type GetWidth() const { return m_Size.x; }
186  coord_type GetHeight() const { return m_Size.y; }
187  coord_type GetRight() const { return m_Pos.x + m_Size.x; }
188  coord_type GetBottom() const { return m_Pos.y + m_Size.y; }
189 
190  // Compatibility aliases
191  coord_type GetLeft() const { return GetX(); }
192  coord_type GetTop() const { return GetY(); }
193  void MoveTopTo( coord_type aTop ) { m_Pos.y = aTop; }
194  void MoveBottomTo( coord_type aBottom ) { m_Size.y = aBottom - m_Pos.y; }
195  void MoveLeftTo( coord_type aLeft ) { m_Pos.x = aLeft; }
196  void MoveRightTo( coord_type aRight ) { m_Size.x = aRight - m_Pos.x; }
197 
198  void SetOrigin( const Vec& pos ) { m_Pos = pos; }
199  void SetOrigin( coord_type x, coord_type y ) { m_Pos.x = x; m_Pos.y = y; }
200  void SetSize( const Vec& size ) { m_Size = size; }
201  void SetSize( coord_type w, coord_type h ) { m_Size.x = w; m_Size.y = h; }
202  void Offset( coord_type dx, coord_type dy ) { m_Pos.x += dx; m_Pos.y += dy; }
203  void Offset( const Vec& offset )
204  {
205  m_Pos.x += offset.x; m_Pos.y +=
206  offset.y;
207  }
208 
209  void SetX( coord_type val ) { m_Pos.x = val; }
210  void SetY( coord_type val ) { m_Pos.y = val; }
211  void SetWidth( coord_type val ) { m_Size.x = val; }
212  void SetHeight( coord_type val ) { m_Size.y = val; }
213  void SetEnd( coord_type x, coord_type y ) { SetEnd( Vec( x, y ) ); }
214  void SetEnd( const Vec& pos )
215  {
216  m_Size.x = pos.x - m_Pos.x; m_Size.y = pos.y - m_Pos.y;
217  }
218 
224  bool Intersects( const BOX2<Vec>& aRect ) const
225  {
226  // this logic taken from wxWidgets' geometry.cpp file:
227  bool rc;
228 
229  BOX2<Vec> me( *this );
230  BOX2<Vec> rect( aRect );
231  me.Normalize(); // ensure size is >= 0
232  rect.Normalize(); // ensure size is >= 0
233 
234  // calculate the left common area coordinate:
235  int left = std::max( me.m_Pos.x, rect.m_Pos.x );
236  // calculate the right common area coordinate:
237  int right = std::min( me.m_Pos.x + me.m_Size.x, rect.m_Pos.x + rect.m_Size.x );
238  // calculate the upper common area coordinate:
239  int top = std::max( me.m_Pos.y, aRect.m_Pos.y );
240  // calculate the lower common area coordinate:
241  int bottom = std::min( me.m_Pos.y + me.m_Size.y, rect.m_Pos.y + rect.m_Size.y );
242 
243  // if a common area exists, it must have a positive (null accepted) size
244  if( left <= right && top <= bottom )
245  rc = true;
246  else
247  rc = false;
248 
249  return rc;
250  }
251 
252  const std::string Format() const
253  {
254  std::stringstream ss;
255 
256  ss << "( box corner " << m_Pos.Format() << " w " << m_Size.x << " h " << m_Size.y << " )";
257 
258  return ss.str();
259  }
260 
266  BOX2<Vec>& Inflate( coord_type dx, coord_type dy )
267  {
268  if( m_Size.x >= 0 )
269  {
270  if( m_Size.x < -2 * dx )
271  {
272  // Don't allow deflate to eat more width than we have,
273  m_Pos.x += m_Size.x / 2;
274  m_Size.x = 0;
275  }
276  else
277  {
278  // The inflate is valid.
279  m_Pos.x -= dx;
280  m_Size.x += 2 * dx;
281  }
282  }
283  else // size.x < 0:
284  {
285  if( m_Size.x > -2 * dx )
286  {
287  // Don't allow deflate to eat more width than we have,
288  m_Pos.x -= m_Size.x / 2;
289  m_Size.x = 0;
290  }
291  else
292  {
293  // The inflate is valid.
294  m_Pos.x += dx;
295  m_Size.x -= 2 * dx; // m_Size.x <0: inflate when dx > 0
296  }
297  }
298 
299  if( m_Size.y >= 0 )
300  {
301  if( m_Size.y < -2 * dy )
302  {
303  // Don't allow deflate to eat more height than we have,
304  m_Pos.y += m_Size.y / 2;
305  m_Size.y = 0;
306  }
307  else
308  {
309  // The inflate is valid.
310  m_Pos.y -= dy;
311  m_Size.y += 2 * dy;
312  }
313  }
314  else // size.y < 0:
315  {
316  if( m_Size.y > 2 * dy )
317  {
318  // Don't allow deflate to eat more height than we have,
319  m_Pos.y -= m_Size.y / 2;
320  m_Size.y = 0;
321  }
322  else
323  {
324  // The inflate is valid.
325  m_Pos.y += dy;
326  m_Size.y -= 2 * dy; // m_Size.y <0: inflate when dy > 0
327  }
328  }
329 
330  return *this;
331  }
332 
338  BOX2<Vec>& Inflate( int aDelta )
339  {
340  Inflate( aDelta, aDelta );
341  return *this;
342  }
343 
350  BOX2<Vec>& Merge( const BOX2<Vec>& aRect )
351  {
352  Normalize(); // ensure width and height >= 0
353  BOX2<Vec> rect = aRect;
354  rect.Normalize(); // ensure width and height >= 0
355  Vec end = GetEnd();
356  Vec rect_end = rect.GetEnd();
357 
358  // Change origin and size in order to contain the given rect
359  m_Pos.x = std::min( m_Pos.x, rect.m_Pos.x );
360  m_Pos.y = std::min( m_Pos.y, rect.m_Pos.y );
361  end.x = std::max( end.x, rect_end.x );
362  end.y = std::max( end.y, rect_end.y );
363  SetEnd( end );
364  return *this;
365  }
366 
372  BOX2<Vec>& Merge( const Vec& aPoint )
373  {
374  Normalize(); // ensure width and height >= 0
375 
376  Vec end = GetEnd();
377  // Change origin and size in order to contain the given rect
378  m_Pos.x = std::min( m_Pos.x, aPoint.x );
379  m_Pos.y = std::min( m_Pos.y, aPoint.y );
380  end.x = std::max( end.x, aPoint.x );
381  end.y = std::max( end.y, aPoint.y );
382  SetEnd( end );
383  return *this;
384  }
385 
391  ecoord_type GetArea() const
392  {
393  return (ecoord_type) GetWidth() * (ecoord_type) GetHeight();
394  }
395 
401  ecoord_type Diagonal() const
402  {
403  return m_Size.EuclideanNorm();
404  }
405 
406  ecoord_type SquaredDistance( const Vec& aP ) const
407  {
408  ecoord_type x2 = m_Pos.x + m_Size.x;
409  ecoord_type y2 = m_Pos.y + m_Size.y;
410  ecoord_type xdiff = std::max( aP.x < m_Pos.x ? m_Pos.x - aP.x : m_Pos.x - x2, (ecoord_type) 0 );
411  ecoord_type ydiff = std::max( aP.y < m_Pos.y ? m_Pos.y - aP.y : m_Pos.y - y2, (ecoord_type) 0 );
412  return xdiff * xdiff + ydiff * ydiff;
413  }
414 
415  ecoord_type Distance( const Vec& aP ) const
416  {
417  return sqrt( SquaredDistance( aP ) );
418  }
419 
426  ecoord_type SquaredDistance( const BOX2<Vec>& aBox ) const
427  {
428  ecoord_type s = 0;
429 
430  if( aBox.m_Pos.x + aBox.m_Size.x < m_Pos.x )
431  {
432  ecoord_type d = aBox.m_Pos.x + aBox.m_Size.x - m_Pos.x;
433  s += d * d;
434  }
435  else if( aBox.m_Pos.x > m_Pos.x + m_Size.x )
436  {
437  ecoord_type d = aBox.m_Pos.x - m_Size.x - m_Pos.x;
438  s += d * d;
439  }
440 
441  if( aBox.m_Pos.y + aBox.m_Size.y < m_Pos.y )
442  {
443  ecoord_type d = aBox.m_Pos.y + aBox.m_Size.y - m_Pos.y;
444  s += d * d;
445  }
446  else if( aBox.m_Pos.y > m_Pos.y + m_Size.y )
447  {
448  ecoord_type d = aBox.m_Pos.y - m_Size.y - m_Pos.y;
449  s += d * d;
450  }
451 
452  return s;
453  }
454 
461  ecoord_type Distance( const BOX2<Vec>& aBox ) const
462  {
463  return sqrt( SquaredDistance( aBox ) );
464  }
465 };
466 
467 /* Default specializations */
470 
472 
473 // FIXME should be removed to avoid multiple typedefs for the same type
474 typedef BOX2D DBOX;
475 
476 #endif
ecoord_type Distance(const Vec &aP) const
Definition: box2.h:415
const Vec & GetOrigin() const
Definition: box2.h:181
void Move(const Vec &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
Definition: box2.h:108
coord_type GetY() const
Definition: box2.h:179
BOX2< VECTOR2I > BOX2I
Definition: box2.h:468
void Offset(const Vec &offset)
Definition: box2.h:203
BOX2()
Definition: box2.h:52
ecoord_type SquaredDistance(const Vec &aP) const
Definition: box2.h:406
BOX2D DBOX
Definition: box2.h:474
const std::string Format() const
Definition: box2.h:252
const Vec GetEnd() const
Definition: box2.h:183
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:139
void MoveBottomTo(coord_type aBottom)
Definition: box2.h:194
BOX2< Vec > & Inflate(int aDelta)
Function Inflate inflates the rectangle horizontally and vertically by aDelta.
Definition: box2.h:338
BOX2< VECTOR2D > BOX2D
Definition: box2.h:469
coord_type GetRight() const
Definition: box2.h:187
ecoord_type GetArea() const
Function GetArea returns the area of the rectangle.
Definition: box2.h:391
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:79
void SetSize(const Vec &size)
Definition: box2.h:200
const Vec & GetSize() const
Definition: box2.h:177
void SetX(coord_type val)
Definition: box2.h:209
Class BOX2 handles a 2-D bounding box, built on top of an origin point and size vector, both of templated class Vec.
Definition: box2.h:41
coord_type GetTop() const
Definition: box2.h:192
coord_type GetWidth() const
Definition: box2.h:185
void MoveLeftTo(coord_type aLeft)
Definition: box2.h:195
void SetOrigin(coord_type x, coord_type y)
Definition: box2.h:199
Vec::extended_type ecoord_type
Definition: box2.h:49
bool Contains(coord_type x, coord_type y) const
Function Contains.
Definition: box2.h:165
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:117
void SetMaximum()
Definition: box2.h:61
const Vec & GetPosition() const
Definition: box2.h:182
void SetSize(coord_type w, coord_type h)
Definition: box2.h:201
coord_type GetBottom() const
Definition: box2.h:188
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:224
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h:350
Vec Centre() const
Definition: box2.h:67
void Offset(coord_type dx, coord_type dy)
Definition: box2.h:202
void SetEnd(coord_type x, coord_type y)
Definition: box2.h:213
ecoord_type SquaredDistance(const BOX2< Vec > &aBox) const
Function SquaredDistance returns the square of the minimum distance between self and box aBox...
Definition: box2.h:426
ecoord_type Distance(const BOX2< Vec > &aBox) const
Function Distance returns the minimum distance between self and box aBox.
Definition: box2.h:461
BOX2(const Vec &aPos, const Vec &aSize)
Definition: box2.h:54
coord_type GetHeight() const
Definition: box2.h:186
void SetHeight(coord_type val)
Definition: box2.h:212
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
ecoord_type Diagonal() const
Function GetArea returns the length of the diagonal of the rectangle.
Definition: box2.h:401
void SetEnd(const Vec &pos)
Definition: box2.h:214
void SetY(coord_type val)
Definition: box2.h:210
Vec m_Pos
Definition: box2.h:44
BOX2< Vec > & Merge(const Vec &aPoint)
Function Merge modifies the position and size of the rectangle in order to contain the given point...
Definition: box2.h:372
#define max(a, b)
Definition: auxiliary.h:86
void SetOrigin(const Vec &pos)
Definition: box2.h:198
coord_type GetLeft() const
Definition: box2.h:191
Vec m_Size
Definition: box2.h:45
void MoveTopTo(coord_type aTop)
Definition: box2.h:193
coord_type GetX() const
Definition: box2.h:178
bool Contains(const BOX2< Vec > &aRect) const
Function Contains.
Definition: box2.h:172
std::numeric_limits< coord_type > coord_limits
Definition: box2.h:50
boost::optional< BOX2I > OPT_BOX2I
Definition: box2.h:471
Vec::coord_type coord_type
Definition: box2.h:48
void SetWidth(coord_type val)
Definition: box2.h:211
#define min(a, b)
Definition: auxiliary.h:85
void MoveRightTo(coord_type aRight)
Definition: box2.h:196