Horizon
Loading...
Searching...
No Matches
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-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 <optional>
36
40template <class Vec>
41class BOX2
42{
43public:
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
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
281 BOX2<Vec>& Inflate( coord_type dx, coord_type dy )
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
405 ecoord_type GetArea() const
406 {
407 return (ecoord_type) GetWidth() * (ecoord_type) GetHeight();
408 }
409
415 ecoord_type Diagonal() const
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
500private:
501 Vec m_Pos; // Rectangle Origin
502 Vec m_Size; // Rectangle Size
503};
504
505/* Default specializations */
506typedef BOX2<VECTOR2I> BOX2I;
507typedef BOX2<VECTOR2D> BOX2D;
508
509typedef std::optional<BOX2I> OPT_BOX2I;
510
511// FIXME should be removed to avoid multiple typedefs for the same type
512typedef BOX2D DBOX;
513
514#endif
A 2D bounding box built on top of an origin point and size vector.
Definition box2.h:42
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
ecoord_type Distance(const BOX2< Vec > &aBox) const
Return the minimum distance between self and aBox.
Definition box2.h:477
BOX2< Vec > Intersect(const BOX2< Vec > &aRect)
Return the intersection of this with another rectangle.
Definition box2.h:248
ecoord_type Diagonal() const
Return the length of the diagonal of the rectangle.
Definition box2.h:415
bool Contains(coord_type x, coord_type y) const
Definition box2.h:160
BOX2< Vec > & Inflate(int aDelta)
Inflate the rectangle horizontally and vertically by aDelta.
Definition box2.h:352
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
bool Intersects(const BOX2< Vec > &aRect) const
Definition box2.h:217
bool Contains(const BOX2< Vec > &aRect) const
Definition box2.h:167
void Move(const Vec &aMoveVector)
Move the rectangle by the aMoveVector.
Definition box2.h:104
bool Contains(const Vec &aPoint) const
Definition box2.h:134
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition box2.h:281
ecoord_type GetArea() const
Return the area of the rectangle.
Definition box2.h:405
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition box2.h:75
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition box2.h:363
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition meta.hpp:1696