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 35 /** 36 * Class BOX2 37 * handles a 2-D bounding box, built on top of an origin point 38 * and size vector, both of templated class Vec 39 */ 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 BOX2()52 BOX2() {}; 53 BOX2(const Vec & aPos,const Vec & aSize)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 /// Constructor with a wxRect as argument BOX2(const wxRect & aRect)63 BOX2( const wxRect& aRect ) : 64 m_Pos( aRect.GetPosition() ), 65 m_Size( aRect.GetSize() ) 66 { 67 Normalize(); 68 } 69 #endif 70 SetMaximum()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 Centre()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 83 /** 84 * @brief Compute the bounding box from a given list of points. 85 * 86 * @param aPointList is the list points of the object. 87 */ 88 template <class Container> Compute(const Container & aPointList)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 113 /** 114 * Function Move 115 * moves the rectangle by the \a aMoveVector. 116 * @param aMoveVector A point that is the value to move this rectangle 117 */ Move(const Vec & aMoveVector)118 void Move( const Vec& aMoveVector ) 119 { 120 m_Pos += aMoveVector; 121 } 122 123 /** 124 * Function Normalize 125 * ensures that the height ant width are positive. 126 */ Normalize()127 BOX2<Vec>& Normalize() 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 144 /** 145 * Function Contains 146 * @param aPoint = the point to test 147 * @return true if aPoint is inside the boundary box. A point on a edge is seen as inside 148 */ Contains(const Vec & aPoint)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 169 /** 170 * Function Contains 171 * @param x = the x coordinate of the point to test 172 * @param y = the x coordinate of the point to test 173 * @return true if point is inside the boundary box. A point on a edge is seen as inside 174 */ Contains(coord_type x,coord_type y)175 bool Contains( coord_type x, coord_type y ) const { return Contains( Vec( x, y ) ); } 176 177 /** 178 * Function Contains 179 * @param aRect = the BOX2 to test 180 * @return true if aRect is Contained. A common edge is seen as contained 181 */ Contains(const BOX2<Vec> & aRect)182 bool Contains( const BOX2<Vec>& aRect ) const 183 { 184 return Contains( aRect.GetOrigin() ) && Contains( aRect.GetEnd() ); 185 } 186 GetSize()187 const Vec& GetSize() const { return m_Size; } GetX()188 coord_type GetX() const { return m_Pos.x; } GetY()189 coord_type GetY() const { return m_Pos.y; } 190 GetOrigin()191 const Vec& GetOrigin() const { return m_Pos; } GetPosition()192 const Vec& GetPosition() const { return m_Pos; } GetEnd()193 const Vec GetEnd() const { return Vec( GetRight(), GetBottom() ); } 194 GetWidth()195 coord_type GetWidth() const { return m_Size.x; } GetHeight()196 coord_type GetHeight() const { return m_Size.y; } GetRight()197 coord_type GetRight() const { return m_Pos.x + m_Size.x; } GetBottom()198 coord_type GetBottom() const { return m_Pos.y + m_Size.y; } 199 200 // Compatibility aliases GetLeft()201 coord_type GetLeft() const { return GetX(); } GetTop()202 coord_type GetTop() const { return GetY(); } MoveTopTo(coord_type aTop)203 void MoveTopTo( coord_type aTop ) { m_Pos.y = aTop; } MoveBottomTo(coord_type aBottom)204 void MoveBottomTo( coord_type aBottom ) { m_Size.y = aBottom - m_Pos.y; } MoveLeftTo(coord_type aLeft)205 void MoveLeftTo( coord_type aLeft ) { m_Pos.x = aLeft; } MoveRightTo(coord_type aRight)206 void MoveRightTo( coord_type aRight ) { m_Size.x = aRight - m_Pos.x; } 207 SetOrigin(const Vec & pos)208 void SetOrigin( const Vec& pos ) { m_Pos = pos; } SetOrigin(coord_type x,coord_type y)209 void SetOrigin( coord_type x, coord_type y ) { m_Pos.x = x; m_Pos.y = y; } SetSize(const Vec & size)210 void SetSize( const Vec& size ) { m_Size = size; } SetSize(coord_type w,coord_type h)211 void SetSize( coord_type w, coord_type h ) { m_Size.x = w; m_Size.y = h; } Offset(coord_type dx,coord_type dy)212 void Offset( coord_type dx, coord_type dy ) { m_Pos.x += dx; m_Pos.y += dy; } Offset(const Vec & offset)213 void Offset( const Vec& offset ) 214 { 215 m_Pos.x += offset.x; m_Pos.y += 216 offset.y; 217 } 218 SetX(coord_type val)219 void SetX( coord_type val ) { m_Pos.x = val; } SetY(coord_type val)220 void SetY( coord_type val ) { m_Pos.y = val; } SetWidth(coord_type val)221 void SetWidth( coord_type val ) { m_Size.x = val; } SetHeight(coord_type val)222 void SetHeight( coord_type val ) { m_Size.y = val; } SetEnd(coord_type x,coord_type y)223 void SetEnd( coord_type x, coord_type y ) { SetEnd( Vec( x, y ) ); } SetEnd(const Vec & pos)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 229 /** 230 * Function Intersects 231 * @return bool - true if the argument rectangle intersects this rectangle. 232 * (i.e. if the 2 rectangles have at least a common point) 233 */ Intersects(const BOX2<Vec> & aRect)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 262 /** 263 * Function Intersect 264 * Returns the intersection of this with another rectangle. 265 */ Intersect(const BOX2<Vec> & aRect)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 Format()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 295 /** 296 * Function Inflate 297 * inflates the rectangle horizontally by \a dx and vertically by \a dy. If \a dx 298 * and/or \a dy is negative the rectangle is deflated. 299 */ Inflate(coord_type dx,coord_type dy)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 367 /** 368 * Function Inflate 369 * inflates the rectangle horizontally and vertically by \a aDelta. If \a aDelta 370 * is negative the rectangle is deflated. 371 */ Inflate(int aDelta)372 BOX2<Vec>& Inflate( int aDelta ) 373 { 374 Inflate( aDelta, aDelta ); 375 return *this; 376 } 377 378 /** 379 * Function Merge 380 * modifies the position and size of the rectangle in order to contain \a aRect. It is 381 * mainly used to calculate bounding boxes. 382 * @param aRect The rectangle to merge with this rectangle. 383 */ Merge(const BOX2<Vec> & aRect)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 401 /** 402 * Function Merge 403 * modifies the position and size of the rectangle in order to contain the given point. 404 * @param aPoint The point to merge with the rectangle. 405 */ Merge(const Vec & aPoint)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 420 /** 421 * Function GetArea 422 * returns the area of the rectangle. 423 * @return The area of the rectangle. 424 */ GetArea()425 ecoord_type GetArea() const 426 { 427 return (ecoord_type) GetWidth() * (ecoord_type) GetHeight(); 428 } 429 430 /** 431 * Function GetArea 432 * returns the length of the diagonal of the rectangle. 433 * @return The area of the diagonal. 434 */ Diagonal()435 ecoord_type Diagonal() const 436 { 437 return m_Size.EuclideanNorm(); 438 } 439 SquaredDistance(const Vec & aP)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 Distance(const Vec & aP)449 ecoord_type Distance( const Vec& aP ) const 450 { 451 return sqrt( SquaredDistance( aP ) ); 452 } 453 454 /** 455 * Function SquaredDistance 456 * returns the square of the minimum distance between self and box aBox 457 * @param aBox: the other box 458 * @return The distance, squared 459 */ SquaredDistance(const BOX2<Vec> & aBox)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 489 /** 490 * Function Distance 491 * returns the minimum distance between self and box aBox 492 * @param aBox: the other box 493 * @return The distance 494 */ Distance(const BOX2<Vec> & aBox)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 */ 520 typedef BOX2<VECTOR2I> BOX2I; 521 typedef BOX2<VECTOR2D> BOX2D; 522 523 typedef OPT<BOX2I> OPT_BOX2I; 524 525 // FIXME should be removed to avoid multiple typedefs for the same type 526 typedef BOX2D DBOX; 527 528 #endif 529