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 SEG& aSeg, int aClearance ) const
1233 {
1234 
1235  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1236 
1237  // Inflate the polygon if necessary.
1238  if( aClearance > 0 )
1239  {
1240  // fixme: the number of arc segments should not be hardcoded
1241  polySet.Inflate( aClearance, 8 );
1242  }
1243 
1244  // We are going to check to see if the segment crosses an external
1245  // boundary. However, if the full segment is inside the polyset, this
1246  // will not be true. So we first test to see if one of the points is
1247  // inside. If true, then we collide
1248  if( polySet.Contains( aSeg.A ) )
1249  return true;
1250 
1251  for( SEGMENT_ITERATOR iterator = polySet.IterateSegmentsWithHoles(); iterator; iterator++ )
1252  {
1253  SEG polygonEdge = *iterator;
1254 
1255  if( polygonEdge.Intersect( aSeg, true ) )
1256  return true;
1257  }
1258 
1259  return false;
1260 }
1261 
1262 
1263 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1264 {
1265  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1266 
1267  // Inflate the polygon if necessary.
1268  if( aClearance > 0 )
1269  {
1270  // fixme: the number of arc segments should not be hardcoded
1271  polySet.Inflate( aClearance, 8 );
1272  }
1273 
1274  // There is a collision if and only if the point is inside of the polygon.
1275  return polySet.Contains( aP );
1276 }
1277 
1278 
1280 {
1281  m_polys.clear();
1282 }
1283 
1284 
1285 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1286 {
1287  // Default polygon is the last one
1288  if( aPolygonIdx < 0 )
1289  aPolygonIdx += m_polys.size();
1290 
1291  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1292 }
1293 
1294 
1296 {
1297  int removed = 0;
1298 
1299  ITERATOR iterator = IterateWithHoles();
1300 
1301  VECTOR2I contourStart = *iterator;
1302  VECTOR2I segmentStart, segmentEnd;
1303 
1304  VERTEX_INDEX indexStart;
1305 
1306  while( iterator )
1307  {
1308  // Obtain first point and its index
1309  segmentStart = *iterator;
1310  indexStart = iterator.GetIndex();
1311 
1312  // Obtain last point
1313  if( iterator.IsEndContour() )
1314  {
1315  segmentEnd = contourStart;
1316 
1317  // Advance
1318  iterator++;
1319 
1320  if( iterator )
1321  contourStart = *iterator;
1322  }
1323  else
1324  {
1325  // Advance
1326  iterator++;
1327 
1328  if( iterator )
1329  segmentEnd = *iterator;
1330  }
1331 
1332  // Remove segment start if both points are equal
1333  if( segmentStart == segmentEnd )
1334  {
1335  RemoveVertex( indexStart );
1336  removed++;
1337 
1338  // Advance the iterator one position, as there is one vertex less.
1339  if( iterator )
1340  iterator++;
1341  }
1342  }
1343 
1344  return removed;
1345 }
1346 
1347 
1349 {
1350  m_polys.erase( m_polys.begin() + aIdx );
1351 }
1352 
1353 
1355 {
1356  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1357 }
1358 
1359 
1360 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1361 {
1362  Append( aP.x, aP.y, aOutline, aHole );
1363 }
1364 
1365 
1367  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1368 {
1369  // Shows whether there was a collision
1370  bool collision = false;
1371 
1372  // Difference vector between each vertex and aPoint.
1373  VECTOR2D delta;
1374  double distance, clearance;
1375 
1376  // Convert clearance to double for precission when comparing distances
1377  clearance = aClearance;
1378 
1379  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1380  {
1381  // Get the difference vector between current vertex and aPoint
1382  delta = *iterator - aPoint;
1383 
1384  // Compute distance
1385  distance = delta.EuclideanNorm();
1386 
1387  // Check for collisions
1388  if( distance <= clearance )
1389  {
1390  collision = true;
1391 
1392  // Update aClearance to look for closer vertices
1393  clearance = distance;
1394 
1395  // Store the indices that identify the vertex
1396  aClosestVertex = iterator.GetIndex();
1397  }
1398  }
1399 
1400  return collision;
1401 }
1402 
1403 
1405  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1406 {
1407  // Shows whether there was a collision
1408  bool collision = false;
1409 
1410  SEGMENT_ITERATOR iterator;
1411 
1412  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1413  {
1414  SEG currentSegment = *iterator;
1415  int distance = currentSegment.Distance( aPoint );
1416 
1417  // Check for collisions
1418  if( distance <= aClearance )
1419  {
1420  collision = true;
1421 
1422  // Update aClearance to look for closer edges
1423  aClearance = distance;
1424 
1425  // Store the indices that identify the vertex
1426  aClosestVertex = iterator.GetIndex();
1427  }
1428  }
1429 
1430  return collision;
1431 }
1432 
1433 
1434 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1435 {
1436  if( m_polys.size() == 0 ) // empty set?
1437  return false;
1438 
1439  // If there is a polygon specified, check the condition against that polygon
1440  if( aSubpolyIndex >= 0 )
1441  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1442 
1443  // In any other case, check it against all polygons in the set
1444  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1445  {
1446  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1447  return true;
1448  }
1449 
1450  return false;
1451 }
1452 
1453 
1454 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1455 {
1456  VERTEX_INDEX index;
1457 
1458  // Assure the to be removed vertex exists, abort otherwise
1459  if( GetRelativeIndices( aGlobalIndex, &index ) )
1460  RemoveVertex( index );
1461  else
1462  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1463 }
1464 
1465 
1467 {
1468  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1469 }
1470 
1471 
1472 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1473 {
1474  // Check that the point is inside the outline
1475  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1476  {
1477  if( !aIgnoreHoles )
1478  {
1479  // Check that the point is not in any of the holes
1480  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1481  {
1482  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1483 
1484  // If the point is inside a hole (and not on its edge),
1485  // it is outside of the polygon
1486  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1487  return false;
1488  }
1489  }
1490 
1491  return true;
1492  }
1493 
1494  return false;
1495 }
1496 
1497 
1498 bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
1499 {
1500  return aPath.PointInside( aP );
1501 }
1502 
1503 
1504 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1505 {
1506  for( POLYGON& poly : m_polys )
1507  {
1508  for( SHAPE_LINE_CHAIN& path : poly )
1509  {
1510  path.Move( aVector );
1511  }
1512  }
1513 }
1514 
1515 
1516 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1517 {
1518  for( POLYGON& poly : m_polys )
1519  {
1520  for( SHAPE_LINE_CHAIN& path : poly )
1521  {
1522  path.Rotate( aAngle, aCenter );
1523  }
1524  }
1525 }
1526 
1527 
1529 {
1530  int c = 0;
1531 
1532  for( const POLYGON& poly : m_polys )
1533  {
1534  for( const SHAPE_LINE_CHAIN& path : poly )
1535  {
1536  c += path.PointCount();
1537  }
1538  }
1539 
1540  return c;
1541 }
1542 
1543 
1544 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1545 {
1546  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1547 }
1548 
1549 
1551  int aErrorMax,
1552  int aIndex )
1553 {
1554  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aErrorMax );
1555 }
1556 
1557 
1558 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1559 {
1560  // We calculate the min dist between the segment and each outline segment
1561  // However, if the segment to test is inside the outline, and does not cross
1562  // any edge, it can be seen outside the polygon.
1563  // Therefore test if a segment end is inside ( testing only one end is enough )
1564  if( containsSingle( aPoint, aPolygonIndex ) )
1565  return 0;
1566 
1567  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1568 
1569  SEG polygonEdge = *iterator;
1570  int minDistance = polygonEdge.Distance( aPoint );
1571 
1572  for( iterator++; iterator && minDistance > 0; iterator++ )
1573  {
1574  polygonEdge = *iterator;
1575 
1576  int currentDistance = polygonEdge.Distance( aPoint );
1577 
1578  if( currentDistance < minDistance )
1579  minDistance = currentDistance;
1580  }
1581 
1582  return minDistance;
1583 }
1584 
1585 
1586 int SHAPE_POLY_SET::DistanceToPolygon( SEG aSegment, int aPolygonIndex, int aSegmentWidth )
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( aSegment.A, aPolygonIndex ) )
1593  return 0;
1594 
1595  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1596 
1597  SEG polygonEdge = *iterator;
1598  int minDistance = polygonEdge.Distance( aSegment );
1599 
1600  for( iterator++; iterator && minDistance > 0; iterator++ )
1601  {
1602  polygonEdge = *iterator;
1603 
1604  int currentDistance = polygonEdge.Distance( aSegment );
1605 
1606  if( currentDistance < minDistance )
1607  minDistance = currentDistance;
1608  }
1609 
1610  // Take into account the width of the segment
1611  if( aSegmentWidth > 0 )
1612  minDistance -= aSegmentWidth / 2;
1613 
1614  // Return the maximum of minDistance and zero
1615  return minDistance < 0 ? 0 : minDistance;
1616 }
1617 
1618 
1620 {
1621  int currentDistance;
1622  int minDistance = DistanceToPolygon( aPoint, 0 );
1623 
1624  // Iterate through all the polygons and get the minimum distance.
1625  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1626  {
1627  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1628 
1629  if( currentDistance < minDistance )
1630  minDistance = currentDistance;
1631  }
1632 
1633  return minDistance;
1634 }
1635 
1636 
1637 int SHAPE_POLY_SET::Distance( const SEG& aSegment, int aSegmentWidth )
1638 {
1639  int currentDistance;
1640  int minDistance = DistanceToPolygon( aSegment, 0 );
1641 
1642  // Iterate through all the polygons and get the minimum distance.
1643  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1644  {
1645  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1646 
1647  if( currentDistance < minDistance )
1648  minDistance = currentDistance;
1649  }
1650 
1651  return minDistance;
1652 }
1653 
1654 
1655 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1656 {
1657  VERTEX_INDEX index;
1658 
1659  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1660  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1661  return false;
1662 
1663  // The contour is a hole if its index is greater than zero
1664  return index.m_contour > 0;
1665 }
1666 
1667 
1669 {
1670  SHAPE_POLY_SET chamfered;
1671 
1672  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1673  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1674 
1675  return chamfered;
1676 }
1677 
1678 
1679 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
1680 {
1681  SHAPE_POLY_SET filleted;
1682 
1683  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1684  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, polygonIdx ) );
1685 
1686  return filleted;
1687 }
1688 
1689 
1691  unsigned int aDistance,
1692  int aIndex,
1693  int aErrorMax )
1694 {
1695  // Null segments create serious issues in calculations. Remove them:
1697 
1698  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1699  SHAPE_POLY_SET::POLYGON newPoly;
1700 
1701  // If the chamfering distance is zero, then the polygon remain intact.
1702  if( aDistance == 0 )
1703  {
1704  return currentPoly;
1705  }
1706 
1707  // Iterate through all the contours (outline and holes) of the polygon.
1708  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1709  {
1710  // Generate a new contour in the new polygon
1711  SHAPE_LINE_CHAIN newContour;
1712 
1713  // Iterate through the vertices of the contour
1714  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1715  {
1716  // Current vertex
1717  int x1 = currContour.Point( currVertex ).x;
1718  int y1 = currContour.Point( currVertex ).y;
1719 
1720  // Indices for previous and next vertices.
1721  int prevVertex;
1722  int nextVertex;
1723 
1724  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1725 
1726  // Previous vertex is the last one if the current vertex is the first one
1727  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1728 
1729  // next vertex is the first one if the current vertex is the last one.
1730  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1731 
1732  // Previous vertex computation
1733  double xa = currContour.Point( prevVertex ).x - x1;
1734  double ya = currContour.Point( prevVertex ).y - y1;
1735 
1736  // Next vertex computation
1737  double xb = currContour.Point( nextVertex ).x - x1;
1738  double yb = currContour.Point( nextVertex ).y - y1;
1739 
1740  // Compute the new distances
1741  double lena = hypot( xa, ya );
1742  double lenb = hypot( xb, yb );
1743 
1744  // Make the final computations depending on the mode selected, chamfered or filleted.
1745  if( aMode == CORNER_MODE::CHAMFERED )
1746  {
1747  double distance = aDistance;
1748 
1749  // Chamfer one half of an edge at most
1750  if( 0.5 * lena < distance )
1751  distance = 0.5 * lena;
1752 
1753  if( 0.5 * lenb < distance )
1754  distance = 0.5 * lenb;
1755 
1756  int nx1 = KiROUND( distance * xa / lena );
1757  int ny1 = KiROUND( distance * ya / lena );
1758 
1759  newContour.Append( x1 + nx1, y1 + ny1 );
1760 
1761  int nx2 = KiROUND( distance * xb / lenb );
1762  int ny2 = KiROUND( distance * yb / lenb );
1763 
1764  newContour.Append( x1 + nx2, y1 + ny2 );
1765  }
1766  else // CORNER_MODE = FILLETED
1767  {
1768  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1769 
1770  double radius = aDistance;
1771  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1772 
1773  // Do nothing in case of parallel edges
1774  if( std::isinf( denom ) )
1775  continue;
1776 
1777  // Limit rounding distance to one half of an edge
1778  if( 0.5 * lena * denom < radius )
1779  radius = 0.5 * lena * denom;
1780 
1781  if( 0.5 * lenb * denom < radius )
1782  radius = 0.5 * lenb * denom;
1783 
1784  // Calculate fillet arc absolute center point (xc, yx)
1785  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1786  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1787  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1788  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1789  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1790 
1791  // Calculate arc start and end vectors
1792  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1793  double xs = x1 + k * xa / lena - xc;
1794  double ys = y1 + k * ya / lena - yc;
1795  double xe = x1 + k * xb / lenb - xc;
1796  double ye = y1 + k * yb / lenb - yc;
1797 
1798  // Cosine of arc angle
1799  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1800 
1801  // Make sure the argument is in [-1,1], interval in which the acos function is
1802  // defined
1803  if( argument < -1 )
1804  argument = -1;
1805  else if( argument > 1 )
1806  argument = 1;
1807 
1808  double arcAngle = acos( argument );
1809  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1810  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1811 
1812  double deltaAngle = arcAngle / segments;
1813  double startAngle = atan2( -ys, xs );
1814 
1815  // Flip arc for inner corners
1816  if( xa * yb - ya * xb <= 0 )
1817  deltaAngle *= -1;
1818 
1819  double nx = xc + xs;
1820  double ny = yc + ys;
1821 
1822  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1823 
1824  // Store the previous added corner to make a sanity check
1825  int prevX = KiROUND( nx );
1826  int prevY = KiROUND( ny );
1827 
1828  for( int j = 0; j < segments; j++ )
1829  {
1830  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1831  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1832 
1833  // Sanity check: the rounding can produce repeated corners; do not add them.
1834  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1835  {
1836  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1837  prevX = KiROUND( nx );
1838  prevY = KiROUND( ny );
1839  }
1840  }
1841  }
1842  }
1843 
1844  // Close the current contour and add it the new polygon
1845  newContour.SetClosed( true );
1846  newPoly.push_back( newContour );
1847  }
1848 
1849  return newPoly;
1850 }
1851 
1852 
1854 {
1855  static_cast<SHAPE&>(*this) = aOther;
1856  m_polys = aOther.m_polys;
1857 
1858  // reset poly cache:
1859  m_hash = MD5_HASH{};
1860  m_triangulationValid = false;
1861  m_triangulatedPolys.clear();
1862  return *this;
1863 }
1864 
1865 
1866 
1867 
1869 {
1870 public:
1871 
1873  m_triPoly( aResultPoly )
1874  {
1875  }
1876 
1877  void AddOutline( const SHAPE_LINE_CHAIN& outl, bool aIsHole = false )
1878  {
1879  m_points.reserve( outl.PointCount() );
1880  m_points.clear();
1881 
1882  for( int i = 0; i < outl.PointCount(); i++ )
1883  {
1884  m_points.push_back( addPoint( outl.CPoint( i ) ) );
1885  }
1886 
1887  if ( aIsHole )
1888  m_cdt->AddHole( m_points );
1889  else
1890  {
1891  m_cdt.reset( new p2t::CDT( m_points ) );
1892  }
1893  }
1894 
1896  {
1897  m_cdt->Triangulate();
1898 
1899  m_triPoly->AllocateTriangles( m_cdt->GetTriangles().size() );
1900 
1901  int i = 0;
1902 
1903  for( auto tri : m_cdt->GetTriangles() )
1904  {
1906 
1907  t.a = tri->GetPoint( 0 )->id;
1908  t.b = tri->GetPoint( 1 )->id;
1909  t.c = tri->GetPoint( 2 )->id;
1910 
1911  m_triPoly->SetTriangle(i, t);
1912  i++;
1913  }
1914 
1915  for( auto p : m_uniquePoints )
1916  delete p;
1917  }
1918 
1919 private:
1920 
1922  {
1923  public:
1924  bool operator()( p2t::Point* a, p2t::Point* b ) const
1925  {
1926  if (a->x < b->x)
1927  return true;
1928 
1929  if( a->x == b->x )
1930  return ( a->y > b->y );
1931 
1932  return false;
1933  }
1934  };
1935 
1936 
1938  {
1939  p2t::Point check( aP.x, aP.y );
1940  auto it = m_uniquePoints.find( &check );
1941 
1942  if( it != m_uniquePoints.end() )
1943  {
1944  return *it;
1945  }
1946  else
1947  {
1948  auto lastId = m_triPoly->GetVertexCount();
1949  auto p = new p2t::Point( aP.x, aP.y, lastId );
1950  m_triPoly->AddVertex( aP );
1951  m_uniquePoints.insert ( p );
1952  return p;
1953  }
1954  }
1955 
1956  typedef std::set<p2t::Point*, comparePoints> P2T_SET;
1957  typedef std::vector<p2t::Point*> P2T_VEC;
1958 
1959  P2T_VEC m_points;
1962  std::unique_ptr<p2t::CDT> m_cdt;
1963 };
1964 
1966 {
1967  Clear();
1968 }
1969 
1970 
1972 {
1973  if( m_vertices )
1974  delete[] m_vertices;
1975 
1976  if( m_triangles )
1977  delete[] m_triangles;
1978 }
1979 
1980 
1982 {
1983  m_vertices = new VECTOR2I[aSize];
1984 }
1985 
1986 
1988 {
1989  m_triangles = new TRI[aSize];
1990  m_triangleCount = aSize;
1991 }
1992 
1993 
1994 static int totalVertexCount( const SHAPE_POLY_SET::POLYGON& aPoly )
1995 {
1996  int cnt = 0;
1997 
1998  for( const auto& outl : aPoly )
1999  {
2000  cnt += outl.PointCount();
2001  }
2002 
2003  return cnt;
2004 }
2005 
2006 
2009 {
2010  if( aPoly.size() == 0 )
2011  return;
2012 
2013  TRIANGULATION_CONTEXT ctx ( &aResult );
2014 
2015  aResult.AllocateVertices( totalVertexCount( aPoly ) );
2016  ctx.AddOutline( aPoly[0], false );
2017  for( unsigned i = 1; i < aPoly.size(); i++ )
2018  {
2019  ctx.AddOutline( aPoly[i], true ); // add holes
2020  }
2021 
2022  ctx.Triangulate();
2023 }
2024 
2025 
2027 {
2028  if( !m_hash.IsValid() )
2029  return checksum();
2030 
2031  return m_hash;
2032 }
2033 
2034 
2036 {
2037  if( !m_triangulationValid )
2038  return false;
2039 
2040  if( !m_hash.IsValid() )
2041  return false;
2042 
2043  auto hash = checksum();
2044 
2045  return hash == m_hash;
2046 }
2047 
2048 
2050 {
2051  bool recalculate = !m_hash.IsValid();
2052  MD5_HASH hash;
2053 
2054  if( !m_triangulationValid )
2055  recalculate = true;
2056 
2057  if( !recalculate )
2058  {
2059  hash = checksum();
2060 
2061  if( m_hash != hash )
2062  {
2063  m_hash = hash;
2064  recalculate = true;
2065  }
2066  }
2067 
2068  if( !recalculate )
2069  return;
2070 
2071  SHAPE_POLY_SET tmpSet = *this;
2072 
2073  if( !tmpSet.HasHoles() )
2074  tmpSet.Unfracture( PM_FAST );
2075 
2076  m_triangulatedPolys.clear();
2077 
2078  if( tmpSet.HasTouchingHoles() )
2079  {
2080  // temporary workaround for overlapping hole vertices that poly2tri doesn't handle
2081  m_triangulationValid = false;
2082  return;
2083  }
2084 
2085  for( int i = 0; i < tmpSet.OutlineCount(); i++ )
2086  {
2087  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2088  triangulateSingle( tmpSet.Polygon( i ), *m_triangulatedPolys.back() );
2089  }
2090 
2091  m_triangulationValid = true;
2092  m_hash = checksum();
2093 }
2094 
2095 
2097 {
2098  MD5_HASH hash;
2099 
2100  hash.Hash( m_polys.size() );
2101 
2102  for( const auto& outline : m_polys )
2103  {
2104  hash.Hash( outline.size() );
2105 
2106  for( const auto& lc : outline )
2107  {
2108  hash.Hash( lc.PointCount() );
2109 
2110  for( int i = 0; i < lc.PointCount(); i++ )
2111  {
2112  hash.Hash( lc.CPoint( i ).x );
2113  hash.Hash( lc.CPoint( i ).y );
2114  }
2115  }
2116  }
2117 
2118  hash.Finalize();
2119 
2120  return hash;
2121 }
2122 
2123 
2125 {
2126  for( int i = 0; i < OutlineCount(); i++ )
2127  {
2128  if( hasTouchingHoles( CPolygon( i ) ) )
2129  {
2130  return true;
2131  }
2132  }
2133 
2134  return false;
2135 }
2136 
2137 
2138 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
2139 {
2140  std::vector< VECTOR2I > pts;
2141 
2142  for( const auto& lc : aPoly )
2143  {
2144  for( int i = 0; i < lc.PointCount(); i++ )
2145  {
2146  const auto p = lc.CPoint( i );
2147 
2148  if( std::find( pts.begin(), pts.end(), p ) != pts.end() )
2149  {
2150  return true;
2151  }
2152 
2153  pts.push_back( p );
2154  }
2155  }
2156 
2157  return false;
2158 }
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()
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
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)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: common.h:106
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
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
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
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 &)
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
simple 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...