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 <geometry/seg.h>
26 
27 template <typename T>
28 int sgn( T aVal )
29 {
30  return ( T( 0 ) < aVal ) - ( aVal < T( 0 ) );
31 }
32 
33 
34 bool SEG::PointCloserThan( const VECTOR2I& aP, int aDist ) const
35 {
36  VECTOR2I d = B - A;
37  ecoord dist_sq = (ecoord) aDist * aDist;
38 
39  SEG::ecoord l_squared = d.Dot( d );
40  SEG::ecoord t = d.Dot( aP - A );
41 
42  if( t <= 0 || !l_squared )
43  return ( aP - A ).SquaredEuclideanNorm() < dist_sq;
44  else if( t >= l_squared )
45  return ( aP - B ).SquaredEuclideanNorm() < dist_sq;
46 
47  int dxdy = abs( d.x ) - abs( d.y );
48 
49  if( ( dxdy >= -1 && dxdy <= 1 ) || abs( d.x ) <= 1 || abs( d.y ) <= 1 )
50  {
51  int ca = -sgn( d.y );
52  int cb = sgn( d.x );
53  int cc = -ca * A.x - cb * A.y;
54 
55  ecoord num = (ecoord) ca * aP.x + (ecoord) cb * aP.y + cc;
56  num *= num;
57 
58  if( ca && cb )
59  num >>= 1;
60 
61  if( num > ( dist_sq + 100 ) )
62  return false;
63 
64  else if( num < ( dist_sq - 100 ) )
65  return true;
66  }
67 
68  VECTOR2I nearest;
69  nearest.x = A.x + rescale( t, (ecoord) d.x, l_squared );
70  nearest.y = A.y + rescale( t, (ecoord) d.y, l_squared );
71 
72  return ( nearest - aP ).SquaredEuclideanNorm() <= dist_sq;
73 }
74 
75 
76 SEG::ecoord SEG::SquaredDistance( const SEG& aSeg ) const
77 {
78  // fixme: rather inefficient....
79  if( Intersect( aSeg ) )
80  return 0;
81 
82  const VECTOR2I pts[4] =
83  {
84  aSeg.NearestPoint( A ) - A,
85  aSeg.NearestPoint( B ) - B,
86  NearestPoint( aSeg.A ) - aSeg.A,
87  NearestPoint( aSeg.B ) - aSeg.B
88  };
89 
91 
92  for( int i = 0; i < 4; i++ )
93  m = std::min( m, pts[i].SquaredEuclideanNorm() );
94 
95  return m;
96 }
97 
98 
99 OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
100 {
101  const VECTOR2I e( B - A );
102  const VECTOR2I f( aSeg.B - aSeg.A );
103  const VECTOR2I ac( aSeg.A - A );
104 
105  ecoord d = f.Cross( e );
106  ecoord p = f.Cross( ac );
107  ecoord q = e.Cross( ac );
108 
109  if( d == 0 )
110  return OPT_VECTOR2I();
111 
112  if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
113  return OPT_VECTOR2I();
114 
115  if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
116  return OPT_VECTOR2I();
117 
118  if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
119  return OPT_VECTOR2I();
120 
121  VECTOR2I ip( aSeg.A.x + rescale( q, (ecoord) f.x, d ),
122  aSeg.A.y + rescale( q, (ecoord) f.y, d ) );
123 
124  return ip;
125 }
126 
127 
128 bool SEG::ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) const
129 {
130  return (ecoord) ( aC.y - aA.y ) * ( aB.x - aA.x ) > (ecoord) ( aB.y - aA.y ) * ( aC.x - aA.x );
131 }
132 
133 
134 bool SEG::Collide( const SEG& aSeg, int aClearance ) const
135 {
136  // check for intersection
137  // fixme: move to a method
138  if( ccw( A, aSeg.A, aSeg.B ) != ccw( B, aSeg.A, aSeg.B ) &&
139  ccw( A, B, aSeg.A ) != ccw( A, B, aSeg.B ) )
140  return true;
141 
142 #define CHK( _seg, _pt ) \
143  if( (_seg).PointCloserThan( _pt, aClearance ) ) return true;
144 
145  CHK( *this, aSeg.A );
146  CHK( *this, aSeg.B );
147  CHK( aSeg, A );
148  CHK( aSeg, B );
149 #undef CHK
150 
151  return false;
152 }
153 
154 
155 bool SEG::Contains( const VECTOR2I& aP ) const
156 {
157  return PointCloserThan( aP, 1 );
158 }
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:478
T
enum T contains all this lexer's tokens.
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:76
#define abs(a)
Definition: auxiliary.h:84
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:128
#define CHK(_seg, _pt)
static const extended_type ECOORD_MAX
Definition: vector2d.h:59
int sgn(T aVal)
Definition: seg.cpp:28
boost::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:35
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:356
extended_type Cross(const VECTOR2< T > &aVector) const
Function Cross() computes cross product of self with aVector.
Definition: vector2d.h:470
Definition: seg.h:37
VECTOR2I A
Definition: seg.h:49
VECTOR2I::extended_type ecoord
Definition: seg.h:40
bool PointCloserThan(const VECTOR2I &aP, int aDist) const
Definition: seg.cpp:34
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
bool Contains(const VECTOR2I &aP) const
Definition: seg.cpp:155
#define min(a, b)
Definition: auxiliary.h:85
VECTOR2I B
Definition: seg.h:50