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 
400 {
401  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
402  SEGMENT_ITERATOR innerIterator;
403 
404  for( iterator = IterateSegmentsWithHoles( 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, POLYGON_MODE aFastMode )
548 {
549  Simplify( aFastMode );
550  Inflate( aFactor, aCircleSegmentsCount );
551  Fracture( aFastMode );
552 }
553 
554 
555 void SHAPE_POLY_SET::Inflate( int aFactor, int aCircleSegmentsCount )
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  for( const POLYGON& poly : m_polys )
566  {
567  for( size_t i = 0; i < poly.size(); i++ )
568  c.AddPath( poly[i].convertToClipper( i == 0 ), jtRound, etClosedPolygon );
569  }
570 
571  PolyTree solution;
572 
573  // Calculate the arc tolerance (arc error) from the seg count by circle.
574  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
575  // see:
576  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
577 
578  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
579  aCircleSegmentsCount = 6;
580 
581  double coeff;
582 
583  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
584  {
585  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
586 
587  if( aCircleSegmentsCount <= SEG_CNT_MAX )
588  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
589  }
590  else
591  coeff = arc_tolerance_factor[aCircleSegmentsCount];
592 
593  c.ArcTolerance = std::abs( aFactor ) * coeff;
594 
595  c.Execute( solution, aFactor );
596 
597  importTree( &solution );
598 }
599 
600 
601 void SHAPE_POLY_SET::importTree( PolyTree* tree )
602 {
603  m_polys.clear();
604 
605  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
606  {
607  if( !n->IsHole() )
608  {
609  POLYGON paths;
610  paths.reserve( n->Childs.size() + 1 );
611  paths.push_back( n->Contour );
612 
613  for( unsigned int i = 0; i < n->Childs.size(); i++ )
614  paths.push_back( n->Childs[i]->Contour );
615 
616  m_polys.push_back( paths );
617  }
618  }
619 }
620 
621 
623 {
624  FractureEdge( bool connected, SHAPE_LINE_CHAIN* owner, int index ) :
625  m_connected( connected ),
626  m_next( NULL )
627  {
628  m_p1 = owner->CPoint( index );
629  m_p2 = owner->CPoint( index + 1 );
630  }
631 
632  FractureEdge( int y = 0 ) :
633  m_connected( false ),
634  m_next( NULL )
635  {
636  m_p1.x = m_p2.y = y;
637  }
638 
639  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
640  m_connected( connected ),
641  m_p1( p1 ),
642  m_p2( p2 ),
643  m_next( NULL )
644  {
645  }
646 
647  bool matches( int y ) const
648  {
649  int y_min = std::min( m_p1.y, m_p2.y );
650  int y_max = std::max( m_p1.y, m_p2.y );
651 
652  return ( y >= y_min ) && ( y <= y_max );
653  }
654 
658 };
659 
660 
661 typedef std::vector<FractureEdge*> FractureEdgeSet;
662 
663 
664 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
665 {
666  int x = edge->m_p1.x;
667  int y = edge->m_p1.y;
668  int min_dist = std::numeric_limits<int>::max();
669  int x_nearest = 0;
670 
671  FractureEdge* e_nearest = NULL;
672 
673  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
674  {
675  if( !(*i)->matches( y ) )
676  continue;
677 
678  int x_intersect;
679 
680  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
681  x_intersect = std::max( (*i)->m_p1.x, (*i)->m_p2.x );
682  else
683  x_intersect = (*i)->m_p1.x + rescale( (*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y,
684  (*i)->m_p2.y - (*i)->m_p1.y );
685 
686  int dist = ( x - x_intersect );
687 
688  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
689  {
690  min_dist = dist;
691  x_nearest = x_intersect;
692  e_nearest = (*i);
693  }
694  }
695 
696  if( e_nearest && e_nearest->m_connected )
697  {
698  int count = 0;
699 
700  FractureEdge* lead1 =
701  new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
702  FractureEdge* lead2 =
703  new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
704  FractureEdge* split_2 =
705  new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
706 
707  edges.push_back( split_2 );
708  edges.push_back( lead1 );
709  edges.push_back( lead2 );
710 
711  FractureEdge* link = e_nearest->m_next;
712 
713  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
714  e_nearest->m_next = lead1;
715  lead1->m_next = edge;
716 
717  FractureEdge* last;
718 
719  for( last = edge; last->m_next != edge; last = last->m_next )
720  {
721  last->m_connected = true;
722  count++;
723  }
724 
725  last->m_connected = true;
726  last->m_next = lead2;
727  lead2->m_next = split_2;
728  split_2->m_next = link;
729 
730  return count + 1;
731  }
732 
733  return 0;
734 }
735 
736 
738 {
739  FractureEdgeSet edges;
740  FractureEdgeSet border_edges;
741  FractureEdge* root = NULL;
742 
743  bool first = true;
744 
745  if( paths.size() == 1 )
746  return;
747 
748  int num_unconnected = 0;
749 
750  for( SHAPE_LINE_CHAIN& path : paths )
751  {
752  int index = 0;
753 
754  FractureEdge* prev = NULL, * first_edge = NULL;
755 
756  int x_min = std::numeric_limits<int>::max();
757 
758  for( int i = 0; i < path.PointCount(); i++ )
759  {
760  const VECTOR2I& p = path.CPoint( i );
761 
762  if( p.x < x_min )
763  x_min = p.x;
764  }
765 
766  for( int i = 0; i < path.PointCount(); i++ )
767  {
768  FractureEdge* fe = new FractureEdge( first, &path, index++ );
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 == path.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( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
807  {
808  int xt = (*i)->m_p1.x;
809 
810  if( ( xt < x_min ) && !(*i)->m_connected )
811  {
812  x_min = xt;
813  smallestX = *i;
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( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
833  delete *i;
834 
835  paths.push_back( 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 iterator = polySet.IterateSegmentsWithHoles(); iterator; iterator++ )
1216  {
1217  SEG polygonEdge = *iterator;
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 
1398 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1399 {
1400  if( m_polys.size() == 0 ) // empty set?
1401  return false;
1402 
1403  // If there is a polygon specified, check the condition against that polygon
1404  if( aSubpolyIndex >= 0 )
1405  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1406 
1407  // In any other case, check it against all polygons in the set
1408  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1409  {
1410  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1411  return true;
1412  }
1413 
1414  return false;
1415 }
1416 
1417 
1418 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1419 {
1420  VERTEX_INDEX index;
1421 
1422  // Assure the to be removed vertex exists, abort otherwise
1423  if( GetRelativeIndices( aGlobalIndex, &index ) )
1424  RemoveVertex( index );
1425  else
1426  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1427 }
1428 
1429 
1431 {
1432  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1433 }
1434 
1435 
1436 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1437 {
1438  // Check that the point is inside the outline
1439  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1440  {
1441  if( !aIgnoreHoles )
1442  {
1443  // Check that the point is not in any of the holes
1444  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1445  {
1446  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1447 
1448  // If the point is inside a hole (and not on its edge),
1449  // it is outside of the polygon
1450  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1451  return false;
1452  }
1453  }
1454 
1455  return true;
1456  }
1457 
1458  return false;
1459 }
1460 
1461 
1462 bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
1463 {
1464  return aPath.PointInside( aP );
1465 }
1466 
1467 
1468 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1469 {
1470  for( POLYGON& poly : m_polys )
1471  {
1472  for( SHAPE_LINE_CHAIN& path : poly )
1473  {
1474  path.Move( aVector );
1475  }
1476  }
1477 }
1478 
1479 
1480 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1481 {
1482  for( POLYGON& poly : m_polys )
1483  {
1484  for( SHAPE_LINE_CHAIN& path : poly )
1485  {
1486  path.Rotate( aAngle, aCenter );
1487  }
1488  }
1489 }
1490 
1491 
1493 {
1494  int c = 0;
1495 
1496  for( const POLYGON& poly : m_polys )
1497  {
1498  for( const SHAPE_LINE_CHAIN& path : poly )
1499  {
1500  c += path.PointCount();
1501  }
1502  }
1503 
1504  return c;
1505 }
1506 
1507 
1508 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1509 {
1510  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1511 }
1512 
1513 
1515  int aErrorMax,
1516  int aIndex )
1517 {
1518  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aErrorMax );
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
1525  // However, if the segment to test is inside the outline, and does not cross
1526  // any edge, it can be seen outside the polygon.
1527  // Therefore test if a segment end is inside ( testing only one end is enough )
1528  if( containsSingle( aPoint, aPolygonIndex ) )
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( SEG aSegment, int aPolygonIndex, int aSegmentWidth )
1551 {
1552  // We calculate the min dist between the segment and each outline segment
1553  // However, if the segment to test is inside the outline, and does not cross
1554  // any edge, it can be seen outside the polygon.
1555  // Therefore test if a segment end is inside ( testing only one end is enough )
1556  if( containsSingle( aSegment.A, aPolygonIndex ) )
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 
1633 {
1634  SHAPE_POLY_SET chamfered;
1635 
1636  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1637  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1638 
1639  return chamfered;
1640 }
1641 
1642 
1643 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
1644 {
1645  SHAPE_POLY_SET filleted;
1646 
1647  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1648  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, polygonIdx ) );
1649 
1650  return filleted;
1651 }
1652 
1653 
1655  unsigned int aDistance,
1656  int aIndex,
1657  int aErrorMax )
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  // Indices for previous and next vertices.
1685  int prevVertex;
1686  int nextVertex;
1687 
1688  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1689 
1690  // Previous vertex is the last one if the current vertex is the first one
1691  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1692 
1693  // next vertex is the first one if the current vertex is the last one.
1694  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1695 
1696  // Previous vertex computation
1697  double xa = currContour.Point( prevVertex ).x - x1;
1698  double ya = currContour.Point( prevVertex ).y - y1;
1699 
1700  // Next vertex computation
1701  double xb = currContour.Point( nextVertex ).x - x1;
1702  double yb = currContour.Point( nextVertex ).y - y1;
1703 
1704  // Compute the new distances
1705  double lena = hypot( xa, ya );
1706  double lenb = hypot( xb, yb );
1707 
1708  // Make the final computations depending on the mode selected, chamfered or filleted.
1709  if( aMode == CORNER_MODE::CHAMFERED )
1710  {
1711  double distance = aDistance;
1712 
1713  // Chamfer one half of an edge at most
1714  if( 0.5 * lena < distance )
1715  distance = 0.5 * lena;
1716 
1717  if( 0.5 * lenb < distance )
1718  distance = 0.5 * lenb;
1719 
1720  int nx1 = round_nearest( distance * xa / lena );
1721  int ny1 = round_nearest( distance * ya / lena );
1722 
1723  newContour.Append( x1 + nx1, y1 + ny1 );
1724 
1725  int nx2 = round_nearest( distance * xb / lenb );
1726  int ny2 = round_nearest( distance * yb / lenb );
1727 
1728  newContour.Append( x1 + nx2, y1 + ny2 );
1729  }
1730  else // CORNER_MODE = FILLETED
1731  {
1732  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1733 
1734  double radius = aDistance;
1735  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1736 
1737  // Do nothing in case of parallel edges
1738  if( std::isinf( denom ) )
1739  continue;
1740 
1741  // Limit rounding distance to one half of an edge
1742  if( 0.5 * lena * denom < radius )
1743  radius = 0.5 * lena * denom;
1744 
1745  if( 0.5 * lenb * denom < radius )
1746  radius = 0.5 * lenb * denom;
1747 
1748  // Calculate fillet arc absolute center point (xc, yx)
1749  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1750  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1751  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1752  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1753  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1754 
1755  // Calculate arc start and end vectors
1756  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1757  double xs = x1 + k * xa / lena - xc;
1758  double ys = y1 + k * ya / lena - yc;
1759  double xe = x1 + k * xb / lenb - xc;
1760  double ye = y1 + k * yb / lenb - yc;
1761 
1762  // Cosine of arc angle
1763  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1764 
1765  // Make sure the argument is in [-1,1], interval in which the acos function is
1766  // defined
1767  if( argument < -1 )
1768  argument = -1;
1769  else if( argument > 1 )
1770  argument = 1;
1771 
1772  double arcAngle = acos( argument );
1773  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1774  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1775 
1776  double deltaAngle = arcAngle / segments;
1777  double startAngle = atan2( -ys, xs );
1778 
1779  // Flip arc for inner corners
1780  if( xa * yb - ya * xb <= 0 )
1781  deltaAngle *= -1;
1782 
1783  double nx = xc + xs;
1784  double ny = yc + ys;
1785 
1786  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1787 
1788  // Store the previous added corner to make a sanity check
1789  int prevX = round_nearest( nx );
1790  int prevY = round_nearest( ny );
1791 
1792  for( int j = 0; j < segments; j++ )
1793  {
1794  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1795  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1796 
1797  // Sanity check: the rounding can produce repeated corners; do not add them.
1798  if( round_nearest( nx ) != prevX || round_nearest( ny ) != prevY )
1799  {
1800  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1801  prevX = round_nearest( nx );
1802  prevY = round_nearest( ny );
1803  }
1804  }
1805  }
1806  }
1807 
1808  // Close the current contour and add it the new polygon
1809  newContour.SetClosed( true );
1810  newPoly.push_back( newContour );
1811  }
1812 
1813  return newPoly;
1814 }
1815 
1816 
1818 {
1819  static_cast<SHAPE&>(*this) = aOther;
1820  m_polys = aOther.m_polys;
1821 
1822  // reset poly cache:
1823  m_hash = MD5_HASH{};
1824  m_triangulationValid = false;
1825  m_triangulatedPolys.clear();
1826  return *this;
1827 }
1828 
1830 {
1831  if( !m_hash.IsValid() )
1832  return checksum();
1833 
1834  return m_hash;
1835 }
1836 
1837 
1839 {
1840  if( !m_triangulationValid )
1841  return false;
1842 
1843  if( !m_hash.IsValid() )
1844  return false;
1845 
1846  auto hash = checksum();
1847 
1848  return hash == m_hash;
1849 }
1850 
1851 
1853 {
1854  bool recalculate = !m_hash.IsValid();
1855  MD5_HASH hash;
1856 
1857  if( !m_triangulationValid )
1858  recalculate = true;
1859 
1860  if( !recalculate )
1861  {
1862  hash = checksum();
1863 
1864  if( m_hash != hash )
1865  {
1866  m_hash = hash;
1867  recalculate = true;
1868  }
1869  }
1870 
1871  if( !recalculate )
1872  return;
1873 
1874  SHAPE_POLY_SET tmpSet = *this;
1875 
1876  if( tmpSet.HasHoles() )
1877  tmpSet.Fracture( PM_FAST );
1878 
1879  m_triangulatedPolys.clear();
1880  m_triangulationValid = true;
1881 
1882  while( tmpSet.OutlineCount() > 0 )
1883  {
1884  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1885  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1886 
1887  // If the tesselation fails, we re-fracture the polygon, which will
1888  // first simplify the system before fracturing and removing the holes
1889  // This may result in multiple, disjoint polygons.
1890  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
1891  {
1892  tmpSet.Fracture( PM_FAST );
1893  m_triangulationValid = false;
1894  continue;
1895  }
1896 
1897  tmpSet.DeletePolygon( 0 );
1898  m_triangulationValid = true;
1899  }
1900 
1901  if( m_triangulationValid )
1902  m_hash = checksum();
1903 }
1904 
1905 
1907 {
1908  MD5_HASH hash;
1909 
1910  hash.Hash( m_polys.size() );
1911 
1912  for( const auto& outline : m_polys )
1913  {
1914  hash.Hash( outline.size() );
1915 
1916  for( const auto& lc : outline )
1917  {
1918  hash.Hash( lc.PointCount() );
1919 
1920  for( int i = 0; i < lc.PointCount(); i++ )
1921  {
1922  hash.Hash( lc.CPoint( i ).x );
1923  hash.Hash( lc.CPoint( i ).y );
1924  }
1925  }
1926  }
1927 
1928  hash.Finalize();
1929 
1930  return hash;
1931 }
1932 
1933 
1935 {
1936  for( int i = 0; i < OutlineCount(); i++ )
1937  {
1938  if( hasTouchingHoles( CPolygon( i ) ) )
1939  {
1940  return true;
1941  }
1942  }
1943 
1944  return false;
1945 }
1946 
1947 
1948 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
1949 {
1950  std::set< long long > ptHashes;
1951 
1952  for( const auto& lc : aPoly )
1953  {
1954  for( const VECTOR2I& pt : lc.CPoints() )
1955  {
1956  const long long ptHash = (long long) pt.x << 32 | pt.y;
1957 
1958  if( ptHashes.count( ptHash ) > 0 )
1959  {
1960  return true;
1961  }
1962 
1963  ptHashes.insert( ptHash );
1964  }
1965  }
1966 
1967  return false;
1968 }
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
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
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)
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
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...
bool PointOnEdge(const VECTOR2I &aP, int aAccuracy=0) const
Function PointOnEdge()
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
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
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.
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
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
FractureEdge(bool connected, SHAPE_LINE_CHAIN *owner, int index)
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.
static const int delta[8][2]
Definition: solve.cpp:112
bool IsTriangulationUpToDate() const
static int round_nearest(double v)
Definition: math_util.h:56
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
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
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
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 &)
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
Class SHAPE_POLY_SET.
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...
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
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,...
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...
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
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
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.
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)
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
VECTOR2I & Point(int aIndex)
Function Point()
void Finalize()
Definition: md5_hash.cpp:76
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0) const
Function PointInside()
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()
bool IsSelfIntersecting()
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
FractureEdge(int y=0)
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
const 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...
#define min(a, b)
Definition: auxiliary.h:85
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
VECTOR2I B
Definition: seg.h:45
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.