Horizon
Loading...
Searching...
No Matches
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 * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6 *
7 * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
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
38typedef std::optional<VECTOR2I> OPT_VECTOR2I;
39
40class SEG
41{
42public:
43 using ecoord = VECTOR2I::extended_type;
44 friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );
45
46 /* Start and the of the segment. Public, to make access simpler.
47 */
48 VECTOR2I A;
49 VECTOR2I B;
50
55 {
56 m_index = -1;
57 }
58
62 SEG( int aX1, int aY1, int aX2, int aY2 ) :
63 A( VECTOR2I( aX1, aY1 ) ),
64 B( VECTOR2I( aX2, aY2 ) )
65 {
66 m_index = -1;
67 }
68
72 SEG( const VECTOR2I& aA, const VECTOR2I& aB ) :
73 A( aA ),
74 B( aB )
75 {
76 m_index = -1;
77 }
78
86 SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) :
87 A( aA ),
88 B( aB )
89 {
90 m_index = aIndex;
91 }
92
96 SEG( const SEG& aSeg ) :
97 A( aSeg.A ),
98 B( aSeg.B ),
99 m_index( aSeg.m_index )
100 {
101 }
102
103 SEG& operator=( const SEG& aSeg )
104 {
105 A = aSeg.A;
106 B = aSeg.B;
107 m_index = aSeg.m_index;
108
109 return *this;
110 }
111
112 bool operator==( const SEG& aSeg ) const
113 {
114 return (A == aSeg.A && B == aSeg.B) ;
115 }
116
117 bool operator!=( const SEG& aSeg ) const
118 {
119 return (A != aSeg.A || B != aSeg.B);
120 }
121
122 static SEG::ecoord Square( int a )
123 {
124 return ecoord( a ) * a;
125 }
126
134 VECTOR2I LineProject( const VECTOR2I& aP ) const;
135
142 int Side( const VECTOR2I& aP ) const
143 {
144 const ecoord det = ( B - A ).Cross( aP - A );
145
146 return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
147 }
148
158 int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;
159
166 double AngleDegrees( const SEG& aOther ) const;
167
173 const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
174
180 const VECTOR2I NearestPoint( const SEG &aSeg ) const;
181
187 const VECTOR2I ReflectPoint( const VECTOR2I& aP ) const;
188
198 OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
199 bool aLines = false ) const;
200
201 bool Intersects( const SEG& aSeg ) const;
202
209 OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
210 {
211 return Intersect( aSeg, false, true );
212 }
213
220 SEG PerpendicularSeg( const VECTOR2I& aP ) const;
221
228 SEG ParallelSeg( const VECTOR2I& aP ) const;
229
230 bool Collide( const SEG& aSeg, int aClearance, int* aActual = nullptr ) const;
231
232 ecoord SquaredDistance( const SEG& aSeg ) const;
233
240 int Distance( const SEG& aSeg ) const;
241
242 ecoord SquaredDistance( const VECTOR2I& aP ) const
243 {
244 return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
245 }
246
253 int Distance( const VECTOR2I& aP ) const;
254
255 void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
256 {
257 qA = ecoord{ A.y } - B.y;
258 qB = ecoord{ B.x } - A.x;
259 qC = -qA * A.x - qB * A.y;
260 }
261
268 bool Collinear( const SEG& aSeg ) const
269 {
270 ecoord qa, qb, qc;
271 CanonicalCoefs( qa, qb, qc );
272
273 ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
274 ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );
275
276 return ( d1 <= 1 && d2 <= 1 );
277 }
278
279 bool ApproxCollinear( const SEG& aSeg ) const
280 {
281 ecoord p, q, r;
282 CanonicalCoefs( p, q, r );
283
284 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
285 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
286
287 return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
288 }
289
290 bool ApproxParallel( const SEG& aSeg, int aDistanceThreshold = 1 ) const
291 {
292 ecoord p, q, r;
293 CanonicalCoefs( p, q, r );
294
295 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
296 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );
297
298 return std::abs( dist1 - dist2 ) <= aDistanceThreshold;
299 }
300
301 bool ApproxPerpendicular( const SEG& aSeg ) const
302 {
303 SEG perp = PerpendicularSeg( A );
304
305 return aSeg.ApproxParallel( perp );
306 }
307
308 bool Overlaps( const SEG& aSeg ) const
309 {
310 if( aSeg.A == aSeg.B ) // single point corner case
311 {
312 if( A == aSeg.A || B == aSeg.A )
313 return false;
314
315 return Contains( aSeg.A );
316 }
317
318 if( !Collinear( aSeg ) )
319 return false;
320
321 if( Contains( aSeg.A ) || Contains( aSeg.B ) )
322 return true;
323
324 if( aSeg.Contains( A ) || aSeg.Contains( B ) )
325 return true;
326
327 return false;
328 }
329
330
331 bool Contains( const SEG& aSeg ) const
332 {
333 if( aSeg.A == aSeg.B ) // single point corner case
334 return Contains( aSeg.A );
335
336 if( !Collinear( aSeg ) )
337 return false;
338
339 if( Contains( aSeg.A ) && Contains( aSeg.B ) )
340 return true;
341
342 return false;
343 }
344
350 int Length() const
351 {
352 return ( A - B ).EuclideanNorm();
353 }
354
355 ecoord SquaredLength() const
356 {
357 return ( A - B ).SquaredEuclideanNorm();
358 }
359
360 ecoord TCoef( const VECTOR2I& aP ) const;
361
368 int Index() const
369 {
370 return m_index;
371 }
372
373 bool Contains( const VECTOR2I& aP ) const;
374
375 void Reverse()
376 {
377 std::swap( A, B );
378 }
379
380 SEG Reversed() const
381 {
382 return SEG( B, A );
383 }
384
386 VECTOR2I Center() const
387 {
388 return A + ( B - A ) / 2;
389 }
390
391private:
392 bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;
393
394 bool intersects( const SEG& aSeg, bool aIgnoreEndpoints = false, bool aLines = false,
395 VECTOR2I* aPt = nullptr ) const;
396
397private:
399 int m_index;
400};
401
402inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
403{
404 VECTOR2I d = B - A;
405 return d.Dot( aP - A);
406}
407
408inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
409{
410 aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";
411
412 return aStream;
413}
414
415#endif // __SEG_H
Definition seg.h:41
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition seg.cpp:249
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:297
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:86
int Index() const
Return the index of this segment in its parent shape (applicable only to non-local segments).
Definition seg.h:368
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Compute a point on the segment (this) that is closest to point aP.
Definition seg.cpp:227
int Length() const
Return the length (this).
Definition seg.h:350
SEG(int aX1, int aY1, int aX2, int aY2)
Create a segment between (aX1, aY1) and (aX2, aY2).
Definition seg.h:62
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:154
SEG()
Create an empty (0, 0) segment.
Definition seg.h:54
bool Collinear(const SEG &aSeg) const
Check if segment aSeg lies on the same line as (this).
Definition seg.h:268
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition seg.cpp:174
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition seg.h:209
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition seg.cpp:285
double AngleDegrees(const SEG &aOther) const
Determine the smallest angle between two segments (result in degrees)
Definition seg.cpp:61
SEG(const SEG &aSeg)
Copy constructor.
Definition seg.h:96
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:268
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition seg.cpp:165
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition seg.h:142
SEG(const VECTOR2I &aA, const VECTOR2I &aB)
Create a segment between (aA) and (aB).
Definition seg.h:72
SEG Reversed() const
Returns the center point of the line.
Definition seg.h:380
extended_type Dot(const VECTOR2< T > &aVector) const
Compute dot product of self with aVector.
Definition vector2d.h:515