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 <algorithm> // for max
31 #include <sstream>
32 #include <vector>
33 #include <wx/gdicmn.h> // for wxPoint
34 
35 #include <core/optional.h>
36 
37 #include <clipper.hpp>
38 #include <geometry/seg.h>
39 #include <geometry/shape.h>
40 #include <geometry/shape_arc.h>
41 #include <math/box2.h> // for BOX2I
42 #include <math/vector2d.h>
43 
44 
54 class SHAPE_LINE_CHAIN : public SHAPE
55 {
56 private:
57  typedef std::vector<VECTOR2I>::iterator point_iter;
58  typedef std::vector<VECTOR2I>::const_iterator point_citer;
59 
60 public:
66  struct INTERSECTION
67  {
74  };
75 
76 
84  {
85  public:
86  POINT_INSIDE_TRACKER( const VECTOR2I& aPoint );
87 
88  void AddPolyline( const SHAPE_LINE_CHAIN& aPolyline );
89  bool IsInside();
90 
91  private:
92 
93  bool processVertex ( const VECTOR2I& ip, const VECTOR2I& ipNext );
94 
98  bool m_finished;
99  int m_state;
100  int m_count;
101  };
102 
103  typedef std::vector<INTERSECTION> INTERSECTIONS;
104 
105 
111  {}
112 
118  : SHAPE( SH_LINE_CHAIN ),
119  m_points( aShape.m_points ),
120  m_shapes( aShape.m_shapes ),
121  m_arcs( aShape.m_arcs ),
122  m_closed( aShape.m_closed ),
123  m_width( aShape.m_width ),
124  m_bbox( aShape.m_bbox )
125  {}
126 
127  SHAPE_LINE_CHAIN( const std::vector<int>& aV);
128 
129  SHAPE_LINE_CHAIN( const std::vector<wxPoint>& aV, bool aClosed = false )
130  : SHAPE( SH_LINE_CHAIN ), m_closed( aClosed ), m_width( 0 )
131  {
132  m_points.reserve( aV.size() );
133 
134  for( auto pt : aV )
135  m_points.emplace_back( pt.x, pt.y );
136 
137  m_shapes = std::vector<ssize_t>( aV.size(), ssize_t( SHAPE_IS_PT ) );
138  }
139 
140  SHAPE_LINE_CHAIN( const std::vector<VECTOR2I>& aV, bool aClosed = false )
141  : SHAPE( SH_LINE_CHAIN ), m_closed( aClosed ), m_width( 0 )
142  {
143  m_points = aV;
144  m_shapes = std::vector<ssize_t>( aV.size(), ssize_t( SHAPE_IS_PT ) );
145  }
146 
147  SHAPE_LINE_CHAIN( const SHAPE_ARC& aArc, bool aClosed = false )
148  : SHAPE( SH_LINE_CHAIN ),
149  m_closed( aClosed ),
150  m_width( 0 )
151  {
153  m_arcs.emplace_back( aArc );
154  m_shapes = std::vector<ssize_t>( m_points.size(), 0 );
155  }
156 
157  SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath ) :
158  SHAPE( SH_LINE_CHAIN ),
159  m_closed( true ),
160  m_width( 0 )
161  {
162  m_points.reserve( aPath.size() );
163  m_shapes = std::vector<ssize_t>( aPath.size(), ssize_t( SHAPE_IS_PT ) );
164 
165  for( const auto& point : aPath )
166  m_points.emplace_back( point.X, point.Y );
167  }
168 
170  {}
171 
172  SHAPE_LINE_CHAIN& operator=(const SHAPE_LINE_CHAIN&) = default;
173 
174  SHAPE* Clone() const override;
175 
180  void Clear()
181  {
182  m_points.clear();
183  m_arcs.clear();
184  m_shapes.clear();
185  m_closed = false;
186  }
187 
195  void SetClosed( bool aClosed )
196  {
197  m_closed = aClosed;
198  }
199 
205  bool IsClosed() const
206  {
207  return m_closed;
208  }
209 
214  void SetWidth( int aWidth )
215  {
216  m_width = aWidth;
217  }
218 
223  int Width() const
224  {
225  return m_width;
226  }
227 
234  int SegmentCount() const
235  {
236  int c = m_points.size() - 1;
237  if( m_closed )
238  c++;
239 
240  return std::max( 0, c );
241  }
242 
249  int PointCount() const
250  {
251  return m_points.size();
252  }
253 
262  SEG Segment( int aIndex )
263  {
264  if( aIndex < 0 )
265  aIndex += SegmentCount();
266 
267  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
268  return SEG( m_points[aIndex], m_points[0], aIndex );
269  else
270  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
271  }
272 
281  const SEG CSegment( int aIndex ) const
282  {
283  if( aIndex < 0 )
284  aIndex += SegmentCount();
285 
286  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
287  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
288  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
289  else
290  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
291  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
292  }
293 
299  void SetPoint( int aIndex, const VECTOR2I& aPos )
300  {
301  if( aIndex < 0 )
302  aIndex += PointCount();
303  else if( aIndex >= PointCount() )
304  aIndex -= PointCount();
305 
306  m_points[aIndex] = aPos;
307 
308  if( m_shapes[aIndex] != SHAPE_IS_PT )
309  convertArc( m_shapes[aIndex] );
310  }
311 
319  const VECTOR2I& CPoint( int aIndex ) const
320  {
321  if( aIndex < 0 )
322  aIndex += PointCount();
323  else if( aIndex >= PointCount() )
324  aIndex -= PointCount();
325 
326  return m_points[aIndex];
327  }
328 
329  const std::vector<VECTOR2I>& CPoints() const
330  {
331  return m_points;
332  }
333 
337  const VECTOR2I& CLastPoint() const
338  {
339  return m_points[PointCount() - 1];
340  }
341 
345  const std::vector<SHAPE_ARC>& CArcs() const
346  {
347  return m_arcs;
348  }
349 
353  const std::vector<ssize_t>& CShapes() const
354  {
355  return m_shapes;
356  }
357 
359  const BOX2I BBox( int aClearance = 0 ) const override
360  {
361  BOX2I bbox;
362  bbox.Compute( m_points );
363 
364  if( aClearance != 0 || m_width != 0 )
365  bbox.Inflate( aClearance + m_width );
366 
367  return bbox;
368  }
369 
371  {
373 
374  if( m_width != 0 )
376  }
377 
378  const BOX2I BBoxFromCache() const
379  {
380  return m_bbox;
381  }
382 
393  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr ) const override;
394 
405  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr ) const override;
406 
414  int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
415  SEG::ecoord SquaredDistance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
416 
423  const SHAPE_LINE_CHAIN Reverse() const;
424 
431  long long int Length() const;
432 
443  void Append( int aX, int aY, bool aAllowDuplication = false )
444  {
445  VECTOR2I v( aX, aY );
446  Append( v, aAllowDuplication );
447  }
448 
458  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
459  {
460  if( m_points.size() == 0 )
461  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
462 
463  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
464  {
465  m_points.push_back( aP );
466  m_shapes.push_back( ssize_t( SHAPE_IS_PT ) );
467  m_bbox.Merge( aP );
468  }
469  }
470 
477  void Append( const SHAPE_LINE_CHAIN& aOtherLine );
478 
479  void Append( const SHAPE_ARC& aArc );
480 
481  void Insert( size_t aVertex, const VECTOR2I& aP );
482 
483  void Insert( size_t aVertex, const SHAPE_ARC& aArc );
484 
494  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
495 
505  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
506 
514  void Remove( int aStartIndex, int aEndIndex );
515 
521  void Remove( int aIndex )
522  {
523  Remove( aIndex, aIndex );
524  }
525 
535  int Split( const VECTOR2I& aP );
536 
544  int Find( const VECTOR2I& aP ) const;
545 
553  int FindSegment( const VECTOR2I& aP ) const;
554 
563  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
564 
566  {
567  compareOriginDistance( const VECTOR2I& aOrigin ):
568  m_origin( aOrigin )
569  {}
570 
571  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
572  {
573  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
574  }
575 
577  };
578 
579  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
580 
590  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
591 
601  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
602 
611  int PathLength( const VECTOR2I& aP ) const;
612 
623  bool PointInside( const VECTOR2I& aPt, int aAccuracy = 0, bool aUseBBoxCache = false ) const;
624 
625 
633  bool PointOnEdge( const VECTOR2I& aP, int aAccuracy = 0 ) const;
634 
642  int EdgeContainingPoint( const VECTOR2I& aP, int aAccuracy = 0 ) const;
643 
652  bool CheckClearance( const VECTOR2I& aP, const int aDist) const;
653 
660  const OPT<INTERSECTION> SelfIntersecting() const;
661 
669 
675  void convertArc( ssize_t aArcIndex );
676 
681  ClipperLib::Path convertToClipper( bool aRequiredOrientation ) const;
682 
689  int NearestSegment( const VECTOR2I& aP ) const;
690 
697  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
698 
708  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
709 
711  const std::string Format() const override;
712 
714  bool Parse( std::stringstream& aStream ) override;
715 
716  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
717  {
718  if( PointCount() != aRhs.PointCount() )
719  return true;
720 
721  for( int i = 0; i < PointCount(); i++ )
722  {
723  if( CPoint( i ) != aRhs.CPoint( i ) )
724  return true;
725  }
726 
727  return false;
728  }
729 
730  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
731 
732  void Move( const VECTOR2I& aVector ) override
733  {
734  for( auto& pt : m_points )
735  pt += aVector;
736 
737  for( auto& arc : m_arcs )
738  arc.Move( aVector );
739  }
740 
747  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
748 
755  void Rotate( double aAngle, const VECTOR2I& aCenter = VECTOR2I( 0, 0 ) ) override;
756 
757  bool IsSolid() const override
758  {
759  return false;
760  }
761 
762  const VECTOR2I PointAlong( int aPathLength ) const;
763 
764  double Area() const;
765 
766  size_t ArcCount() const
767  {
768  return m_arcs.size();
769  }
770 
771  ssize_t ArcIndex( size_t aSegment ) const
772  {
773  if( aSegment >= m_shapes.size() )
774  return SHAPE_IS_PT;
775 
776  return m_shapes[aSegment];
777  }
778 
779  const SHAPE_ARC& Arc( size_t aArc ) const
780  {
781  return m_arcs[aArc];
782  }
783 
784  bool isArc( size_t aSegment ) const
785  {
786  return aSegment < m_shapes.size() && m_shapes[aSegment] != SHAPE_IS_PT;
787  }
788 
789 private:
790 
791  constexpr static ssize_t SHAPE_IS_PT = -1;
792 
794  std::vector<VECTOR2I> m_points;
795 
801  std::vector<ssize_t> m_shapes;
802 
803  std::vector<SHAPE_ARC> m_arcs;
804 
806  bool m_closed;
807 
812  int m_width;
813 
816 };
817 
818 
819 #endif // __SHAPE_LINE_CHAIN
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
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()
const SHAPE_ARC & Arc(size_t aArc) const
long long int Length() const
Function Length()
int Split(const VECTOR2I &aP)
Function Split()
int EdgeContainingPoint(const VECTOR2I &aP, int aAccuracy=0) const
Function EdgeContainingPoint()
BOX2< VECTOR2I > BOX2I
Definition: box2.h:521
bool isArc(size_t aSegment) const
bool operator!=(const SHAPE_LINE_CHAIN &aRhs) const
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
std::vector< INTERSECTION > INTERSECTIONS
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Function PointOnEdge()
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.
VECTOR2I::extended_type ecoord
Definition: seg.h:42
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:90
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:594
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
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
double dist(const double ax, const double ay, const double bx, const double by)
Definition: delauney.h:168
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
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
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()
bool Intersects(const SHAPE_LINE_CHAIN &aChain) const
bool IsSolid() const override
SHAPE.
Definition: shape.h:74
SEG::ecoord SquaredDistance(const VECTOR2I &aP, bool aOutlineOnly=false) const
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:385
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()
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:39
int NearestSegment(const VECTOR2I &aP) const
Find the segment nearest the given point.
bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr) const override
Function Collide()
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:301
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 segment
Definition: shape.h:43
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()
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
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 SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=500.0) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:238
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