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-2019
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 <sstream>
30 #include <vector>
31 #include <wx/gdicmn.h>
32 
33 #include <core/optional.h>
34 
35 #include <math/vector2d.h>
36 #include <geometry/shape.h>
37 #include <geometry/seg.h>
38 
39 #include <clipper.hpp>
40 
50 class SHAPE_LINE_CHAIN : public SHAPE
51 {
52 private:
53  typedef std::vector<VECTOR2I>::iterator point_iter;
54  typedef std::vector<VECTOR2I>::const_iterator point_citer;
55 
56 public:
62  struct INTERSECTION
63  {
70  };
71 
72  typedef std::vector<INTERSECTION> INTERSECTIONS;
73 
74 
80  SHAPE( SH_LINE_CHAIN ), m_closed( false )
81  {}
82 
87  SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed )
88  {}
89 
90  SHAPE_LINE_CHAIN( const std::vector<wxPoint>& aV, bool aClosed = false )
91  : SHAPE( SH_LINE_CHAIN ), m_closed( aClosed )
92  {
93  m_points.reserve( aV.size() );
94 
95  for( auto pt : aV )
96  m_points.emplace_back( pt.x, pt.y );
97  }
98 
99  SHAPE_LINE_CHAIN( const std::vector<VECTOR2I>& aV, bool aClosed = false )
100  : SHAPE( SH_LINE_CHAIN ), m_closed( aClosed )
101  {
102  m_points = aV;
103  }
104 
105  SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath ) :
106  SHAPE( SH_LINE_CHAIN ),
107  m_closed( true )
108  {
109  m_points.reserve( aPath.size() );
110 
111  for( const auto& point : aPath )
112  m_points.emplace_back( point.X, point.Y );
113  }
114 
116  {}
117 
118  SHAPE* Clone() const override;
119 
124  void Clear()
125  {
126  m_points.clear();
127  m_closed = false;
128  }
129 
137  void SetClosed( bool aClosed )
138  {
139  m_closed = aClosed;
140  }
141 
147  bool IsClosed() const
148  {
149  return m_closed;
150  }
151 
158  int SegmentCount() const
159  {
160  int c = m_points.size() - 1;
161  if( m_closed )
162  c++;
163 
164  return std::max( 0, c );
165  }
166 
173  int PointCount() const
174  {
175  return m_points.size();
176  }
177 
186  SEG Segment( int aIndex )
187  {
188  if( aIndex < 0 )
189  aIndex += SegmentCount();
190 
191  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
192  return SEG( m_points[aIndex], m_points[0], aIndex );
193  else
194  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
195  }
196 
205  const SEG CSegment( int aIndex ) const
206  {
207  if( aIndex < 0 )
208  aIndex += SegmentCount();
209 
210  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
211  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
212  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
213  else
214  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
215  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
216  }
217 
223  void SetPoint( int aIndex, const VECTOR2I& aPos )
224  {
225  if( aIndex < 0 )
226  aIndex += PointCount();
227  else if( aIndex >= PointCount() )
228  aIndex -= PointCount();
229 
230  m_points[aIndex] = aPos;
231  }
232 
240  const VECTOR2I& CPoint( int aIndex ) const
241  {
242  if( aIndex < 0 )
243  aIndex += PointCount();
244  else if( aIndex >= PointCount() )
245  aIndex -= PointCount();
246 
247  return m_points[aIndex];
248  }
249 
250  const std::vector<VECTOR2I>& CPoints() const
251  {
252  return m_points;
253  }
254 
258  const VECTOR2I& CLastPoint() const
259  {
260  return m_points[PointCount() - 1];
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 
276  {
278  }
279 
288  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
289 
298  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
299 
307  int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
308 
315  const SHAPE_LINE_CHAIN Reverse() const;
316 
323  long long int Length() const;
324 
335  void Append( int aX, int aY, bool aAllowDuplication = false )
336  {
337  VECTOR2I v( aX, aY );
338  Append( v, aAllowDuplication );
339  }
340 
350  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
351  {
352  if( m_points.size() == 0 )
353  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
354 
355  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
356  {
357  m_points.push_back( aP );
358  m_bbox.Merge( aP );
359  }
360  }
361 
368  void Append( const SHAPE_LINE_CHAIN& aOtherLine )
369  {
370  if( aOtherLine.PointCount() == 0 )
371  return;
372 
373  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
374  {
375  const VECTOR2I p = aOtherLine.CPoint( 0 );
376  m_points.push_back( p );
377  m_bbox.Merge( p );
378  }
379 
380  for( int i = 1; i < aOtherLine.PointCount(); i++ )
381  {
382  const VECTOR2I p = aOtherLine.CPoint( i );
383  m_points.push_back( p );
384  m_bbox.Merge( p );
385  }
386  }
387 
388  void Insert( int aVertex, const VECTOR2I& aP )
389  {
390  m_points.insert( m_points.begin() + aVertex, aP );
391  }
392 
402  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
403 
413  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
414 
422  void Remove( int aStartIndex, int aEndIndex );
423 
429  void Remove( int aIndex )
430  {
431  Remove( aIndex, aIndex );
432  }
433 
443  int Split( const VECTOR2I& aP );
444 
452  int Find( const VECTOR2I& aP ) const;
453 
461  int FindSegment( const VECTOR2I& aP ) const;
462 
471  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
472 
474  {
475  compareOriginDistance( const VECTOR2I& aOrigin ):
476  m_origin( aOrigin )
477  {}
478 
479  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
480  {
481  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
482  }
483 
485  };
486 
487  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
488 
498  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
499 
509  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
510 
519  int PathLength( const VECTOR2I& aP ) const;
520 
531  bool PointInside( const VECTOR2I& aPt, int aAccuracy = 0, bool aUseBBoxCache = false ) const;
532 
540  bool PointOnEdge( const VECTOR2I& aP, int aAccuracy = 0 ) const;
541 
549  int EdgeContainingPoint( const VECTOR2I& aP, int aAccuracy = 0 ) const;
550 
559  bool CheckClearance( const VECTOR2I& aP, const int aDist) const;
560 
567  const OPT<INTERSECTION> SelfIntersecting() const;
568 
576 
581  ClipperLib::Path convertToClipper( bool aRequiredOrientation ) const;
582 
589  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
590 
600  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
601 
603  const std::string Format() const override;
604 
606  bool Parse( std::stringstream& aStream ) override;
607 
608  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
609  {
610  if( PointCount() != aRhs.PointCount() )
611  return true;
612 
613  for( int i = 0; i < PointCount(); i++ )
614  {
615  if( CPoint( i ) != aRhs.CPoint( i ) )
616  return true;
617  }
618 
619  return false;
620  }
621 
622  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
623 
624  void Move( const VECTOR2I& aVector ) override
625  {
626  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
627  (*i) += aVector;
628  }
629 
636  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } )
637  {
638  for( auto& pt : m_points )
639  {
640  if( aX )
641  pt.x = -pt.x + 2 * aRef.x;
642 
643  if( aY )
644  pt.y = -pt.y + 2 * aRef.y;
645  }
646  }
647 
654  void Rotate( double aAngle, const VECTOR2I& aCenter = VECTOR2I( 0, 0 ) );
655 
656  bool IsSolid() const override
657  {
658  return false;
659  }
660 
661  const VECTOR2I PointAlong( int aPathLength ) const;
662 
663  double Area() const;
664 
665 private:
667  std::vector<VECTOR2I> m_points;
668 
670  bool m_closed;
671 
674 };
675 
676 #endif // __SHAPE_LINE_CHAIN
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:123
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()
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: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 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.
void Rotate(double aAngle, const VECTOR2I &aCenter=VECTOR2I(0, 0))
Function Rotate rotates all vertices by a given angle.
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
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
virtual ~SHAPE_LINE_CHAIN()
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
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)
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 Point()
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()
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
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
SHAPE_LINE_CHAIN(const std::vector< wxPoint > &aV, bool aClosed=false)
Definition: seg.h:36
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:649
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()
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
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
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