KiCad PCB EDA Suite
shape_line_chain.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  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
25 #ifndef __SHAPE_LINE_CHAIN
26 #define __SHAPE_LINE_CHAIN
27 
28 #include <vector>
29 #include <sstream>
30 
31 #include <boost/optional.hpp>
32 
33 #include <math/vector2d.h>
34 #include <geometry/shape.h>
35 #include <geometry/seg.h>
36 
46 class SHAPE_LINE_CHAIN : public SHAPE
47 {
48 private:
49  typedef std::vector<VECTOR2I>::iterator point_iter;
50  typedef std::vector<VECTOR2I>::const_iterator point_citer;
51 
52 public:
58  struct INTERSECTION
59  {
66  };
67 
68  typedef std::vector<INTERSECTION> INTERSECTIONS;
69 
75  SHAPE( SH_LINE_CHAIN ), m_closed( false )
76  {}
77 
82  SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed )
83  {}
84 
89  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) :
90  SHAPE( SH_LINE_CHAIN ), m_closed( false )
91  {
92  m_points.resize( 2 );
93  m_points[0] = aA;
94  m_points[1] = aB;
95  }
96 
97  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) :
98  SHAPE( SH_LINE_CHAIN ), m_closed( false )
99  {
100  m_points.resize( 3 );
101  m_points[0] = aA;
102  m_points[1] = aB;
103  m_points[2] = aC;
104  }
105 
106  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) :
107  SHAPE( SH_LINE_CHAIN ), m_closed( false )
108  {
109  m_points.resize( 4 );
110  m_points[0] = aA;
111  m_points[1] = aB;
112  m_points[2] = aC;
113  m_points[3] = aD;
114  }
115 
116 
117  SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) :
118  SHAPE( SH_LINE_CHAIN ),
119  m_closed( false )
120  {
121  m_points.resize( aCount );
122 
123  for( int i = 0; i < aCount; i++ )
124  m_points[i] = *aV++;
125  }
126 
128  {}
129 
130  SHAPE* Clone() const override;
131 
136  void Clear()
137  {
138  m_points.clear();
139  m_closed = false;
140  }
141 
149  void SetClosed( bool aClosed )
150  {
151  m_closed = aClosed;
152  }
153 
159  bool IsClosed() const
160  {
161  return m_closed;
162  }
163 
170  int SegmentCount() const
171  {
172  int c = m_points.size() - 1;
173  if( m_closed )
174  c++;
175 
176  return std::max( 0, c );
177  }
178 
185  int PointCount() const
186  {
187  return m_points.size();
188  }
189 
199  SEG Segment( int aIndex )
200  {
201  if( aIndex < 0 )
202  aIndex += SegmentCount();
203 
204  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
205  return SEG( m_points[aIndex], m_points[0], aIndex );
206  else
207  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
208  }
209 
218  const SEG CSegment( int aIndex ) const
219  {
220  if( aIndex < 0 )
221  aIndex += SegmentCount();
222 
223  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
224  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
225  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
226  else
227  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
228  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
229  }
230 
238  VECTOR2I& Point( int aIndex )
239  {
240  if( aIndex < 0 )
241  aIndex += PointCount();
242 
243  return m_points[aIndex];
244  }
245 
253  const VECTOR2I& CPoint( int aIndex ) const
254  {
255  if( aIndex < 0 )
256  aIndex += PointCount();
257  else if( aIndex >= PointCount() )
258  aIndex -= PointCount();
259 
260  return m_points[aIndex];
261  }
262 
264  const BOX2I BBox( int aClearance = 0 ) const override
265  {
266  BOX2I bbox;
267  bbox.Compute( m_points );
268 
269  if( aClearance != 0 )
270  bbox.Inflate( aClearance );
271 
272  return bbox;
273  }
274 
283  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
284 
293  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
294 
302  int Distance( const VECTOR2I& aP ) const;
303 
310  const SHAPE_LINE_CHAIN Reverse() const;
311 
318  int Length() const;
319 
327  void Append( int aX, int aY, bool aAllowDuplication = false )
328  {
329  VECTOR2I v( aX, aY );
330  Append( v, aAllowDuplication );
331  }
332 
339  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
340  {
341  if( m_points.size() == 0 )
342  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
343 
344  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
345  {
346  m_points.push_back( aP );
347  m_bbox.Merge( aP );
348  }
349  }
350 
357  void Append( const SHAPE_LINE_CHAIN& aOtherLine )
358  {
359  if( aOtherLine.PointCount() == 0 )
360  return;
361 
362  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
363  {
364  const VECTOR2I p = aOtherLine.CPoint( 0 );
365  m_points.push_back( p );
366  m_bbox.Merge( p );
367  }
368 
369  for( int i = 1; i < aOtherLine.PointCount(); i++ )
370  {
371  const VECTOR2I p = aOtherLine.CPoint( i );
372  m_points.push_back( p );
373  m_bbox.Merge( p );
374  }
375  }
376 
377  void Insert( int aVertex, const VECTOR2I& aP )
378  {
379  m_points.insert( m_points.begin() + aVertex, aP );
380  }
381 
391  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
392 
402  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
403 
411  void Remove( int aStartIndex, int aEndIndex );
412 
418  void Remove( int aIndex )
419  {
420  Remove( aIndex, aIndex );
421  }
422 
432  int Split( const VECTOR2I& aP );
433 
441  int Find( const VECTOR2I& aP ) const;
442 
450  int FindSegment( const VECTOR2I& aP ) const;
451 
460  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
461 
463  {
464  compareOriginDistance( const VECTOR2I& aOrigin ):
465  m_origin( aOrigin )
466  {}
467 
468  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
469  {
470  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
471  }
472 
474  };
475 
476  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
477 
487  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
488 
498  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
499 
508  int PathLength( const VECTOR2I& aP ) const;
509 
518  bool PointInside( const VECTOR2I& aP ) const;
519 
527  bool PointOnEdge( const VECTOR2I& aP ) const;
528 
536 
544 
551  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
552 
562  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
563 
565  const std::string Format() const override;
566 
568  bool Parse( std::stringstream& aStream ) override;
569 
570  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
571  {
572  if( PointCount() != aRhs.PointCount() )
573  return true;
574 
575  for( int i = 0; i < PointCount(); i++ )
576  {
577  if( CPoint( i ) != aRhs.CPoint( i ) )
578  return true;
579  }
580 
581  return false;
582  }
583 
584  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
585 
586  void Move( const VECTOR2I& aVector ) override
587  {
588  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
589  (*i) += aVector;
590  }
591 
592  bool IsSolid() const override
593  {
594  return false;
595  }
596 
597  const VECTOR2I PointAlong( int aPathLength ) const;
598 
599 private:
601  std::vector<VECTOR2I> m_points;
602 
604  bool m_closed;
605 
608 };
609 
610 #endif // __SHAPE_LINE_CHAIN
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:104
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
BOX2I m_bbox
cached bounding box
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
compareOriginDistance(const VECTOR2I &aOrigin)
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Function Append()
int Split(const VECTOR2I &aP)
Function Split()
BOX2< VECTOR2I > BOX2I
Definition: box2.h:468
std::vector< INTERSECTION > INTERSECTIONS
void Insert(int aVertex, const VECTOR2I &aP)
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
bool operator!=(const SHAPE_LINE_CHAIN &aRhs) const
int PointCount() const
Function PointCount()
SHAPE_LINE_CHAIN(const SHAPE_LINE_CHAIN &aShape)
Copy Constructor.
VECTOR2I p
point of intersection between our and their.
void Move(const VECTOR2I &aVector) override
static const int dist[10][10]
Definition: dist.cpp:57
std::vector< VECTOR2I >::const_iterator point_citer
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:79
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
SHAPE_LINE_CHAIN(const VECTOR2I *aV, int aCount)
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
SHAPE_LINE_CHAIN(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Initializes a 2-point line chain (a single segment)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
bool operator()(const INTERSECTION &aA, const INTERSECTION &aB)
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
const boost::optional< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
bool Parse(std::stringstream &aStream) override
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
int Find(const VECTOR2I &aP) const
Function Find()
bool m_closed
is the line chain closed?
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
SEG their
segment belonging from the aOther argument of Intersect()
const VECTOR2I PointAlong(int aPathLength) const
const BOX2I BBox(int aClearance=0) const override
Function BBox()
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
std::vector< VECTOR2I > m_points
array of vertices
SHAPE_LINE_CHAIN(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC)
bool IsSolid() const override
Class SHAPE.
Definition: shape.h:57
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h:350
const std::string Format() const override
void Remove(int aIndex)
Function Remove() removes the aIndex-th point from the line chain.
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
Definition: seg.h:37
int Distance(const VECTOR2I &aP) const
Function Distance()
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
int PathLength(const VECTOR2I &aP) const
Function PathLength()
SEG Segment(int aIndex)
Function Segment()
#define max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
SHAPE_LINE_CHAIN(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC, const VECTOR2I &aD)
line segment
Definition: shape.h:45
bool IsClosed() const
Function IsClosed()
void Clear()
Function Clear() Removes all points from the line chain.
SHAPE * Clone() const override
Function Clone()
VECTOR2I & Point(int aIndex)
Function Point()
void Append(const SHAPE_LINE_CHAIN &aOtherLine)
Function Append()
std::vector< VECTOR2I >::iterator point_iter
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
SEG our
segment belonging from the (this) argument of Intersect()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int SegmentCount() const
Function SegmentCount()
int Length() const
Function Length()