seg.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright (C) 2013 CERN
 * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
 *
 * @author Tomasz Wlostowski <[email protected]>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, you may find one here:
 * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
 * or you may search the http://www.gnu.org website for the version 2 license,
 * or you may write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */

#ifndef __SEG_H
#define __SEG_H

#include <math.h> // for sqrt
#include <stdlib.h> // for abs
#include <ostream> // for operator<<, ostream, basic_os...
#include <type_traits> // for swap

#include <core/optional.h>
#include <math/vector2d.h>

typedef OPT<VECTOR2I> OPT_VECTOR2I;

class SEG
{
public:
 using ecoord = VECTOR2I::extended_type;
 friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg );

 /* Start and the of the segment. Public, to make access simpler.
 */
 VECTOR2I A;
 VECTOR2I B;

 SEG()
 {
 m_index = -1;
 }

 SEG( int aX1, int aY1, int aX2, int aY2 ) :
 A( VECTOR2I( aX1, aY1 ) ),
 B( VECTOR2I( aX2, aY2 ) )
 {
 m_index = -1;
 }

 SEG( const VECTOR2I& aA, const VECTOR2I& aB ) :
 A( aA ),
 B( aB )
 {
 m_index = -1;
 }

 SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) :
 A( aA ),
 B( aB )
 {
 m_index = aIndex;
 }

 SEG( const SEG& aSeg ) :
 A( aSeg.A ),
 B( aSeg.B ),
 m_index( aSeg.m_index )
 {
 }

 SEG& operator=( const SEG& aSeg )
 {
 A = aSeg.A;
 B = aSeg.B;
 m_index = aSeg.m_index;

 return *this;
 }

 bool operator==( const SEG& aSeg ) const
 {
 return (A == aSeg.A && B == aSeg.B) ;
 }

 bool operator!=( const SEG& aSeg ) const
 {
 return (A != aSeg.A || B != aSeg.B);
 }

 static SEG::ecoord Square( int a )
 {
 return ecoord( a ) * a;
 }

 VECTOR2I LineProject( const VECTOR2I& aP ) const;

 int Side( const VECTOR2I& aP ) const
 {
 const ecoord det = ( B - A ).Cross( aP - A );

 return det < 0 ? -1 : ( det > 0 ? 1 : 0 );
 }

 int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const;

 double AngleDegrees( const SEG& aOther ) const;

 const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;

 const VECTOR2I NearestPoint( const SEG &aSeg ) const;

 const VECTOR2I ReflectPoint( const VECTOR2I& aP ) const;

 OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false,
 bool aLines = false ) const;

 bool Intersects( const SEG& aSeg ) const;

 OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const
 {
 return Intersect( aSeg, false, true );
 }

 SEG PerpendicularSeg( const VECTOR2I& aP ) const;

 SEG ParallelSeg( const VECTOR2I& aP ) const;

 bool Collide( const SEG& aSeg, int aClearance, int* aActual = nullptr ) const;

 ecoord SquaredDistance( const SEG& aSeg ) const;

 int Distance( const SEG& aSeg ) const;

 ecoord SquaredDistance( const VECTOR2I& aP ) const
 {
 return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm();
 }

 int Distance( const VECTOR2I& aP ) const;

 void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const
 {
 qA = ecoord{ A.y } - B.y;
 qB = ecoord{ B.x } - A.x;
 qC = -qA * A.x - qB * A.y;
 }

 bool Collinear( const SEG& aSeg ) const
 {
 ecoord qa, qb, qc;
 CanonicalCoefs( qa, qb, qc );

 ecoord d1 = std::abs( aSeg.A.x * qa + aSeg.A.y * qb + qc );
 ecoord d2 = std::abs( aSeg.B.x * qa + aSeg.B.y * qb + qc );

 return ( d1 <= 1 && d2 <= 1 );
 }

 bool ApproxCollinear( const SEG& aSeg ) const
 {
 ecoord p, q, r;
 CanonicalCoefs( p, q, r );

 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );

 return std::abs( dist1 ) <= 1 && std::abs( dist2 ) <= 1;
 }

 bool ApproxParallel( const SEG& aSeg, int aDistanceThreshold = 1 ) const
 {
 ecoord p, q, r;
 CanonicalCoefs( p, q, r );

 ecoord dist1 = ( p * aSeg.A.x + q * aSeg.A.y + r ) / sqrt( p * p + q * q );
 ecoord dist2 = ( p * aSeg.B.x + q * aSeg.B.y + r ) / sqrt( p * p + q * q );

 return std::abs( dist1 - dist2 ) <= aDistanceThreshold;
 }

 bool ApproxPerpendicular( const SEG& aSeg ) const
 {
 SEG perp = PerpendicularSeg( A );

 return aSeg.ApproxParallel( perp );
 }

 bool Overlaps( const SEG& aSeg ) const
 {
 if( aSeg.A == aSeg.B ) // single point corner case
 {
 if( A == aSeg.A || B == aSeg.A )
 return false;

 return Contains( aSeg.A );
 }

 if( !Collinear( aSeg ) )
 return false;

 if( Contains( aSeg.A ) || Contains( aSeg.B ) )
 return true;

 if( aSeg.Contains( A ) || aSeg.Contains( B ) )
 return true;

 return false;
 }


 bool Contains( const SEG& aSeg ) const
 {
 if( aSeg.A == aSeg.B ) // single point corner case
 return Contains( aSeg.A );

 if( !Collinear( aSeg ) )
 return false;

 if( Contains( aSeg.A ) && Contains( aSeg.B ) )
 return true;

 return false;
 }

 int Length() const
 {
 return ( A - B ).EuclideanNorm();
 }

 ecoord SquaredLength() const
 {
 return ( A - B ).SquaredEuclideanNorm();
 }

 ecoord TCoef( const VECTOR2I& aP ) const;

 int Index() const
 {
 return m_index;
 }

 bool Contains( const VECTOR2I& aP ) const;

 void Reverse()
 {
 std::swap( A, B );
 }

 SEG Reversed() const
 {
 return SEG( B, A );
 }

 VECTOR2I Center() const
 {
 return A + ( B - A ) / 2;
 }

private:
 bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const;

 bool intersects( const SEG& aSeg, bool aIgnoreEndpoints = false, bool aLines = false,
 VECTOR2I* aPt = nullptr ) const;

private:
 int m_index;
};

inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const
{
 VECTOR2I d = B - A;
 return d.Dot( aP - A);
}

inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg )
{
 aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]";

 return aStream;
}

#endif // __SEG_H