KiCad PCB EDA Suite
seg.h
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 * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <[email protected]>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version 2
12 * of the License, or (at your option) any later version.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, you may find one here:
21 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
22 * or you may search the http://www.gnu.org website for the version 2 license,
23 * or you may write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
25 */
26
27#ifndef __SEG_H
28#define __SEG_H
29
30#include <math.h> // for sqrt
31#include <stdlib.h> // for abs
32#include <ostream> // for operator<<, ostream, basic_os...
33#include <type_traits> // for swap
34
35#include <optional>
36#include <math/vector2d.h>
37#include <geometry/eda_angle.h>
38
39typedef std::optional<VECTOR2I> OPT_VECTOR2I;
40
41class SEG
42{
43public:
45 friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
46
47 /* Start and the of the segment. Public, to make access simpler.
48 */
51
56 {
57 m_index = -1;
58 }
59
63 SEG( int aX1, int aY1, int aX2, int aY2 ) :
64 A( VECTOR2I( aX1, aY1 ) ),
65 B( VECTOR2I( aX2, aY2 ) )
66 {
67 m_index = -1;
68 }
69
73 SEG( const VECTOR2I& aA, const VECTOR2I& aB ) :
74 A( aA ),
75 B( aB )
76 {
77 m_index = -1;
78 }
79
87 SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) :
88 A( aA ),
89 B( aB )
90 {
91 m_index = aIndex;
92 }
93
97 SEG( const SEG& aSeg ) :
98 A( aSeg.A ),
99 B( aSeg.B ),
100 m_index( aSeg.m_index )
101 {
102 }
103
104 SEG& operator=( const SEG& aSeg )
105 {
106 A = aSeg.A;
107 B = aSeg.B;
108 m_index = aSeg.m_index;
109
110 return *this;
111 }
112
113 bool operator==( const SEG& aSeg ) const
114 {
115 return (A == aSeg.A && B == aSeg.B) ;
116 }
117
118 bool operator!=( const SEG& aSeg ) const
119 {
120 return (A != aSeg.A || B != aSeg.B);
121 }
122
123 static SEG::ecoord Square( int a )
124 {
125 return ecoord( a ) * a;
126 }
127
135 VECTOR2I LineProject( const VECTOR2I& aP ) const;
136
143 int Side( const VECTOR2I& aP ) const
144 {
145 const ecoord det = ( B - A ).Cross( aP - A );
146
147 return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
148 }
149
159 int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
160
167 EDA_ANGLE Angle( const SEG& aOther ) const;
168
174 const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
175
181 const VECTOR2I NearestPoint( const SEG &aSeg ) const;
182
188 const VECTOR2I ReflectPoint( const VECTOR2I& aP ) const;
189
199 OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
200 bool aLines = false ) const;
201
202 bool Intersects( const SEG& aSeg ) const;
203
210 OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
211 {
212 return Intersect( aSeg, false, true );
213 }
214
221 SEG PerpendicularSeg( const VECTOR2I& aP ) const;
222
229 SEG ParallelSeg( const VECTOR2I& aP ) const;
230
231 bool Collide( const SEG& aSeg, int aClearance, int* aActual = nullptr ) const;
232
233 ecoord SquaredDistance( const SEG& aSeg ) const;
234
241 int Distance( const SEG& aSeg ) const;
242
243 ecoord SquaredDistance( const VECTOR2I& aP ) const
244 {
245 return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
246 }
247
254 int Distance( const VECTOR2I& aP ) const;
255
256 void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
257 {
258 qA = ecoord{ A.y } - B.y;
259 qB = ecoord{ B.x } - A.x;
260 qC = -qA * A.x - qB * A.y;
261 }
262
269 bool Collinear( const SEG& aSeg ) const
270 {
271 ecoord qa, qb, qc;
272 CanonicalCoefs( qa, qb, qc );
273
274 ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
275 ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
276
277 return ( d1 <= 1 && d2 <= 1 );
278 }
279
280 bool ApproxCollinear( const SEG& aSeg ) const
281 {
282 ecoord p, q, r;
283 CanonicalCoefs( p, q, r );
284
285 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
286 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
287
288 return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
289 }
290
291 bool ApproxParallel( const SEG& aSeg, int aDistanceThreshold = 1 ) const
292 {
293 ecoord p, q, r;
294 CanonicalCoefs( p, q, r );
295
296 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
297 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
298
299 return std::abs( dist1 - dist2 ) <= aDistanceThreshold;
300 }
301
302 bool ApproxPerpendicular( const SEG& aSeg ) const
303 {
304 SEG perp = PerpendicularSeg( A );
305
306 return aSeg.ApproxParallel( perp );
307 }
308
309 bool Overlaps( const SEG& aSeg ) const
310 {
311 if( aSeg.A == aSeg.B ) // single point corner case
312 {
313 if( A == aSeg.A || B == aSeg.A )
314 return false;
315
316 return Contains( aSeg.A );
317 }
318
319 if( !Collinear( aSeg ) )
320 return false;
321
322 if( Contains( aSeg.A ) || Contains( aSeg.B ) )
323 return true;
324
325 if( aSeg.Contains( A ) || aSeg.Contains( B ) )
326 return true;
327
328 return false;
329 }
330
331
332 bool Contains( const SEG& aSeg ) const
333 {
334 if( aSeg.A == aSeg.B ) // single point corner case
335 return Contains( aSeg.A );
336
337 if( !Collinear( aSeg ) )
338 return false;
339
340 if( Contains( aSeg.A ) && Contains( aSeg.B ) )
341 return true;
342
343 return false;
344 }
345
351 int Length() const
352 {
353 return ( A - B ).EuclideanNorm();
354 }
355
357 {
358 return ( A - B ).SquaredEuclideanNorm();
359 }
360
361 ecoord TCoef( const VECTOR2I& aP ) const;
362
369 int Index() const
370 {
371 return m_index;
372 }
373
374 bool Contains( const VECTOR2I& aP ) const;
375
376 void Reverse()
377 {
378 std::swap( A, B );
379 }
380
381 SEG Reversed() const
382 {
383 return SEG( B, A );
384 }
385
388 {
389 return A + ( B - A ) / 2;
390 }
391
392private:
393 bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
394
395 bool intersects( const SEG& aSeg, bool aIgnoreEndpoints = false, bool aLines = false,
396 VECTOR2I* aPt = nullptr ) const;
397
398private:
401};
402
403inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
404{
405 VECTOR2I d = B - A;
406 return d.Dot( aP - A);
407}
408
409inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
410{
411 aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
412
413 return aStream;
414}
415
416#endif // __SEG_H
Definition: seg.h:42
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:283
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:331
ecoord SquaredDistance(const SEG &aSeg) const
Definition: seg.cpp:75
bool intersects(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false, VECTOR2I *aPt=nullptr) const
Definition: seg.cpp:150
int m_index
< index within the parent shape (used when m_is_local == false)
Definition: seg.h:400
VECTOR2I::extended_type ecoord
Definition: seg.h:44
void CanonicalCoefs(ecoord &qA, ecoord &qB, ecoord &qC) const
Definition: seg.h:256
SEG(const VECTOR2I &aA, const VECTOR2I &aB, int aIndex)
Create a segment between (aA) and (aB), referenced to a multi-segment shape.
Definition: seg.h:87
friend std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:409
SEG & operator=(const SEG &aSeg)
Definition: seg.h:104
VECTOR2I B
Definition: seg.h:50
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition: seg.h:369
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition: seg.cpp:261
ecoord SquaredDistance(const VECTOR2I &aP) const
Definition: seg.h:243
bool Intersects(const SEG &aSeg) const
Definition: seg.cpp:182
int Length() const
Return the length (this).
Definition: seg.h:351
SEG(int aX1, int aY1, int aX2, int aY2)
Create a segment between (aX1, aY1) and (aX2, aY2).
Definition: seg.h:63
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:188
static SEG::ecoord Square(int a)
Definition: seg.h:123
VECTOR2I Center() const
Definition: seg.h:387
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:223
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.h:291
SEG()
Create an empty (0, 0) segment.
Definition: seg.h:55
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition: seg.h:269
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:208
ecoord TCoef(const VECTOR2I &aP) const
Definition: seg.h:403
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
ecoord SquaredLength() const
Definition: seg.h:356
bool operator==(const SEG &aSeg) const
Definition: seg.h:113
void Reverse()
Definition: seg.h:376
bool ApproxCollinear(const SEG &aSeg) const
Definition: seg.h:280
bool ApproxPerpendicular(const SEG &aSeg) const
Definition: seg.h:302
bool Overlaps(const SEG &aSeg) const
Definition: seg.h:309
bool operator!=(const SEG &aSeg) const
Definition: seg.h:118
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.cpp:319
bool ccw(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC) const
Definition: seg.cpp:217
bool Contains(const SEG &aSeg) const
Definition: seg.h:332
SEG(const SEG &aSeg)
Copy constructor.
Definition: seg.h:97
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:302
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:199
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:143
EDA_ANGLE Angle(const SEG &aOther) const
Determine the smallest angle between two segments.
Definition: seg.cpp:97
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Create a segment between (aA) and (aB).
Definition: seg.h:73
SEG Reversed() const
Returns the center point of the line.
Definition: seg.h:381
VECTOR2_TRAITS< int >::extended_type extended_type
Definition: vector2d.h:76
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition: vector2d.h:495
E_SERIE r
Definition: eserie.cpp:41
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
std::ostream & operator<<(std::ostream &aStream, const SEG &aSeg)
Definition: seg.h:409
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
VECTOR2I::extended_type ecoord