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 <core/optional.h>
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 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 #ifdef WX_COMPATIBILITY
62  BOX2( const wxRect& aRect ) :
64  m_Pos( aRect.GetPosition() ),
65  m_Size( aRect.GetSize() )
66  {
67  Normalize();
68  }
69 #endif
70 
71  void SetMaximum()
72  {
73  m_Pos.x = m_Pos.y = coord_limits::lowest() / 2 + coord_limits::epsilon();
74  m_Size.x = m_Size.y = coord_limits::max() - coord_limits::epsilon();
75  }
76 
77  Vec Centre() const
78  {
79  return Vec( m_Pos.x + ( m_Size.x / 2 ),
80  m_Pos.y + ( m_Size.y / 2 ) );
81  }
82 
88  template <class Container>
89  void Compute( const Container& aPointList )
90  {
91  Vec vmin, vmax;
92 
93  typename Container::const_iterator i;
94 
95  if( !aPointList.size() )
96  return;
97 
98  vmin = vmax = aPointList[0];
99 
100  for( i = aPointList.begin(); i != aPointList.end(); ++i )
101  {
102  Vec p( *i );
103  vmin.x = std::min( vmin.x, p.x );
104  vmin.y = std::min( vmin.y, p.y );
105  vmax.x = std::max( vmax.x, p.x );
106  vmax.y = std::max( vmax.y, p.y );
107  }
108 
109  SetOrigin( vmin );
110  SetSize( vmax - vmin );
111  }
112 
118  void Move( const Vec& aMoveVector )
119  {
120  m_Pos += aMoveVector;
121  }
122 
128  {
129  if( m_Size.y < 0 )
130  {
131  m_Size.y = -m_Size.y;
132  m_Pos.y -= m_Size.y;
133  }
134 
135  if( m_Size.x < 0 )
136  {
137  m_Size.x = -m_Size.x;
138  m_Pos.x -= m_Size.x;
139  }
140 
141  return *this;
142  }
143 
149  bool Contains( const Vec& aPoint ) const
150  {
151  Vec rel_pos = aPoint - m_Pos;
152  Vec size = m_Size;
153 
154  if( size.x < 0 )
155  {
156  size.x = -size.x;
157  rel_pos.x += size.x;
158  }
159 
160  if( size.y < 0 )
161  {
162  size.y = -size.y;
163  rel_pos.y += size.y;
164  }
165 
166  return ( rel_pos.x >= 0 ) && ( rel_pos.y >= 0 ) && ( rel_pos.y <= size.y) && ( rel_pos.x <= size.x);
167  }
168 
175  bool Contains( coord_type x, coord_type y ) const { return Contains( Vec( x, y ) ); }
176 
182  bool Contains( const BOX2<Vec>& aRect ) const
183  {
184  return Contains( aRect.GetOrigin() ) && Contains( aRect.GetEnd() );
185  }
186 
187  const Vec& GetSize() const { return m_Size; }
188  coord_type GetX() const { return m_Pos.x; }
189  coord_type GetY() const { return m_Pos.y; }
190 
191  const Vec& GetOrigin() const { return m_Pos; }
192  const Vec& GetPosition() const { return m_Pos; }
193  const Vec GetEnd() const { return Vec( GetRight(), GetBottom() ); }
194 
195  coord_type GetWidth() const { return m_Size.x; }
196  coord_type GetHeight() const { return m_Size.y; }
197  coord_type GetRight() const { return m_Pos.x + m_Size.x; }
198  coord_type GetBottom() const { return m_Pos.y + m_Size.y; }
199 
200  // Compatibility aliases
201  coord_type GetLeft() const { return GetX(); }
202  coord_type GetTop() const { return GetY(); }
203  void MoveTopTo( coord_type aTop ) { m_Pos.y = aTop; }
204  void MoveBottomTo( coord_type aBottom ) { m_Size.y = aBottom - m_Pos.y; }
205  void MoveLeftTo( coord_type aLeft ) { m_Pos.x = aLeft; }
206  void MoveRightTo( coord_type aRight ) { m_Size.x = aRight - m_Pos.x; }
207 
208  void SetOrigin( const Vec& pos ) { m_Pos = pos; }
209  void SetOrigin( coord_type x, coord_type y ) { m_Pos.x = x; m_Pos.y = y; }
210  void SetSize( const Vec& size ) { m_Size = size; }
211  void SetSize( coord_type w, coord_type h ) { m_Size.x = w; m_Size.y = h; }
212  void Offset( coord_type dx, coord_type dy ) { m_Pos.x += dx; m_Pos.y += dy; }
213  void Offset( const Vec& offset )
214  {
215  m_Pos.x += offset.x; m_Pos.y +=
216  offset.y;
217  }
218 
219  void SetX( coord_type val ) { m_Pos.x = val; }
220  void SetY( coord_type val ) { m_Pos.y = val; }
221  void SetWidth( coord_type val ) { m_Size.x = val; }
222  void SetHeight( coord_type val ) { m_Size.y = val; }
223  void SetEnd( coord_type x, coord_type y ) { SetEnd( Vec( x, y ) ); }
224  void SetEnd( const Vec& pos )
225  {
226  m_Size.x = pos.x - m_Pos.x; m_Size.y = pos.y - m_Pos.y;
227  }
228 
234  bool Intersects( const BOX2<Vec>& aRect ) const
235  {
236  // this logic taken from wxWidgets' geometry.cpp file:
237  bool rc;
238 
239  BOX2<Vec> me( *this );
240  BOX2<Vec> rect( aRect );
241  me.Normalize(); // ensure size is >= 0
242  rect.Normalize(); // ensure size is >= 0
243 
244  // calculate the left common area coordinate:
245  int left = std::max( me.m_Pos.x, rect.m_Pos.x );
246  // calculate the right common area coordinate:
247  int right = std::min( me.m_Pos.x + me.m_Size.x, rect.m_Pos.x + rect.m_Size.x );
248  // calculate the upper common area coordinate:
249  int top = std::max( me.m_Pos.y, aRect.m_Pos.y );
250  // calculate the lower common area coordinate:
251  int bottom = std::min( me.m_Pos.y + me.m_Size.y, rect.m_Pos.y + rect.m_Size.y );
252 
253  // if a common area exists, it must have a positive (null accepted) size
254  if( left <= right && top <= bottom )
255  rc = true;
256  else
257  rc = false;
258 
259  return rc;
260  }
261 
266  BOX2<Vec> Intersect( const BOX2<Vec>& aRect )
267  {
268  BOX2<Vec> me( *this );
269  BOX2<Vec> rect( aRect );
270  me.Normalize(); // ensure size is >= 0
271  rect.Normalize(); // ensure size is >= 0
272 
273  Vec topLeft, bottomRight;
274 
275  topLeft.x = std::max( me.m_Pos.x, rect.m_Pos.x );
276  bottomRight.x = std::min( me.m_Pos.x + me.m_Size.x, rect.m_Pos.x + rect.m_Size.x );
277  topLeft.y = std::max( me.m_Pos.y, rect.m_Pos.y );
278  bottomRight.y = std::min( me.m_Pos.y + me.m_Size.y, rect.m_Pos.y + rect.m_Size.y );
279 
280  if ( topLeft.x < bottomRight.x && topLeft.y < bottomRight.y )
281  return BOX2<Vec>( topLeft, bottomRight - topLeft );
282  else
283  return BOX2<Vec>( Vec( 0, 0 ), Vec( 0, 0 ) );
284  }
285 
286  const std::string Format() const
287  {
288  std::stringstream ss;
289 
290  ss << "( box corner " << m_Pos.Format() << " w " << m_Size.x << " h " << m_Size.y << " )";
291 
292  return ss.str();
293  }
294 
300  BOX2<Vec>& Inflate( coord_type dx, coord_type dy )
301  {
302  if( m_Size.x >= 0 )
303  {
304  if( m_Size.x < -2 * dx )
305  {
306  // Don't allow deflate to eat more width than we have,
307  m_Pos.x += m_Size.x / 2;
308  m_Size.x = 0;
309  }
310  else
311  {
312  // The inflate is valid.
313  m_Pos.x -= dx;
314  m_Size.x += 2 * dx;
315  }
316  }
317  else // size.x < 0:
318  {
319  if( m_Size.x > -2 * dx )
320  {
321  // Don't allow deflate to eat more width than we have,
322  m_Pos.x -= m_Size.x / 2;
323  m_Size.x = 0;
324  }
325  else
326  {
327  // The inflate is valid.
328  m_Pos.x += dx;
329  m_Size.x -= 2 * dx; // m_Size.x <0: inflate when dx > 0
330  }
331  }
332 
333  if( m_Size.y >= 0 )
334  {
335  if( m_Size.y < -2 * dy )
336  {
337  // Don't allow deflate to eat more height than we have,
338  m_Pos.y += m_Size.y / 2;
339  m_Size.y = 0;
340  }
341  else
342  {
343  // The inflate is valid.
344  m_Pos.y -= dy;
345  m_Size.y += 2 * dy;
346  }
347  }
348  else // size.y < 0:
349  {
350  if( m_Size.y > 2 * dy )
351  {
352  // Don't allow deflate to eat more height than we have,
353  m_Pos.y -= m_Size.y / 2;
354  m_Size.y = 0;
355  }
356  else
357  {
358  // The inflate is valid.
359  m_Pos.y += dy;
360  m_Size.y -= 2 * dy; // m_Size.y <0: inflate when dy > 0
361  }
362  }
363 
364  return *this;
365  }
366 
372  BOX2<Vec>& Inflate( int aDelta )
373  {
374  Inflate( aDelta, aDelta );
375  return *this;
376  }
377 
384  BOX2<Vec>& Merge( const BOX2<Vec>& aRect )
385  {
386  Normalize(); // ensure width and height >= 0
387  BOX2<Vec> rect = aRect;
388  rect.Normalize(); // ensure width and height >= 0
389  Vec end = GetEnd();
390  Vec rect_end = rect.GetEnd();
391 
392  // Change origin and size in order to contain the given rect
393  m_Pos.x = std::min( m_Pos.x, rect.m_Pos.x );
394  m_Pos.y = std::min( m_Pos.y, rect.m_Pos.y );
395  end.x = std::max( end.x, rect_end.x );
396  end.y = std::max( end.y, rect_end.y );
397  SetEnd( end );
398  return *this;
399  }
400 
406  BOX2<Vec>& Merge( const Vec& aPoint )
407  {
408  Normalize(); // ensure width and height >= 0
409 
410  Vec end = GetEnd();
411  // Change origin and size in order to contain the given rect
412  m_Pos.x = std::min( m_Pos.x, aPoint.x );
413  m_Pos.y = std::min( m_Pos.y, aPoint.y );
414  end.x = std::max( end.x, aPoint.x );
415  end.y = std::max( end.y, aPoint.y );
416  SetEnd( end );
417  return *this;
418  }
419 
425  ecoord_type GetArea() const
426  {
427  return (ecoord_type) GetWidth() * (ecoord_type) GetHeight();
428  }
429 
435  ecoord_type Diagonal() const
436  {
437  return m_Size.EuclideanNorm();
438  }
439 
440  ecoord_type SquaredDistance( const Vec& aP ) const
441  {
442  ecoord_type x2 = m_Pos.x + m_Size.x;
443  ecoord_type y2 = m_Pos.y + m_Size.y;
444  ecoord_type xdiff = std::max( aP.x < m_Pos.x ? m_Pos.x - aP.x : m_Pos.x - x2, (ecoord_type) 0 );
445  ecoord_type ydiff = std::max( aP.y < m_Pos.y ? m_Pos.y - aP.y : m_Pos.y - y2, (ecoord_type) 0 );
446  return xdiff * xdiff + ydiff * ydiff;
447  }
448 
449  ecoord_type Distance( const Vec& aP ) const
450  {
451  return sqrt( SquaredDistance( aP ) );
452  }
453 
460  ecoord_type SquaredDistance( const BOX2<Vec>& aBox ) const
461  {
462  ecoord_type s = 0;
463 
464  if( aBox.m_Pos.x + aBox.m_Size.x < m_Pos.x )
465  {
466  ecoord_type d = aBox.m_Pos.x + aBox.m_Size.x - m_Pos.x;
467  s += d * d;
468  }
469  else if( aBox.m_Pos.x > m_Pos.x + m_Size.x )
470  {
471  ecoord_type d = aBox.m_Pos.x - m_Size.x - m_Pos.x;
472  s += d * d;
473  }
474 
475  if( aBox.m_Pos.y + aBox.m_Size.y < m_Pos.y )
476  {
477  ecoord_type d = aBox.m_Pos.y + aBox.m_Size.y - m_Pos.y;
478  s += d * d;
479  }
480  else if( aBox.m_Pos.y > m_Pos.y + m_Size.y )
481  {
482  ecoord_type d = aBox.m_Pos.y - m_Size.y - m_Pos.y;
483  s += d * d;
484  }
485 
486  return s;
487  }
488 
495  ecoord_type Distance( const BOX2<Vec>& aBox ) const
496  {
497  return sqrt( SquaredDistance( aBox ) );
498  }
499 };
500 
501 /* Default specializations */
504 
506 
507 // FIXME should be removed to avoid multiple typedefs for the same type
508 typedef BOX2D DBOX;
509 
510 #endif
ecoord_type Distance(const Vec &aP) const
Definition: box2.h:449
const Vec & GetOrigin() const
Definition: box2.h:191
void Move(const Vec &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
Definition: box2.h:118
coord_type GetY() const
Definition: box2.h:189
BOX2< VECTOR2I > BOX2I
Definition: box2.h:502
void Offset(const Vec &offset)
Definition: box2.h:213
BOX2()
Definition: box2.h:52
ecoord_type SquaredDistance(const Vec &aP) const
Definition: box2.h:440
BOX2D DBOX
Definition: box2.h:508
const std::string Format() const
Definition: box2.h:286
const Vec GetEnd() const
Definition: box2.h:193
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:149
void MoveBottomTo(coord_type aBottom)
Definition: box2.h:204
BOX2< Vec > & Inflate(int aDelta)
Function Inflate inflates the rectangle horizontally and vertically by aDelta.
Definition: box2.h:372
BOX2< VECTOR2D > BOX2D
Definition: box2.h:503
coord_type GetRight() const
Definition: box2.h:197
ecoord_type GetArea() const
Function GetArea returns the area of the rectangle.
Definition: box2.h:425
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:89
void SetSize(const Vec &size)
Definition: box2.h:210
const Vec & GetSize() const
Definition: box2.h:187
void SetX(coord_type val)
Definition: box2.h:219
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:202
coord_type GetWidth() const
Definition: box2.h:195
void MoveLeftTo(coord_type aLeft)
Definition: box2.h:205
void SetOrigin(coord_type x, coord_type y)
Definition: box2.h:209
Vec::extended_type ecoord_type
Definition: box2.h:49
bool Contains(coord_type x, coord_type y) const
Function Contains.
Definition: box2.h:175
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:127
void SetMaximum()
Definition: box2.h:71
const Vec & GetPosition() const
Definition: box2.h:192
void SetSize(coord_type w, coord_type h)
Definition: box2.h:211
coord_type GetBottom() const
Definition: box2.h:198
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:234
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:384
Vec Centre() const
Definition: box2.h:77
void Offset(coord_type dx, coord_type dy)
Definition: box2.h:212
void SetEnd(coord_type x, coord_type y)
Definition: box2.h:223
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:460
ecoord_type Distance(const BOX2< Vec > &aBox) const
Function Distance returns the minimum distance between self and box aBox.
Definition: box2.h:495
BOX2(const Vec &aPos, const Vec &aSize)
Definition: box2.h:54
coord_type GetHeight() const
Definition: box2.h:196
void SetHeight(coord_type val)
Definition: box2.h:222
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:300
ecoord_type Diagonal() const
Function GetArea returns the length of the diagonal of the rectangle.
Definition: box2.h:435
void SetEnd(const Vec &pos)
Definition: box2.h:224
void SetY(coord_type val)
Definition: box2.h:220
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:406
#define max(a, b)
Definition: auxiliary.h:86
size_t i
Definition: json11.cpp:597
void SetOrigin(const Vec &pos)
Definition: box2.h:208
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:505
boost::optional< T > OPT
Definition: optional.h:7
coord_type GetLeft() const
Definition: box2.h:201
Vec m_Size
Definition: box2.h:45
void MoveTopTo(coord_type aTop)
Definition: box2.h:203
coord_type GetX() const
Definition: box2.h:188
bool Contains(const BOX2< Vec > &aRect) const
Function Contains.
Definition: box2.h:182
std::numeric_limits< coord_type > coord_limits
Definition: box2.h:50
Vec::coord_type coord_type
Definition: box2.h:48
void SetWidth(coord_type val)
Definition: box2.h:221
#define min(a, b)
Definition: auxiliary.h:85
BOX2< Vec > Intersect(const BOX2< Vec > &aRect)
Function Intersect Returns the intersection of this with another rectangle.
Definition: box2.h:266
void MoveRightTo(coord_type aRight)
Definition: box2.h:206