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-2020 KiCad Developers, see AUTHORS.txt for contributors.
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 
30 #include <clipper.hpp>
31 #include <geometry/seg.h>
32 #include <geometry/shape.h>
33 #include <geometry/shape_arc.h>
34 #include <math/vector2d.h>
35 
36 
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 
76  {
77  public:
78  POINT_INSIDE_TRACKER( const VECTOR2I& aPoint );
79 
80  void AddPolyline( const SHAPE_LINE_CHAIN& aPolyline );
81  bool IsInside();
82 
83  private:
84 
85  bool processVertex ( const VECTOR2I& ip, const VECTOR2I& ipNext );
86 
90  bool m_finished;
91  int m_state;
92  int m_count;
93  };
94 
95  typedef std::vector<INTERSECTION> INTERSECTIONS;
96 
97 
103  {}
104 
111  m_points( aShape.m_points ),
112  m_shapes( aShape.m_shapes ),
113  m_arcs( aShape.m_arcs ),
114  m_closed( aShape.m_closed ),
115  m_width( aShape.m_width ),
116  m_bbox( aShape.m_bbox )
117  {}
118 
119  SHAPE_LINE_CHAIN( const std::vector<int>& aV);
120 
121  SHAPE_LINE_CHAIN( const std::vector<wxPoint>& aV, bool aClosed = false )
122  : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( aClosed ), m_width( 0 )
123  {
124  m_points.reserve( aV.size() );
125 
126  for( auto pt : aV )
127  m_points.emplace_back( pt.x, pt.y );
128 
129  m_shapes = std::vector<ssize_t>( aV.size(), ssize_t( SHAPE_IS_PT ) );
130  }
131 
132  SHAPE_LINE_CHAIN( const std::vector<VECTOR2I>& aV, bool aClosed = false )
133  : SHAPE_LINE_CHAIN_BASE( SH_LINE_CHAIN ), m_closed( aClosed ), m_width( 0 )
134  {
135  m_points = aV;
136  m_shapes = std::vector<ssize_t>( aV.size(), ssize_t( SHAPE_IS_PT ) );
137  }
138 
139  SHAPE_LINE_CHAIN( const SHAPE_ARC& aArc, bool aClosed = false )
141  m_closed( aClosed ),
142  m_width( 0 )
143  {
145  m_arcs.emplace_back( aArc );
146  m_shapes = std::vector<ssize_t>( m_points.size(), 0 );
147  }
148 
149  SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath ) :
151  m_closed( true ),
152  m_width( 0 )
153  {
154  m_points.reserve( aPath.size() );
155  m_shapes = std::vector<ssize_t>( aPath.size(), ssize_t( SHAPE_IS_PT ) );
156 
157  for( const auto& point : aPath )
158  m_points.emplace_back( point.X, point.Y );
159  }
160 
162  {}
163 
164  SHAPE_LINE_CHAIN& operator=(const SHAPE_LINE_CHAIN&) = default;
165 
166  SHAPE* Clone() const override;
167 
172  void Clear()
173  {
174  m_points.clear();
175  m_arcs.clear();
176  m_shapes.clear();
177  m_closed = false;
178  }
179 
187  void SetClosed( bool aClosed )
188  {
189  m_closed = aClosed;
190  }
191 
197  bool IsClosed() const override
198  {
199  return m_closed;
200  }
201 
206  void SetWidth( int aWidth )
207  {
208  m_width = aWidth;
209  }
210 
215  int Width() const
216  {
217  return m_width;
218  }
219 
226  int SegmentCount() const
227  {
228  int c = m_points.size() - 1;
229  if( m_closed )
230  c++;
231 
232  return std::max( 0, c );
233  }
234 
240  int ShapeCount() const;
241 
248  int PointCount() const
249  {
250  return m_points.size();
251  }
252 
261  SEG Segment( int aIndex )
262  {
263  if( aIndex < 0 )
264  aIndex += SegmentCount();
265 
266  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
267  return SEG( m_points[aIndex], m_points[0], aIndex );
268  else
269  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
270  }
271 
280  const SEG CSegment( int aIndex ) const
281  {
282  if( aIndex < 0 )
283  aIndex += SegmentCount();
284 
285  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
286  return SEG( m_points[aIndex], m_points[0], aIndex );
287  else
288  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
289  }
290 
300  int NextShape( int aPointIndex, bool aForwards = true ) const;
301 
302  int PrevShape( int aPointIndex ) const
303  {
304  return NextShape( aPointIndex, false );
305  }
306 
312  void SetPoint( int aIndex, const VECTOR2I& aPos )
313  {
314  if( aIndex < 0 )
315  aIndex += PointCount();
316  else if( aIndex >= PointCount() )
317  aIndex -= PointCount();
318 
319  m_points[aIndex] = aPos;
320 
321  if( m_shapes[aIndex] != SHAPE_IS_PT )
322  convertArc( m_shapes[aIndex] );
323  }
324 
332  const VECTOR2I& CPoint( int aIndex ) const
333  {
334  if( aIndex < 0 )
335  aIndex += PointCount();
336  else if( aIndex >= PointCount() )
337  aIndex -= PointCount();
338 
339  return m_points[aIndex];
340  }
341 
342  const std::vector<VECTOR2I>& CPoints() const
343  {
344  return m_points;
345  }
346 
350  const VECTOR2I& CLastPoint() const
351  {
352  return m_points[PointCount() - 1];
353  }
354 
358  const std::vector<SHAPE_ARC>& CArcs() const
359  {
360  return m_arcs;
361  }
362 
366  const std::vector<ssize_t>& CShapes() const
367  {
368  return m_shapes;
369  }
370 
372  const BOX2I BBox( int aClearance = 0 ) const override
373  {
374  BOX2I bbox;
375  bbox.Compute( m_points );
376 
377  if( aClearance != 0 || m_width != 0 )
378  bbox.Inflate( aClearance + m_width );
379 
380  return bbox;
381  }
382 
383  void GenerateBBoxCache() const
384  {
386 
387  if( m_width != 0 )
389  }
390 
391  const BOX2I BBoxFromCache() const
392  {
393  return m_bbox;
394  }
395 
403  int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
404 
411  const SHAPE_LINE_CHAIN Reverse() const;
412 
419  long long int Length() const;
420 
431  void Append( int aX, int aY, bool aAllowDuplication = false )
432  {
433  VECTOR2I v( aX, aY );
434  Append( v, aAllowDuplication );
435  }
436 
446  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
447  {
448  if( m_points.size() == 0 )
449  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
450 
451  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
452  {
453  m_points.push_back( aP );
454  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
455  m_bbox.Merge( aP );
456  }
457  }
458 
465  void Append( const SHAPE_LINE_CHAIN& aOtherLine );
466 
467  void Append( const SHAPE_ARC& aArc );
468 
469  void Insert( size_t aVertex, const VECTOR2I& aP );
470 
471  void Insert( size_t aVertex, const SHAPE_ARC& aArc );
472 
481  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
482 
492  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
493 
501  void Remove( int aStartIndex, int aEndIndex );
502 
508  void Remove( int aIndex )
509  {
510  Remove( aIndex, aIndex );
511  }
512 
519  void RemoveShape( int aPointIndex );
520 
530  int Split( const VECTOR2I& aP );
531 
539  int Find( const VECTOR2I& aP ) const;
540 
548  int FindSegment( const VECTOR2I& aP ) const;
549 
558  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
559 
561  {
562  compareOriginDistance( const VECTOR2I& aOrigin ):
563  m_origin( aOrigin )
564  {}
565 
566  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
567  {
568  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
569  }
570 
572  };
573 
574  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
575 
585  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
586 
596  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
597 
605  int PathLength( const VECTOR2I& aP ) const;
606 
615  bool CheckClearance( const VECTOR2I& aP, const int aDist) const;
616 
623  const OPT<INTERSECTION> SelfIntersecting() const;
624 
632  SHAPE_LINE_CHAIN& Simplify( bool aRemoveColinear = true );
633 
639  void convertArc( ssize_t aArcIndex );
640 
644  ClipperLib::Path convertToClipper( bool aRequiredOrientation ) const;
645 
652  int NearestSegment( const VECTOR2I& aP ) const;
653 
661  const VECTOR2I NearestPoint( const VECTOR2I& aP, bool aAllowInternalShapePoints = true ) const;
662 
670  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
671 
673  const std::string Format() const override;
674 
676  bool Parse( std::stringstream& aStream ) override;
677 
678  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
679  {
680  if( PointCount() != aRhs.PointCount() )
681  return true;
682 
683  for( int i = 0; i < PointCount(); i++ )
684  {
685  if( CPoint( i ) != aRhs.CPoint( i ) )
686  return true;
687  }
688 
689  return false;
690  }
691 
692  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
693 
694  void Move( const VECTOR2I& aVector ) override
695  {
696  for( auto& pt : m_points )
697  pt += aVector;
698 
699  for( auto& arc : m_arcs )
700  arc.Move( aVector );
701  }
702 
709  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
710 
715  void Mirror( const SEG& axis );
716 
723  void Rotate( double aAngle, const VECTOR2I& aCenter = VECTOR2I( 0, 0 ) ) override;
724 
725  bool IsSolid() const override
726  {
727  return false;
728  }
729 
730  const VECTOR2I PointAlong( int aPathLength ) const;
731 
732  double Area() const;
733 
734  size_t ArcCount() const
735  {
736  return m_arcs.size();
737  }
738 
739  ssize_t ArcIndex( size_t aSegment ) const
740  {
741  if( aSegment >= m_shapes.size() )
742  return SHAPE_IS_PT;
743 
744  return m_shapes[aSegment];
745  }
746 
747  const SHAPE_ARC& Arc( size_t aArc ) const
748  {
749  return m_arcs[aArc];
750  }
751 
752  bool isArc( size_t aSegment ) const
753  {
759  return ( aSegment < m_shapes.size() - 1
760  && m_shapes[aSegment] != SHAPE_IS_PT
761  && m_shapes[aSegment] == m_shapes[aSegment + 1] );
762  }
763 
764  virtual const VECTOR2I GetPoint( int aIndex ) const override { return CPoint(aIndex); }
765  virtual const SEG GetSegment( int aIndex ) const override { return CSegment(aIndex); }
766  virtual size_t GetPointCount() const override { return PointCount(); }
767  virtual size_t GetSegmentCount() const override { return SegmentCount(); }
768 
769 private:
770 
771  constexpr static ssize_t SHAPE_IS_PT = -1;
772 
774  std::vector<VECTOR2I> m_points;
775 
781  std::vector<ssize_t> m_shapes;
782 
783  std::vector<SHAPE_ARC> m_arcs;
784 
786  bool m_closed;
787 
793  int m_width;
794 
796  mutable BOX2I m_bbox;
797 };
798 
799 
800 #endif // __SHAPE_LINE_CHAIN
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
int Find(const VECTOR2I &aP) const
Function Find()
int PrevShape(int aPointIndex) const
BOX2I m_bbox
cached bounding box
compareOriginDistance(const VECTOR2I &aOrigin)
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Function Append()
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
const SHAPE_ARC & Arc(size_t aArc) const
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
BOX2< VECTOR2I > BOX2I
Definition: box2.h:522
bool isArc(size_t aSegment) const
bool operator!=(const SHAPE_LINE_CHAIN &aRhs) const
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
virtual size_t GetSegmentCount() const override
std::vector< INTERSECTION > INTERSECTIONS
virtual size_t GetPointCount() const override
void RemoveShape(int aPointIndex)
Removes the shape at the given index from the line chain.
SHAPE_LINE_CHAIN & Simplify(bool aRemoveColinear=true)
Function Simplify()
void SetPoint(int aIndex, const VECTOR2I &aPos)
Accessor Function to move a point to a specific location.
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
int Width() const
Gets the current width of the segments in the chain.
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:91
SHAPE_LINE_CHAIN(const SHAPE_ARC &aArc, bool aClosed=false)
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
virtual ~SHAPE_LINE_CHAIN()
size_t ArcCount() const
void AddPolyline(const SHAPE_LINE_CHAIN &aPolyline)
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
const std::vector< SHAPE_ARC > & CArcs() const
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
void convertArc(ssize_t aArcIndex)
Converts an arc to only a point chain by removing the arc and references.
int PointCount() const
Function PointCount()
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
SHAPE_LINE_CHAIN(const std::vector< VECTOR2I > &aV, bool aClosed=false)
bool operator()(const INTERSECTION &aA, const INTERSECTION &aB)
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
std::vector< SHAPE_ARC > m_arcs
const VECTOR2I NearestPoint(const VECTOR2I &aP, bool aAllowInternalShapePoints=true) const
Finds a point on the line chain that is closest to point aP.
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
void Insert(size_t aVertex, const VECTOR2I &aP)
const std::vector< ssize_t > & CShapes() const
ssize_t ArcIndex(size_t aSegment) const
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetWidth(int aWidth)
Sets the width of all segments in the chain.
void SetClosed(bool aClosed)
Function SetClosed()
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()
SHAPE_LINE_CHAIN & operator=(const SHAPE_LINE_CHAIN &)=default
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:417
bool IsClosed() const override
Function IsClosed()
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()
virtual const SEG GetSegment(int aIndex) const override
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
int ShapeCount() const
Returns the number of shapes (line segments or arcs) in this line chain.
bool IsSolid() const override
An abstract shape on 2D plane.
Definition: shape.h:116
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:386
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()
virtual const VECTOR2I GetPoint(int aIndex) const override
SHAPE_LINE_CHAIN(const std::vector< wxPoint > &aV, bool aClosed=false)
void Rotate(double aAngle, const VECTOR2I &aCenter=VECTOR2I(0, 0)) override
Function Rotate rotates all vertices by a given angle.
Definition: seg.h:41
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
SEG Segment(int aIndex)
Function Segment()
std::vector< ssize_t > m_shapes
Array of indices that refer to the index of the shape if the point is part of a larger shape,...
const SEG CSegment(int aIndex) const
Function CSegment()
static constexpr ssize_t SHAPE_IS_PT
SHAPE_LINE_CHAIN.
int m_width
Width of the segments (for BBox calculations in RTree) TODO Adjust usage of SHAPE_LINE_CHAIN to accou...
line chain (polyline)
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
Return a dynamically allocated copy of the shape.
void GenerateBBoxCache() const
std::vector< VECTOR2I >::iterator point_iter
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
int NextShape(int aPointIndex, bool aForwards=true) const
Returns the vertex index of the next shape in the chain, or -1 if aPoint is in the last shape If aPoi...
SEG our
segment belonging from the (this) argument of Intersect()
const BOX2I BBoxFromCache() const
const VECTOR2I PointAlong(int aPathLength) const
bool processVertex(const VECTOR2I &ip, const VECTOR2I &ipNext)
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirrors the line points about y or x (or both)
bool CompareGeometry(const SHAPE_LINE_CHAIN &aOther) const