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