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 SEG::ecoord SEG::SquaredDistance( const SEG& aSeg ) const
38 {
39  // fixme: rather inefficient....
40  if( Intersect( aSeg ) )
41  return 0;
42 
43  const VECTOR2I pts[4] =
44  {
45  aSeg.NearestPoint( A ) - A,
46  aSeg.NearestPoint( B ) - B,
47  NearestPoint( aSeg.A ) - aSeg.A,
48  NearestPoint( aSeg.B ) - aSeg.B
49  };
50 
52 
53  for( int i = 0; i < 4; i++ )
54  {
55  m = std::min( m, pts[i].SquaredEuclideanNorm() );
56  }
57 
58  return m;
59 }
60 
61 
62 const VECTOR2I SEG::NearestPoint( const SEG& aSeg ) const
63 {
64  if( OPT_VECTOR2I p = Intersect( aSeg ) )
65  return *p;
66 
67  const VECTOR2I pts_origin[4] =
68  {
69  aSeg.NearestPoint( A ),
70  aSeg.NearestPoint( B ),
71  NearestPoint( aSeg.A ),
72  NearestPoint( aSeg.B )
73  };
74 
75 
76  const VECTOR2I* pts_out[4] =
77  {
78  &A,
79  &B,
80  &pts_origin[2],
81  &pts_origin[3]
82  };
83 
84  const ecoord pts_dist[4] =
85  {
86  ( pts_origin[0] - A ).SquaredEuclideanNorm(),
87  ( pts_origin[1] - B ).SquaredEuclideanNorm(),
88  ( pts_origin[2] - aSeg.A ).SquaredEuclideanNorm(),
89  ( pts_origin[3] - aSeg.B ).SquaredEuclideanNorm()
90  };
91 
92  int min_i = 0;
93 
94  for( int i = 0; i < 4; i++ )
95  {
96  if( pts_dist[i] < pts_dist[min_i] )
97  min_i = i;
98  }
99 
100  return *pts_out[min_i];
101 }
102 
103 
104 OPT_VECTOR2I SEG::Intersect( const SEG& aSeg, bool aIgnoreEndpoints, bool aLines ) const
105 {
106  const VECTOR2I e( B - A );
107  const VECTOR2I f( aSeg.B - aSeg.A );
108  const VECTOR2I ac( aSeg.A - A );
109 
110  ecoord d = f.Cross( e );
111  ecoord p = f.Cross( ac );
112  ecoord q = e.Cross( ac );
113 
114  if( d == 0 )
115  return OPT_VECTOR2I();
116 
117  if( !aLines && d > 0 && ( q < 0 || q > d || p < 0 || p > d ) )
118  return OPT_VECTOR2I();
119 
120  if( !aLines && d < 0 && ( q < d || p < d || p > 0 || q > 0 ) )
121  return OPT_VECTOR2I();
122 
123  if( !aLines && aIgnoreEndpoints && ( q == 0 || q == d ) && ( p == 0 || p == d ) )
124  return OPT_VECTOR2I();
125 
126  VECTOR2I ip( aSeg.A.x + rescale( q, (ecoord) f.x, d ),
127  aSeg.A.y + rescale( q, (ecoord) f.y, d ) );
128 
129  return ip;
130 }
131 
132 
133 bool SEG::ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) const
134 {
135  return (ecoord) ( aC.y - aA.y ) * ( aB.x - aA.x ) > (ecoord) ( aB.y - aA.y ) * ( aC.x - aA.x );
136 }
137 
138 
139 bool SEG::Collide( const SEG& aSeg, int aClearance, int* aActual ) const
140 {
141  // check for intersection
142  // fixme: move to a method
143  if( ccw( A, aSeg.A, aSeg.B ) != ccw( B, aSeg.A, aSeg.B ) &&
144  ccw( A, B, aSeg.A ) != ccw( A, B, aSeg.B ) )
145  {
146  if( aActual )
147  *aActual = 0;
148 
149  return true;
150  }
151 
152  ecoord dist_sq = VECTOR2I::ECOORD_MAX;
153 
154  dist_sq = std::min( dist_sq, SquaredDistance( aSeg.A ) );
155  dist_sq = std::min( dist_sq, SquaredDistance( aSeg.B ) );
156  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( A ) );
157  dist_sq = std::min( dist_sq, aSeg.SquaredDistance( B ) );
158 
159  if( dist_sq == 0 || dist_sq < (ecoord) aClearance * aClearance )
160  {
161  if( aActual )
162  *aActual = sqrt( dist_sq );
163 
164  return true;
165  }
166 
167  return false;
168 }
169 
170 
171 bool SEG::Contains( const VECTOR2I& aP ) const
172 {
173  return SquaredDistance( aP ) < 1; // 1 * 1 to be pedantic
174 }
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:133
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:104
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:139
VECTOR2I::extended_type ecoord
Definition: seg.h:42
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:37
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
OPT< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:37
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:395
int sgn(T aVal)
Definition: seg.cpp:31
Definition: seg.h:39
VECTOR2I A
Definition: seg.h:47
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
bool Contains(const SEG &aSeg) const
Definition: seg.h:299
VECTOR2I B
Definition: seg.h:48