KiCad PCB EDA Suite
Loading...
Searching...
No Matches
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 <[email protected]>
5 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
6 * Copyright (C) 2013 CERN
7 * @author Tomasz Wlostowski <[email protected]>
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, see <https://www.gnu.org/licenses/>.
21 */
22
23#ifndef __BOX2_H
24#define __BOX2_H
25
26#include <algorithm>
27#include <cmath>
28#include <limits>
29#include <optional>
30
31#include <math/vector2d.h>
32#include <geometry/eda_angle.h>
33#include <core/kicad_algo.h>
34#include <trigo.h>
35
39template <class Vec>
40class BOX2
41{
42public:
43 typedef typename Vec::coord_type coord_type;
44 typedef typename Vec::extended_type size_type;
45 typedef typename Vec::extended_type ecoord_type;
47 typedef std::numeric_limits<coord_type> coord_limits;
48
49 constexpr BOX2() :
50 m_Pos( 0, 0 ),
51 m_Size( 0, 0 ),
52 m_init( false )
53 {};
54
55 constexpr BOX2( const Vec& aPos, const SizeVec& aSize = SizeVec(0, 0) ) :
56 m_Pos( aPos ),
57 m_Size( aSize ),
58 m_init( true )
59 {
60 // Range check
63
64 Normalize();
65 }
66
67 static constexpr BOX2<Vec> ByCorners( const Vec& aCorner1, const Vec& aCorner2 )
68 {
69 return BOX2( aCorner1, aCorner2 - aCorner1 );
70 }
71
72 static constexpr BOX2<Vec> ByCenter( const Vec& aCenter, const SizeVec& aSize )
73 {
74 return BOX2( aCenter - aSize / 2, aSize );
75 }
76
77 constexpr void SetMaximum()
78 {
79 if constexpr( std::is_floating_point<coord_type>() )
80 {
81 m_Pos.x = m_Pos.y = coord_limits::lowest() / 2.0;
82 m_Size.x = m_Size.y = coord_limits::max();
83 }
84 else if( std::is_same_v<size_type, coord_type> )
85 {
86 // BOX2L uses 64-bit ints for both coords and sizes
87 m_Pos.x = m_Pos.y = -( ( coord_limits::max() / 2 ) - coord_limits::epsilon() );
88 m_Size.x = m_Size.y = coord_limits::max() - coord_limits::epsilon();
89 }
90 else
91 {
92 // We want to be able to invert the box, so don't use lowest()
93 m_Pos.x = m_Pos.y = -coord_limits::max();
94 m_Size.x = m_Size.y = size_type( coord_limits::max() ) + coord_limits::max();
95 }
96
97 m_init = true;
98 }
99
100 constexpr Vec Centre() const
101 {
104 }
105
111 template <class Container>
112 void Compute( const Container& aPointList )
113 {
114 Vec vmin, vmax;
115
116 typename Container::const_iterator i;
117
118 if( !aPointList.size() )
119 return;
120
121 vmin = vmax = aPointList[0];
122
123 for( i = aPointList.begin(); i != aPointList.end(); ++i )
124 {
125 Vec p( *i );
126 vmin.x = std::min( vmin.x, p.x );
127 vmin.y = std::min( vmin.y, p.y );
128 vmax.x = std::max( vmax.x, p.x );
129 vmax.y = std::max( vmax.y, p.y );
130 }
131
132 SetOrigin( vmin );
133 SetSize( vmax - vmin );
134 }
135
141 constexpr void Move( const Vec& aMoveVector )
142 {
143 m_Pos += aMoveVector;
144 }
145
149 constexpr BOX2<Vec>& Normalize()
150 {
151 if( m_Size.y < 0 )
152 {
153 m_Size.y = -m_Size.y;
155 }
156
157 if( m_Size.x < 0 )
158 {
159 m_Size.x = -m_Size.x;
161 }
162
163 return *this;
164 }
165
171 constexpr bool Contains( const Vec& aPoint ) const
172 {
173 SizeVec rel_pos = SizeVec( aPoint ) - m_Pos;
174 SizeVec size = m_Size;
175
176 if( size.x < 0 )
177 {
178 size.x = -size.x;
179 rel_pos.x += size.x;
180 }
181
182 if( size.y < 0 )
183 {
184 size.y = -size.y;
185 rel_pos.y += size.y;
186 }
187
188 return ( rel_pos.x >= 0 ) && ( rel_pos.y >= 0 ) && ( rel_pos.y <= size.y) &&
189 ( rel_pos.x <= size.x);
190 }
191
197 constexpr bool Contains( coord_type x, coord_type y ) const { return Contains( Vec( x, y ) ); }
198
204 constexpr bool Contains( const BOX2<Vec>& aRect ) const
205 {
206 return Contains( aRect.GetOrigin() ) && Contains( aRect.GetEnd() );
207 }
208
209 constexpr const SizeVec& GetSize() const { return m_Size; }
210 constexpr coord_type GetX() const { return m_Pos.x; }
211 constexpr coord_type GetY() const { return m_Pos.y; }
212
213 constexpr const Vec& GetOrigin() const { return m_Pos; }
214 constexpr const Vec& GetPosition() const { return m_Pos; }
215 constexpr const Vec GetEnd() const { return Vec( GetRight(), GetBottom() ); }
216
217 constexpr size_type GetWidth() const { return m_Size.x; }
218 constexpr size_type GetHeight() const { return m_Size.y; }
219
220 constexpr coord_type GetRight() const
221 {
223 }
224
225 constexpr coord_type GetBottom() const
226 {
228 }
229
230 // Compatibility aliases
231 constexpr coord_type GetLeft() const { return GetX(); }
232 constexpr coord_type GetTop() const { return GetY(); }
233 constexpr const Vec GetCenter() const { return Centre(); }
234
238 constexpr int GetSizeMax() const { return ( m_Size.x > m_Size.y ) ? m_Size.x : m_Size.y; }
239
240 constexpr void SetOrigin( const Vec& pos )
241 {
242 m_Pos = pos;
243 m_init = true;
244 }
245
246 constexpr void SetOrigin( coord_type x, coord_type y )
247 {
248 SetOrigin( Vec( x, y ) );
249 }
250
251 constexpr void SetSize( const SizeVec& size )
252 {
253 m_Size = size;
254 m_init = true;
255 }
256
257 constexpr void SetSize( size_type w, size_type h )
258 {
259 SetSize( SizeVec( w, h ) );
260 }
261
262 constexpr void Offset( coord_type dx, coord_type dy )
263 {
264 m_Pos.x += dx;
265 m_Pos.y += dy;
266 }
267
268 constexpr void Offset( const Vec& offset )
269 {
270 Offset( offset.x, offset.y );
271 }
272
273 constexpr BOX2<Vec> GetWithOffset( const Vec& aMoveVector ) const
274 {
275 BOX2<Vec> ret( *this );
276 ret.Move( aMoveVector );
277 return ret;
278 }
279
280 constexpr void SetX( coord_type val )
281 {
282 SetOrigin( val, m_Pos.y );
283 }
284
285 constexpr void SetY( coord_type val )
286 {
287 SetOrigin( m_Pos.x, val );
288 }
289
290 constexpr void SetWidth( size_type val )
291 {
292 SetSize( val, m_Size.y );
293 }
294
295 constexpr void SetHeight( size_type val )
296 {
297 SetSize( m_Size.x, val );
298 }
299
300 constexpr void SetEnd( coord_type x, coord_type y )
301 {
302 SetEnd( Vec( x, y ) );
303 }
304
305 constexpr void SetEnd( const Vec& pos )
306 {
307 SetSize( SizeVec( pos ) - m_Pos );
308 }
309
314 constexpr bool Intersects( const BOX2<Vec>& aRect ) const
315 {
316 // this logic taken from wxWidgets' geometry.cpp file:
317 bool rc;
318
319 BOX2<Vec> me( *this );
320 BOX2<Vec> rect( aRect );
321 me.Normalize(); // ensure size is >= 0
322 rect.Normalize(); // ensure size is >= 0
323
324 // calculate the left common area coordinate:
325 ecoord_type left = std::max( me.m_Pos.x, rect.m_Pos.x );
326
327 // calculate the right common area coordinate:
328 ecoord_type right = std::min( ecoord_type( me.m_Pos.x ) + me.m_Size.x,
329 ecoord_type( rect.m_Pos.x ) + rect.m_Size.x );
330
331 // calculate the upper common area coordinate:
332 ecoord_type top = std::max( me.m_Pos.y, rect.m_Pos.y );
333
334 // calculate the lower common area coordinate:
335 ecoord_type bottom = std::min( ecoord_type( me.m_Pos.y ) + me.m_Size.y,
336 ecoord_type( rect.m_Pos.y ) + rect.m_Size.y );
337
338 // if a common area exists, it must have a positive (null accepted) size
339 if( left <= right && top <= bottom )
340 rc = true;
341 else
342 rc = false;
343
344 return rc;
345 }
346
350 constexpr BOX2<Vec> Intersect( const BOX2<Vec>& aRect )
351 {
352 BOX2<Vec> me( *this );
353 BOX2<Vec> rect( aRect );
354 me.Normalize(); // ensure size is >= 0
355 rect.Normalize(); // ensure size is >= 0
356
357 Vec topLeft, bottomRight;
358
359 topLeft.x = std::max( me.m_Pos.x, rect.m_Pos.x );
360
361 bottomRight.x = std::min( me.GetRight(), rect.GetRight() );
362
363 topLeft.y = std::max( me.m_Pos.y, rect.m_Pos.y );
364
365 bottomRight.y = std::min( me.GetBottom(), rect.GetBottom() );
366
367 if( topLeft.x < bottomRight.x && topLeft.y < bottomRight.y )
368 return BOX2<Vec>( topLeft, SizeVec( bottomRight ) - topLeft );
369 else
370 return BOX2<Vec>( Vec( 0, 0 ), SizeVec( 0, 0 ) );
371 }
372
376 bool Intersects( const Vec& aPoint1, const Vec& aPoint2 ) const
377 {
378 Vec point2, point4;
379
380 if( Contains( aPoint1 ) || Contains( aPoint2 ) )
381 return true;
382
383 point2.x = GetEnd().x;
384 point2.y = GetOrigin().y;
385 point4.x = GetOrigin().x;
386 point4.y = GetEnd().y;
387
388 //Only need to test 3 sides since a straight line can't enter and exit on same side
389 if( SegmentIntersectsSegment( aPoint1, aPoint2, GetOrigin(), point2 ) )
390 return true;
391
392 if( SegmentIntersectsSegment( aPoint1, aPoint2, point2, GetEnd() ) )
393 return true;
394
395 if( SegmentIntersectsSegment( aPoint1, aPoint2, GetEnd(), point4 ) )
396 return true;
397
398 return false;
399 }
400
405 bool Intersects( const BOX2<Vec>& aRect, const EDA_ANGLE& aRotation ) const
406 {
407 if( !m_init )
408 return false;
409
410 EDA_ANGLE rotation = aRotation;
411 rotation.Normalize();
412
413 /*
414 * Most rectangles will be axis aligned. It is quicker to check for this case and pass
415 * the rect to the simpler intersection test.
416 */
417
418 // Prevent floating point comparison errors
419 static const EDA_ANGLE ROT_EPSILON( 0.000000001, DEGREES_T );
420
421 // Test for non-rotated rectangle
422 for( EDA_ANGLE ii : { ANGLE_0, ANGLE_180, ANGLE_360 } )
423 {
424 if( std::abs( rotation - ii ) < ROT_EPSILON )
425 return Intersects( aRect );
426 }
427
428 // Test for rectangle rotated by multiple of 90 degrees
429 for( EDA_ANGLE jj : { ANGLE_90, ANGLE_270 } )
430 {
431 if( std::abs( rotation - jj ) < ROT_EPSILON )
432 {
433 BOX2<Vec> rotRect;
434
435 // Rotate the supplied rect by 90 degrees
436 rotRect.SetOrigin( aRect.Centre() );
437 rotRect.Inflate( ( aRect.GetHeight() / 2 ) + 1, ( aRect.GetWidth() / 2 ) + 1 );
438 return Intersects( rotRect );
439 }
440 }
441
442 /* There is some non-orthogonal rotation.
443 * There are three cases to test:
444 * A) One point of this rect is inside the rotated rect
445 * B) One point of the rotated rect is inside this rect
446 * C) One of the sides of the rotated rect intersect this
447 */
448
449 VECTOR2I corners[4];
450
451 /* Test A : Any corners exist in rotated rect? */
452 corners[0] = VECTOR2I( GetLeft(), GetTop() );
453 corners[1] = VECTOR2I( GetRight(), GetTop() );
454 corners[2] = VECTOR2I( GetRight(), GetBottom() );
455 corners[3] = VECTOR2I( GetLeft(), GetBottom() );
456
457 VECTOR2I rCentre = aRect.Centre();
458
459 for( int i = 0; i < 4; i++ )
460 {
461 VECTOR2I delta = corners[i] - rCentre;
462 RotatePoint( delta, -rotation );
463 delta += rCentre;
464
465 if( aRect.Contains( delta ) )
466 return true;
467 }
468
469 /* Test B : Any corners of rotated rect exist in this one? */
472
473 // Construct corners around center of shape
474 corners[0] = VECTOR2I( -w, -h );
475 corners[1] = VECTOR2I( w, -h );
476 corners[2] = VECTOR2I( w, h );
477 corners[3] = VECTOR2I( -w, h );
478
479 // Rotate and test each corner
480 for( int j = 0; j < 4; j++ )
481 {
482 RotatePoint( corners[j], rotation );
483 corners[j] += rCentre;
484
485 if( Contains( corners[j] ) )
486 return true;
487 }
488
489 /* Test C : Any sides of rotated rect intersect this */
490 if( Intersects( corners[0], corners[1] ) || Intersects( corners[1], corners[2] )
491 || Intersects( corners[2], corners[3] ) || Intersects( corners[3], corners[0] ) )
492 {
493 return true;
494 }
495
496 return false;
497 }
498
502 bool IntersectsCircle( const Vec& aCenter, const int aRadius ) const
503 {
504 if( !m_init )
505 return false;
506
507 Vec closest = NearestPoint( aCenter );
508
509 double dx = static_cast<double>( aCenter.x ) - closest.x;
510 double dy = static_cast<double>( aCenter.y ) - closest.y;
511
512 double r = static_cast<double>( aRadius );
513
514 return ( dx * dx + dy * dy ) <= ( r * r );
515 }
516
521 bool IntersectsCircleEdge( const Vec& aCenter, const int aRadius, const int aWidth ) const
522 {
523 if( !m_init )
524 return false;
525
526 BOX2<Vec> me( *this );
527 me.Normalize(); // ensure size is >= 0
528
529 // Test if the circle intersects at all
530 if( !IntersectsCircle( aCenter, aRadius + ( aWidth / 2 ) + 1 ) )
531 return false;
532
533 Vec farpt = FarthestPointTo( aCenter );
534 // Farthest point must be further than the inside of the line
535 double fx = (double) farpt.x - aCenter.x;
536 double fy = (double) farpt.y - aCenter.y;
537
538 double r = (double) aRadius - (double) aWidth / 2;
539
540 return ( fx * fx + fy * fy ) > ( r * r );
541 }
542
543 const std::string Format() const
544 {
545 std::stringstream ss;
546
547 ss << "( box corner " << m_Pos.Format() << " w " << m_Size.x << " h " << m_Size.y << " )";
548
549 return ss.str();
550 }
551
557 {
558 inflateAxis( m_Pos.x, m_Size.x, dx );
559 inflateAxis( m_Pos.y, m_Size.y, dy );
560
561 return *this;
562 }
563
568 constexpr BOX2<Vec>& Inflate( coord_type aDelta )
569 {
570 Inflate( aDelta, aDelta );
571 return *this;
572 }
573
577 constexpr BOX2<Vec> GetInflated( coord_type aDx, coord_type aDy ) const
578 {
579 BOX2<Vec> ret( *this );
580 ret.Inflate( aDx, aDy );
581 return ret;
582 }
583
587 constexpr BOX2<Vec> GetInflated( coord_type aDelta ) const
588 {
589 return GetInflated( aDelta, aDelta );
590 }
591
597 constexpr BOX2<Vec>& Merge( const BOX2<Vec>& aRect )
598 {
599 if( !m_init )
600 {
601 if( aRect.m_init )
602 {
603 m_Pos = aRect.GetPosition();
604 m_Size = aRect.GetSize();
605 m_init = true;
606 }
607
608 return *this;
609 }
610
611 Normalize(); // ensure width and height >= 0
612 BOX2<Vec> rect = aRect;
613 rect.Normalize(); // ensure width and height >= 0
614 Vec end = GetEnd();
615 Vec rect_end = rect.GetEnd();
616
617 // Change origin and size in order to contain the given rect
618 m_Pos.x = std::min( m_Pos.x, rect.m_Pos.x );
619 m_Pos.y = std::min( m_Pos.y, rect.m_Pos.y );
620 end.x = std::max( end.x, rect_end.x );
621 end.y = std::max( end.y, rect_end.y );
622 SetEnd( end );
623 return *this;
624 }
625
631 constexpr BOX2<Vec>& Merge( const Vec& aPoint )
632 {
633 if( !m_init )
634 {
635 m_Pos = aPoint;
636 m_Size = VECTOR2I( 0, 0 );
637 m_init = true;
638 return *this;
639 }
640
641 Normalize(); // ensure width and height >= 0
642
643 Vec end = GetEnd();
644
645 // Change origin and size in order to contain the given rectangle.
646 m_Pos.x = std::min( m_Pos.x, aPoint.x );
647 m_Pos.y = std::min( m_Pos.y, aPoint.y );
648 end.x = std::max( end.x, aPoint.x );
649 end.y = std::max( end.y, aPoint.y );
650 SetEnd( end );
651 return *this;
652 }
653
659 const BOX2<Vec> GetBoundingBoxRotated( const VECTOR2I& aRotCenter,
660 const EDA_ANGLE& aAngle ) const
661 {
662 VECTOR2I corners[4];
663
664 // Build the corners list
665 corners[0] = GetOrigin();
666 corners[2] = GetEnd();
667 corners[1].x = corners[0].x;
668 corners[1].y = corners[2].y;
669 corners[3].x = corners[2].x;
670 corners[3].y = corners[0].y;
671
672 // Rotate all corners, to find the bounding box
673 for( int ii = 0; ii < 4; ii++ )
674 RotatePoint( corners[ii], aRotCenter, aAngle );
675
676 // Find the corners bounding box
677 VECTOR2I start = corners[0];
678 VECTOR2I end = corners[0];
679
680 for( int ii = 1; ii < 4; ii++ )
681 {
682 start.x = std::min( start.x, corners[ii].x );
683 start.y = std::min( start.y, corners[ii].y );
684 end.x = std::max( end.x, corners[ii].x );
685 end.y = std::max( end.y, corners[ii].y );
686 }
687
688 BOX2<Vec> bbox;
689 bbox.SetOrigin( start );
690 bbox.SetEnd( end );
691
692 return bbox;
693 }
694
700 constexpr ecoord_type GetArea() const
701 {
702 return (ecoord_type) GetWidth() * (ecoord_type) GetHeight();
703 }
704
711 {
712 return m_Size.EuclideanNorm();
713 }
714
720 constexpr ecoord_type SquaredDiagonal() const
721 {
722 return m_Size.SquaredEuclideanNorm();
723 }
724
725 constexpr ecoord_type SquaredDistance( const Vec& aP ) const
726 {
727 const ecoord_type x1 = std::min<ecoord_type>( m_Pos.x, ecoord_type( m_Pos.x ) + m_Size.x );
728 const ecoord_type x2 = std::max<ecoord_type>( m_Pos.x, ecoord_type( m_Pos.x ) + m_Size.x );
729 const ecoord_type y1 = std::min<ecoord_type>( m_Pos.y, ecoord_type( m_Pos.y ) + m_Size.y );
730 const ecoord_type y2 = std::max<ecoord_type>( m_Pos.y, ecoord_type( m_Pos.y ) + m_Size.y );
731
732 const ecoord_type xdiff = std::max<ecoord_type>( aP.x < x1 ? x1 - aP.x : ecoord_type( aP.x ) - x2, 0 );
733 const ecoord_type ydiff = std::max<ecoord_type>( aP.y < y1 ? y1 - aP.y : ecoord_type( aP.y ) - y2, 0 );
734
735 return xdiff * xdiff + ydiff * ydiff;
736 }
737
738 ecoord_type Distance( const Vec& aP ) const
739 {
740 const double dist = std::sqrt( static_cast<double>( SquaredDistance( aP ) ) );
741
742 if constexpr( std::is_floating_point<ecoord_type>() )
743 return static_cast<ecoord_type>( dist );
744 else
745 return KiROUND<double, ecoord_type>( dist );
746 }
747
754 constexpr ecoord_type SquaredDistance( const BOX2<Vec>& aBox ) const
755 {
756 ecoord_type s = 0;
757
758 if( aBox.m_Pos.x + aBox.m_Size.x < m_Pos.x )
759 {
760 ecoord_type d = aBox.m_Pos.x + aBox.m_Size.x - m_Pos.x;
761 s += d * d;
762 }
763 else if( aBox.m_Pos.x > m_Pos.x + m_Size.x )
764 {
765 ecoord_type d = aBox.m_Pos.x - m_Size.x - m_Pos.x;
766 s += d * d;
767 }
768
769 if( aBox.m_Pos.y + aBox.m_Size.y < m_Pos.y )
770 {
771 ecoord_type d = aBox.m_Pos.y + aBox.m_Size.y - m_Pos.y;
772 s += d * d;
773 }
774 else if( aBox.m_Pos.y > m_Pos.y + m_Size.y )
775 {
776 ecoord_type d = aBox.m_Pos.y - m_Size.y - m_Pos.y;
777 s += d * d;
778 }
779
780 return s;
781 }
782
789 ecoord_type Distance( const BOX2<Vec>& aBox ) const
790 {
791 const double dist = std::sqrt( static_cast<double>( SquaredDistance( aBox ) ) );
792
793 if constexpr( std::is_floating_point<ecoord_type>() )
794 return static_cast<ecoord_type>( dist );
795 else
796 return KiROUND<double, ecoord_type>( dist );
797 }
798
802 constexpr Vec NearestPoint( const Vec& aPoint ) const
803 {
804 BOX2<Vec> me( *this );
805
806 me.Normalize(); // ensure size is >= 0
807
808 // Determine closest point to the circle centre within this rect
809 const coord_type nx = std::clamp( aPoint.x, me.GetLeft(), me.GetRight() );
810 const coord_type ny = std::clamp( aPoint.y, me.GetTop(), me.GetBottom() );
811
812 return Vec( nx, ny );
813 }
814
818 constexpr Vec FarthestPointTo( const Vec& aPoint ) const
819 {
820 BOX2<Vec> me( *this );
821
822 me.Normalize(); // ensure size is >= 0
823
824 coord_type fx;
825 coord_type fy;
826
827 Vec center = me.GetCenter();
828
829 if( aPoint.x < center.x )
830 fx = me.GetRight();
831 else
832 fx = me.GetLeft();
833
834 if( aPoint.y < center.y )
835 fy = me.GetBottom();
836 else
837 fy = me.GetTop();
838
839 return Vec( fx, fy );
840 }
841
842 constexpr bool operator==( const BOX2<Vec>& aOther ) const
843 {
844 auto t1 ( *this );
845 auto t2 ( aOther );
846 t1.Normalize();
847 t2.Normalize();
848 return ( t1.m_Pos == t2.m_Pos && t1.m_Size == t2.m_Size );
849 }
850
851 constexpr bool operator!=( const BOX2<Vec>& aOther ) const
852 {
853 auto t1 ( *this );
854 auto t2 ( aOther );
855 t1.Normalize();
856 t2.Normalize();
857 return ( t1.m_Pos != t2.m_Pos || t1.m_Size != t2.m_Size );
858 }
859
860 constexpr bool IsValid() const
861 {
862 return m_init;
863 }
864
865private:
866 // Widened so that sentinel deltas cannot wrap, results saturate outward to keep the original region covered
867 static constexpr void inflateAxis( coord_type& aPos, size_type& aSize, coord_type aDelta )
868 {
869 const ecoord_type pos = aPos;
870 const ecoord_type delta = aDelta;
871 const ecoord_type lowLimit = coord_limits::lowest();
872 const ecoord_type highLimit = coord_limits::max();
873
874 if( aSize >= 0 )
875 {
876 if( aSize < -2 * delta )
877 {
878 // Don't allow deflate to eat more width than we have,
879 aPos = KiCheckedCast<ecoord_type, coord_type>( pos + aSize / 2 );
880 aSize = 0;
881 }
882 else
883 {
884 const ecoord_type lo = std::clamp<ecoord_type>( pos - delta, lowLimit, highLimit );
885 const ecoord_type hi = std::clamp<ecoord_type>( pos + aSize + delta, lowLimit, highLimit );
886
887 aPos = static_cast<coord_type>( lo );
888 aSize = hi - lo;
889 }
890 }
891 else
892 {
893 if( aSize > 2 * delta )
894 {
895 aPos = KiCheckedCast<ecoord_type, coord_type>( pos - aSize / 2 );
896 aSize = 0;
897 }
898 else
899 {
900 // Negative size, pos is the high edge so inflating moves it up and the low edge down
901 const ecoord_type hi = std::clamp<ecoord_type>( pos + delta, lowLimit, highLimit );
902 const ecoord_type lo = std::clamp<ecoord_type>( pos + aSize - delta, lowLimit, highLimit );
903
904 aPos = static_cast<coord_type>( hi );
905 aSize = lo - hi;
906 }
907 }
908 }
909
910 Vec m_Pos; // Rectangle Origin
911 SizeVec m_Size; // Rectangle Size
912
913 bool m_init; // Is the rectangle initialized
914};
915
916/* Default specializations */
920
921typedef std::optional<BOX2I> OPT_BOX2I;
922
923
924inline constexpr BOX2I BOX2ISafe( const BOX2D& aInput )
925{
926 constexpr double high = std::numeric_limits<int>::max();
927 constexpr double low = -std::numeric_limits<int>::max();
928
929 int left = (int) std::clamp( aInput.GetLeft(), low, high );
930 int top = (int) std::clamp( aInput.GetTop(), low, high );
931
932 int64_t right = (int64_t) std::clamp( aInput.GetRight(), low, high );
933 int64_t bottom = (int64_t) std::clamp( aInput.GetBottom(), low, high );
934
935 return BOX2I( VECTOR2I( left, top ), VECTOR2L( right - left, bottom - top ) );
936}
937
938
943template <typename Vec>
944inline constexpr bool IsBOX2Safe( const BOX2<Vec>& aInput )
945{
946 constexpr double high = std::numeric_limits<int>::max();
947 constexpr double low = -std::numeric_limits<int>::max();
948
949 return ( aInput.GetLeft() >= low && aInput.GetTop() >= low &&
950 aInput.GetRight() <= high && aInput.GetBottom() <= high );
951}
952
953
954inline constexpr BOX2I BOX2ISafe( const VECTOR2D& aPos, const VECTOR2D& aSize )
955{
956 constexpr double high = std::numeric_limits<int>::max();
957 constexpr double low = -std::numeric_limits<int>::max();
958
959 int left = (int) std::clamp( aPos.x, low, high );
960 int top = (int) std::clamp( aPos.y, low, high );
961
962 int64_t right = (int64_t) std::clamp( aPos.x + aSize.x, low, high );
963 int64_t bottom = (int64_t) std::clamp( aPos.y + aSize.y, low, high );
964
965 return BOX2I( VECTOR2I( left, top ), VECTOR2L( right - left, bottom - top ) );
966}
967
968
969template <typename S, std::enable_if_t<std::is_integral<S>::value, int> = 0>
970inline constexpr BOX2I BOX2ISafe( const VECTOR2I& aPos, const VECTOR2<S>& aSize )
971{
972 constexpr int64_t high = std::numeric_limits<int>::max();
973 constexpr int64_t low = -std::numeric_limits<int>::max();
974
975 int64_t ext_right = int64_t( aPos.x ) + aSize.x;
976 int64_t ext_bottom = int64_t( aPos.y ) + aSize.y;
977
978 int64_t right = std::clamp( ext_right, low, high );
979 int64_t bottom = std::clamp( ext_bottom, low, high );
980
981 return BOX2I( aPos, VECTOR2L( right - aPos.x, bottom - aPos.y ) );
982}
983
984/* KiROUND specialization for double -> int boxes */
985inline constexpr BOX2I KiROUND( const BOX2D& aBoxD )
986{
987 return BOX2I( KiROUND( aBoxD.GetOrigin() ), KiROUND( aBoxD.GetSize() ) );
988}
989
990#endif
constexpr bool IsBOX2Safe(const BOX2< Vec > &aInput)
Check if a BOX2 is safe for use with BOX2D (probably BOX2D or BOX2L)
Definition box2.h:944
constexpr BOX2I BOX2ISafe(const BOX2D &aInput)
Definition box2.h:924
BOX2< VECTOR2L > BOX2L
Definition box2.h:919
BOX2< VECTOR2I > BOX2I
Definition box2.h:917
std::optional< BOX2I > OPT_BOX2I
Definition box2.h:921
constexpr BOX2I KiROUND(const BOX2D &aBoxD)
Definition box2.h:985
BOX2< VECTOR2D > BOX2D
Definition box2.h:918
A 2D bounding box built on top of an origin point and size vector.
Definition box2.h:41
constexpr BOX2< Vec > Intersect(const BOX2< Vec > &aRect)
Definition box2.h:350
constexpr ecoord_type SquaredDistance(const BOX2< Vec > &aBox) const
Return the square of the minimum distance between self and box aBox.
Definition box2.h:754
constexpr const Vec & GetPosition() const
Definition box2.h:214
constexpr int GetSizeMax() const
Definition box2.h:238
constexpr void SetMaximum()
Definition box2.h:77
Vec::extended_type size_type
Definition box2.h:44
constexpr BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Inflates the rectangle horizontally by dx and vertically by dy.
Definition box2.h:556
static constexpr BOX2< Vec > ByCorners(const Vec &aCorner1, const Vec &aCorner2)
Definition box2.h:67
constexpr bool operator==(const BOX2< Vec > &aOther) const
Definition box2.h:842
ecoord_type Distance(const BOX2< Vec > &aBox) const
Return the minimum distance between self and aBox.
Definition box2.h:789
static constexpr void inflateAxis(coord_type &aPos, size_type &aSize, coord_type aDelta)
Definition box2.h:867
constexpr void SetHeight(size_type val)
Definition box2.h:295
const std::string Format() const
Definition box2.h:543
constexpr BOX2< Vec > & Inflate(coord_type aDelta)
Inflate the rectangle horizontally and vertically by aDelta.
Definition box2.h:568
constexpr const Vec GetEnd() const
Definition box2.h:215
constexpr void SetOrigin(const Vec &pos)
Definition box2.h:240
bool Intersects(const BOX2< Vec > &aRect, const EDA_ANGLE &aRotation) const
Definition box2.h:405
constexpr ecoord_type SquaredDiagonal() const
Return the square of the length of the diagonal of the rectangle.
Definition box2.h:720
constexpr BOX2< Vec > & Normalize()
Ensure that the height and width are positive.
Definition box2.h:149
constexpr Vec NearestPoint(const Vec &aPoint) const
Return the point in this rect that is closest to the provided point.
Definition box2.h:802
ecoord_type Diagonal() const
Return the length of the diagonal of the rectangle.
Definition box2.h:710
constexpr coord_type GetY() const
Definition box2.h:211
bool Intersects(const Vec &aPoint1, const Vec &aPoint2) const
Definition box2.h:376
static constexpr BOX2< Vec > ByCenter(const Vec &aCenter, const SizeVec &aSize)
Definition box2.h:72
VECTOR2I m_Pos
Definition box2.h:910
constexpr BOX2()
Definition box2.h:49
constexpr bool operator!=(const BOX2< Vec > &aOther) const
Definition box2.h:851
constexpr void SetSize(size_type w, size_type h)
Definition box2.h:257
constexpr size_type GetWidth() const
Definition box2.h:217
constexpr Vec Centre() const
Definition box2.h:100
Vec::extended_type ecoord_type
Definition box2.h:45
constexpr coord_type GetX() const
Definition box2.h:210
constexpr void SetEnd(const Vec &pos)
Definition box2.h:305
bool IntersectsCircleEdge(const Vec &aCenter, const int aRadius, const int aWidth) const
Definition box2.h:521
constexpr BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Modify the position and size of the rectangle in order to contain aRect.
Definition box2.h:597
bool IntersectsCircle(const Vec &aCenter, const int aRadius) const
Definition box2.h:502
constexpr BOX2(const Vec &aPos, const SizeVec &aSize=SizeVec(0, 0))
Definition box2.h:55
VECTOR2< size_type > SizeVec
Definition box2.h:46
constexpr ecoord_type GetArea() const
Return the area of the rectangle.
Definition box2.h:700
constexpr const Vec GetCenter() const
Definition box2.h:233
constexpr void SetSize(const SizeVec &size)
Definition box2.h:251
std::numeric_limits< coord_type > coord_limits
Definition box2.h:47
constexpr void Offset(const Vec &offset)
Definition box2.h:268
SizeVec m_Size
Definition box2.h:911
constexpr size_type GetHeight() const
Definition box2.h:218
constexpr coord_type GetLeft() const
Definition box2.h:231
constexpr bool Contains(const Vec &aPoint) const
Definition box2.h:171
constexpr void SetOrigin(coord_type x, coord_type y)
Definition box2.h:246
constexpr void SetWidth(size_type val)
Definition box2.h:290
constexpr bool Contains(const BOX2< Vec > &aRect) const
Definition box2.h:204
Vec::coord_type coord_type
Definition box2.h:43
constexpr void Move(const Vec &aMoveVector)
Move the rectangle by the aMoveVector.
Definition box2.h:141
constexpr BOX2< Vec > GetInflated(coord_type aDelta) const
Get a new rectangle that is this one, inflated by aDelta.
Definition box2.h:587
ecoord_type Distance(const Vec &aP) const
Definition box2.h:738
constexpr BOX2< Vec > GetWithOffset(const Vec &aMoveVector) const
Definition box2.h:273
constexpr void SetX(coord_type val)
Definition box2.h:280
constexpr bool Contains(coord_type x, coord_type y) const
Definition box2.h:197
constexpr ecoord_type SquaredDistance(const Vec &aP) const
Definition box2.h:725
constexpr BOX2< Vec > GetInflated(coord_type aDx, coord_type aDy) const
Get a new rectangle that is this one, inflated by aDx and aDy.
Definition box2.h:577
constexpr const Vec & GetOrigin() const
Definition box2.h:213
constexpr void SetY(coord_type val)
Definition box2.h:285
constexpr bool IsValid() const
Definition box2.h:860
const BOX2< Vec > GetBoundingBoxRotated(const VECTOR2I &aRotCenter, const EDA_ANGLE &aAngle) const
Useful to calculate bounding box of rotated items, when rotation is not cardinal.
Definition box2.h:659
constexpr coord_type GetRight() const
Definition box2.h:220
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition box2.h:112
constexpr const SizeVec & GetSize() const
Definition box2.h:209
constexpr BOX2< Vec > & Merge(const Vec &aPoint)
Modify the position and size of the rectangle in order to contain the given point.
Definition box2.h:631
constexpr void SetEnd(coord_type x, coord_type y)
Definition box2.h:300
constexpr coord_type GetTop() const
Definition box2.h:232
constexpr void Offset(coord_type dx, coord_type dy)
Definition box2.h:262
constexpr bool Intersects(const BOX2< Vec > &aRect) const
Definition box2.h:314
constexpr coord_type GetBottom() const
Definition box2.h:225
constexpr Vec FarthestPointTo(const Vec &aPoint) const
Return the point in this rect that is farthest from the provided point.
Definition box2.h:818
EDA_ANGLE Normalize()
Definition eda_angle.h:228
Define a general 2D-vector/point.
Definition vector2d.h:67
static constexpr EDA_ANGLE ANGLE_0
Definition eda_angle.h:472
static constexpr EDA_ANGLE ANGLE_90
Definition eda_angle.h:474
@ DEGREES_T
Definition eda_angle.h:30
static constexpr EDA_ANGLE ANGLE_270
Definition eda_angle.h:477
static constexpr EDA_ANGLE ANGLE_360
Definition eda_angle.h:478
static constexpr EDA_ANGLE ANGLE_180
Definition eda_angle.h:476
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition eda_angle.h:461
KIBIS top(path, &reporter)
VECTOR2I center
VECTOR2I end
int delta
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Calculate the new point of coord coord pX, pY, for a rotation center 0, 0.
Definition trigo.cpp:227
bool SegmentIntersectsSegment(const VECTOR2I &a_p1_l1, const VECTOR2I &a_p2_l1, const VECTOR2I &a_p1_l2, const VECTOR2I &a_p2_l2, VECTOR2I *aIntersectionPoint=nullptr)
Test if two lines intersect.
Definition trigo.cpp:105
constexpr ret_type KiCheckedCast(in_type v)
Perform a cast between numerical types.
Definition util.h:66
VECTOR2< int32_t > VECTOR2I
Definition vector2d.h:708
VECTOR2< double > VECTOR2D
Definition vector2d.h:707
VECTOR2< int64_t > VECTOR2L
Definition vector2d.h:709
static PIECE rect(double aLeft, double aTop, double aRight, double aBottom, bool aMixed=false)