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
49class SHAPE_LINE_CHAIN : public SHAPE
50{
51private:
52 typedef std::vector<VECTOR2I>::iterator point_iter;
53 typedef std::vector<VECTOR2I>::const_iterator point_citer;
54
55public:
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
700private:
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
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
void Compute(const Container &aPointList)
Compute the bounding box from a given list of points.
Definition: box2.h:89
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
Definition: seg.h:37
Class SHAPE_LINE_CHAIN.
Definition: shape_line_chain.h:50
const SHAPE_LINE_CHAIN Reverse() const
Function Reverse()
Definition: shape_line_chain.cpp:91
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
Definition: shape_line_chain.cpp:384
void Remove(int aIndex)
Function Remove() removes the aIndex-th point from the line chain.
Definition: shape_line_chain.h:477
int Width() const
Gets the current width of the segments in the chain.
Definition: shape_line_chain.h:192
void Append(const VECTOR2I &aP, bool aAllowDuplication=false)
Function Append()
Definition: shape_line_chain.h:398
bool Parse(std::stringstream &aStream) override
Definition: shape_line_chain.cpp:633
bool CheckClearance(const VECTOR2I &aP, const int aDist) const
Function CheckClearance()
Definition: shape_line_chain.cpp:412
const std::string Format() const override
Definition: shape_line_chain.cpp:592
int Find(const VECTOR2I &aP) const
Function Find()
Definition: shape_line_chain.cpp:208
int Split(const VECTOR2I &aP)
Function Split()
Definition: shape_line_chain.cpp:170
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
void SetClosed(bool aClosed)
Function SetClosed()
Definition: shape_line_chain.h:164
const VECTOR2I NearestPoint(const VECTOR2I &aP) const
Function NearestPoint()
Definition: shape_line_chain.cpp:552
int Length() const
Function Length()
Definition: shape_line_chain.cpp:102
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
int Intersect(const SEG &aSeg, INTERSECTIONS &aIp) const
Function Intersect()
Definition: shape_line_chain.cpp:260
void Append(const SHAPE_LINE_CHAIN &aOtherLine)
Function Append()
Definition: shape_line_chain.h:416
SHAPE_LINE_CHAIN()
Constructor Initializes an empty line chain.
Definition: shape_line_chain.h:77
int PointCount() const
Function PointCount()
Definition: shape_line_chain.h:218
int FindSegment(const VECTOR2I &aP) const
Function FindSegment()
Definition: shape_line_chain.cpp:218
void Replace(int aStartIndex, int aEndIndex, const VECTOR2I &aP)
Function Replace()
Definition: shape_line_chain.cpp:113
const OPT< INTERSECTION > SelfIntersecting() const
Function SelfIntersecting()
Definition: shape_line_chain.cpp:435
void Clear()
Function Clear() Removes all points from the line chain.
Definition: shape_line_chain.h:151
const SHAPE_LINE_CHAIN Slice(int aStartIndex, int aEndIndex=-1) const
Function Slice()
Definition: shape_line_chain.cpp:228
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
Definition: shape_line_chain.h:383
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
Definition: shape_line_chain.h:285
SHAPE_LINE_CHAIN & Simplify()
Function Simplify()
Definition: shape_line_chain.cpp:483
int EdgeContainingPoint(const VECTOR2I &aP) const
Function EdgeContainingPoint()
Definition: shape_line_chain.cpp:389
int SegmentCount() const
Function SegmentCount()
Definition: shape_line_chain.h:203
int Distance(const VECTOR2I &aP, bool aOutlineOnly=false) const
Function Distance()
Definition: shape_line_chain.cpp:156
const VECTOR2I & CLastPoint() const
Returns the last point in the line chain.
Definition: shape_line_chain.h:311
VECTOR2I & Point(int aIndex)
Function Point()
Definition: shape_line_chain.h:270
bool IsClosed() const
Function IsClosed()
Definition: shape_line_chain.h:174
SHAPE_LINE_CHAIN(const SHAPE_LINE_CHAIN &aShape)
Copy Constructor.
Definition: shape_line_chain.h:83
VECTOR2I & LastPoint()
Returns the last point in the line chain.
Definition: shape_line_chain.h:303
void Remove(int aStartIndex, int aEndIndex)
Function Remove()
Definition: shape_line_chain.cpp:144
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide()
Definition: shape_line_chain.cpp:49
const SEG CSegment(int aIndex) const
Function CSegment()
Definition: shape_line_chain.h:250
int PathLength(const VECTOR2I &aP) const
Function PathLength()
Definition: shape_line_chain.cpp:329
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
Definition: shape_line_chain.cpp:57
void SetWidth(int aWidth)
Sets the width of all segments in the chain.
Definition: shape_line_chain.h:183
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
Definition: shape_line_chain.cpp:351
const BOX2I BBox(int aClearance=0) const override
Function BBox()
Definition: shape_line_chain.h:317
SHAPE * Clone() const override
Function Clone()
Definition: shape_line_chain.cpp:628
void convertFromClipper(const ClipperLib::Path &aPath)
Function convertFromClipper() Appends the Clipper path to the current SHAPE_LINE_CHAIN.
SEG Segment(int aIndex)
Function Segment()
Definition: shape_line_chain.h:231
Class SHAPE.
Definition: shape.h:59
Struct INTERSECTION.
Definition: shape_line_chain.h:62
SEG their
segment belonging from the aOther argument of Intersect()
Definition: shape_line_chain.h:66
VECTOR2I p
point of intersection between our and their.
Definition: shape_line_chain.h:68
SEG our
segment belonging from the (this) argument of Intersect()
Definition: shape_line_chain.h:64
Definition: shape_line_chain.h:522