Horizon
shape_line_chain.h
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/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 
77  SHAPE_LINE_CHAIN() : SHAPE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
78  {}
79 
84  : SHAPE( SH_LINE_CHAIN ),
85  m_points( aShape.m_points ),
86  m_closed( aShape.m_closed ),
87  m_width( aShape.m_width )
88  {}
89 
94  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) :
95  SHAPE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
96  {
97  m_points.resize( 2 );
98  m_points[0] = aA;
99  m_points[1] = aB;
100  }
101 
102  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) :
103  SHAPE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
104  {
105  m_points.resize( 3 );
106  m_points[0] = aA;
107  m_points[1] = aB;
108  m_points[2] = aC;
109  }
110 
111  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) :
112  SHAPE( SH_LINE_CHAIN ), m_closed( false ), m_width( 0 )
113  {
114  m_points.resize( 4 );
115  m_points[0] = aA;
116  m_points[1] = aB;
117  m_points[2] = aC;
118  m_points[3] = aD;
119  }
120 
121 
122  SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) :
123  SHAPE( SH_LINE_CHAIN ),
124  m_closed( false ),
125  m_width( 0 )
126  {
127  m_points.resize( aCount );
128 
129  for( int i = 0; i < aCount; i++ )
130  m_points[i] = *aV++;
131  }
132 
133  SHAPE_LINE_CHAIN( const ClipperLib::Path& aPath )
134  : SHAPE( SH_LINE_CHAIN ), m_closed( true ), m_width( 0 )
135  {
136  m_points.reserve( aPath.size() );
137 
138  for( const auto& point : aPath )
139  m_points.emplace_back( point.X, point.Y );
140  }
141 
143  {}
144 
145  SHAPE* Clone() const override;
146 
151  void Clear()
152  {
153  m_points.clear();
154  m_closed = false;
155  }
156 
164  void SetClosed( bool aClosed )
165  {
166  m_closed = aClosed;
167  }
168 
174  bool IsClosed() const
175  {
176  return m_closed;
177  }
178 
183  void SetWidth( int aWidth )
184  {
185  m_width = aWidth;
186  }
187 
192  int Width() const
193  {
194  return m_width;
195  }
196 
203  int SegmentCount() const
204  {
205  int c = m_points.size() - 1;
206  if( m_closed )
207  c++;
208 
209  return std::max( 0, c );
210  }
211 
218  int PointCount() const
219  {
220  return m_points.size();
221  }
222 
231  SEG Segment( int aIndex )
232  {
233  if( aIndex < 0 )
234  aIndex += SegmentCount();
235 
236  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
237  return SEG( m_points[aIndex], m_points[0], aIndex );
238  else
239  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
240  }
241 
250  const SEG CSegment( int aIndex ) const
251  {
252  if( aIndex < 0 )
253  aIndex += SegmentCount();
254 
255  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
256  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
257  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
258  else
259  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
260  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
261  }
262 
270  VECTOR2I& Point( int aIndex )
271  {
272  if( aIndex < 0 )
273  aIndex += PointCount();
274 
275  return m_points[aIndex];
276  }
277 
285  const VECTOR2I& CPoint( int aIndex ) const
286  {
287  if( aIndex < 0 )
288  aIndex += PointCount();
289  else if( aIndex >= PointCount() )
290  aIndex -= PointCount();
291 
292  return m_points[aIndex];
293  }
294 
295  const std::vector<VECTOR2I>& CPoints() const
296  {
297  return m_points;
298  }
299 
304  {
305  return m_points[PointCount() - 1];
306  }
307 
311  const VECTOR2I& CLastPoint() const
312  {
313  return m_points[PointCount() - 1];
314  }
315 
317  const BOX2I BBox( int aClearance = 0 ) const override
318  {
319  BOX2I bbox;
320  bbox.Compute( m_points );
321 
322  if( aClearance != 0 || m_width != 0 )
323  bbox.Inflate( aClearance + m_width );
324 
325  return bbox;
326  }
327 
336  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
337 
346  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
347 
355  int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
356 
363  const SHAPE_LINE_CHAIN Reverse() const;
364 
371  int Length() const;
372 
383  void Append( int aX, int aY, bool aAllowDuplication = false )
384  {
385  VECTOR2I v( aX, aY );
386  Append( v, aAllowDuplication );
387  }
388 
398  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
399  {
400  if( m_points.size() == 0 )
401  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
402 
403  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
404  {
405  m_points.push_back( aP );
406  m_bbox.Merge( aP );
407  }
408  }
409 
416  void Append( const SHAPE_LINE_CHAIN& aOtherLine )
417  {
418  if( aOtherLine.PointCount() == 0 )
419  return;
420 
421  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
422  {
423  const VECTOR2I p = aOtherLine.CPoint( 0 );
424  m_points.push_back( p );
425  m_bbox.Merge( p );
426  }
427 
428  for( int i = 1; i < aOtherLine.PointCount(); i++ )
429  {
430  const VECTOR2I p = aOtherLine.CPoint( i );
431  m_points.push_back( p );
432  m_bbox.Merge( p );
433  }
434  }
435 
436  void Insert( int aVertex, const VECTOR2I& aP )
437  {
438  m_points.insert( m_points.begin() + aVertex, aP );
439  }
440 
450  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
451 
461  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
462 
470  void Remove( int aStartIndex, int aEndIndex );
471 
477  void Remove( int aIndex )
478  {
479  Remove( aIndex, aIndex );
480  }
481 
491  int Split( const VECTOR2I& aP );
492 
500  int Find( const VECTOR2I& aP ) const;
501 
509  int FindSegment( const VECTOR2I& aP ) const;
510 
519  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
520 
522  {
523  compareOriginDistance( const VECTOR2I& aOrigin ):
524  m_origin( aOrigin )
525  {}
526 
527  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
528  {
529  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
530  }
531 
532  VECTOR2I m_origin;
533  };
534 
535  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
536 
546  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
547 
557  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
558 
567  int PathLength( const VECTOR2I& aP ) const;
568 
577  bool PointInside( const VECTOR2I& aP ) const;
578 
586  bool PointOnEdge( const VECTOR2I& aP ) const;
587 
595  int EdgeContainingPoint( const VECTOR2I& aP ) const;
596 
605  bool CheckClearance( const VECTOR2I& aP, const int aDist) const;
606 
613  const OPT<INTERSECTION> SelfIntersecting() const;
614 
622 
628  void convertFromClipper( const ClipperLib::Path& aPath );
629 
634  ClipperLib::Path convertToClipper( bool aRequiredOrientation ) const;
635 
642  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
643 
653  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
654 
656  const std::string Format() const override;
657 
659  bool Parse( std::stringstream& aStream ) override;
660 
661  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
662  {
663  if( PointCount() != aRhs.PointCount() )
664  return true;
665 
666  for( int i = 0; i < PointCount(); i++ )
667  {
668  if( CPoint( i ) != aRhs.CPoint( i ) )
669  return true;
670  }
671 
672  return false;
673  }
674 
675  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
676 
677  void Move( const VECTOR2I& aVector ) override
678  {
679  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
680  (*i) += aVector;
681  }
682 
689  void Rotate( double aAngle, const VECTOR2I& aCenter );
690 
691  bool IsSolid() const override
692  {
693  return false;
694  }
695 
696  const VECTOR2I PointAlong( int aPathLength ) const;
697 
698  double Area() const;
699 
700 private:
702  std::vector<VECTOR2I> m_points;
703 
705  bool m_closed;
706 
711  int m_width;
712 
714  BOX2I m_bbox;
715 };
716 
717 #endif // __SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN::INTERSECTION::p
VECTOR2I p
point of intersection between our and their.
Definition: shape_line_chain.h:68
SHAPE_LINE_CHAIN::NearestPoint
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: shape_line_chain.cpp:552
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN(const SHAPE_LINE_CHAIN &aShape)
Copy Constructor.
Definition: shape_line_chain.h:83
SHAPE_LINE_CHAIN::Intersect
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
Definition: shape_line_chain.cpp:260
SHAPE_LINE_CHAIN::CLastPoint
const VECTOR2I & CLastPoint() const
Returns the last point in the line chain.
Definition: shape_line_chain.h:311
BOX2::Inflate
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
SHAPE_LINE_CHAIN::SetWidth
void SetWidth(int aWidth)
Sets the width of all segments in the chain.
Definition: shape_line_chain.h:183
SHAPE_LINE_CHAIN::Append
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
Definition: shape_line_chain.h:383
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN(const VECTOR2I &aA, const VECTOR2I &aB)
Constructor Initializes a 2-point line chain (a single segment)
Definition: shape_line_chain.h:94
SHAPE_LINE_CHAIN::Clear
void Clear()
Function Clear() Removes all points from the line chain.
Definition: shape_line_chain.h:151
SHAPE_LINE_CHAIN::Format
const std::string Format() const override
Definition: shape_line_chain.cpp:592
SHAPE_LINE_CHAIN::Segment
SEG Segment(int aIndex)
Function Segment()
Definition: shape_line_chain.h:231
SHAPE_LINE_CHAIN::Slice
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Definition: shape_line_chain.cpp:228
SHAPE_LINE_CHAIN::EdgeContainingPoint
int EdgeContainingPoint(const VECTOR2I &aP) const
Function EdgeContainingPoint()
Definition: shape_line_chain.cpp:389
SHAPE_LINE_CHAIN::Point
VECTOR2I & Point(int aIndex)
Function Point()
Definition: shape_line_chain.h:270
BOX2::Merge
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
SHAPE_LINE_CHAIN::SegmentCount
int SegmentCount() const
Function SegmentCount()
Definition: shape_line_chain.h:203
SHAPE_LINE_CHAIN::Replace
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
Definition: shape_line_chain.cpp:113
SHAPE_LINE_CHAIN::Remove
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
Definition: shape_line_chain.cpp:144
SHAPE_LINE_CHAIN::CSegment
const SEG CSegment(int aIndex) const
Function CSegment()
Definition: shape_line_chain.h:250
VECTOR2< int >
SHAPE_LINE_CHAIN::SetClosed
void SetClosed(bool aClosed)
Function SetClosed()
Definition: shape_line_chain.h:164
SHAPE_LINE_CHAIN::SelfIntersecting
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
Definition: shape_line_chain.cpp:435
SHAPE_LINE_CHAIN::PointInside
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
Definition: shape_line_chain.cpp:351
SHAPE_LINE_CHAIN::LastPoint
VECTOR2I & LastPoint()
Returns the last point in the line chain.
Definition: shape_line_chain.h:303
SHAPE_LINE_CHAIN::Append
void Append(const SHAPE_LINE_CHAIN &aOtherLine)
Function Append()
Definition: shape_line_chain.h:416
SHAPE_LINE_CHAIN::BBox
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_line_chain.h:317
SHAPE_LINE_CHAIN::Clone
SHAPE * Clone() const override
Function Clone()
Definition: shape_line_chain.cpp:628
SHAPE_LINE_CHAIN::Rotate
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
Definition: shape_line_chain.cpp:57
SHAPE_LINE_CHAIN::INTERSECTION::their
SEG their
segment belonging from the aOther argument of Intersect()
Definition: shape_line_chain.h:66
SHAPE_LINE_CHAIN::convertFromClipper
void convertFromClipper(const ClipperLib::Path &aPath)
Function convertFromClipper() Appends the Clipper path to the current SHAPE_LINE_CHAIN.
SHAPE_LINE_CHAIN::Distance
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
Definition: shape_line_chain.cpp:156
SHAPE_LINE_CHAIN::PointCount
int PointCount() const
Function PointCount()
Definition: shape_line_chain.h:218
SHAPE_LINE_CHAIN::PointOnEdge
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
Definition: shape_line_chain.cpp:384
SHAPE_LINE_CHAIN::CPoint
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
Definition: shape_line_chain.h:285
SHAPE_LINE_CHAIN::IsClosed
bool IsClosed() const
Function IsClosed()
Definition: shape_line_chain.h:174
BOX2< VECTOR2I >
SEG
Definition: seg.h:37
SHAPE_LINE_CHAIN::compareOriginDistance
Definition: shape_line_chain.h:522
SHAPE_LINE_CHAIN::INTERSECTION::our
SEG our
segment belonging from the (this) argument of Intersect()
Definition: shape_line_chain.h:64
SHAPE_LINE_CHAIN::INTERSECTION
Struct INTERSECTION.
Definition: shape_line_chain.h:62
SHAPE_LINE_CHAIN::Parse
bool Parse(std::stringstream &aStream) override
Definition: shape_line_chain.cpp:633
SHAPE_LINE_CHAIN::Find
int Find(const VECTOR2I &aP) const
Function Find()
Definition: shape_line_chain.cpp:208
SHAPE_LINE_CHAIN::PathLength
int PathLength(const VECTOR2I &aP) const
Function PathLength()
Definition: shape_line_chain.cpp:329
SHAPE_LINE_CHAIN::CheckClearance
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
Definition: shape_line_chain.cpp:412
SHAPE_LINE_CHAIN::Append
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Function Append()
Definition: shape_line_chain.h:398
SHAPE_LINE_CHAIN::Width
int Width() const
Gets the current width of the segments in the chain.
Definition: shape_line_chain.h:192
SHAPE_LINE_CHAIN::Split
int Split(const VECTOR2I &aP)
Function Split()
Definition: shape_line_chain.cpp:170
SHAPE_LINE_CHAIN
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:50
SHAPE_LINE_CHAIN::Simplify
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
Definition: shape_line_chain.cpp:483
SHAPE
Class SHAPE.
Definition: shape.h:59
BOX2::Compute
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:89
SHAPE_LINE_CHAIN::Length
int Length() const
Function Length()
Definition: shape_line_chain.cpp:102
SHAPE_LINE_CHAIN::convertToClipper
ClipperLib::Path convertToClipper(bool aRequiredOrientation) const
Creates a new Clipper path from the SHAPE_LINE_CHAIN in a given orientation.
Definition: shape_line_chain.cpp:32
SHAPE_LINE_CHAIN::Remove
void Remove(int aIndex)
Function Remove() removes the aIndex-th point from the line chain.
Definition: shape_line_chain.h:477
SHAPE_LINE_CHAIN::Collide
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
Definition: shape_line_chain.cpp:49
SHAPE_LINE_CHAIN::FindSegment
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
Definition: shape_line_chain.cpp:218
SHAPE_LINE_CHAIN::Reverse
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
Definition: shape_line_chain.cpp:91
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
Definition: shape_line_chain.h:77