Merge pull request #3 from saurabhb17/master

secondary files

1 files changed, 598 insertions, 0 deletions

diff --git a/include/geometry/shape_line_chain.h b/include/geometry/shape_line_chain.h
new file mode 100644
index 0000000..ae2bf5e
--- /dev/null
+++ b/include/geometry/shape_line_chain.h
@@ -0,0 +1,598 @@
+/*
+ * 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 __SHAPE_LINE_CHAIN
+#define __SHAPE_LINE_CHAIN
+
+#include <vector>
+#include <sstream>
+
+#include <boost/optional.hpp>
+
+#include <math/vector2d.h>
+#include <geometry/shape.h>
+#include <geometry/seg.h>
+
+/**
+ * Class SHAPE_LINE_CHAIN
+ *
+ * Represents a polyline (an zero-thickness chain of connected line segments).
+ * I purposedly didn't name it "polyline" to avoid confusion with the existing CPolyLine
+ * class in pcbnew.
+ *
+ * SHAPE_LINE_CHAIN class shall not be used for polygons!
+ */
+class SHAPE_LINE_CHAIN : public SHAPE
+{
+private:
+    typedef std::vector<VECTOR2I>::iterator point_iter;
+    typedef std::vector<VECTOR2I>::const_iterator point_citer;
+
+public:
+    /**
+     * Struct INTERSECTION
+     *
+     * Represents an intersection between two line segments
+     */
+    struct INTERSECTION
+    {
+        /// segment belonging from the (this) argument of Intersect()
+        SEG our;
+        /// segment belonging from the aOther argument of Intersect()
+        SEG their;
+        /// point of intersection between our and their.
+        VECTOR2I p;
+    };
+
+    typedef std::vector<INTERSECTION> INTERSECTIONS;
+
+    /**
+     * Constructor
+     * Initializes an empty line chain.
+     */
+    SHAPE_LINE_CHAIN() :
+        SHAPE( SH_LINE_CHAIN ), m_closed( false )
+    {}
+
+    /**
+     * Copy Constructor
+     */
+    SHAPE_LINE_CHAIN( const SHAPE_LINE_CHAIN& aShape ) :
+        SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed )
+    {}
+
+    /**
+     * Constructor
+     * Initializes a 2-point line chain (a single segment)
+     */
+    SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) :
+        SHAPE( SH_LINE_CHAIN ), m_closed( false )
+    {
+        m_points.resize( 2 );
+        m_points[0] = aA;
+        m_points[1] = aB;
+    }
+
+    SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) :
+        SHAPE( SH_LINE_CHAIN ), m_closed( false )
+    {
+        m_points.resize( 3 );
+        m_points[0] = aA;
+        m_points[1] = aB;
+        m_points[2] = aC;
+    }
+
+    SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) :
+        SHAPE( SH_LINE_CHAIN ), m_closed( false )
+    {
+        m_points.resize( 4 );
+        m_points[0] = aA;
+        m_points[1] = aB;
+        m_points[2] = aC;
+        m_points[3] = aD;
+    }
+
+
+    SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) :
+        SHAPE( SH_LINE_CHAIN ),
+        m_closed( false )
+    {
+        m_points.resize( aCount );
+
+        for( int i = 0; i < aCount; i++ )
+            m_points[i] = *aV++;
+    }
+
+    ~SHAPE_LINE_CHAIN()
+    {}
+
+    SHAPE* Clone() const;
+
+    /**
+     * Function Clear()
+     * Removes all points from the line chain.
+     */
+    void Clear()
+    {
+        m_points.clear();
+        m_closed = false;
+    }
+
+    /**
+     * Function SetClosed()
+     *
+     * Marks the line chain as closed (i.e. with a segment connecting the last point with
+     * the first point).
+     * @param aClosed: whether the line chain is to be closed or not.
+     */
+    void SetClosed( bool aClosed )
+    {
+        m_closed = aClosed;
+    }
+
+    /**
+     * Function IsClosed()
+     *
+     * @return aClosed: true, when our line is closed.
+     */
+    bool IsClosed() const
+    {
+        return m_closed;
+    }
+
+    /**
+     * Function SegmentCount()
+     *
+     * Returns number of segments in this line chain.
+     * @return number of segments
+     */
+    int SegmentCount() const
+    {
+        int c = m_points.size() - 1;
+        if( m_closed )
+            c++;
+
+        return std::max( 0, c );
+    }
+
+    /**
+     * Function PointCount()
+     *
+     * Returns the number of points (vertices) in this line chain
+     * @return number of points
+     */
+    int PointCount() const
+    {
+        return m_points.size();
+    }
+
+    /**
+     * Function Segment()
+     *
+     * Returns a segment referencing to the segment (index) in the line chain.
+     * Modifying ends of the returned segment will modify corresponding points in the line chain.
+     * @param aIndex: index of the segment in the line chain. Negative values are counted from
+     * the end (i.e. -1 means the last segment in the line chain)
+     * @return SEG referenced to given segment in the line chain
+     */
+    SEG Segment( int aIndex )
+    {
+        if( aIndex < 0 )
+            aIndex += SegmentCount();
+
+        if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
+            return SEG( m_points[aIndex], m_points[0], aIndex );
+        else
+            return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
+    }
+
+    /**
+     * Function CSegment()
+     *
+     * Returns a read-only segment referencing to the segment (index) in the line chain.
+     * @param aIndex: index of the segment in the line chain. Negative values are counted from
+     * the end (i.e. -1 means the last segment in the line chain)
+     * @return SEG referenced to given segment in the line chain
+     */
+    const SEG CSegment( int aIndex ) const
+    {
+        if( aIndex < 0 )
+            aIndex += SegmentCount();
+
+        if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
+            return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
+                        const_cast<VECTOR2I&>( m_points[0] ), aIndex );
+        else
+            return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
+                        const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
+    }
+
+    /**
+     * Function Point()
+     *
+     * Returns a reference to a given point in the line chain.
+     * @param aIndex index of the point
+     * @return reference to the point
+     */
+    VECTOR2I& Point( int aIndex )
+    {
+        if( aIndex < 0 )
+            aIndex += PointCount();
+
+        return m_points[aIndex];
+    }
+
+    /**
+     * Function CPoint()
+     *
+     * Returns a const reference to a given point in the line chain.
+     * @param aIndex index of the point
+     * @return const reference to the point
+     */
+    const VECTOR2I& CPoint( int aIndex ) const
+    {
+        if( aIndex < 0 )
+            aIndex += PointCount();
+        else if( aIndex >= PointCount() )
+            aIndex -= PointCount();
+
+        return m_points[aIndex];
+    }
+
+    /// @copydoc SHAPE::BBox()
+    const BOX2I BBox( int aClearance = 0 ) const
+    {
+        BOX2I bbox;
+        bbox.Compute( m_points );
+
+        if( aClearance != 0 )
+            bbox.Inflate( aClearance );
+
+        return bbox;
+    }
+
+    /**
+     * Function Collide()
+     *
+     * Checks if point aP lies closer to us than aClearance.
+     * @param aP the point to check for collisions with
+     * @param aClearance minimum distance that does not qualify as a collision.
+     * @return true, when a collision has been found
+     */
+    bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const;
+
+    /**
+     * Function Collide()
+     *
+     * Checks if segment aSeg lies closer to us than aClearance.
+     * @param aSeg the segment to check for collisions with
+     * @param aClearance minimum distance that does not qualify as a collision.
+     * @return true, when a collision has been found
+     */
+    bool Collide( const SEG& aSeg, int aClearance = 0 ) const;
+
+    /**
+     * Function Distance()
+     *
+     * Computes the minimum distance between the line chain and a point aP.
+     * @param aP the point
+     * @return minimum distance.
+     */
+    int Distance( const VECTOR2I& aP ) const;
+
+    /**
+     * Function Reverse()
+     *
+     * Reverses point order in the line chain.
+     * @return line chain with reversed point order (original A-B-C-D: returned D-C-B-A)
+     */
+    const SHAPE_LINE_CHAIN Reverse() const;
+
+    /**
+     * Function Length()
+     *
+     * Returns length of the line chain in Euclidean metric.
+     * @return length of the line chain
+     */
+    int Length() const;
+
+    /**
+     * Function Append()
+     *
+     * Appends a new point at the end of the line chain.
+     * @param aX is X coordinate of the new point
+     * @param aY is Y coordinate of the new point
+     */
+    void Append( int aX, int aY, bool aAllowDuplication = false )
+    {
+        VECTOR2I v( aX, aY );
+        Append( v, aAllowDuplication );
+    }
+
+    /**
+     * Function Append()
+     *
+     * Appends a new point at the end of the line chain.
+     * @param aP the new point
+     */
+    void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
+    {
+        if( m_points.size() == 0 )
+            m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
+
+        if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
+        {
+            m_points.push_back( aP );
+            m_bbox.Merge( aP );
+        }
+    }
+
+    /**
+     * Function Append()
+     *
+     * Appends another line chain at the end.
+     * @param aOtherLine the line chain to be appended.
+     */
+    void Append( const SHAPE_LINE_CHAIN& aOtherLine )
+    {
+        if( aOtherLine.PointCount() == 0 )
+            return;
+
+        else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
+        {
+            const VECTOR2I p = aOtherLine.CPoint( 0 );
+            m_points.push_back( p );
+            m_bbox.Merge( p );
+        }
+
+        for( int i = 1; i < aOtherLine.PointCount(); i++ )
+        {
+            const VECTOR2I p = aOtherLine.CPoint( i );
+            m_points.push_back( p );
+            m_bbox.Merge( p );
+        }
+    }
+
+    void Insert( int aVertex, const VECTOR2I& aP )
+    {
+        m_points.insert( m_points.begin() + aVertex, aP );
+    }
+
+    /**
+     * Function Replace()
+     *
+     * Replaces points with indices in range [start_index, end_index] with a single
+     * point aP.
+     * @param aStartIndex start of the point range to be replaced (inclusive)
+     * @param aEndIndex end of the point range to be replaced (inclusive)
+     * @param aP replacement point
+     */
+    void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
+
+    /**
+     * Function Replace()
+     *
+     * Replaces points with indices in range [start_index, end_index] with the points from
+     * line chain aLine.
+     * @param aStartIndex start of the point range to be replaced (inclusive)
+     * @param aEndIndex end of the point range to be replaced (inclusive)
+     * @param aLine replacement line chain.
+     */
+    void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
+
+    /**
+     * Function Remove()
+     *
+     * Removes the range of points [start_index, end_index] from the line chain.
+     * @param aStartIndex start of the point range to be replaced (inclusive)
+     * @param aEndIndex end of the point range to be replaced (inclusive)
+     */
+    void Remove( int aStartIndex, int aEndIndex );
+
+    /**
+     * Function Split()
+     *
+     * Inserts the point aP belonging to one of the our segments, splitting the adjacent
+     * segment in two.
+     * @param aP the point to be inserted
+     * @return index of the newly inserted point (or a negative value if aP does not lie on
+     * our line)
+     */
+    int Split( const VECTOR2I& aP );
+
+    /**
+     * Function Find()
+     *
+     * Searches for point aP.
+     * @param aP the point to be looked for
+     * @return index of the correspoinding point in the line chain or negative when not found.
+     */
+    int Find( const VECTOR2I& aP ) const;
+
+    /**
+     * Function FindSegment()
+     *
+     * Searches for segment containing point aP.
+     * @param aP the point to be looked for
+     * @return index of the correspoinding segment in the line chain or negative when not found.
+     */
+    int FindSegment( const VECTOR2I& aP ) const;
+
+    /**
+     * Function Slice()
+     *
+     * Returns a subset of this line chain containing the [start_index, end_index] range of points.
+     * @param aStartIndex start of the point range to be returned (inclusive)
+     * @param aEndIndex end of the point range to be returned (inclusive)
+     * @return cut line chain.
+     */
+    const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
+
+    struct compareOriginDistance
+    {
+        compareOriginDistance( const VECTOR2I& aOrigin ):
+            m_origin( aOrigin )
+        {}
+
+        bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
+        {
+            return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
+        }
+
+        VECTOR2I m_origin;
+    };
+
+    bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
+
+    /**
+     * Function Intersect()
+     *
+     * Finds all intersection points between our line chain and the segment aSeg.
+     * @param aSeg the segment chain to find intersections with
+     * @param aIp reference to a vector to store found intersections. Intersection points
+     * are sorted with increasing distances from point aSeg.a.
+     * @return number of intersections found
+     */
+    int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
+
+    /**
+     * Function Intersect()
+     *
+     * Finds all intersection points between our line chain and the line chain aChain.
+     * @param aChain the line chain to find intersections with
+     * @param aIp reference to a vector to store found intersections. Intersection points
+     * are sorted with increasing path lengths from the starting point of aChain.
+     * @return number of intersections found
+     */
+    int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
+
+    /**
+     * Function PathLength()
+     *
+     * Computes the walk path length from the beginning of the line chain and
+     * the point aP belonging to our line.
+     * @return: path length in Euclidean metric or negative if aP does not belong to
+     * the line chain.
+     */
+    int PathLength( const VECTOR2I& aP ) const;
+
+    /**
+     * Function PointInside()
+     *
+     * Checks if point aP lies inside a convex polygon defined by the line chain. For closed
+     * shapes only.
+     * @param aP point to check
+     * @return true if the point is inside the shape (edge is not treated as being inside).
+     */
+     bool PointInside( const VECTOR2I& aP ) const;
+
+    /**
+     * Function PointOnEdge()
+     *
+     * Checks if point aP lies on an edge or vertex of the line chain.
+     * @param aP point to check
+     * @return true if the point lies on the edge.
+     */
+    bool PointOnEdge( const VECTOR2I& aP ) const;
+
+    /**
+     * Function SelfIntersecting()
+     *
+     * Checks if the line chain is self-intersecting.
+     * @return (optional) first found self-intersection point.
+     */
+    const boost::optional<INTERSECTION> SelfIntersecting() const;
+
+    /**
+     * Function Simplify()
+     *
+     * Simplifies the line chain by removing colinear adjacent segments and duplicate vertices.
+     * @return reference to self.
+     */
+    SHAPE_LINE_CHAIN& Simplify();
+
+    /**
+     * Function NearestPoint()
+     *
+     * Finds a point on the line chain that is closest to point aP.
+     * @return the nearest point.
+     */
+    const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
+
+    /**
+     * Function NearestPoint()
+     *
+     * Finds a point on the line chain that is closest to the line defined
+     * by the points of segment aSeg, also returns the distance.
+     * @param aSeg Segment defining the line.
+     * @param dist reference receiving the distance to the nearest point.
+     * @return the nearest point.
+     */
+    const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
+
+    /// @copydoc SHAPE::Format()
+    const std::string Format() const;
+
+    /// @copydoc SHAPE::Parse()
+    bool Parse( std::stringstream& aStream );
+
+    bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
+    {
+        if( PointCount() != aRhs.PointCount() )
+            return true;
+
+        for( int i = 0; i < PointCount(); i++ )
+        {
+            if( CPoint( i ) != aRhs.CPoint( i ) )
+                return true;
+        }
+
+        return false;
+    }
+
+    bool CompareGeometry( const SHAPE_LINE_CHAIN & aOther ) const;
+
+    void Move( const VECTOR2I& aVector )
+    {
+        for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
+            (*i) += aVector;
+    }
+
+    bool IsSolid() const
+    {
+        return false;
+    }
+
+private:
+    /// array of vertices
+    std::vector<VECTOR2I> m_points;
+
+    /// is the line chain closed?
+    bool m_closed;
+
+    /// cached bounding box
+    BOX2I m_bbox;
+};
+
+#endif // __SHAPE_LINE_CHAIN