KiCad PCB EDA Suite
Loading...
Searching...
No Matches
vector2d.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) 2010 Virtenio GmbH, Torsten Hueter, torsten.hueter <at> virtenio.de
5 * Copyright (C) 2012 SoftPLC Corporation, Dick Hollenbeck <[email protected]>
6 * Copyright (C) 2012-2021 KiCad Developers, see AUTHORS.txt for contributors.
7 * Copyright (C) 2013 CERN
8 * @author Tomasz Wlostowski <[email protected]>
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, you may find one here:
22 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23 * or you may search the http://www.gnu.org website for the version 2 license,
24 * or you may write to the Free Software Foundation, Inc.,
25 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26 */
27
28#ifndef VECTOR2D_H_
29#define VECTOR2D_H_
30
31#include <limits>
32#include <iostream>
33#include <sstream>
34#include <type_traits>
35
36#include <math/util.h>
37
41template <class T>
43{
46 typedef T extended_type;
47};
48
49template <>
50struct VECTOR2_TRAITS<int>
51{
52 typedef int64_t extended_type;
53};
54
55// Forward declarations for template friends
56template <class T>
57class VECTOR2;
58template <class T>
59std::ostream& operator<<( std::ostream& aStream, const VECTOR2<T>& aVector );
60
68template <class T = int>
70{
71public:
73 typedef T coord_type;
74
75 static constexpr extended_type ECOORD_MAX = std::numeric_limits<extended_type>::max();
76 static constexpr extended_type ECOORD_MIN = std::numeric_limits<extended_type>::min();
77
78 T x, y;
79
82
84 VECTOR2( T x, T y );
85
87 template <typename CastingType>
89 {
90 if( std::is_floating_point<T>() )
91 {
92 x = static_cast<T>( aVec.x );
93 y = static_cast<T>( aVec.y );
94 }
95 else if( std::is_floating_point<CastingType>() )
96 {
97 CastingType minI = static_cast<CastingType>( std::numeric_limits<T>::min() );
98 CastingType maxI = static_cast<CastingType>( std::numeric_limits<T>::max() );
99
100 x = static_cast<T>( Clamp( minI, aVec.x, maxI ) );
101 y = static_cast<T>( Clamp( minI, aVec.y, maxI ) );
102 }
103 else if( std::is_integral<T>() && std::is_integral<CastingType>() )
104 {
105 int64_t minI = static_cast<int64_t>( std::numeric_limits<T>::min() );
106 int64_t maxI = static_cast<int64_t>( std::numeric_limits<T>::max() );
107
108 x = static_cast<T>( Clamp( minI, static_cast<int64_t>( aVec.x ), maxI ) );
109 y = static_cast<T>( Clamp( minI, static_cast<int64_t>(aVec.y), maxI ) );
110 }
111 else
112 {
113 x = static_cast<T>( aVec.x );
114 y = static_cast<T>( aVec.y );
115 }
116 }
117
119 VECTOR2( const VECTOR2<T>& aVec )
120 {
121 x = aVec.x;
122 y = aVec.y;
123 }
124
126 template <typename U>
128 {
129 if( std::is_floating_point<U>::value )
130 {
131 return VECTOR2<U>( static_cast<U>( x ), static_cast<U>( y ) );
132 }
133 else if( std::is_floating_point<T>() )
134 {
135 T minI = static_cast<T>( std::numeric_limits<U>::min() );
136 T maxI = static_cast<T>( std::numeric_limits<U>::max() );
137 return VECTOR2<U>( static_cast<U>( Clamp( minI, x, maxI ) ),
138 static_cast<U>( Clamp( minI, y, maxI ) ) );
139 }
140 else if( std::is_integral<T>() && std::is_integral<U>() )
141 {
142 int64_t minI = static_cast<int64_t>( std::numeric_limits<U>::min() );
143 int64_t maxI = static_cast<int64_t>( std::numeric_limits<U>::max() );
144
145 return VECTOR2<U>(
146 static_cast<U>( Clamp( minI, static_cast<int64_t>( x ), maxI ) ),
147 static_cast<U>( Clamp( minI, static_cast<int64_t>( y ), maxI ) ) );
148 }
149 else
150 {
151 return VECTOR2<U>( static_cast<U>( x ), static_cast<U>( y ) );
152 }
153 }
154
155 // virtual ~VECTOR2();
156
164 T EuclideanNorm() const;
165
174
175
182
189 VECTOR2<T> Resize( T aNewLength ) const;
190
196 const std::string Format() const;
197
201 extended_type Cross( const VECTOR2<T>& aVector ) const;
202
206 extended_type Dot( const VECTOR2<T>& aVector ) const;
207
212 double Distance( const VECTOR2<extended_type>& aVector ) const;
213
214
215 // Operators
216
218 VECTOR2<T>& operator=( const VECTOR2<T>& aVector );
219
221 VECTOR2<T>& operator+=( const VECTOR2<T>& aVector );
222
224 VECTOR2<T>& operator*=( const VECTOR2<T>& aVector );
225
226 VECTOR2<T>& operator*=( const T& aScalar );
227
229 VECTOR2<T>& operator+=( const T& aScalar );
230
232 VECTOR2<T>& operator-=( const VECTOR2<T>& aVector );
233
235 VECTOR2<T>& operator-=( const T& aScalar );
236
239
241 VECTOR2<T> operator/( double aFactor ) const;
242
244 bool operator==( const VECTOR2<T>& aVector ) const;
245
247 bool operator!=( const VECTOR2<T>& aVector ) const;
248
250 bool operator<( const VECTOR2<T>& aVector ) const;
251 bool operator<=( const VECTOR2<T>& aVector ) const;
252
254 bool operator>( const VECTOR2<T>& aVector ) const;
255 bool operator>=( const VECTOR2<T>& aVector ) const;
256};
257
258
259// ----------------------
260// --- Implementation ---
261// ----------------------
262
263template <class T>
265{
266}
267
268
269template <class T>
271{
272 x = aX;
273 y = aY;
274}
275
276
277template <class T>
279{
280 // 45° are common in KiCad, so we can optimize the calculation
281 if( std::abs( x ) == std::abs( y ) )
282 {
283 if( std::is_integral<T>::value )
284 return KiROUND<double, T>( std::abs( x ) * M_SQRT2 );
285
286 return static_cast<T>( std::abs( x ) * M_SQRT2 );
287 }
288
289 if( x == 0 )
290 return static_cast<T>( std::abs( y ) );
291 if( y == 0 )
292 return static_cast<T>( std::abs( x ) );
293
294 if( std::is_integral<T>::value )
295 return KiROUND<double, T>( std::hypot( x, y ) );
296
297 return static_cast<T>( std::hypot( x, y ) );
298}
299
300
301template <class T>
303{
304 return (extended_type) x * x + (extended_type) y * y;
305}
306
307
308template <class T>
310{
311 VECTOR2<T> perpendicular( -y, x );
312 return perpendicular;
313}
314
315
316template <class T>
318{
319 x = aVector.x;
320 y = aVector.y;
321 return *this;
322}
323
324
325template <class T>
327{
328 x += aVector.x;
329 y += aVector.y;
330 return *this;
331}
332
333
334template <class T>
336{
337 x *= aVector.x;
338 y *= aVector.y;
339 return *this;
340}
341
342
343template <class T>
345{
346 x *= aScalar;
347 y *= aScalar;
348 return *this;
349}
350
351
352template <class T>
354{
355 x += aScalar;
356 y += aScalar;
357 return *this;
358}
359
360
361template <class T>
363{
364 x -= aVector.x;
365 y -= aVector.y;
366 return *this;
367}
368
369
370template <class T>
372{
373 x -= aScalar;
374 y -= aScalar;
375 return *this;
376}
377
378
379template <class T>
380VECTOR2<T> VECTOR2<T>::Resize( T aNewLength ) const
381{
382 if( x == 0 && y == 0 )
383 return VECTOR2<T> ( 0, 0 );
384
385 double newX;
386 double newY;
387
388 if( std::abs( x ) == std::abs( y ) )
389 {
390 newX = newY = std::abs( aNewLength ) * M_SQRT1_2;
391 }
392 else
393 {
394 extended_type x_sq = (extended_type) x * x;
395 extended_type y_sq = (extended_type) y * y;
396 extended_type l_sq = x_sq + y_sq;
397 extended_type newLength_sq = (extended_type) aNewLength * aNewLength;
398 newX = std::sqrt( rescale( newLength_sq, x_sq, l_sq ) );
399 newY = std::sqrt( rescale( newLength_sq, y_sq, l_sq ) );
400 }
401
402 if( std::is_integral<T>::value )
403 {
404 return VECTOR2<T>( static_cast<T>( x < 0 ? -KiROUND( newX ) : KiROUND( newX ) ),
405 static_cast<T>( y < 0 ? -KiROUND( newY ) : KiROUND( newY ) ) )
406 * sign( aNewLength );
407 }
408 else
409 {
410 return VECTOR2<T>( static_cast<T>( x < 0 ? -newX : newX ),
411 static_cast<T>( y < 0 ? -newY : newY ) )
412 * sign( aNewLength );
413 }
414}
415
416
417template <class T>
418const std::string VECTOR2<T>::Format() const
419{
420 std::stringstream ss;
421
422 ss << "( xy " << x << " " << y << " )";
423
424 return ss.str();
425}
426
427
428template <class T>
429concept FloatingPoint = std::is_floating_point<T>::value;
430
431template <class T>
432concept Integral = std::is_integral<T>::value;
433
434
435template <class T, class U>
437{
438 return VECTOR2<std::common_type_t<T, U>>( aLHS.x + aRHS.x, aLHS.y + aRHS.y );
439}
440
441
442template <FloatingPoint T, class U>
443VECTOR2<T> operator+( const VECTOR2<T>& aLHS, const U& aScalar )
444{
445 return VECTOR2<T>( aLHS.x + aScalar, aLHS.y + aScalar );
446}
447
448
449template <Integral T, Integral U>
450VECTOR2<T> operator+( const VECTOR2<T>& aLHS, const U& aScalar )
451{
452 return VECTOR2<T>( aLHS.x + aScalar, aLHS.y + aScalar );
453}
454
455
456template <Integral T, FloatingPoint U>
457VECTOR2<T> operator+( const VECTOR2<T>& aLHS, const U& aScalar )
458{
459 return VECTOR2<T>( KiROUND( aLHS.x + aScalar ), KiROUND( aLHS.y + aScalar ) );
460}
461
462
463template <class T, class U>
465{
466 return VECTOR2<std::common_type_t<T, U>>( aLHS.x - aRHS.x, aLHS.y - aRHS.y );
467}
468
469
470template <FloatingPoint T, class U>
471VECTOR2<T> operator-( const VECTOR2<T>& aLHS, U aScalar )
472{
473 return VECTOR2<T>( aLHS.x - aScalar, aLHS.y - aScalar );
474}
475
476
477template <Integral T, Integral U>
478VECTOR2<T> operator-( const VECTOR2<T>& aLHS, U aScalar )
479{
480 return VECTOR2<T>( aLHS.x - aScalar, aLHS.y - aScalar );
481}
482
483
484template <Integral T, FloatingPoint U>
485VECTOR2<T> operator-( const VECTOR2<T>& aLHS, const U& aScalar )
486{
487 return VECTOR2<T>( KiROUND( aLHS.x - aScalar ), KiROUND( aLHS.y - aScalar ) );
488}
489
490
491template <class T>
493{
494 return VECTOR2<T> ( -x, -y );
495}
496
497
498template <class T, class U>
499#ifdef SWIG
500double operator*( const VECTOR2<T>& aLHS, const VECTOR2<U>& aRHS )
501#else
502auto operator*( const VECTOR2<T>& aLHS, const VECTOR2<U>& aRHS )
503#endif
504{
505 using extended_type = typename VECTOR2<std::common_type_t<T, U>>::extended_type;
506 return (extended_type)aLHS.x * aRHS.x + (extended_type)aLHS.y * aRHS.y;
507}
508
509
510template <class T, class U>
512{
513 return VECTOR2<std::common_type_t<T, U>>( aLHS.x * aScalar, aLHS.y * aScalar );
514}
515
516
517template <class T, class U>
518VECTOR2<std::common_type_t<T, U>> operator*( const T& aScalar, const VECTOR2<U>& aVector )
519{
520 return VECTOR2<std::common_type_t<T, U>>( aScalar * aVector.x, aScalar * aVector.y );
521}
522
523
524template <class T>
525VECTOR2<T> VECTOR2<T>::operator/( double aFactor ) const
526{
527 if( std::is_integral<T>::value )
528 return VECTOR2<T>( KiROUND( x / aFactor ), KiROUND( y / aFactor ) );
529 else
530 return VECTOR2<T>( static_cast<T>( x / aFactor ), static_cast<T>( y / aFactor ) );
531}
532
533
534template <class T>
536{
537 return (extended_type) x * (extended_type) aVector.y -
538 (extended_type) y * (extended_type) aVector.x;
539}
540
541
542template <class T>
544{
545 return (extended_type) x * (extended_type) aVector.x +
546 (extended_type) y * (extended_type) aVector.y;
547}
548
549template <class T>
550double VECTOR2<T>::Distance( const VECTOR2<extended_type>& aVector ) const
551{
552 VECTOR2<double> diff( aVector.x - x, aVector.y - y );
553 return diff.EuclideanNorm();
554}
555
556
557template <class T>
558bool VECTOR2<T>::operator<( const VECTOR2<T>& aVector ) const
559{
560 return ( *this * *this ) < ( aVector * aVector );
561}
562
563
564template <class T>
565bool VECTOR2<T>::operator<=( const VECTOR2<T>& aVector ) const
566{
567 return ( *this * *this ) <= ( aVector * aVector );
568}
569
570
571template <class T>
572bool VECTOR2<T>::operator>( const VECTOR2<T>& aVector ) const
573{
574 return ( *this * *this ) > ( aVector * aVector );
575}
576
577
578template <class T>
579bool VECTOR2<T>::operator>=( const VECTOR2<T>& aVector ) const
580{
581 return ( *this * *this ) >= ( aVector * aVector );
582}
583
584
585template <class T>
586bool VECTOR2<T>::operator==( VECTOR2<T> const& aVector ) const
587{
588 return ( aVector.x == x ) && ( aVector.y == y );
589}
590
591
592template <class T>
593bool VECTOR2<T>::operator!=( VECTOR2<T> const& aVector ) const
594{
595 return ( aVector.x != x ) || ( aVector.y != y );
596}
597
598
599template <class T>
601{
602 if( aA.x > aB.x )
603 return aA;
604 else if( aA.x == aB.x && aA.y > aB.y )
605 return aA;
606
607 return aB;
608}
609
610
611template <class T>
613{
614 if( aA.x < aB.x )
615 return aA;
616 else if( aA.x == aB.x && aA.y < aB.y )
617 return aA;
618
619 return aB;
620}
621
622
623template <class T>
625{
626 if( aA.x < aB.x )
627 return -1;
628 else if( aA.x > aB.x )
629 return 1;
630 else // aA.x == aB.x
631 {
632 if( aA.y < aB.y )
633 return -1;
634 else if( aA.y > aB.y )
635 return 1;
636 else
637 return 0;
638 }
639}
640
641
650template <class T>
651typename std::enable_if<!std::numeric_limits<T>::is_integer, bool>::type
652equals( VECTOR2<T> const& aFirst, VECTOR2<T> const& aSecond,
653 T aEpsilon = std::numeric_limits<T>::epsilon() )
654{
655 if( !equals( aFirst.x, aSecond.x, aEpsilon ) )
656 {
657 return false;
658 }
659
660 return equals( aFirst.y, aSecond.y, aEpsilon );
661}
662
663
664template <class T>
665std::ostream& operator<<( std::ostream& aStream, const VECTOR2<T>& aVector )
666{
667 aStream << "[ " << aVector.x << " | " << aVector.y << " ]";
668 return aStream;
669}
670
671/* Default specializations */
675
676/* KiROUND specialization for vectors */
677inline VECTOR2I KiROUND( const VECTOR2D& vec )
678{
679 return VECTOR2I( KiROUND( vec.x ), KiROUND( vec.y ) );
680}
681
682/* STL specializations */
683namespace std
684{
685 // Required to enable correct use in std::map/unordered_map
686 // DO NOT USE hash tables with VECTOR2 elements. It is inefficient
687 // and degenerates to a linear search. Use the std::map/std::set
688 // trees instead that utilize the less operator below
689 // This function is purposely deleted after substantial testing
690 template <>
691 struct hash<VECTOR2I>
692 {
693 size_t operator()( const VECTOR2I& k ) const = delete;
694 };
695
696 // Required to enable use of std::hash with maps.
697 template <>
698 struct less<VECTOR2I>
699 {
700 bool operator()( const VECTOR2I& aA, const VECTOR2I& aB ) const;
701 };
702}
703
704#endif // VECTOR2D_H_
Define a general 2D-vector/point.
Definition: vector2d.h:70
VECTOR2< T > & operator+=(const T &aScalar)
Compound assignment operator.
Definition: vector2d.h:353
VECTOR2(const VECTOR2< CastingType > &aVec)
Initializes a vector from another specialization. Beware of rounding issues.
Definition: vector2d.h:88
VECTOR2< T > & operator*=(const T &aScalar)
Definition: vector2d.h:344
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:302
double Distance(const VECTOR2< extended_type > &aVector) const
Compute the distance between two vectors.
Definition: vector2d.h:550
VECTOR2< T > & operator*=(const VECTOR2< T > &aVector)
Compound assignment operator.
Definition: vector2d.h:335
const std::string Format() const
Return the vector formatted as a string.
Definition: vector2d.h:418
VECTOR2()
Construct a 2D-vector with x, y = 0.
Definition: vector2d.h:264
VECTOR2< T > operator/(double aFactor) const
Division with a factor.
Definition: vector2d.h:525
VECTOR2(T x, T y)
Construct a vector with given components x, y.
Definition: vector2d.h:270
bool operator>=(const VECTOR2< T > &aVector) const
Definition: vector2d.h:579
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:75
VECTOR2< T > & operator+=(const VECTOR2< T > &aVector)
Compound assignment operator.
Definition: vector2d.h:326
VECTOR2(const VECTOR2< T > &aVec)
Copy a vector.
Definition: vector2d.h:119
VECTOR2< U > operator()() const
Cast a vector to another specialized subclass. Beware of rounding issues.
Definition: vector2d.h:127
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:278
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:72
bool operator==(const VECTOR2< T > &aVector) const
Equality operator.
Definition: vector2d.h:586
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:309
bool operator<=(const VECTOR2< T > &aVector) const
Definition: vector2d.h:565
VECTOR2< T > & operator=(const VECTOR2< T > &aVector)
Assignment operator.
Definition: vector2d.h:317
VECTOR2< T > & operator-=(const T &aScalar)
Compound assignment operator.
Definition: vector2d.h:371
bool operator!=(const VECTOR2< T > &aVector) const
Not equality operator.
Definition: vector2d.h:593
static constexpr extended_type ECOORD_MIN
Definition: vector2d.h:76
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:535
bool operator>(const VECTOR2< T > &aVector) const
Greater than operator.
Definition: vector2d.h:572
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:543
VECTOR2< T > & operator-=(const VECTOR2< T > &aVector)
Compound assignment operator.
Definition: vector2d.h:362
bool operator<(const VECTOR2< T > &aVector) const
Smaller than operator.
Definition: vector2d.h:558
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:380
VECTOR2< T > operator-()
Negate Vector operator.
Definition: vector2d.h:492
T coord_type
Definition: vector2d.h:73
std::ostream & operator<<(std::ostream &aStream, const EDA_TEXT &aText)
Definition: eda_text.cpp:1170
STL namespace.
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:390
int64_t extended_type
Definition: vector2d.h:52
Traits class for VECTOR2.
Definition: vector2d.h:43
T extended_type
extended range/precision types used by operations involving multiple multiplications to prevent overf...
Definition: vector2d.h:46
size_t operator()(const VECTOR2I &k) const =delete
int sign(T val)
Definition: util.h:171
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:165
constexpr T Clamp(const T &lower, const T &value, const T &upper)
Limit value within the range lower <= value <= upper.
Definition: util.h:65
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:673
VECTOR2< double > VECTOR2D
Definition: vector2d.h:672
const VECTOR2< T > LexicographicalMax(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:600
std::enable_if<!std::numeric_limits< T >::is_integer, bool >::type equals(VECTOR2< T > const &aFirst, VECTOR2< T > const &aSecond, T aEpsilon=std::numeric_limits< T >::epsilon())
Template to compare two VECTOR2<T> values for equality within a required epsilon.
Definition: vector2d.h:652
VECTOR2< std::common_type_t< T, U > > operator+(const VECTOR2< T > &aLHS, const VECTOR2< U > &aRHS)
Definition: vector2d.h:436
auto operator*(const VECTOR2< T > &aLHS, const VECTOR2< U > &aRHS)
Definition: vector2d.h:502
VECTOR2< int64_t > VECTOR2L
Definition: vector2d.h:674
VECTOR2< std::common_type_t< T, U > > operator-(const VECTOR2< T > &aLHS, const VECTOR2< U > &aRHS)
Definition: vector2d.h:464
VECTOR2I KiROUND(const VECTOR2D &vec)
Definition: vector2d.h:677
const VECTOR2< T > LexicographicalMin(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:612
int LexicographicalCompare(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:624