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 
47 class SHAPE_LINE_CHAIN : public SHAPE
48 {
49 private:
50  typedef std::vector<VECTOR2I>::iterator point_iter;
51  typedef std::vector<VECTOR2I>::const_iterator point_citer;
52 
53 public:
59  struct INTERSECTION
60  {
67  };
68 
69  typedef std::vector<INTERSECTION> INTERSECTIONS;
70 
76  SHAPE( SH_LINE_CHAIN ), m_closed( false )
77  {}
78 
83  SHAPE( SH_LINE_CHAIN ), m_points( aShape.m_points ), m_closed( aShape.m_closed )
84  {}
85 
90  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB ) :
91  SHAPE( SH_LINE_CHAIN ), m_closed( false )
92  {
93  m_points.resize( 2 );
94  m_points[0] = aA;
95  m_points[1] = aB;
96  }
97 
98  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC ) :
99  SHAPE( SH_LINE_CHAIN ), m_closed( false )
100  {
101  m_points.resize( 3 );
102  m_points[0] = aA;
103  m_points[1] = aB;
104  m_points[2] = aC;
105  }
106 
107  SHAPE_LINE_CHAIN( const VECTOR2I& aA, const VECTOR2I& aB, const VECTOR2I& aC, const VECTOR2I& aD ) :
108  SHAPE( SH_LINE_CHAIN ), m_closed( false )
109  {
110  m_points.resize( 4 );
111  m_points[0] = aA;
112  m_points[1] = aB;
113  m_points[2] = aC;
114  m_points[3] = aD;
115  }
116 
117 
118  SHAPE_LINE_CHAIN( const VECTOR2I* aV, int aCount ) :
119  SHAPE( SH_LINE_CHAIN ),
120  m_closed( false )
121  {
122  m_points.resize( aCount );
123 
124  for( int i = 0; i < aCount; i++ )
125  m_points[i] = *aV++;
126  }
127 
129  {}
130 
131  SHAPE* Clone() const override;
132 
137  void Clear()
138  {
139  m_points.clear();
140  m_closed = false;
141  }
142 
150  void SetClosed( bool aClosed )
151  {
152  m_closed = aClosed;
153  }
154 
160  bool IsClosed() const
161  {
162  return m_closed;
163  }
164 
171  int SegmentCount() const
172  {
173  int c = m_points.size() - 1;
174  if( m_closed )
175  c++;
176 
177  return std::max( 0, c );
178  }
179 
186  int PointCount() const
187  {
188  return m_points.size();
189  }
190 
199  SEG Segment( int aIndex )
200  {
201  if( aIndex < 0 )
202  aIndex += SegmentCount();
203 
204  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
205  return SEG( m_points[aIndex], m_points[0], aIndex );
206  else
207  return SEG( m_points[aIndex], m_points[aIndex + 1], aIndex );
208  }
209 
218  const SEG CSegment( int aIndex ) const
219  {
220  if( aIndex < 0 )
221  aIndex += SegmentCount();
222 
223  if( aIndex == (int)( m_points.size() - 1 ) && m_closed )
224  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
225  const_cast<VECTOR2I&>( m_points[0] ), aIndex );
226  else
227  return SEG( const_cast<VECTOR2I&>( m_points[aIndex] ),
228  const_cast<VECTOR2I&>( m_points[aIndex + 1] ), aIndex );
229  }
230 
238  VECTOR2I& Point( int aIndex )
239  {
240  if( aIndex < 0 )
241  aIndex += PointCount();
242 
243  return m_points[aIndex];
244  }
245 
253  const VECTOR2I& CPoint( int aIndex ) const
254  {
255  if( aIndex < 0 )
256  aIndex += PointCount();
257  else if( aIndex >= PointCount() )
258  aIndex -= PointCount();
259 
260  return m_points[aIndex];
261  }
262 
267  {
268  return m_points[PointCount() - 1];
269  }
270 
274  const VECTOR2I& CLastPoint() const
275  {
276  return m_points[PointCount() - 1];
277  }
278 
280  const BOX2I BBox( int aClearance = 0 ) const override
281  {
282  BOX2I bbox;
283  bbox.Compute( m_points );
284 
285  if( aClearance != 0 )
286  bbox.Inflate( aClearance );
287 
288  return bbox;
289  }
290 
299  bool Collide( const VECTOR2I& aP, int aClearance = 0 ) const override;
300 
309  bool Collide( const SEG& aSeg, int aClearance = 0 ) const override;
310 
318  int Distance( const VECTOR2I& aP, bool aOutlineOnly = false ) const;
319 
326  const SHAPE_LINE_CHAIN Reverse() const;
327 
334  int Length() const;
335 
346  void Append( int aX, int aY, bool aAllowDuplication = false )
347  {
348  VECTOR2I v( aX, aY );
349  Append( v, aAllowDuplication );
350  }
351 
361  void Append( const VECTOR2I& aP, bool aAllowDuplication = false )
362  {
363  if( m_points.size() == 0 )
364  m_bbox = BOX2I( aP, VECTOR2I( 0, 0 ) );
365 
366  if( m_points.size() == 0 || aAllowDuplication || CPoint( -1 ) != aP )
367  {
368  m_points.push_back( aP );
369  m_bbox.Merge( aP );
370  }
371  }
372 
379  void Append( const SHAPE_LINE_CHAIN& aOtherLine )
380  {
381  if( aOtherLine.PointCount() == 0 )
382  return;
383 
384  else if( PointCount() == 0 || aOtherLine.CPoint( 0 ) != CPoint( -1 ) )
385  {
386  const VECTOR2I p = aOtherLine.CPoint( 0 );
387  m_points.push_back( p );
388  m_bbox.Merge( p );
389  }
390 
391  for( int i = 1; i < aOtherLine.PointCount(); i++ )
392  {
393  const VECTOR2I p = aOtherLine.CPoint( i );
394  m_points.push_back( p );
395  m_bbox.Merge( p );
396  }
397  }
398 
399  void Insert( int aVertex, const VECTOR2I& aP )
400  {
401  m_points.insert( m_points.begin() + aVertex, aP );
402  }
403 
413  void Replace( int aStartIndex, int aEndIndex, const VECTOR2I& aP );
414 
424  void Replace( int aStartIndex, int aEndIndex, const SHAPE_LINE_CHAIN& aLine );
425 
433  void Remove( int aStartIndex, int aEndIndex );
434 
440  void Remove( int aIndex )
441  {
442  Remove( aIndex, aIndex );
443  }
444 
454  int Split( const VECTOR2I& aP );
455 
463  int Find( const VECTOR2I& aP ) const;
464 
472  int FindSegment( const VECTOR2I& aP ) const;
473 
482  const SHAPE_LINE_CHAIN Slice( int aStartIndex, int aEndIndex = -1 ) const;
483 
485  {
486  compareOriginDistance( const VECTOR2I& aOrigin ):
487  m_origin( aOrigin )
488  {}
489 
490  bool operator()( const INTERSECTION& aA, const INTERSECTION& aB )
491  {
492  return ( m_origin - aA.p ).EuclideanNorm() < ( m_origin - aB.p ).EuclideanNorm();
493  }
494 
495  VECTOR2I m_origin;
496  };
497 
498  bool Intersects( const SHAPE_LINE_CHAIN& aChain ) const;
499 
509  int Intersect( const SEG& aSeg, INTERSECTIONS& aIp ) const;
510 
520  int Intersect( const SHAPE_LINE_CHAIN& aChain, INTERSECTIONS& aIp ) const;
521 
530  int PathLength( const VECTOR2I& aP ) const;
531 
540  bool PointInside( const VECTOR2I& aP ) const;
541 
549  bool PointOnEdge( const VECTOR2I& aP ) const;
550 
559  bool CheckClearance( const VECTOR2I& aP, const int aDist) const;
560 
567  const OPT<INTERSECTION> SelfIntersecting() const;
568 
576 
583  const VECTOR2I NearestPoint( const VECTOR2I& aP ) const;
584 
594  const VECTOR2I NearestPoint( const SEG& aSeg, int& dist ) const;
595 
597  const std::string Format() const override;
598 
600  bool Parse( std::stringstream& aStream ) override;
601 
602  bool operator!=( const SHAPE_LINE_CHAIN& aRhs ) const
603  {
604  if( PointCount() != aRhs.PointCount() )
605  return true;
606 
607  for( int i = 0; i < PointCount(); i++ )
608  {
609  if( CPoint( i ) != aRhs.CPoint( i ) )
610  return true;
611  }
612 
613  return false;
614  }
615 
616  bool CompareGeometry( const SHAPE_LINE_CHAIN& aOther ) const;
617 
618  void Move( const VECTOR2I& aVector ) override
619  {
620  for( std::vector<VECTOR2I>::iterator i = m_points.begin(); i != m_points.end(); ++i )
621  (*i) += aVector;
622  }
623 
630  void Rotate( double aAngle, const VECTOR2I& aCenter );
631 
632  bool IsSolid() const override
633  {
634  return false;
635  }
636 
637  const VECTOR2I PointAlong( int aPathLength ) const;
638 
639  double Area() const;
640 
641 private:
643  std::vector<VECTOR2I> m_points;
644 
646  bool m_closed;
647 
649  BOX2I m_bbox;
650 };
651 
652 #endif // __SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN::INTERSECTION::p
VECTOR2I p
point of intersection between our and their.
Definition: shape_line_chain.h:66
SHAPE_LINE_CHAIN::NearestPoint
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: shape_line_chain.cpp:537
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN(const SHAPE_LINE_CHAIN &aShape)
Copy Constructor.
Definition: shape_line_chain.h:82
SHAPE_LINE_CHAIN::Intersect
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
Definition: shape_line_chain.cpp:242
SHAPE_LINE_CHAIN::CLastPoint
const VECTOR2I & CLastPoint() const
Returns the last point in the line chain.
Definition: shape_line_chain.h:274
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::Append
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
Definition: shape_line_chain.h:346
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:90
SHAPE_LINE_CHAIN::Clear
void Clear()
Function Clear() Removes all points from the line chain.
Definition: shape_line_chain.h:137
SHAPE_LINE_CHAIN::Format
const std::string Format() const override
Definition: shape_line_chain.cpp:577
SHAPE_LINE_CHAIN::Segment
SEG Segment(int aIndex)
Function Segment()
Definition: shape_line_chain.h:199
SHAPE_LINE_CHAIN::Slice
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Definition: shape_line_chain.cpp:210
SHAPE_LINE_CHAIN::Point
VECTOR2I & Point(int aIndex)
Function Point()
Definition: shape_line_chain.h:238
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:171
SHAPE_LINE_CHAIN::Replace
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
Definition: shape_line_chain.cpp:95
SHAPE_LINE_CHAIN::Remove
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
Definition: shape_line_chain.cpp:126
SHAPE_LINE_CHAIN::CSegment
const SEG CSegment(int aIndex) const
Function CSegment()
Definition: shape_line_chain.h:218
VECTOR2< int >
SHAPE_LINE_CHAIN::SetClosed
void SetClosed(bool aClosed)
Function SetClosed()
Definition: shape_line_chain.h:150
SHAPE_LINE_CHAIN::SelfIntersecting
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
Definition: shape_line_chain.cpp:420
SHAPE_LINE_CHAIN::PointInside
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
Definition: shape_line_chain.cpp:333
SHAPE_LINE_CHAIN::LastPoint
VECTOR2I & LastPoint()
Returns the last point in the line chain.
Definition: shape_line_chain.h:266
SHAPE_LINE_CHAIN::Append
void Append(const SHAPE_LINE_CHAIN &aOtherLine)
Function Append()
Definition: shape_line_chain.h:379
SHAPE_LINE_CHAIN::BBox
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_line_chain.h:280
SHAPE_LINE_CHAIN::Clone
SHAPE * Clone() const override
Function Clone()
Definition: shape_line_chain.cpp:613
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:39
SHAPE_LINE_CHAIN::INTERSECTION::their
SEG their
segment belonging from the aOther argument of Intersect()
Definition: shape_line_chain.h:64
SHAPE_LINE_CHAIN::Distance
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
Definition: shape_line_chain.cpp:138
SHAPE_LINE_CHAIN::PointCount
int PointCount() const
Function PointCount()
Definition: shape_line_chain.h:186
SHAPE_LINE_CHAIN::PointOnEdge
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
Definition: shape_line_chain.cpp:367
SHAPE_LINE_CHAIN::CPoint
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
Definition: shape_line_chain.h:253
SHAPE_LINE_CHAIN::IsClosed
bool IsClosed() const
Function IsClosed()
Definition: shape_line_chain.h:160
BOX2< VECTOR2I >
SEG
Definition: seg.h:36
SHAPE_LINE_CHAIN::compareOriginDistance
Definition: shape_line_chain.h:484
SHAPE_LINE_CHAIN::INTERSECTION::our
SEG our
segment belonging from the (this) argument of Intersect()
Definition: shape_line_chain.h:62
SHAPE_LINE_CHAIN::INTERSECTION
Struct INTERSECTION.
Definition: shape_line_chain.h:59
SHAPE_LINE_CHAIN::Parse
bool Parse(std::stringstream &aStream) override
Definition: shape_line_chain.cpp:618
SHAPE_LINE_CHAIN::Find
int Find(const VECTOR2I &aP) const
Function Find()
Definition: shape_line_chain.cpp:190
SHAPE_LINE_CHAIN::PathLength
int PathLength(const VECTOR2I &aP) const
Function PathLength()
Definition: shape_line_chain.cpp:311
SHAPE_LINE_CHAIN::CheckClearance
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
Definition: shape_line_chain.cpp:397
SHAPE_LINE_CHAIN::Append
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Function Append()
Definition: shape_line_chain.h:361
SHAPE_LINE_CHAIN::Split
int Split(const VECTOR2I &aP)
Function Split()
Definition: shape_line_chain.cpp:152
SHAPE_LINE_CHAIN
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:47
SHAPE_LINE_CHAIN::Simplify
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
Definition: shape_line_chain.cpp:468
SHAPE
Class SHAPE.
Definition: shape.h:58
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:84
SHAPE_LINE_CHAIN::Remove
void Remove(int aIndex)
Function Remove() removes the aIndex-th point from the line chain.
Definition: shape_line_chain.h:440
SHAPE_LINE_CHAIN::Collide
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
Definition: shape_line_chain.cpp:31
SHAPE_LINE_CHAIN::FindSegment
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
Definition: shape_line_chain.cpp:200
SHAPE_LINE_CHAIN::Reverse
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
Definition: shape_line_chain.cpp:73
SHAPE_LINE_CHAIN::SHAPE_LINE_CHAIN
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
Definition: shape_line_chain.h:75