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  assert( aOutline < (int)m_polys.size() );
431 
432  POLYGON& poly = m_polys[aOutline];
433 
434  assert( poly.size() );
435 
436  poly.push_back( aHole );
437 
438  return poly.size() - 1;
439 }
440 
441 
442 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
443  POLYGON_MODE aFastMode )
444 {
445  booleanOp( aType, *this, aOtherShape, aFastMode );
446 }
447 
448 
449 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
450  const SHAPE_POLY_SET& aShape,
451  const SHAPE_POLY_SET& aOtherShape,
452  POLYGON_MODE aFastMode )
453 {
454  Clipper c;
455 
456  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
457 
458  for( auto poly : aShape.m_polys )
459  {
460  for( size_t i = 0 ; i < poly.size(); i++ )
461  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
462  }
463 
464  for( auto poly : aOtherShape.m_polys )
465  {
466  for( size_t i = 0; i < poly.size(); i++ )
467  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
468  }
469 
470  PolyTree solution;
471 
472  c.Execute( aType, solution, pftNonZero, pftNonZero );
473 
474  importTree( &solution );
475 }
476 
477 
479 {
480  booleanOp( ctUnion, b, aFastMode );
481 }
482 
483 
485 {
486  booleanOp( ctDifference, b, aFastMode );
487 }
488 
489 
491 {
492  booleanOp( ctIntersection, b, aFastMode );
493 }
494 
495 
497  const SHAPE_POLY_SET& b,
498  POLYGON_MODE aFastMode )
499 {
500  booleanOp( ctUnion, a, b, aFastMode );
501 }
502 
503 
505  const SHAPE_POLY_SET& b,
506  POLYGON_MODE aFastMode )
507 {
508  booleanOp( ctDifference, a, b, aFastMode );
509 }
510 
511 
513  const SHAPE_POLY_SET& b,
514  POLYGON_MODE aFastMode )
515 {
516  booleanOp( ctIntersection, a, b, aFastMode );
517 }
518 
519 
520 void SHAPE_POLY_SET::InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount,
521  POLYGON_MODE aFastMode )
522 {
523  Simplify( aFastMode );
524  Inflate( aFactor, aCircleSegmentsCount );
525  Fracture( aFastMode );
526 }
527 
528 
529 void SHAPE_POLY_SET::Inflate( int aAmount, int aCircleSegmentsCount,
530  CORNER_STRATEGY aCornerStrategy )
531 {
532  // A static table to avoid repetitive calculations of the coefficient
533  // 1.0 - cos( M_PI / aCircleSegmentsCount )
534  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
535  #define SEG_CNT_MAX 64
536  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
537 
538  ClipperOffset c;
539 
540  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
541  // and are not what you'd think they are.
542  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
543  JoinType joinType = jtRound; // The way corners are offsetted
544  double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
545  JoinType miterFallback = jtSquare;
546 
547  switch( aCornerStrategy )
548  {
549  case ALLOW_ACUTE_CORNERS:
550  joinType = jtMiter;
551  miterLimit = 10; // Allows large spikes
552  miterFallback = jtSquare;
553  break;
554 
555  case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
556  joinType = jtMiter;
557  miterFallback = jtRound;
558  break;
559 
560  case ROUND_ACUTE_CORNERS: // Acute angles are rounded
561  joinType = jtMiter;
562  miterFallback = jtSquare;
563  break;
564 
565  case CHAMFER_ALL_CORNERS: // All angles are chamfered.
566  joinType = jtSquare;
567  miterFallback = jtSquare;
568  break;
569 
570  case ROUND_ALL_CORNERS: // All angles are rounded.
571  joinType = jtRound;
572  miterFallback = jtSquare;
573  break;
574  }
575 
576  for( const POLYGON& poly : m_polys )
577  {
578  for( size_t i = 0; i < poly.size(); i++ )
579  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
580  }
581 
582  PolyTree solution;
583 
584  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
585  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
586  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
587 
588  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
589  aCircleSegmentsCount = 6;
590 
591  double coeff;
592 
593  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
594  {
595  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
596 
597  if( aCircleSegmentsCount <= SEG_CNT_MAX )
598  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
599  }
600  else
601  coeff = arc_tolerance_factor[aCircleSegmentsCount];
602 
603  c.ArcTolerance = std::abs( aAmount ) * coeff;
604  c.MiterLimit = miterLimit;
605  c.MiterFallback = miterFallback;
606  c.Execute( solution, aAmount );
607 
608  importTree( &solution );
609 }
610 
611 
612 void SHAPE_POLY_SET::importTree( PolyTree* tree )
613 {
614  m_polys.clear();
615 
616  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
617  {
618  if( !n->IsHole() )
619  {
620  POLYGON paths;
621  paths.reserve( n->Childs.size() + 1 );
622  paths.push_back( n->Contour );
623 
624  for( unsigned int i = 0; i < n->Childs.size(); i++ )
625  paths.push_back( n->Childs[i]->Contour );
626 
627  m_polys.push_back( paths );
628  }
629  }
630 }
631 
632 
634 {
635  FractureEdge( int y = 0 ) :
636  m_connected( false ),
637  m_next( NULL )
638  {
639  m_p1.x = m_p2.y = y;
640  }
641 
642  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
643  m_connected( connected ),
644  m_p1( p1 ),
645  m_p2( p2 ),
646  m_next( NULL )
647  {
648  }
649 
650  bool matches( int y ) const
651  {
652  return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
653  }
654 
658 };
659 
660 
661 typedef std::vector<FractureEdge*> FractureEdgeSet;
662 
663 
664 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
665 {
666  int x = edge->m_p1.x;
667  int y = edge->m_p1.y;
668  int min_dist = std::numeric_limits<int>::max();
669  int x_nearest = 0;
670 
671  FractureEdge* e_nearest = NULL;
672 
673  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
674  {
675  if( !(*i)->matches( y ) )
676  continue;
677 
678  int x_intersect;
679 
680  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
681  x_intersect = std::max( (*i)->m_p1.x, (*i)->m_p2.x );
682  else
683  x_intersect = (*i)->m_p1.x + rescale( (*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y,
684  (*i)->m_p2.y - (*i)->m_p1.y );
685 
686  int dist = ( x - x_intersect );
687 
688  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
689  {
690  min_dist = dist;
691  x_nearest = x_intersect;
692  e_nearest = (*i);
693  }
694  }
695 
696  if( e_nearest && e_nearest->m_connected )
697  {
698  int count = 0;
699 
700  FractureEdge* lead1 =
701  new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
702  FractureEdge* lead2 =
703  new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
704  FractureEdge* split_2 =
705  new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
706 
707  edges.push_back( split_2 );
708  edges.push_back( lead1 );
709  edges.push_back( lead2 );
710 
711  FractureEdge* link = e_nearest->m_next;
712 
713  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
714  e_nearest->m_next = lead1;
715  lead1->m_next = edge;
716 
717  FractureEdge* last;
718 
719  for( last = edge; last->m_next != edge; last = last->m_next )
720  {
721  last->m_connected = true;
722  count++;
723  }
724 
725  last->m_connected = true;
726  last->m_next = lead2;
727  lead2->m_next = split_2;
728  split_2->m_next = link;
729 
730  return count + 1;
731  }
732 
733  return 0;
734 }
735 
736 
738 {
739  FractureEdgeSet edges;
740  FractureEdgeSet border_edges;
741  FractureEdge* root = NULL;
742 
743  bool first = true;
744 
745  if( paths.size() == 1 )
746  return;
747 
748  int num_unconnected = 0;
749 
750  for( const SHAPE_LINE_CHAIN& path : paths )
751  {
752  const std::vector<VECTOR2I>& points = path.CPoints();
753  int pointCount = points.size();
754 
755  FractureEdge* prev = NULL, * first_edge = NULL;
756 
757  int x_min = std::numeric_limits<int>::max();
758 
759  for( const VECTOR2I& p : points )
760  {
761  if( p.x < x_min )
762  x_min = p.x;
763  }
764 
765  for( int i = 0; i < pointCount; i++ )
766  {
767  // Do not use path.CPoint() here; open-coding it using the local variables "points"
768  // and "pointCount" gives a non-trivial performance boost to zone fill times.
769  FractureEdge* fe = new FractureEdge( first, points[ i ],
770  points[ i+1 == pointCount ? 0 : i+1 ] );
771 
772  if( !root )
773  root = fe;
774 
775  if( !first_edge )
776  first_edge = fe;
777 
778  if( prev )
779  prev->m_next = fe;
780 
781  if( i == pointCount - 1 )
782  fe->m_next = first_edge;
783 
784  prev = fe;
785  edges.push_back( fe );
786 
787  if( !first )
788  {
789  if( fe->m_p1.x == x_min )
790  border_edges.push_back( fe );
791  }
792 
793  if( !fe->m_connected )
794  num_unconnected++;
795  }
796 
797  first = false; // first path is always the outline
798  }
799 
800  // keep connecting holes to the main outline, until there's no holes left...
801  while( num_unconnected > 0 )
802  {
803  int x_min = std::numeric_limits<int>::max();
804 
805  FractureEdge* smallestX = NULL;
806 
807  // find the left-most hole edge and merge with the outline
808  for( FractureEdge* border_edge : border_edges )
809  {
810  int xt = border_edge->m_p1.x;
811 
812  if( ( xt < x_min ) && !border_edge->m_connected )
813  {
814  x_min = xt;
815  smallestX = border_edge;
816  }
817  }
818 
819  num_unconnected -= processEdge( edges, smallestX );
820  }
821 
822  paths.clear();
823  SHAPE_LINE_CHAIN newPath;
824 
825  newPath.SetClosed( true );
826 
827  FractureEdge* e;
828 
829  for( e = root; e->m_next != root; e = e->m_next )
830  newPath.Append( e->m_p1 );
831 
832  newPath.Append( e->m_p1 );
833 
834  for( FractureEdge* edge : edges )
835  delete edge;
836 
837  paths.push_back( std::move( newPath ) );
838 }
839 
840 
842 {
843  Simplify( aFastMode ); // remove overlapping holes/degeneracy
844 
845  for( POLYGON& paths : m_polys )
846  {
847  fractureSingle( paths );
848  }
849 }
850 
851 
853 {
854  assert( aPoly.size() == 1 );
855 
856  struct EDGE
857  {
858  int m_index = 0;
859  SHAPE_LINE_CHAIN* m_poly = nullptr;
860  bool m_duplicate = false;
861 
862  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
863  m_index( aIndex ),
864  m_poly( aPolygon )
865  {}
866 
867  bool compareSegs( const SEG& s1, const SEG& s2 ) const
868  {
869  return (s1.A == s2.B && s1.B == s2.A);
870  }
871 
872  bool operator==( const EDGE& aOther ) const
873  {
874  return compareSegs( m_poly->CSegment( m_index ),
875  aOther.m_poly->CSegment( aOther.m_index ) );
876  }
877 
878  bool operator!=( const EDGE& aOther ) const
879  {
880  return !compareSegs( m_poly->CSegment( m_index ),
881  aOther.m_poly->CSegment( aOther.m_index ) );
882  }
883 
884  struct HASH
885  {
886  std::size_t operator()( const EDGE& aEdge ) const
887  {
888  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
889 
890  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
891  }
892  };
893  };
894 
895  struct EDGE_LIST_ENTRY
896  {
897  int index;
898  EDGE_LIST_ENTRY* next;
899  };
900 
901  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
902 
903  auto lc = aPoly[0];
904  lc.Simplify();
905 
906  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
907 
908  for( int i = 0; i < lc.SegmentCount(); i++ )
909  {
910  edgeList[i].index = i;
911  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
912  }
913 
914  std::unordered_set<EDGE_LIST_ENTRY*> queue;
915 
916  for( int i = 0; i < lc.SegmentCount(); i++ )
917  {
918  EDGE e( &lc, i );
919  uniqueEdges.insert( e );
920  }
921 
922  for( int i = 0; i < lc.SegmentCount(); i++ )
923  {
924  EDGE e( &lc, i );
925  auto it = uniqueEdges.find( e );
926 
927  if( it != uniqueEdges.end() && it->m_index != i )
928  {
929  int e1 = it->m_index;
930  int e2 = i;
931 
932  if( e1 > e2 )
933  std::swap( e1, e2 );
934 
935  int e1_prev = e1 - 1;
936 
937  if( e1_prev < 0 )
938  e1_prev = lc.SegmentCount() - 1;
939 
940  int e2_prev = e2 - 1;
941 
942  if( e2_prev < 0 )
943  e2_prev = lc.SegmentCount() - 1;
944 
945  int e1_next = e1 + 1;
946 
947  if( e1_next == lc.SegmentCount() )
948  e1_next = 0;
949 
950  int e2_next = e2 + 1;
951 
952  if( e2_next == lc.SegmentCount() )
953  e2_next = 0;
954 
955  edgeList[e1_prev].next = &edgeList[ e2_next ];
956  edgeList[e2_prev].next = &edgeList[ e1_next ];
957  edgeList[i].next = nullptr;
958  edgeList[it->m_index].next = nullptr;
959  }
960  }
961 
962  for( int i = 0; i < lc.SegmentCount(); i++ )
963  {
964  if( edgeList[i].next )
965  queue.insert( &edgeList[i] );
966  }
967 
968  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
969 
970  int n = 0;
971  int outline = -1;
972 
973  POLYGON result;
974 
975  while( queue.size() )
976  {
977  auto e_first = (*queue.begin() );
978  auto e = e_first;
979  int cnt = 0;
980 
981  do {
982  edgeBuf[cnt++] = e;
983  e = e->next;
984  } while( e && e != e_first );
985 
986  SHAPE_LINE_CHAIN outl;
987 
988  for( int i = 0; i < cnt; i++ )
989  {
990  auto p = lc.CPoint( edgeBuf[i]->index );
991  outl.Append( p );
992  queue.erase( edgeBuf[i] );
993  }
994 
995  outl.SetClosed( true );
996 
997  bool cw = outl.Area() > 0.0;
998 
999  if( cw )
1000  outline = n;
1001 
1002  result.push_back( outl );
1003  n++;
1004  }
1005 
1006  if( outline > 0 )
1007  std::swap( result[0], result[outline] );
1008 
1009  aPoly = result;
1010 }
1011 
1012 
1014 {
1015  // Iterate through all the polygons on the set
1016  for( const POLYGON& paths : m_polys )
1017  {
1018  // If any of them has more than one contour, it is a hole.
1019  if( paths.size() > 1 )
1020  return true;
1021  }
1022 
1023  // Return false if and only if every polygon has just one outline, without holes.
1024  return false;
1025 }
1026 
1027 
1029 {
1030  for( POLYGON& path : m_polys )
1031  {
1032  unfractureSingle( path );
1033  }
1034 
1035  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1036 }
1037 
1038 
1040 {
1042 
1043  booleanOp( ctUnion, empty, aFastMode );
1044 }
1045 
1046 
1048 {
1049  // We are expecting only one main outline, but this main outline can have holes
1050  // if holes: combine holes and remove them from the main outline.
1051  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1052  // calculations, but it is not mandatory. It is used mainly
1053  // because there is usually only very few vertices in area outlines
1054  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1055  SHAPE_POLY_SET holesBuffer;
1056 
1057  // Move holes stored in outline to holesBuffer:
1058  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1059  while( outline.size() > 1 )
1060  {
1061  holesBuffer.AddOutline( outline.back() );
1062  outline.pop_back();
1063  }
1064 
1066 
1067  // If any hole, substract it to main outline
1068  if( holesBuffer.OutlineCount() )
1069  {
1070  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1072  }
1073 
1075 
1076  return OutlineCount();
1077 }
1078 
1079 
1080 const std::string SHAPE_POLY_SET::Format() const
1081 {
1082  std::stringstream ss;
1083 
1084  ss << "polyset " << m_polys.size() << "\n";
1085 
1086  for( unsigned i = 0; i < m_polys.size(); i++ )
1087  {
1088  ss << "poly " << m_polys[i].size() << "\n";
1089 
1090  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1091  {
1092  ss << m_polys[i][j].PointCount() << "\n";
1093 
1094  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1095  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1096  }
1097 
1098  ss << "\n";
1099  }
1100 
1101  return ss.str();
1102 }
1103 
1104 
1105 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1106 {
1107  std::string tmp;
1108 
1109  aStream >> tmp;
1110 
1111  if( tmp != "polyset" )
1112  return false;
1113 
1114  aStream >> tmp;
1115 
1116  int n_polys = atoi( tmp.c_str() );
1117 
1118  if( n_polys < 0 )
1119  return false;
1120 
1121  for( int i = 0; i < n_polys; i++ )
1122  {
1123  POLYGON paths;
1124 
1125  aStream >> tmp;
1126 
1127  if( tmp != "poly" )
1128  return false;
1129 
1130  aStream >> tmp;
1131  int n_outlines = atoi( tmp.c_str() );
1132 
1133  if( n_outlines < 0 )
1134  return false;
1135 
1136  for( int j = 0; j < n_outlines; j++ )
1137  {
1138  SHAPE_LINE_CHAIN outline;
1139 
1140  outline.SetClosed( true );
1141 
1142  aStream >> tmp;
1143  int n_vertices = atoi( tmp.c_str() );
1144 
1145  for( int v = 0; v < n_vertices; v++ )
1146  {
1147  VECTOR2I p;
1148 
1149  aStream >> tmp; p.x = atoi( tmp.c_str() );
1150  aStream >> tmp; p.y = atoi( tmp.c_str() );
1151  outline.Append( p );
1152  }
1153 
1154  paths.push_back( outline );
1155  }
1156 
1157  m_polys.push_back( paths );
1158  }
1159 
1160  return true;
1161 }
1162 
1163 
1164 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1165 {
1166  BOX2I bb;
1167 
1168  for( unsigned i = 0; i < m_polys.size(); i++ )
1169  {
1170  if( i == 0 )
1171  bb = m_polys[i][0].BBox();
1172  else
1173  bb.Merge( m_polys[i][0].BBox() );
1174  }
1175 
1176  bb.Inflate( aClearance );
1177  return bb;
1178 }
1179 
1180 
1181 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1182 {
1183  // Iterate through all the polygons in the set
1184  for( const POLYGON& polygon : m_polys )
1185  {
1186  // Iterate through all the line chains in the polygon
1187  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1188  {
1189  if( lineChain.PointOnEdge( aP ) )
1190  return true;
1191  }
1192  }
1193 
1194  return false;
1195 }
1196 
1197 
1198 bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance ) const
1199 {
1200 
1201  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1202 
1203  // Inflate the polygon if necessary.
1204  if( aClearance > 0 )
1205  {
1206  // fixme: the number of arc segments should not be hardcoded
1207  polySet.Inflate( aClearance, 8 );
1208  }
1209 
1210  // We are going to check to see if the segment crosses an external
1211  // boundary. However, if the full segment is inside the polyset, this
1212  // will not be true. So we first test to see if one of the points is
1213  // inside. If true, then we collide
1214  if( polySet.Contains( aSeg.A ) )
1215  return true;
1216 
1217  for( SEGMENT_ITERATOR it = ( (SHAPE_POLY_SET*) this )->IterateSegmentsWithHoles(); it; it++ )
1218  {
1219  SEG polygonEdge = *it;
1220 
1221  if( polygonEdge.Intersect( aSeg, true ) )
1222  return true;
1223  }
1224 
1225  return false;
1226 }
1227 
1228 
1229 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1230 {
1231  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1232 
1233  // Inflate the polygon if necessary.
1234  if( aClearance > 0 )
1235  {
1236  // fixme: the number of arc segments should not be hardcoded
1237  polySet.Inflate( aClearance, 8 );
1238  }
1239 
1240  // There is a collision if and only if the point is inside of the polygon.
1241  return polySet.Contains( aP );
1242 }
1243 
1244 
1246 {
1247  m_polys.clear();
1248 }
1249 
1250 
1251 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1252 {
1253  // Default polygon is the last one
1254  if( aPolygonIdx < 0 )
1255  aPolygonIdx += m_polys.size();
1256 
1257  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1258 }
1259 
1260 
1262 {
1263  int removed = 0;
1264 
1265  ITERATOR iterator = IterateWithHoles();
1266 
1267  VECTOR2I contourStart = *iterator;
1268  VECTOR2I segmentStart, segmentEnd;
1269 
1270  VERTEX_INDEX indexStart;
1271 
1272  while( iterator )
1273  {
1274  // Obtain first point and its index
1275  segmentStart = *iterator;
1276  indexStart = iterator.GetIndex();
1277 
1278  // Obtain last point
1279  if( iterator.IsEndContour() )
1280  {
1281  segmentEnd = contourStart;
1282 
1283  // Advance
1284  iterator++;
1285 
1286  if( iterator )
1287  contourStart = *iterator;
1288  }
1289  else
1290  {
1291  // Advance
1292  iterator++;
1293 
1294  if( iterator )
1295  segmentEnd = *iterator;
1296  }
1297 
1298  // Remove segment start if both points are equal
1299  if( segmentStart == segmentEnd )
1300  {
1301  RemoveVertex( indexStart );
1302  removed++;
1303 
1304  // Advance the iterator one position, as there is one vertex less.
1305  if( iterator )
1306  iterator++;
1307  }
1308  }
1309 
1310  return removed;
1311 }
1312 
1313 
1315 {
1316  m_polys.erase( m_polys.begin() + aIdx );
1317 }
1318 
1319 
1321 {
1322  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1323 }
1324 
1325 
1326 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1327 {
1328  Append( aP.x, aP.y, aOutline, aHole );
1329 }
1330 
1331 
1333  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1334 {
1335  // Shows whether there was a collision
1336  bool collision = false;
1337 
1338  // Difference vector between each vertex and aPoint.
1339  VECTOR2D delta;
1340  double distance, clearance;
1341 
1342  // Convert clearance to double for precission when comparing distances
1343  clearance = aClearance;
1344 
1345  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1346  {
1347  // Get the difference vector between current vertex and aPoint
1348  delta = *iterator - aPoint;
1349 
1350  // Compute distance
1351  distance = delta.EuclideanNorm();
1352 
1353  // Check for collisions
1354  if( distance <= clearance )
1355  {
1356  collision = true;
1357 
1358  // Update aClearance to look for closer vertices
1359  clearance = distance;
1360 
1361  // Store the indices that identify the vertex
1362  aClosestVertex = iterator.GetIndex();
1363  }
1364  }
1365 
1366  return collision;
1367 }
1368 
1369 
1371  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1372 {
1373  // Shows whether there was a collision
1374  bool collision = false;
1375 
1376  SEGMENT_ITERATOR iterator;
1377 
1378  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1379  {
1380  SEG currentSegment = *iterator;
1381  int distance = currentSegment.Distance( aPoint );
1382 
1383  // Check for collisions
1384  if( distance <= aClearance )
1385  {
1386  collision = true;
1387 
1388  // Update aClearance to look for closer edges
1389  aClearance = distance;
1390 
1391  // Store the indices that identify the vertex
1392  aClosestVertex = iterator.GetIndex();
1393  }
1394  }
1395 
1396  return collision;
1397 }
1398 
1399 
1401 {
1402  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1403  {
1404  Outline( polygonIdx ).GenerateBBoxCache();
1405 
1406  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1407  Hole( polygonIdx, holeIdx ).GenerateBBoxCache();
1408  }
1409 }
1410 
1411 
1412 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1413  bool aUseBBoxCaches ) const
1414 {
1415  if( m_polys.empty() )
1416  return false;
1417 
1418  // If there is a polygon specified, check the condition against that polygon
1419  if( aSubpolyIndex >= 0 )
1420  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1421 
1422  // In any other case, check it against all polygons in the set
1423  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1424  {
1425  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1426  return true;
1427  }
1428 
1429  return false;
1430 }
1431 
1432 
1433 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1434 {
1435  VERTEX_INDEX index;
1436 
1437  // Assure the to be removed vertex exists, abort otherwise
1438  if( GetRelativeIndices( aGlobalIndex, &index ) )
1439  RemoveVertex( index );
1440  else
1441  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1442 }
1443 
1444 
1446 {
1447  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1448 }
1449 
1450 
1451 void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
1452 {
1453  VERTEX_INDEX index;
1454 
1455  if( GetRelativeIndices( aGlobalIndex, &index ) )
1456  SetVertex( index, aPos );
1457  else
1458  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1459 }
1460 
1461 
1462 void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
1463 {
1464  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1465 }
1466 
1467 
1468 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1469  bool aUseBBoxCaches ) const
1470 {
1471  // Check that the point is inside the outline
1472  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1473  {
1474  // Check that the point is not in any of the holes
1475  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1476  {
1477  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1478 
1479  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1480  // here as it's meaning would be inverted.
1481  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1482  return false;
1483  }
1484 
1485  return true;
1486  }
1487 
1488  return false;
1489 }
1490 
1491 
1492 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1493 {
1494  for( POLYGON& poly : m_polys )
1495  {
1496  for( SHAPE_LINE_CHAIN& path : poly )
1497  path.Move( aVector );
1498  }
1499 }
1500 
1501 
1502 void SHAPE_POLY_SET::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
1503 {
1504  for( POLYGON& poly : m_polys )
1505  {
1506  for( SHAPE_LINE_CHAIN& path : poly )
1507  {
1508  path.Mirror( aX, aY, aRef );
1509  }
1510  }
1511 }
1512 
1513 
1514 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1515 {
1516  for( POLYGON& poly : m_polys )
1517  {
1518  for( SHAPE_LINE_CHAIN& path : poly )
1519  path.Rotate( aAngle, aCenter );
1520  }
1521 }
1522 
1523 
1525 {
1526  int c = 0;
1527 
1528  for( const POLYGON& poly : m_polys )
1529  {
1530  for( const SHAPE_LINE_CHAIN& path : poly )
1531  c += path.PointCount();
1532  }
1533 
1534  return c;
1535 }
1536 
1537 
1538 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex,
1539  std::set<VECTOR2I>* aPreserveCorners )
1540 {
1541  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0, aPreserveCorners );
1542 }
1543 
1544 
1545 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
1546  int aIndex,
1547  std::set<VECTOR2I>* aPreserveCorners )
1548 {
1549  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax, aPreserveCorners );
1550 }
1551 
1552 
1553 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1554 {
1555  // We calculate the min dist between the segment and each outline segment. However, if the
1556  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1557  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1558  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1559  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1560  return 0;
1561 
1562  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1563 
1564  SEG polygonEdge = *iterator;
1565  int minDistance = polygonEdge.Distance( aPoint );
1566 
1567  for( iterator++; iterator && minDistance > 0; iterator++ )
1568  {
1569  polygonEdge = *iterator;
1570 
1571  int currentDistance = polygonEdge.Distance( aPoint );
1572 
1573  if( currentDistance < minDistance )
1574  minDistance = currentDistance;
1575  }
1576 
1577  return minDistance;
1578 }
1579 
1580 
1581 int SHAPE_POLY_SET::DistanceToPolygon( const SEG& aSegment, int aPolygonIndex, int aSegmentWidth )
1582 {
1583  // We calculate the min dist between the segment and each outline segment. However, if the
1584  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1585  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1586  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1587  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1588  return 0;
1589 
1590  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1591 
1592  SEG polygonEdge = *iterator;
1593  int minDistance = polygonEdge.Distance( aSegment );
1594 
1595  for( iterator++; iterator && minDistance > 0; iterator++ )
1596  {
1597  polygonEdge = *iterator;
1598 
1599  int currentDistance = polygonEdge.Distance( aSegment );
1600 
1601  if( currentDistance < minDistance )
1602  minDistance = currentDistance;
1603  }
1604 
1605  // Take into account the width of the segment
1606  if( aSegmentWidth > 0 )
1607  minDistance -= aSegmentWidth / 2;
1608 
1609  // Return the maximum of minDistance and zero
1610  return minDistance < 0 ? 0 : minDistance;
1611 }
1612 
1613 
1615 {
1616  int currentDistance;
1617  int minDistance = DistanceToPolygon( aPoint, 0 );
1618 
1619  // Iterate through all the polygons and get the minimum distance.
1620  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1621  {
1622  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1623 
1624  if( currentDistance < minDistance )
1625  minDistance = currentDistance;
1626  }
1627 
1628  return minDistance;
1629 }
1630 
1631 
1632 int SHAPE_POLY_SET::Distance( const SEG& aSegment, int aSegmentWidth )
1633 {
1634  int currentDistance;
1635  int minDistance = DistanceToPolygon( aSegment, 0, aSegmentWidth );
1636 
1637  // Iterate through all the polygons and get the minimum distance.
1638  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1639  {
1640  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1641 
1642  if( currentDistance < minDistance )
1643  minDistance = currentDistance;
1644  }
1645 
1646  return minDistance;
1647 }
1648 
1649 
1650 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1651 {
1652  VERTEX_INDEX index;
1653 
1654  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1655  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1656  return false;
1657 
1658  // The contour is a hole if its index is greater than zero
1659  return index.m_contour > 0;
1660 }
1661 
1662 
1663 SHAPE_POLY_SET SHAPE_POLY_SET::Chamfer( int aDistance, std::set<VECTOR2I>* aPreserveCorners )
1664 {
1665  SHAPE_POLY_SET chamfered;
1666 
1667  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1668  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx, aPreserveCorners ) );
1669 
1670  return chamfered;
1671 }
1672 
1673 
1674 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax,
1675  std::set<VECTOR2I>* aPreserveCorners )
1676 {
1677  SHAPE_POLY_SET filleted;
1678 
1679  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1680  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx, aPreserveCorners ) );
1681 
1682  return filleted;
1683 }
1684 
1685 
1687  unsigned int aDistance, int aIndex, int aErrorMax,
1688  std::set<VECTOR2I>* aPreserveCorners )
1689 {
1690  // Null segments create serious issues in calculations. Remove them:
1692 
1693  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1694  SHAPE_POLY_SET::POLYGON newPoly;
1695 
1696  // If the chamfering distance is zero, then the polygon remain intact.
1697  if( aDistance == 0 )
1698  {
1699  return currentPoly;
1700  }
1701 
1702  // Iterate through all the contours (outline and holes) of the polygon.
1703  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1704  {
1705  // Generate a new contour in the new polygon
1706  SHAPE_LINE_CHAIN newContour;
1707 
1708  // Iterate through the vertices of the contour
1709  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1710  {
1711  // Current vertex
1712  int x1 = currContour.CPoint( currVertex ).x;
1713  int y1 = currContour.CPoint( currVertex ).y;
1714 
1715  if( aPreserveCorners && aPreserveCorners->count( VECTOR2I( x1, y1 ) ) > 0 )
1716  {
1717  newContour.Append( x1, y1 );
1718  continue;
1719  }
1720 
1721  // Indices for previous and next vertices.
1722  int prevVertex;
1723  int nextVertex;
1724 
1725  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1726 
1727  // Previous vertex is the last one if the current vertex is the first one
1728  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1729 
1730  // next vertex is the first one if the current vertex is the last one.
1731  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1732 
1733  // Previous vertex computation
1734  double xa = currContour.CPoint( prevVertex ).x - x1;
1735  double ya = currContour.CPoint( prevVertex ).y - y1;
1736 
1737  // Next vertex computation
1738  double xb = currContour.CPoint( nextVertex ).x - x1;
1739  double yb = currContour.CPoint( nextVertex ).y - y1;
1740 
1741  // Compute the new distances
1742  double lena = hypot( xa, ya );
1743  double lenb = hypot( xb, yb );
1744 
1745  // Make the final computations depending on the mode selected, chamfered or filleted.
1746  if( aMode == CORNER_MODE::CHAMFERED )
1747  {
1748  double distance = aDistance;
1749 
1750  // Chamfer one half of an edge at most
1751  if( 0.5 * lena < distance )
1752  distance = 0.5 * lena;
1753 
1754  if( 0.5 * lenb < distance )
1755  distance = 0.5 * lenb;
1756 
1757  int nx1 = KiROUND( distance * xa / lena );
1758  int ny1 = KiROUND( distance * ya / lena );
1759 
1760  newContour.Append( x1 + nx1, y1 + ny1 );
1761 
1762  int nx2 = KiROUND( distance * xb / lenb );
1763  int ny2 = KiROUND( distance * yb / lenb );
1764 
1765  newContour.Append( x1 + nx2, y1 + ny2 );
1766  }
1767  else // CORNER_MODE = FILLETED
1768  {
1769  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1770 
1771  double radius = aDistance;
1772  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1773 
1774  // Do nothing in case of parallel edges
1775  if( std::isinf( denom ) )
1776  continue;
1777 
1778  // Limit rounding distance to one half of an edge
1779  if( 0.5 * lena * denom < radius )
1780  radius = 0.5 * lena * denom;
1781 
1782  if( 0.5 * lenb * denom < radius )
1783  radius = 0.5 * lenb * denom;
1784 
1785  // Calculate fillet arc absolute center point (xc, yx)
1786  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1787  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1788  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1789  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1790  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1791 
1792  // Calculate arc start and end vectors
1793  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1794  double xs = x1 + k * xa / lena - xc;
1795  double ys = y1 + k * ya / lena - yc;
1796  double xe = x1 + k * xb / lenb - xc;
1797  double ye = y1 + k * yb / lenb - yc;
1798 
1799  // Cosine of arc angle
1800  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1801 
1802  // Make sure the argument is in [-1,1], interval in which the acos function is
1803  // defined
1804  if( argument < -1 )
1805  argument = -1;
1806  else if( argument > 1 )
1807  argument = 1;
1808 
1809  double arcAngle = acos( argument );
1810  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1811  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1812 
1813  double deltaAngle = arcAngle / segments;
1814  double startAngle = atan2( -ys, xs );
1815 
1816  // Flip arc for inner corners
1817  if( xa * yb - ya * xb <= 0 )
1818  deltaAngle *= -1;
1819 
1820  double nx = xc + xs;
1821  double ny = yc + ys;
1822 
1823  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1824 
1825  // Store the previous added corner to make a sanity check
1826  int prevX = KiROUND( nx );
1827  int prevY = KiROUND( ny );
1828 
1829  for( int j = 0; j < segments; j++ )
1830  {
1831  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1832  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1833 
1834  // Sanity check: the rounding can produce repeated corners; do not add them.
1835  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1836  {
1837  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1838  prevX = KiROUND( nx );
1839  prevY = KiROUND( ny );
1840  }
1841  }
1842  }
1843  }
1844 
1845  // Close the current contour and add it the new polygon
1846  newContour.SetClosed( true );
1847  newPoly.push_back( newContour );
1848  }
1849 
1850  return newPoly;
1851 }
1852 
1853 
1855 {
1856  static_cast<SHAPE&>(*this) = aOther;
1857  m_polys = aOther.m_polys;
1858 
1859  // reset poly cache:
1860  m_hash = MD5_HASH{};
1861  m_triangulationValid = false;
1862  m_triangulatedPolys.clear();
1863  return *this;
1864 }
1865 
1867 {
1868  if( !m_hash.IsValid() )
1869  return checksum();
1870 
1871  return m_hash;
1872 }
1873 
1874 
1876 {
1877  if( !m_triangulationValid )
1878  return false;
1879 
1880  if( !m_hash.IsValid() )
1881  return false;
1882 
1883  auto hash = checksum();
1884 
1885  return hash == m_hash;
1886 }
1887 
1888 
1890 {
1891  bool recalculate = !m_hash.IsValid();
1892  MD5_HASH hash;
1893 
1894  if( !m_triangulationValid )
1895  recalculate = true;
1896 
1897  if( !recalculate )
1898  {
1899  hash = checksum();
1900 
1901  if( m_hash != hash )
1902  {
1903  m_hash = hash;
1904  recalculate = true;
1905  }
1906  }
1907 
1908  if( !recalculate )
1909  return;
1910 
1911  SHAPE_POLY_SET tmpSet = *this;
1912 
1913  if( tmpSet.HasHoles() )
1914  tmpSet.Fracture( PM_FAST );
1915 
1916  m_triangulatedPolys.clear();
1917  m_triangulationValid = true;
1918 
1919  while( tmpSet.OutlineCount() > 0 )
1920  {
1921  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1922  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1923 
1924  // If the tesselation fails, we re-fracture the polygon, which will
1925  // first simplify the system before fracturing and removing the holes
1926  // This may result in multiple, disjoint polygons.
1927  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
1928  {
1929  tmpSet.Fracture( PM_FAST );
1930  m_triangulationValid = false;
1931  continue;
1932  }
1933 
1934  tmpSet.DeletePolygon( 0 );
1935  m_triangulationValid = true;
1936  }
1937 
1938  if( m_triangulationValid )
1939  m_hash = checksum();
1940 }
1941 
1942 
1944 {
1945  MD5_HASH hash;
1946 
1947  hash.Hash( m_polys.size() );
1948 
1949  for( const auto& outline : m_polys )
1950  {
1951  hash.Hash( outline.size() );
1952 
1953  for( const auto& lc : outline )
1954  {
1955  hash.Hash( lc.PointCount() );
1956 
1957  for( int i = 0; i < lc.PointCount(); i++ )
1958  {
1959  hash.Hash( lc.CPoint( i ).x );
1960  hash.Hash( lc.CPoint( i ).y );
1961  }
1962  }
1963  }
1964 
1965  hash.Finalize();
1966 
1967  return hash;
1968 }
1969 
1970 
1972 {
1973  for( int i = 0; i < OutlineCount(); i++ )
1974  {
1975  if( hasTouchingHoles( CPolygon( i ) ) )
1976  {
1977  return true;
1978  }
1979  }
1980 
1981  return false;
1982 }
1983 
1984 
1985 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
1986 {
1987  std::set< long long > ptHashes;
1988 
1989  for( const auto& lc : aPoly )
1990  {
1991  for( const VECTOR2I& pt : lc.CPoints() )
1992  {
1993  const long long ptHash = (long long) pt.x << 32 | pt.y;
1994 
1995  if( ptHashes.count( ptHash ) > 0 )
1996  {
1997  return true;
1998  }
1999 
2000  ptHashes.insert( ptHash );
2001  }
2002  }
2003 
2004  return false;
2005 }
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
All angles are chamfered.
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.
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
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 &)
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.
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
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
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()
just inflate the polygon. Acute angles create spikes
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.