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 <algorithm>
32#include <limits>
33#include <iostream>
34#include <sstream>
35#include <type_traits>
36
37#include <math/util.h>
38
42template <class T>
44{
47 typedef T extended_type;
48};
49
50template <>
51struct VECTOR2_TRAITS<int>
52{
53 typedef int64_t extended_type;
54};
55
56// Forward declarations for template friends
57template <class T>
58class VECTOR2;
59template <class T>
60std::ostream& operator<<( std::ostream& aStream, const VECTOR2<T>& aVector );
61
69template <class T = int>
71{
72public:
74 typedef T coord_type;
75
76 static constexpr extended_type ECOORD_MAX = std::numeric_limits<extended_type>::max();
77 static constexpr extended_type ECOORD_MIN = std::numeric_limits<extended_type>::min();
78
79 T x, y;
80
83
85 VECTOR2( T x, T y );
86
88 template <typename CastingType>
90 {
91 if( std::is_floating_point<T>() )
92 {
93 x = static_cast<T>( aVec.x );
94 y = static_cast<T>( aVec.y );
95 }
96 else if( std::is_floating_point<CastingType>() )
97 {
98 CastingType minI = static_cast<CastingType>( std::numeric_limits<T>::min() );
99 CastingType maxI = static_cast<CastingType>( std::numeric_limits<T>::max() );
100
101 x = static_cast<T>( std::clamp( aVec.x, minI, maxI ) );
102 y = static_cast<T>( std::clamp( aVec.y, minI, maxI ) );
103 }
104 else if( std::is_integral<T>() && std::is_integral<CastingType>() )
105 {
106 int64_t minI = static_cast<int64_t>( std::numeric_limits<T>::min() );
107 int64_t maxI = static_cast<int64_t>( std::numeric_limits<T>::max() );
108
109 x = static_cast<T>( std::clamp( static_cast<int64_t>( aVec.x ), minI, maxI ) );
110 y = static_cast<T>( std::clamp( static_cast<int64_t>( aVec.y ), minI, maxI ) );
111 }
112 else
113 {
114 x = static_cast<T>( aVec.x );
115 y = static_cast<T>( aVec.y );
116 }
117 }
118
120 VECTOR2( const VECTOR2<T>& aVec )
121 {
122 x = aVec.x;
123 y = aVec.y;
124 }
125
127 template <typename U>
129 {
130 if( std::is_floating_point<U>::value )
131 {
132 return VECTOR2<U>( static_cast<U>( x ), static_cast<U>( y ) );
133 }
134 else if( std::is_floating_point<T>() )
135 {
136 T minI = static_cast<T>( std::numeric_limits<U>::min() );
137 T maxI = static_cast<T>( std::numeric_limits<U>::max() );
138 return VECTOR2<U>( static_cast<U>( std::clamp( x, minI, maxI ) ),
139 static_cast<U>( std::clamp( y, minI, maxI ) ) );
140 }
141 else if( std::is_integral<T>() && std::is_integral<U>() )
142 {
143 int64_t minI = static_cast<int64_t>( std::numeric_limits<U>::min() );
144 int64_t maxI = static_cast<int64_t>( std::numeric_limits<U>::max() );
145 int64_t x64 = static_cast<int64_t>( x );
146 int64_t y64 = static_cast<int64_t>( y );
147
148 return VECTOR2<U>(
149 static_cast<U>( std::clamp( x64, minI, maxI ) ),
150 static_cast<U>( std::clamp( y64, minI, maxI ) ) );
151 }
152 else
153 {
154 return VECTOR2<U>( static_cast<U>( x ), static_cast<U>( y ) );
155 }
156 }
157
158 // virtual ~VECTOR2();
159
167 T EuclideanNorm() const;
168
177
178
185
192 VECTOR2<T> Resize( T aNewLength ) const;
193
199 const std::string Format() const;
200
204 extended_type Cross( const VECTOR2<T>& aVector ) const;
205
209 extended_type Dot( const VECTOR2<T>& aVector ) const;
210
215 double Distance( const VECTOR2<extended_type>& aVector ) const;
216
217
218 // Operators
219
221 VECTOR2<T>& operator=( const VECTOR2<T>& aVector );
222
224 VECTOR2<T>& operator+=( const VECTOR2<T>& aVector );
225
227 VECTOR2<T>& operator*=( const VECTOR2<T>& aVector );
228
229 VECTOR2<T>& operator*=( const T& aScalar );
230
232 VECTOR2<T>& operator+=( const T& aScalar );
233
235 VECTOR2<T>& operator-=( const VECTOR2<T>& aVector );
236
238 VECTOR2<T>& operator-=( const T& aScalar );
239
242
244 VECTOR2<T> operator/( double aFactor ) const;
245
247 bool operator==( const VECTOR2<T>& aVector ) const;
248
250 bool operator!=( const VECTOR2<T>& aVector ) const;
251
253 bool operator<( const VECTOR2<T>& aVector ) const;
254 bool operator<=( const VECTOR2<T>& aVector ) const;
255
257 bool operator>( const VECTOR2<T>& aVector ) const;
258 bool operator>=( const VECTOR2<T>& aVector ) const;
259};
260
261
262// ----------------------
263// --- Implementation ---
264// ----------------------
265
266template <class T>
268{
269}
270
271
272template <class T>
274{
275 x = aX;
276 y = aY;
277}
278
279
280template <class T>
282{
283 // 45° are common in KiCad, so we can optimize the calculation
284 if( std::abs( x ) == std::abs( y ) )
285 {
286 if( std::is_integral<T>::value )
287 return KiROUND<double, T>( std::abs( x ) * M_SQRT2 );
288
289 return static_cast<T>( std::abs( x ) * M_SQRT2 );
290 }
291
292 if( x == 0 )
293 return static_cast<T>( std::abs( y ) );
294 if( y == 0 )
295 return static_cast<T>( std::abs( x ) );
296
297 if( std::is_integral<T>::value )
298 return KiROUND<double, T>( std::hypot( x, y ) );
299
300 return static_cast<T>( std::hypot( x, y ) );
301}
302
303
304template <class T>
306{
307 return (extended_type) x * x + (extended_type) y * y;
308}
309
310
311template <class T>
313{
314 VECTOR2<T> perpendicular( -y, x );
315 return perpendicular;
316}
317
318
319template <class T>
321{
322 x = aVector.x;
323 y = aVector.y;
324 return *this;
325}
326
327
328template <class T>
330{
331 x += aVector.x;
332 y += aVector.y;
333 return *this;
334}
335
336
337template <class T>
339{
340 x *= aVector.x;
341 y *= aVector.y;
342 return *this;
343}
344
345
346template <class T>
348{
349 x *= aScalar;
350 y *= aScalar;
351 return *this;
352}
353
354
355template <class T>
357{
358 x += aScalar;
359 y += aScalar;
360 return *this;
361}
362
363
364template <class T>
366{
367 x -= aVector.x;
368 y -= aVector.y;
369 return *this;
370}
371
372
373template <class T>
375{
376 x -= aScalar;
377 y -= aScalar;
378 return *this;
379}
380
381
382template <class T>
383VECTOR2<T> VECTOR2<T>::Resize( T aNewLength ) const
384{
385 if( x == 0 && y == 0 )
386 return VECTOR2<T> ( 0, 0 );
387
388 double newX;
389 double newY;
390
391 if( std::abs( x ) == std::abs( y ) )
392 {
393 newX = newY = std::abs( aNewLength ) * M_SQRT1_2;
394 }
395 else
396 {
397 extended_type x_sq = (extended_type) x * x;
398 extended_type y_sq = (extended_type) y * y;
399 extended_type l_sq = x_sq + y_sq;
400 extended_type newLength_sq = (extended_type) aNewLength * aNewLength;
401 newX = std::sqrt( rescale( newLength_sq, x_sq, l_sq ) );
402 newY = std::sqrt( rescale( newLength_sq, y_sq, l_sq ) );
403 }
404
405 if( std::is_integral<T>::value )
406 {
407 return VECTOR2<T>( static_cast<T>( x < 0 ? -KiROUND( newX ) : KiROUND( newX ) ),
408 static_cast<T>( y < 0 ? -KiROUND( newY ) : KiROUND( newY ) ) )
409 * sign( aNewLength );
410 }
411 else
412 {
413 return VECTOR2<T>( static_cast<T>( x < 0 ? -newX : newX ),
414 static_cast<T>( y < 0 ? -newY : newY ) )
415 * sign( aNewLength );
416 }
417}
418
419
420template <class T>
421const std::string VECTOR2<T>::Format() const
422{
423 std::stringstream ss;
424
425 ss << "( xy " << x << " " << y << " )";
426
427 return ss.str();
428}
429
430
431template <class T>
432concept FloatingPoint = std::is_floating_point<T>::value;
433
434template <class T>
435concept Integral = std::is_integral<T>::value;
436
437
438template <class T, class U>
440{
441 return VECTOR2<std::common_type_t<T, U>>( aLHS.x + aRHS.x, aLHS.y + aRHS.y );
442}
443
444
445template <FloatingPoint T, class U>
446VECTOR2<T> operator+( const VECTOR2<T>& aLHS, const U& aScalar )
447{
448 return VECTOR2<T>( aLHS.x + aScalar, aLHS.y + aScalar );
449}
450
451
452template <Integral T, Integral U>
453VECTOR2<T> operator+( const VECTOR2<T>& aLHS, const U& aScalar )
454{
455 return VECTOR2<T>( aLHS.x + aScalar, aLHS.y + aScalar );
456}
457
458
459template <Integral T, FloatingPoint U>
460VECTOR2<T> operator+( const VECTOR2<T>& aLHS, const U& aScalar )
461{
462 return VECTOR2<T>( KiROUND( aLHS.x + aScalar ), KiROUND( aLHS.y + aScalar ) );
463}
464
465
466template <class T, class U>
468{
469 return VECTOR2<std::common_type_t<T, U>>( aLHS.x - aRHS.x, aLHS.y - aRHS.y );
470}
471
472
473template <FloatingPoint T, class U>
474VECTOR2<T> operator-( const VECTOR2<T>& aLHS, U aScalar )
475{
476 return VECTOR2<T>( aLHS.x - aScalar, aLHS.y - aScalar );
477}
478
479
480template <Integral T, Integral U>
481VECTOR2<T> operator-( const VECTOR2<T>& aLHS, U aScalar )
482{
483 return VECTOR2<T>( aLHS.x - aScalar, aLHS.y - aScalar );
484}
485
486
487template <Integral T, FloatingPoint U>
488VECTOR2<T> operator-( const VECTOR2<T>& aLHS, const U& aScalar )
489{
490 return VECTOR2<T>( KiROUND( aLHS.x - aScalar ), KiROUND( aLHS.y - aScalar ) );
491}
492
493
494template <class T>
496{
497 return VECTOR2<T> ( -x, -y );
498}
499
500
501template <class T, class U>
502#ifdef SWIG
503double operator*( const VECTOR2<T>& aLHS, const VECTOR2<U>& aRHS )
504#else
505auto operator*( const VECTOR2<T>& aLHS, const VECTOR2<U>& aRHS )
506#endif
507{
508 using extended_type = typename VECTOR2<std::common_type_t<T, U>>::extended_type;
509 return (extended_type)aLHS.x * aRHS.x + (extended_type)aLHS.y * aRHS.y;
510}
511
512
513template <class T, class U>
515{
516 return VECTOR2<std::common_type_t<T, U>>( aLHS.x * aScalar, aLHS.y * aScalar );
517}
518
519
520template <class T, class U>
521VECTOR2<std::common_type_t<T, U>> operator*( const T& aScalar, const VECTOR2<U>& aVector )
522{
523 return VECTOR2<std::common_type_t<T, U>>( aScalar * aVector.x, aScalar * aVector.y );
524}
525
526
527template <class T>
528VECTOR2<T> VECTOR2<T>::operator/( double aFactor ) const
529{
530 if( std::is_integral<T>::value )
531 return VECTOR2<T>( KiROUND( x / aFactor ), KiROUND( y / aFactor ) );
532 else
533 return VECTOR2<T>( static_cast<T>( x / aFactor ), static_cast<T>( y / aFactor ) );
534}
535
536
537template <class T>
539{
540 return (extended_type) x * (extended_type) aVector.y -
541 (extended_type) y * (extended_type) aVector.x;
542}
543
544
545template <class T>
547{
548 return (extended_type) x * (extended_type) aVector.x +
549 (extended_type) y * (extended_type) aVector.y;
550}
551
552template <class T>
553double VECTOR2<T>::Distance( const VECTOR2<extended_type>& aVector ) const
554{
555 VECTOR2<double> diff( aVector.x - x, aVector.y - y );
556 return diff.EuclideanNorm();
557}
558
559
560template <class T>
561bool VECTOR2<T>::operator<( const VECTOR2<T>& aVector ) const
562{
563 return ( *this * *this ) < ( aVector * aVector );
564}
565
566
567template <class T>
568bool VECTOR2<T>::operator<=( const VECTOR2<T>& aVector ) const
569{
570 return ( *this * *this ) <= ( aVector * aVector );
571}
572
573
574template <class T>
575bool VECTOR2<T>::operator>( const VECTOR2<T>& aVector ) const
576{
577 return ( *this * *this ) > ( aVector * aVector );
578}
579
580
581template <class T>
582bool VECTOR2<T>::operator>=( const VECTOR2<T>& aVector ) const
583{
584 return ( *this * *this ) >= ( aVector * aVector );
585}
586
587
588template <class T>
589bool VECTOR2<T>::operator==( VECTOR2<T> const& aVector ) const
590{
591 return ( aVector.x == x ) && ( aVector.y == y );
592}
593
594
595template <class T>
596bool VECTOR2<T>::operator!=( VECTOR2<T> const& aVector ) const
597{
598 return ( aVector.x != x ) || ( aVector.y != y );
599}
600
601
602template <class T>
604{
605 if( aA.x > aB.x )
606 return aA;
607 else if( aA.x == aB.x && aA.y > aB.y )
608 return aA;
609
610 return aB;
611}
612
613
614template <class T>
616{
617 if( aA.x < aB.x )
618 return aA;
619 else if( aA.x == aB.x && aA.y < aB.y )
620 return aA;
621
622 return aB;
623}
624
625
626template <class T>
628{
629 if( aA.x < aB.x )
630 return -1;
631 else if( aA.x > aB.x )
632 return 1;
633 else // aA.x == aB.x
634 {
635 if( aA.y < aB.y )
636 return -1;
637 else if( aA.y > aB.y )
638 return 1;
639 else
640 return 0;
641 }
642}
643
644
653template <class T>
654typename std::enable_if<!std::numeric_limits<T>::is_integer, bool>::type
655equals( VECTOR2<T> const& aFirst, VECTOR2<T> const& aSecond,
656 T aEpsilon = std::numeric_limits<T>::epsilon() )
657{
658 if( !equals( aFirst.x, aSecond.x, aEpsilon ) )
659 {
660 return false;
661 }
662
663 return equals( aFirst.y, aSecond.y, aEpsilon );
664}
665
666
667template <class T>
668std::ostream& operator<<( std::ostream& aStream, const VECTOR2<T>& aVector )
669{
670 aStream << "[ " << aVector.x << " | " << aVector.y << " ]";
671 return aStream;
672}
673
674/* Default specializations */
678
679/* KiROUND specialization for vectors */
680inline VECTOR2I KiROUND( const VECTOR2D& vec )
681{
682 return VECTOR2I( KiROUND( vec.x ), KiROUND( vec.y ) );
683}
684
685/* STL specializations */
686namespace std
687{
688 // Required to enable correct use in std::map/unordered_map
689 // DO NOT USE hash tables with VECTOR2 elements. It is inefficient
690 // and degenerates to a linear search. Use the std::map/std::set
691 // trees instead that utilize the less operator below
692 // This function is purposely deleted after substantial testing
693 template <>
694 struct hash<VECTOR2I>
695 {
696 size_t operator()( const VECTOR2I& k ) const = delete;
697 };
698
699 // Required to enable use of std::hash with maps.
700 template <>
701 struct less<VECTOR2I>
702 {
703 bool operator()( const VECTOR2I& aA, const VECTOR2I& aB ) const;
704 };
705}
706
707#endif // VECTOR2D_H_
Define a general 2D-vector/point.
Definition: vector2d.h:71
VECTOR2< T > & operator+=(const T &aScalar)
Compound assignment operator.
Definition: vector2d.h:356
VECTOR2(const VECTOR2< CastingType > &aVec)
Initializes a vector from another specialization. Beware of rounding issues.
Definition: vector2d.h:89
VECTOR2< T > & operator*=(const T &aScalar)
Definition: vector2d.h:347
extended_type SquaredEuclideanNorm() const
Compute the squared euclidean norm of the vector, which is defined as (x ** 2 + y ** 2).
Definition: vector2d.h:305
double Distance(const VECTOR2< extended_type > &aVector) const
Compute the distance between two vectors.
Definition: vector2d.h:553
VECTOR2< T > & operator*=(const VECTOR2< T > &aVector)
Compound assignment operator.
Definition: vector2d.h:338
const std::string Format() const
Return the vector formatted as a string.
Definition: vector2d.h:421
VECTOR2()
Construct a 2D-vector with x, y = 0.
Definition: vector2d.h:267
VECTOR2< T > operator/(double aFactor) const
Division with a factor.
Definition: vector2d.h:528
VECTOR2(T x, T y)
Construct a vector with given components x, y.
Definition: vector2d.h:273
bool operator>=(const VECTOR2< T > &aVector) const
Definition: vector2d.h:582
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:76
VECTOR2< T > & operator+=(const VECTOR2< T > &aVector)
Compound assignment operator.
Definition: vector2d.h:329
VECTOR2(const VECTOR2< T > &aVec)
Copy a vector.
Definition: vector2d.h:120
VECTOR2< U > operator()() const
Cast a vector to another specialized subclass. Beware of rounding issues.
Definition: vector2d.h:128
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:281
VECTOR2_TRAITS< T >::extended_type extended_type
Definition: vector2d.h:73
bool operator==(const VECTOR2< T > &aVector) const
Equality operator.
Definition: vector2d.h:589
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:312
bool operator<=(const VECTOR2< T > &aVector) const
Definition: vector2d.h:568
VECTOR2< T > & operator=(const VECTOR2< T > &aVector)
Assignment operator.
Definition: vector2d.h:320
VECTOR2< T > & operator-=(const T &aScalar)
Compound assignment operator.
Definition: vector2d.h:374
bool operator!=(const VECTOR2< T > &aVector) const
Not equality operator.
Definition: vector2d.h:596
static constexpr extended_type ECOORD_MIN
Definition: vector2d.h:77
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:538
bool operator>(const VECTOR2< T > &aVector) const
Greater than operator.
Definition: vector2d.h:575
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:546
VECTOR2< T > & operator-=(const VECTOR2< T > &aVector)
Compound assignment operator.
Definition: vector2d.h:365
bool operator<(const VECTOR2< T > &aVector) const
Smaller than operator.
Definition: vector2d.h:561
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:383
VECTOR2< T > operator-()
Negate Vector operator.
Definition: vector2d.h:495
T coord_type
Definition: vector2d.h:74
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:53
Traits class for VECTOR2.
Definition: vector2d.h:44
T extended_type
extended range/precision types used by operations involving multiple multiplications to prevent overf...
Definition: vector2d.h:47
size_t operator()(const VECTOR2I &k) const =delete
int sign(T val)
Definition: util.h:159
T rescale(T aNumerator, T aValue, T aDenominator)
Scale a number (value) by rational (numerator/denominator).
Definition: util.h:153
VECTOR2< int32_t > VECTOR2I
Definition: vector2d.h:676
VECTOR2< double > VECTOR2D
Definition: vector2d.h:675
const VECTOR2< T > LexicographicalMax(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:603
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:655
VECTOR2< std::common_type_t< T, U > > operator+(const VECTOR2< T > &aLHS, const VECTOR2< U > &aRHS)
Definition: vector2d.h:439
auto operator*(const VECTOR2< T > &aLHS, const VECTOR2< U > &aRHS)
Definition: vector2d.h:505
VECTOR2< int64_t > VECTOR2L
Definition: vector2d.h:677
VECTOR2< std::common_type_t< T, U > > operator-(const VECTOR2< T > &aLHS, const VECTOR2< U > &aRHS)
Definition: vector2d.h:467
VECTOR2I KiROUND(const VECTOR2D &vec)
Definition: vector2d.h:680
const VECTOR2< T > LexicographicalMin(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:615
int LexicographicalCompare(const VECTOR2< T > &aA, const VECTOR2< T > &aB)
Definition: vector2d.h:627