Horizon
box2.h
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
40template <class Vec>
41class BOX2
42{
43private:
44 Vec m_Pos; // Rectangle Origin
45 Vec m_Size; // Rectangle Size
46
47public:
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
63 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
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 bool operator==( const BOX2<Vec>& aOther ) const
501 {
502 auto t1 ( *this );
503 auto t2 ( aOther );
504 t1.Normalize();
505 t2.Normalize();
506 return ( t1.m_Pos == t2.m_Pos && t1.m_Size == t2.m_Size );
507 }
508
509 bool operator!=( const BOX2<Vec>& aOther ) const
510 {
511 auto t1 ( *this );
512 auto t2 ( aOther );
513 t1.Normalize();
514 t2.Normalize();
515 return ( t1.m_Pos != t2.m_Pos || t1.m_Size != t2.m_Size );
516 }
517};
518
519/* Default specializations */
520typedef BOX2<VECTOR2I> BOX2I;
521typedef BOX2<VECTOR2D> BOX2D;
522
523typedef OPT<BOX2I> OPT_BOX2I;
524
525// FIXME should be removed to avoid multiple typedefs for the same type
526typedef BOX2D DBOX;
527
528#endif
Class BOX2 handles a 2-D bounding box, built on top of an origin point and size vector,...
Definition: box2.h:42
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
BOX2< Vec > & Normalize()
Function Normalize ensures that the height ant width are positive.
Definition: box2.h:127
ecoord_type Distance(const BOX2< Vec > &aBox) const
Function Distance returns the minimum distance between self and box aBox.
Definition: box2.h:495
BOX2< Vec > Intersect(const BOX2< Vec > &aRect)
Function Intersect Returns the intersection of this with another rectangle.
Definition: box2.h:266
ecoord_type Diagonal() const
Function GetArea returns the length of the diagonal of the rectangle.
Definition: box2.h:435
bool Contains(coord_type x, coord_type y) const
Function Contains.
Definition: box2.h:175
BOX2< Vec > & Inflate(int aDelta)
Function Inflate inflates the rectangle horizontally and vertically by aDelta.
Definition: box2.h:372
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
bool Intersects(const BOX2< Vec > &aRect) const
Function Intersects.
Definition: box2.h:234
bool Contains(const BOX2< Vec > &aRect) const
Function Contains.
Definition: box2.h:182
void Move(const Vec &aMoveVector)
Function Move moves the rectangle by the aMoveVector.
Definition: box2.h:118
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:149
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 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
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