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 #include <algorithm>
30 #include <assert.h> // for assert
31 #include <cmath> // for sqrt, cos, hypot, isinf
32 #include <cstdio>
33 #include <istream> // for operator<<, operator>>
34 #include <limits> // for numeric_limits
35 #include <memory>
36 #include <set>
37 #include <string> // for char_traits, operator!=
38 #include <type_traits> // for swap, move
39 #include <unordered_set>
40 #include <vector>
41 
42 #include <clipper.hpp> // for Clipper, PolyNode, Clipp...
45 #include <geometry/seg.h> // for SEG, OPT_VECTOR2I
46 #include <geometry/shape.h>
49 #include <math/box2.h> // for BOX2I
50 #include <math/util.h> // for KiROUND, rescale
51 #include <math/vector2d.h> // for VECTOR2I, VECTOR2D, VECTOR2
52 #include <md5_hash.h>
53 #include <geometry/shape_segment.h>
54 #include <geometry/shape_circle.h>
55 #include <geometry/shape_simple.h>
57 
58 using namespace ClipperLib;
59 
62 {
63 }
64 
65 
68 {
69  AddOutline( aOutline );
70 }
71 
72 
74  SHAPE( aOther ), m_polys( aOther.m_polys )
75 {
76  if( aOther.IsTriangulationUpToDate() )
77  {
78  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
79  m_triangulatedPolys.push_back(
80  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
81 
82  m_hash = aOther.GetHash();
83  m_triangulationValid = true;
84  }
85  else
86  {
87  m_triangulationValid = false;
88  m_hash = MD5_HASH();
89  m_triangulatedPolys.clear();
90  }
91 }
92 
93 
95 {
96 }
97 
98 
100 {
101  return new SHAPE_POLY_SET( *this );
102 }
103 
104 
106  SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
107 {
108  int polygonIdx = 0;
109  unsigned int contourIdx = 0;
110  int vertexIdx = 0;
111 
112  int currentGlobalIdx = 0;
113 
114  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
115  {
116  const POLYGON& currentPolygon = CPolygon( polygonIdx );
117 
118  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
119  {
120  const SHAPE_LINE_CHAIN& currentContour = currentPolygon[contourIdx];
121  int totalPoints = currentContour.PointCount();
122 
123  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
124  {
125  // Check if the current vertex is the globally indexed as aGlobalIdx
126  if( currentGlobalIdx == aGlobalIdx )
127  {
128  aRelativeIndices->m_polygon = polygonIdx;
129  aRelativeIndices->m_contour = contourIdx;
130  aRelativeIndices->m_vertex = vertexIdx;
131 
132  return true;
133  }
134 
135  // Advance
136  currentGlobalIdx++;
137  }
138  }
139  }
140 
141  return false;
142 }
143 
144 
146  int& aGlobalIdx )
147 {
148  int selectedVertex = aRelativeIndices.m_vertex;
149  unsigned int selectedContour = aRelativeIndices.m_contour;
150  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
151 
152  // Check whether the vertex indices make sense in this poly set
153  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size()
154  && selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
155  {
156  POLYGON currentPolygon;
157 
158  aGlobalIdx = 0;
159 
160  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
161  {
162  currentPolygon = Polygon( polygonIdx );
163 
164  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
165  {
166  aGlobalIdx += currentPolygon[contourIdx].PointCount();
167  }
168  }
169 
170  currentPolygon = Polygon( selectedPolygon );
171 
172  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx++ )
173  {
174  aGlobalIdx += currentPolygon[contourIdx].PointCount();
175  }
176 
177  aGlobalIdx += selectedVertex;
178 
179  return true;
180  }
181  else
182  {
183  return false;
184  }
185 }
186 
187 
189 {
190  SHAPE_LINE_CHAIN empty_path;
191  POLYGON poly;
192 
193  empty_path.SetClosed( true );
194  poly.push_back( empty_path );
195  m_polys.push_back( poly );
196  return m_polys.size() - 1;
197 }
198 
199 
200 int SHAPE_POLY_SET::NewHole( int aOutline )
201 {
202  SHAPE_LINE_CHAIN empty_path;
203 
204  empty_path.SetClosed( true );
205 
206  // Default outline is the last one
207  if( aOutline < 0 )
208  aOutline += m_polys.size();
209 
210  // Add hole to the selected outline
211  m_polys[aOutline].push_back( empty_path );
212 
213  return m_polys.back().size() - 2;
214 }
215 
216 
217 int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
218 {
219  assert( m_polys.size() );
220 
221  if( aOutline < 0 )
222  aOutline += m_polys.size();
223 
224  int idx;
225 
226  if( aHole < 0 )
227  idx = 0;
228  else
229  idx = aHole + 1;
230 
231  assert( aOutline < (int) m_polys.size() );
232  assert( idx < (int) m_polys[aOutline].size() );
233 
234  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
235 
236  return m_polys[aOutline][idx].PointCount();
237 }
238 
239 
240 void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex )
241 {
242  VERTEX_INDEX index;
243 
244  if( aGlobalIndex < 0 )
245  aGlobalIndex = 0;
246 
247  if( aGlobalIndex >= TotalVertices() )
248  {
249  Append( aNewVertex );
250  }
251  else
252  {
253  // Assure the position to be inserted exists; throw an exception otherwise
254  if( GetRelativeIndices( aGlobalIndex, &index ) )
255  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
256  else
257  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
258  }
259 }
260 
261 
262 int SHAPE_POLY_SET::VertexCount( int aOutline, int aHole ) const
263 {
264  if( m_polys.size() == 0 ) // Empty poly set
265  return 0;
266 
267  if( aOutline < 0 ) // Use last outline
268  aOutline += m_polys.size();
269 
270  int idx;
271 
272  if( aHole < 0 )
273  idx = 0;
274  else
275  idx = aHole + 1;
276 
277  if( aOutline >= (int) m_polys.size() ) // not existing outline
278  return 0;
279 
280  if( idx >= (int) m_polys[aOutline].size() ) // not existing hole
281  return 0;
282 
283  return m_polys[aOutline][idx].PointCount();
284 }
285 
286 
287 SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
288 {
289  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
290 
291  SHAPE_POLY_SET newPolySet;
292 
293  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
294  {
295  newPolySet.m_polys.push_back( Polygon( index ) );
296  }
297 
298  return newPolySet;
299 }
300 
301 
302 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
303 {
304  if( aOutline < 0 )
305  aOutline += m_polys.size();
306 
307  int idx;
308 
309  if( aHole < 0 )
310  idx = 0;
311  else
312  idx = aHole + 1;
313 
314  assert( aOutline < (int) m_polys.size() );
315  assert( idx < (int) m_polys[aOutline].size() );
316 
317  return m_polys[aOutline][idx].CPoint( aIndex );
318 }
319 
320 
321 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
322 {
324 
325  // Assure the passed index references a legal position; abort otherwise
326  if( !GetRelativeIndices( aGlobalIndex, &index ) )
327  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
328 
329  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
330 }
331 
332 
334 {
335  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
336 }
337 
338 
339 bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext )
340 {
342 
343  // If the edge does not exist, throw an exception, it is an illegal access memory error
344  if( !GetRelativeIndices( aGlobalIndex, &index ) )
345  return false;
346 
347  // Calculate the previous and next index of aGlobalIndex, corresponding to
348  // the same contour;
349  VERTEX_INDEX inext = index;
350  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
351 
352  if( index.m_vertex == 0 )
353  {
354  index.m_vertex = lastpoint;
355  inext.m_vertex = 1;
356  }
357  else if( index.m_vertex == lastpoint )
358  {
359  index.m_vertex--;
360  inext.m_vertex = 0;
361  }
362  else
363  {
364  inext.m_vertex++;
365  index.m_vertex--;
366  }
367 
368  if( aPrevious )
369  {
370  int previous;
371  GetGlobalIndex( index, previous );
372  *aPrevious = previous;
373  }
374 
375  if( aNext )
376  {
377  int next;
378  GetGlobalIndex( inext, next );
379  *aNext = next;
380  }
381 
382  return true;
383 }
384 
385 
386 bool SHAPE_POLY_SET::IsPolygonSelfIntersecting( int aPolygonIndex ) const
387 {
388  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
389  CONST_SEGMENT_ITERATOR innerIterator;
390 
391  for( iterator = CIterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
392  {
393  SEG firstSegment = *iterator;
394 
395  // Iterate through all remaining segments.
396  innerIterator = iterator;
397 
398  // Start in the next segment, we don't want to check collision between a segment and itself
399  for( innerIterator++; innerIterator; innerIterator++ )
400  {
401  SEG secondSegment = *innerIterator;
402 
403  // Check whether the two segments built collide, only when they are not adjacent.
404  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
405  return true;
406  }
407  }
408 
409  return false;
410 }
411 
412 
414 {
415  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
416  {
417  if( IsPolygonSelfIntersecting( polygon ) )
418  return true;
419  }
420 
421  return false;
422 }
423 
424 
426 {
427  assert( aOutline.IsClosed() );
428 
429  POLYGON poly;
430 
431  poly.push_back( aOutline );
432 
433  m_polys.push_back( poly );
434 
435  return m_polys.size() - 1;
436 }
437 
438 
439 int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
440 {
441  assert( m_polys.size() );
442 
443  if( aOutline < 0 )
444  aOutline += m_polys.size();
445 
446  assert( aOutline < (int)m_polys.size() );
447 
448  POLYGON& poly = m_polys[aOutline];
449 
450  assert( poly.size() );
451 
452  poly.push_back( aHole );
453 
454  return poly.size() - 2;
455 }
456 
457 
458 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
459  POLYGON_MODE aFastMode )
460 {
461  booleanOp( aType, *this, aOtherShape, aFastMode );
462 }
463 
464 
465 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
466  const SHAPE_POLY_SET& aShape,
467  const SHAPE_POLY_SET& aOtherShape,
468  POLYGON_MODE aFastMode )
469 {
470  Clipper c;
471 
472  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
473 
474  for( auto poly : aShape.m_polys )
475  {
476  for( size_t i = 0 ; i < poly.size(); i++ )
477  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
478  }
479 
480  for( auto poly : aOtherShape.m_polys )
481  {
482  for( size_t i = 0; i < poly.size(); i++ )
483  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
484  }
485 
486  PolyTree solution;
487 
488  c.Execute( aType, solution, pftNonZero, pftNonZero );
489 
490  importTree( &solution );
491 }
492 
493 
495 {
496  booleanOp( ctUnion, b, aFastMode );
497 }
498 
499 
501 {
502  booleanOp( ctDifference, b, aFastMode );
503 }
504 
505 
507 {
508  booleanOp( ctIntersection, b, aFastMode );
509 }
510 
511 
513  const SHAPE_POLY_SET& b,
514  POLYGON_MODE aFastMode )
515 {
516  booleanOp( ctUnion, a, b, aFastMode );
517 }
518 
519 
521  const SHAPE_POLY_SET& b,
522  POLYGON_MODE aFastMode )
523 {
524  booleanOp( ctDifference, a, b, aFastMode );
525 }
526 
527 
529  const SHAPE_POLY_SET& b,
530  POLYGON_MODE aFastMode )
531 {
532  booleanOp( ctIntersection, a, b, aFastMode );
533 }
534 
535 
536 void SHAPE_POLY_SET::InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount,
537  POLYGON_MODE aFastMode )
538 {
539  Simplify( aFastMode );
540  Inflate( aFactor, aCircleSegmentsCount );
541  Fracture( aFastMode );
542 }
543 
544 
545 void SHAPE_POLY_SET::Inflate( int aAmount, int aCircleSegmentsCount,
546  CORNER_STRATEGY aCornerStrategy )
547 {
548  // A static table to avoid repetitive calculations of the coefficient
549  // 1.0 - cos( M_PI / aCircleSegmentsCount )
550  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
551  #define SEG_CNT_MAX 64
552  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
553 
554  ClipperOffset c;
555 
556  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
557  // and are not what you'd think they are.
558  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
559  JoinType joinType = jtRound; // The way corners are offsetted
560  double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
561  JoinType miterFallback = jtSquare;
562 
563  switch( aCornerStrategy )
564  {
565  case ALLOW_ACUTE_CORNERS:
566  joinType = jtMiter;
567  miterLimit = 10; // Allows large spikes
568  miterFallback = jtSquare;
569  break;
570 
571  case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
572  joinType = jtMiter;
573  miterFallback = jtRound;
574  break;
575 
576  case ROUND_ACUTE_CORNERS: // Acute angles are rounded
577  joinType = jtMiter;
578  miterFallback = jtSquare;
579  break;
580 
581  case CHAMFER_ALL_CORNERS: // All angles are chamfered.
582  joinType = jtSquare;
583  miterFallback = jtSquare;
584  break;
585 
586  case ROUND_ALL_CORNERS: // All angles are rounded.
587  joinType = jtRound;
588  miterFallback = jtSquare;
589  break;
590  }
591 
592  for( const POLYGON& poly : m_polys )
593  {
594  for( size_t i = 0; i < poly.size(); i++ )
595  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
596  }
597 
598  PolyTree solution;
599 
600  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
601  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
602  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
603 
604  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
605  aCircleSegmentsCount = 6;
606 
607  double coeff;
608 
609  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
610  {
611  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
612 
613  if( aCircleSegmentsCount <= SEG_CNT_MAX )
614  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
615  }
616  else
617  coeff = arc_tolerance_factor[aCircleSegmentsCount];
618 
619  c.ArcTolerance = std::abs( aAmount ) * coeff;
620  c.MiterLimit = miterLimit;
621  c.MiterFallback = miterFallback;
622  c.Execute( solution, aAmount );
623 
624  importTree( &solution );
625 }
626 
627 
628 void SHAPE_POLY_SET::importTree( PolyTree* tree )
629 {
630  m_polys.clear();
631 
632  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
633  {
634  if( !n->IsHole() )
635  {
636  POLYGON paths;
637  paths.reserve( n->Childs.size() + 1 );
638  paths.push_back( n->Contour );
639 
640  for( unsigned int i = 0; i < n->Childs.size(); i++ )
641  paths.push_back( n->Childs[i]->Contour );
642 
643  m_polys.push_back( paths );
644  }
645  }
646 }
647 
648 
650 {
651  FractureEdge( int y = 0 ) :
652  m_connected( false ),
653  m_next( NULL )
654  {
655  m_p1.x = m_p2.y = y;
656  }
657 
658  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
659  m_connected( connected ),
660  m_p1( p1 ),
661  m_p2( p2 ),
662  m_next( NULL )
663  {
664  }
665 
666  bool matches( int y ) const
667  {
668  return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
669  }
670 
674 };
675 
676 
677 typedef std::vector<FractureEdge*> FractureEdgeSet;
678 
679 
680 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
681 {
682  int x = edge->m_p1.x;
683  int y = edge->m_p1.y;
684  int min_dist = std::numeric_limits<int>::max();
685  int x_nearest = 0;
686 
687  FractureEdge* e_nearest = NULL;
688 
689  for( FractureEdge* e : edges )
690  {
691  if( !e->matches( y ) )
692  continue;
693 
694  int x_intersect;
695 
696  if( e->m_p1.y == e->m_p2.y ) // horizontal edge
697  {
698  x_intersect = std::max( e->m_p1.x, e->m_p2.x );
699  }
700  else
701  {
702  x_intersect = e->m_p1.x + rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y,
703  e->m_p2.y - e->m_p1.y );
704  }
705 
706  int dist = ( x - x_intersect );
707 
708  if( dist >= 0 && dist < min_dist && e->m_connected )
709  {
710  min_dist = dist;
711  x_nearest = x_intersect;
712  e_nearest = e;
713  }
714  }
715 
716  if( e_nearest && e_nearest->m_connected )
717  {
718  int count = 0;
719 
720  FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
721  FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
722  FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
723 
724  edges.push_back( split_2 );
725  edges.push_back( lead1 );
726  edges.push_back( lead2 );
727 
728  FractureEdge* link = e_nearest->m_next;
729 
730  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
731  e_nearest->m_next = lead1;
732  lead1->m_next = edge;
733 
734  FractureEdge* last;
735 
736  for( last = edge; last->m_next != edge; last = last->m_next )
737  {
738  last->m_connected = true;
739  count++;
740  }
741 
742  last->m_connected = true;
743  last->m_next = lead2;
744  lead2->m_next = split_2;
745  split_2->m_next = link;
746 
747  return count + 1;
748  }
749 
750  return 0;
751 }
752 
753 
755 {
756  FractureEdgeSet edges;
757  FractureEdgeSet border_edges;
758  FractureEdge* root = NULL;
759 
760  bool first = true;
761 
762  if( paths.size() == 1 )
763  return;
764 
765  int num_unconnected = 0;
766 
767  for( const SHAPE_LINE_CHAIN& path : paths )
768  {
769  const std::vector<VECTOR2I>& points = path.CPoints();
770  int pointCount = points.size();
771 
772  FractureEdge* prev = NULL, * first_edge = NULL;
773 
774  int x_min = std::numeric_limits<int>::max();
775 
776  for( const VECTOR2I& p : points )
777  {
778  if( p.x < x_min )
779  x_min = p.x;
780  }
781 
782  for( int i = 0; i < pointCount; i++ )
783  {
784  // Do not use path.CPoint() here; open-coding it using the local variables "points"
785  // and "pointCount" gives a non-trivial performance boost to zone fill times.
786  FractureEdge* fe = new FractureEdge( first, points[ i ],
787  points[ i+1 == pointCount ? 0 : i+1 ] );
788 
789  if( !root )
790  root = fe;
791 
792  if( !first_edge )
793  first_edge = fe;
794 
795  if( prev )
796  prev->m_next = fe;
797 
798  if( i == pointCount - 1 )
799  fe->m_next = first_edge;
800 
801  prev = fe;
802  edges.push_back( fe );
803 
804  if( !first )
805  {
806  if( fe->m_p1.x == x_min )
807  border_edges.push_back( fe );
808  }
809 
810  if( !fe->m_connected )
811  num_unconnected++;
812  }
813 
814  first = false; // first path is always the outline
815  }
816 
817  // keep connecting holes to the main outline, until there's no holes left...
818  while( num_unconnected > 0 )
819  {
820  int x_min = std::numeric_limits<int>::max();
821 
822  FractureEdge* smallestX = NULL;
823 
824  // find the left-most hole edge and merge with the outline
825  for( FractureEdge* border_edge : border_edges )
826  {
827  int xt = border_edge->m_p1.x;
828 
829  if( ( xt < x_min ) && !border_edge->m_connected )
830  {
831  x_min = xt;
832  smallestX = border_edge;
833  }
834  }
835 
836  num_unconnected -= processEdge( edges, smallestX );
837  }
838 
839  paths.clear();
840  SHAPE_LINE_CHAIN newPath;
841 
842  newPath.SetClosed( true );
843 
844  FractureEdge* e;
845 
846  for( e = root; e->m_next != root; e = e->m_next )
847  newPath.Append( e->m_p1 );
848 
849  newPath.Append( e->m_p1 );
850 
851  for( FractureEdge* edge : edges )
852  delete edge;
853 
854  paths.push_back( std::move( newPath ) );
855 }
856 
857 
859 {
860  Simplify( aFastMode ); // remove overlapping holes/degeneracy
861 
862  for( POLYGON& paths : m_polys )
863  {
864  fractureSingle( paths );
865  }
866 }
867 
868 
870 {
871  assert( aPoly.size() == 1 );
872 
873  struct EDGE
874  {
875  int m_index = 0;
876  SHAPE_LINE_CHAIN* m_poly = nullptr;
877  bool m_duplicate = false;
878 
879  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
880  m_index( aIndex ),
881  m_poly( aPolygon )
882  {}
883 
884  bool compareSegs( const SEG& s1, const SEG& s2 ) const
885  {
886  return (s1.A == s2.B && s1.B == s2.A);
887  }
888 
889  bool operator==( const EDGE& aOther ) const
890  {
891  return compareSegs( m_poly->CSegment( m_index ),
892  aOther.m_poly->CSegment( aOther.m_index ) );
893  }
894 
895  bool operator!=( const EDGE& aOther ) const
896  {
897  return !compareSegs( m_poly->CSegment( m_index ),
898  aOther.m_poly->CSegment( aOther.m_index ) );
899  }
900 
901  struct HASH
902  {
903  std::size_t operator()( const EDGE& aEdge ) const
904  {
905  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
906 
907  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
908  }
909  };
910  };
911 
912  struct EDGE_LIST_ENTRY
913  {
914  int index;
915  EDGE_LIST_ENTRY* next;
916  };
917 
918  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
919 
920  auto lc = aPoly[0];
921  lc.Simplify();
922 
923  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
924 
925  for( int i = 0; i < lc.SegmentCount(); i++ )
926  {
927  edgeList[i].index = i;
928  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
929  }
930 
931  std::unordered_set<EDGE_LIST_ENTRY*> queue;
932 
933  for( int i = 0; i < lc.SegmentCount(); i++ )
934  {
935  EDGE e( &lc, i );
936  uniqueEdges.insert( e );
937  }
938 
939  for( int i = 0; i < lc.SegmentCount(); i++ )
940  {
941  EDGE e( &lc, i );
942  auto it = uniqueEdges.find( e );
943 
944  if( it != uniqueEdges.end() && it->m_index != i )
945  {
946  int e1 = it->m_index;
947  int e2 = i;
948 
949  if( e1 > e2 )
950  std::swap( e1, e2 );
951 
952  int e1_prev = e1 - 1;
953 
954  if( e1_prev < 0 )
955  e1_prev = lc.SegmentCount() - 1;
956 
957  int e2_prev = e2 - 1;
958 
959  if( e2_prev < 0 )
960  e2_prev = lc.SegmentCount() - 1;
961 
962  int e1_next = e1 + 1;
963 
964  if( e1_next == lc.SegmentCount() )
965  e1_next = 0;
966 
967  int e2_next = e2 + 1;
968 
969  if( e2_next == lc.SegmentCount() )
970  e2_next = 0;
971 
972  edgeList[e1_prev].next = &edgeList[ e2_next ];
973  edgeList[e2_prev].next = &edgeList[ e1_next ];
974  edgeList[i].next = nullptr;
975  edgeList[it->m_index].next = nullptr;
976  }
977  }
978 
979  for( int i = 0; i < lc.SegmentCount(); i++ )
980  {
981  if( edgeList[i].next )
982  queue.insert( &edgeList[i] );
983  }
984 
985  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
986 
987  int n = 0;
988  int outline = -1;
989 
990  POLYGON result;
991 
992  while( queue.size() )
993  {
994  auto e_first = (*queue.begin() );
995  auto e = e_first;
996  int cnt = 0;
997 
998  do {
999  edgeBuf[cnt++] = e;
1000  e = e->next;
1001  } while( e && e != e_first );
1002 
1003  SHAPE_LINE_CHAIN outl;
1004 
1005  for( int i = 0; i < cnt; i++ )
1006  {
1007  auto p = lc.CPoint( edgeBuf[i]->index );
1008  outl.Append( p );
1009  queue.erase( edgeBuf[i] );
1010  }
1011 
1012  outl.SetClosed( true );
1013 
1014  bool cw = outl.Area() > 0.0;
1015 
1016  if( cw )
1017  outline = n;
1018 
1019  result.push_back( outl );
1020  n++;
1021  }
1022 
1023  if( outline > 0 )
1024  std::swap( result[0], result[outline] );
1025 
1026  aPoly = result;
1027 }
1028 
1029 
1031 {
1032  // Iterate through all the polygons on the set
1033  for( const POLYGON& paths : m_polys )
1034  {
1035  // If any of them has more than one contour, it is a hole.
1036  if( paths.size() > 1 )
1037  return true;
1038  }
1039 
1040  // Return false if and only if every polygon has just one outline, without holes.
1041  return false;
1042 }
1043 
1044 
1046 {
1047  for( POLYGON& path : m_polys )
1048  {
1049  unfractureSingle( path );
1050  }
1051 
1052  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1053 }
1054 
1055 
1057 {
1059 
1060  booleanOp( ctUnion, empty, aFastMode );
1061 }
1062 
1063 
1065 {
1066  // We are expecting only one main outline, but this main outline can have holes
1067  // if holes: combine holes and remove them from the main outline.
1068  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1069  // calculations, but it is not mandatory. It is used mainly
1070  // because there is usually only very few vertices in area outlines
1071  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1072  SHAPE_POLY_SET holesBuffer;
1073 
1074  // Move holes stored in outline to holesBuffer:
1075  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1076  while( outline.size() > 1 )
1077  {
1078  holesBuffer.AddOutline( outline.back() );
1079  outline.pop_back();
1080  }
1081 
1083 
1084  // If any hole, substract it to main outline
1085  if( holesBuffer.OutlineCount() )
1086  {
1087  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1089  }
1090 
1092 
1093  return OutlineCount();
1094 }
1095 
1096 
1097 const std::string SHAPE_POLY_SET::Format() const
1098 {
1099  std::stringstream ss;
1100 
1101  ss << "SHAPE_LINE_CHAIN poly; \n";
1102 
1103  for( unsigned i = 0; i < m_polys.size(); i++ )
1104  {
1105  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1106  {
1107 
1108  ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1109 
1110  SHAPE_POLY_SET poly;
1111 
1112  if( j == 0 )
1113  {
1114  ss << " poly.AddOutline(tmp); } \n";
1115  }
1116  else
1117  {
1118  ss << " poly.AddHole(tmp); } \n";
1119  }
1120 
1121  }
1122  }
1123 
1124  return ss.str();
1125 }
1126 
1127 
1128 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1129 {
1130  std::string tmp;
1131 
1132  aStream >> tmp;
1133 
1134  if( tmp != "polyset" )
1135  return false;
1136 
1137  aStream >> tmp;
1138 
1139  int n_polys = atoi( tmp.c_str() );
1140 
1141  if( n_polys < 0 )
1142  return false;
1143 
1144  for( int i = 0; i < n_polys; i++ )
1145  {
1146  POLYGON paths;
1147 
1148  aStream >> tmp;
1149 
1150  if( tmp != "poly" )
1151  return false;
1152 
1153  aStream >> tmp;
1154  int n_outlines = atoi( tmp.c_str() );
1155 
1156  if( n_outlines < 0 )
1157  return false;
1158 
1159  for( int j = 0; j < n_outlines; j++ )
1160  {
1161  SHAPE_LINE_CHAIN outline;
1162 
1163  outline.SetClosed( true );
1164 
1165  aStream >> tmp;
1166  int n_vertices = atoi( tmp.c_str() );
1167 
1168  for( int v = 0; v < n_vertices; v++ )
1169  {
1170  VECTOR2I p;
1171 
1172  aStream >> tmp; p.x = atoi( tmp.c_str() );
1173  aStream >> tmp; p.y = atoi( tmp.c_str() );
1174  outline.Append( p );
1175  }
1176 
1177  paths.push_back( outline );
1178  }
1179 
1180  m_polys.push_back( paths );
1181  }
1182 
1183  return true;
1184 }
1185 
1186 
1187 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1188 {
1189  BOX2I bb;
1190 
1191  for( unsigned i = 0; i < m_polys.size(); i++ )
1192  {
1193  if( i == 0 )
1194  bb = m_polys[i][0].BBox();
1195  else
1196  bb.Merge( m_polys[i][0].BBox() );
1197  }
1198 
1199  bb.Inflate( aClearance );
1200  return bb;
1201 }
1202 
1203 
1205 {
1206  BOX2I bb;
1207 
1208  for( unsigned i = 0; i < m_polys.size(); i++ )
1209  {
1210  if( i == 0 )
1211  bb = m_polys[i][0].BBoxFromCache();
1212  else
1213  bb.Merge( m_polys[i][0].BBoxFromCache() );
1214  }
1215 
1216  return bb;
1217 }
1218 
1219 
1220 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1221 {
1222  // Iterate through all the polygons in the set
1223  for( const POLYGON& polygon : m_polys )
1224  {
1225  // Iterate through all the line chains in the polygon
1226  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1227  {
1228  if( lineChain.PointOnEdge( aP ) )
1229  return true;
1230  }
1231  }
1232 
1233  return false;
1234 }
1235 
1236 
1237 bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance, int* aActual,
1238  VECTOR2I* aLocation ) const
1239 {
1240  VECTOR2I nearest;
1241  ecoord dist_sq = SquaredDistance( aSeg, aLocation ? &nearest : nullptr );
1242 
1243  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1244  {
1245  if( aLocation )
1246  *aLocation = nearest;
1247 
1248  if( aActual )
1249  *aActual = sqrt( dist_sq );
1250 
1251  return true;
1252  }
1253 
1254  return false;
1255 }
1256 
1257 
1258 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
1259  VECTOR2I* aLocation ) const
1260 {
1261  VECTOR2I nearest;
1262  ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1263 
1264  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1265  {
1266  if( aLocation )
1267  *aLocation = nearest;
1268 
1269  if( aActual )
1270  *aActual = sqrt( dist_sq );
1271 
1272  return true;
1273  }
1274 
1275  return false;
1276 }
1277 
1278 
1279 bool SHAPE_POLY_SET::Collide( const SHAPE* aShape, int aClearance, int* aActual,
1280  VECTOR2I* aLocation ) const
1281 {
1282  // A couple of simple cases are worth trying before we fall back on triangulation.
1283 
1284  if( aShape->Type() == SH_SEGMENT )
1285  {
1286  const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1287  int extra = segment->GetWidth() / 2;
1288 
1289  if( Collide( segment->GetSeg(), aClearance + extra, aActual, aLocation ) )
1290  {
1291  if( aActual )
1292  *aActual = std::max( 0, *aActual - extra );
1293 
1294  return true;
1295  }
1296 
1297  return false;
1298  }
1299 
1300  if( aShape->Type() == SH_CIRCLE )
1301  {
1302  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1303  int extra = circle->GetRadius();
1304 
1305  if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
1306  {
1307  if( aActual )
1308  *aActual = std::max( 0, *aActual - extra );
1309 
1310  return true;
1311  }
1312 
1313  return false;
1314  }
1315 
1316  const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( true );
1317 
1318  int actual = INT_MAX;
1319  VECTOR2I location;
1320 
1321  for( auto& tpoly : m_triangulatedPolys )
1322  {
1323  for ( auto& tri : tpoly->Triangles() )
1324  {
1325  int triActual;
1326  VECTOR2I triLocation;
1327 
1328  if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1329  {
1330  if( !aActual && !aLocation )
1331  return true;
1332 
1333  if( triActual < actual )
1334  {
1335  actual = triActual;
1336  location = triLocation;
1337  }
1338  }
1339  }
1340  }
1341 
1342  if( actual < INT_MAX )
1343  {
1344  if( aActual )
1345  *aActual = std::max( 0, actual );
1346 
1347  if( aLocation )
1348  *aLocation = location;
1349 
1350  return true;
1351  }
1352 
1353  return false;
1354 }
1355 
1356 
1358 {
1359  m_polys.clear();
1360 }
1361 
1362 
1363 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1364 {
1365  // Default polygon is the last one
1366  if( aPolygonIdx < 0 )
1367  aPolygonIdx += m_polys.size();
1368 
1369  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1370 }
1371 
1372 
1374 {
1375  int removed = 0;
1376 
1377  ITERATOR iterator = IterateWithHoles();
1378 
1379  VECTOR2I contourStart = *iterator;
1380  VECTOR2I segmentStart, segmentEnd;
1381 
1382  VERTEX_INDEX indexStart;
1383 
1384  while( iterator )
1385  {
1386  // Obtain first point and its index
1387  segmentStart = *iterator;
1388  indexStart = iterator.GetIndex();
1389 
1390  // Obtain last point
1391  if( iterator.IsEndContour() )
1392  {
1393  segmentEnd = contourStart;
1394 
1395  // Advance
1396  iterator++;
1397 
1398  if( iterator )
1399  contourStart = *iterator;
1400  }
1401  else
1402  {
1403  // Advance
1404  iterator++;
1405 
1406  if( iterator )
1407  segmentEnd = *iterator;
1408  }
1409 
1410  // Remove segment start if both points are equal
1411  if( segmentStart == segmentEnd )
1412  {
1413  RemoveVertex( indexStart );
1414  removed++;
1415 
1416  // Advance the iterator one position, as there is one vertex less.
1417  if( iterator )
1418  iterator++;
1419  }
1420  }
1421 
1422  return removed;
1423 }
1424 
1425 
1427 {
1428  m_polys.erase( m_polys.begin() + aIdx );
1429 }
1430 
1431 
1433 {
1434  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1435 }
1436 
1437 
1438 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1439 {
1440  Append( aP.x, aP.y, aOutline, aHole );
1441 }
1442 
1443 
1445  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex,
1446  int aClearance ) const
1447 {
1448  // Shows whether there was a collision
1449  bool collision = false;
1450 
1451  // Difference vector between each vertex and aPoint.
1452  VECTOR2D delta;
1453  double distance, clearance;
1454 
1455  // Convert clearance to double for precission when comparing distances
1456  clearance = aClearance;
1457 
1458  for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1459  {
1460  // Get the difference vector between current vertex and aPoint
1461  delta = *iterator - aPoint;
1462 
1463  // Compute distance
1464  distance = delta.EuclideanNorm();
1465 
1466  // Check for collisions
1467  if( distance <= clearance )
1468  {
1469  collision = true;
1470 
1471  // Update aClearance to look for closer vertices
1472  clearance = distance;
1473 
1474  // Store the indices that identify the vertex
1475  aClosestVertex = iterator.GetIndex();
1476  }
1477  }
1478 
1479  return collision;
1480 }
1481 
1482 
1484  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex,
1485  int aClearance ) const
1486 {
1487  // Shows whether there was a collision
1488  bool collision = false;
1489 
1490  for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1491  {
1492  const SEG currentSegment = *iterator;
1493  int distance = currentSegment.Distance( aPoint );
1494 
1495  // Check for collisions
1496  if( distance <= aClearance )
1497  {
1498  collision = true;
1499 
1500  // Update aClearance to look for closer edges
1501  aClearance = distance;
1502 
1503  // Store the indices that identify the vertex
1504  aClosestVertex = iterator.GetIndex();
1505  }
1506  }
1507 
1508  return collision;
1509 }
1510 
1511 
1513 {
1514  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1515  {
1516  Outline( polygonIdx ).GenerateBBoxCache();
1517 
1518  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1519  Hole( polygonIdx, holeIdx ).GenerateBBoxCache();
1520  }
1521 }
1522 
1523 
1524 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1525  bool aUseBBoxCaches ) const
1526 {
1527  if( m_polys.empty() )
1528  return false;
1529 
1530  // If there is a polygon specified, check the condition against that polygon
1531  if( aSubpolyIndex >= 0 )
1532  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1533 
1534  // In any other case, check it against all polygons in the set
1535  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1536  {
1537  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1538  return true;
1539  }
1540 
1541  return false;
1542 }
1543 
1544 
1545 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1546 {
1547  VERTEX_INDEX index;
1548 
1549  // Assure the to be removed vertex exists, abort otherwise
1550  if( GetRelativeIndices( aGlobalIndex, &index ) )
1551  RemoveVertex( index );
1552  else
1553  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1554 }
1555 
1556 
1558 {
1559  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1560 }
1561 
1562 
1563 void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
1564 {
1565  VERTEX_INDEX index;
1566 
1567  if( GetRelativeIndices( aGlobalIndex, &index ) )
1568  SetVertex( index, aPos );
1569  else
1570  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1571 }
1572 
1573 
1574 void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
1575 {
1576  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1577 }
1578 
1579 
1580 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1581  bool aUseBBoxCaches ) const
1582 {
1583  // Check that the point is inside the outline
1584  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1585  {
1586  // Check that the point is not in any of the holes
1587  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1588  {
1589  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1590 
1591  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1592  // here as it's meaning would be inverted.
1593  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1594  return false;
1595  }
1596 
1597  return true;
1598  }
1599 
1600  return false;
1601 }
1602 
1603 
1604 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1605 {
1606  for( POLYGON& poly : m_polys )
1607  {
1608  for( SHAPE_LINE_CHAIN& path : poly )
1609  path.Move( aVector );
1610  }
1611 
1612  for( auto& tri : m_triangulatedPolys )
1613  tri->Move( aVector );
1614 
1615  m_hash = checksum();
1616 }
1617 
1618 
1619 void SHAPE_POLY_SET::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
1620 {
1621  for( POLYGON& poly : m_polys )
1622  {
1623  for( SHAPE_LINE_CHAIN& path : poly )
1624  {
1625  path.Mirror( aX, aY, aRef );
1626  }
1627  }
1628 }
1629 
1630 
1631 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1632 {
1633  for( POLYGON& poly : m_polys )
1634  {
1635  for( SHAPE_LINE_CHAIN& path : poly )
1636  path.Rotate( aAngle, aCenter );
1637  }
1638 
1639  // Don't re-cache if the triangulation is already invalid
1640  if( m_triangulationValid )
1642 }
1643 
1644 
1646 {
1647  int c = 0;
1648 
1649  for( const POLYGON& poly : m_polys )
1650  {
1651  for( const SHAPE_LINE_CHAIN& path : poly )
1652  c += path.PointCount();
1653  }
1654 
1655  return c;
1656 }
1657 
1658 
1659 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1660 {
1661  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1662 }
1663 
1664 
1665 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
1666  int aIndex )
1667 {
1668  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
1669 }
1670 
1671 
1673  VECTOR2I* aNearest ) const
1674 {
1675  // We calculate the min dist between the segment and each outline segment. However, if the
1676  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1677  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1678  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1679  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1680  {
1681  if( aNearest )
1682  *aNearest = aPoint;
1683 
1684  return 0;
1685  }
1686 
1687  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1688 
1689  SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1690 
1691  for( iterator++; iterator && minDistance > 0; iterator++ )
1692  {
1693  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1694 
1695  if( currentDistance < minDistance )
1696  {
1697  if( aNearest )
1698  *aNearest = (*iterator).NearestPoint( aPoint );
1699 
1700  minDistance = currentDistance;
1701  }
1702  }
1703 
1704  return minDistance;
1705 }
1706 
1707 
1708 SEG::ecoord SHAPE_POLY_SET::SquaredDistanceToPolygon( const SEG& aSegment, int aPolygonIndex,
1709  VECTOR2I* aNearest ) const
1710 {
1711  // We calculate the min dist between the segment and each outline segment. However, if the
1712  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1713  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1714  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1715  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) )
1716  {
1717  if( aNearest )
1718  *aNearest = ( aSegment.A + aSegment.B ) / 2;
1719 
1720  return 0;
1721  }
1722 
1723  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1724  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1725 
1726  for( iterator++; iterator && minDistance > 0; iterator++ )
1727  {
1728  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1729 
1730  if( currentDistance < minDistance )
1731  {
1732  if( aNearest )
1733  *aNearest = (*iterator).NearestPoint( aSegment );
1734 
1735  minDistance = currentDistance;
1736  }
1737  }
1738 
1739  // Return the maximum of minDistance and zero
1740  return minDistance < 0 ? 0 : minDistance;
1741 }
1742 
1743 
1745 {
1746  SEG::ecoord currentDistance_sq;
1747  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1748  VECTOR2I nearest;
1749 
1750  // Iterate through all the polygons and get the minimum distance.
1751  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1752  {
1753  currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
1754  aNearest ? &nearest : nullptr );
1755 
1756  if( currentDistance_sq < minDistance_sq )
1757  {
1758  if( aNearest )
1759  *aNearest = nearest;
1760 
1761  minDistance_sq = currentDistance_sq;
1762  }
1763  }
1764 
1765  return minDistance_sq;
1766 }
1767 
1768 
1769 SEG::ecoord SHAPE_POLY_SET::SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest ) const
1770 {
1771  SEG::ecoord currentDistance_sq;
1772  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1773  VECTOR2I nearest;
1774 
1775  // Iterate through all the polygons and get the minimum distance.
1776  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1777  {
1778  currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
1779  aNearest ? &nearest : nullptr );
1780 
1781  if( currentDistance_sq < minDistance_sq )
1782  {
1783  if( aNearest )
1784  *aNearest = nearest;
1785 
1786  minDistance_sq = currentDistance_sq;
1787  }
1788  }
1789 
1790  return minDistance_sq;
1791 }
1792 
1793 
1794 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1795 {
1796  VERTEX_INDEX index;
1797 
1798  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1799  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1800  return false;
1801 
1802  // The contour is a hole if its index is greater than zero
1803  return index.m_contour > 0;
1804 }
1805 
1806 
1808 {
1809  SHAPE_POLY_SET chamfered;
1810 
1811  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1812  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
1813 
1814  return chamfered;
1815 }
1816 
1817 
1818 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
1819 {
1820  SHAPE_POLY_SET filleted;
1821 
1822  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1823  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
1824 
1825  return filleted;
1826 }
1827 
1828 
1830  unsigned int aDistance, int aIndex, int aErrorMax )
1831 {
1832  // Null segments create serious issues in calculations. Remove them:
1834 
1835  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1836  SHAPE_POLY_SET::POLYGON newPoly;
1837 
1838  // If the chamfering distance is zero, then the polygon remain intact.
1839  if( aDistance == 0 )
1840  {
1841  return currentPoly;
1842  }
1843 
1844  // Iterate through all the contours (outline and holes) of the polygon.
1845  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1846  {
1847  // Generate a new contour in the new polygon
1848  SHAPE_LINE_CHAIN newContour;
1849 
1850  // Iterate through the vertices of the contour
1851  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1852  {
1853  // Current vertex
1854  int x1 = currContour.CPoint( currVertex ).x;
1855  int y1 = currContour.CPoint( currVertex ).y;
1856 
1857  // Indices for previous and next vertices.
1858  int prevVertex;
1859  int nextVertex;
1860 
1861  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1862 
1863  // Previous vertex is the last one if the current vertex is the first one
1864  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1865 
1866  // next vertex is the first one if the current vertex is the last one.
1867  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1868 
1869  // Previous vertex computation
1870  double xa = currContour.CPoint( prevVertex ).x - x1;
1871  double ya = currContour.CPoint( prevVertex ).y - y1;
1872 
1873  // Next vertex computation
1874  double xb = currContour.CPoint( nextVertex ).x - x1;
1875  double yb = currContour.CPoint( nextVertex ).y - y1;
1876 
1877  // Compute the new distances
1878  double lena = hypot( xa, ya );
1879  double lenb = hypot( xb, yb );
1880 
1881  // Make the final computations depending on the mode selected, chamfered or filleted.
1882  if( aMode == CORNER_MODE::CHAMFERED )
1883  {
1884  double distance = aDistance;
1885 
1886  // Chamfer one half of an edge at most
1887  if( 0.5 * lena < distance )
1888  distance = 0.5 * lena;
1889 
1890  if( 0.5 * lenb < distance )
1891  distance = 0.5 * lenb;
1892 
1893  int nx1 = KiROUND( distance * xa / lena );
1894  int ny1 = KiROUND( distance * ya / lena );
1895 
1896  newContour.Append( x1 + nx1, y1 + ny1 );
1897 
1898  int nx2 = KiROUND( distance * xb / lenb );
1899  int ny2 = KiROUND( distance * yb / lenb );
1900 
1901  newContour.Append( x1 + nx2, y1 + ny2 );
1902  }
1903  else // CORNER_MODE = FILLETED
1904  {
1905  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1906 
1907  double radius = aDistance;
1908  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1909 
1910  // Do nothing in case of parallel edges
1911  if( std::isinf( denom ) )
1912  continue;
1913 
1914  // Limit rounding distance to one half of an edge
1915  if( 0.5 * lena * denom < radius )
1916  radius = 0.5 * lena * denom;
1917 
1918  if( 0.5 * lenb * denom < radius )
1919  radius = 0.5 * lenb * denom;
1920 
1921  // Calculate fillet arc absolute center point (xc, yx)
1922  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1923  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1924  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1925  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1926  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1927 
1928  // Calculate arc start and end vectors
1929  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1930  double xs = x1 + k * xa / lena - xc;
1931  double ys = y1 + k * ya / lena - yc;
1932  double xe = x1 + k * xb / lenb - xc;
1933  double ye = y1 + k * yb / lenb - yc;
1934 
1935  // Cosine of arc angle
1936  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1937 
1938  // Make sure the argument is in [-1,1], interval in which the acos function is
1939  // defined
1940  if( argument < -1 )
1941  argument = -1;
1942  else if( argument > 1 )
1943  argument = 1;
1944 
1945  double arcAngle = acos( argument );
1946  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1947  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1948 
1949  double deltaAngle = arcAngle / segments;
1950  double startAngle = atan2( -ys, xs );
1951 
1952  // Flip arc for inner corners
1953  if( xa * yb - ya * xb <= 0 )
1954  deltaAngle *= -1;
1955 
1956  double nx = xc + xs;
1957  double ny = yc + ys;
1958 
1959  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1960 
1961  // Store the previous added corner to make a sanity check
1962  int prevX = KiROUND( nx );
1963  int prevY = KiROUND( ny );
1964 
1965  for( int j = 0; j < segments; j++ )
1966  {
1967  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1968  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1969 
1970  // Sanity check: the rounding can produce repeated corners; do not add them.
1971  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1972  {
1973  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1974  prevX = KiROUND( nx );
1975  prevY = KiROUND( ny );
1976  }
1977  }
1978  }
1979  }
1980 
1981  // Close the current contour and add it the new polygon
1982  newContour.SetClosed( true );
1983  newPoly.push_back( newContour );
1984  }
1985 
1986  return newPoly;
1987 }
1988 
1989 
1991 {
1992  static_cast<SHAPE&>(*this) = aOther;
1993  m_polys = aOther.m_polys;
1994  m_triangulatedPolys.clear();
1995  m_triangulationValid = false;
1996 
1997  if( aOther.IsTriangulationUpToDate() )
1998  {
1999  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2000  m_triangulatedPolys.push_back(
2001  std::make_unique<TRIANGULATED_POLYGON>( *aOther.TriangulatedPolygon( i ) ) );
2002 
2003  m_hash = aOther.GetHash();
2004  m_triangulationValid = true;
2005  }
2006 
2007  return *this;
2008 }
2009 
2011 {
2012  if( !m_hash.IsValid() )
2013  return checksum();
2014 
2015  return m_hash;
2016 }
2017 
2018 
2020 {
2021  if( !m_triangulationValid )
2022  return false;
2023 
2024  if( !m_hash.IsValid() )
2025  return false;
2026 
2027  auto hash = checksum();
2028 
2029  return hash == m_hash;
2030 }
2031 
2032 
2034  const SHAPE_POLY_SET& aPoly, int aSize, SHAPE_POLY_SET& aOut )
2035 {
2036  BOX2I bb = aPoly.BBox();
2037 
2038  double w = bb.GetWidth();
2039  double h = bb.GetHeight();
2040 
2041  if( w == 0.0 || h == 0.0 )
2042  return;
2043 
2044  int n_cells_x, n_cells_y;
2045 
2046  if( w > h )
2047  {
2048  n_cells_x = w / aSize;
2049  n_cells_y = floor( h / w * n_cells_x ) + 1;
2050  }
2051  else
2052  {
2053  n_cells_y = h / aSize;
2054  n_cells_x = floor( w / h * n_cells_y ) + 1;
2055  }
2056 
2057  SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2058 
2059  for( int yy = 0; yy < n_cells_y; yy++ )
2060  for( int xx = 0; xx < n_cells_x; xx++ )
2061  {
2062  VECTOR2I p;
2063 
2064  p.x = bb.GetX() + w * xx / n_cells_x;
2065  p.y = bb.GetY() + h * yy / n_cells_y;
2066 
2067  VECTOR2I p2;
2068 
2069  p2.x = bb.GetX() + w * ( xx + 1 ) / n_cells_x;
2070  p2.y = bb.GetY() + h * ( yy + 1 ) / n_cells_y;
2071 
2072 
2073  SHAPE_LINE_CHAIN mask;
2074  mask.Append( VECTOR2I( p.x, p.y ) );
2075  mask.Append( VECTOR2I( p2.x, p.y ) );
2076  mask.Append( VECTOR2I( p2.x, p2.y ) );
2077  mask.Append( VECTOR2I( p.x, p2.y ) );
2078  mask.SetClosed( true );
2079 
2080  if( ( xx ^ yy ) & 1 )
2081  maskSetOdd.AddOutline( mask );
2082  else
2083  maskSetEven.AddOutline( mask );
2084  }
2085 
2086  ps1.BooleanIntersection( maskSetOdd, SHAPE_POLY_SET::PM_FAST );
2087  ps2.BooleanIntersection( maskSetEven, SHAPE_POLY_SET::PM_FAST );
2088  ps1.Fracture( SHAPE_POLY_SET::PM_FAST );
2089  ps2.Fracture( SHAPE_POLY_SET::PM_FAST );
2090 
2091  aOut = ps1;
2092  for( int i = 0; i < ps2.OutlineCount(); i++ )
2093  {
2094  aOut.AddOutline( ps2.COutline( i ) );
2095  }
2096 
2097  if( !aOut.OutlineCount() )
2098  aOut = aPoly;
2099 }
2100 
2101 
2102 void SHAPE_POLY_SET::CacheTriangulation( bool aPartition )
2103 {
2104  bool recalculate = !m_hash.IsValid();
2105  MD5_HASH hash;
2106 
2107  if( !m_triangulationValid )
2108  recalculate = true;
2109 
2110  if( !recalculate )
2111  {
2112  hash = checksum();
2113 
2114  if( m_hash != hash )
2115  {
2116  m_hash = hash;
2117  recalculate = true;
2118  }
2119  }
2120 
2121  if( !recalculate )
2122  return;
2123 
2124  SHAPE_POLY_SET tmpSet;
2125 
2126  if( aPartition )
2127  // This partitions into regularly-sized grids (1cm in pcbnew)
2128  partitionPolyIntoRegularCellGrid( *this, 1e7, tmpSet );
2129  else
2130  {
2131  tmpSet = *this;
2132 
2133  if( tmpSet.HasHoles() )
2134  tmpSet.Fracture( PM_FAST );
2135  }
2136 
2137  m_triangulatedPolys.clear();
2138  m_triangulationValid = true;
2139 
2140  while( tmpSet.OutlineCount() > 0 )
2141  {
2142  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2143  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2144 
2145  // If the tesselation fails, we re-fracture the polygon, which will
2146  // first simplify the system before fracturing and removing the holes
2147  // This may result in multiple, disjoint polygons.
2148  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2149  {
2150  tmpSet.Fracture( PM_FAST );
2151  m_triangulationValid = false;
2152  continue;
2153  }
2154 
2155  tmpSet.DeletePolygon( 0 );
2156  m_triangulationValid = true;
2157  }
2158 
2159  if( m_triangulationValid )
2160  m_hash = checksum();
2161 }
2162 
2163 
2165 {
2166  MD5_HASH hash;
2167 
2168  hash.Hash( m_polys.size() );
2169 
2170  for( const auto& outline : m_polys )
2171  {
2172  hash.Hash( outline.size() );
2173 
2174  for( const auto& lc : outline )
2175  {
2176  hash.Hash( lc.PointCount() );
2177 
2178  for( int i = 0; i < lc.PointCount(); i++ )
2179  {
2180  hash.Hash( lc.CPoint( i ).x );
2181  hash.Hash( lc.CPoint( i ).y );
2182  }
2183  }
2184  }
2185 
2186  hash.Finalize();
2187 
2188  return hash;
2189 }
2190 
2191 
2193 {
2194  for( int i = 0; i < OutlineCount(); i++ )
2195  {
2196  if( hasTouchingHoles( CPolygon( i ) ) )
2197  {
2198  return true;
2199  }
2200  }
2201 
2202  return false;
2203 }
2204 
2205 
2206 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
2207 {
2208  std::set< long long > ptHashes;
2209 
2210  for( const auto& lc : aPoly )
2211  {
2212  for( const VECTOR2I& pt : lc.CPoints() )
2213  {
2214  const long long ptHash = (long long) pt.x << 32 | pt.y;
2215 
2216  if( ptHashes.count( ptHash ) > 0 )
2217  {
2218  return true;
2219  }
2220 
2221  ptHashes.insert( ptHash );
2222  }
2223  }
2224 
2225  return false;
2226 }
2227 
2228 
2230 {
2231  return IsTriangulationUpToDate();
2232 }
2233 
2234 
2236 {
2237  size_t n = 0;
2238 
2239  for( auto& t : m_triangulatedPolys )
2240  n += t->GetTriangleCount();
2241 
2242  return n;
2243 }
2244 
2245 
2246 void SHAPE_POLY_SET:: GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes )
2247 {
2248  aSubshapes.reserve( GetIndexableSubshapeCount() );
2249 
2250  for( auto& tpoly : m_triangulatedPolys )
2251  {
2252  for ( auto& tri : tpoly->Triangles() )
2253  {
2254  SHAPE *s = static_cast<SHAPE*> ( &tri );
2255  aSubshapes.push_back( &tri );
2256  }
2257  }
2258 }
2259 
2260 
2262 {
2263  BOX2I bbox( parent->m_vertices[a] );
2264  bbox.Merge( parent->m_vertices[b] );
2265  bbox.Merge( parent->m_vertices[c] );
2266 
2267  if( aClearance != 0 )
2268  bbox.Inflate( aClearance );
2269 
2270  return bbox;
2271 }
2272 
2273 
2275 {
2276  m_triangles.emplace_back( a, b, c, this );
2277 }
2278 
2279 
2281 {
2282  m_vertices = aOther.m_vertices;
2283  m_triangles = aOther.m_triangles;
2284 
2285  for( TRI& tri : m_triangles )
2286  tri.parent = this;
2287 }
2288 
2289 
2291 {
2292  m_vertices = aOther.m_vertices;
2293  m_triangles = aOther.m_triangles;
2294 
2295  for( TRI& tri : m_triangles )
2296  tri.parent = this;
2297 
2298  return *this;
2299 }
2300 
2301 
2303 {
2304 }
2305 
2306 
2308 {
2309 }
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:126
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
const POLYGON & CPolygon(int aIndex) const
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:207
virtual bool HasIndexableSubshapes() const override
int OutlineCount() const
Returns the number of outlines in the set
All angles are chamfered.
bool IsEndContour() const
Function IsEndContour.
void fractureSingle(POLYGON &paths)
int GetRadius() const
Definition: shape_circle.h:99
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
coord_type GetX() const
Definition: box2.h:190
const BOX2I BBoxFromCaches() const
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 Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:139
VECTOR2I::extended_type ecoord
Definition: seg.h:42
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Returns an iterator object, for the aOutline-th outline in the set (with holes)
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.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
Struct VERTEX_INDEX.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
MD5_HASH checksum() const
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Function Rotate rotates all vertices by a given angle.
const VECTOR2I GetCenter() const
Definition: shape_circle.h:104
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Function Fillet returns a filleted version of the polygon set.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Returns true if a given subpolygon contains the point aP.
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
int PointCount() const
Function PointCount()
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
static SEG::ecoord Square(int a)
Definition: seg.h:116
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Function SquaredDistance computes the minimum distance squared between aPoint and all the polygons in...
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
VERTEX_INDEX GetIndex()
Function GetIndex.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Function Collide()
Definition: shape.h:176
bool IsTriangulationUpToDate() const
const SEG & GetSeg() const
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirrors the line points about y or x (or both)
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.
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
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...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
Function SetVertex Accessor function to set the position of a specific point.
const VECTOR2I & CPoint(int aIndex) const
Function Point()
void SetClosed(bool aClosed)
Function SetClosed()
static constexpr extended_type ECOORD_MAX
Definition: vector2d.h:80
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:65
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &)
Acute angles are rounded.
#define NULL
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
bool IsClosed() const override
Function IsClosed()
SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
coord_type GetWidth() const
Definition: box2.h:197
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Function IsPolygonSelfIntersecting.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Function PointInside()
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
SHAPE.
Definition: shape.h:122
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint.
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:386
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
Acute angles are chamfered.
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
line chain (polyline)
Definition: shape.h:46
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
void BuildBBoxCaches()
Constructs BBoxCaches for Contains(), below.
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:39
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Function Collide()
coord_type GetY() const
Definition: box2.h:191
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
virtual const BOX2I BBox(int aClearance=0) const override
Function BBox()
simple polygon
Definition: shape.h:48
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
void AddTriangle(int a, int b, int c)
const SEG CSegment(int aIndex) const
Function CSegment()
bool matches(int y) const
bool HasTouchingHoles() const
Returns true if the polygon set has any holes tha share a vertex.
ITERATOR IterateWithHoles()
Function IterateWithHoles.
VECTOR2I::extended_type ecoord
Definition: shape.h:125
SHAPE_LINE_CHAIN.
virtual void GetIndexableSubshapes(std::vector< SHAPE * > &aSubshapes) override
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
unsigned int TriangulatedPolyCount() const
Returns the number of triangulated polygons
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Function Fillet returns a filleted version of the aIndex-th polygon.
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
VECTOR2I A
Definition: seg.h:47
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
T rescale(T aNumerator, T aValue, T aDenominator)
Function rescale()
Definition: util.h:95
static bool empty(const wxTextEntryBase *aCtrl)
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:68
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aErrorMax)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
coord_type GetHeight() const
Definition: box2.h:198
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Performs outline inflation/deflation, using round corners.
virtual size_t GetIndexableSubshapeCount() const override
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
void Finalize()
Definition: md5_hash.cpp:75
void CacheTriangulation(bool aPartition=true)
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:299
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 IsValid() const
Definition: md5_hash.h:24
SHAPE * Clone() const override
Function Clone()
FractureEdge(int y=0)
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
int GetWidth() const
const BOX2I BBox(int aClearance=0) const override
Function BBox()
just inflate the polygon. Acute angles create spikes
const TRIANGULATED_POLYGON * TriangulatedPolygon(int aIndex) const
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
SHAPE_TYPE Type() const
Function Type()
Definition: shape.h:98
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
bool operator!=(const PART_LIB &aLibrary, const wxString &aName)
CONST_ITERATOR CIterateWithHoles() const
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...
axis-aligned rectangle
Definition: shape.h:44
bool IsSelfIntersecting() const
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting.
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline)
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
VECTOR2I B
Definition: seg.h:48
void Unfracture(POLYGON_MODE aFastMode)
Converts a single outline slitted ("fractured") polygon into a set ouf outlines with holes.