KiCad PCB EDA Suite
seg.cpp
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) 2013 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #include <algorithm> // for min
27 #include <geometry/seg.h>
28 #include <math/util.h> // for rescale
29 #include <math/vector2d.h> // for VECTOR2I, VECTOR2
30 
31 template <typename T>
32 int sgn( T aVal )
33 {
34  return ( T( 0 ) < aVal ) - ( aVal < T( 0 ) );
35 }
36 
37 
38 SEG::ecoord SEG::SquaredDistance( const SEG& aSeg ) const
39 {
40  // fixme: rather inefficient....
41  if( Intersect( aSeg ) )
42  return 0;
43 
44  const VECTOR2I pts[4] =
45  {
46  aSeg.NearestPoint( A ) - A,
47  aSeg.NearestPoint( B ) - B,
48  NearestPoint( aSeg.A ) - aSeg.A,
49  NearestPoint( aSeg.B ) - aSeg.B
50  };
51 
53 
54  for( int i = 0; i < 4; i++ )
55  {
56  m = std::min( m, pts[i].SquaredEuclideanNorm() );
57  }
58 
59  return m;
60 }
61 
62 
63 const VECTOR2I SEG::NearestPoint( const SEG& aSeg ) const
64 {
65  if( OPT_VECTOR2I p = Intersect( aSeg ) )
66  return *p;
67 
68  const VECTOR2I pts_origin[4] =
69  {
70  aSeg.NearestPoint( A ),
71  aSeg.NearestPoint( B ),
72  NearestPoint( aSeg.A ),
73  NearestPoint( aSeg.B )
74  };
75 
76 
77  const VECTOR2I* pts_out[4] =
78  {
79  &A,
80  &B,
81  &pts_origin[2],
82  &pts_origin[3]
83  };
84 
85  const ecoord pts_dist[4] =
86  {
87  ( pts_origin[0] - A ).SquaredEuclideanNorm(),
88  ( pts_origin[1] - B ).SquaredEuclideanNorm(),
89  ( pts_origin[2] - aSeg.A ).SquaredEuclideanNorm(),
90  ( pts_origin[3] - aSeg.B ).SquaredEuclideanNorm()
91  };
92 
93  int min_i = 0;
94 
95  for( int i = 0; i < 4; i++ )
96  {
97  if( pts_dist[i] < pts_dist[min_i] )
98  min_i = i;
99  }
100 
101  return *pts_out[min_i];
102 }
103 
104 
105 OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
106 {
107  const VECTOR2I e( B - A );
108  const VECTOR2I f( aSeg.B - aSeg.A );
109  const VECTOR2I ac( aSeg.A - A );
110 
111  ecoord d = f.Cross( e );
112  ecoord p = f.Cross( ac );
113  ecoord q = e.Cross( ac );
114 
115  if( d == 0 )
116  return OPT_VECTOR2I();
117 
118  if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
119  return OPT_VECTOR2I();
120 
121  if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
122  return OPT_VECTOR2I();
123 
124  if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
125  return OPT_VECTOR2I();
126 
127  VECTOR2I ip( aSeg.A.x + rescale( q, (ecoord) f.x, d ),
128  aSeg.A.y + rescale( q, (ecoord) f.y, d ) );
129 
130  return ip;
131 }
132 
133 
135 {
136  VECTOR2I slope( B - A );
137  VECTOR2I endPoint = slope.Perpendicular() + aP;
138 
139  return SEG( aP, endPoint );
140 }
141 
142 
143 SEG SEG::ParallelSeg( const VECTOR2I& aP ) const
144 {
145  VECTOR2I slope( B - A );
146  VECTOR2I endPoint = slope + aP;
147 
148  return SEG( aP, endPoint );
149 }
150 
151 
152 bool SEG::ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) const
153 {
154  return (ecoord) ( aC.y - aA.y ) * ( aB.x - aA.x ) > (ecoord) ( aB.y - aA.y ) * ( aC.x - aA.x );
155 }
156 
157 
158 bool SEG::Collide( const SEG& aSeg, int aClearance, int* aActual ) const
159 {
160  // check for intersection
161  // fixme: move to a method
162  if( ccw( A, aSeg.A, aSeg.B ) != ccw( B, aSeg.A, aSeg.B ) &&
163  ccw( A, B, aSeg.A ) != ccw( A, B, aSeg.B ) )
164  {
165  if( aActual )
166  *aActual = 0;
167 
168  return true;
169  }
170 
171  ecoord dist_sq = VECTOR2I::ECOORD_MAX;
172 
173  dist_sq = std::min( dist_sq, SquaredDistance( aSeg.A ) );
174  dist_sq = std::min( dist_sq, SquaredDistance( aSeg.B ) );
175  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( A ) );
176  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( B ) );
177 
178  if( dist_sq == 0 || dist_sq < (ecoord) aClearance * aClearance )
179  {
180  if( aActual )
181  *aActual = sqrt( dist_sq );
182 
183  return true;
184  }
185 
186  return false;
187 }
188 
189 
190 bool SEG::Contains( const VECTOR2I& aP ) const
191 {
192  return SquaredDistance( aP ) <= 1; // 1 * 1 to be pedantic
193 }
extended_type Cross(const VECTOR2< T > &aVector) const
Compute cross product of self with aVector.
Definition: vector2d.h:513
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:134
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:152
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
SEG()
Create an empty (0, 0) segment.
Definition: seg.h:55
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Compute intersection point of segment (this) with segment aSeg.
Definition: seg.cpp:105
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:158
VECTOR2I::extended_type ecoord
Definition: seg.h:44
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:38
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:143
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:79
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.h:422
int sgn(T aVal)
Definition: seg.cpp:32
Definition: seg.h:41
VECTOR2I A
Definition: seg.h:49
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
bool Contains(const SEG &aSeg) const
Definition: seg.h:321
VECTOR2I B
Definition: seg.h:50