KiCad PCB EDA Suite
shape_poly_set.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2015-2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
7  *
8  * Point in polygon algorithm adapted from Clipper Library (C) Angus Johnson,
9  * subject to Clipper library license.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 
30 #include <vector>
31 #include <cstdio>
32 #include <set>
33 #include <list>
34 #include <algorithm>
35 #include <unordered_set>
36 #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::Inflate( int aFactor, int aCircleSegmentsCount )
548 {
549  // A static table to avoid repetitive calculations of the coefficient
550  // 1.0 - cos( M_PI/aCircleSegmentsCount)
551  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
552  #define SEG_CNT_MAX 64
553  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
554 
555  ClipperOffset c;
556 
557  for( const POLYGON& poly : m_polys )
558  {
559  for( size_t i = 0; i < poly.size(); i++ )
560  c.AddPath( poly[i].convertToClipper( i == 0 ), jtRound, etClosedPolygon );
561  }
562 
563  PolyTree solution;
564 
565  // Calculate the arc tolerance (arc error) from the seg count by circle.
566  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
567  // see:
568  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
569 
570  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
571  aCircleSegmentsCount = 6;
572 
573  double coeff;
574 
575  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
576  {
577  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
578 
579  if( aCircleSegmentsCount <= SEG_CNT_MAX )
580  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
581  }
582  else
583  coeff = arc_tolerance_factor[aCircleSegmentsCount];
584 
585  c.ArcTolerance = std::abs( aFactor ) * coeff;
586 
587  c.Execute( solution, aFactor );
588 
589  importTree( &solution );
590 }
591 
592 
593 void SHAPE_POLY_SET::importTree( PolyTree* tree )
594 {
595  m_polys.clear();
596 
597  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
598  {
599  if( !n->IsHole() )
600  {
601  POLYGON paths;
602  paths.reserve( n->Childs.size() + 1 );
603  paths.push_back( n->Contour );
604 
605  for( unsigned int i = 0; i < n->Childs.size(); i++ )
606  paths.push_back( n->Childs[i]->Contour );
607 
608  m_polys.push_back( paths );
609  }
610  }
611 }
612 
613 
615 {
616  FractureEdge( bool connected, SHAPE_LINE_CHAIN* owner, int index ) :
617  m_connected( connected ),
618  m_next( NULL )
619  {
620  m_p1 = owner->CPoint( index );
621  m_p2 = owner->CPoint( index + 1 );
622  }
623 
624  FractureEdge( int y = 0 ) :
625  m_connected( false ),
626  m_next( NULL )
627  {
628  m_p1.x = m_p2.y = y;
629  }
630 
631  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
632  m_connected( connected ),
633  m_p1( p1 ),
634  m_p2( p2 ),
635  m_next( NULL )
636  {
637  }
638 
639  bool matches( int y ) const
640  {
641  int y_min = std::min( m_p1.y, m_p2.y );
642  int y_max = std::max( m_p1.y, m_p2.y );
643 
644  return ( y >= y_min ) && ( y <= y_max );
645  }
646 
648  VECTOR2I m_p1, m_p2;
650 };
651 
652 
653 typedef std::vector<FractureEdge*> FractureEdgeSet;
654 
655 
656 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
657 {
658  int x = edge->m_p1.x;
659  int y = edge->m_p1.y;
660  int min_dist = std::numeric_limits<int>::max();
661  int x_nearest = 0;
662 
663  FractureEdge* e_nearest = NULL;
664 
665  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
666  {
667  if( !(*i)->matches( y ) )
668  continue;
669 
670  int x_intersect;
671 
672  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
673  x_intersect = std::max( (*i)->m_p1.x, (*i)->m_p2.x );
674  else
675  x_intersect = (*i)->m_p1.x + rescale( (*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y,
676  (*i)->m_p2.y - (*i)->m_p1.y );
677 
678  int dist = ( x - x_intersect );
679 
680  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
681  {
682  min_dist = dist;
683  x_nearest = x_intersect;
684  e_nearest = (*i);
685  }
686  }
687 
688  if( e_nearest && e_nearest->m_connected )
689  {
690  int count = 0;
691 
692  FractureEdge* lead1 =
693  new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
694  FractureEdge* lead2 =
695  new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
696  FractureEdge* split_2 =
697  new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
698 
699  edges.push_back( split_2 );
700  edges.push_back( lead1 );
701  edges.push_back( lead2 );
702 
703  FractureEdge* link = e_nearest->m_next;
704 
705  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
706  e_nearest->m_next = lead1;
707  lead1->m_next = edge;
708 
709  FractureEdge* last;
710 
711  for( last = edge; last->m_next != edge; last = last->m_next )
712  {
713  last->m_connected = true;
714  count++;
715  }
716 
717  last->m_connected = true;
718  last->m_next = lead2;
719  lead2->m_next = split_2;
720  split_2->m_next = link;
721 
722  return count + 1;
723  }
724 
725  return 0;
726 }
727 
728 
730 {
731  FractureEdgeSet edges;
732  FractureEdgeSet border_edges;
733  FractureEdge* root = NULL;
734 
735  bool first = true;
736 
737  if( paths.size() == 1 )
738  return;
739 
740  int num_unconnected = 0;
741 
742  for( SHAPE_LINE_CHAIN& path : paths )
743  {
744  int index = 0;
745 
746  FractureEdge* prev = NULL, * first_edge = NULL;
747 
748  int x_min = std::numeric_limits<int>::max();
749 
750  for( int i = 0; i < path.PointCount(); i++ )
751  {
752  const VECTOR2I& p = path.CPoint( i );
753 
754  if( p.x < x_min )
755  x_min = p.x;
756  }
757 
758  for( int i = 0; i < path.PointCount(); i++ )
759  {
760  FractureEdge* fe = new FractureEdge( first, &path, index++ );
761 
762  if( !root )
763  root = fe;
764 
765  if( !first_edge )
766  first_edge = fe;
767 
768  if( prev )
769  prev->m_next = fe;
770 
771  if( i == path.PointCount() - 1 )
772  fe->m_next = first_edge;
773 
774  prev = fe;
775  edges.push_back( fe );
776 
777  if( !first )
778  {
779  if( fe->m_p1.x == x_min )
780  border_edges.push_back( fe );
781  }
782 
783  if( !fe->m_connected )
784  num_unconnected++;
785  }
786 
787  first = false; // first path is always the outline
788  }
789 
790  // keep connecting holes to the main outline, until there's no holes left...
791  while( num_unconnected > 0 )
792  {
793  int x_min = std::numeric_limits<int>::max();
794 
795  FractureEdge* smallestX = NULL;
796 
797  // find the left-most hole edge and merge with the outline
798  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
799  {
800  int xt = (*i)->m_p1.x;
801 
802  if( ( xt < x_min ) && !(*i)->m_connected )
803  {
804  x_min = xt;
805  smallestX = *i;
806  }
807  }
808 
809  num_unconnected -= processEdge( edges, smallestX );
810  }
811 
812  paths.clear();
813  SHAPE_LINE_CHAIN newPath;
814 
815  newPath.SetClosed( true );
816 
817  FractureEdge* e;
818 
819  for( e = root; e->m_next != root; e = e->m_next )
820  newPath.Append( e->m_p1 );
821 
822  newPath.Append( e->m_p1 );
823 
824  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
825  delete *i;
826 
827  paths.push_back( newPath );
828 }
829 
830 
832 {
833  Simplify( aFastMode ); // remove overlapping holes/degeneracy
834 
835  for( POLYGON& paths : m_polys )
836  {
837  fractureSingle( paths );
838  }
839 }
840 
841 
843 {
844  assert( aPoly.size() == 1 );
845 
846  struct EDGE
847  {
848  int m_index = 0;
849  SHAPE_LINE_CHAIN* m_poly = nullptr;
850  bool m_duplicate = false;
851 
852  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
853  m_index( aIndex ),
854  m_poly( aPolygon )
855  {}
856 
857  bool compareSegs( const SEG& s1, const SEG& s2 ) const
858  {
859  return (s1.A == s2.B && s1.B == s2.A);
860  }
861 
862  bool operator==( const EDGE& aOther ) const
863  {
864  return compareSegs( m_poly->CSegment( m_index ),
865  aOther.m_poly->CSegment( aOther.m_index ) );
866  }
867 
868  bool operator!=( const EDGE& aOther ) const
869  {
870  return !compareSegs( m_poly->CSegment( m_index ),
871  aOther.m_poly->CSegment( aOther.m_index ) );
872  }
873 
874  struct HASH
875  {
876  std::size_t operator()( const EDGE& aEdge ) const
877  {
878  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
879 
880  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
881  }
882  };
883  };
884 
885  struct EDGE_LIST_ENTRY
886  {
887  int index;
888  EDGE_LIST_ENTRY* next;
889  };
890 
891  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
892 
893  auto lc = aPoly[0];
894  lc.Simplify();
895 
896  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
897 
898  for( int i = 0; i < lc.SegmentCount(); i++ )
899  {
900  edgeList[i].index = i;
901  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
902  }
903 
904  std::unordered_set<EDGE_LIST_ENTRY*> queue;
905 
906  for( int i = 0; i < lc.SegmentCount(); i++ )
907  {
908  EDGE e( &lc, i );
909  uniqueEdges.insert( e );
910  }
911 
912  for( int i = 0; i < lc.SegmentCount(); i++ )
913  {
914  EDGE e( &lc, i );
915  auto it = uniqueEdges.find( e );
916 
917  if( it != uniqueEdges.end() && it->m_index != i )
918  {
919  int e1 = it->m_index;
920  int e2 = i;
921 
922  if( e1 > e2 )
923  std::swap( e1, e2 );
924 
925  int e1_prev = e1 - 1;
926 
927  if( e1_prev < 0 )
928  e1_prev = lc.SegmentCount() - 1;
929 
930  int e2_prev = e2 - 1;
931 
932  if( e2_prev < 0 )
933  e2_prev = lc.SegmentCount() - 1;
934 
935  int e1_next = e1 + 1;
936 
937  if( e1_next == lc.SegmentCount() )
938  e1_next = 0;
939 
940  int e2_next = e2 + 1;
941 
942  if( e2_next == lc.SegmentCount() )
943  e2_next = 0;
944 
945  edgeList[e1_prev].next = &edgeList[ e2_next ];
946  edgeList[e2_prev].next = &edgeList[ e1_next ];
947  edgeList[i].next = nullptr;
948  edgeList[it->m_index].next = nullptr;
949  }
950  }
951 
952  for( int i = 0; i < lc.SegmentCount(); i++ )
953  {
954  if( edgeList[i].next )
955  queue.insert( &edgeList[i] );
956  }
957 
958  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
959 
960  int n = 0;
961  int outline = -1;
962 
963  POLYGON result;
964 
965  while( queue.size() )
966  {
967  auto e_first = (*queue.begin() );
968  auto e = e_first;
969  int cnt = 0;
970 
971  do {
972  edgeBuf[cnt++] = e;
973  e = e->next;
974  } while( e && e != e_first );
975 
976  SHAPE_LINE_CHAIN outl;
977 
978  for( int i = 0; i < cnt; i++ )
979  {
980  auto p = lc.CPoint( edgeBuf[i]->index );
981  outl.Append( p );
982  queue.erase( edgeBuf[i] );
983  }
984 
985  outl.SetClosed( true );
986 
987  bool cw = outl.Area() > 0.0;
988 
989  if( cw )
990  outline = n;
991 
992  result.push_back( outl );
993  n++;
994  }
995 
996  if( outline > 0 )
997  std::swap( result[0], result[outline] );
998 
999  aPoly = result;
1000 }
1001 
1002 
1004 {
1005  // Iterate through all the polygons on the set
1006  for( const POLYGON& paths : m_polys )
1007  {
1008  // If any of them has more than one contour, it is a hole.
1009  if( paths.size() > 1 )
1010  return true;
1011  }
1012 
1013  // Return false if and only if every polygon has just one outline, without holes.
1014  return false;
1015 }
1016 
1017 
1019 {
1020  for( POLYGON& path : m_polys )
1021  {
1022  unfractureSingle( path );
1023  }
1024 
1025  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1026 }
1027 
1028 
1030 {
1032 
1033  booleanOp( ctUnion, empty, aFastMode );
1034 }
1035 
1036 
1038 {
1039  // We are expecting only one main outline, but this main outline can have holes
1040  // if holes: combine holes and remove them from the main outline.
1041  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1042  // calculations, but it is not mandatory. It is used mainly
1043  // because there is usually only very few vertices in area outlines
1044  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1045  SHAPE_POLY_SET holesBuffer;
1046 
1047  // Move holes stored in outline to holesBuffer:
1048  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1049  while( outline.size() > 1 )
1050  {
1051  holesBuffer.AddOutline( outline.back() );
1052  outline.pop_back();
1053  }
1054 
1056 
1057  // If any hole, substract it to main outline
1058  if( holesBuffer.OutlineCount() )
1059  {
1060  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1062  }
1063 
1065 
1066  return OutlineCount();
1067 }
1068 
1069 
1070 const std::string SHAPE_POLY_SET::Format() const
1071 {
1072  std::stringstream ss;
1073 
1074  ss << "polyset " << m_polys.size() << "\n";
1075 
1076  for( unsigned i = 0; i < m_polys.size(); i++ )
1077  {
1078  ss << "poly " << m_polys[i].size() << "\n";
1079 
1080  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1081  {
1082  ss << m_polys[i][j].PointCount() << "\n";
1083 
1084  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
1085  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
1086  }
1087 
1088  ss << "\n";
1089  }
1090 
1091  return ss.str();
1092 }
1093 
1094 
1095 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1096 {
1097  std::string tmp;
1098 
1099  aStream >> tmp;
1100 
1101  if( tmp != "polyset" )
1102  return false;
1103 
1104  aStream >> tmp;
1105 
1106  int n_polys = atoi( tmp.c_str() );
1107 
1108  if( n_polys < 0 )
1109  return false;
1110 
1111  for( int i = 0; i < n_polys; i++ )
1112  {
1113  POLYGON paths;
1114 
1115  aStream >> tmp;
1116 
1117  if( tmp != "poly" )
1118  return false;
1119 
1120  aStream >> tmp;
1121  int n_outlines = atoi( tmp.c_str() );
1122 
1123  if( n_outlines < 0 )
1124  return false;
1125 
1126  for( int j = 0; j < n_outlines; j++ )
1127  {
1128  SHAPE_LINE_CHAIN outline;
1129 
1130  outline.SetClosed( true );
1131 
1132  aStream >> tmp;
1133  int n_vertices = atoi( tmp.c_str() );
1134 
1135  for( int v = 0; v < n_vertices; v++ )
1136  {
1137  VECTOR2I p;
1138 
1139  aStream >> tmp; p.x = atoi( tmp.c_str() );
1140  aStream >> tmp; p.y = atoi( tmp.c_str() );
1141  outline.Append( p );
1142  }
1143 
1144  paths.push_back( outline );
1145  }
1146 
1147  m_polys.push_back( paths );
1148  }
1149 
1150  return true;
1151 }
1152 
1153 
1154 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1155 {
1156  BOX2I bb;
1157 
1158  for( unsigned i = 0; i < m_polys.size(); i++ )
1159  {
1160  if( i == 0 )
1161  bb = m_polys[i][0].BBox();
1162  else
1163  bb.Merge( m_polys[i][0].BBox() );
1164  }
1165 
1166  bb.Inflate( aClearance );
1167  return bb;
1168 }
1169 
1170 
1171 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1172 {
1173  // Iterate through all the polygons in the set
1174  for( const POLYGON& polygon : m_polys )
1175  {
1176  // Iterate through all the line chains in the polygon
1177  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1178  {
1179  if( lineChain.PointOnEdge( aP ) )
1180  return true;
1181  }
1182  }
1183 
1184  return false;
1185 }
1186 
1187 
1188 bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance ) const
1189 {
1190 
1191  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1192 
1193  // Inflate the polygon if necessary.
1194  if( aClearance > 0 )
1195  {
1196  // fixme: the number of arc segments should not be hardcoded
1197  polySet.Inflate( aClearance, 8 );
1198  }
1199 
1200  // We are going to check to see if the segment crosses an external
1201  // boundary. However, if the full segment is inside the polyset, this
1202  // will not be true. So we first test to see if one of the points is
1203  // inside. If true, then we collide
1204  if( polySet.Contains( aSeg.A ) )
1205  return true;
1206 
1207  for( SEGMENT_ITERATOR iterator = polySet.IterateSegmentsWithHoles(); iterator; iterator++ )
1208  {
1209  SEG polygonEdge = *iterator;
1210 
1211  if( polygonEdge.Intersect( aSeg, true ) )
1212  return true;
1213  }
1214 
1215  return false;
1216 }
1217 
1218 
1219 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1220 {
1221  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1222 
1223  // Inflate the polygon if necessary.
1224  if( aClearance > 0 )
1225  {
1226  // fixme: the number of arc segments should not be hardcoded
1227  polySet.Inflate( aClearance, 8 );
1228  }
1229 
1230  // There is a collision if and only if the point is inside of the polygon.
1231  return polySet.Contains( aP );
1232 }
1233 
1234 
1236 {
1237  m_polys.clear();
1238 }
1239 
1240 
1241 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1242 {
1243  // Default polygon is the last one
1244  if( aPolygonIdx < 0 )
1245  aPolygonIdx += m_polys.size();
1246 
1247  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1248 }
1249 
1250 
1252 {
1253  int removed = 0;
1254 
1255  ITERATOR iterator = IterateWithHoles();
1256 
1257  VECTOR2I contourStart = *iterator;
1258  VECTOR2I segmentStart, segmentEnd;
1259 
1260  VERTEX_INDEX indexStart;
1261 
1262  while( iterator )
1263  {
1264  // Obtain first point and its index
1265  segmentStart = *iterator;
1266  indexStart = iterator.GetIndex();
1267 
1268  // Obtain last point
1269  if( iterator.IsEndContour() )
1270  {
1271  segmentEnd = contourStart;
1272 
1273  // Advance
1274  iterator++;
1275 
1276  if( iterator )
1277  contourStart = *iterator;
1278  }
1279  else
1280  {
1281  // Advance
1282  iterator++;
1283 
1284  if( iterator )
1285  segmentEnd = *iterator;
1286  }
1287 
1288  // Remove segment start if both points are equal
1289  if( segmentStart == segmentEnd )
1290  {
1291  RemoveVertex( indexStart );
1292  removed++;
1293 
1294  // Advance the iterator one position, as there is one vertex less.
1295  if( iterator )
1296  iterator++;
1297  }
1298  }
1299 
1300  return removed;
1301 }
1302 
1303 
1305 {
1306  m_polys.erase( m_polys.begin() + aIdx );
1307 }
1308 
1309 
1311 {
1312  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1313 }
1314 
1315 
1316 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1317 {
1318  Append( aP.x, aP.y, aOutline, aHole );
1319 }
1320 
1321 
1323  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1324 {
1325  // Shows whether there was a collision
1326  bool collision = false;
1327 
1328  // Difference vector between each vertex and aPoint.
1329  VECTOR2D delta;
1330  double distance, clearance;
1331 
1332  // Convert clearance to double for precission when comparing distances
1333  clearance = aClearance;
1334 
1335  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1336  {
1337  // Get the difference vector between current vertex and aPoint
1338  delta = *iterator - aPoint;
1339 
1340  // Compute distance
1341  distance = delta.EuclideanNorm();
1342 
1343  // Check for collisions
1344  if( distance <= clearance )
1345  {
1346  collision = true;
1347 
1348  // Update aClearance to look for closer vertices
1349  clearance = distance;
1350 
1351  // Store the indices that identify the vertex
1352  aClosestVertex = iterator.GetIndex();
1353  }
1354  }
1355 
1356  return collision;
1357 }
1358 
1359 
1361  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1362 {
1363  // Shows whether there was a collision
1364  bool collision = false;
1365 
1366  SEGMENT_ITERATOR iterator;
1367 
1368  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1369  {
1370  SEG currentSegment = *iterator;
1371  int distance = currentSegment.Distance( aPoint );
1372 
1373  // Check for collisions
1374  if( distance <= aClearance )
1375  {
1376  collision = true;
1377 
1378  // Update aClearance to look for closer edges
1379  aClearance = distance;
1380 
1381  // Store the indices that identify the vertex
1382  aClosestVertex = iterator.GetIndex();
1383  }
1384  }
1385 
1386  return collision;
1387 }
1388 
1389 
1390 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1391 {
1392  if( m_polys.size() == 0 ) // empty set?
1393  return false;
1394 
1395  // If there is a polygon specified, check the condition against that polygon
1396  if( aSubpolyIndex >= 0 )
1397  return containsSingle( aP, aSubpolyIndex, aIgnoreHoles );
1398 
1399  // In any other case, check it against all polygons in the set
1400  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1401  {
1402  if( containsSingle( aP, polygonIdx, aIgnoreHoles ) )
1403  return true;
1404  }
1405 
1406  return false;
1407 }
1408 
1409 
1410 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1411 {
1412  VERTEX_INDEX index;
1413 
1414  // Assure the to be removed vertex exists, abort otherwise
1415  if( GetRelativeIndices( aGlobalIndex, &index ) )
1416  RemoveVertex( index );
1417  else
1418  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1419 }
1420 
1421 
1423 {
1424  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1425 }
1426 
1427 
1428 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, bool aIgnoreHoles ) const
1429 {
1430  // Check that the point is inside the outline
1431  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1432  {
1433  if( !aIgnoreHoles )
1434  {
1435  // Check that the point is not in any of the holes
1436  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1437  {
1438  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1439 
1440  // If the point is inside a hole (and not on its edge),
1441  // it is outside of the polygon
1442  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1443  return false;
1444  }
1445  }
1446 
1447  return true;
1448  }
1449 
1450  return false;
1451 }
1452 
1453 
1454 bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
1455 {
1456  return aPath.PointInside( aP );
1457 }
1458 
1459 
1460 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1461 {
1462  for( POLYGON& poly : m_polys )
1463  {
1464  for( SHAPE_LINE_CHAIN& path : poly )
1465  {
1466  path.Move( aVector );
1467  }
1468  }
1469 }
1470 
1471 
1472 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1473 {
1474  for( POLYGON& poly : m_polys )
1475  {
1476  for( SHAPE_LINE_CHAIN& path : poly )
1477  {
1478  path.Rotate( aAngle, aCenter );
1479  }
1480  }
1481 }
1482 
1483 
1485 {
1486  int c = 0;
1487 
1488  for( const POLYGON& poly : m_polys )
1489  {
1490  for( const SHAPE_LINE_CHAIN& path : poly )
1491  {
1492  c += path.PointCount();
1493  }
1494  }
1495 
1496  return c;
1497 }
1498 
1499 
1500 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1501 {
1502  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1503 }
1504 
1505 
1507  int aErrorMax,
1508  int aIndex )
1509 {
1510  return chamferFilletPolygon( CORNER_MODE::FILLETED, aRadius, aIndex, aErrorMax );
1511 }
1512 
1513 
1514 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1515 {
1516  // We calculate the min dist between the segment and each outline segment
1517  // However, if the segment to test is inside the outline, and does not cross
1518  // any edge, it can be seen outside the polygon.
1519  // Therefore test if a segment end is inside ( testing only one end is enough )
1520  if( containsSingle( aPoint, aPolygonIndex ) )
1521  return 0;
1522 
1523  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1524 
1525  SEG polygonEdge = *iterator;
1526  int minDistance = polygonEdge.Distance( aPoint );
1527 
1528  for( iterator++; iterator && minDistance > 0; iterator++ )
1529  {
1530  polygonEdge = *iterator;
1531 
1532  int currentDistance = polygonEdge.Distance( aPoint );
1533 
1534  if( currentDistance < minDistance )
1535  minDistance = currentDistance;
1536  }
1537 
1538  return minDistance;
1539 }
1540 
1541 
1542 int SHAPE_POLY_SET::DistanceToPolygon( SEG aSegment, int aPolygonIndex, int aSegmentWidth )
1543 {
1544  // We calculate the min dist between the segment and each outline segment
1545  // However, if the segment to test is inside the outline, and does not cross
1546  // any edge, it can be seen outside the polygon.
1547  // Therefore test if a segment end is inside ( testing only one end is enough )
1548  if( containsSingle( aSegment.A, aPolygonIndex ) )
1549  return 0;
1550 
1551  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1552 
1553  SEG polygonEdge = *iterator;
1554  int minDistance = polygonEdge.Distance( aSegment );
1555 
1556  for( iterator++; iterator && minDistance > 0; iterator++ )
1557  {
1558  polygonEdge = *iterator;
1559 
1560  int currentDistance = polygonEdge.Distance( aSegment );
1561 
1562  if( currentDistance < minDistance )
1563  minDistance = currentDistance;
1564  }
1565 
1566  // Take into account the width of the segment
1567  if( aSegmentWidth > 0 )
1568  minDistance -= aSegmentWidth / 2;
1569 
1570  // Return the maximum of minDistance and zero
1571  return minDistance < 0 ? 0 : minDistance;
1572 }
1573 
1574 
1576 {
1577  int currentDistance;
1578  int minDistance = DistanceToPolygon( aPoint, 0 );
1579 
1580  // Iterate through all the polygons and get the minimum distance.
1581  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1582  {
1583  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1584 
1585  if( currentDistance < minDistance )
1586  minDistance = currentDistance;
1587  }
1588 
1589  return minDistance;
1590 }
1591 
1592 
1593 int SHAPE_POLY_SET::Distance( const SEG& aSegment, int aSegmentWidth )
1594 {
1595  int currentDistance;
1596  int minDistance = DistanceToPolygon( aSegment, 0 );
1597 
1598  // Iterate through all the polygons and get the minimum distance.
1599  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1600  {
1601  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1602 
1603  if( currentDistance < minDistance )
1604  minDistance = currentDistance;
1605  }
1606 
1607  return minDistance;
1608 }
1609 
1610 
1611 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1612 {
1613  VERTEX_INDEX index;
1614 
1615  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1616  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1617  return false;
1618 
1619  // The contour is a hole if its index is greater than zero
1620  return index.m_contour > 0;
1621 }
1622 
1623 
1625 {
1626  SHAPE_POLY_SET chamfered;
1627 
1628  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1629  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1630 
1631  return chamfered;
1632 }
1633 
1634 
1635 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
1636 {
1637  SHAPE_POLY_SET filleted;
1638 
1639  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1640  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, polygonIdx ) );
1641 
1642  return filleted;
1643 }
1644 
1645 
1647  unsigned int aDistance,
1648  int aIndex,
1649  int aErrorMax )
1650 {
1651  // Null segments create serious issues in calculations. Remove them:
1653 
1654  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1655  SHAPE_POLY_SET::POLYGON newPoly;
1656 
1657  // If the chamfering distance is zero, then the polygon remain intact.
1658  if( aDistance == 0 )
1659  {
1660  return currentPoly;
1661  }
1662 
1663  // Iterate through all the contours (outline and holes) of the polygon.
1664  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1665  {
1666  // Generate a new contour in the new polygon
1667  SHAPE_LINE_CHAIN newContour;
1668 
1669  // Iterate through the vertices of the contour
1670  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1671  {
1672  // Current vertex
1673  int x1 = currContour.Point( currVertex ).x;
1674  int y1 = currContour.Point( currVertex ).y;
1675 
1676  // Indices for previous and next vertices.
1677  int prevVertex;
1678  int nextVertex;
1679 
1680  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1681 
1682  // Previous vertex is the last one if the current vertex is the first one
1683  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1684 
1685  // next vertex is the first one if the current vertex is the last one.
1686  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1687 
1688  // Previous vertex computation
1689  double xa = currContour.Point( prevVertex ).x - x1;
1690  double ya = currContour.Point( prevVertex ).y - y1;
1691 
1692  // Next vertex computation
1693  double xb = currContour.Point( nextVertex ).x - x1;
1694  double yb = currContour.Point( nextVertex ).y - y1;
1695 
1696  // Compute the new distances
1697  double lena = hypot( xa, ya );
1698  double lenb = hypot( xb, yb );
1699 
1700  // Make the final computations depending on the mode selected, chamfered or filleted.
1701  if( aMode == CORNER_MODE::CHAMFERED )
1702  {
1703  double distance = aDistance;
1704 
1705  // Chamfer one half of an edge at most
1706  if( 0.5 * lena < distance )
1707  distance = 0.5 * lena;
1708 
1709  if( 0.5 * lenb < distance )
1710  distance = 0.5 * lenb;
1711 
1712  int nx1 = round_nearest( distance * xa / lena );
1713  int ny1 = round_nearest( distance * ya / lena );
1714 
1715  newContour.Append( x1 + nx1, y1 + ny1 );
1716 
1717  int nx2 = round_nearest( distance * xb / lenb );
1718  int ny2 = round_nearest( distance * yb / lenb );
1719 
1720  newContour.Append( x1 + nx2, y1 + ny2 );
1721  }
1722  else // CORNER_MODE = FILLETED
1723  {
1724  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1725 
1726  double radius = aDistance;
1727  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1728 
1729  // Do nothing in case of parallel edges
1730  if( std::isinf( denom ) )
1731  continue;
1732 
1733  // Limit rounding distance to one half of an edge
1734  if( 0.5 * lena * denom < radius )
1735  radius = 0.5 * lena * denom;
1736 
1737  if( 0.5 * lenb * denom < radius )
1738  radius = 0.5 * lenb * denom;
1739 
1740  // Calculate fillet arc absolute center point (xc, yx)
1741  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1742  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1743  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1744  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1745  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1746 
1747  // Calculate arc start and end vectors
1748  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1749  double xs = x1 + k * xa / lena - xc;
1750  double ys = y1 + k * ya / lena - yc;
1751  double xe = x1 + k * xb / lenb - xc;
1752  double ye = y1 + k * yb / lenb - yc;
1753 
1754  // Cosine of arc angle
1755  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1756 
1757  // Make sure the argument is in [-1,1], interval in which the acos function is
1758  // defined
1759  if( argument < -1 )
1760  argument = -1;
1761  else if( argument > 1 )
1762  argument = 1;
1763 
1764  double arcAngle = acos( argument );
1765  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1766  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1767 
1768  double deltaAngle = arcAngle / segments;
1769  double startAngle = atan2( -ys, xs );
1770 
1771  // Flip arc for inner corners
1772  if( xa * yb - ya * xb <= 0 )
1773  deltaAngle *= -1;
1774 
1775  double nx = xc + xs;
1776  double ny = yc + ys;
1777 
1778  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1779 
1780  // Store the previous added corner to make a sanity check
1781  int prevX = round_nearest( nx );
1782  int prevY = round_nearest( ny );
1783 
1784  for( int j = 0; j < segments; j++ )
1785  {
1786  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1787  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1788 
1789  // Sanity check: the rounding can produce repeated corners; do not add them.
1790  if( round_nearest( nx ) != prevX || round_nearest( ny ) != prevY )
1791  {
1792  newContour.Append( round_nearest( nx ), round_nearest( ny ) );
1793  prevX = round_nearest( nx );
1794  prevY = round_nearest( ny );
1795  }
1796  }
1797  }
1798  }
1799 
1800  // Close the current contour and add it the new polygon
1801  newContour.SetClosed( true );
1802  newPoly.push_back( newContour );
1803  }
1804 
1805  return newPoly;
1806 }
1807 
1808 
1810 {
1811  static_cast<SHAPE&>(*this) = aOther;
1812  m_polys = aOther.m_polys;
1813 
1814  // reset poly cache:
1815  m_hash = MD5_HASH{};
1816  m_triangulationValid = false;
1817  m_triangulatedPolys.clear();
1818  return *this;
1819 }
1820 
1822 {
1823  if( !m_hash.IsValid() )
1824  return checksum();
1825 
1826  return m_hash;
1827 }
1828 
1829 
1831 {
1832  if( !m_triangulationValid )
1833  return false;
1834 
1835  if( !m_hash.IsValid() )
1836  return false;
1837 
1838  auto hash = checksum();
1839 
1840  return hash == m_hash;
1841 }
1842 
1843 
1845 {
1846  bool recalculate = !m_hash.IsValid();
1847  MD5_HASH hash;
1848 
1849  if( !m_triangulationValid )
1850  recalculate = true;
1851 
1852  if( !recalculate )
1853  {
1854  hash = checksum();
1855 
1856  if( m_hash != hash )
1857  {
1858  m_hash = hash;
1859  recalculate = true;
1860  }
1861  }
1862 
1863  if( !recalculate )
1864  return;
1865 
1866  SHAPE_POLY_SET tmpSet = *this;
1867 
1868  if( tmpSet.HasHoles() )
1869  tmpSet.Fracture( PM_FAST );
1870 
1871  m_triangulatedPolys.clear();
1872 
1873  for( int i = 0; i < tmpSet.OutlineCount(); i++ )
1874  {
1875  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
1876  PolygonTriangulation tess( *m_triangulatedPolys.back() );
1877 
1878  tess.TesselatePolygon( tmpSet.Polygon( i ).front() );
1879  }
1880 
1881  m_triangulationValid = true;
1882  m_hash = checksum();
1883 }
1884 
1885 
1887 {
1888  MD5_HASH hash;
1889 
1890  hash.Hash( m_polys.size() );
1891 
1892  for( const auto& outline : m_polys )
1893  {
1894  hash.Hash( outline.size() );
1895 
1896  for( const auto& lc : outline )
1897  {
1898  hash.Hash( lc.PointCount() );
1899 
1900  for( int i = 0; i < lc.PointCount(); i++ )
1901  {
1902  hash.Hash( lc.CPoint( i ).x );
1903  hash.Hash( lc.CPoint( i ).y );
1904  }
1905  }
1906  }
1907 
1908  hash.Finalize();
1909 
1910  return hash;
1911 }
1912 
1913 
1915 {
1916  for( int i = 0; i < OutlineCount(); i++ )
1917  {
1918  if( hasTouchingHoles( CPolygon( i ) ) )
1919  {
1920  return true;
1921  }
1922  }
1923 
1924  return false;
1925 }
1926 
1927 
1928 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
1929 {
1930  std::set< long long > ptHashes;
1931 
1932  for( const auto& lc : aPoly )
1933  {
1934  for( const VECTOR2I& pt : lc.CPoints() )
1935  {
1936  const long long ptHash = (long long) pt.x << 32 | pt.y;
1937 
1938  if( ptHashes.count( ptHash ) > 0 )
1939  {
1940  return true;
1941  }
1942 
1943  ptHashes.insert( ptHash );
1944  }
1945  }
1946 
1947  return false;
1948 }
std::vector< SHAPE_LINE_CHAIN > POLYGON
represents a single polygon outline with holes.
void booleanOp(ClipperLib::ClipType aType, const SHAPE_POLY_SET &aOtherShape, POLYGON_MODE aFastMode)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
CITER next(CITER it)
Definition: ptree.cpp:130
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
bool PointInside(const VECTOR2I &aP) const
Function PointInside()
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
bool HasHoles() const
Returns true if the polygon set has any holes.
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
bool matches(int y) const
void fractureSingle(POLYGON &paths)
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
static 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...
int PointCount() const
Function PointCount()
MD5_HASH checksum() const
MD5_HASH GetHash() const
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Returns total number of vertices stored in the set.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, bool aIgnoreHoles=false) const
Returns true if a given subpolygon contains the point aP.
Struct VERTEX_INDEX.
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
Class SEGMENT_ITERATOR_TEMPLATE.
void TesselatePolygon(const SHAPE_LINE_CHAIN &aPoly)
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
bool IsTriangulationUpToDate() const
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
int OutlineCount() const
Returns the number of outlines in the set
OPT_VECTOR2I Intersect(const SEG &aSeg, bool aIgnoreEndpoints=false, bool aLines=false) const
Function Intersect()
Definition: seg.cpp:99
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
FractureEdge(bool connected, SHAPE_LINE_CHAIN *owner, int index)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:587
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
#define abs(a)
Definition: auxiliary.h:84
VERTEX_INDEX GetIndex()
Function GetIndex.
static const int delta[8][2]
Definition: solve.cpp:112
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.
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool IsEndContour() const
Function IsEndContour.
#define SEG_CNT_MAX
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
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 SEG CSegment(int aIndex) const
Function CSegment()
void SetClosed(bool aClosed)
Function SetClosed()
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:66
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:292
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
void Move(const VECTOR2I &aVector) override
Class SHAPE_POLY_SET.
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
bool hasTouchingHoles(const POLYGON &aPoly) const
Returns true if the polygon set has any holes that touch share a vertex.
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
Class SHAPE.
Definition: shape.h:58
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide Checks whether the point aP collides with the inside of the polygon set; if the poin...
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h: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 ...
int NewOutline()
Creates a new empty polygon in the set and returns its index
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon...
Definition: seg.h:36
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint...
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
bool IsValid() const
Definition: md5_hash.h:23
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h: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.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
#define max(a, b)
Definition: auxiliary.h:86
ITERATOR IterateWithHoles()
Function IterateWithHoles.
Class SHAPE_LINE_CHAIN.
double Area() const
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
int Distance(VECTOR2I aPoint)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
Class ITERATOR_TEMPLATE.
size_t i
Definition: json11.cpp:597
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
VECTOR2I A
Definition: seg.h:46
static bool empty(const wxTextEntryBase *aCtrl)
bool IsClosed() const
Function IsClosed()
const POLYGON & CPolygon(int aIndex) const
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
VECTOR2I & Point(int aIndex)
Function Point()
void Finalize()
Definition: md5_hash.cpp:76
POLYGON_MODE
operations on polygons use a aFastMode param if aFastMode is PM_FAST (true) the result can be a weak ...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp ...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, bool aIgnoreHoles=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
SHAPE * Clone() const override
Function Clone()
bool IsSelfIntersecting()
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting...
FractureEdge(int y=0)
void Rotate(double aAngle, const VECTOR2I &aCenter)
Function Rotate rotates all vertices by a given angle.
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:195
const BOX2I BBox(int aClearance=0) const override
Function BBox()
VERTEX_INDEX GetIndex()
Function GetIndex.
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
#define min(a, b)
Definition: auxiliary.h:85
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline) ...
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set...
void importTree(ClipperLib::PolyTree *tree)
VECTOR2I B
Definition: seg.h:47
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes...