KiCad PCB EDA Suite
shape_poly_set.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2019 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
7  *
8  * Point in polygon algorithm adapted from Clipper Library (C) Angus Johnson,
9  * subject to Clipper library license.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 
30 #include <vector>
31 #include <cstdio>
32 #include <set>
33 #include <list>
34 #include <algorithm>
35 #include <unordered_set>
36 #include <memory>
37 
38 #include <md5_hash.h>
39 #include <map>
40 
42 #include <geometry/shape.h>
46 
47 using namespace ClipperLib;
48 
51 {
52 }
53 
54 
55 SHAPE_POLY_SET::SHAPE_POLY_SET( const SHAPE_POLY_SET& aOther, bool aDeepCopy ) :
56  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
57 {
58  if( aOther.IsTriangulationUpToDate() )
59  {
60  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
61  m_triangulatedPolys.push_back(
62  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
63 
64  m_hash = aOther.GetHash();
65  m_triangulationValid = true;
66  }
67 }
68 
69 
71 {
72 }
73 
74 
76 {
77  return new SHAPE_POLY_SET( *this );
78 }
79 
80 
82  SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
83 {
84  int polygonIdx = 0;
85  unsigned int contourIdx = 0;
86  int vertexIdx = 0;
87 
88  int currentGlobalIdx = 0;
89 
90  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
91  {
92  const POLYGON currentPolygon = CPolygon( polygonIdx );
93 
94  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
95  {
96  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
97  int totalPoints = currentContour.PointCount();
98 
99  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
100  {
101  // Check if the current vertex is the globally indexed as aGlobalIdx
102  if( currentGlobalIdx == aGlobalIdx )
103  {
104  aRelativeIndices->m_polygon = polygonIdx;
105  aRelativeIndices->m_contour = contourIdx;
106  aRelativeIndices->m_vertex = vertexIdx;
107 
108  return true;
109  }
110 
111  // Advance
112  currentGlobalIdx++;
113  }
114  }
115  }
116 
117  return false;
118 }
119 
120 
122  int& aGlobalIdx )
123 {
124  int selectedVertex = aRelativeIndices.m_vertex;
125  unsigned int selectedContour = aRelativeIndices.m_contour;
126  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
127 
128  // Check whether the vertex indices make sense in this poly set
129  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
130  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
131  {
132  POLYGON currentPolygon;
133 
134  aGlobalIdx = 0;
135 
136  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
137  {
138  currentPolygon = Polygon( polygonIdx );
139 
140  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
141  {
142  aGlobalIdx += currentPolygon[contourIdx].PointCount();
143  }
144  }
145 
146  currentPolygon = Polygon( selectedPolygon );
147 
148  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
149  {
150  aGlobalIdx += currentPolygon[contourIdx].PointCount();
151  }
152 
153  aGlobalIdx += selectedVertex;
154 
155  return true;
156  }
157  else
158  {
159  return false;
160  }
161 }
162 
163 
165 {
166  SHAPE_LINE_CHAIN empty_path;
167  POLYGON poly;
168 
169  empty_path.SetClosed( true );
170  poly.push_back( empty_path );
171  m_polys.push_back( poly );
172  return m_polys.size() - 1;
173 }
174 
175 
176 int SHAPE_POLY_SET::NewHole( int aOutline )
177 {
178  SHAPE_LINE_CHAIN empty_path;
179 
180  empty_path.SetClosed( true );
181 
182  // Default outline is the last one
183  if( aOutline < 0 )
184  aOutline += m_polys.size();
185 
186  // Add hole to the selected outline
187  m_polys[aOutline].push_back( empty_path );
188 
189  return m_polys.back().size() - 2;
190 }
191 
192 
193 int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
194 {
195  if( aOutline < 0 )
196  aOutline += m_polys.size();
197 
198  int idx;
199 
200  if( aHole < 0 )
201  idx = 0;
202  else
203  idx = aHole + 1;
204 
205  assert( aOutline < (int) m_polys.size() );
206  assert( idx < (int) m_polys[aOutline].size() );
207 
208  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
209 
210  return m_polys[aOutline][idx].PointCount();
211 }
212 
213 
214 void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex )
215 {
216  VERTEX_INDEX index;
217 
218  if( aGlobalIndex < 0 )
219  aGlobalIndex = 0;
220 
221  if( aGlobalIndex >= TotalVertices() )
222  {
223  Append( aNewVertex );
224  }
225  else
226  {
227  // Assure the position to be inserted exists; throw an exception otherwise
228  if( GetRelativeIndices( aGlobalIndex, &index ) )
229  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
230  else
231  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
232  }
233 }
234 
235 
236 int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
237 {
238  if( m_polys.size() == 0 ) // Empty poly set
239  return 0;
240 
241  if( aOutline < 0 ) // Use last outline
242  aOutline += m_polys.size();
243 
244  int idx;
245 
246  if( aHole < 0 )
247  idx = 0;
248  else
249  idx = aHole + 1;
250 
251  if( aOutline >= (int) m_polys.size() ) // not existing outline
252  return 0;
253 
254  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
255  return 0;
256 
257  return m_polys[aOutline][idx].PointCount();
258 }
259 
260 
261 SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
262 {
263  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
264 
265  SHAPE_POLY_SET newPolySet;
266 
267  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
268  {
269  newPolySet.m_polys.push_back( Polygon( index ) );
270  }
271 
272  return newPolySet;
273 }
274 
275 
276 VECTOR2I& SHAPE_POLY_SET::Vertex( int aIndex, int aOutline, int aHole )
277 {
278  if( aOutline < 0 )
279  aOutline += m_polys.size();
280 
281  int idx;
282 
283  if( aHole < 0 )
284  idx = 0;
285  else
286  idx = aHole + 1;
287 
288  assert( aOutline < (int) m_polys.size() );
289  assert( idx < (int) m_polys[aOutline].size() );
290 
291  return m_polys[aOutline][idx].Point( aIndex );
292 }
293 
294 
295 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
296 {
297  if( aOutline < 0 )
298  aOutline += m_polys.size();
299 
300  int idx;
301 
302  if( aHole < 0 )
303  idx = 0;
304  else
305  idx = aHole + 1;
306 
307  assert( aOutline < (int) m_polys.size() );
308  assert( idx < (int) m_polys[aOutline].size() );
309 
310  return m_polys[aOutline][idx].CPoint( aIndex );
311 }
312 
313 
314 VECTOR2I& SHAPE_POLY_SET::Vertex( int aGlobalIndex )
315 {
317 
318  // Assure the passed index references a legal position; abort otherwise
319  if( !GetRelativeIndices( aGlobalIndex, &index ) )
320  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
321 
322  return m_polys[index.m_polygon][index.m_contour].Point( index.m_vertex );
323 }
324 
325 
326 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
327 {
329 
330  // Assure the passed index references a legal position; abort otherwise
331  if( !GetRelativeIndices( aGlobalIndex, &index ) )
332  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
333 
334  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
335 }
336 
337 
339 {
340  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
341 }
342 
343 
345 {
346  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
347 }
348 
349 
350 bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext )
351 {
353 
354  // If the edge does not exist, throw an exception, it is an illegal access memory error
355  if( !GetRelativeIndices( aGlobalIndex, &index ) )
356  return false;
357 
358  // Calculate the previous and next index of aGlobalIndex, corresponding to
359  // the same contour;
360  VERTEX_INDEX inext = index;
361  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
362 
363  if( index.m_vertex == 0 )
364  {
365  index.m_vertex = lastpoint;
366  inext.m_vertex = 1;
367  }
368  else if( index.m_vertex == lastpoint )
369  {
370  index.m_vertex--;
371  inext.m_vertex = 0;
372  }
373  else
374  {
375  inext.m_vertex++;
376  index.m_vertex--;
377  }
378 
379  if( aPrevious )
380  {
381  int previous;
382  GetGlobalIndex( index, previous );
383  *aPrevious = previous;
384  }
385 
386  if( aNext )
387  {
388  int next;
389  GetGlobalIndex( inext, next );
390  *aNext = next;
391  }
392 
393  return true;
394 }
395 
396 
397 bool SHAPE_POLY_SET::IsPolygonSelfIntersecting( int aPolygonIndex ) const
398 {
399  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
400  CONST_SEGMENT_ITERATOR innerIterator;
401 
402  for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
403  {
404  SEG firstSegment = *iterator;
405 
406  // Iterate through all remaining segments.
407  innerIterator = iterator;
408 
409  // Start in the next segment, we don't want to check collision between a segment and itself
410  for( innerIterator++; innerIterator; innerIterator++ )
411  {
412  SEG secondSegment = *innerIterator;
413 
414  // Check whether the two segments built collide, only when they are not adjacent.
415  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
416  return true;
417  }
418  }
419 
420  return false;
421 }
422 
423 
425 {
426  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
427  {
428  if( IsPolygonSelfIntersecting( polygon ) )
429  return true;
430  }
431 
432  return false;
433 }
434 
435 
437 {
438  assert( aOutline.IsClosed() );
439 
440  POLYGON poly;
441 
442  poly.push_back( aOutline );
443 
444  m_polys.push_back( poly );
445 
446  return m_polys.size() - 1;
447 }
448 
449 
450 int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
451 {
452  assert( m_polys.size() );
453 
454  if( aOutline < 0 )
455  aOutline += m_polys.size();
456 
457  POLYGON& poly = m_polys[aOutline];
458 
459  assert( poly.size() );
460 
461  poly.push_back( aHole );
462 
463  return poly.size() - 1;
464 }
465 
466 
467 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
468  POLYGON_MODE aFastMode )
469 {
470  booleanOp( aType, *this, aOtherShape, aFastMode );
471 }
472 
473 
474 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
475  const SHAPE_POLY_SET& aShape,
476  const SHAPE_POLY_SET& aOtherShape,
477  POLYGON_MODE aFastMode )
478 {
479  Clipper c;
480 
481  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
482 
483  for( auto poly : aShape.m_polys )
484  {
485  for( size_t i = 0 ; i < poly.size(); i++ )
486  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
487  }
488 
489  for( auto poly : aOtherShape.m_polys )
490  {
491  for( size_t i = 0; i < poly.size(); i++ )
492  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
493  }
494 
495  PolyTree solution;
496 
497  c.Execute( aType, solution, pftNonZero, pftNonZero );
498 
499  importTree( &solution );
500 }
501 
502 
504 {
505  booleanOp( ctUnion, b, aFastMode );
506 }
507 
508 
510 {
511  booleanOp( ctDifference, b, aFastMode );
512 }
513 
514 
516 {
517  booleanOp( ctIntersection, b, aFastMode );
518 }
519 
520 
522  const SHAPE_POLY_SET& b,
523  POLYGON_MODE aFastMode )
524 {
525  booleanOp( ctUnion, a, b, aFastMode );
526 }
527 
528 
530  const SHAPE_POLY_SET& b,
531  POLYGON_MODE aFastMode )
532 {
533  booleanOp( ctDifference, a, b, aFastMode );
534 }
535 
536 
538  const SHAPE_POLY_SET& b,
539  POLYGON_MODE aFastMode )
540 {
541  booleanOp( ctIntersection, a, b, aFastMode );
542 }
543 
544 
545 void SHAPE_POLY_SET::InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount,
546  POLYGON_MODE aFastMode )
547 {
548  Simplify( aFastMode );
549  Inflate( aFactor, aCircleSegmentsCount );
550  Fracture( aFastMode );
551 }
552 
553 
554 void SHAPE_POLY_SET::Inflate( int aAmount, int aCircleSegmentsCount,
555  CORNER_STRATEGY aCornerStrategy )
556 {
557  // A static table to avoid repetitive calculations of the coefficient
558  // 1.0 - cos( M_PI / aCircleSegmentsCount )
559  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
560  #define SEG_CNT_MAX 64
561  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
562 
563  ClipperOffset c;
564 
565  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
566  // and are not what you'd think they are.
567  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
568  JoinType joinType = aCornerStrategy == ROUND_ALL_CORNERS ? jtRound : jtMiter;
569  double miterLimit = aCornerStrategy == ALLOW_ACUTE_CORNERS ? 10 : 1.5;
570  JoinType miterFallback = aCornerStrategy == ROUND_ACUTE_CORNERS ? jtRound : jtSquare;
571 
572  for( const POLYGON& poly : m_polys )
573  {
574  for( size_t i = 0; i < poly.size(); i++ )
575  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
576  }
577 
578  PolyTree solution;
579 
580  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
581  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
582  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
583 
584  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
585  aCircleSegmentsCount = 6;
586 
587  double coeff;
588 
589  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
590  {
591  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
592 
593  if( aCircleSegmentsCount <= SEG_CNT_MAX )
594  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
595  }
596  else
597  coeff = arc_tolerance_factor[aCircleSegmentsCount];
598 
599  c.ArcTolerance = std::abs( aAmount ) * coeff;
600  c.MiterLimit = miterLimit;
601  c.MiterFallback = miterFallback;
602  c.Execute( solution, aAmount );
603 
604  importTree( &solution );
605 }
606 
607 
608 void SHAPE_POLY_SET::importTree( PolyTree* tree )
609 {
610  m_polys.clear();
611 
612  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
613  {
614  if( !n->IsHole() )
615  {
616  POLYGON paths;
617  paths.reserve( n->Childs.size() + 1 );
618  paths.push_back( n->Contour );
619 
620  for( unsigned int i = 0; i < n->Childs.size(); i++ )
621  paths.push_back( n->Childs[i]->Contour );
622 
623  m_polys.push_back( paths );
624  }
625  }
626 }
627 
628 
630 {
631  FractureEdge( int y = 0 ) :
632  m_connected( false ),
633  m_next( NULL )
634  {
635  m_p1.x = m_p2.y = y;
636  }
637 
638  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
639  m_connected( connected ),
640  m_p1( p1 ),
641  m_p2( p2 ),
642  m_next( NULL )
643  {
644  }
645 
646  bool matches( int y ) const
647  {
648  return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
649  }
650 
654 };
655 
656 
657 typedef std::vector<FractureEdge*> FractureEdgeSet;
658 
659 
660 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
661 {
662  int x = edge->m_p1.x;
663  int y = edge->m_p1.y;
664  int min_dist = std::numeric_limits<int>::max();
665  int x_nearest = 0;
666 
667  FractureEdge* e_nearest = NULL;
668 
669  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
670  {
671  if( !(*i)->matches( y ) )
672  continue;
673 
674  int x_intersect;
675 
676  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
677  x_intersect = std::max( (*i)->m_p1.x, (*i)->m_p2.x );
678  else
679  x_intersect = (*i)->m_p1.x + rescale( (*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y,
680  (*i)->m_p2.y - (*i)->m_p1.y );
681 
682  int dist = ( x - x_intersect );
683 
684  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
685  {
686  min_dist = dist;
687  x_nearest = x_intersect;
688  e_nearest = (*i);
689  }
690  }
691 
692  if( e_nearest && e_nearest->m_connected )
693  {
694  int count = 0;
695 
696  FractureEdge* lead1 =
697  new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
698  FractureEdge* lead2 =
699  new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
700  FractureEdge* split_2 =
701  new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
702 
703  edges.push_back( split_2 );
704  edges.push_back( lead1 );
705  edges.push_back( lead2 );
706 
707  FractureEdge* link = e_nearest->m_next;
708 
709  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
710  e_nearest->m_next = lead1;
711  lead1->m_next = edge;
712 
713  FractureEdge* last;
714 
715  for( last = edge; last->m_next != edge; last = last->m_next )
716  {
717  last->m_connected = true;
718  count++;
719  }
720 
721  last->m_connected = true;
722  last->m_next = lead2;
723  lead2->m_next = split_2;
724  split_2->m_next = link;
725 
726  return count + 1;
727  }
728 
729  return 0;
730 }
731 
732 
734 {
735  FractureEdgeSet edges;
736  FractureEdgeSet border_edges;
737  FractureEdge* root = NULL;
738 
739  bool first = true;
740 
741  if( paths.size() == 1 )
742  return;
743 
744  int num_unconnected = 0;
745 
746  for( const SHAPE_LINE_CHAIN& path : paths )
747  {
748  const std::vector<VECTOR2I>& points = path.CPoints();
749  int pointCount = points.size();
750 
751  FractureEdge* prev = NULL, * first_edge = NULL;
752 
753  int x_min = std::numeric_limits<int>::max();
754 
755  for( const VECTOR2I& p : points )
756  {
757  if( p.x < x_min )
758  x_min = p.x;
759  }
760 
761  for( int i = 0; i < pointCount; i++ )
762  {
763  // Do not use path.CPoint() here; open-coding it using the local variables "points"
764  // and "pointCount" gives a non-trivial performance boost to zone fill times.
765  FractureEdge* fe = new FractureEdge( first, points[ i ],
766  points[ i+1 == pointCount ? 0 : i+1 ] );
767 
768  if( !root )
769  root = fe;
770 
771  if( !first_edge )
772  first_edge = fe;
773 
774  if( prev )
775  prev->m_next = fe;
776 
777  if( i == pointCount - 1 )
778  fe->m_next = first_edge;
779 
780  prev = fe;
781  edges.push_back( fe );
782 
783  if( !first )
784  {
785  if( fe->m_p1.x == x_min )
786  border_edges.push_back( fe );
787  }
788 
789  if( !fe->m_connected )
790  num_unconnected++;
791  }
792 
793  first = false; // first path is always the outline
794  }
795 
796  // keep connecting holes to the main outline, until there's no holes left...
797  while( num_unconnected > 0 )
798  {
799  int x_min = std::numeric_limits<int>::max();
800 
801  FractureEdge* smallestX = NULL;
802 
803  // find the left-most hole edge and merge with the outline
804  for( FractureEdge* border_edge : border_edges )
805  {
806  int xt = border_edge->m_p1.x;
807 
808  if( ( xt < x_min ) && !border_edge->m_connected )
809  {
810  x_min = xt;
811  smallestX = border_edge;
812  }
813  }
814 
815  num_unconnected -= processEdge( edges, smallestX );
816  }
817 
818  paths.clear();
819  SHAPE_LINE_CHAIN newPath;
820 
821  newPath.SetClosed( true );
822 
823  FractureEdge* e;
824 
825  for( e = root; e->m_next != root; e = e->m_next )
826  newPath.Append( e->m_p1 );
827 
828  newPath.Append( e->m_p1 );
829 
830  for( FractureEdge* edge : edges )
831  delete edge;
832 
833  paths.push_back( std::move( newPath ) );
834 }
835 
836 
838 {
839  Simplify( aFastMode ); // remove overlapping holes/degeneracy
840 
841  for( POLYGON& paths : m_polys )
842  {
843  fractureSingle( paths );
844  }
845 }
846 
847 
849 {
850  assert( aPoly.size() == 1 );
851 
852  struct EDGE
853  {
854  int m_index = 0;
855  SHAPE_LINE_CHAIN* m_poly = nullptr;
856  bool m_duplicate = false;
857 
858  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
859  m_index( aIndex ),
860  m_poly( aPolygon )
861  {}
862 
863  bool compareSegs( const SEG& s1, const SEG& s2 ) const
864  {
865  return (s1.A == s2.B && s1.B == s2.A);
866  }
867 
868  bool operator==( const EDGE& aOther ) const
869  {
870  return compareSegs( m_poly->CSegment( m_index ),
871  aOther.m_poly->CSegment( aOther.m_index ) );
872  }
873 
874  bool operator!=( const EDGE& aOther ) const
875  {
876  return !compareSegs( m_poly->CSegment( m_index ),
877  aOther.m_poly->CSegment( aOther.m_index ) );
878  }
879 
880  struct HASH
881  {
882  std::size_t operator()( const EDGE& aEdge ) const
883  {
884  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
885 
886  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
887  }
888  };
889  };
890 
891  struct EDGE_LIST_ENTRY
892  {
893  int index;
894  EDGE_LIST_ENTRY* next;
895  };
896 
897  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
898 
899  auto lc = aPoly[0];
900  lc.Simplify();
901 
902  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
903 
904  for( int i = 0; i < lc.SegmentCount(); i++ )
905  {
906  edgeList[i].index = i;
907  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
908  }
909 
910  std::unordered_set<EDGE_LIST_ENTRY*> queue;
911 
912  for( int i = 0; i < lc.SegmentCount(); i++ )
913  {
914  EDGE e( &lc, i );
915  uniqueEdges.insert( e );
916  }
917 
918  for( int i = 0; i < lc.SegmentCount(); i++ )
919  {
920  EDGE e( &lc, i );
921  auto it = uniqueEdges.find( e );
922 
923  if( it != uniqueEdges.end() && it->m_index != i )
924  {
925  int e1 = it->m_index;
926  int e2 = i;
927 
928  if( e1 > e2 )
929  std::swap( e1, e2 );
930 
931  int e1_prev = e1 - 1;
932 
933  if( e1_prev < 0 )
934  e1_prev = lc.SegmentCount() - 1;
935 
936  int e2_prev = e2 - 1;
937 
938  if( e2_prev < 0 )
939  e2_prev = lc.SegmentCount() - 1;
940 
941  int e1_next = e1 + 1;
942 
943  if( e1_next == lc.SegmentCount() )
944  e1_next = 0;
945 
946  int e2_next = e2 + 1;
947 
948  if( e2_next == lc.SegmentCount() )
949  e2_next = 0;
950 
951  edgeList[e1_prev].next = &edgeList[ e2_next ];
952  edgeList[e2_prev].next = &edgeList[ e1_next ];
953  edgeList[i].next = nullptr;
954  edgeList[it->m_index].next = nullptr;
955  }
956  }
957 
958  for( int i = 0; i < lc.SegmentCount(); i++ )
959  {
960  if( edgeList[i].next )
961  queue.insert( &edgeList[i] );
962  }
963 
964  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
965 
966  int n = 0;
967  int outline = -1;
968 
969  POLYGON result;
970 
971  while( queue.size() )
972  {
973  auto e_first = (*queue.begin() );
974  auto e = e_first;
975  int cnt = 0;
976 
977  do {
978  edgeBuf[cnt++] = e;
979  e = e->next;
980  } while( e && e != e_first );
981 
982  SHAPE_LINE_CHAIN outl;
983 
984  for( int i = 0; i < cnt; i++ )
985  {
986  auto p = lc.CPoint( edgeBuf[i]->index );
987  outl.Append( p );
988  queue.erase( edgeBuf[i] );
989  }
990 
991  outl.SetClosed( true );
992 
993  bool cw = outl.Area() > 0.0;
994 
995  if( cw )
996  outline = n;
997 
998  result.push_back( outl );
999  n++;
1000  }
1001 
1002  if( outline > 0 )
1003  std::swap( result[0], result[outline] );
1004 
1005  aPoly = result;
1006 }
1007 
1008 
1010 {
1011  // Iterate through all the polygons on the set
1012  for( const POLYGON& paths : m_polys )
1013  {
1014  // If any of them has more than one contour, it is a hole.
1015  if( paths.size() > 1 )
1016  return true;
1017  }
1018 
1019  // Return false if and only if every polygon has just one outline, without holes.
1020  return false;
1021 }
1022 
1023 
1025 {
1026  for( POLYGON& path : m_polys )
1027  {
1028  unfractureSingle( path );
1029  }
1030 
1031  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1032 }
1033 
1034 
1036 {
1038 
1039  booleanOp( ctUnion, empty, aFastMode );
1040 }
1041 
1042 
1044 {
1045  // We are expecting only one main outline, but this main outline can have holes
1046  // if holes: combine holes and remove them from the main outline.
1047  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1048  // calculations, but it is not mandatory. It is used mainly
1049  // because there is usually only very few vertices in area outlines
1050  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1051  SHAPE_POLY_SET holesBuffer;
1052 
1053  // Move holes stored in outline to holesBuffer:
1054  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1055  while( outline.size() > 1 )
1056  {
1057  holesBuffer.AddOutline( outline.back() );
1058  outline.pop_back();
1059  }
1060 
1062 
1063  // If any hole, substract it to main outline
1064  if( holesBuffer.OutlineCount() )
1065  {
1066  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1068  }
1069 
1071 
1072  return OutlineCount();
1073 }
1074 
1075 
1076 const std::string SHAPE_POLY_SET::Format() const
1077 {
1078  std::stringstream ss;
1079 
1080  ss << "polyset " << m_polys.size() << "\n";
1081 
1082  for( unsigned i = 0; i < m_polys.size(); i++ )
1083  {
1084  ss << "poly " << m_polys[i].size() << "\n";
1085 
1086  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1087  {
1088  ss << m_polys[i][j].PointCount() << "\n";
1089 
1090  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1091  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1092  }
1093 
1094  ss << "\n";
1095  }
1096 
1097  return ss.str();
1098 }
1099 
1100 
1101 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1102 {
1103  std::string tmp;
1104 
1105  aStream >> tmp;
1106 
1107  if( tmp != "polyset" )
1108  return false;
1109 
1110  aStream >> tmp;
1111 
1112  int n_polys = atoi( tmp.c_str() );
1113 
1114  if( n_polys < 0 )
1115  return false;
1116 
1117  for( int i = 0; i < n_polys; i++ )
1118  {
1119  POLYGON paths;
1120 
1121  aStream >> tmp;
1122 
1123  if( tmp != "poly" )
1124  return false;
1125 
1126  aStream >> tmp;
1127  int n_outlines = atoi( tmp.c_str() );
1128 
1129  if( n_outlines < 0 )
1130  return false;
1131 
1132  for( int j = 0; j < n_outlines; j++ )
1133  {
1134  SHAPE_LINE_CHAIN outline;
1135 
1136  outline.SetClosed( true );
1137 
1138  aStream >> tmp;
1139  int n_vertices = atoi( tmp.c_str() );
1140 
1141  for( int v = 0; v < n_vertices; v++ )
1142  {
1143  VECTOR2I p;
1144 
1145  aStream >> tmp; p.x = atoi( tmp.c_str() );
1146  aStream >> tmp; p.y = atoi( tmp.c_str() );
1147  outline.Append( p );
1148  }
1149 
1150  paths.push_back( outline );
1151  }
1152 
1153  m_polys.push_back( paths );
1154  }
1155 
1156  return true;
1157 }
1158 
1159 
1160 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1161 {
1162  BOX2I bb;
1163 
1164  for( unsigned i = 0; i < m_polys.size(); i++ )
1165  {
1166  if( i == 0 )
1167  bb = m_polys[i][0].BBox();
1168  else
1169  bb.Merge( m_polys[i][0].BBox() );
1170  }
1171 
1172  bb.Inflate( aClearance );
1173  return bb;
1174 }
1175 
1176 
1177 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1178 {
1179  // Iterate through all the polygons in the set
1180  for( const POLYGON& polygon : m_polys )
1181  {
1182  // Iterate through all the line chains in the polygon
1183  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1184  {
1185  if( lineChain.PointOnEdge( aP ) )
1186  return true;
1187  }
1188  }
1189 
1190  return false;
1191 }
1192 
1193 
1194 bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance ) const
1195 {
1196 
1197  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1198 
1199  // Inflate the polygon if necessary.
1200  if( aClearance > 0 )
1201  {
1202  // fixme: the number of arc segments should not be hardcoded
1203  polySet.Inflate( aClearance, 8 );
1204  }
1205 
1206  // We are going to check to see if the segment crosses an external
1207  // boundary. However, if the full segment is inside the polyset, this
1208  // will not be true. So we first test to see if one of the points is
1209  // inside. If true, then we collide
1210  if( polySet.Contains( aSeg.A ) )
1211  return true;
1212 
1213  for( SEGMENT_ITERATOR it = ( (SHAPE_POLY_SET*) this )->IterateSegmentsWithHoles(); it; it++ )
1214  {
1215  SEG polygonEdge = *it;
1216 
1217  if( polygonEdge.Intersect( aSeg, true ) )
1218  return true;
1219  }
1220 
1221  return false;
1222 }
1223 
1224 
1225 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1226 {
1227  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1228 
1229  // Inflate the polygon if necessary.
1230  if( aClearance > 0 )
1231  {
1232  // fixme: the number of arc segments should not be hardcoded
1233  polySet.Inflate( aClearance, 8 );
1234  }
1235 
1236  // There is a collision if and only if the point is inside of the polygon.
1237  return polySet.Contains( aP );
1238 }
1239 
1240 
1242 {
1243  m_polys.clear();
1244 }
1245 
1246 
1247 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1248 {
1249  // Default polygon is the last one
1250  if( aPolygonIdx < 0 )
1251  aPolygonIdx += m_polys.size();
1252 
1253  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1254 }
1255 
1256 
1258 {
1259  int removed = 0;
1260 
1261  ITERATOR iterator = IterateWithHoles();
1262 
1263  VECTOR2I contourStart = *iterator;
1264  VECTOR2I segmentStart, segmentEnd;
1265 
1266  VERTEX_INDEX indexStart;
1267 
1268  while( iterator )
1269  {
1270  // Obtain first point and its index
1271  segmentStart = *iterator;
1272  indexStart = iterator.GetIndex();
1273 
1274  // Obtain last point
1275  if( iterator.IsEndContour() )
1276  {
1277  segmentEnd = contourStart;
1278 
1279  // Advance
1280  iterator++;
1281 
1282  if( iterator )
1283  contourStart = *iterator;
1284  }
1285  else
1286  {
1287  // Advance
1288  iterator++;
1289 
1290  if( iterator )
1291  segmentEnd = *iterator;
1292  }
1293 
1294  // Remove segment start if both points are equal
1295  if( segmentStart == segmentEnd )
1296  {
1297  RemoveVertex( indexStart );
1298  removed++;
1299 
1300  // Advance the iterator one position, as there is one vertex less.
1301  if( iterator )
1302  iterator++;
1303  }
1304  }
1305 
1306  return removed;
1307 }
1308 
1309 
1311 {
1312  m_polys.erase( m_polys.begin() + aIdx );
1313 }
1314 
1315 
1317 {
1318  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1319 }
1320 
1321 
1322 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1323 {
1324  Append( aP.x, aP.y, aOutline, aHole );
1325 }
1326 
1327 
1329  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1330 {
1331  // Shows whether there was a collision
1332  bool collision = false;
1333 
1334  // Difference vector between each vertex and aPoint.
1335  VECTOR2D delta;
1336  double distance, clearance;
1337 
1338  // Convert clearance to double for precission when comparing distances
1339  clearance = aClearance;
1340 
1341  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1342  {
1343  // Get the difference vector between current vertex and aPoint
1344  delta = *iterator - aPoint;
1345 
1346  // Compute distance
1347  distance = delta.EuclideanNorm();
1348 
1349  // Check for collisions
1350  if( distance <= clearance )
1351  {
1352  collision = true;
1353 
1354  // Update aClearance to look for closer vertices
1355  clearance = distance;
1356 
1357  // Store the indices that identify the vertex
1358  aClosestVertex = iterator.GetIndex();
1359  }
1360  }
1361 
1362  return collision;
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  SEGMENT_ITERATOR iterator;
1373 
1374  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1375  {
1376  SEG currentSegment = *iterator;
1377  int distance = currentSegment.Distance( aPoint );
1378 
1379  // Check for collisions
1380  if( distance <= aClearance )
1381  {
1382  collision = true;
1383 
1384  // Update aClearance to look for closer edges
1385  aClearance = distance;
1386 
1387  // Store the indices that identify the vertex
1388  aClosestVertex = iterator.GetIndex();
1389  }
1390  }
1391 
1392  return collision;
1393 }
1394 
1395 
1397 {
1398  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1399  {
1400  Outline( polygonIdx ).GenerateBBoxCache();
1401 
1402  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1403  Hole( polygonIdx, holeIdx ).GenerateBBoxCache();
1404  }
1405 }
1406 
1407 
1408 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1409  bool aUseBBoxCaches ) const
1410 {
1411  if( m_polys.empty() )
1412  return false;
1413 
1414  // If there is a polygon specified, check the condition against that polygon
1415  if( aSubpolyIndex >= 0 )
1416  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1417 
1418  // In any other case, check it against all polygons in the set
1419  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1420  {
1421  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1422  return true;
1423  }
1424 
1425  return false;
1426 }
1427 
1428 
1429 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1430 {
1431  VERTEX_INDEX index;
1432 
1433  // Assure the to be removed vertex exists, abort otherwise
1434  if( GetRelativeIndices( aGlobalIndex, &index ) )
1435  RemoveVertex( index );
1436  else
1437  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1438 }
1439 
1440 
1442 {
1443  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1444 }
1445 
1446 
1447 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1448  bool aUseBBoxCaches ) const
1449 {
1450  // Check that the point is inside the outline
1451  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1452  {
1453  // Check that the point is not in any of the holes
1454  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1455  {
1456  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1457 
1458  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1459  // here as it's meaning would be inverted.
1460  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1461  return false;
1462  }
1463 
1464  return true;
1465  }
1466 
1467  return false;
1468 }
1469 
1470 
1471 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1472 {
1473  for( POLYGON& poly : m_polys )
1474  {
1475  for( SHAPE_LINE_CHAIN& path : poly )
1476  path.Move( aVector );
1477  }
1478 }
1479 
1480 
1481 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1482 {
1483  for( POLYGON& poly : m_polys )
1484  {
1485  for( SHAPE_LINE_CHAIN& path : poly )
1486  path.Rotate( aAngle, aCenter );
1487  }
1488 }
1489 
1490 
1492 {
1493  int c = 0;
1494 
1495  for( const POLYGON& poly : m_polys )
1496  {
1497  for( const SHAPE_LINE_CHAIN& path : poly )
1498  c += path.PointCount();
1499  }
1500 
1501  return c;
1502 }
1503 
1504 
1505 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex,
1506  std::set<VECTOR2I>* aPreserveCorners )
1507 {
1508  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0, aPreserveCorners );
1509 }
1510 
1511 
1512 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
1513  int aIndex,
1514  std::set<VECTOR2I>* aPreserveCorners )
1515 {
1516  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax, aPreserveCorners );
1517 }
1518 
1519 
1520 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1521 {
1522  // We calculate the min dist between the segment and each outline segment. However, if the
1523  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1524  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1525  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1526  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1527  return 0;
1528 
1529  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1530 
1531  SEG polygonEdge = *iterator;
1532  int minDistance = polygonEdge.Distance( aPoint );
1533 
1534  for( iterator++; iterator && minDistance > 0; iterator++ )
1535  {
1536  polygonEdge = *iterator;
1537 
1538  int currentDistance = polygonEdge.Distance( aPoint );
1539 
1540  if( currentDistance < minDistance )
1541  minDistance = currentDistance;
1542  }
1543 
1544  return minDistance;
1545 }
1546 
1547 
1548 int SHAPE_POLY_SET::DistanceToPolygon( const SEG& aSegment, int aPolygonIndex, int aSegmentWidth )
1549 {
1550  // We calculate the min dist between the segment and each outline segment. However, if the
1551  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1552  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1553  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1554  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1555  return 0;
1556 
1557  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1558 
1559  SEG polygonEdge = *iterator;
1560  int minDistance = polygonEdge.Distance( aSegment );
1561 
1562  for( iterator++; iterator && minDistance > 0; iterator++ )
1563  {
1564  polygonEdge = *iterator;
1565 
1566  int currentDistance = polygonEdge.Distance( aSegment );
1567 
1568  if( currentDistance < minDistance )
1569  minDistance = currentDistance;
1570  }
1571 
1572  // Take into account the width of the segment
1573  if( aSegmentWidth > 0 )
1574  minDistance -= aSegmentWidth / 2;
1575 
1576  // Return the maximum of minDistance and zero
1577  return minDistance < 0 ? 0 : minDistance;
1578 }
1579 
1580 
1582 {
1583  int currentDistance;
1584  int minDistance = DistanceToPolygon( aPoint, 0 );
1585 
1586  // Iterate through all the polygons and get the minimum distance.
1587  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1588  {
1589  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1590 
1591  if( currentDistance < minDistance )
1592  minDistance = currentDistance;
1593  }
1594 
1595  return minDistance;
1596 }
1597 
1598 
1599 int SHAPE_POLY_SET::Distance( const SEG& aSegment, int aSegmentWidth )
1600 {
1601  int currentDistance;
1602  int minDistance = DistanceToPolygon( aSegment, 0, aSegmentWidth );
1603 
1604  // Iterate through all the polygons and get the minimum distance.
1605  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1606  {
1607  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1608 
1609  if( currentDistance < minDistance )
1610  minDistance = currentDistance;
1611  }
1612 
1613  return minDistance;
1614 }
1615 
1616 
1617 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1618 {
1619  VERTEX_INDEX index;
1620 
1621  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1622  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1623  return false;
1624 
1625  // The contour is a hole if its index is greater than zero
1626  return index.m_contour > 0;
1627 }
1628 
1629 
1630 SHAPE_POLY_SET SHAPE_POLY_SET::Chamfer( int aDistance, std::set<VECTOR2I>* aPreserveCorners )
1631 {
1632  SHAPE_POLY_SET chamfered;
1633 
1634  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1635  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx, aPreserveCorners ) );
1636 
1637  return chamfered;
1638 }
1639 
1640 
1641 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax,
1642  std::set<VECTOR2I>* aPreserveCorners )
1643 {
1644  SHAPE_POLY_SET filleted;
1645 
1646  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1647  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx, aPreserveCorners ) );
1648 
1649  return filleted;
1650 }
1651 
1652 
1654  unsigned int aDistance, int aIndex, int aErrorMax,
1655  std::set<VECTOR2I>* aPreserveCorners )
1656 {
1657  // Null segments create serious issues in calculations. Remove them:
1659 
1660  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1661  SHAPE_POLY_SET::POLYGON newPoly;
1662 
1663  // If the chamfering distance is zero, then the polygon remain intact.
1664  if( aDistance == 0 )
1665  {
1666  return currentPoly;
1667  }
1668 
1669  // Iterate through all the contours (outline and holes) of the polygon.
1670  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1671  {
1672  // Generate a new contour in the new polygon
1673  SHAPE_LINE_CHAIN newContour;
1674 
1675  // Iterate through the vertices of the contour
1676  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1677  {
1678  // Current vertex
1679  int x1 = currContour.Point( currVertex ).x;
1680  int y1 = currContour.Point( currVertex ).y;
1681 
1682  if( aPreserveCorners && aPreserveCorners->count( VECTOR2I( x1, y1 ) ) > 0 )
1683  {
1684  newContour.Append( x1, y1 );
1685  continue;
1686  }
1687 
1688  // Indices for previous and next vertices.
1689  int prevVertex;
1690  int nextVertex;
1691 
1692  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1693 
1694  // Previous vertex is the last one if the current vertex is the first one
1695  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1696 
1697  // next vertex is the first one if the current vertex is the last one.
1698  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1699 
1700  // Previous vertex computation
1701  double xa = currContour.Point( prevVertex ).x - x1;
1702  double ya = currContour.Point( prevVertex ).y - y1;
1703 
1704  // Next vertex computation
1705  double xb = currContour.Point( nextVertex ).x - x1;
1706  double yb = currContour.Point( nextVertex ).y - y1;
1707 
1708  // Compute the new distances
1709  double lena = hypot( xa, ya );
1710  double lenb = hypot( xb, yb );
1711 
1712  // Make the final computations depending on the mode selected, chamfered or filleted.
1713  if( aMode == CORNER_MODE::CHAMFERED )
1714  {
1715  double distance = aDistance;
1716 
1717  // Chamfer one half of an edge at most
1718  if( 0.5 * lena < distance )
1719  distance = 0.5 * lena;
1720 
1721  if( 0.5 * lenb < distance )
1722  distance = 0.5 * lenb;
1723 
1724  int nx1 = round_nearest( distance * xa / lena );
1725  int ny1 = round_nearest( distance * ya / lena );
1726 
1727  newContour.Append( x1 + nx1, y1 + ny1 );
1728 
1729  int nx2 = round_nearest( distance * xb / lenb );
1730  int ny2 = round_nearest( distance * yb / lenb );
1731 
1732  newContour.Append( x1 + nx2, y1 + ny2 );
1733  }
1734  else // CORNER_MODE = FILLETED
1735  {
1736  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1737 
1738  double radius = aDistance;
1739  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1740 
1741  // Do nothing in case of parallel edges
1742  if( std::isinf( denom ) )
1743  continue;
1744 
1745  // Limit rounding distance to one half of an edge
1746  if( 0.5 * lena * denom < radius )
1747  radius = 0.5 * lena * denom;
1748 
1749  if( 0.5 * lenb * denom < radius )
1750  radius = 0.5 * lenb * denom;
1751 
1752  // Calculate fillet arc absolute center point (xc, yx)
1753  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1754  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1755  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1756  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1757  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1758 
1759  // Calculate arc start and end vectors
1760  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1761  double xs = x1 + k * xa / lena - xc;
1762  double ys = y1 + k * ya / lena - yc;
1763  double xe = x1 + k * xb / lenb - xc;
1764  double ye = y1 + k * yb / lenb - yc;
1765 
1766  // Cosine of arc angle
1767  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1768 
1769  // Make sure the argument is in [-1,1], interval in which the acos function is
1770  // defined
1771  if( argument < -1 )
1772  argument = -1;
1773  else if( argument > 1 )
1774  argument = 1;
1775 
1776  double arcAngle = acos( argument );
1777  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1778  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1779 
1780  double deltaAngle = arcAngle / segments;
1781  double startAngle = atan2( -ys, xs );
1782 
1783  // Flip arc for inner corners
1784  if( xa * yb - ya * xb <= 0 )
1785  deltaAngle *= -1;
1786 
1787  double nx = xc + xs;
1788  double ny = yc + ys;
1789 
1790  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1791 
1792  // Store the previous added corner to make a sanity check
1793  int prevX = round_nearest( nx );
1794  int prevY = round_nearest( ny );
1795 
1796  for( int j = 0; j < segments; j++ )
1797  {
1798  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1799  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1800 
1801  // Sanity check: the rounding can produce repeated corners; do not add them.
1802  if( round_nearest( nx ) != prevX || round_nearest( ny ) != prevY )
1803  {
1804  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1805  prevX = round_nearest( nx );
1806  prevY = round_nearest( ny );
1807  }
1808  }
1809  }
1810  }
1811 
1812  // Close the current contour and add it the new polygon
1813  newContour.SetClosed( true );
1814  newPoly.push_back( newContour );
1815  }
1816 
1817  return newPoly;
1818 }
1819 
1820 
1822 {
1823  static_cast<SHAPE&>(*this) = aOther;
1824  m_polys = aOther.m_polys;
1825 
1826  // reset poly cache:
1827  m_hash = MD5_HASH{};
1828  m_triangulationValid = false;
1829  m_triangulatedPolys.clear();
1830  return *this;
1831 }
1832 
1834 {
1835  if( !m_hash.IsValid() )
1836  return checksum();
1837 
1838  return m_hash;
1839 }
1840 
1841 
1843 {
1844  if( !m_triangulationValid )
1845  return false;
1846 
1847  if( !m_hash.IsValid() )
1848  return false;
1849 
1850  auto hash = checksum();
1851 
1852  return hash == m_hash;
1853 }
1854 
1855 
1857 {
1858  bool recalculate = !m_hash.IsValid();
1859  MD5_HASH hash;
1860 
1861  if( !m_triangulationValid )
1862  recalculate = true;
1863 
1864  if( !recalculate )
1865  {
1866  hash = checksum();
1867 
1868  if( m_hash != hash )
1869  {
1870  m_hash = hash;
1871  recalculate = true;
1872  }
1873  }
1874 
1875  if( !recalculate )
1876  return;
1877 
1878  SHAPE_POLY_SET tmpSet = *this;
1879 
1880  if( tmpSet.HasHoles() )
1881  tmpSet.Fracture( PM_FAST );
1882 
1883  m_triangulatedPolys.clear();
1884  m_triangulationValid = true;
1885 
1886  while( tmpSet.OutlineCount() > 0 )
1887  {
1888  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1889  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1890 
1891  // If the tesselation fails, we re-fracture the polygon, which will
1892  // first simplify the system before fracturing and removing the holes
1893  // This may result in multiple, disjoint polygons.
1894  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
1895  {
1896  tmpSet.Fracture( PM_FAST );
1897  m_triangulationValid = false;
1898  continue;
1899  }
1900 
1901  tmpSet.DeletePolygon( 0 );
1902  m_triangulationValid = true;
1903  }
1904 
1905  if( m_triangulationValid )
1906  m_hash = checksum();
1907 }
1908 
1909 
1911 {
1912  MD5_HASH hash;
1913 
1914  hash.Hash( m_polys.size() );
1915 
1916  for( const auto& outline : m_polys )
1917  {
1918  hash.Hash( outline.size() );
1919 
1920  for( const auto& lc : outline )
1921  {
1922  hash.Hash( lc.PointCount() );
1923 
1924  for( int i = 0; i < lc.PointCount(); i++ )
1925  {
1926  hash.Hash( lc.CPoint( i ).x );
1927  hash.Hash( lc.CPoint( i ).y );
1928  }
1929  }
1930  }
1931 
1932  hash.Finalize();
1933 
1934  return hash;
1935 }
1936 
1937 
1939 {
1940  for( int i = 0; i < OutlineCount(); i++ )
1941  {
1942  if( hasTouchingHoles( CPolygon( i ) ) )
1943  {
1944  return true;
1945  }
1946  }
1947 
1948  return false;
1949 }
1950 
1951 
1952 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
1953 {
1954  std::set< long long > ptHashes;
1955 
1956  for( const auto& lc : aPoly )
1957  {
1958  for( const VECTOR2I& pt : lc.CPoints() )
1959  {
1960  const long long ptHash = (long long) pt.x << 32 | pt.y;
1961 
1962  if( ptHashes.count( ptHash ) > 0 )
1963  {
1964  return true;
1965  }
1966 
1967  ptHashes.insert( ptHash );
1968  }
1969  }
1970 
1971  return false;
1972 }
int TotalVertices() const
Returns total number of vertices stored in the set.
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND,...
CITER next(CITER it)
Definition: ptree.cpp:130
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
const POLYGON & CPolygon(int aIndex) const
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:199
int OutlineCount() const
Returns the number of outlines in the set
bool IsEndContour() const
Function IsEndContour.
void fractureSingle(POLYGON &paths)
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
static const int dist[10][10]
Definition: ar_matrix.cpp:320
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:132
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Returns true if the polygon set has any holes.
Struct VERTEX_INDEX.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
MD5_HASH checksum() const
Class SEGMENT_ITERATOR_TEMPLATE.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Returns true if a given subpolygon contains the point aP.
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
int PointCount() const
Function PointCount()
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
#define abs(a)
Definition: auxiliary.h:84
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
VERTEX_INDEX GetIndex()
Function GetIndex.
bool IsTriangulationUpToDate() const
static int round_nearest(double v)
Definition: math_util.h:56
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
#define SEG_CNT_MAX
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
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
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...
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
void SetClosed(bool aClosed)
Function SetClosed()
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
Class SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles(int aOutline) const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
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:384
const std::string Format() const override
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
int NewOutline()
Creates a new empty polygon in the set and returns its index
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
void BuildBBoxCaches()
Constructs BBoxCaches for Contains(), below.
double Area() const
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon,...
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the polygon set.
Definition: seg.h: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
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex, std::set< VECTOR2I > *aPreserveCorners)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:300
simple polygon
Definition: shape.h:48
const SEG CSegment(int aIndex) const
Function CSegment()
bool matches(int y) const
#define max(a, b)
Definition: auxiliary.h:86
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
ITERATOR IterateWithHoles()
Function IterateWithHoles.
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Class SHAPE_LINE_CHAIN.
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Fillet returns a filleted version of the aIndex-th polygon.
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
Class ITERATOR_TEMPLATE.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
size_t i
Definition: json11.cpp:597
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
VECTOR2I A
Definition: seg.h:44
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
SHAPE_POLY_SET Chamfer(int aDistance, std::set< VECTOR2I > *aPreserveCorners=nullptr)
Function Chamfer returns a chamfered version of the polygon set.
static bool empty(const wxTextEntryBase *aCtrl)
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Performs outline inflation/deflation, using round corners.
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:167
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
VECTOR2I & Point(int aIndex)
Function Point()
void Finalize()
Definition: md5_hash.cpp:76
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:292
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
bool IsClosed() const
Function IsClosed()
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool IsValid() const
Definition: md5_hash.h:24
SHAPE * Clone() const override
Function Clone()
FractureEdge(int y=0)
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
const BOX2I BBox(int aClearance=0) const override
Function BBox()
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
VERTEX_INDEX GetIndex()
Function GetIndex.
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
bool IsSelfIntersecting() const
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
VECTOR2I B
Definition: seg.h:45
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.