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  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 #include <algorithm> // for min
26 #include <geometry/seg.h>
27 #include <math/util.h> // for rescale
28 #include <math/vector2d.h> // for VECTOR2I, VECTOR2
29 
30 template <typename T>
31 int sgn( T aVal )
32 {
33  return ( T( 0 ) < aVal ) - ( aVal < T( 0 ) );
34 }
35 
36 
37 bool SEG::PointCloserThan( const VECTOR2I& aP, int aDist ) const
38 {
39  // See http://geomalgorithms.com/a02-_lines.html for some explanations and ideas.
40  VECTOR2I d = B - A;
41  ecoord dist_sq = (ecoord) aDist * aDist;
42 
43  SEG::ecoord l_squared = d.Dot( d );
44  SEG::ecoord t = d.Dot( aP - A );
45 
46  if( t <= 0 || !l_squared )
47  return ( aP - A ).SquaredEuclideanNorm() < dist_sq;
48  else if( t >= l_squared )
49  return ( aP - B ).SquaredEuclideanNorm() < dist_sq;
50 
51  // JPC: This code is not trivial and is not commented
52  // and does not work for d.x or d.y = -1...1
53  // I am guessing it is here for calculation time optimization.
54  // if someone can understand it, please fix it.
55  // It can be tested with a segment having d.x or d.y value
56  // is -1 or +1 ("this" is a quasi vertical or horizontal segment)
57  int dxdy = std::abs( d.x ) - std::abs( d.y );
58 
59  if( ( dxdy >= -1 && dxdy <= 1 ) // quasi 45 deg segment
60  /*|| std::abs( d.x ) <= 1 // quasi horizontal segment
61  || std::abs( d.y ) <= 1 // quasi vertical segment */ )
62  {
63  int ca = -sgn( d.y );
64  int cb = sgn( d.x );
65  int cc = -ca * A.x - cb * A.y;
66 
67  ecoord num = (ecoord) ca * aP.x + (ecoord) cb * aP.y + cc;
68  num *= num;
69 
70  if( ca && cb )
71  num >>= 1;
72 
73  if( num > ( dist_sq + 100 ) )
74  return false;
75 
76  else if( num < ( dist_sq - 100 ) )
77  return true;
78  }
79 
80  VECTOR2I nearest;
81  nearest.x = A.x + rescale( t, (ecoord) d.x, l_squared );
82  nearest.y = A.y + rescale( t, (ecoord) d.y, l_squared );
83 
84  return ( nearest - aP ).SquaredEuclideanNorm() <= dist_sq;
85 }
86 
87 
88 SEG::ecoord SEG::SquaredDistance( const SEG& aSeg ) const
89 {
90  // fixme: rather inefficient....
91  if( Intersect( aSeg ) )
92  return 0;
93 
94  const VECTOR2I pts[4] =
95  {
96  aSeg.NearestPoint( A ) - A,
97  aSeg.NearestPoint( B ) - B,
98  NearestPoint( aSeg.A ) - aSeg.A,
99  NearestPoint( aSeg.B ) - aSeg.B
100  };
101 
103 
104  for( int i = 0; i < 4; i++ )
105  m = std::min( m, pts[i].SquaredEuclideanNorm() );
106 
107  return m;
108 }
109 
110 
111 const VECTOR2I SEG::NearestPoint( const SEG& aSeg ) const
112 {
113  if( auto p = Intersect( aSeg ) )
114  return *p;
115 
116  const VECTOR2I pts_origin[4] =
117  {
118  aSeg.NearestPoint( A ),
119  aSeg.NearestPoint( B ),
120  NearestPoint( aSeg.A ),
121  NearestPoint( aSeg.B )
122  };
123 
124  const ecoord pts_dist[4] =
125  {
126  ( pts_origin[0] - A ).SquaredEuclideanNorm(),
127  ( pts_origin[1] - B ).SquaredEuclideanNorm(),
128  ( pts_origin[2] - aSeg.A ).SquaredEuclideanNorm(),
129  ( pts_origin[3] - aSeg.B ).SquaredEuclideanNorm()
130  };
131 
132  int min_i = 0;
133 
134  for( int i = 0; i < 4; i++ )
135  {
136  if( pts_dist[i] < pts_dist[min_i] )
137  min_i = i;
138  }
139 
140  return pts_origin[min_i];
141 }
142 
143 
144 OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
145 {
146  const VECTOR2I e( B - A );
147  const VECTOR2I f( aSeg.B - aSeg.A );
148  const VECTOR2I ac( aSeg.A - A );
149 
150  ecoord d = f.Cross( e );
151  ecoord p = f.Cross( ac );
152  ecoord q = e.Cross( ac );
153 
154  if( d == 0 )
155  return OPT_VECTOR2I();
156 
157  if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
158  return OPT_VECTOR2I();
159 
160  if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
161  return OPT_VECTOR2I();
162 
163  if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
164  return OPT_VECTOR2I();
165 
166  VECTOR2I ip( aSeg.A.x + rescale( q, (ecoord) f.x, d ),
167  aSeg.A.y + rescale( q, (ecoord) f.y, d ) );
168 
169  return ip;
170 }
171 
172 
173 bool SEG::ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) const
174 {
175  return (ecoord) ( aC.y - aA.y ) * ( aB.x - aA.x ) > (ecoord) ( aB.y - aA.y ) * ( aC.x - aA.x );
176 }
177 
178 
179 bool SEG::Collide( const SEG& aSeg, int aClearance ) const
180 {
181  // check for intersection
182  // fixme: move to a method
183  if( ccw( A, aSeg.A, aSeg.B ) != ccw( B, aSeg.A, aSeg.B ) &&
184  ccw( A, B, aSeg.A ) != ccw( A, B, aSeg.B ) )
185  return true;
186 
187 #define CHK( _seg, _pt ) \
188  if( (_seg).PointCloserThan( _pt, aClearance ) ) return true;
189 
190  CHK( *this, aSeg.A );
191  CHK( *this, aSeg.B );
192  CHK( aSeg, A );
193  CHK( aSeg, B );
194 #undef CHK
195 
196  return false;
197 }
198 
199 
200 bool SEG::Contains( const VECTOR2I& aP ) const
201 {
202  return PointCloserThan( aP, 1 );
203 }
extended_type Cross(const VECTOR2< T > &aVector) const
Function Cross() computes cross product of self with aVector.
Definition: vector2d.h:484
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:173
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:144
VECTOR2I::extended_type ecoord
Definition: seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:88
bool PointCloserThan(const VECTOR2I &aP, int aDist) const
Definition: seg.cpp:37
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:37
#define CHK(_seg, _pt)
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:397
int sgn(T aVal)
Definition: seg.cpp:31
Definition: seg.h:39
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:492
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:84
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:179
bool Contains(const SEG &aSeg) const
Definition: seg.h:299
VECTOR2I B
Definition: seg.h:48