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