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