Horizon
shape_poly_set.h
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2019 CERN
5  * Copyright (C) 2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
8  * @author Alejandro García Montoro <alejandro.garciamontoro@gmail.com>
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 #ifndef __SHAPE_POLY_SET_H
29 #define __SHAPE_POLY_SET_H
30 
31 #include <cstdio>
32 #include <deque> // for deque
33 #include <vector> // for vector
34 #include <iosfwd> // for string, stringstream
35 #include <memory>
36 #include <set> // for set
37 #include <stdexcept> // for out_of_range
38 #include <stdlib.h> // for abs
39 #include <vector>
40 
41 #include "router/clipper_kicad/clipper.hpp" // for ClipType, PolyTree (ptr only)
42 #include <geometry/seg.h> // for SEG
43 #include <geometry/shape.h>
44 #include <geometry/shape_line_chain.h>
45 #include <math/box2.h> // for BOX2I
46 #include <math/vector2d.h> // for VECTOR2I
47 #include <md5_hash.h>
48 
49 
64 class SHAPE_POLY_SET : public SHAPE
65 {
66 public:
70  typedef std::vector<SHAPE_LINE_CHAIN> POLYGON;
71 
73  {
74  public:
75  struct TRI : public SHAPE_LINE_CHAIN_BASE
76  {
77  TRI( int _a = 0, int _b = 0, int _c = 0, TRIANGULATED_POLYGON* aParent = nullptr ) :
78  SHAPE_LINE_CHAIN_BASE( SH_POLY_SET_TRIANGLE ),
79  a( _a ),
80  b( _b ),
81  c( _c ),
82  parent( aParent )
83  {
84  }
85 
86  virtual void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override {};
87 
88  virtual void Move( const VECTOR2I& aVector ) override {};
89 
90  virtual bool IsSolid() const override { return true; }
91 
92  virtual bool IsClosed() const override { return true; }
93 
94  virtual const BOX2I BBox( int aClearance = 0 ) const override;
95 
96  virtual const VECTOR2I GetPoint( int aIndex ) const override
97  {
98  switch(aIndex)
99  {
100  case 0: return parent->m_vertices[a];
101  case 1: return parent->m_vertices[b];
102  case 2: return parent->m_vertices[c];
103  default: assert(false);
104  }
105  return VECTOR2I(0, 0);
106  }
107 
108  virtual const SEG GetSegment( int aIndex ) const override
109  {
110  switch(aIndex)
111  {
112  case 0: return SEG( parent->m_vertices[a], parent->m_vertices[b] );
113  case 1: return SEG( parent->m_vertices[b], parent->m_vertices[c] );
114  case 2: return SEG( parent->m_vertices[c], parent->m_vertices[a] );
115  default: assert(false);
116  }
117  return SEG();
118  }
119 
120  virtual size_t GetPointCount() const override { return 3; }
121  virtual size_t GetSegmentCount() const override { return 3; }
122 
123 
124  int a, b, c;
125  TRIANGULATED_POLYGON* parent;
126  };
127 
128  TRIANGULATED_POLYGON();
129  TRIANGULATED_POLYGON( const TRIANGULATED_POLYGON& aOther );
130  ~TRIANGULATED_POLYGON();
131 
132  void Clear()
133  {
134  m_vertices.clear();
135  m_triangles.clear();
136  }
137 
138  void GetTriangle( int index, VECTOR2I& a, VECTOR2I& b, VECTOR2I& c ) const
139  {
140  auto tri = m_triangles[ index ];
141  a = m_vertices[ tri.a ];
142  b = m_vertices[ tri.b ];
143  c = m_vertices[ tri.c ];
144  }
145 
146  TRIANGULATED_POLYGON& operator=( const TRIANGULATED_POLYGON& aOther );
147 
148  void AddTriangle( int a, int b, int c );
149 
150  void AddVertex( const VECTOR2I& aP )
151  {
152  m_vertices.push_back( aP );
153  }
154 
155  size_t GetTriangleCount() const
156  {
157  return m_triangles.size();
158  }
159 
160  std::deque<TRI>& Triangles()
161  {
162  return m_triangles;
163  }
164 
165  size_t GetVertexCount() const
166  {
167  return m_vertices.size();
168  }
169 
170  void Move( const VECTOR2I& aVec )
171  {
172  for( auto& vertex : m_vertices )
173  vertex += aVec;
174  }
175 
176  private:
177  std::deque<TRI> m_triangles;
178  std::deque<VECTOR2I> m_vertices;
179  };
180 
187  {
188  int m_polygon;
189  int m_contour;
190  int m_vertex;
192  VERTEX_INDEX() :
193  m_polygon(-1),
194  m_contour(-1),
195  m_vertex(-1)
196  {
197  }
198  };
199 
203  template <class T>
205  {
206  public:
207 
212  bool IsEndContour() const
213  {
214  return m_currentVertex + 1 ==
215  m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount();
216  }
217 
221  bool IsLastPolygon() const
222  {
223  return m_currentPolygon == m_lastPolygon;
224  }
225 
226  operator bool() const
227  {
228  if( m_currentPolygon < m_lastPolygon )
229  return true;
230 
231  if( m_currentPolygon != m_poly->OutlineCount() - 1 )
232  return false;
233 
234  const auto& currentPolygon = m_poly->CPolygon( m_currentPolygon );
235 
236  return m_currentContour < (int) currentPolygon.size() - 1
237  || m_currentVertex < currentPolygon[m_currentContour].PointCount();
238  }
239 
244  void Advance()
245  {
246  // Advance vertex index
247  m_currentVertex ++;
248 
249  // Check whether the user wants to iterate through the vertices of the holes
250  // and behave accordingly
251  if( m_iterateHoles )
252  {
253  // If the last vertex of the contour was reached, advance the contour index
254  if( m_currentVertex >=
255  m_poly->CPolygon( m_currentPolygon )[m_currentContour].PointCount() )
256  {
257  m_currentVertex = 0;
258  m_currentContour++;
259 
260  // If the last contour of the current polygon was reached, advance the
261  // outline index
262  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
263 
264  if( m_currentContour >= totalContours )
265  {
266  m_currentContour = 0;
267  m_currentPolygon++;
268  }
269  }
270  }
271  else
272  {
273  // If the last vertex of the outline was reached, advance to the following polygon
274  if( m_currentVertex >= m_poly->CPolygon( m_currentPolygon )[0].PointCount() )
275  {
276  m_currentVertex = 0;
277  m_currentPolygon++;
278  }
279  }
280  }
281 
282  void operator++( int dummy )
283  {
284  Advance();
285  }
286 
287  void operator++()
288  {
289  Advance();
290  }
291 
292  const T& Get()
293  {
294  return m_poly->Polygon( m_currentPolygon )[m_currentContour].CPoint( m_currentVertex );
295  }
296 
297  const T& operator*()
298  {
299  return Get();
300  }
301 
302  const T* operator->()
303  {
304  return &Get();
305  }
306 
311  {
312  VERTEX_INDEX index;
313 
314  index.m_polygon = m_currentPolygon;
315  index.m_contour = m_currentContour;
316  index.m_vertex = m_currentVertex;
317 
318  return index;
319  }
320 
321  private:
322  friend class SHAPE_POLY_SET;
323 
324  SHAPE_POLY_SET* m_poly;
325  int m_currentPolygon;
326  int m_currentContour;
327  int m_currentVertex;
328  int m_lastPolygon;
329  bool m_iterateHoles;
330  };
331 
335  template <class T>
337  {
338  public:
342  bool IsLastPolygon() const
343  {
344  return m_currentPolygon == m_lastPolygon;
345  }
346 
347  operator bool() const
348  {
349  return m_currentPolygon <= m_lastPolygon;
350  }
351 
356  void Advance()
357  {
358  // Advance vertex index
359  m_currentSegment++;
360  int last;
361 
362  // Check whether the user wants to iterate through the vertices of the holes
363  // and behave accordingly.
364  if( m_iterateHoles )
365  {
366  last = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
367 
368  // If the last vertex of the contour was reached, advance the contour index.
369  if( m_currentSegment >= last )
370  {
371  m_currentSegment = 0;
372  m_currentContour++;
373 
374  // If the last contour of the current polygon was reached, advance the
375  // outline index.
376  int totalContours = m_poly->CPolygon( m_currentPolygon ).size();
377 
378  if( m_currentContour >= totalContours )
379  {
380  m_currentContour = 0;
381  m_currentPolygon++;
382  }
383  }
384  }
385  else
386  {
387  last = m_poly->CPolygon( m_currentPolygon )[0].SegmentCount();
388  // If the last vertex of the outline was reached, advance to the following
389  // polygon
390  if( m_currentSegment >= last )
391  {
392  m_currentSegment = 0;
393  m_currentPolygon++;
394  }
395  }
396  }
397 
398  void operator++( int dummy )
399  {
400  Advance();
401  }
402 
403  void operator++()
404  {
405  Advance();
406  }
407 
408  T Get()
409  {
410  return m_poly->Polygon( m_currentPolygon )[m_currentContour].Segment( m_currentSegment );
411  }
412 
413  T operator*()
414  {
415  return Get();
416  }
417 
422  {
423  VERTEX_INDEX index;
424 
425  index.m_polygon = m_currentPolygon;
426  index.m_contour = m_currentContour;
427  index.m_vertex = m_currentSegment;
428 
429  return index;
430  }
431 
438  {
439  // Check that both iterators point to the same contour of the same polygon of the
440  // same polygon set.
441  if( m_poly == aOther.m_poly && m_currentPolygon == aOther.m_currentPolygon &&
442  m_currentContour == aOther.m_currentContour )
443  {
444  // Compute the total number of segments.
445  int numSeg;
446  numSeg = m_poly->CPolygon( m_currentPolygon )[m_currentContour].SegmentCount();
447 
448  // Compute the difference of the segment indices. If it is exactly one, they
449  // are adjacent. The only missing case where they also are adjacent is when
450  // the segments are the first and last one, in which case the difference
451  // always equals the total number of segments minus one.
452  int indexDiff = std::abs( m_currentSegment - aOther.m_currentSegment );
453 
454  return ( indexDiff == 1 ) || ( indexDiff == (numSeg - 1) );
455  }
456 
457  return false;
458  }
459 
460  private:
461  friend class SHAPE_POLY_SET;
462 
463  SHAPE_POLY_SET* m_poly;
464  int m_currentPolygon;
465  int m_currentContour;
466  int m_currentSegment;
467  int m_lastPolygon;
468  bool m_iterateHoles;
469  };
470 
471  // Iterator and const iterator types to visit polygon's points.
472  typedef ITERATOR_TEMPLATE<VECTOR2I> ITERATOR;
473  typedef ITERATOR_TEMPLATE<const VECTOR2I> CONST_ITERATOR;
474 
475  // Iterator and const iterator types to visit polygon's edges.
476  typedef SEGMENT_ITERATOR_TEMPLATE<SEG> SEGMENT_ITERATOR;
477  typedef SEGMENT_ITERATOR_TEMPLATE<const SEG> CONST_SEGMENT_ITERATOR;
478 
479  SHAPE_POLY_SET();
480 
481  SHAPE_POLY_SET( const BOX2D& aRect );
482 
488  SHAPE_POLY_SET( const SHAPE_LINE_CHAIN& aOutline );
489 
496  SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther );
497 
498  ~SHAPE_POLY_SET();
499 
500  SHAPE_POLY_SET& operator=( const SHAPE_POLY_SET& aOther );
501 
502  void CacheTriangulation( bool aPartition = true );
503  bool IsTriangulationUpToDate() const;
504 
505  MD5_HASH GetHash() const;
506 
507  virtual bool HasIndexableSubshapes() const override;
508 
509  virtual size_t GetIndexableSubshapeCount() const override;
510 
511  virtual void GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes ) override;
512 
524  bool GetRelativeIndices( int aGlobalIdx, VERTEX_INDEX* aRelativeIndices ) const;
525 
535  bool GetGlobalIndex( VERTEX_INDEX aRelativeIndices, int& aGlobalIdx ) const;
536 
538  SHAPE* Clone() const override;
539 
541  int NewOutline();
542 
544  int NewHole( int aOutline = -1 );
545 
547  int AddOutline( const SHAPE_LINE_CHAIN& aOutline );
548 
550  int AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline = -1 );
551 
553  double Area();
554 
556  int ArcCount() const;
557 
559  void GetArcs( std::vector<SHAPE_ARC>& aArcBuffer ) const;
560 
562  void ClearArcs();
563 
565 
577  int Append( int x, int y, int aOutline = -1, int aHole = -1, bool aAllowDuplication = false );
578 
580  void Append( const SHAPE_POLY_SET& aSet );
581 
583  void Append( const VECTOR2I& aP, int aOutline = -1, int aHole = -1 );
584 
593  int Append( SHAPE_ARC& aArc, int aOutline = -1, int aHole = -1 );
594 
602  void InsertVertex( int aGlobalIndex, const VECTOR2I& aNewVertex );
603 
605  const VECTOR2I& CVertex( int aIndex, int aOutline, int aHole ) const;
606 
608  const VECTOR2I& CVertex( int aGlobalIndex ) const;
609 
611  const VECTOR2I& CVertex( VERTEX_INDEX aIndex ) const;
612 
626  bool GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext );
627 
634  bool IsPolygonSelfIntersecting( int aPolygonIndex ) const;
635 
641  bool IsSelfIntersecting() const;
642 
644  unsigned int TriangulatedPolyCount() const { return m_triangulatedPolys.size(); }
645 
647  int OutlineCount() const { return m_polys.size(); }
648 
650  int VertexCount( int aOutline = -1, int aHole = -1 ) const;
651 
654  int FullPointCount() const;
655 
657  int HoleCount( int aOutline ) const
658  {
659  if( ( aOutline < 0 ) || ( aOutline >= (int) m_polys.size() )
660  || ( m_polys[aOutline].size() < 2 ) )
661  return 0;
662 
663  // the first polygon in m_polys[aOutline] is the main contour,
664  // only others are holes:
665  return m_polys[aOutline].size() - 1;
666  }
667 
669  SHAPE_LINE_CHAIN& Outline( int aIndex )
670  {
671  return m_polys[aIndex][0];
672  }
673 
674  const SHAPE_LINE_CHAIN& Outline( int aIndex ) const
675  {
676  return m_polys[aIndex][0];
677  }
678 
688  SHAPE_POLY_SET Subset( int aFirstPolygon, int aLastPolygon );
689 
690  SHAPE_POLY_SET UnitSet( int aPolygonIndex )
691  {
692  return Subset( aPolygonIndex, aPolygonIndex + 1 );
693  }
694 
696  SHAPE_LINE_CHAIN& Hole( int aOutline, int aHole )
697  {
698  return m_polys[aOutline][aHole + 1];
699  }
700 
702  POLYGON& Polygon( int aIndex )
703  {
704  return m_polys[aIndex];
705  }
706 
707  const POLYGON& Polygon( int aIndex ) const
708  {
709  return m_polys[aIndex];
710  }
711 
712  const TRIANGULATED_POLYGON* TriangulatedPolygon( int aIndex ) const
713  {
714  return m_triangulatedPolys[aIndex].get();
715  }
716 
717  const SHAPE_LINE_CHAIN& COutline( int aIndex ) const
718  {
719  return m_polys[aIndex][0];
720  }
721 
722  const SHAPE_LINE_CHAIN& CHole( int aOutline, int aHole ) const
723  {
724  return m_polys[aOutline][aHole + 1];
725  }
726 
727  const POLYGON& CPolygon( int aIndex ) const
728  {
729  return m_polys[aIndex];
730  }
731 
742  ITERATOR Iterate( int aFirst, int aLast, bool aIterateHoles = false )
743  {
744  ITERATOR iter;
745 
746  iter.m_poly = this;
747  iter.m_currentPolygon = aFirst;
748  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
749  iter.m_currentContour = 0;
750  iter.m_currentVertex = 0;
751  iter.m_iterateHoles = aIterateHoles;
752 
753  return iter;
754  }
755 
761  ITERATOR Iterate( int aOutline )
762  {
763  return Iterate( aOutline, aOutline );
764  }
765 
771  ITERATOR IterateWithHoles( int aOutline )
772  {
773  return Iterate( aOutline, aOutline, true );
774  }
775 
781  {
782  return Iterate( 0, OutlineCount() - 1 );
783  }
784 
790  {
791  return Iterate( 0, OutlineCount() - 1, true );
792  }
793 
794 
795  CONST_ITERATOR CIterate( int aFirst, int aLast, bool aIterateHoles = false ) const
796  {
797  CONST_ITERATOR iter;
798 
799  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
800  iter.m_currentPolygon = aFirst;
801  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
802  iter.m_currentContour = 0;
803  iter.m_currentVertex = 0;
804  iter.m_iterateHoles = aIterateHoles;
805 
806  return iter;
807  }
808 
809  CONST_ITERATOR CIterate( int aOutline ) const
810  {
811  return CIterate( aOutline, aOutline );
812  }
813 
814  CONST_ITERATOR CIterateWithHoles( int aOutline ) const
815  {
816  return CIterate( aOutline, aOutline, true );
817  }
818 
819  CONST_ITERATOR CIterate() const
820  {
821  return CIterate( 0, OutlineCount() - 1 );
822  }
823 
824  CONST_ITERATOR CIterateWithHoles() const
825  {
826  return CIterate( 0, OutlineCount() - 1, true );
827  }
828 
830  {
831  // Build iterator
832  ITERATOR iter = IterateWithHoles();
833 
834  // Get the relative indices of the globally indexed vertex
835  VERTEX_INDEX indices;
836 
837  if( !GetRelativeIndices( aGlobalIdx, &indices ) )
838  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
839 
840  // Adjust where the iterator is pointing
841  iter.m_currentPolygon = indices.m_polygon;
842  iter.m_currentContour = indices.m_contour;
843  iter.m_currentVertex = indices.m_vertex;
844 
845  return iter;
846  }
847 
850  SEGMENT_ITERATOR IterateSegments( int aFirst, int aLast, bool aIterateHoles = false )
851  {
852  SEGMENT_ITERATOR iter;
853 
854  iter.m_poly = this;
855  iter.m_currentPolygon = aFirst;
856  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
857  iter.m_currentContour = 0;
858  iter.m_currentSegment = 0;
859  iter.m_iterateHoles = aIterateHoles;
860 
861  return iter;
862  }
863 
866  CONST_SEGMENT_ITERATOR CIterateSegments( int aFirst, int aLast,
867  bool aIterateHoles = false ) const
868  {
870 
871  iter.m_poly = const_cast<SHAPE_POLY_SET*>( this );
872  iter.m_currentPolygon = aFirst;
873  iter.m_lastPolygon = aLast < 0 ? OutlineCount() - 1 : aLast;
874  iter.m_currentContour = 0;
875  iter.m_currentSegment = 0;
876  iter.m_iterateHoles = aIterateHoles;
877 
878  return iter;
879  }
880 
883  {
884  return IterateSegments( aPolygonIdx, aPolygonIdx );
885  }
886 
888  CONST_SEGMENT_ITERATOR CIterateSegments( int aPolygonIdx ) const
889  {
890  return CIterateSegments( aPolygonIdx, aPolygonIdx );
891  }
892 
895  {
896  return IterateSegments( 0, OutlineCount() - 1 );
897  }
898 
901  {
902  return CIterateSegments( 0, OutlineCount() - 1 );
903  }
904 
907  {
908  return IterateSegments( 0, OutlineCount() - 1, true );
909  }
910 
913  {
914  return IterateSegments( aOutline, aOutline, true );
915  }
916 
919  {
920  return CIterateSegments( 0, OutlineCount() - 1, true );
921  }
922 
924  CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles( int aOutline ) const
925  {
926  return CIterateSegments( aOutline, aOutline, true );
927  }
928 
938  {
939  PM_FAST = true,
940  PM_STRICTLY_SIMPLE = false
941  };
942 
945  void BooleanAdd( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
946 
949  void BooleanSubtract( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
950 
953  void BooleanIntersection( const SHAPE_POLY_SET& b, POLYGON_MODE aFastMode );
954 
957  void BooleanAdd( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
958  POLYGON_MODE aFastMode );
959 
962  void BooleanSubtract( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
963  POLYGON_MODE aFastMode );
964 
967  void BooleanIntersection( const SHAPE_POLY_SET& a, const SHAPE_POLY_SET& b,
968  POLYGON_MODE aFastMode );
969 
971  {
980  };
981 
996  void Inflate( int aAmount, int aCircleSegCount,
997  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS );
998 
999  void Deflate( int aAmount, int aCircleSegmentsCount,
1000  CORNER_STRATEGY aCornerStrategy = ROUND_ALL_CORNERS )
1001  {
1002  Inflate( -aAmount, aCircleSegmentsCount, aCornerStrategy );
1003  }
1004 
1012  void InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode );
1013 
1017  void Fracture( POLYGON_MODE aFastMode );
1018 
1021  void Unfracture( POLYGON_MODE aFastMode );
1022 
1024  bool HasHoles() const;
1025 
1027  bool HasTouchingHoles() const;
1028 
1029 
1032  void Simplify( POLYGON_MODE aFastMode );
1033 
1042  int NormalizeAreaOutlines();
1043 
1045  const std::string Format() const override;
1046 
1048  bool Parse( std::stringstream& aStream ) override;
1049 
1051  void Move( const VECTOR2I& aVector ) override;
1052 
1060  void Mirror( bool aX = true, bool aY = false, const VECTOR2I& aRef = { 0, 0 } );
1061 
1068  void Rotate( double aAngle, const VECTOR2I& aCenter = { 0, 0 } ) override;
1069 
1071  bool IsSolid() const override
1072  {
1073  return true;
1074  }
1075 
1076  const BOX2I BBox( int aClearance = 0 ) const override;
1077 
1084  bool PointOnEdge( const VECTOR2I& aP ) const;
1085 
1098  bool Collide( const SHAPE* aShape, int aClearance = 0, int* aActual = nullptr,
1099  VECTOR2I* aLocation = nullptr ) const override;
1100 
1119  bool Collide( const VECTOR2I& aP, int aClearance = 0, int* aActual = nullptr,
1120  VECTOR2I* aLocation = nullptr ) const override;
1121 
1140  bool Collide( const SEG& aSeg, int aClearance = 0, int* aActual = nullptr,
1141  VECTOR2I* aLocation = nullptr ) const override;
1142 
1153  bool CollideVertex( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1154  int aClearance = 0 ) const;
1155 
1166  bool CollideEdge( const VECTOR2I& aPoint, VERTEX_INDEX& aClosestVertex,
1167  int aClearance = 0 ) const;
1168 
1175  void BuildBBoxCaches() const;
1176 
1177  const BOX2I BBoxFromCaches() const;
1178 
1189  bool Contains( const VECTOR2I& aP, int aSubpolyIndex = -1, int aAccuracy = 0,
1190  bool aUseBBoxCaches = false ) const;
1191 
1193  bool IsEmpty() const
1194  {
1195  return m_polys.empty();
1196  }
1197 
1203  void RemoveVertex( int aGlobalIndex );
1204 
1210  void RemoveVertex( VERTEX_INDEX aRelativeIndices );
1211 
1213  void RemoveAllContours();
1214 
1223  void RemoveContour( int aContourIdx, int aPolygonIdx = -1 );
1224 
1230  int RemoveNullSegments();
1231 
1238  void SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos );
1239 
1248  void SetVertex( int aGlobalIndex, const VECTOR2I& aPos );
1249 
1251  int TotalVertices() const;
1252 
1254  void DeletePolygon( int aIdx );
1255 
1263  POLYGON ChamferPolygon( unsigned int aDistance, int aIndex );
1264 
1273  POLYGON FilletPolygon( unsigned int aRadius, int aErrorMax, int aIndex );
1274 
1281  SHAPE_POLY_SET Chamfer( int aDistance );
1282 
1290  SHAPE_POLY_SET Fillet( int aRadius, int aErrorMax );
1291 
1302  SEG::ecoord SquaredDistanceToPolygon( VECTOR2I aPoint, int aIndex,
1303  VECTOR2I* aNearest ) const;
1304 
1317  SEG::ecoord SquaredDistanceToPolygon( const SEG& aSegment, int aIndex,
1318  VECTOR2I* aNearest) const;
1319 
1330  SEG::ecoord SquaredDistance( VECTOR2I aPoint, VECTOR2I* aNearest = nullptr ) const;
1331 
1343  SEG::ecoord SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest = nullptr ) const;
1344 
1351  bool IsVertexInHole( int aGlobalIdx );
1352 
1361  static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths( const std::vector<SHAPE_LINE_CHAIN>& aPaths, bool aReverseOrientation = false, bool aEvenOdd = false );
1362 
1363 private:
1364  void fractureSingle( POLYGON& paths );
1365  void unfractureSingle ( POLYGON& path );
1366  void importTree( ClipperLibKiCad::PolyTree* tree,
1367  const std::vector<CLIPPER_Z_VALUE>& aZValueBuffer,
1368  const std::vector<SHAPE_ARC>& aArcBuffe );
1369 
1382  void booleanOp( ClipperLibKiCad::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
1383  POLYGON_MODE aFastMode );
1384 
1385  void booleanOp( ClipperLibKiCad::ClipType aType, const SHAPE_POLY_SET& aShape,
1386  const SHAPE_POLY_SET& aOtherShape, POLYGON_MODE aFastMode );
1387 
1402  bool containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1403  bool aUseBBoxCaches = false ) const;
1404 
1410  enum CORNER_MODE
1411  {
1412  CHAMFERED,
1413  FILLETED
1414  };
1415 
1429  POLYGON chamferFilletPolygon( CORNER_MODE aMode, unsigned int aDistance,
1430  int aIndex, int aErrorMax );
1431 
1433  bool hasTouchingHoles( const POLYGON& aPoly ) const;
1434 
1435  MD5_HASH checksum() const;
1436 
1437 private:
1438  typedef std::vector<POLYGON> POLYSET;
1439 
1440  POLYSET m_polys;
1441 
1442  std::vector<std::unique_ptr<TRIANGULATED_POLYGON>> m_triangulatedPolys;
1443 
1444  bool m_triangulationValid = false;
1445  MD5_HASH m_hash;
1446 };
1447 
1448 #endif // __SHAPE_POLY_SET_H
Definition: clipper.hpp:193
Definition: md5_hash.h:12
Definition: seg.h:41
Definition: shape_arc.h:36
Definition: shape.h:241
Represent a polyline containing arcs as well as line segments: A chain of connected line and/or arc s...
Definition: shape_line_chain.h:81
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
Definition: shape_poly_set.h:205
bool IsLastPolygon() const
Definition: shape_poly_set.h:221
VERTEX_INDEX GetIndex()
Definition: shape_poly_set.h:310
bool IsEndContour() const
Definition: shape_poly_set.h:212
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
Definition: shape_poly_set.h:244
Base class for iterating over all segments in a given SHAPE_POLY_SET.
Definition: shape_poly_set.h:337
bool IsLastPolygon() const
Definition: shape_poly_set.h:342
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
Definition: shape_poly_set.h:437
void Advance()
Advance the indices of the current vertex/outline/contour, checking whether the vertices in the holes...
Definition: shape_poly_set.h:356
VERTEX_INDEX GetIndex() const
Definition: shape_poly_set.h:421
Definition: shape_poly_set.h:73
Represent a set of closed polygons.
Definition: shape_poly_set.h:65
static const SHAPE_POLY_SET BuildPolysetFromOrientedPaths(const std::vector< SHAPE_LINE_CHAIN > &aPaths, bool aReverseOrientation=false, bool aEvenOdd=false)
Build a SHAPE_POLY_SET from a bunch of outlines in provided in random order.
Definition: shape_poly_set.cpp:2531
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
Definition: shape_poly_set.cpp:1956
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
Definition: shape_poly_set.cpp:2019
const std::string Format() const override
Definition: shape_poly_set.cpp:1299
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
Definition: shape_poly_set.cpp:684
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
Definition: shape_poly_set.cpp:1234
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
Definition: shape_poly_set.cpp:1422
ITERATOR IterateWithHoles(int aOutline)
Definition: shape_poly_set.h:771
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
Definition: shape_poly_set.cpp:1063
ITERATOR IterateWithHoles()
Definition: shape_poly_set.h:789
void ClearArcs()
Appends a vertex at the end of the given outline/hole (default: the last outline)
Definition: shape_poly_set.cpp:556
POLYGON_MODE
Operations on polygons use a aFastMode param if aFastMode is #PM_FAST (true) the result can be a weak...
Definition: shape_poly_set.h:938
void InsertVertex(int aGlobalIndex, const VECTOR2I &aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
Definition: shape_poly_set.cpp:276
CORNER_STRATEGY
< define how inflate transform build inflated polygon
Definition: shape_poly_set.h:971
@ ALLOW_ACUTE_CORNERS
just inflate the polygon. Acute angles create spikes
Definition: shape_poly_set.h:972
@ CHAMFER_ACUTE_CORNERS
Acute angles are chamfered.
Definition: shape_poly_set.h:973
@ ROUND_ACUTE_CORNERS
Acute angles are rounded.
Definition: shape_poly_set.h:974
@ CHAMFER_ALL_CORNERS
All angles are chamfered.
Definition: shape_poly_set.h:975
@ ROUND_ALL_CORNERS
All angles are rounded.
Definition: shape_poly_set.h:978
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
Definition: shape_poly_set.cpp:480
int VertexCount(int aOutline=-1, int aHole=-1) const
Return the number of points in the shape poly set.
Definition: shape_poly_set.cpp:298
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
Definition: shape_poly_set.h:696
double Area()
Count the number of arc shapes present.
Definition: shape_poly_set.cpp:513
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Accessor function to set the position of a specific point.
Definition: shape_poly_set.cpp:1784
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
Definition: shape_poly_set.cpp:678
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
Definition: shape_poly_set.cpp:1484
ITERATOR Iterate(int aOutline)
Definition: shape_poly_set.h:761
bool Parse(std::stringstream &aStream) override
Definition: shape_poly_set.cpp:1330
int TotalVertices() const
Delete aIdx-th polygon from the set.
Definition: shape_poly_set.cpp:1856
int FullPointCount() const
Returns the number of holes in a given outline.
Definition: shape_poly_set.cpp:323
void GetArcs(std::vector< SHAPE_ARC > &aArcBuffer) const
Removes all arc references from all the outlines and holes in the polyset.
Definition: shape_poly_set.cpp:543
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
Definition: shape_poly_set.cpp:2006
void Inflate(int aAmount, int aCircleSegCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
Definition: shape_poly_set.cpp:726
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
Definition: shape_poly_set.cpp:1266
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
Definition: shape_poly_set.cpp:1755
SEGMENT_ITERATOR IterateSegments(int aPolygonIdx)
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
Definition: shape_poly_set.h:882
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
Definition: shape_poly_set.cpp:1842
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
Definition: shape_poly_set.cpp:690
SEGMENT_ITERATOR IterateSegmentsWithHoles(int aOutline)
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition: shape_poly_set.h:912
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
Definition: shape_poly_set.cpp:122
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
Definition: shape_poly_set.cpp:441
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
Definition: shape_poly_set.cpp:344
SHAPE_POLY_SET UnitSet(int aPolygonIndex)
Return the reference to aHole-th hole in the aIndex-th outline.
Definition: shape_poly_set.h:690
int RemoveNullSegments()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
Definition: shape_poly_set.cpp:1583
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Definition: shape_poly_set.h:657
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
Definition: shape_poly_set.cpp:230
std::vector< SHAPE_LINE_CHAIN > POLYGON
< represents a single polygon outline with holes.
Definition: shape_poly_set.h:70
SEGMENT_ITERATOR IterateSegments()
Returns an iterator object, for all outlines in the set (no holes)
Definition: shape_poly_set.h:894
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
Definition: shape_poly_set.cpp:394
ITERATOR Iterate()
Definition: shape_poly_set.h:780
CONST_SEGMENT_ITERATOR CIterateSegments() const
Returns an iterator object, for all outlines in the set (with holes)
Definition: shape_poly_set.h:900
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
Definition: shape_poly_set.cpp:494
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
Definition: shape_poly_set.cpp:1573
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
Definition: shape_poly_set.cpp:1829
int ArcCount() const
Appends all the arcs in this polyset to aArcBuffer.
Definition: shape_poly_set.cpp:529
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.
Definition: shape_poly_set.cpp:1249
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
Definition: shape_poly_set.cpp:162
bool IsSolid() const override
Definition: shape_poly_set.h:1071
int NewOutline()
Creates a new hole in a given outline.
Definition: shape_poly_set.cpp:201
CONST_SEGMENT_ITERATOR CIterateSegments(int aPolygonIdx) const
Return an iterator object, for all outlines in the set (no holes).
Definition: shape_poly_set.h:888
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
Definition: shape_poly_set.cpp:1693
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
Definition: shape_poly_set.h:644
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
Definition: shape_poly_set.cpp:213
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
Definition: shape_poly_set.cpp:1883
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition: shape_poly_set.h:918
SEGMENT_ITERATOR IterateSegments(int aFirst, int aLast, bool aIterateHoles=false)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
Definition: shape_poly_set.h:850
ITERATOR Iterate(int aFirst, int aLast, bool aIterateHoles=false)
Return an object to iterate through the points of the polygons between aFirst and aLast.
Definition: shape_poly_set.h:742
CONST_SEGMENT_ITERATOR CIterateSegments(int aFirst, int aLast, bool aIterateHoles=false) const
Return an iterator object, for iterating aPolygonIdx-th polygon edges.
Definition: shape_poly_set.h:866
ITERATOR IterateFromVertexWithHoles(int aGlobalIdx)
Return an iterator object, for iterating between aFirst and aLast outline, with or without holes (def...
Definition: shape_poly_set.h:829
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
Definition: shape_poly_set.cpp:1654
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
Definition: shape_poly_set.cpp:1722
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
Definition: shape_poly_set.cpp:1876
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Return the aGlobalIndex-th vertex in the poly set.
Definition: shape_poly_set.cpp:357
int OutlineCount() const
Return the number of vertices in a given outline/hole.
Definition: shape_poly_set.h:647
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
Definition: shape_poly_set.cpp:2030
void Move(const VECTOR2I &aVector) override
Definition: shape_poly_set.cpp:1814
bool HasTouchingHoles() const
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
Definition: shape_poly_set.cpp:2417
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
Definition: shape_poly_set.cpp:116
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
Definition: shape_poly_set.cpp:1734
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
Definition: shape_poly_set.cpp:717
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
Definition: shape_poly_set.cpp:1870
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Return an iterator object, for the aOutline-th outline in the set (with holes).
Definition: shape_poly_set.h:906
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_poly_set.cpp:1389
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
Definition: shape_poly_set.cpp:468
An abstract shape on 2D plane.
Definition: shape.h:117
Definition: shape_poly_set.h:76
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
Definition: shape_poly_set.cpp:2479
virtual void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Definition: shape_poly_set.h:86
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
Definition: shape_poly_set.h:187
int m_vertex
Definition: shape_poly_set.h:190
int m_polygon
Definition: shape_poly_set.h:188
int m_contour
Definition: shape_poly_set.h:189