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() - 2;
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 
1541  // Don't re-cache if the triangulation is already invalid
1542  if( m_triangulationValid )
1544 }
1545 
1546 
1548 {
1549  int c = 0;
1550 
1551  for( const POLYGON& poly : m_polys )
1552  {
1553  for( const SHAPE_LINE_CHAIN& path : poly )
1554  c += path.PointCount();
1555  }
1556 
1557  return c;
1558 }
1559 
1560 
1561 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1562 {
1563  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1564 }
1565 
1566 
1567 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
1568  int aIndex )
1569 {
1570  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
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::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1586 
1587  for( iterator++; iterator && minDistance > 0; iterator++ )
1588  {
1589  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1590 
1591  if( currentDistance < minDistance )
1592  minDistance = currentDistance;
1593  }
1594 
1595  return minDistance;
1596 }
1597 
1598 
1599 SEG::ecoord SHAPE_POLY_SET::SquaredDistanceToPolygon( const SEG& aSegment, int aPolygonIndex ) const
1600 {
1601  // We calculate the min dist between the segment and each outline segment. However, if the
1602  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1603  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1604  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1605  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1606  return 0;
1607 
1608  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1609  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1610 
1611  for( iterator++; iterator && minDistance > 0; iterator++ )
1612  {
1613  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1614 
1615  if( currentDistance < minDistance )
1616  minDistance = currentDistance;
1617  }
1618 
1619  // Return the maximum of minDistance and zero
1620  return minDistance < 0 ? 0 : minDistance;
1621 }
1622 
1623 
1625 {
1626  SEG::ecoord currentDistance;
1627  SEG::ecoord minDistance = SquaredDistanceToPolygon( aPoint, 0 );
1628 
1629  // Iterate through all the polygons and get the minimum distance.
1630  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1631  {
1632  currentDistance = SquaredDistanceToPolygon( aPoint, polygonIdx );
1633 
1634  if( currentDistance < minDistance )
1635  minDistance = currentDistance;
1636  }
1637 
1638  return minDistance;
1639 }
1640 
1641 
1643 {
1644  SEG::ecoord currentDistance;
1645  SEG::ecoord minDistance = SquaredDistanceToPolygon( aSegment, 0 );
1646 
1647  // Iterate through all the polygons and get the minimum distance.
1648  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1649  {
1650  currentDistance = SquaredDistanceToPolygon( aSegment, polygonIdx );
1651 
1652  if( currentDistance < minDistance )
1653  minDistance = currentDistance;
1654  }
1655 
1656  return minDistance;
1657 }
1658 
1659 
1660 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1661 {
1662  VERTEX_INDEX index;
1663 
1664  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1665  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1666  return false;
1667 
1668  // The contour is a hole if its index is greater than zero
1669  return index.m_contour > 0;
1670 }
1671 
1672 
1674 {
1675  SHAPE_POLY_SET chamfered;
1676 
1677  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1678  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
1679 
1680  return chamfered;
1681 }
1682 
1683 
1684 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
1685 {
1686  SHAPE_POLY_SET filleted;
1687 
1688  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1689  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
1690 
1691  return filleted;
1692 }
1693 
1694 
1696  unsigned int aDistance, int aIndex, int aErrorMax )
1697 {
1698  // Null segments create serious issues in calculations. Remove them:
1700 
1701  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1702  SHAPE_POLY_SET::POLYGON newPoly;
1703 
1704  // If the chamfering distance is zero, then the polygon remain intact.
1705  if( aDistance == 0 )
1706  {
1707  return currentPoly;
1708  }
1709 
1710  // Iterate through all the contours (outline and holes) of the polygon.
1711  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1712  {
1713  // Generate a new contour in the new polygon
1714  SHAPE_LINE_CHAIN newContour;
1715 
1716  // Iterate through the vertices of the contour
1717  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1718  {
1719  // Current vertex
1720  int x1 = currContour.CPoint( currVertex ).x;
1721  int y1 = currContour.CPoint( currVertex ).y;
1722 
1723  // Indices for previous and next vertices.
1724  int prevVertex;
1725  int nextVertex;
1726 
1727  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1728 
1729  // Previous vertex is the last one if the current vertex is the first one
1730  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1731 
1732  // next vertex is the first one if the current vertex is the last one.
1733  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1734 
1735  // Previous vertex computation
1736  double xa = currContour.CPoint( prevVertex ).x - x1;
1737  double ya = currContour.CPoint( prevVertex ).y - y1;
1738 
1739  // Next vertex computation
1740  double xb = currContour.CPoint( nextVertex ).x - x1;
1741  double yb = currContour.CPoint( nextVertex ).y - y1;
1742 
1743  // Compute the new distances
1744  double lena = hypot( xa, ya );
1745  double lenb = hypot( xb, yb );
1746 
1747  // Make the final computations depending on the mode selected, chamfered or filleted.
1748  if( aMode == CORNER_MODE::CHAMFERED )
1749  {
1750  double distance = aDistance;
1751 
1752  // Chamfer one half of an edge at most
1753  if( 0.5 * lena < distance )
1754  distance = 0.5 * lena;
1755 
1756  if( 0.5 * lenb < distance )
1757  distance = 0.5 * lenb;
1758 
1759  int nx1 = KiROUND( distance * xa / lena );
1760  int ny1 = KiROUND( distance * ya / lena );
1761 
1762  newContour.Append( x1 + nx1, y1 + ny1 );
1763 
1764  int nx2 = KiROUND( distance * xb / lenb );
1765  int ny2 = KiROUND( distance * yb / lenb );
1766 
1767  newContour.Append( x1 + nx2, y1 + ny2 );
1768  }
1769  else // CORNER_MODE = FILLETED
1770  {
1771  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1772 
1773  double radius = aDistance;
1774  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1775 
1776  // Do nothing in case of parallel edges
1777  if( std::isinf( denom ) )
1778  continue;
1779 
1780  // Limit rounding distance to one half of an edge
1781  if( 0.5 * lena * denom < radius )
1782  radius = 0.5 * lena * denom;
1783 
1784  if( 0.5 * lenb * denom < radius )
1785  radius = 0.5 * lenb * denom;
1786 
1787  // Calculate fillet arc absolute center point (xc, yx)
1788  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1789  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1790  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1791  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1792  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1793 
1794  // Calculate arc start and end vectors
1795  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1796  double xs = x1 + k * xa / lena - xc;
1797  double ys = y1 + k * ya / lena - yc;
1798  double xe = x1 + k * xb / lenb - xc;
1799  double ye = y1 + k * yb / lenb - yc;
1800 
1801  // Cosine of arc angle
1802  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1803 
1804  // Make sure the argument is in [-1,1], interval in which the acos function is
1805  // defined
1806  if( argument < -1 )
1807  argument = -1;
1808  else if( argument > 1 )
1809  argument = 1;
1810 
1811  double arcAngle = acos( argument );
1812  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1813  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1814 
1815  double deltaAngle = arcAngle / segments;
1816  double startAngle = atan2( -ys, xs );
1817 
1818  // Flip arc for inner corners
1819  if( xa * yb - ya * xb <= 0 )
1820  deltaAngle *= -1;
1821 
1822  double nx = xc + xs;
1823  double ny = yc + ys;
1824 
1825  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1826 
1827  // Store the previous added corner to make a sanity check
1828  int prevX = KiROUND( nx );
1829  int prevY = KiROUND( ny );
1830 
1831  for( int j = 0; j < segments; j++ )
1832  {
1833  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1834  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1835 
1836  // Sanity check: the rounding can produce repeated corners; do not add them.
1837  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1838  {
1839  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1840  prevX = KiROUND( nx );
1841  prevY = KiROUND( ny );
1842  }
1843  }
1844  }
1845  }
1846 
1847  // Close the current contour and add it the new polygon
1848  newContour.SetClosed( true );
1849  newPoly.push_back( newContour );
1850  }
1851 
1852  return newPoly;
1853 }
1854 
1855 
1857 {
1858  static_cast<SHAPE&>(*this) = aOther;
1859  m_polys = aOther.m_polys;
1860  m_triangulatedPolys.clear();
1861  m_triangulationValid = false;
1862 
1863  if( aOther.IsTriangulationUpToDate() )
1864  {
1865  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
1866  m_triangulatedPolys.push_back(
1867  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
1868 
1869  m_hash = aOther.GetHash();
1870  m_triangulationValid = true;
1871  }
1872 
1873  return *this;
1874 }
1875 
1877 {
1878  if( !m_hash.IsValid() )
1879  return checksum();
1880 
1881  return m_hash;
1882 }
1883 
1884 
1886 {
1887  if( !m_triangulationValid )
1888  return false;
1889 
1890  if( !m_hash.IsValid() )
1891  return false;
1892 
1893  auto hash = checksum();
1894 
1895  return hash == m_hash;
1896 }
1897 
1898 
1900  const SHAPE_POLY_SET& aPoly, int aSize, SHAPE_POLY_SET& aOut )
1901 {
1902  BOX2I bb = aPoly.BBox();
1903 
1904  double w = bb.GetWidth();
1905  double h = bb.GetHeight();
1906 
1907  if( w == 0.0 || h == 0.0 )
1908  return;
1909 
1910  int n_cells_x, n_cells_y;
1911 
1912  if( w > h )
1913  {
1914  n_cells_x = w / aSize;
1915  n_cells_y = floor( h / w * n_cells_x ) + 1;
1916  }
1917  else
1918  {
1919  n_cells_y = h / aSize;
1920  n_cells_x = floor( w / h * n_cells_y ) + 1;
1921  }
1922 
1923  SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
1924 
1925  for( int yy = 0; yy < n_cells_y; yy++ )
1926  for( int xx = 0; xx < n_cells_x; xx++ )
1927  {
1928  VECTOR2I p;
1929 
1930  p.x = bb.GetX() + w * xx / n_cells_x;
1931  p.y = bb.GetY() + h * yy / n_cells_y;
1932 
1933  VECTOR2I p2;
1934 
1935  p2.x = bb.GetX() + w * ( xx + 1 ) / n_cells_x;
1936  p2.y = bb.GetY() + h * ( yy + 1 ) / n_cells_y;
1937 
1938 
1939  SHAPE_LINE_CHAIN mask;
1940  mask.Append( VECTOR2I( p.x, p.y ) );
1941  mask.Append( VECTOR2I( p2.x, p.y ) );
1942  mask.Append( VECTOR2I( p2.x, p2.y ) );
1943  mask.Append( VECTOR2I( p.x, p2.y ) );
1944  mask.SetClosed( true );
1945 
1946  if( ( xx ^ yy ) & 1 )
1947  maskSetOdd.AddOutline( mask );
1948  else
1949  maskSetEven.AddOutline( mask );
1950  }
1951 
1952  ps1.BooleanIntersection( maskSetOdd, SHAPE_POLY_SET::PM_FAST );
1953  ps2.BooleanIntersection( maskSetEven, SHAPE_POLY_SET::PM_FAST );
1954  ps1.Fracture( SHAPE_POLY_SET::PM_FAST );
1955  ps2.Fracture( SHAPE_POLY_SET::PM_FAST );
1956 
1957  aOut = ps1;
1958  for( int i = 0; i < ps2.OutlineCount(); i++ )
1959  {
1960  aOut.AddOutline( ps2.COutline( i ) );
1961  }
1962 
1963  if( !aOut.OutlineCount() )
1964  aOut = aPoly;
1965 }
1966 
1967 
1968 void SHAPE_POLY_SET::CacheTriangulation( bool aPartition )
1969 {
1970  bool recalculate = !m_hash.IsValid();
1971  MD5_HASH hash;
1972 
1973  if( !m_triangulationValid )
1974  recalculate = true;
1975 
1976  if( !recalculate )
1977  {
1978  hash = checksum();
1979 
1980  if( m_hash != hash )
1981  {
1982  m_hash = hash;
1983  recalculate = true;
1984  }
1985  }
1986 
1987  if( !recalculate )
1988  return;
1989 
1990  SHAPE_POLY_SET tmpSet;
1991 
1992  if( aPartition )
1993  // This partitions into regularly-sized grids (1cm in pcbnew)
1994  partitionPolyIntoRegularCellGrid( *this, 1e7, tmpSet );
1995  else
1996  {
1997  tmpSet = *this;
1998 
1999  if( tmpSet.HasHoles() )
2000  tmpSet.Fracture( PM_FAST );
2001  }
2002 
2003  m_triangulatedPolys.clear();
2004  m_triangulationValid = true;
2005 
2006  while( tmpSet.OutlineCount() > 0 )
2007  {
2008  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2009  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2010 
2011  // If the tesselation fails, we re-fracture the polygon, which will
2012  // first simplify the system before fracturing and removing the holes
2013  // This may result in multiple, disjoint polygons.
2014  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2015  {
2016  tmpSet.Fracture( PM_FAST );
2017  m_triangulationValid = false;
2018  continue;
2019  }
2020 
2021  tmpSet.DeletePolygon( 0 );
2022  m_triangulationValid = true;
2023  }
2024 
2025  if( m_triangulationValid )
2026  m_hash = checksum();
2027 }
2028 
2029 
2031 {
2032  MD5_HASH hash;
2033 
2034  hash.Hash( m_polys.size() );
2035 
2036  for( const auto& outline : m_polys )
2037  {
2038  hash.Hash( outline.size() );
2039 
2040  for( const auto& lc : outline )
2041  {
2042  hash.Hash( lc.PointCount() );
2043 
2044  for( int i = 0; i < lc.PointCount(); i++ )
2045  {
2046  hash.Hash( lc.CPoint( i ).x );
2047  hash.Hash( lc.CPoint( i ).y );
2048  }
2049  }
2050  }
2051 
2052  hash.Finalize();
2053 
2054  return hash;
2055 }
2056 
2057 
2059 {
2060  for( int i = 0; i < OutlineCount(); i++ )
2061  {
2062  if( hasTouchingHoles( CPolygon( i ) ) )
2063  {
2064  return true;
2065  }
2066  }
2067 
2068  return false;
2069 }
2070 
2071 
2072 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
2073 {
2074  std::set< long long > ptHashes;
2075 
2076  for( const auto& lc : aPoly )
2077  {
2078  for( const VECTOR2I& pt : lc.CPoints() )
2079  {
2080  const long long ptHash = (long long) pt.x << 32 | pt.y;
2081 
2082  if( ptHashes.count( ptHash ) > 0 )
2083  {
2084  return true;
2085  }
2086 
2087  ptHashes.insert( ptHash );
2088  }
2089  }
2090 
2091  return false;
2092 }
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:126
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
coord_type GetX() const
Definition: box2.h:190
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
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...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
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
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
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
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:65
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
Acute angles are rounded.
#define NULL
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
bool IsClosed() const override
Function IsClosed()
SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
coord_type GetWidth() const
Definition: box2.h:197
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
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:120
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:386
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.
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
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,...
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
coord_type GetY() const
Definition: box2.h:191
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...
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
simple polygon
Definition: shape.h:47
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
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:123
SHAPE_LINE_CHAIN.
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Function Fillet returns a filleted version of the aIndex-th polygon.
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)
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
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
coord_type GetHeight() const
Definition: box2.h:198
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.
void Finalize()
Definition: md5_hash.cpp:75
void CacheTriangulation(bool aPartition=true)
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
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.