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