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-2021 Kicad Developers, see AUTHORS.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 
40 template <class Vec>
41 class BOX2
42 {
43 public:
44  typedef typename Vec::coord_type coord_type;
45  typedef typename Vec::extended_type ecoord_type;
46  typedef std::numeric_limits<coord_type> coord_limits;
47 
48  BOX2() {};
49 
50  BOX2( const Vec& aPos, const Vec& aSize = Vec(0, 0) ) :
51  m_Pos( aPos ),
52  m_Size( aSize )
53  {
54  Normalize();
55  }
56 
57  void SetMaximum()
58  {
59  m_Pos.x = m_Pos.y = coord_limits::lowest() / 2 + coord_limits::epsilon();
60  m_Size.x = m_Size.y = coord_limits::max() - coord_limits::epsilon();
61  }
62 
63  Vec Centre() const
64  {
65  return Vec( m_Pos.x + ( m_Size.x / 2 ),
66  m_Pos.y + ( m_Size.y / 2 ) );
67  }
68 
74  template <class Container>
75  void Compute( const Container& aPointList )
76  {
77  Vec vmin, vmax;
78 
79  typename Container::const_iterator i;
80 
81  if( !aPointList.size() )
82  return;
83 
84  vmin = vmax = aPointList[0];
85 
86  for( i = aPointList.begin(); i != aPointList.end(); ++i )
87  {
88  Vec p( *i );
89  vmin.x = std::min( vmin.x, p.x );
90  vmin.y = std::min( vmin.y, p.y );
91  vmax.x = std::max( vmax.x, p.x );
92  vmax.y = std::max( vmax.y, p.y );
93  }
94 
95  SetOrigin( vmin );
96  SetSize( vmax - vmin );
97  }
98 
104  void Move( const Vec& aMoveVector )
105  {
106  m_Pos += aMoveVector;
107  }
108 
113  {
114  if( m_Size.y < 0 )
115  {
116  m_Size.y = -m_Size.y;
117  m_Pos.y -= m_Size.y;
118  }
119 
120  if( m_Size.x < 0 )
121  {
122  m_Size.x = -m_Size.x;
123  m_Pos.x -= m_Size.x;
124  }
125 
126  return *this;
127  }
128 
134  bool Contains( const Vec& aPoint ) const
135  {
136  Vec rel_pos = aPoint - m_Pos;
137  Vec size = m_Size;
138 
139  if( size.x < 0 )
140  {
141  size.x = -size.x;
142  rel_pos.x += size.x;
143  }
144 
145  if( size.y < 0 )
146  {
147  size.y = -size.y;
148  rel_pos.y += size.y;
149  }
150 
151  return ( rel_pos.x >= 0 ) && ( rel_pos.y >= 0 ) && ( rel_pos.y <= size.y) &&
152  ( rel_pos.x <= size.x);
153  }
154 
160  bool Contains( coord_type x, coord_type y ) const { return Contains( Vec( x, y ) ); }
161 
167  bool Contains( const BOX2<Vec>& aRect ) const
168  {
169  return Contains( aRect.GetOrigin() ) && Contains( aRect.GetEnd() );
170  }
171 
172  const Vec& GetSize() const { return m_Size; }
173  coord_type GetX() const { return m_Pos.x; }
174  coord_type GetY() const { return m_Pos.y; }
175 
176  const Vec& GetOrigin() const { return m_Pos; }
177  const Vec& GetPosition() const { return m_Pos; }
178  const Vec GetEnd() const { return Vec( GetRight(), GetBottom() ); }
179 
180  coord_type GetWidth() const { return m_Size.x; }
181  coord_type GetHeight() const { return m_Size.y; }
182  coord_type GetRight() const { return m_Pos.x + m_Size.x; }
183  coord_type GetBottom() const { return m_Pos.y + m_Size.y; }
184 
185  // Compatibility aliases
186  coord_type GetLeft() const { return GetX(); }
187  coord_type GetTop() const { return GetY(); }
188  void MoveTopTo( coord_type aTop ) { m_Pos.y = aTop; }
189  void MoveBottomTo( coord_type aBottom ) { m_Size.y = aBottom - m_Pos.y; }
190  void MoveLeftTo( coord_type aLeft ) { m_Pos.x = aLeft; }
191  void MoveRightTo( coord_type aRight ) { m_Size.x = aRight - m_Pos.x; }
192 
193  void SetOrigin( const Vec& pos ) { m_Pos = pos; }
194  void SetOrigin( coord_type x, coord_type y ) { m_Pos.x = x; m_Pos.y = y; }
195  void SetSize( const Vec& size ) { m_Size = size; }
196  void SetSize( coord_type w, coord_type h ) { m_Size.x = w; m_Size.y = h; }
197  void Offset( coord_type dx, coord_type dy ) { m_Pos.x += dx; m_Pos.y += dy; }
198  void Offset( const Vec& offset )
199  {
200  m_Pos.x += offset.x; m_Pos.y += offset.y;
201  }
202 
203  void SetX( coord_type val ) { m_Pos.x = val; }
204  void SetY( coord_type val ) { m_Pos.y = val; }
205  void SetWidth( coord_type val ) { m_Size.x = val; }
206  void SetHeight( coord_type val ) { m_Size.y = val; }
207  void SetEnd( coord_type x, coord_type y ) { SetEnd( Vec( x, y ) ); }
208  void SetEnd( const Vec& pos )
209  {
210  m_Size.x = pos.x - m_Pos.x; m_Size.y = pos.y - m_Pos.y;
211  }
212 
217  bool Intersects( const BOX2<Vec>& aRect ) const
218  {
219  // this logic taken from wxWidgets' geometry.cpp file:
220  bool rc;
221 
222  BOX2<Vec> me( *this );
223  BOX2<Vec> rect( aRect );
224  me.Normalize(); // ensure size is >= 0
225  rect.Normalize(); // ensure size is >= 0
226 
227  // calculate the left common area coordinate:
228  int left = std::max( me.m_Pos.x, rect.m_Pos.x );
229  // calculate the right common area coordinate:
230  int right = std::min( me.m_Pos.x + me.m_Size.x, rect.m_Pos.x + rect.m_Size.x );
231  // calculate the upper common area coordinate:
232  int top = std::max( me.m_Pos.y, aRect.m_Pos.y );
233  // calculate the lower common area coordinate:
234  int bottom = std::min( me.m_Pos.y + me.m_Size.y, rect.m_Pos.y + rect.m_Size.y );
235 
236  // if a common area exists, it must have a positive (null accepted) size
237  if( left <= right && top <= bottom )
238  rc = true;
239  else
240  rc = false;
241 
242  return rc;
243  }
244 
248  BOX2<Vec> Intersect( const BOX2<Vec>& aRect )
249  {
250  BOX2<Vec> me( *this );
251  BOX2<Vec> rect( aRect );
252  me.Normalize(); // ensure size is >= 0
253  rect.Normalize(); // ensure size is >= 0
254 
255  Vec topLeft, bottomRight;
256 
257  topLeft.x = std::max( me.m_Pos.x, rect.m_Pos.x );
258  bottomRight.x = std::min( me.m_Pos.x + me.m_Size.x, rect.m_Pos.x + rect.m_Size.x );
259  topLeft.y = std::max( me.m_Pos.y, rect.m_Pos.y );
260  bottomRight.y = std::min( me.m_Pos.y + me.m_Size.y, rect.m_Pos.y + rect.m_Size.y );
261 
262  if ( topLeft.x < bottomRight.x && topLeft.y < bottomRight.y )
263  return BOX2<Vec>( topLeft, bottomRight - topLeft );
264  else
265  return BOX2<Vec>( Vec( 0, 0 ), Vec( 0, 0 ) );
266  }
267 
268  const std::string Format() const
269  {
270  std::stringstream ss;
271 
272  ss << "( box corner " << m_Pos.Format() << " w " << m_Size.x << " h " << m_Size.y << " )";
273 
274  return ss.str();
275  }
276 
282  {
283  if( m_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;
296  }
297  }
298  else // size.x < 0:
299  {
300  if( m_Size.x > -2 * dx )
301  {
302  // Don't allow deflate to eat more width than we have,
303  m_Pos.x -= m_Size.x / 2;
304  m_Size.x = 0;
305  }
306  else
307  {
308  // The inflate is valid.
309  m_Pos.x += dx;
310  m_Size.x -= 2 * dx; // m_Size.x <0: inflate when dx > 0
311  }
312  }
313 
314  if( m_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;
327  }
328  }
329  else // size.y < 0:
330  {
331  if( m_Size.y > 2 * dy )
332  {
333  // Don't allow deflate to eat more height than we have,
334  m_Pos.y -= m_Size.y / 2;
335  m_Size.y = 0;
336  }
337  else
338  {
339  // The inflate is valid.
340  m_Pos.y += dy;
341  m_Size.y -= 2 * dy; // m_Size.y <0: inflate when dy > 0
342  }
343  }
344 
345  return *this;
346  }
347 
352  BOX2<Vec>& Inflate( int aDelta )
353  {
354  Inflate( aDelta, aDelta );
355  return *this;
356  }
357 
363  BOX2<Vec>& Merge( const BOX2<Vec>& aRect )
364  {
365  Normalize(); // ensure width and height >= 0
366  BOX2<Vec> rect = aRect;
367  rect.Normalize(); // ensure width and height >= 0
368  Vec end = GetEnd();
369  Vec rect_end = rect.GetEnd();
370 
371  // Change origin and size in order to contain the given rect
372  m_Pos.x = std::min( m_Pos.x, rect.m_Pos.x );
373  m_Pos.y = std::min( m_Pos.y, rect.m_Pos.y );
374  end.x = std::max( end.x, rect_end.x );
375  end.y = std::max( end.y, rect_end.y );
376  SetEnd( end );
377  return *this;
378  }
379 
385  BOX2<Vec>& Merge( const Vec& aPoint )
386  {
387  Normalize(); // ensure width and height >= 0
388 
389  Vec end = GetEnd();
390 
391  // Change origin and size in order to contain the given rectangle.
392  m_Pos.x = std::min( m_Pos.x, aPoint.x );
393  m_Pos.y = std::min( m_Pos.y, aPoint.y );
394  end.x = std::max( end.x, aPoint.x );
395  end.y = std::max( end.y, aPoint.y );
396  SetEnd( end );
397  return *this;
398  }
399 
406  {
407  return (ecoord_type) GetWidth() * (ecoord_type) GetHeight();
408  }
409 
416  {
417  return m_Size.EuclideanNorm();
418  }
419 
420  ecoord_type SquaredDistance( const Vec& aP ) const
421  {
422  ecoord_type x2 = m_Pos.x + m_Size.x;
423  ecoord_type y2 = m_Pos.y + m_Size.y;
424  ecoord_type xdiff = std::max( aP.x < m_Pos.x ? m_Pos.x - aP.x : m_Pos.x - x2,
425  (ecoord_type) 0 );
426  ecoord_type ydiff = std::max( aP.y < m_Pos.y ? m_Pos.y - aP.y : m_Pos.y - y2,
427  (ecoord_type) 0 );
428  return xdiff * xdiff + ydiff * ydiff;
429  }
430 
431  ecoord_type Distance( const Vec& aP ) const
432  {
433  return sqrt( SquaredDistance( aP ) );
434  }
435 
442  ecoord_type SquaredDistance( const BOX2<Vec>& aBox ) const
443  {
444  ecoord_type s = 0;
445 
446  if( aBox.m_Pos.x + aBox.m_Size.x < m_Pos.x )
447  {
448  ecoord_type d = aBox.m_Pos.x + aBox.m_Size.x - m_Pos.x;
449  s += d * d;
450  }
451  else if( aBox.m_Pos.x > m_Pos.x + m_Size.x )
452  {
453  ecoord_type d = aBox.m_Pos.x - m_Size.x - m_Pos.x;
454  s += d * d;
455  }
456 
457  if( aBox.m_Pos.y + aBox.m_Size.y < m_Pos.y )
458  {
459  ecoord_type d = aBox.m_Pos.y + aBox.m_Size.y - m_Pos.y;
460  s += d * d;
461  }
462  else if( aBox.m_Pos.y > m_Pos.y + m_Size.y )
463  {
464  ecoord_type d = aBox.m_Pos.y - m_Size.y - m_Pos.y;
465  s += d * d;
466  }
467 
468  return s;
469  }
470 
477  ecoord_type Distance( const BOX2<Vec>& aBox ) const
478  {
479  return sqrt( SquaredDistance( aBox ) );
480  }
481 
482  bool operator==( const BOX2<Vec>& aOther ) const
483  {
484  auto t1 ( *this );
485  auto t2 ( aOther );
486  t1.Normalize();
487  t2.Normalize();
488  return ( t1.m_Pos == t2.m_Pos && t1.m_Size == t2.m_Size );
489  }
490 
491  bool operator!=( const BOX2<Vec>& aOther ) const
492  {
493  auto t1 ( *this );
494  auto t2 ( aOther );
495  t1.Normalize();
496  t2.Normalize();
497  return ( t1.m_Pos != t2.m_Pos || t1.m_Size != t2.m_Size );
498  }
499 
500 private:
501  Vec m_Pos; // Rectangle Origin
502  Vec m_Size; // Rectangle Size
503 };
504 
505 /* Default specializations */
508 
510 
511 // FIXME should be removed to avoid multiple typedefs for the same type
512 typedef BOX2D DBOX;
513 
514 #endif
ecoord_type Diagonal() const
Return the length of the diagonal of the rectangle.
Definition: box2.h:415
void Move(const Vec &aMoveVector)
Move the rectangle by the aMoveVector.
Definition: box2.h:104
BOX2< VECTOR2I > BOX2I
Definition: box2.h:506
void Offset(const Vec &offset)
Definition: box2.h:198
BOX2()
Definition: box2.h:48
bool operator!=(const BOX2< Vec > &aOther) const
Definition: box2.h:491
const Vec GetEnd() const
Definition: box2.h:178
coord_type GetX() const
Definition: box2.h:173
coord_type GetTop() const
Definition: box2.h:187
BOX2D DBOX
Definition: box2.h:512
void MoveBottomTo(coord_type aBottom)
Definition: box2.h:189
BOX2< Vec > & Inflate(int aDelta)
Inflate the rectangle horizontally and vertically by aDelta.
Definition: box2.h:352
BOX2< VECTOR2D > BOX2D
Definition: box2.h:507
coord_type GetRight() const
Definition: box2.h:182
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:75
ecoord_type SquaredDistance(const Vec &aP) const
Definition: box2.h:420
void SetSize(const Vec &size)
Definition: box2.h:195
coord_type GetBottom() const
Definition: box2.h:183
void SetX(coord_type val)
Definition: box2.h:203
A 2D bounding box built on top of an origin point and size vector.
Definition: box2.h:41
bool operator==(const BOX2< Vec > &aOther) const
Definition: box2.h:482
bool Intersects(const BOX2< Vec > &aRect) const
Definition: box2.h:217
bool Contains(coord_type x, coord_type y) const
Definition: box2.h:160
void MoveLeftTo(coord_type aLeft)
Definition: box2.h:190
void SetOrigin(coord_type x, coord_type y)
Definition: box2.h:194
Vec::extended_type ecoord_type
Definition: box2.h:45
coord_type GetWidth() const
Definition: box2.h:180
ecoord_type SquaredDistance(const BOX2< Vec > &aBox) const
Return the square of the minimum distance between self and box aBox.
Definition: box2.h:442
BOX2< Vec > & Normalize()
Ensure that the height ant width are positive.
Definition: box2.h:112
bool Contains(const Vec &aPoint) const
Definition: box2.h:134
void SetMaximum()
Definition: box2.h:57
void SetSize(coord_type w, coord_type h)
Definition: box2.h:196
BOX2(const Vec &aPos, const Vec &aSize=Vec(0, 0))
Definition: box2.h:50
bool Contains(const BOX2< Vec > &aRect) const
Definition: box2.h:167
ecoord_type GetArea() const
Return the area of the rectangle.
Definition: box2.h:405
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition: box2.h:363
void Offset(coord_type dx, coord_type dy)
Definition: box2.h:197
void SetEnd(coord_type x, coord_type y)
Definition: box2.h:207
const Vec & GetPosition() const
Definition: box2.h:177
coord_type GetY() const
Definition: box2.h:174
void SetHeight(coord_type val)
Definition: box2.h:206
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:281
Vec Centre() const
Definition: box2.h:63
void SetEnd(const Vec &pos)
Definition: box2.h:208
void SetY(coord_type val)
Definition: box2.h:204
Vec m_Pos
Definition: box2.h:501
BOX2< Vec > & Merge(const Vec &aPoint)
Modify the position and size of the rectangle in order to contain the given point.
Definition: box2.h:385
void SetOrigin(const Vec &pos)
Definition: box2.h:193
coord_type GetHeight() const
Definition: box2.h:181
OPT< BOX2I > OPT_BOX2I
Definition: box2.h:509
boost::optional< T > OPT
Definition: optional.h:7
const Vec & GetSize() const
Definition: box2.h:172
coord_type GetLeft() const
Definition: box2.h:186
Vec m_Size
Definition: box2.h:502
const Vec & GetOrigin() const
Definition: box2.h:176
void MoveTopTo(coord_type aTop)
Definition: box2.h:188
ecoord_type Distance(const Vec &aP) const
Definition: box2.h:431
std::numeric_limits< coord_type > coord_limits
Definition: box2.h:46
ecoord_type Distance(const BOX2< Vec > &aBox) const
Return the minimum distance between self and aBox.
Definition: box2.h:477
Vec::coord_type coord_type
Definition: box2.h:44
const std::string Format() const
Definition: box2.h:268
void SetWidth(coord_type val)
Definition: box2.h:205
BOX2< Vec > Intersect(const BOX2< Vec > &aRect)
Return the intersection of this with another rectangle.
Definition: box2.h:248
void MoveRightTo(coord_type aRight)
Definition: box2.h:191