KiCad PCB EDA Suite
shape_poly_set.cpp
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) 2015-2019 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
7  *
8  * Point in polygon algorithm adapted from Clipper Library (C) Angus Johnson,
9  * subject to Clipper library license.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 #include <algorithm>
30 #include <assert.h> // for assert
31 #include <cmath> // for sqrt, cos, hypot, isinf
32 #include <cstdio>
33 #include <istream> // for operator<<, operator>>
34 #include <limits> // for numeric_limits
35 #include <memory>
36 #include <set>
37 #include <string> // for char_traits, operator!=
38 #include <type_traits> // for swap, move
39 #include <unordered_set>
40 #include <vector>
41 
42 #include <clipper.hpp> // for Clipper, PolyNode, Clipp...
45 #include <geometry/seg.h> // for SEG, OPT_VECTOR2I
46 #include <geometry/shape.h>
49 #include <math/box2.h> // for BOX2I
50 #include <math/util.h> // for KiROUND, rescale
51 #include <math/vector2d.h> // for VECTOR2I, VECTOR2D, VECTOR2
52 #include <md5_hash.h>
53 
54 
55 using namespace ClipperLib;
56 
59 {
60 }
61 
62 
63 SHAPE_POLY_SET::SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther, bool aDeepCopy ) :
64  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
65 {
66  if( aOther.IsTriangulationUpToDate() )
67  {
68  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
69  m_triangulatedPolys.push_back(
70  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
71 
72  m_hash = aOther.GetHash();
73  m_triangulationValid = true;
74  }
75 }
76 
77 
79 {
80 }
81 
82 
84 {
85  return new SHAPE_POLY_SET( *this );
86 }
87 
88 
90  SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
91 {
92  int polygonIdx = 0;
93  unsigned int contourIdx = 0;
94  int vertexIdx = 0;
95 
96  int currentGlobalIdx = 0;
97 
98  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
99  {
100  const POLYGON currentPolygon = CPolygon( polygonIdx );
101 
102  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
103  {
104  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
105  int totalPoints = currentContour.PointCount();
106 
107  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
108  {
109  // Check if the current vertex is the globally indexed as aGlobalIdx
110  if( currentGlobalIdx == aGlobalIdx )
111  {
112  aRelativeIndices->m_polygon = polygonIdx;
113  aRelativeIndices->m_contour = contourIdx;
114  aRelativeIndices->m_vertex = vertexIdx;
115 
116  return true;
117  }
118 
119  // Advance
120  currentGlobalIdx++;
121  }
122  }
123  }
124 
125  return false;
126 }
127 
128 
130  int& aGlobalIdx )
131 {
132  int selectedVertex = aRelativeIndices.m_vertex;
133  unsigned int selectedContour = aRelativeIndices.m_contour;
134  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
135 
136  // Check whether the vertex indices make sense in this poly set
137  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
138  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
139  {
140  POLYGON currentPolygon;
141 
142  aGlobalIdx = 0;
143 
144  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
145  {
146  currentPolygon = Polygon( polygonIdx );
147 
148  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
149  {
150  aGlobalIdx += currentPolygon[contourIdx].PointCount();
151  }
152  }
153 
154  currentPolygon = Polygon( selectedPolygon );
155 
156  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
157  {
158  aGlobalIdx += currentPolygon[contourIdx].PointCount();
159  }
160 
161  aGlobalIdx += selectedVertex;
162 
163  return true;
164  }
165  else
166  {
167  return false;
168  }
169 }
170 
171 
173 {
174  SHAPE_LINE_CHAIN empty_path;
175  POLYGON poly;
176 
177  empty_path.SetClosed( true );
178  poly.push_back( empty_path );
179  m_polys.push_back( poly );
180  return m_polys.size() - 1;
181 }
182 
183 
184 int SHAPE_POLY_SET::NewHole( int aOutline )
185 {
186  SHAPE_LINE_CHAIN empty_path;
187 
188  empty_path.SetClosed( true );
189 
190  // Default outline is the last one
191  if( aOutline < 0 )
192  aOutline += m_polys.size();
193 
194  // Add hole to the selected outline
195  m_polys[aOutline].push_back( empty_path );
196 
197  return m_polys.back().size() - 2;
198 }
199 
200 
201 int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
202 {
203  assert( m_polys.size() );
204 
205  if( aOutline < 0 )
206  aOutline += m_polys.size();
207 
208  int idx;
209 
210  if( aHole < 0 )
211  idx = 0;
212  else
213  idx = aHole + 1;
214 
215  assert( aOutline < (int) m_polys.size() );
216  assert( idx < (int) m_polys[aOutline].size() );
217 
218  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
219 
220  return m_polys[aOutline][idx].PointCount();
221 }
222 
223 
224 void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex )
225 {
226  VERTEX_INDEX index;
227 
228  if( aGlobalIndex < 0 )
229  aGlobalIndex = 0;
230 
231  if( aGlobalIndex >= TotalVertices() )
232  {
233  Append( aNewVertex );
234  }
235  else
236  {
237  // Assure the position to be inserted exists; throw an exception otherwise
238  if( GetRelativeIndices( aGlobalIndex, &index ) )
239  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
240  else
241  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
242  }
243 }
244 
245 
246 int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
247 {
248  if( m_polys.size() == 0 ) // Empty poly set
249  return 0;
250 
251  if( aOutline < 0 ) // Use last outline
252  aOutline += m_polys.size();
253 
254  int idx;
255 
256  if( aHole < 0 )
257  idx = 0;
258  else
259  idx = aHole + 1;
260 
261  if( aOutline >= (int) m_polys.size() ) // not existing outline
262  return 0;
263 
264  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
265  return 0;
266 
267  return m_polys[aOutline][idx].PointCount();
268 }
269 
270 
271 SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
272 {
273  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
274 
275  SHAPE_POLY_SET newPolySet;
276 
277  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
278  {
279  newPolySet.m_polys.push_back( Polygon( index ) );
280  }
281 
282  return newPolySet;
283 }
284 
285 
286 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
287 {
288  if( aOutline < 0 )
289  aOutline += m_polys.size();
290 
291  int idx;
292 
293  if( aHole < 0 )
294  idx = 0;
295  else
296  idx = aHole + 1;
297 
298  assert( aOutline < (int) m_polys.size() );
299  assert( idx < (int) m_polys[aOutline].size() );
300 
301  return m_polys[aOutline][idx].CPoint( aIndex );
302 }
303 
304 
305 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
306 {
308 
309  // Assure the passed index references a legal position; abort otherwise
310  if( !GetRelativeIndices( aGlobalIndex, &index ) )
311  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
312 
313  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
314 }
315 
316 
318 {
319  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
320 }
321 
322 
323 bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext )
324 {
326 
327  // If the edge does not exist, throw an exception, it is an illegal access memory error
328  if( !GetRelativeIndices( aGlobalIndex, &index ) )
329  return false;
330 
331  // Calculate the previous and next index of aGlobalIndex, corresponding to
332  // the same contour;
333  VERTEX_INDEX inext = index;
334  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
335 
336  if( index.m_vertex == 0 )
337  {
338  index.m_vertex = lastpoint;
339  inext.m_vertex = 1;
340  }
341  else if( index.m_vertex == lastpoint )
342  {
343  index.m_vertex--;
344  inext.m_vertex = 0;
345  }
346  else
347  {
348  inext.m_vertex++;
349  index.m_vertex--;
350  }
351 
352  if( aPrevious )
353  {
354  int previous;
355  GetGlobalIndex( index, previous );
356  *aPrevious = previous;
357  }
358 
359  if( aNext )
360  {
361  int next;
362  GetGlobalIndex( inext, next );
363  *aNext = next;
364  }
365 
366  return true;
367 }
368 
369 
370 bool SHAPE_POLY_SET::IsPolygonSelfIntersecting( int aPolygonIndex ) const
371 {
372  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
373  CONST_SEGMENT_ITERATOR innerIterator;
374 
375  for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
376  {
377  SEG firstSegment = *iterator;
378 
379  // Iterate through all remaining segments.
380  innerIterator = iterator;
381 
382  // Start in the next segment, we don't want to check collision between a segment and itself
383  for( innerIterator++; innerIterator; innerIterator++ )
384  {
385  SEG secondSegment = *innerIterator;
386 
387  // Check whether the two segments built collide, only when they are not adjacent.
388  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
389  return true;
390  }
391  }
392 
393  return false;
394 }
395 
396 
398 {
399  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
400  {
401  if( IsPolygonSelfIntersecting( polygon ) )
402  return true;
403  }
404 
405  return false;
406 }
407 
408 
410 {
411  assert( aOutline.IsClosed() );
412 
413  POLYGON poly;
414 
415  poly.push_back( aOutline );
416 
417  m_polys.push_back( poly );
418 
419  return m_polys.size() - 1;
420 }
421 
422 
423 int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
424 {
425  assert( m_polys.size() );
426 
427  if( aOutline < 0 )
428  aOutline += m_polys.size();
429 
430  POLYGON& poly = m_polys[aOutline];
431 
432  assert( poly.size() );
433 
434  poly.push_back( aHole );
435 
436  return poly.size() - 1;
437 }
438 
439 
440 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
441  POLYGON_MODE aFastMode )
442 {
443  booleanOp( aType, *this, aOtherShape, aFastMode );
444 }
445 
446 
447 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
448  const SHAPE_POLY_SET& aShape,
449  const SHAPE_POLY_SET& aOtherShape,
450  POLYGON_MODE aFastMode )
451 {
452  Clipper c;
453 
454  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
455 
456  for( auto poly : aShape.m_polys )
457  {
458  for( size_t i = 0 ; i < poly.size(); i++ )
459  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
460  }
461 
462  for( auto poly : aOtherShape.m_polys )
463  {
464  for( size_t i = 0; i < poly.size(); i++ )
465  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
466  }
467 
468  PolyTree solution;
469 
470  c.Execute( aType, solution, pftNonZero, pftNonZero );
471 
472  importTree( &solution );
473 }
474 
475 
477 {
478  booleanOp( ctUnion, b, aFastMode );
479 }
480 
481 
483 {
484  booleanOp( ctDifference, b, aFastMode );
485 }
486 
487 
489 {
490  booleanOp( ctIntersection, b, aFastMode );
491 }
492 
493 
495  const SHAPE_POLY_SET& b,
496  POLYGON_MODE aFastMode )
497 {
498  booleanOp( ctUnion, a, b, aFastMode );
499 }
500 
501 
503  const SHAPE_POLY_SET& b,
504  POLYGON_MODE aFastMode )
505 {
506  booleanOp( ctDifference, a, b, aFastMode );
507 }
508 
509 
511  const SHAPE_POLY_SET& b,
512  POLYGON_MODE aFastMode )
513 {
514  booleanOp( ctIntersection, a, b, aFastMode );
515 }
516 
517 
518 void SHAPE_POLY_SET::InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount,
519  POLYGON_MODE aFastMode )
520 {
521  Simplify( aFastMode );
522  Inflate( aFactor, aCircleSegmentsCount );
523  Fracture( aFastMode );
524 }
525 
526 
527 void SHAPE_POLY_SET::Inflate( int aAmount, int aCircleSegmentsCount,
528  CORNER_STRATEGY aCornerStrategy )
529 {
530  // A static table to avoid repetitive calculations of the coefficient
531  // 1.0 - cos( M_PI / aCircleSegmentsCount )
532  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
533  #define SEG_CNT_MAX 64
534  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
535 
536  ClipperOffset c;
537 
538  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
539  // and are not what you'd think they are.
540  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
541  JoinType joinType = aCornerStrategy == ROUND_ALL_CORNERS ? jtRound : jtMiter;
542  double miterLimit = aCornerStrategy == ALLOW_ACUTE_CORNERS ? 10 : 1.5;
543  JoinType miterFallback = aCornerStrategy == ROUND_ACUTE_CORNERS ? jtRound : jtSquare;
544 
545  for( const POLYGON& poly : m_polys )
546  {
547  for( size_t i = 0; i < poly.size(); i++ )
548  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
549  }
550 
551  PolyTree solution;
552 
553  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
554  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
555  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
556 
557  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
558  aCircleSegmentsCount = 6;
559 
560  double coeff;
561 
562  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
563  {
564  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
565 
566  if( aCircleSegmentsCount <= SEG_CNT_MAX )
567  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
568  }
569  else
570  coeff = arc_tolerance_factor[aCircleSegmentsCount];
571 
572  c.ArcTolerance = std::abs( aAmount ) * coeff;
573  c.MiterLimit = miterLimit;
574  c.MiterFallback = miterFallback;
575  c.Execute( solution, aAmount );
576 
577  importTree( &solution );
578 }
579 
580 
581 void SHAPE_POLY_SET::importTree( PolyTree* tree )
582 {
583  m_polys.clear();
584 
585  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
586  {
587  if( !n->IsHole() )
588  {
589  POLYGON paths;
590  paths.reserve( n->Childs.size() + 1 );
591  paths.push_back( n->Contour );
592 
593  for( unsigned int i = 0; i < n->Childs.size(); i++ )
594  paths.push_back( n->Childs[i]->Contour );
595 
596  m_polys.push_back( paths );
597  }
598  }
599 }
600 
601 
603 {
604  FractureEdge( int y = 0 ) :
605  m_connected( false ),
606  m_next( NULL )
607  {
608  m_p1.x = m_p2.y = y;
609  }
610 
611  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
612  m_connected( connected ),
613  m_p1( p1 ),
614  m_p2( p2 ),
615  m_next( NULL )
616  {
617  }
618 
619  bool matches( int y ) const
620  {
621  return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
622  }
623 
627 };
628 
629 
630 typedef std::vector<FractureEdge*> FractureEdgeSet;
631 
632 
633 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
634 {
635  int x = edge->m_p1.x;
636  int y = edge->m_p1.y;
637  int min_dist = std::numeric_limits<int>::max();
638  int x_nearest = 0;
639 
640  FractureEdge* e_nearest = NULL;
641 
642  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
643  {
644  if( !(*i)->matches( y ) )
645  continue;
646 
647  int x_intersect;
648 
649  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
650  x_intersect = std::max( (*i)->m_p1.x, (*i)->m_p2.x );
651  else
652  x_intersect = (*i)->m_p1.x + rescale( (*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y,
653  (*i)->m_p2.y - (*i)->m_p1.y );
654 
655  int dist = ( x - x_intersect );
656 
657  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
658  {
659  min_dist = dist;
660  x_nearest = x_intersect;
661  e_nearest = (*i);
662  }
663  }
664 
665  if( e_nearest && e_nearest->m_connected )
666  {
667  int count = 0;
668 
669  FractureEdge* lead1 =
670  new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
671  FractureEdge* lead2 =
672  new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
673  FractureEdge* split_2 =
674  new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
675 
676  edges.push_back( split_2 );
677  edges.push_back( lead1 );
678  edges.push_back( lead2 );
679 
680  FractureEdge* link = e_nearest->m_next;
681 
682  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
683  e_nearest->m_next = lead1;
684  lead1->m_next = edge;
685 
686  FractureEdge* last;
687 
688  for( last = edge; last->m_next != edge; last = last->m_next )
689  {
690  last->m_connected = true;
691  count++;
692  }
693 
694  last->m_connected = true;
695  last->m_next = lead2;
696  lead2->m_next = split_2;
697  split_2->m_next = link;
698 
699  return count + 1;
700  }
701 
702  return 0;
703 }
704 
705 
707 {
708  FractureEdgeSet edges;
709  FractureEdgeSet border_edges;
710  FractureEdge* root = NULL;
711 
712  bool first = true;
713 
714  if( paths.size() == 1 )
715  return;
716 
717  int num_unconnected = 0;
718 
719  for( const SHAPE_LINE_CHAIN& path : paths )
720  {
721  const std::vector<VECTOR2I>& points = path.CPoints();
722  int pointCount = points.size();
723 
724  FractureEdge* prev = NULL, * first_edge = NULL;
725 
726  int x_min = std::numeric_limits<int>::max();
727 
728  for( const VECTOR2I& p : points )
729  {
730  if( p.x < x_min )
731  x_min = p.x;
732  }
733 
734  for( int i = 0; i < pointCount; i++ )
735  {
736  // Do not use path.CPoint() here; open-coding it using the local variables "points"
737  // and "pointCount" gives a non-trivial performance boost to zone fill times.
738  FractureEdge* fe = new FractureEdge( first, points[ i ],
739  points[ i+1 == pointCount ? 0 : i+1 ] );
740 
741  if( !root )
742  root = fe;
743 
744  if( !first_edge )
745  first_edge = fe;
746 
747  if( prev )
748  prev->m_next = fe;
749 
750  if( i == pointCount - 1 )
751  fe->m_next = first_edge;
752 
753  prev = fe;
754  edges.push_back( fe );
755 
756  if( !first )
757  {
758  if( fe->m_p1.x == x_min )
759  border_edges.push_back( fe );
760  }
761 
762  if( !fe->m_connected )
763  num_unconnected++;
764  }
765 
766  first = false; // first path is always the outline
767  }
768 
769  // keep connecting holes to the main outline, until there's no holes left...
770  while( num_unconnected > 0 )
771  {
772  int x_min = std::numeric_limits<int>::max();
773 
774  FractureEdge* smallestX = NULL;
775 
776  // find the left-most hole edge and merge with the outline
777  for( FractureEdge* border_edge : border_edges )
778  {
779  int xt = border_edge->m_p1.x;
780 
781  if( ( xt < x_min ) && !border_edge->m_connected )
782  {
783  x_min = xt;
784  smallestX = border_edge;
785  }
786  }
787 
788  num_unconnected -= processEdge( edges, smallestX );
789  }
790 
791  paths.clear();
792  SHAPE_LINE_CHAIN newPath;
793 
794  newPath.SetClosed( true );
795 
796  FractureEdge* e;
797 
798  for( e = root; e->m_next != root; e = e->m_next )
799  newPath.Append( e->m_p1 );
800 
801  newPath.Append( e->m_p1 );
802 
803  for( FractureEdge* edge : edges )
804  delete edge;
805 
806  paths.push_back( std::move( newPath ) );
807 }
808 
809 
811 {
812  Simplify( aFastMode ); // remove overlapping holes/degeneracy
813 
814  for( POLYGON& paths : m_polys )
815  {
816  fractureSingle( paths );
817  }
818 }
819 
820 
822 {
823  assert( aPoly.size() == 1 );
824 
825  struct EDGE
826  {
827  int m_index = 0;
828  SHAPE_LINE_CHAIN* m_poly = nullptr;
829  bool m_duplicate = false;
830 
831  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
832  m_index( aIndex ),
833  m_poly( aPolygon )
834  {}
835 
836  bool compareSegs( const SEG& s1, const SEG& s2 ) const
837  {
838  return (s1.A == s2.B && s1.B == s2.A);
839  }
840 
841  bool operator==( const EDGE& aOther ) const
842  {
843  return compareSegs( m_poly->CSegment( m_index ),
844  aOther.m_poly->CSegment( aOther.m_index ) );
845  }
846 
847  bool operator!=( const EDGE& aOther ) const
848  {
849  return !compareSegs( m_poly->CSegment( m_index ),
850  aOther.m_poly->CSegment( aOther.m_index ) );
851  }
852 
853  struct HASH
854  {
855  std::size_t operator()( const EDGE& aEdge ) const
856  {
857  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
858 
859  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
860  }
861  };
862  };
863 
864  struct EDGE_LIST_ENTRY
865  {
866  int index;
867  EDGE_LIST_ENTRY* next;
868  };
869 
870  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
871 
872  auto lc = aPoly[0];
873  lc.Simplify();
874 
875  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
876 
877  for( int i = 0; i < lc.SegmentCount(); i++ )
878  {
879  edgeList[i].index = i;
880  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
881  }
882 
883  std::unordered_set<EDGE_LIST_ENTRY*> queue;
884 
885  for( int i = 0; i < lc.SegmentCount(); i++ )
886  {
887  EDGE e( &lc, i );
888  uniqueEdges.insert( e );
889  }
890 
891  for( int i = 0; i < lc.SegmentCount(); i++ )
892  {
893  EDGE e( &lc, i );
894  auto it = uniqueEdges.find( e );
895 
896  if( it != uniqueEdges.end() && it->m_index != i )
897  {
898  int e1 = it->m_index;
899  int e2 = i;
900 
901  if( e1 > e2 )
902  std::swap( e1, e2 );
903 
904  int e1_prev = e1 - 1;
905 
906  if( e1_prev < 0 )
907  e1_prev = lc.SegmentCount() - 1;
908 
909  int e2_prev = e2 - 1;
910 
911  if( e2_prev < 0 )
912  e2_prev = lc.SegmentCount() - 1;
913 
914  int e1_next = e1 + 1;
915 
916  if( e1_next == lc.SegmentCount() )
917  e1_next = 0;
918 
919  int e2_next = e2 + 1;
920 
921  if( e2_next == lc.SegmentCount() )
922  e2_next = 0;
923 
924  edgeList[e1_prev].next = &edgeList[ e2_next ];
925  edgeList[e2_prev].next = &edgeList[ e1_next ];
926  edgeList[i].next = nullptr;
927  edgeList[it->m_index].next = nullptr;
928  }
929  }
930 
931  for( int i = 0; i < lc.SegmentCount(); i++ )
932  {
933  if( edgeList[i].next )
934  queue.insert( &edgeList[i] );
935  }
936 
937  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
938 
939  int n = 0;
940  int outline = -1;
941 
942  POLYGON result;
943 
944  while( queue.size() )
945  {
946  auto e_first = (*queue.begin() );
947  auto e = e_first;
948  int cnt = 0;
949 
950  do {
951  edgeBuf[cnt++] = e;
952  e = e->next;
953  } while( e && e != e_first );
954 
955  SHAPE_LINE_CHAIN outl;
956 
957  for( int i = 0; i < cnt; i++ )
958  {
959  auto p = lc.CPoint( edgeBuf[i]->index );
960  outl.Append( p );
961  queue.erase( edgeBuf[i] );
962  }
963 
964  outl.SetClosed( true );
965 
966  bool cw = outl.Area() > 0.0;
967 
968  if( cw )
969  outline = n;
970 
971  result.push_back( outl );
972  n++;
973  }
974 
975  if( outline > 0 )
976  std::swap( result[0], result[outline] );
977 
978  aPoly = result;
979 }
980 
981 
983 {
984  // Iterate through all the polygons on the set
985  for( const POLYGON& paths : m_polys )
986  {
987  // If any of them has more than one contour, it is a hole.
988  if( paths.size() > 1 )
989  return true;
990  }
991 
992  // Return false if and only if every polygon has just one outline, without holes.
993  return false;
994 }
995 
996 
998 {
999  for( POLYGON& path : m_polys )
1000  {
1001  unfractureSingle( path );
1002  }
1003 
1004  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1005 }
1006 
1007 
1009 {
1011 
1012  booleanOp( ctUnion, empty, aFastMode );
1013 }
1014 
1015 
1017 {
1018  // We are expecting only one main outline, but this main outline can have holes
1019  // if holes: combine holes and remove them from the main outline.
1020  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1021  // calculations, but it is not mandatory. It is used mainly
1022  // because there is usually only very few vertices in area outlines
1023  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1024  SHAPE_POLY_SET holesBuffer;
1025 
1026  // Move holes stored in outline to holesBuffer:
1027  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1028  while( outline.size() > 1 )
1029  {
1030  holesBuffer.AddOutline( outline.back() );
1031  outline.pop_back();
1032  }
1033 
1035 
1036  // If any hole, substract it to main outline
1037  if( holesBuffer.OutlineCount() )
1038  {
1039  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1041  }
1042 
1044 
1045  return OutlineCount();
1046 }
1047 
1048 
1049 const std::string SHAPE_POLY_SET::Format() const
1050 {
1051  std::stringstream ss;
1052 
1053  ss << "polyset " << m_polys.size() << "\n";
1054 
1055  for( unsigned i = 0; i < m_polys.size(); i++ )
1056  {
1057  ss << "poly " << m_polys[i].size() << "\n";
1058 
1059  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1060  {
1061  ss << m_polys[i][j].PointCount() << "\n";
1062 
1063  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1064  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1065  }
1066 
1067  ss << "\n";
1068  }
1069 
1070  return ss.str();
1071 }
1072 
1073 
1074 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1075 {
1076  std::string tmp;
1077 
1078  aStream >> tmp;
1079 
1080  if( tmp != "polyset" )
1081  return false;
1082 
1083  aStream >> tmp;
1084 
1085  int n_polys = atoi( tmp.c_str() );
1086 
1087  if( n_polys < 0 )
1088  return false;
1089 
1090  for( int i = 0; i < n_polys; i++ )
1091  {
1092  POLYGON paths;
1093 
1094  aStream >> tmp;
1095 
1096  if( tmp != "poly" )
1097  return false;
1098 
1099  aStream >> tmp;
1100  int n_outlines = atoi( tmp.c_str() );
1101 
1102  if( n_outlines < 0 )
1103  return false;
1104 
1105  for( int j = 0; j < n_outlines; j++ )
1106  {
1107  SHAPE_LINE_CHAIN outline;
1108 
1109  outline.SetClosed( true );
1110 
1111  aStream >> tmp;
1112  int n_vertices = atoi( tmp.c_str() );
1113 
1114  for( int v = 0; v < n_vertices; v++ )
1115  {
1116  VECTOR2I p;
1117 
1118  aStream >> tmp; p.x = atoi( tmp.c_str() );
1119  aStream >> tmp; p.y = atoi( tmp.c_str() );
1120  outline.Append( p );
1121  }
1122 
1123  paths.push_back( outline );
1124  }
1125 
1126  m_polys.push_back( paths );
1127  }
1128 
1129  return true;
1130 }
1131 
1132 
1133 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1134 {
1135  BOX2I bb;
1136 
1137  for( unsigned i = 0; i < m_polys.size(); i++ )
1138  {
1139  if( i == 0 )
1140  bb = m_polys[i][0].BBox();
1141  else
1142  bb.Merge( m_polys[i][0].BBox() );
1143  }
1144 
1145  bb.Inflate( aClearance );
1146  return bb;
1147 }
1148 
1149 
1150 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1151 {
1152  // Iterate through all the polygons in the set
1153  for( const POLYGON& polygon : m_polys )
1154  {
1155  // Iterate through all the line chains in the polygon
1156  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1157  {
1158  if( lineChain.PointOnEdge( aP ) )
1159  return true;
1160  }
1161  }
1162 
1163  return false;
1164 }
1165 
1166 
1167 bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance ) const
1168 {
1169 
1170  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1171 
1172  // Inflate the polygon if necessary.
1173  if( aClearance > 0 )
1174  {
1175  // fixme: the number of arc segments should not be hardcoded
1176  polySet.Inflate( aClearance, 8 );
1177  }
1178 
1179  // We are going to check to see if the segment crosses an external
1180  // boundary. However, if the full segment is inside the polyset, this
1181  // will not be true. So we first test to see if one of the points is
1182  // inside. If true, then we collide
1183  if( polySet.Contains( aSeg.A ) )
1184  return true;
1185 
1186  for( SEGMENT_ITERATOR it = ( (SHAPE_POLY_SET*) this )->IterateSegmentsWithHoles(); it; it++ )
1187  {
1188  SEG polygonEdge = *it;
1189 
1190  if( polygonEdge.Intersect( aSeg, true ) )
1191  return true;
1192  }
1193 
1194  return false;
1195 }
1196 
1197 
1198 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1199 {
1200  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1201 
1202  // Inflate the polygon if necessary.
1203  if( aClearance > 0 )
1204  {
1205  // fixme: the number of arc segments should not be hardcoded
1206  polySet.Inflate( aClearance, 8 );
1207  }
1208 
1209  // There is a collision if and only if the point is inside of the polygon.
1210  return polySet.Contains( aP );
1211 }
1212 
1213 
1215 {
1216  m_polys.clear();
1217 }
1218 
1219 
1220 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1221 {
1222  // Default polygon is the last one
1223  if( aPolygonIdx < 0 )
1224  aPolygonIdx += m_polys.size();
1225 
1226  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1227 }
1228 
1229 
1231 {
1232  int removed = 0;
1233 
1234  ITERATOR iterator = IterateWithHoles();
1235 
1236  VECTOR2I contourStart = *iterator;
1237  VECTOR2I segmentStart, segmentEnd;
1238 
1239  VERTEX_INDEX indexStart;
1240 
1241  while( iterator )
1242  {
1243  // Obtain first point and its index
1244  segmentStart = *iterator;
1245  indexStart = iterator.GetIndex();
1246 
1247  // Obtain last point
1248  if( iterator.IsEndContour() )
1249  {
1250  segmentEnd = contourStart;
1251 
1252  // Advance
1253  iterator++;
1254 
1255  if( iterator )
1256  contourStart = *iterator;
1257  }
1258  else
1259  {
1260  // Advance
1261  iterator++;
1262 
1263  if( iterator )
1264  segmentEnd = *iterator;
1265  }
1266 
1267  // Remove segment start if both points are equal
1268  if( segmentStart == segmentEnd )
1269  {
1270  RemoveVertex( indexStart );
1271  removed++;
1272 
1273  // Advance the iterator one position, as there is one vertex less.
1274  if( iterator )
1275  iterator++;
1276  }
1277  }
1278 
1279  return removed;
1280 }
1281 
1282 
1284 {
1285  m_polys.erase( m_polys.begin() + aIdx );
1286 }
1287 
1288 
1290 {
1291  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1292 }
1293 
1294 
1295 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1296 {
1297  Append( aP.x, aP.y, aOutline, aHole );
1298 }
1299 
1300 
1302  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1303 {
1304  // Shows whether there was a collision
1305  bool collision = false;
1306 
1307  // Difference vector between each vertex and aPoint.
1308  VECTOR2D delta;
1309  double distance, clearance;
1310 
1311  // Convert clearance to double for precission when comparing distances
1312  clearance = aClearance;
1313 
1314  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1315  {
1316  // Get the difference vector between current vertex and aPoint
1317  delta = *iterator - aPoint;
1318 
1319  // Compute distance
1320  distance = delta.EuclideanNorm();
1321 
1322  // Check for collisions
1323  if( distance <= clearance )
1324  {
1325  collision = true;
1326 
1327  // Update aClearance to look for closer vertices
1328  clearance = distance;
1329 
1330  // Store the indices that identify the vertex
1331  aClosestVertex = iterator.GetIndex();
1332  }
1333  }
1334 
1335  return collision;
1336 }
1337 
1338 
1340  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1341 {
1342  // Shows whether there was a collision
1343  bool collision = false;
1344 
1345  SEGMENT_ITERATOR iterator;
1346 
1347  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1348  {
1349  SEG currentSegment = *iterator;
1350  int distance = currentSegment.Distance( aPoint );
1351 
1352  // Check for collisions
1353  if( distance <= aClearance )
1354  {
1355  collision = true;
1356 
1357  // Update aClearance to look for closer edges
1358  aClearance = distance;
1359 
1360  // Store the indices that identify the vertex
1361  aClosestVertex = iterator.GetIndex();
1362  }
1363  }
1364 
1365  return collision;
1366 }
1367 
1368 
1370 {
1371  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1372  {
1373  Outline( polygonIdx ).GenerateBBoxCache();
1374 
1375  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1376  Hole( polygonIdx, holeIdx ).GenerateBBoxCache();
1377  }
1378 }
1379 
1380 
1381 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1382  bool aUseBBoxCaches ) const
1383 {
1384  if( m_polys.empty() )
1385  return false;
1386 
1387  // If there is a polygon specified, check the condition against that polygon
1388  if( aSubpolyIndex >= 0 )
1389  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1390 
1391  // In any other case, check it against all polygons in the set
1392  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1393  {
1394  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1395  return true;
1396  }
1397 
1398  return false;
1399 }
1400 
1401 
1402 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1403 {
1404  VERTEX_INDEX index;
1405 
1406  // Assure the to be removed vertex exists, abort otherwise
1407  if( GetRelativeIndices( aGlobalIndex, &index ) )
1408  RemoveVertex( index );
1409  else
1410  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1411 }
1412 
1413 
1415 {
1416  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1417 }
1418 
1419 
1420 void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
1421 {
1422  VERTEX_INDEX index;
1423 
1424  if( GetRelativeIndices( aGlobalIndex, &index ) )
1425  SetVertex( index, aPos );
1426  else
1427  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1428 }
1429 
1430 
1431 void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
1432 {
1433  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1434 }
1435 
1436 
1437 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1438  bool aUseBBoxCaches ) const
1439 {
1440  // Check that the point is inside the outline
1441  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1442  {
1443  // Check that the point is not in any of the holes
1444  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1445  {
1446  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1447 
1448  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1449  // here as it's meaning would be inverted.
1450  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1451  return false;
1452  }
1453 
1454  return true;
1455  }
1456 
1457  return false;
1458 }
1459 
1460 
1461 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1462 {
1463  for( POLYGON& poly : m_polys )
1464  {
1465  for( SHAPE_LINE_CHAIN& path : poly )
1466  path.Move( aVector );
1467  }
1468 }
1469 
1470 
1471 void SHAPE_POLY_SET::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
1472 {
1473  for( POLYGON& poly : m_polys )
1474  {
1475  for( SHAPE_LINE_CHAIN& path : poly )
1476  {
1477  path.Mirror( aX, aY, aRef );
1478  }
1479  }
1480 }
1481 
1482 
1483 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1484 {
1485  for( POLYGON& poly : m_polys )
1486  {
1487  for( SHAPE_LINE_CHAIN& path : poly )
1488  path.Rotate( aAngle, aCenter );
1489  }
1490 }
1491 
1492 
1494 {
1495  int c = 0;
1496 
1497  for( const POLYGON& poly : m_polys )
1498  {
1499  for( const SHAPE_LINE_CHAIN& path : poly )
1500  c += path.PointCount();
1501  }
1502 
1503  return c;
1504 }
1505 
1506 
1507 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex,
1508  std::set<VECTOR2I>* aPreserveCorners )
1509 {
1510  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0, aPreserveCorners );
1511 }
1512 
1513 
1514 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
1515  int aIndex,
1516  std::set<VECTOR2I>* aPreserveCorners )
1517 {
1518  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax, aPreserveCorners );
1519 }
1520 
1521 
1522 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1523 {
1524  // We calculate the min dist between the segment and each outline segment. However, if the
1525  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1526  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1527  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1528  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1529  return 0;
1530 
1531  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1532 
1533  SEG polygonEdge = *iterator;
1534  int minDistance = polygonEdge.Distance( aPoint );
1535 
1536  for( iterator++; iterator && minDistance > 0; iterator++ )
1537  {
1538  polygonEdge = *iterator;
1539 
1540  int currentDistance = polygonEdge.Distance( aPoint );
1541 
1542  if( currentDistance < minDistance )
1543  minDistance = currentDistance;
1544  }
1545 
1546  return minDistance;
1547 }
1548 
1549 
1550 int SHAPE_POLY_SET::DistanceToPolygon( const SEG& aSegment, int aPolygonIndex, int aSegmentWidth )
1551 {
1552  // We calculate the min dist between the segment and each outline segment. However, if the
1553  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1554  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1555  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1556  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1557  return 0;
1558 
1559  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1560 
1561  SEG polygonEdge = *iterator;
1562  int minDistance = polygonEdge.Distance( aSegment );
1563 
1564  for( iterator++; iterator && minDistance > 0; iterator++ )
1565  {
1566  polygonEdge = *iterator;
1567 
1568  int currentDistance = polygonEdge.Distance( aSegment );
1569 
1570  if( currentDistance < minDistance )
1571  minDistance = currentDistance;
1572  }
1573 
1574  // Take into account the width of the segment
1575  if( aSegmentWidth > 0 )
1576  minDistance -= aSegmentWidth / 2;
1577 
1578  // Return the maximum of minDistance and zero
1579  return minDistance < 0 ? 0 : minDistance;
1580 }
1581 
1582 
1584 {
1585  int currentDistance;
1586  int minDistance = DistanceToPolygon( aPoint, 0 );
1587 
1588  // Iterate through all the polygons and get the minimum distance.
1589  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1590  {
1591  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1592 
1593  if( currentDistance < minDistance )
1594  minDistance = currentDistance;
1595  }
1596 
1597  return minDistance;
1598 }
1599 
1600 
1601 int SHAPE_POLY_SET::Distance( const SEG& aSegment, int aSegmentWidth )
1602 {
1603  int currentDistance;
1604  int minDistance = DistanceToPolygon( aSegment, 0, aSegmentWidth );
1605 
1606  // Iterate through all the polygons and get the minimum distance.
1607  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1608  {
1609  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1610 
1611  if( currentDistance < minDistance )
1612  minDistance = currentDistance;
1613  }
1614 
1615  return minDistance;
1616 }
1617 
1618 
1619 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1620 {
1621  VERTEX_INDEX index;
1622 
1623  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1624  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1625  return false;
1626 
1627  // The contour is a hole if its index is greater than zero
1628  return index.m_contour > 0;
1629 }
1630 
1631 
1632 SHAPE_POLY_SET SHAPE_POLY_SET::Chamfer( int aDistance, std::set<VECTOR2I>* aPreserveCorners )
1633 {
1634  SHAPE_POLY_SET chamfered;
1635 
1636  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1637  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx, aPreserveCorners ) );
1638 
1639  return chamfered;
1640 }
1641 
1642 
1643 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax,
1644  std::set<VECTOR2I>* aPreserveCorners )
1645 {
1646  SHAPE_POLY_SET filleted;
1647 
1648  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1649  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx, aPreserveCorners ) );
1650 
1651  return filleted;
1652 }
1653 
1654 
1656  unsigned int aDistance, int aIndex, int aErrorMax,
1657  std::set<VECTOR2I>* aPreserveCorners )
1658 {
1659  // Null segments create serious issues in calculations. Remove them:
1661 
1662  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1663  SHAPE_POLY_SET::POLYGON newPoly;
1664 
1665  // If the chamfering distance is zero, then the polygon remain intact.
1666  if( aDistance == 0 )
1667  {
1668  return currentPoly;
1669  }
1670 
1671  // Iterate through all the contours (outline and holes) of the polygon.
1672  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1673  {
1674  // Generate a new contour in the new polygon
1675  SHAPE_LINE_CHAIN newContour;
1676 
1677  // Iterate through the vertices of the contour
1678  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1679  {
1680  // Current vertex
1681  int x1 = currContour.CPoint( currVertex ).x;
1682  int y1 = currContour.CPoint( currVertex ).y;
1683 
1684  if( aPreserveCorners && aPreserveCorners->count( VECTOR2I( x1, y1 ) ) > 0 )
1685  {
1686  newContour.Append( x1, y1 );
1687  continue;
1688  }
1689 
1690  // Indices for previous and next vertices.
1691  int prevVertex;
1692  int nextVertex;
1693 
1694  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1695 
1696  // Previous vertex is the last one if the current vertex is the first one
1697  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1698 
1699  // next vertex is the first one if the current vertex is the last one.
1700  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1701 
1702  // Previous vertex computation
1703  double xa = currContour.CPoint( prevVertex ).x - x1;
1704  double ya = currContour.CPoint( prevVertex ).y - y1;
1705 
1706  // Next vertex computation
1707  double xb = currContour.CPoint( nextVertex ).x - x1;
1708  double yb = currContour.CPoint( nextVertex ).y - y1;
1709 
1710  // Compute the new distances
1711  double lena = hypot( xa, ya );
1712  double lenb = hypot( xb, yb );
1713 
1714  // Make the final computations depending on the mode selected, chamfered or filleted.
1715  if( aMode == CORNER_MODE::CHAMFERED )
1716  {
1717  double distance = aDistance;
1718 
1719  // Chamfer one half of an edge at most
1720  if( 0.5 * lena < distance )
1721  distance = 0.5 * lena;
1722 
1723  if( 0.5 * lenb < distance )
1724  distance = 0.5 * lenb;
1725 
1726  int nx1 = KiROUND( distance * xa / lena );
1727  int ny1 = KiROUND( distance * ya / lena );
1728 
1729  newContour.Append( x1 + nx1, y1 + ny1 );
1730 
1731  int nx2 = KiROUND( distance * xb / lenb );
1732  int ny2 = KiROUND( distance * yb / lenb );
1733 
1734  newContour.Append( x1 + nx2, y1 + ny2 );
1735  }
1736  else // CORNER_MODE = FILLETED
1737  {
1738  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1739 
1740  double radius = aDistance;
1741  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1742 
1743  // Do nothing in case of parallel edges
1744  if( std::isinf( denom ) )
1745  continue;
1746 
1747  // Limit rounding distance to one half of an edge
1748  if( 0.5 * lena * denom < radius )
1749  radius = 0.5 * lena * denom;
1750 
1751  if( 0.5 * lenb * denom < radius )
1752  radius = 0.5 * lenb * denom;
1753 
1754  // Calculate fillet arc absolute center point (xc, yx)
1755  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1756  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1757  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1758  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1759  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1760 
1761  // Calculate arc start and end vectors
1762  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1763  double xs = x1 + k * xa / lena - xc;
1764  double ys = y1 + k * ya / lena - yc;
1765  double xe = x1 + k * xb / lenb - xc;
1766  double ye = y1 + k * yb / lenb - yc;
1767 
1768  // Cosine of arc angle
1769  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1770 
1771  // Make sure the argument is in [-1,1], interval in which the acos function is
1772  // defined
1773  if( argument < -1 )
1774  argument = -1;
1775  else if( argument > 1 )
1776  argument = 1;
1777 
1778  double arcAngle = acos( argument );
1779  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1780  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1781 
1782  double deltaAngle = arcAngle / segments;
1783  double startAngle = atan2( -ys, xs );
1784 
1785  // Flip arc for inner corners
1786  if( xa * yb - ya * xb <= 0 )
1787  deltaAngle *= -1;
1788 
1789  double nx = xc + xs;
1790  double ny = yc + ys;
1791 
1792  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1793 
1794  // Store the previous added corner to make a sanity check
1795  int prevX = KiROUND( nx );
1796  int prevY = KiROUND( ny );
1797 
1798  for( int j = 0; j < segments; j++ )
1799  {
1800  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1801  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1802 
1803  // Sanity check: the rounding can produce repeated corners; do not add them.
1804  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1805  {
1806  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1807  prevX = KiROUND( nx );
1808  prevY = KiROUND( ny );
1809  }
1810  }
1811  }
1812  }
1813 
1814  // Close the current contour and add it the new polygon
1815  newContour.SetClosed( true );
1816  newPoly.push_back( newContour );
1817  }
1818 
1819  return newPoly;
1820 }
1821 
1822 
1824 {
1825  static_cast<SHAPE&>(*this) = aOther;
1826  m_polys = aOther.m_polys;
1827 
1828  // reset poly cache:
1829  m_hash = MD5_HASH{};
1830  m_triangulationValid = false;
1831  m_triangulatedPolys.clear();
1832  return *this;
1833 }
1834 
1836 {
1837  if( !m_hash.IsValid() )
1838  return checksum();
1839 
1840  return m_hash;
1841 }
1842 
1843 
1845 {
1846  if( !m_triangulationValid )
1847  return false;
1848 
1849  if( !m_hash.IsValid() )
1850  return false;
1851 
1852  auto hash = checksum();
1853 
1854  return hash == m_hash;
1855 }
1856 
1857 
1859 {
1860  bool recalculate = !m_hash.IsValid();
1861  MD5_HASH hash;
1862 
1863  if( !m_triangulationValid )
1864  recalculate = true;
1865 
1866  if( !recalculate )
1867  {
1868  hash = checksum();
1869 
1870  if( m_hash != hash )
1871  {
1872  m_hash = hash;
1873  recalculate = true;
1874  }
1875  }
1876 
1877  if( !recalculate )
1878  return;
1879 
1880  SHAPE_POLY_SET tmpSet = *this;
1881 
1882  if( tmpSet.HasHoles() )
1883  tmpSet.Fracture( PM_FAST );
1884 
1885  m_triangulatedPolys.clear();
1886  m_triangulationValid = true;
1887 
1888  while( tmpSet.OutlineCount() > 0 )
1889  {
1890  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1891  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1892 
1893  // If the tesselation fails, we re-fracture the polygon, which will
1894  // first simplify the system before fracturing and removing the holes
1895  // This may result in multiple, disjoint polygons.
1896  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
1897  {
1898  tmpSet.Fracture( PM_FAST );
1899  m_triangulationValid = false;
1900  continue;
1901  }
1902 
1903  tmpSet.DeletePolygon( 0 );
1904  m_triangulationValid = true;
1905  }
1906 
1907  if( m_triangulationValid )
1908  m_hash = checksum();
1909 }
1910 
1911 
1913 {
1914  MD5_HASH hash;
1915 
1916  hash.Hash( m_polys.size() );
1917 
1918  for( const auto& outline : m_polys )
1919  {
1920  hash.Hash( outline.size() );
1921 
1922  for( const auto& lc : outline )
1923  {
1924  hash.Hash( lc.PointCount() );
1925 
1926  for( int i = 0; i < lc.PointCount(); i++ )
1927  {
1928  hash.Hash( lc.CPoint( i ).x );
1929  hash.Hash( lc.CPoint( i ).y );
1930  }
1931  }
1932  }
1933 
1934  hash.Finalize();
1935 
1936  return hash;
1937 }
1938 
1939 
1941 {
1942  for( int i = 0; i < OutlineCount(); i++ )
1943  {
1944  if( hasTouchingHoles( CPolygon( i ) ) )
1945  {
1946  return true;
1947  }
1948  }
1949 
1950  return false;
1951 }
1952 
1953 
1954 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
1955 {
1956  std::set< long long > ptHashes;
1957 
1958  for( const auto& lc : aPoly )
1959  {
1960  for( const VECTOR2I& pt : lc.CPoints() )
1961  {
1962  const long long ptHash = (long long) pt.x << 32 | pt.y;
1963 
1964  if( ptHashes.count( ptHash ) > 0 )
1965  {
1966  return true;
1967  }
1968 
1969  ptHashes.insert( ptHash );
1970  }
1971  }
1972 
1973  return false;
1974 }
int TotalVertices() const
Returns total number of vertices stored in the set.
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...
CITER next(CITER it)
Definition: ptree.cpp:130
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 })
Function Rotate rotates all vertices by a given angle.
const POLYGON & CPolygon(int aIndex) const
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:202
int OutlineCount() const
Returns the number of outlines in the set
bool IsEndContour() const
Function IsEndContour.
void fractureSingle(POLYGON &paths)
static const int dist[10][10]
Definition: ar_matrix.cpp:326
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:144
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Returns true if the polygon set has any holes.
Struct VERTEX_INDEX.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
MD5_HASH checksum() const
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Returns true if a given subpolygon contains the point aP.
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
int PointCount() const
Function PointCount()
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
VERTEX_INDEX GetIndex()
Function GetIndex.
bool IsTriangulationUpToDate() const
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirrors the line points about y or x (or both)
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
#define SEG_CNT_MAX
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Returns the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a con...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Function SetVertex Accessor function to set the position of a specific point.
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetClosed(bool aClosed)
Function SetClosed()
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
#define NULL
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
SHAPE.
Definition: shape.h:60
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide Checks whether the point aP collides with the inside of the polygon set; if the poin...
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:385
const std::string Format() const override
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
int NewOutline()
Creates a new empty polygon in the set and returns its index
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
void BuildBBoxCaches()
Constructs BBoxCaches for Contains(), below.
double Area() const
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the polygon set.
Definition: seg.h:39
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex, std::set< VECTOR2I > *aPreserveCorners)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:301
simple polygon
Definition: shape.h:50
const SEG CSegment(int aIndex) const
Function CSegment()
bool matches(int y) const
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
ITERATOR IterateWithHoles()
Function IterateWithHoles.
SHAPE_LINE_CHAIN.
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the aIndex-th polygon.
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
VECTOR2I A
Definition: seg.h:47
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
SHAPE_POLY_SET Chamfer(int aDistance, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Chamfer returns a chamfered version of the polygon set.
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:84
static bool empty(const wxTextEntryBase *aCtrl)
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:61
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Performs outline inflation/deflation, using round corners.
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:179
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
void Finalize()
Definition: md5_hash.cpp:76
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:299
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
bool IsClosed() const
Function IsClosed()
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool IsValid() const
Definition: md5_hash.h:24
SHAPE * Clone() const override
Function Clone()
FractureEdge(int y=0)
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
VERTEX_INDEX GetIndex()
Function GetIndex.
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
bool IsSelfIntersecting() const
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
VECTOR2I B
Definition: seg.h:48
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.