Horizon
seg.h
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#ifndef __SEG_H
26#define __SEG_H
27
28#include <cstdio>
29#include <climits>
30
31#include <math/vector2d.h>
32#include <core/optional.h>
33
34typedef OPT<VECTOR2I> OPT_VECTOR2I;
35
36class SEG
37{
38public:
39 using ecoord = VECTOR2I::extended_type;
40 friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
41
42 /* Start and the of the segment. Public, to make access simpler.
43 */
44 VECTOR2I A;
45 VECTOR2I B;
46
51 {
52 m_index = -1;
53 }
54
59 SEG( int aX1, int aY1, int aX2, int aY2 ) :
60 A ( VECTOR2I( aX1, aY1 ) ),
61 B ( VECTOR2I( aX2, aY2 ) )
62 {
63 m_index = -1;
64 }
65
70 SEG( const VECTOR2I& aA, const VECTOR2I& aB ) : A( aA ), B( aB )
71 {
72 m_index = -1;
73 }
74
82 SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) : A( aA ), B( aB )
83 {
84 m_index = aIndex;
85 }
86
90 SEG( const SEG& aSeg ) : A( aSeg.A ), B( aSeg.B ), m_index( aSeg.m_index )
91 {
92 }
93
94 SEG& operator=( const SEG& aSeg )
95 {
96 A = aSeg.A;
97 B = aSeg.B;
98 m_index = aSeg.m_index;
99
100 return *this;
101 }
102
103 bool operator==( const SEG& aSeg ) const
104 {
105 return (A == aSeg.A && B == aSeg.B) ;
106 }
107
108 bool operator!=( const SEG& aSeg ) const
109 {
110 return (A != aSeg.A || B != aSeg.B);
111 }
112
121 VECTOR2I LineProject( const VECTOR2I& aP ) const;
122
130 int Side( const VECTOR2I& aP ) const
131 {
132 const ecoord det = ( B - A ).Cross( aP - A );
133
134 return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
135 }
136
147 int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
148
155 const VECTOR2I NearestPoint( const VECTOR2I &aP ) const;
156
161 const VECTOR2I NearestPoint( const SEG &aSeg ) const;
162
173 OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
174 bool aLines = false ) const;
175
183 OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
184 {
185 return Intersect( aSeg, false, true );
186 }
187
188 bool Collide( const SEG& aSeg, int aClearance ) const;
189
190 ecoord SquaredDistance( const SEG& aSeg ) const;
191
199 int Distance( const SEG& aSeg ) const
200 {
201 return sqrt( SquaredDistance( aSeg ) );
202 }
203
204 ecoord SquaredDistance( const VECTOR2I& aP ) const
205 {
206 return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
207 }
208
216 int Distance( const VECTOR2I& aP ) const
217 {
218 return sqrt( SquaredDistance( aP ) );
219 }
220
221 void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
222 {
223 qA = A.y - B.y;
224 qB = B.x - A.x;
225 qC = -qA * A.x - qB * A.y;
226 }
227
235 bool Collinear( const SEG& aSeg ) const
236 {
237 ecoord qa, qb, qc;
238 CanonicalCoefs( qa, qb, qc );
239
240 ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
241 ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
242
243 return ( d1 <= 1 && d2 <= 1 );
244 }
245
246 bool ApproxCollinear( const SEG& aSeg ) const
247 {
248 ecoord p, q, r;
249 CanonicalCoefs( p, q, r );
250
251 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
252 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
253
254 return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
255 }
256
257 bool ApproxParallel ( const SEG& aSeg ) const
258 {
259 ecoord p, q, r;
260 CanonicalCoefs( p, q, r );
261
262 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
263 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
264
265 return std::abs( dist1 - dist2 ) <= 1;
266 }
267
268
269 bool Overlaps( const SEG& aSeg ) const
270 {
271 if( aSeg.A == aSeg.B ) // single point corner case
272 {
273 if( A == aSeg.A || B == aSeg.A )
274 return false;
275
276 return Contains( aSeg.A );
277 }
278
279 if( !Collinear( aSeg ) )
280 return false;
281
282 if( Contains( aSeg.A ) || Contains( aSeg.B ) )
283 return true;
284 if( aSeg.Contains( A ) || aSeg.Contains( B ) )
285 return true;
286
287 return false;
288 }
289
296 int Length() const
297 {
298 return ( A - B ).EuclideanNorm();
299 }
300
301 ecoord SquaredLength() const
302 {
303 return ( A - B ).SquaredEuclideanNorm();
304 }
305
306 ecoord TCoef( const VECTOR2I& aP ) const;
307
314 int Index() const
315 {
316 return m_index;
317 }
318
319 bool Contains( const VECTOR2I& aP ) const;
320
321 bool PointCloserThan( const VECTOR2I& aP, int aDist ) const;
322
323 void Reverse()
324 {
325 std::swap( A, B );
326 }
327
330 {
331 return A + ( B - A ) / 2;
332 }
333
334private:
335 bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
336
338 int m_index;
339};
340
341inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const
342{
343 VECTOR2I d = B - A;
344 ecoord l_squared = d.Dot( d );
345
346 if( l_squared == 0 )
347 return A;
348
349 ecoord t = d.Dot( aP - A );
350
351 int xp = rescale( t, (ecoord)d.x, l_squared );
352 int yp = rescale( t, (ecoord)d.y, l_squared );
353
354 return A + VECTOR2I( xp, yp );
355}
356
357inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const
358{
359 ecoord p = A.y - B.y;
360 ecoord q = B.x - A.x;
361 ecoord r = -p * A.x - q * A.y;
362
363 ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q );
364
365 return aDetermineSide ? dist : std::abs( dist );
366}
367
368inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
369{
370 VECTOR2I d = B - A;
371 return d.Dot( aP - A);
372}
373
374inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const
375{
376 VECTOR2I d = B - A;
377 ecoord l_squared = d.Dot( d );
378
379 if( l_squared == 0 )
380 return A;
381
382 ecoord t = d.Dot( aP - A );
383
384 if( t < 0 )
385 return A;
386 else if( t > l_squared )
387 return B;
388
389 int xp = rescale( t, (ecoord)d.x, l_squared );
390 int yp = rescale( t, (ecoord)d.y, l_squared );
391
392 return A + VECTOR2I( xp, yp );
393}
394
395inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
396{
397 aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
398
399 return aStream;
400}
401
402#endif // __SEG_H
Definition: seg.h:37
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Function LineDistance()
Definition: seg.h:357
SEG(const VECTOR2I &aA, const VECTOR2I &aB, int aIndex)
Constructor Creates a segment between (aA) and (aB), referenced to a multi-segment shape.
Definition: seg.h:82
int Index() const
Function Index()
Definition: seg.h:314
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: seg.h:374
int Length() const
Function Length()
Definition: seg.h:296
SEG(int aX1, int aY1, int aX2, int aY2)
Constructor Creates a segment between (aX1, aY1) and (aX2, aY2)
Definition: seg.h:59
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:141
VECTOR2I Center() const
‍Returns the center point of the line
Definition: seg.h:329
SEG()
Default constructor Creates an empty (0, 0) segment.
Definition: seg.h:50
bool Collinear(const SEG &aSeg) const
Function Collinear()
Definition: seg.h:235
int Distance(const VECTOR2I &aP) const
Function Distance()
Definition: seg.h:216
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Function IntersectLines()
Definition: seg.h:183
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:199
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:90
VECTOR2I LineProject(const VECTOR2I &aP) const
Function LineProject()
Definition: seg.h:341
int Side(const VECTOR2I &aP) const
Function Side()
Definition: seg.h:130
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Creates a segment between (aA) and (aB)
Definition: seg.h:70
extended_type Dot(const VECTOR2< T > &aVector) const
Function Dot() computes dot product of self with aVector.
Definition: vector2d.h:476