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-2017 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 
30 #include <vector>
31 #include <cstdio>
32 #include <set>
33 #include <list>
34 #include <algorithm>
35 #include <unordered_set>
36 
37 #include <common.h>
38 #include <md5_hash.h>
39 #include <map>
40 
41 #include <geometry/shape.h>
44 
45 #include "poly2tri/poly2tri.h"
46 
47 using namespace ClipperLib;
48 
51 {
52 }
53 
54 
56  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
57 {
58 }
59 
60 
62 {
63 }
64 
65 
67 {
68  return new SHAPE_POLY_SET( *this );
69 }
70 
71 
73  SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
74 {
75  int polygonIdx = 0;
76  unsigned int contourIdx = 0;
77  int vertexIdx = 0;
78 
79  int currentGlobalIdx = 0;
80 
81  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
82  {
83  const POLYGON currentPolygon = CPolygon( polygonIdx );
84 
85  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
86  {
87  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
88  int totalPoints = currentContour.PointCount();
89 
90  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
91  {
92  // Check if the current vertex is the globally indexed as aGlobalIdx
93  if( currentGlobalIdx == aGlobalIdx )
94  {
95  aRelativeIndices->m_polygon = polygonIdx;
96  aRelativeIndices->m_contour = contourIdx;
97  aRelativeIndices->m_vertex = vertexIdx;
98 
99  return true;
100  }
101 
102  // Advance
103  currentGlobalIdx++;
104  }
105  }
106  }
107 
108  return false;
109 }
110 
111 
113  int& aGlobalIdx )
114 {
115  int selectedVertex = aRelativeIndices.m_vertex;
116  unsigned int selectedContour = aRelativeIndices.m_contour;
117  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
118 
119  // Check whether the vertex indices make sense in this poly set
120  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
121  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
122  {
123  POLYGON currentPolygon;
124 
125  aGlobalIdx = 0;
126 
127  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
128  {
129  currentPolygon = Polygon( polygonIdx );
130 
131  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
132  {
133  aGlobalIdx += currentPolygon[contourIdx].PointCount();
134  }
135  }
136 
137  currentPolygon = Polygon( selectedPolygon );
138 
139  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
140  {
141  aGlobalIdx += currentPolygon[contourIdx].PointCount();
142  }
143 
144  aGlobalIdx += selectedVertex;
145 
146  return true;
147  }
148  else
149  {
150  return false;
151  }
152 }
153 
154 
156 {
157  SHAPE_LINE_CHAIN empty_path;
158  POLYGON poly;
159 
160  empty_path.SetClosed( true );
161  poly.push_back( empty_path );
162  m_polys.push_back( poly );
163  return m_polys.size() - 1;
164 }
165 
166 
167 int SHAPE_POLY_SET::NewHole( int aOutline )
168 {
169  SHAPE_LINE_CHAIN empty_path;
170 
171  empty_path.SetClosed( true );
172 
173  // Default outline is the last one
174  if( aOutline < 0 )
175  aOutline += m_polys.size();
176 
177  // Add hole to the selected outline
178  m_polys[aOutline].push_back( empty_path );
179 
180  return m_polys.back().size() - 2;
181 }
182 
183 
184 int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
185 {
186  if( aOutline < 0 )
187  aOutline += m_polys.size();
188 
189  int idx;
190 
191  if( aHole < 0 )
192  idx = 0;
193  else
194  idx = aHole + 1;
195 
196  assert( aOutline < (int) m_polys.size() );
197  assert( idx < (int) m_polys[aOutline].size() );
198 
199  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
200 
201  return m_polys[aOutline][idx].PointCount();
202 }
203 
204 
205 void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex )
206 {
207  VERTEX_INDEX index;
208 
209  if( aGlobalIndex < 0 )
210  aGlobalIndex = 0;
211 
212  if( aGlobalIndex >= TotalVertices() )
213  {
214  Append( aNewVertex );
215  }
216  else
217  {
218  // Assure the position to be inserted exists; throw an exception otherwise
219  if( GetRelativeIndices( aGlobalIndex, &index ) )
220  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
221  else
222  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
223  }
224 }
225 
226 
227 int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
228 {
229  if( m_polys.size() == 0 ) // Empty poly set
230  return 0;
231 
232  if( aOutline < 0 ) // Use last outline
233  aOutline += m_polys.size();
234 
235  int idx;
236 
237  if( aHole < 0 )
238  idx = 0;
239  else
240  idx = aHole + 1;
241 
242  if( aOutline >= (int) m_polys.size() ) // not existing outline
243  return 0;
244 
245  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
246  return 0;
247 
248  return m_polys[aOutline][idx].PointCount();
249 }
250 
251 
252 SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
253 {
254  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
255 
256  SHAPE_POLY_SET newPolySet;
257 
258  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
259  {
260  newPolySet.m_polys.push_back( Polygon( index ) );
261  }
262 
263  return newPolySet;
264 }
265 
266 
267 VECTOR2I& SHAPE_POLY_SET::Vertex( int aIndex, int aOutline, int aHole )
268 {
269  if( aOutline < 0 )
270  aOutline += m_polys.size();
271 
272  int idx;
273 
274  if( aHole < 0 )
275  idx = 0;
276  else
277  idx = aHole + 1;
278 
279  assert( aOutline < (int) m_polys.size() );
280  assert( idx < (int) m_polys[aOutline].size() );
281 
282  return m_polys[aOutline][idx].Point( aIndex );
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 VECTOR2I& SHAPE_POLY_SET::Vertex( int aGlobalIndex )
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].Point( index.m_vertex );
314 }
315 
316 
317 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
318 {
320 
321  // Assure the passed index references a legal position; abort otherwise
322  if( !GetRelativeIndices( aGlobalIndex, &index ) )
323  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
324 
325  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
326 }
327 
328 
330 {
331  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
332 }
333 
334 
336 {
337  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
338 }
339 
340 
341 bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext )
342 {
344 
345  // If the edge does not exist, throw an exception, it is an illegal access memory error
346  if( !GetRelativeIndices( aGlobalIndex, &index ) )
347  return false;
348 
349  // Calculate the previous and next index of aGlobalIndex, corresponding to
350  // the same contour;
351  VERTEX_INDEX inext = index;
352  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
353 
354  if( index.m_vertex == 0 )
355  {
356  index.m_vertex = lastpoint;
357  inext.m_vertex = 1;
358  }
359  else if( index.m_vertex == lastpoint )
360  {
361  index.m_vertex--;
362  inext.m_vertex = 0;
363  }
364  else
365  {
366  inext.m_vertex++;
367  index.m_vertex--;
368  }
369 
370  if( aPrevious )
371  {
372  int previous;
373  GetGlobalIndex( index, previous );
374  *aPrevious = previous;
375  }
376 
377  if( aNext )
378  {
379  int next;
380  GetGlobalIndex( inext, next );
381  *aNext = next;
382  }
383 
384  return true;
385 }
386 
387 
389 {
390  // Get polygon
391  const POLYGON poly = CPolygon( aPolygonIndex );
392 
393  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
394  SEGMENT_ITERATOR innerIterator;
395 
396  for( iterator = IterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
397  {
398  SEG firstSegment = *iterator;
399 
400  // Iterate through all remaining segments.
401  innerIterator = iterator;
402 
403  // Start in the next segment, we don't want to check collision between a segment and itself
404  for( innerIterator++; innerIterator; innerIterator++ )
405  {
406  SEG secondSegment = *innerIterator;
407 
408  // Check whether the two segments built collide, only when they are not adjacent.
409  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
410  return true;
411  }
412  }
413 
414  return false;
415 }
416 
417 
419 {
420  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
421  {
422  if( IsPolygonSelfIntersecting( polygon ) )
423  return true;
424  }
425 
426  return false;
427 }
428 
429 
431 {
432  assert( aOutline.IsClosed() );
433 
434  POLYGON poly;
435 
436  poly.push_back( aOutline );
437 
438  m_polys.push_back( poly );
439 
440  return m_polys.size() - 1;
441 }
442 
443 
444 int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
445 {
446  assert( m_polys.size() );
447 
448  if( aOutline < 0 )
449  aOutline += m_polys.size();
450 
451  POLYGON& poly = m_polys[aOutline];
452 
453  assert( poly.size() );
454 
455  poly.push_back( aHole );
456 
457  return poly.size() - 1;
458 }
459 
460 
462  bool aRequiredOrientation )
463 {
464  Path c_path;
465 
466  for( int i = 0; i < aPath.PointCount(); i++ )
467  {
468  const VECTOR2I& vertex = aPath.CPoint( i );
469  c_path.push_back( IntPoint( vertex.x, vertex.y ) );
470  }
471 
472  if( Orientation( c_path ) != aRequiredOrientation )
473  ReversePath( c_path );
474 
475  return c_path;
476 }
477 
478 
480 {
481  SHAPE_LINE_CHAIN lc;
482 
483  for( unsigned int i = 0; i < aPath.size(); i++ )
484  lc.Append( aPath[i].X, aPath[i].Y );
485 
486  lc.SetClosed( true );
487 
488  return lc;
489 }
490 
491 
492 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
493  POLYGON_MODE aFastMode )
494 {
495  Clipper c;
496 
497  if( aFastMode == PM_STRICTLY_SIMPLE )
498  c.StrictlySimple( true );
499 
500  for( const POLYGON& poly : m_polys )
501  {
502  for( unsigned int i = 0; i < poly.size(); i++ )
503  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
504  }
505 
506  for( const POLYGON& poly : aOtherShape.m_polys )
507  {
508  for( unsigned int i = 0; i < poly.size(); i++ )
509  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
510  }
511 
512  PolyTree solution;
513 
514  c.Execute( aType, solution, pftNonZero, pftNonZero );
515 
516  importTree( &solution );
517 }
518 
519 
520 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
521  const SHAPE_POLY_SET& aShape,
522  const SHAPE_POLY_SET& aOtherShape,
523  POLYGON_MODE aFastMode )
524 {
525  Clipper c;
526 
527  if( aFastMode == PM_STRICTLY_SIMPLE )
528  c.StrictlySimple( true );
529 
530  for( const POLYGON& poly : aShape.m_polys )
531  {
532  for( unsigned int i = 0; i < poly.size(); i++ )
533  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
534  }
535 
536  for( const POLYGON& poly : aOtherShape.m_polys )
537  {
538  for( unsigned int i = 0; i < poly.size(); i++ )
539  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
540  }
541 
542  PolyTree solution;
543 
544  c.Execute( aType, solution, pftNonZero, pftNonZero );
545 
546  importTree( &solution );
547 }
548 
549 
551 {
552  booleanOp( ctUnion, b, aFastMode );
553 }
554 
555 
557 {
558  booleanOp( ctDifference, b, aFastMode );
559 }
560 
561 
563 {
564  booleanOp( ctIntersection, b, aFastMode );
565 }
566 
567 
569  const SHAPE_POLY_SET& b,
570  POLYGON_MODE aFastMode )
571 {
572  booleanOp( ctUnion, a, b, aFastMode );
573 }
574 
575 
577  const SHAPE_POLY_SET& b,
578  POLYGON_MODE aFastMode )
579 {
580  booleanOp( ctDifference, a, b, aFastMode );
581 }
582 
583 
585  const SHAPE_POLY_SET& b,
586  POLYGON_MODE aFastMode )
587 {
588  booleanOp( ctIntersection, a, b, aFastMode );
589 }
590 
591 
592 void SHAPE_POLY_SET::Inflate( int aFactor, int aCircleSegmentsCount )
593 {
594  // A static table to avoid repetitive calculations of the coefficient
595  // 1.0 - cos( M_PI/aCircleSegmentsCount)
596  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
597  #define SEG_CNT_MAX 64
598  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
599 
600  ClipperOffset c;
601 
602  for( const POLYGON& poly : m_polys )
603  {
604  for( unsigned int i = 0; i < poly.size(); i++ )
605  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), jtRound,
606  etClosedPolygon );
607  }
608 
609  PolyTree solution;
610 
611  // Calculate the arc tolerance (arc error) from the seg count by circle.
612  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
613  // see:
614  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
615 
616  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
617  aCircleSegmentsCount = 6;
618 
619  double coeff;
620 
621  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
622  {
623  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
624 
625  if( aCircleSegmentsCount <= SEG_CNT_MAX )
626  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
627  }
628  else
629  coeff = arc_tolerance_factor[aCircleSegmentsCount];
630 
631  c.ArcTolerance = std::abs( aFactor ) * coeff;
632 
633  c.Execute( solution, aFactor );
634 
635  importTree( &solution );
636 }
637 
638 
639 void SHAPE_POLY_SET::importTree( PolyTree* tree )
640 {
641  m_polys.clear();
642 
643  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
644  {
645  if( !n->IsHole() )
646  {
647  POLYGON paths;
648  paths.reserve( n->Childs.size() + 1 );
649  paths.push_back( convertFromClipper( n->Contour ) );
650 
651  for( unsigned int i = 0; i < n->Childs.size(); i++ )
652  paths.push_back( convertFromClipper( n->Childs[i]->Contour ) );
653 
654  m_polys.push_back( paths );
655  }
656  }
657 }
658 
659 
661 {
662  FractureEdge( bool connected, SHAPE_LINE_CHAIN* owner, int index ) :
663  m_connected( connected ),
664  m_next( NULL )
665  {
666  m_p1 = owner->CPoint( index );
667  m_p2 = owner->CPoint( index + 1 );
668  }
669 
670  FractureEdge( int y = 0 ) :
671  m_connected( false ),
672  m_next( NULL )
673  {
674  m_p1.x = m_p2.y = y;
675  }
676 
677  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
678  m_connected( connected ),
679  m_p1( p1 ),
680  m_p2( p2 ),
681  m_next( NULL )
682  {
683  }
684 
685  bool matches( int y ) const
686  {
687  int y_min = std::min( m_p1.y, m_p2.y );
688  int y_max = std::max( m_p1.y, m_p2.y );
689 
690  return ( y >= y_min ) && ( y <= y_max );
691  }
692 
694  VECTOR2I m_p1, m_p2;
696 };
697 
698 
699 typedef std::vector<FractureEdge*> FractureEdgeSet;
700 
701 
702 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
703 {
704  int x = edge->m_p1.x;
705  int y = edge->m_p1.y;
706  int min_dist = std::numeric_limits<int>::max();
707  int x_nearest = 0;
708 
709  FractureEdge* e_nearest = NULL;
710 
711  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
712  {
713  if( !(*i)->matches( y ) )
714  continue;
715 
716  int x_intersect;
717 
718  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
719  x_intersect = std::max( (*i)->m_p1.x, (*i)->m_p2.x );
720  else
721  x_intersect = (*i)->m_p1.x + rescale( (*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y,
722  (*i)->m_p2.y - (*i)->m_p1.y );
723 
724  int dist = ( x - x_intersect );
725 
726  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
727  {
728  min_dist = dist;
729  x_nearest = x_intersect;
730  e_nearest = (*i);
731  }
732  }
733 
734  if( e_nearest && e_nearest->m_connected )
735  {
736  int count = 0;
737 
738  FractureEdge* lead1 =
739  new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
740  FractureEdge* lead2 =
741  new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
742  FractureEdge* split_2 =
743  new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
744 
745  edges.push_back( split_2 );
746  edges.push_back( lead1 );
747  edges.push_back( lead2 );
748 
749  FractureEdge* link = e_nearest->m_next;
750 
751  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
752  e_nearest->m_next = lead1;
753  lead1->m_next = edge;
754 
755  FractureEdge* last;
756 
757  for( last = edge; last->m_next != edge; last = last->m_next )
758  {
759  last->m_connected = true;
760  count++;
761  }
762 
763  last->m_connected = true;
764  last->m_next = lead2;
765  lead2->m_next = split_2;
766  split_2->m_next = link;
767 
768  return count + 1;
769  }
770 
771  return 0;
772 }
773 
774 
776 {
777  FractureEdgeSet edges;
778  FractureEdgeSet border_edges;
779  FractureEdge* root = NULL;
780 
781  bool first = true;
782 
783  if( paths.size() == 1 )
784  return;
785 
786  int num_unconnected = 0;
787 
788  for( SHAPE_LINE_CHAIN& path : paths )
789  {
790  int index = 0;
791 
792  FractureEdge* prev = NULL, * first_edge = NULL;
793 
794  int x_min = std::numeric_limits<int>::max();
795 
796  for( int i = 0; i < path.PointCount(); i++ )
797  {
798  const VECTOR2I& p = path.CPoint( i );
799 
800  if( p.x < x_min )
801  x_min = p.x;
802  }
803 
804  for( int i = 0; i < path.PointCount(); i++ )
805  {
806  FractureEdge* fe = new FractureEdge( first, &path, index++ );
807 
808  if( !root )
809  root = fe;
810 
811  if( !first_edge )
812  first_edge = fe;
813 
814  if( prev )
815  prev->m_next = fe;
816 
817  if( i == path.PointCount() - 1 )
818  fe->m_next = first_edge;
819 
820  prev = fe;
821  edges.push_back( fe );
822 
823  if( !first )
824  {
825  if( fe->m_p1.x == x_min )
826  border_edges.push_back( fe );
827  }
828 
829  if( !fe->m_connected )
830  num_unconnected++;
831  }
832 
833  first = false; // first path is always the outline
834  }
835 
836  // keep connecting holes to the main outline, until there's no holes left...
837  while( num_unconnected > 0 )
838  {
839  int x_min = std::numeric_limits<int>::max();
840 
841  FractureEdge* smallestX = NULL;
842 
843  // find the left-most hole edge and merge with the outline
844  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
845  {
846  int xt = (*i)->m_p1.x;
847 
848  if( ( xt < x_min ) && !(*i)->m_connected )
849  {
850  x_min = xt;
851  smallestX = *i;
852  }
853  }
854 
855  num_unconnected -= processEdge( edges, smallestX );
856  }
857 
858  paths.clear();
859  SHAPE_LINE_CHAIN newPath;
860 
861  newPath.SetClosed( true );
862 
863  FractureEdge* e;
864 
865  for( e = root; e->m_next != root; e = e->m_next )
866  newPath.Append( e->m_p1 );
867 
868  newPath.Append( e->m_p1 );
869 
870  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
871  delete *i;
872 
873  paths.push_back( newPath );
874 }
875 
876 
878 {
879  Simplify( aFastMode ); // remove overlapping holes/degeneracy
880 
881  for( POLYGON& paths : m_polys )
882  {
883  fractureSingle( paths );
884  }
885 }
886 
887 
889 {
890  assert( aPoly.size() == 1 );
891 
892  struct EDGE
893  {
894  int m_index = 0;
895  SHAPE_LINE_CHAIN* m_poly = nullptr;
896  bool m_duplicate = false;
897 
898  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
899  m_index( aIndex ),
900  m_poly( aPolygon )
901  {}
902 
903  bool compareSegs( const SEG& s1, const SEG& s2 ) const
904  {
905  return (s1.A == s2.B && s1.B == s2.A);
906  }
907 
908  bool operator==( const EDGE& aOther ) const
909  {
910  return compareSegs( m_poly->CSegment( m_index ),
911  aOther.m_poly->CSegment( aOther.m_index ) );
912  }
913 
914  bool operator!=( const EDGE& aOther ) const
915  {
916  return !compareSegs( m_poly->CSegment( m_index ),
917  aOther.m_poly->CSegment( aOther.m_index ) );
918  }
919 
920  struct HASH
921  {
922  std::size_t operator()( const EDGE& aEdge ) const
923  {
924  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
925 
926  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
927  }
928  };
929  };
930 
931  struct EDGE_LIST_ENTRY
932  {
933  int index;
934  EDGE_LIST_ENTRY* next;
935  };
936 
937  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
938 
939  auto lc = aPoly[0];
940  lc.Simplify();
941 
942  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
943 
944  for( int i = 0; i < lc.SegmentCount(); i++ )
945  {
946  edgeList[i].index = i;
947  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
948  }
949 
950  std::unordered_set<EDGE_LIST_ENTRY*> queue;
951 
952  for( int i = 0; i < lc.SegmentCount(); i++ )
953  {
954  EDGE e( &lc, i );
955  uniqueEdges.insert( e );
956  }
957 
958  for( int i = 0; i < lc.SegmentCount(); i++ )
959  {
960  EDGE e( &lc, i );
961  auto it = uniqueEdges.find( e );
962 
963  if( it != uniqueEdges.end() && it->m_index != i )
964  {
965  int e1 = it->m_index;
966  int e2 = i;
967 
968  if( e1 > e2 )
969  std::swap( e1, e2 );
970 
971  int e1_prev = e1 - 1;
972 
973  if( e1_prev < 0 )
974  e1_prev = lc.SegmentCount() - 1;
975 
976  int e2_prev = e2 - 1;
977 
978  if( e2_prev < 0 )
979  e2_prev = lc.SegmentCount() - 1;
980 
981  int e1_next = e1 + 1;
982 
983  if( e1_next == lc.SegmentCount() )
984  e1_next = 0;
985 
986  int e2_next = e2 + 1;
987 
988  if( e2_next == lc.SegmentCount() )
989  e2_next = 0;
990 
991  edgeList[e1_prev].next = &edgeList[ e2_next ];
992  edgeList[e2_prev].next = &edgeList[ e1_next ];
993  edgeList[i].next = nullptr;
994  edgeList[it->m_index].next = nullptr;
995  }
996  }
997 
998  for( int i = 0; i < lc.SegmentCount(); i++ )
999  {
1000  if( edgeList[i].next )
1001  queue.insert( &edgeList[i] );
1002  }
1003 
1004  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1005 
1006  int n = 0;
1007  int outline = -1;
1008 
1009  POLYGON result;
1010 
1011  while( queue.size() )
1012  {
1013  auto e_first = (*queue.begin() );
1014  auto e = e_first;
1015  int cnt = 0;
1016 
1017  do {
1018  edgeBuf[cnt++] = e;
1019  e = e->next;
1020  } while( e && e != e_first );
1021 
1022  SHAPE_LINE_CHAIN outl;
1023 
1024  for( int i = 0; i < cnt; i++ )
1025  {
1026  auto p = lc.CPoint( edgeBuf[i]->index );
1027  outl.Append( p );
1028  queue.erase( edgeBuf[i] );
1029  }
1030 
1031  outl.SetClosed( true );
1032 
1033  bool cw = outl.Area() > 0.0;
1034 
1035  if( cw )
1036  outline = n;
1037 
1038  result.push_back( outl );
1039  n++;
1040  }
1041 
1042  if( outline > 0 )
1043  std::swap( result[0], result[outline] );
1044 
1045  aPoly = result;
1046 }
1047 
1048 
1050 {
1051  // Iterate through all the polygons on the set
1052  for( const POLYGON& paths : m_polys )
1053  {
1054  // If any of them has more than one contour, it is a hole.
1055  if( paths.size() > 1 )
1056  return true;
1057  }
1058 
1059  // Return false if and only if every polygon has just one outline, without holes.
1060  return false;
1061 }
1062 
1063 
1065 {
1066  for( POLYGON& path : m_polys )
1067  {
1068  unfractureSingle( path );
1069  }
1070 
1071  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1072 }
1073 
1074 
1076 {
1078 
1079  booleanOp( ctUnion, empty, aFastMode );
1080 }
1081 
1082 
1084 {
1085  // We are expecting only one main outline, but this main outline can have holes
1086  // if holes: combine holes and remove them from the main outline.
1087  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1088  // calculations, but it is not mandatory. It is used mainly
1089  // because there is usually only very few vertices in area outlines
1090  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1091  SHAPE_POLY_SET holesBuffer;
1092 
1093  // Move holes stored in outline to holesBuffer:
1094  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1095  while( outline.size() > 1 )
1096  {
1097  holesBuffer.AddOutline( outline.back() );
1098  outline.pop_back();
1099  }
1100 
1102 
1103  // If any hole, substract it to main outline
1104  if( holesBuffer.OutlineCount() )
1105  {
1106  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1108  }
1109 
1111 
1112  return OutlineCount();
1113 }
1114 
1115 
1116 const std::string SHAPE_POLY_SET::Format() const
1117 {
1118  std::stringstream ss;
1119 
1120  ss << "polyset " << m_polys.size() << "\n";
1121 
1122  for( unsigned i = 0; i < m_polys.size(); i++ )
1123  {
1124  ss << "poly " << m_polys[i].size() << "\n";
1125 
1126  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1127  {
1128  ss << m_polys[i][j].PointCount() << "\n";
1129 
1130  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1131  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1132  }
1133 
1134  ss << "\n";
1135  }
1136 
1137  return ss.str();
1138 }
1139 
1140 
1141 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1142 {
1143  std::string tmp;
1144 
1145  aStream >> tmp;
1146 
1147  if( tmp != "polyset" )
1148  return false;
1149 
1150  aStream >> tmp;
1151 
1152  int n_polys = atoi( tmp.c_str() );
1153 
1154  if( n_polys < 0 )
1155  return false;
1156 
1157  for( int i = 0; i < n_polys; i++ )
1158  {
1159  POLYGON paths;
1160 
1161  aStream >> tmp;
1162 
1163  if( tmp != "poly" )
1164  return false;
1165 
1166  aStream >> tmp;
1167  int n_outlines = atoi( tmp.c_str() );
1168 
1169  if( n_outlines < 0 )
1170  return false;
1171 
1172  for( int j = 0; j < n_outlines; j++ )
1173  {
1174  SHAPE_LINE_CHAIN outline;
1175 
1176  outline.SetClosed( true );
1177 
1178  aStream >> tmp;
1179  int n_vertices = atoi( tmp.c_str() );
1180 
1181  for( int v = 0; v < n_vertices; v++ )
1182  {
1183  VECTOR2I p;
1184 
1185  aStream >> tmp; p.x = atoi( tmp.c_str() );
1186  aStream >> tmp; p.y = atoi( tmp.c_str() );
1187  outline.Append( p );
1188  }
1189 
1190  paths.push_back( outline );
1191  }
1192 
1193  m_polys.push_back( paths );
1194  }
1195 
1196  return true;
1197 }
1198 
1199 
1200 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1201 {
1202  BOX2I bb;
1203 
1204  for( unsigned i = 0; i < m_polys.size(); i++ )
1205  {
1206  if( i == 0 )
1207  bb = m_polys[i][0].BBox();
1208  else
1209  bb.Merge( m_polys[i][0].BBox() );
1210  }
1211 
1212  bb.Inflate( aClearance );
1213  return bb;
1214 }
1215 
1216 
1217 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1218 {
1219  // Iterate through all the polygons in the set
1220  for( const POLYGON& polygon : m_polys )
1221  {
1222  // Iterate through all the line chains in the polygon
1223  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1224  {
1225  if( lineChain.PointOnEdge( aP ) )
1226  return true;
1227  }
1228  }
1229 
1230  return false;
1231 }
1232 
1233 
1234 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1235 {
1236  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1237 
1238  // Inflate the polygon if necessary.
1239  if( aClearance > 0 )
1240  {
1241  // fixme: the number of arc segments should not be hardcoded
1242  polySet.Inflate( aClearance, 8 );
1243  }
1244 
1245  // There is a collision if and only if the point is inside of the polygon.
1246  return polySet.Contains( aP );
1247 }
1248 
1249 
1251 {
1252  m_polys.clear();
1253 }
1254 
1255 
1256 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1257 {
1258  // Default polygon is the last one
1259  if( aPolygonIdx < 0 )
1260  aPolygonIdx += m_polys.size();
1261 
1262  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1263 }
1264 
1265 
1267 {
1268  int removed = 0;
1269 
1270  ITERATOR iterator = IterateWithHoles();
1271 
1272  VECTOR2I contourStart = *iterator;
1273  VECTOR2I segmentStart, segmentEnd;
1274 
1275  VERTEX_INDEX indexStart;
1276 
1277  while( iterator )
1278  {
1279  // Obtain first point and its index
1280  segmentStart = *iterator;
1281  indexStart = iterator.GetIndex();
1282 
1283  // Obtain last point
1284  if( iterator.IsEndContour() )
1285  {
1286  segmentEnd = contourStart;
1287 
1288  // Advance
1289  iterator++;
1290 
1291  if( iterator )
1292  contourStart = *iterator;
1293  }
1294  else
1295  {
1296  // Advance
1297  iterator++;
1298 
1299  if( iterator )
1300  segmentEnd = *iterator;
1301  }
1302 
1303  // Remove segment start if both points are equal
1304  if( segmentStart == segmentEnd )
1305  {
1306  RemoveVertex( indexStart );
1307  removed++;
1308 
1309  // Advance the iterator one position, as there is one vertex less.
1310  if( iterator )
1311  iterator++;
1312  }
1313  }
1314 
1315  return removed;
1316 }
1317 
1318 
1320 {
1321  m_polys.erase( m_polys.begin() + aIdx );
1322 }
1323 
1324 
1326 {
1327  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1328 }
1329 
1330 
1331 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1332 {
1333  Append( aP.x, aP.y, aOutline, aHole );
1334 }
1335 
1336 
1338  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1339 {
1340  // Shows whether there was a collision
1341  bool collision = false;
1342 
1343  // Difference vector between each vertex and aPoint.
1344  VECTOR2D delta;
1345  double distance, clearance;
1346 
1347  // Convert clearance to double for precission when comparing distances
1348  clearance = aClearance;
1349 
1350  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1351  {
1352  // Get the difference vector between current vertex and aPoint
1353  delta = *iterator - aPoint;
1354 
1355  // Compute distance
1356  distance = delta.EuclideanNorm();
1357 
1358  // Check for collisions
1359  if( distance <= clearance )
1360  {
1361  collision = true;
1362 
1363  // Update aClearance to look for closer vertices
1364  clearance = distance;
1365 
1366  // Store the indices that identify the vertex
1367  aClosestVertex = iterator.GetIndex();
1368  }
1369  }
1370 
1371  return collision;
1372 }
1373 
1374 
1376  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1377 {
1378  // Shows whether there was a collision
1379  bool collision = false;
1380 
1381  SEGMENT_ITERATOR iterator;
1382 
1383  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1384  {
1385  SEG currentSegment = *iterator;
1386  int distance = currentSegment.Distance( aPoint );
1387 
1388  // Check for collisions
1389  if( distance <= aClearance )
1390  {
1391  collision = true;
1392 
1393  // Update aClearance to look for closer edges
1394  aClearance = distance;
1395 
1396  // Store the indices that identify the vertex
1397  aClosestVertex = iterator.GetIndex();
1398  }
1399  }
1400 
1401  return collision;
1402 }
1403 
1404 
1405 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1406 {
1407  if( m_polys.size() == 0 ) // empty set?
1408  return false;
1409 
1410  // If there is a polygon specified, check the condition against that polygon
1411  if( aSubpolyIndex >= 0 )
1412  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1413 
1414  // In any other case, check it against all polygons in the set
1415  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1416  {
1417  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1418  return true;
1419  }
1420 
1421  return false;
1422 }
1423 
1424 
1425 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1426 {
1427  VERTEX_INDEX index;
1428 
1429  // Assure the to be removed vertex exists, abort otherwise
1430  if( GetRelativeIndices( aGlobalIndex, &index ) )
1431  RemoveVertex( index );
1432  else
1433  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1434 }
1435 
1436 
1438 {
1439  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1440 }
1441 
1442 
1443 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1444 {
1445  // Check that the point is inside the outline
1446  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1447  {
1448  if( !aIgnoreHoles )
1449  {
1450  // Check that the point is not in any of the holes
1451  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1452  {
1453  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1454 
1455  // If the point is inside a hole (and not on its edge),
1456  // it is outside of the polygon
1457  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1458  return false;
1459  }
1460  }
1461 
1462  return true;
1463  }
1464 
1465  return false;
1466 }
1467 
1468 
1469 bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
1470 {
1471  int result = 0;
1472  int cnt = aPath.PointCount();
1473 
1474  if( !aPath.BBox().Contains( aP ) ) // test with bounding box first
1475  return false;
1476 
1477  if( cnt < 3 )
1478  return false;
1479 
1480  VECTOR2I ip = aPath.CPoint( 0 );
1481 
1482  for( int i = 1; i <= cnt; ++i )
1483  {
1484  VECTOR2I ipNext = ( i == cnt ? aPath.CPoint( 0 ) : aPath.CPoint( i ) );
1485 
1486  if( ipNext.y == aP.y )
1487  {
1488  if( ( ipNext.x == aP.x ) || ( ip.y == aP.y
1489  && ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
1490  return true;
1491  }
1492 
1493  if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
1494  {
1495  if( ip.x >= aP.x )
1496  {
1497  if( ipNext.x > aP.x )
1498  result = 1 - result;
1499  else
1500  {
1501  int64_t d = (int64_t) ( ip.x - aP.x ) * (int64_t) ( ipNext.y - aP.y ) -
1502  (int64_t) ( ipNext.x - aP.x ) * (int64_t) ( ip.y - aP.y );
1503 
1504  if( !d )
1505  return true;
1506 
1507  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1508  result = 1 - result;
1509  }
1510  }
1511  else
1512  {
1513  if( ipNext.x > aP.x )
1514  {
1515  int64_t d = (int64_t) ( ip.x - aP.x ) * (int64_t) ( ipNext.y - aP.y ) -
1516  (int64_t) ( ipNext.x - aP.x ) * (int64_t) ( ip.y - aP.y );
1517 
1518  if( !d )
1519  return true;
1520 
1521  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1522  result = 1 - result;
1523  }
1524  }
1525  }
1526 
1527  ip = ipNext;
1528  }
1529 
1530  return result ? true : false;
1531 }
1532 
1533 
1534 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1535 {
1536  for( POLYGON& poly : m_polys )
1537  {
1538  for( SHAPE_LINE_CHAIN& path : poly )
1539  {
1540  path.Move( aVector );
1541  }
1542  }
1543 }
1544 
1545 
1546 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1547 {
1548  for( POLYGON& poly : m_polys )
1549  {
1550  for( SHAPE_LINE_CHAIN& path : poly )
1551  {
1552  path.Rotate( aAngle, aCenter );
1553  }
1554  }
1555 }
1556 
1557 
1559 {
1560  int c = 0;
1561 
1562  for( const POLYGON& poly : m_polys )
1563  {
1564  for( const SHAPE_LINE_CHAIN& path : poly )
1565  {
1566  c += path.PointCount();
1567  }
1568  }
1569 
1570  return c;
1571 }
1572 
1573 
1574 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1575 {
1576  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1577 }
1578 
1579 
1581  unsigned int aSegments,
1582  int aIndex )
1583 {
1584  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aSegments );
1585 }
1586 
1587 
1588 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1589 {
1590  // We calculate the min dist between the segment and each outline segment
1591  // However, if the segment to test is inside the outline, and does not cross
1592  // any edge, it can be seen outside the polygon.
1593  // Therefore test if a segment end is inside ( testing only one end is enough )
1594  if( containsSingle( aPoint, aPolygonIndex ) )
1595  return 0;
1596 
1597  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1598 
1599  SEG polygonEdge = *iterator;
1600  int minDistance = polygonEdge.Distance( aPoint );
1601 
1602  for( iterator++; iterator && minDistance > 0; iterator++ )
1603  {
1604  polygonEdge = *iterator;
1605 
1606  int currentDistance = polygonEdge.Distance( aPoint );
1607 
1608  if( currentDistance < minDistance )
1609  minDistance = currentDistance;
1610  }
1611 
1612  return minDistance;
1613 }
1614 
1615 
1616 int SHAPE_POLY_SET::DistanceToPolygon( SEG aSegment, int aPolygonIndex, int aSegmentWidth )
1617 {
1618  // We calculate the min dist between the segment and each outline segment
1619  // However, if the segment to test is inside the outline, and does not cross
1620  // any edge, it can be seen outside the polygon.
1621  // Therefore test if a segment end is inside ( testing only one end is enough )
1622  if( containsSingle( aSegment.A, aPolygonIndex ) )
1623  return 0;
1624 
1625  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1626 
1627  SEG polygonEdge = *iterator;
1628  int minDistance = polygonEdge.Distance( aSegment );
1629 
1630  for( iterator++; iterator && minDistance > 0; iterator++ )
1631  {
1632  polygonEdge = *iterator;
1633 
1634  int currentDistance = polygonEdge.Distance( aSegment );
1635 
1636  if( currentDistance < minDistance )
1637  minDistance = currentDistance;
1638  }
1639 
1640  // Take into account the width of the segment
1641  if( aSegmentWidth > 0 )
1642  minDistance -= aSegmentWidth / 2;
1643 
1644  // Return the maximum of minDistance and zero
1645  return minDistance < 0 ? 0 : minDistance;
1646 }
1647 
1648 
1650 {
1651  int currentDistance;
1652  int minDistance = DistanceToPolygon( aPoint, 0 );
1653 
1654  // Iterate through all the polygons and get the minimum distance.
1655  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1656  {
1657  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1658 
1659  if( currentDistance < minDistance )
1660  minDistance = currentDistance;
1661  }
1662 
1663  return minDistance;
1664 }
1665 
1666 
1667 int SHAPE_POLY_SET::Distance( const SEG& aSegment, int aSegmentWidth )
1668 {
1669  int currentDistance;
1670  int minDistance = DistanceToPolygon( aSegment, 0 );
1671 
1672  // Iterate through all the polygons and get the minimum distance.
1673  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1674  {
1675  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1676 
1677  if( currentDistance < minDistance )
1678  minDistance = currentDistance;
1679  }
1680 
1681  return minDistance;
1682 }
1683 
1684 
1685 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1686 {
1687  VERTEX_INDEX index;
1688 
1689  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1690  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1691  return false;
1692 
1693  // The contour is a hole if its index is greater than zero
1694  return index.m_contour > 0;
1695 }
1696 
1697 
1699 {
1700  SHAPE_POLY_SET chamfered;
1701 
1702  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1703  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1704 
1705  return chamfered;
1706 }
1707 
1708 
1709 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aSegments )
1710 {
1711  SHAPE_POLY_SET filleted;
1712 
1713  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1714  filleted.m_polys.push_back( FilletPolygon( aRadius, aSegments, polygonIdx ) );
1715 
1716  return filleted;
1717 }
1718 
1719 
1721  unsigned int aDistance,
1722  int aIndex,
1723  int aSegments )
1724 {
1725  // Null segments create serious issues in calculations. Remove them:
1727 
1728  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1729  SHAPE_POLY_SET::POLYGON newPoly;
1730 
1731  // If the chamfering distance is zero, then the polygon remain intact.
1732  if( aDistance == 0 )
1733  {
1734  return currentPoly;
1735  }
1736 
1737  // Iterate through all the contours (outline and holes) of the polygon.
1738  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1739  {
1740  // Generate a new contour in the new polygon
1741  SHAPE_LINE_CHAIN newContour;
1742 
1743  // Iterate through the vertices of the contour
1744  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1745  {
1746  // Current vertex
1747  int x1 = currContour.Point( currVertex ).x;
1748  int y1 = currContour.Point( currVertex ).y;
1749 
1750  // Indices for previous and next vertices.
1751  int prevVertex;
1752  int nextVertex;
1753 
1754  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1755 
1756  // Previous vertex is the last one if the current vertex is the first one
1757  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1758 
1759  // next vertex is the first one if the current vertex is the last one.
1760  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1761 
1762  // Previous vertex computation
1763  double xa = currContour.Point( prevVertex ).x - x1;
1764  double ya = currContour.Point( prevVertex ).y - y1;
1765 
1766  // Next vertex computation
1767  double xb = currContour.Point( nextVertex ).x - x1;
1768  double yb = currContour.Point( nextVertex ).y - y1;
1769 
1770  // Compute the new distances
1771  double lena = hypot( xa, ya );
1772  double lenb = hypot( xb, yb );
1773 
1774  // Make the final computations depending on the mode selected, chamfered or filleted.
1775  if( aMode == CORNER_MODE::CHAMFERED )
1776  {
1777  double distance = aDistance;
1778 
1779  // Chamfer one half of an edge at most
1780  if( 0.5 * lena < distance )
1781  distance = 0.5 * lena;
1782 
1783  if( 0.5 * lenb < distance )
1784  distance = 0.5 * lenb;
1785 
1786  int nx1 = KiROUND( distance * xa / lena );
1787  int ny1 = KiROUND( distance * ya / lena );
1788 
1789  newContour.Append( x1 + nx1, y1 + ny1 );
1790 
1791  int nx2 = KiROUND( distance * xb / lenb );
1792  int ny2 = KiROUND( distance * yb / lenb );
1793 
1794  newContour.Append( x1 + nx2, y1 + ny2 );
1795  }
1796  else // CORNER_MODE = FILLETED
1797  {
1798  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1799 
1800  double radius = aDistance;
1801  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1802 
1803  // Do nothing in case of parallel edges
1804  if( std::isinf( denom ) )
1805  continue;
1806 
1807  // Limit rounding distance to one half of an edge
1808  if( 0.5 * lena * denom < radius )
1809  radius = 0.5 * lena * denom;
1810 
1811  if( 0.5 * lenb * denom < radius )
1812  radius = 0.5 * lenb * denom;
1813 
1814  // Calculate fillet arc absolute center point (xc, yx)
1815  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1816  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1817  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1818  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1819  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1820 
1821  // Calculate arc start and end vectors
1822  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1823  double xs = x1 + k * xa / lena - xc;
1824  double ys = y1 + k * ya / lena - yc;
1825  double xe = x1 + k * xb / lenb - xc;
1826  double ye = y1 + k * yb / lenb - yc;
1827 
1828  // Cosine of arc angle
1829  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1830 
1831  // Make sure the argument is in [-1,1], interval in which the acos function is
1832  // defined
1833  if( argument < -1 )
1834  argument = -1;
1835  else if( argument > 1 )
1836  argument = 1;
1837 
1838  double arcAngle = acos( argument );
1839 
1840  // Calculate the number of segments
1841  unsigned int segments = ceil( (double) aSegments * ( arcAngle / ( 2 * M_PI ) ) );
1842 
1843  double deltaAngle = arcAngle / segments;
1844  double startAngle = atan2( -ys, xs );
1845 
1846  // Flip arc for inner corners
1847  if( xa * yb - ya * xb <= 0 )
1848  deltaAngle *= -1;
1849 
1850  double nx = xc + xs;
1851  double ny = yc + ys;
1852 
1853  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1854 
1855  // Store the previous added corner to make a sanity check
1856  int prevX = KiROUND( nx );
1857  int prevY = KiROUND( ny );
1858 
1859  for( unsigned int j = 0; j < segments; j++ )
1860  {
1861  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1862  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1863 
1864  // Sanity check: the rounding can produce repeated corners; do not add them.
1865  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1866  {
1867  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1868  prevX = KiROUND( nx );
1869  prevY = KiROUND( ny );
1870  }
1871  }
1872  }
1873  }
1874 
1875  // Close the current contour and add it the new polygon
1876  newContour.SetClosed( true );
1877  newPoly.push_back( newContour );
1878  }
1879 
1880  return newPoly;
1881 }
1882 
1883 
1885 {
1886  static_cast<SHAPE&>(*this) = aOther;
1887  m_polys = aOther.m_polys;
1888 
1889  // reset poly cache:
1890  m_hash = MD5_HASH{};
1891  m_triangulationValid = false;
1892  m_triangulatedPolys.clear();
1893  return *this;
1894 }
1895 
1896 
1897 
1898 
1900 {
1901 public:
1902 
1904  m_triPoly( aResultPoly )
1905  {
1906  }
1907 
1908  void AddOutline( const SHAPE_LINE_CHAIN& outl, bool aIsHole = false )
1909  {
1910  m_points.reserve( outl.PointCount() );
1911  m_points.clear();
1912 
1913  for( int i = 0; i < outl.PointCount(); i++ )
1914  {
1915  m_points.push_back( addPoint( outl.CPoint( i ) ) );
1916  }
1917 
1918  if ( aIsHole )
1919  m_cdt->AddHole( m_points );
1920  else
1921  {
1922  m_cdt.reset( new p2t::CDT( m_points ) );
1923  }
1924  }
1925 
1927  {
1928  m_cdt->Triangulate();
1929 
1930  m_triPoly->AllocateTriangles( m_cdt->GetTriangles().size() );
1931 
1932  int i = 0;
1933 
1934  for( auto tri : m_cdt->GetTriangles() )
1935  {
1937 
1938  t.a = tri->GetPoint( 0 )->id;
1939  t.b = tri->GetPoint( 1 )->id;
1940  t.c = tri->GetPoint( 2 )->id;
1941 
1942  m_triPoly->SetTriangle(i, t);
1943  i++;
1944  }
1945 
1946  for( auto p : m_uniquePoints )
1947  delete p;
1948  }
1949 
1950 private:
1951 
1953  {
1954  public:
1955  bool operator()( p2t::Point* a, p2t::Point* b ) const
1956  {
1957  if (a->x < b->x)
1958  return true;
1959 
1960  if( a->x == b->x )
1961  return ( a->y > b->y );
1962 
1963  return false;
1964  }
1965  };
1966 
1967 
1969  {
1970  p2t::Point check( aP.x, aP.y );
1971  auto it = m_uniquePoints.find( &check );
1972 
1973  if( it != m_uniquePoints.end() )
1974  {
1975  return *it;
1976  }
1977  else
1978  {
1979  auto lastId = m_triPoly->GetVertexCount();
1980  auto p = new p2t::Point( aP.x, aP.y, lastId );
1981  m_triPoly->AddVertex( aP );
1982  m_uniquePoints.insert ( p );
1983  return p;
1984  }
1985  }
1986 
1987  typedef std::set<p2t::Point*, comparePoints> P2T_SET;
1988  typedef std::vector<p2t::Point*> P2T_VEC;
1989 
1990  P2T_VEC m_points;
1993  std::unique_ptr<p2t::CDT> m_cdt;
1994 };
1995 
1997 {
1998  Clear();
1999 }
2000 
2001 
2003 {
2004  if( m_vertices )
2005  delete[] m_vertices;
2006 
2007  if( m_triangles )
2008  delete[] m_triangles;
2009 }
2010 
2011 
2013 {
2014  m_vertices = new VECTOR2I[aSize];
2015 }
2016 
2017 
2019 {
2020  m_triangles = new TRI[aSize];
2021  m_triangleCount = aSize;
2022 }
2023 
2024 
2025 static int totalVertexCount( const SHAPE_POLY_SET::POLYGON& aPoly )
2026 {
2027  int cnt = 0;
2028 
2029  for( const auto& outl : aPoly )
2030  {
2031  cnt += outl.PointCount();
2032  }
2033 
2034  return cnt;
2035 }
2036 
2037 
2040 {
2041  if( aPoly.size() == 0 )
2042  return;
2043 
2044  TRIANGULATION_CONTEXT ctx ( &aResult );
2045 
2046  aResult.AllocateVertices( totalVertexCount( aPoly ) );
2047  ctx.AddOutline( aPoly[0], false );
2048  for( unsigned i = 1; i < aPoly.size(); i++ )
2049  {
2050  ctx.AddOutline( aPoly[i], true ); // add holes
2051  }
2052 
2053  ctx.Triangulate();
2054 }
2055 
2056 
2058 {
2059  if( !m_triangulationValid )
2060  return false;
2061 
2062  if( !m_hash.IsValid() )
2063  return false;
2064 
2065  auto hash = checksum();
2066 
2067  return hash == m_hash;
2068 }
2069 
2070 
2072 {
2073  bool recalculate = !m_hash.IsValid();
2074  MD5_HASH hash;
2075 
2076  if( !m_triangulationValid )
2077  recalculate = true;
2078 
2079  if( !recalculate )
2080  {
2081  hash = checksum();
2082 
2083  if( m_hash != hash )
2084  {
2085  m_hash = hash;
2086  recalculate = true;
2087  }
2088  }
2089 
2090  if( !recalculate )
2091  return;
2092 
2093  SHAPE_POLY_SET tmpSet = *this;
2094 
2095  if( !tmpSet.HasHoles() )
2096  tmpSet.Unfracture( PM_FAST );
2097 
2098  m_triangulatedPolys.clear();
2099 
2100  if( tmpSet.HasTouchingHoles() )
2101  {
2102  // temporary workaround for overlapping hole vertices that poly2tri doesn't handle
2103  m_triangulationValid = false;
2104  return;
2105  }
2106 
2107  for( int i = 0; i < tmpSet.OutlineCount(); i++ )
2108  {
2109  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2110  triangulateSingle( tmpSet.Polygon( i ), *m_triangulatedPolys.back() );
2111  }
2112 
2113  m_triangulationValid = true;
2114  m_hash = checksum();
2115 }
2116 
2117 
2119 {
2120  MD5_HASH hash;
2121 
2122  hash.Hash( m_polys.size() );
2123 
2124  for( const auto& outline : m_polys )
2125  {
2126  hash.Hash( outline.size() );
2127 
2128  for( const auto& lc : outline )
2129  {
2130  hash.Hash( lc.PointCount() );
2131 
2132  for( int i = 0; i < lc.PointCount(); i++ )
2133  {
2134  hash.Hash( lc.CPoint( i ).x );
2135  hash.Hash( lc.CPoint( i ).y );
2136  }
2137  }
2138  }
2139 
2140  hash.Finalize();
2141 
2142  return hash;
2143 }
2144 
2145 
2147 {
2148  for( int i = 0; i < OutlineCount(); i++ )
2149  {
2150  if( hasTouchingHoles( CPolygon( i ) ) )
2151  {
2152  return true;
2153  }
2154  }
2155 
2156  return false;
2157 }
2158 
2159 
2160 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
2161 {
2162  std::vector< VECTOR2I > pts;
2163 
2164  for( const auto& lc : aPoly )
2165  {
2166  for( int i = 0; i < lc.PointCount(); i++ )
2167  {
2168  const auto p = lc.CPoint( i );
2169 
2170  if( std::find( pts.begin(), pts.end(), p ) != pts.end() )
2171  {
2172  return true;
2173  }
2174 
2175  pts.push_back( p );
2176  }
2177  }
2178 
2179  return false;
2180 }
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, OR, ...
CITER next(CITER it)
Definition: ptree.cpp:130
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
bool HasHoles() const
Returns true if the polygon set has any holes.
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 matches(int y) const
void fractureSingle(POLYGON &paths)
static int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
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...
int PointCount() const
Function PointCount()
const ClipperLib::Path convertToClipper(const SHAPE_LINE_CHAIN &aPath, bool aRequiredOrientation)
MD5_HASH checksum() const
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:139
double y
Definition: shapes.h:47
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
static const int dist[10][10]
Definition: dist.cpp:57
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Returns total number of vertices stored in the set.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
Struct VERTEX_INDEX.
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
Class SEGMENT_ITERATOR_TEMPLATE.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool IsTriangulationUpToDate() const
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aSegments=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
int OutlineCount() const
Returns the number of outlines in the set
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
double x
Definition: shapes.h:47
FractureEdge(bool connected, SHAPE_LINE_CHAIN *owner, int index)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:589
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
#define abs(a)
Definition: auxiliary.h:84
VERTEX_INDEX GetIndex()
Function GetIndex.
static const int delta[8][2]
Definition: solve.cpp:112
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool IsEndContour() const
Function IsEndContour.
#define SEG_CNT_MAX
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
static int totalVertexCount(const SHAPE_POLY_SET::POLYGON &aPoly)
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...
static list_size_check check
const SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
Definition: cdt.h:47
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
const BOX2I BBox(int aClearance=0) const override
Function BBox()
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:294
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
SHAPE_POLY_SET Fillet(int aRadius, int aSegments)
Function Fillet returns a filleted version of the polygon set.
void Move(const VECTOR2I &aVector) override
void AddOutline(const SHAPE_LINE_CHAIN &outl, bool aIsHole=false)
Class SHAPE_POLY_SET.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
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...
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
Class SHAPE.
Definition: shape.h:58
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:350
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 ...
void triangulateSingle(const POLYGON &aPoly, SHAPE_POLY_SET::TRIANGULATED_POLYGON &aResult)
int NewOutline()
Creates a new empty polygon in the set and returns its index
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
VECTOR2I & vertex(int aCornerId)
bool operator()(p2t::Point *a, p2t::Point *b) const
std::vector< p2t::Point * > P2T_VEC
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon...
Definition: seg.h:36
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
bool IsValid() const
Definition: md5_hash.h:23
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
std::set< p2t::Point *, comparePoints > P2T_SET
convex polygon
Definition: shape.h:48
TRIANGULATION_CONTEXT(TRIANGULATED_POLYGON *aResultPoly)
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
const SHAPE_LINE_CHAIN convertFromClipper(const ClipperLib::Path &aPath)
#define max(a, b)
Definition: auxiliary.h:86
p2t::Point * addPoint(const VECTOR2I &aP)
ITERATOR IterateWithHoles()
Function IterateWithHoles.
Class SHAPE_LINE_CHAIN.
double Area() const
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
Class ITERATOR_TEMPLATE.
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
VECTOR2I A
Definition: seg.h:46
static bool empty(const wxTextEntryBase *aCtrl)
The common library.
bool IsClosed() const
Function IsClosed()
const POLYGON & CPolygon(int aIndex) const
std::unique_ptr< p2t::CDT > m_cdt
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
VECTOR2I & Point(int aIndex)
Function Point()
void Finalize()
Definition: md5_hash.cpp:76
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 Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
POLYGON FilletPolygon(unsigned int aRadius, unsigned int aSegments, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
SHAPE * Clone() const override
Function Clone()
bool IsSelfIntersecting()
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting...
FractureEdge(int y=0)
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
const BOX2I BBox(int aClearance=0) const override
Function BBox()
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...
#define min(a, b)
Definition: auxiliary.h:85
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:47
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes...