diff options
Diffstat (limited to 'include/geometry/seg.h')
| -rw-r--r-- | include/geometry/seg.h | 384 |
1 files changed, 384 insertions, 0 deletions
diff --git a/include/geometry/seg.h b/include/geometry/seg.h new file mode 100644 index 0000000..164457b --- /dev/null +++ b/include/geometry/seg.h @@ -0,0 +1,384 @@ +/* + * This program source code file is part of KiCad, a free EDA CAD application. + * + * Copyright (C) 2013 CERN + * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch> + * + * 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 <cstdio> +#include <climits> + +#include <math/vector2d.h> + +#include <boost/optional/optional.hpp> + +typedef boost::optional<VECTOR2I> OPT_VECTOR2I; + +class SEG +{ +private: + typedef VECTOR2I::extended_type ecoord; + +public: + friend inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg ); + + /* Start and the of the segment. Public, to make access simpler. These are references + * to an object the segment belongs to (e.g. a line chain) or references to locally stored + * points (m_a, m_b). + */ + VECTOR2I A; + VECTOR2I B; + + /** Default constructor + * Creates an empty (0, 0) segment, locally-referenced + */ + SEG() + { + m_index = -1; + } + + /** + * Constructor + * Creates a segment between (aX1, aY1) and (aX2, aY2), locally referenced + */ + SEG( int aX1, int aY1, int aX2, int aY2 ) : + A ( VECTOR2I( aX1, aY1 ) ), + B ( VECTOR2I( aX2, aY2 ) ) + { + m_index = -1; + } + + /** + * Constructor + * Creates a segment between (aA) and (aB), locally referenced + */ + SEG( const VECTOR2I& aA, const VECTOR2I& aB ) : A( aA ), B( aB ) + { + m_index = -1; + } + + /** + * Constructor + * Creates a segment between (aA) and (aB), referenced to a multi-segment shape + * @param aA reference to the start point in the parent shape + * @param aB reference to the end point in the parent shape + * @param aIndex index of the segment within the parent shape + */ + SEG( const VECTOR2I& aA, const VECTOR2I& aB, int aIndex ) : A( aA ), B( aB ) + { + m_index = aIndex; + } + + /** + * Copy constructor + */ + 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; + } + + /** + * Function LineProject() + * + * Computes the perpendicular projection point of aP on a line passing through + * ends of the segment. + * @param aP point to project + * @return projected point + */ + VECTOR2I LineProject( const VECTOR2I& aP ) const; + + /** + * Function Side() + * + * Determines on which side of directed line passing via segment ends point aP lies. + * @param aP point to determine the orientation wrs to self + * @return: < 0: left, 0 : on the line, > 0 : right + */ + int Side( const VECTOR2I& aP ) const + { + const ecoord det = ( B - A ).Cross( aP - A ); + + return det < 0 ? -1 : ( det > 0 ? 1 : 0 ); + } + + /** + * Function LineDistance() + * + * Returns the closest Euclidean distance between point aP and the line defined by + * the ends of segment (this). + * @param aDetermineSide: when true, the sign of the returned value indicates + * the side of the line at which we are (negative = left) + * @return the distance + */ + int LineDistance( const VECTOR2I& aP, bool aDetermineSide = false ) const; + + /** + * Function NearestPoint() + * + * Computes a point on the segment (this) that is closest to point aP. + * @return: nearest point + */ + const VECTOR2I NearestPoint( const VECTOR2I &aP ) const; + + /** + * Function Intersect() + * + * Computes intersection point of segment (this) with segment aSeg. + * @param aSeg: segment to intersect with + * @param aIgnoreEndpoints: don't treat corner cases (i.e. end of one segment touching the + * other) as intersections. + * @param aLines: treat segments as infinite lines + * @return intersection point, if exists + */ + OPT_VECTOR2I Intersect( const SEG& aSeg, bool aIgnoreEndpoints = false, + bool aLines = false ) const; + + /** + * Function IntersectLines() + * + * Computes the intersection point of lines passing through ends of (this) and aSeg + * @param aSeg segment defining the line to intersect with + * @return intersection point, if exists + */ + OPT_VECTOR2I IntersectLines( const SEG& aSeg ) const + { + return Intersect( aSeg, false, true ); + } + + bool Collide( const SEG& aSeg, int aClearance ) const; + + ecoord SquaredDistance( const SEG& aSeg ) const; + + /** + * Function Distance() + * + * Computes minimum Euclidean distance to segment aSeg. + * @param aSeg other segment + * @return minimum distance + */ + int Distance( const SEG& aSeg ) const + { + return sqrt( SquaredDistance( aSeg ) ); + } + + ecoord SquaredDistance( const VECTOR2I& aP ) const + { + return ( NearestPoint( aP ) - aP ).SquaredEuclideanNorm(); + } + + /** + * Function Distance() + * + * Computes minimum Euclidean distance to point aP. + * @param aP the point + * @return minimum distance + */ + int Distance( const VECTOR2I& aP ) const + { + return sqrt( SquaredDistance( aP ) ); + } + + void CanonicalCoefs( ecoord& qA, ecoord& qB, ecoord& qC ) const + { + qA = A.y - B.y; + qB = B.x - A.x; + qC = -qA * A.x - qB * A.y; + } + + /** + * Function Collinear() + * + * Checks if segment aSeg lies on the same line as (this). + * @param aSeg the segment to chech colinearity with + * @return true, when segments are collinear. + */ + 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 ) 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 ) <= 1; + } + + + 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; + } + + /** + * Function Length() + * + * Returns the length (this) + * @return length + */ + int Length() const + { + return ( A - B ).EuclideanNorm(); + } + + ecoord SquaredLength() const + { + return ( A - B ).SquaredEuclideanNorm(); + } + + ecoord TCoef( const VECTOR2I& aP ) const; + + /** + * Function Index() + * + * Return the index of this segment in its parent shape (applicable only to non-local segments) + * @return index value + */ + int Index() const + { + return m_index; + } + + bool Contains( const VECTOR2I& aP ) const; + + bool PointCloserThan( const VECTOR2I& aP, int aDist ) const; + + void Reverse() + { + std::swap( A, B ); + } + +private: + bool ccw( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I &aC ) const; + + ///> index withing the parent shape (used when m_is_local == false) + int m_index; +}; + +inline VECTOR2I SEG::LineProject( const VECTOR2I& aP ) const +{ + VECTOR2I d = B - A; + ecoord l_squared = d.Dot( d ); + + if( l_squared == 0 ) + return A; + + ecoord t = d.Dot( aP - A ); + + int xp = rescale( t, (ecoord)d.x, l_squared ); + int yp = rescale( t, (ecoord)d.y, l_squared ); + + return A + VECTOR2I( xp, yp ); +} + +inline int SEG::LineDistance( const VECTOR2I& aP, bool aDetermineSide ) const +{ + ecoord p = A.y - B.y; + ecoord q = B.x - A.x; + ecoord r = -p * A.x - q * A.y; + + ecoord dist = ( p * aP.x + q * aP.y + r ) / sqrt( p * p + q * q ); + + return aDetermineSide ? dist : std::abs( dist ); +} + +inline SEG::ecoord SEG::TCoef( const VECTOR2I& aP ) const +{ + VECTOR2I d = B - A; + return d.Dot( aP - A); +} + +inline const VECTOR2I SEG::NearestPoint( const VECTOR2I& aP ) const +{ + VECTOR2I d = B - A; + ecoord l_squared = d.Dot( d ); + + if( l_squared == 0 ) + return A; + + ecoord t = d.Dot( aP - A ); + + if( t < 0 ) + return A; + else if( t > l_squared ) + return B; + + int xp = rescale( t, (ecoord)d.x, l_squared ); + int yp = rescale( t, (ecoord)d.y, l_squared ); + + return A + VECTOR2I( xp, yp ); +} + +inline std::ostream& operator<<( std::ostream& aStream, const SEG& aSeg ) +{ + aStream << "[ " << aSeg.A << " - " << aSeg.B << " ]"; + + return aStream; +} + +#endif // __SEG_H |