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  * Copyright (C) 2013-2017
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, you may find one here:
20  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
21  * or you may search the http://www.gnu.org website for the version 2 license,
22  * or you may write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
24  */
25 
26 #ifndef __SHAPE_LINE_CHAIN
27 #define __SHAPE_LINE_CHAIN
28 
29 #include <vector>
30 #include <sstream>
31 
32 #include <core/optional.h>
33 
34 #include <math/vector2d.h>
35 #include <geometry/shape.h>
36 #include <geometry/seg.h>
37 
38 #include <clipper.hpp>
39 
49 class SHAPE_LINE_CHAIN : public SHAPE
50 {
51 private:
52  typedef std::vector<VECTOR2I>::iterator point_iter;
53  typedef std::vector<VECTOR2I>::const_iterator point_citer;
54 
55 public:
61  struct INTERSECTION
62  {
69  };
70 
71  typedef std::vector<INTERSECTION> INTERSECTIONS;
72 
78  SHAPE( SH_LINE_CHAIN ), m_closed( false )
79  {}
80 
85  SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed )
86  {}
87 
92  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) :
93  SHAPE( SH_LINE_CHAIN ), m_closed( false )
94  {
95  m_points.resize( 2 );
96  m_points[0] = aA;
97  m_points[1] = aB;
98  }
99 
100  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) :
101  SHAPE( SH_LINE_CHAIN ), m_closed( false )
102  {
103  m_points.resize( 3 );
104  m_points[0] = aA;
105  m_points[1] = aB;
106  m_points[2] = aC;
107  }
108 
109  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) :
110  SHAPE( SH_LINE_CHAIN ), m_closed( false )
111  {
112  m_points.resize( 4 );
113  m_points[0] = aA;
114  m_points[1] = aB;
115  m_points[2] = aC;
116  m_points[3] = aD;
117  }
118 
119 
120  SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) :
121  SHAPE( SH_LINE_CHAIN ),
122  m_closed( false )
123  {
124  m_points.resize( aCount );
125 
126  for( int i = 0; i < aCount; i++ )
127  m_points[i] = *aV++;
128  }
129 
130  SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath ) :
131  SHAPE( SH_LINE_CHAIN ),
132  m_closed( true )
133  {
134  m_points.reserve( aPath.size() );
135 
136  for( const auto& point : aPath )
137  m_points.emplace_back( point.X, point.Y );
138  }
139 
141  {}
142 
143  SHAPE* Clone() const override;
144 
149  void Clear()
150  {
151  m_points.clear();
152  m_closed = false;
153  }
154 
162  void SetClosed( bool aClosed )
163  {
164  m_closed = aClosed;
165  }
166 
172  bool IsClosed() const
173  {
174  return m_closed;
175  }
176 
183  int SegmentCount() const
184  {
185  int c = m_points.size() - 1;
186  if( m_closed )
187  c++;
188 
189  return std::max( 0, c );
190  }
191 
198  int PointCount() const
199  {
200  return m_points.size();
201  }
202 
211  SEG Segment( int aIndex )
212  {
213  if( aIndex < 0 )
214  aIndex += SegmentCount();
215 
216  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
217  return SEG( m_points[aIndex], m_points[0], aIndex );
218  else
219  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
220  }
221 
230  const SEG CSegment( int aIndex ) const
231  {
232  if( aIndex < 0 )
233  aIndex += SegmentCount();
234 
235  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
236  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
237  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
238  else
239  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
240  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
241  }
242 
250  VECTOR2I& Point( int aIndex )
251  {
252  if( aIndex < 0 )
253  aIndex += PointCount();
254 
255  return m_points[aIndex];
256  }
257 
265  const VECTOR2I& CPoint( int aIndex ) const
266  {
267  if( aIndex < 0 )
268  aIndex += PointCount();
269  else if( aIndex >= PointCount() )
270  aIndex -= PointCount();
271 
272  return m_points[aIndex];
273  }
274 
275  const std::vector<VECTOR2I>& CPoints() const
276  {
277  return m_points;
278  }
279 
284  {
285  return m_points[PointCount() - 1];
286  }
287 
291  const VECTOR2I& CLastPoint() const
292  {
293  return m_points[PointCount() - 1];
294  }
295 
297  const BOX2I BBox( int aClearance = 0 ) const override
298  {
299  BOX2I bbox;
300  bbox.Compute( m_points );
301 
302  if( aClearance != 0 )
303  bbox.Inflate( aClearance );
304 
305  return bbox;
306  }
307 
316  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
317 
326  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
327 
335  int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
336 
343  const SHAPE_LINE_CHAIN Reverse() const;
344 
351  int Length() const;
352 
363  void Append( int aX, int aY, bool aAllowDuplication = false )
364  {
365  VECTOR2I v( aX, aY );
366  Append( v, aAllowDuplication );
367  }
368 
378  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
379  {
380  if( m_points.size() == 0 )
381  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
382 
383  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
384  {
385  m_points.push_back( aP );
386  m_bbox.Merge( aP );
387  }
388  }
389 
396  void Append( const SHAPE_LINE_CHAIN& aOtherLine )
397  {
398  if( aOtherLine.PointCount() == 0 )
399  return;
400 
401  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
402  {
403  const VECTOR2I p = aOtherLine.CPoint( 0 );
404  m_points.push_back( p );
405  m_bbox.Merge( p );
406  }
407 
408  for( int i = 1; i < aOtherLine.PointCount(); i++ )
409  {
410  const VECTOR2I p = aOtherLine.CPoint( i );
411  m_points.push_back( p );
412  m_bbox.Merge( p );
413  }
414  }
415 
416  void Insert( int aVertex, const VECTOR2I& aP )
417  {
418  m_points.insert( m_points.begin() + aVertex, aP );
419  }
420 
430  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
431 
441  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
442 
450  void Remove( int aStartIndex, int aEndIndex );
451 
457  void Remove( int aIndex )
458  {
459  Remove( aIndex, aIndex );
460  }
461 
471  int Split( const VECTOR2I& aP );
472 
480  int Find( const VECTOR2I& aP ) const;
481 
489  int FindSegment( const VECTOR2I& aP ) const;
490 
499  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
500 
502  {
503  compareOriginDistance( const VECTOR2I& aOrigin ):
504  m_origin( aOrigin )
505  {}
506 
507  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
508  {
509  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
510  }
511 
513  };
514 
515  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
516 
526  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
527 
537  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
538 
547  int PathLength( const VECTOR2I& aP ) const;
548 
557  bool PointInside( const VECTOR2I& aP ) const;
558 
566  bool PointOnEdge( const VECTOR2I& aP ) const;
567 
575  int EdgeContainingPoint( const VECTOR2I& aP ) const;
576 
585  bool CheckClearance( const VECTOR2I& aP, const int aDist) const;
586 
593  const OPT<INTERSECTION> SelfIntersecting() const;
594 
602 
608  void convertFromClipper( const ClipperLib::Path& aPath );
609 
614  ClipperLib::Path convertToClipper( bool aRequiredOrientation ) const;
615 
622  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
623 
633  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
634 
636  const std::string Format() const override;
637 
639  bool Parse( std::stringstream& aStream ) override;
640 
641  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
642  {
643  if( PointCount() != aRhs.PointCount() )
644  return true;
645 
646  for( int i = 0; i < PointCount(); i++ )
647  {
648  if( CPoint( i ) != aRhs.CPoint( i ) )
649  return true;
650  }
651 
652  return false;
653  }
654 
655  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
656 
657  void Move( const VECTOR2I& aVector ) override
658  {
659  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
660  (*i) += aVector;
661  }
662 
669  void Rotate( double aAngle, const VECTOR2I& aCenter );
670 
671  bool IsSolid() const override
672  {
673  return false;
674  }
675 
676  const VECTOR2I PointAlong( int aPathLength ) const;
677 
678  double Area() const;
679 
680 private:
682  std::vector<VECTOR2I> m_points;
683 
685  bool m_closed;
686 
689 };
690 
691 #endif // __SHAPE_LINE_CHAIN
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:112
int Find(const VECTOR2I &aP) const
Function Find()
BOX2I m_bbox
cached bounding box
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
compareOriginDistance(const VECTOR2I &aOrigin)
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Function Append()
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
int Split(const VECTOR2I &aP)
Function Split()
BOX2< VECTOR2I > BOX2I
Definition: box2.h:520
bool operator!=(const SHAPE_LINE_CHAIN &aRhs) const
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
void Insert(int aVertex, const VECTOR2I &aP)
static const int dist[10][10]
Definition: ar_matrix.cpp:320
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
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
SHAPE_LINE_CHAIN(const ClipperLib::Path &aPath)
std::vector< VECTOR2I >::const_iterator point_citer
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:89
SHAPE_LINE_CHAIN(const VECTOR2I *aV, int aCount)
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
void convertFromClipper(const ClipperLib::Path &aPath)
Function convertFromClipper() Appends the Clipper path to the current SHAPE_LINE_CHAIN.
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
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:587
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
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()
int PathLength(const VECTOR2I &aP) const
Function PathLength()
ClipperLib::Path convertToClipper(bool aRequiredOrientation) const
Creates a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
bool Parse(std::stringstream &aStream) override
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void SetClosed(bool aClosed)
Function SetClosed()
bool m_closed
is the line chain closed?
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
int EdgeContainingPoint(const VECTOR2I &aP) const
Function EdgeContainingPoint()
SEG their
segment belonging from the aOther argument of Intersect()
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const std::vector< VECTOR2I > & CPoints() const
std::vector< VECTOR2I > m_points
array of vertices
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
SHAPE_LINE_CHAIN(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC)
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
bool IsSolid() const override
Class SHAPE.
Definition: shape.h:58
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:384
const std::string Format() const override
void Remove(int aIndex)
Function Remove() removes the aIndex-th point from the line chain.
int SegmentCount() const
Function SegmentCount()
double Area() const
Definition: seg.h:36
VECTOR2I & LastPoint()
Returns the last point in the line chain.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:300
SEG Segment(int aIndex)
Function Segment()
const SEG CSegment(int aIndex) const
Function CSegment()
#define max(a, b)
Definition: auxiliary.h:86
Class SHAPE_LINE_CHAIN.
size_t i
Definition: json11.cpp:597
int Length() const
Function Length()
SHAPE_LINE_CHAIN(const VECTOR2I &aA, const VECTOR2I &aB, const VECTOR2I &aC, const VECTOR2I &aD)
line segment
Definition: shape.h:45
const VECTOR2I & CLastPoint() const
Returns the last point in the line chain.
boost::optional< T > OPT
Definition: optional.h:7
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 IsClosed() const
Function IsClosed()
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
SEG our
segment belonging from the (this) argument of Intersect()
const VECTOR2I PointAlong(int aPathLength) const
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const