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 ) const
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 
459 {
460  double area = 0.0;
461 
462  for( int i = 0; i < OutlineCount(); i++ )
463  {
464  area += Outline( i ).Area();
465 
466  for( int j = 0; j < HoleCount( i ); j++ )
467  area -= Hole( i, j ).Area();
468  }
469 
470  return area;
471 }
472 
473 
474 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType, const SHAPE_POLY_SET& aOtherShape,
475  POLYGON_MODE aFastMode )
476 {
477  booleanOp( aType, *this, aOtherShape, aFastMode );
478 }
479 
480 
481 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
482  const SHAPE_POLY_SET& aShape,
483  const SHAPE_POLY_SET& aOtherShape,
484  POLYGON_MODE aFastMode )
485 {
486  Clipper c;
487 
488  c.StrictlySimple( aFastMode == PM_STRICTLY_SIMPLE );
489 
490  for( auto poly : aShape.m_polys )
491  {
492  for( size_t i = 0 ; i < poly.size(); i++ )
493  c.AddPath( poly[i].convertToClipper( i == 0 ), ptSubject, true );
494  }
495 
496  for( auto poly : aOtherShape.m_polys )
497  {
498  for( size_t i = 0; i < poly.size(); i++ )
499  c.AddPath( poly[i].convertToClipper( i == 0 ), ptClip, true );
500  }
501 
502  PolyTree solution;
503 
504  c.Execute( aType, solution, pftNonZero, pftNonZero );
505 
506  importTree( &solution );
507 }
508 
509 
511 {
512  booleanOp( ctUnion, b, aFastMode );
513 }
514 
515 
517 {
518  booleanOp( ctDifference, b, aFastMode );
519 }
520 
521 
523 {
524  booleanOp( ctIntersection, b, aFastMode );
525 }
526 
527 
529  const SHAPE_POLY_SET& b,
530  POLYGON_MODE aFastMode )
531 {
532  booleanOp( ctUnion, a, b, aFastMode );
533 }
534 
535 
537  const SHAPE_POLY_SET& b,
538  POLYGON_MODE aFastMode )
539 {
540  booleanOp( ctDifference, a, b, aFastMode );
541 }
542 
543 
545  const SHAPE_POLY_SET& b,
546  POLYGON_MODE aFastMode )
547 {
548  booleanOp( ctIntersection, a, b, aFastMode );
549 }
550 
551 
552 void SHAPE_POLY_SET::InflateWithLinkedHoles( int aFactor, int aCircleSegmentsCount,
553  POLYGON_MODE aFastMode )
554 {
555  Simplify( aFastMode );
556  Inflate( aFactor, aCircleSegmentsCount );
557  Fracture( aFastMode );
558 }
559 
560 
561 void SHAPE_POLY_SET::Inflate( int aAmount, int aCircleSegmentsCount,
562  CORNER_STRATEGY aCornerStrategy )
563 {
564  // A static table to avoid repetitive calculations of the coefficient
565  // 1.0 - cos( M_PI / aCircleSegmentsCount )
566  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
567  #define SEG_CNT_MAX 64
568  static double arc_tolerance_factor[SEG_CNT_MAX + 1];
569 
570  ClipperOffset c;
571 
572  // N.B. see the Clipper documentation for jtSquare/jtMiter/jtRound. They are poorly named
573  // and are not what you'd think they are.
574  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/JoinType.htm
575  JoinType joinType = jtRound; // The way corners are offsetted
576  double miterLimit = 2.0; // Smaller value when using jtMiter for joinType
577  JoinType miterFallback = jtSquare;
578 
579  switch( aCornerStrategy )
580  {
581  case ALLOW_ACUTE_CORNERS:
582  joinType = jtMiter;
583  miterLimit = 10; // Allows large spikes
584  miterFallback = jtSquare;
585  break;
586 
587  case CHAMFER_ACUTE_CORNERS: // Acute angles are chamfered
588  joinType = jtMiter;
589  miterFallback = jtRound;
590  break;
591 
592  case ROUND_ACUTE_CORNERS: // Acute angles are rounded
593  joinType = jtMiter;
594  miterFallback = jtSquare;
595  break;
596 
597  case CHAMFER_ALL_CORNERS: // All angles are chamfered.
598  joinType = jtSquare;
599  miterFallback = jtSquare;
600  break;
601 
602  case ROUND_ALL_CORNERS: // All angles are rounded.
603  joinType = jtRound;
604  miterFallback = jtSquare;
605  break;
606  }
607 
608  for( const POLYGON& poly : m_polys )
609  {
610  for( size_t i = 0; i < poly.size(); i++ )
611  c.AddPath( poly[i].convertToClipper( i == 0 ), joinType, etClosedPolygon );
612  }
613 
614  PolyTree solution;
615 
616  // Calculate the arc tolerance (arc error) from the seg count by circle. The seg count is
617  // nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aAmount))
618  // http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
619 
620  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
621  aCircleSegmentsCount = 6;
622 
623  double coeff;
624 
625  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
626  {
627  coeff = 1.0 - cos( M_PI / aCircleSegmentsCount );
628 
629  if( aCircleSegmentsCount <= SEG_CNT_MAX )
630  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
631  }
632  else
633  coeff = arc_tolerance_factor[aCircleSegmentsCount];
634 
635  c.ArcTolerance = std::abs( aAmount ) * coeff;
636  c.MiterLimit = miterLimit;
637  c.MiterFallback = miterFallback;
638  c.Execute( solution, aAmount );
639 
640  importTree( &solution );
641 }
642 
643 
644 void SHAPE_POLY_SET::importTree( PolyTree* tree )
645 {
646  m_polys.clear();
647 
648  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
649  {
650  if( !n->IsHole() )
651  {
652  POLYGON paths;
653  paths.reserve( n->Childs.size() + 1 );
654  paths.push_back( n->Contour );
655 
656  for( unsigned int i = 0; i < n->Childs.size(); i++ )
657  paths.push_back( n->Childs[i]->Contour );
658 
659  m_polys.push_back( paths );
660  }
661  }
662 }
663 
664 
666 {
667  FractureEdge( int y = 0 ) :
668  m_connected( false ),
669  m_next( NULL )
670  {
671  m_p1.x = m_p2.y = y;
672  }
673 
674  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
675  m_connected( connected ),
676  m_p1( p1 ),
677  m_p2( p2 ),
678  m_next( NULL )
679  {
680  }
681 
682  bool matches( int y ) const
683  {
684  return ( y >= m_p1.y || y >= m_p2.y ) && ( y <= m_p1.y || y <= m_p2.y );
685  }
686 
690 };
691 
692 
693 typedef std::vector<FractureEdge*> FractureEdgeSet;
694 
695 
696 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
697 {
698  int x = edge->m_p1.x;
699  int y = edge->m_p1.y;
700  int min_dist = std::numeric_limits<int>::max();
701  int x_nearest = 0;
702 
703  FractureEdge* e_nearest = NULL;
704 
705  for( FractureEdge* e : edges )
706  {
707  if( !e->matches( y ) )
708  continue;
709 
710  int x_intersect;
711 
712  if( e->m_p1.y == e->m_p2.y ) // horizontal edge
713  {
714  x_intersect = std::max( e->m_p1.x, e->m_p2.x );
715  }
716  else
717  {
718  x_intersect = e->m_p1.x + rescale( e->m_p2.x - e->m_p1.x, y - e->m_p1.y,
719  e->m_p2.y - e->m_p1.y );
720  }
721 
722  int dist = ( x - x_intersect );
723 
724  if( dist >= 0 && dist < min_dist && e->m_connected )
725  {
726  min_dist = dist;
727  x_nearest = x_intersect;
728  e_nearest = e;
729  }
730  }
731 
732  if( e_nearest && e_nearest->m_connected )
733  {
734  int count = 0;
735 
736  FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
737  FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
738  FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
739 
740  edges.push_back( split_2 );
741  edges.push_back( lead1 );
742  edges.push_back( lead2 );
743 
744  FractureEdge* link = e_nearest->m_next;
745 
746  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
747  e_nearest->m_next = lead1;
748  lead1->m_next = edge;
749 
750  FractureEdge* last;
751 
752  for( last = edge; last->m_next != edge; last = last->m_next )
753  {
754  last->m_connected = true;
755  count++;
756  }
757 
758  last->m_connected = true;
759  last->m_next = lead2;
760  lead2->m_next = split_2;
761  split_2->m_next = link;
762 
763  return count + 1;
764  }
765 
766  return 0;
767 }
768 
769 
771 {
772  FractureEdgeSet edges;
773  FractureEdgeSet border_edges;
774  FractureEdge* root = NULL;
775 
776  bool first = true;
777 
778  if( paths.size() == 1 )
779  return;
780 
781  int num_unconnected = 0;
782 
783  for( const SHAPE_LINE_CHAIN& path : paths )
784  {
785  const std::vector<VECTOR2I>& points = path.CPoints();
786  int pointCount = points.size();
787 
788  FractureEdge* prev = NULL, * first_edge = NULL;
789 
790  int x_min = std::numeric_limits<int>::max();
791 
792  for( const VECTOR2I& p : points )
793  {
794  if( p.x < x_min )
795  x_min = p.x;
796  }
797 
798  for( int i = 0; i < pointCount; i++ )
799  {
800  // Do not use path.CPoint() here; open-coding it using the local variables "points"
801  // and "pointCount" gives a non-trivial performance boost to zone fill times.
802  FractureEdge* fe = new FractureEdge( first, points[ i ],
803  points[ i+1 == pointCount ? 0 : i+1 ] );
804 
805  if( !root )
806  root = fe;
807 
808  if( !first_edge )
809  first_edge = fe;
810 
811  if( prev )
812  prev->m_next = fe;
813 
814  if( i == pointCount - 1 )
815  fe->m_next = first_edge;
816 
817  prev = fe;
818  edges.push_back( fe );
819 
820  if( !first )
821  {
822  if( fe->m_p1.x == x_min )
823  border_edges.push_back( fe );
824  }
825 
826  if( !fe->m_connected )
827  num_unconnected++;
828  }
829 
830  first = false; // first path is always the outline
831  }
832 
833  // keep connecting holes to the main outline, until there's no holes left...
834  while( num_unconnected > 0 )
835  {
836  int x_min = std::numeric_limits<int>::max();
837 
838  FractureEdge* smallestX = NULL;
839 
840  // find the left-most hole edge and merge with the outline
841  for( FractureEdge* border_edge : border_edges )
842  {
843  int xt = border_edge->m_p1.x;
844 
845  if( ( xt < x_min ) && !border_edge->m_connected )
846  {
847  x_min = xt;
848  smallestX = border_edge;
849  }
850  }
851 
852  num_unconnected -= processEdge( edges, smallestX );
853  }
854 
855  paths.clear();
856  SHAPE_LINE_CHAIN newPath;
857 
858  newPath.SetClosed( true );
859 
860  FractureEdge* e;
861 
862  for( e = root; e->m_next != root; e = e->m_next )
863  newPath.Append( e->m_p1 );
864 
865  newPath.Append( e->m_p1 );
866 
867  for( FractureEdge* edge : edges )
868  delete edge;
869 
870  paths.push_back( std::move( newPath ) );
871 }
872 
873 
875 {
876  Simplify( aFastMode ); // remove overlapping holes/degeneracy
877 
878  for( POLYGON& paths : m_polys )
879  {
880  fractureSingle( paths );
881  }
882 }
883 
884 
886 {
887  assert( aPoly.size() == 1 );
888 
889  struct EDGE
890  {
891  int m_index = 0;
892  SHAPE_LINE_CHAIN* m_poly = nullptr;
893  bool m_duplicate = false;
894 
895  EDGE( SHAPE_LINE_CHAIN* aPolygon, int aIndex ) :
896  m_index( aIndex ),
897  m_poly( aPolygon )
898  {}
899 
900  bool compareSegs( const SEG& s1, const SEG& s2 ) const
901  {
902  return (s1.A == s2.B && s1.B == s2.A);
903  }
904 
905  bool operator==( const EDGE& aOther ) const
906  {
907  return compareSegs( m_poly->CSegment( m_index ),
908  aOther.m_poly->CSegment( aOther.m_index ) );
909  }
910 
911  bool operator!=( const EDGE& aOther ) const
912  {
913  return !compareSegs( m_poly->CSegment( m_index ),
914  aOther.m_poly->CSegment( aOther.m_index ) );
915  }
916 
917  struct HASH
918  {
919  std::size_t operator()( const EDGE& aEdge ) const
920  {
921  const auto& a = aEdge.m_poly->CSegment( aEdge.m_index );
922 
923  return (std::size_t) ( a.A.x + a.B.x + a.A.y + a.B.y );
924  }
925  };
926  };
927 
928  struct EDGE_LIST_ENTRY
929  {
930  int index;
931  EDGE_LIST_ENTRY* next;
932  };
933 
934  std::unordered_set<EDGE, EDGE::HASH> uniqueEdges;
935 
936  auto lc = aPoly[0];
937  lc.Simplify();
938 
939  auto edgeList = std::make_unique<EDGE_LIST_ENTRY []>( lc.SegmentCount() );
940 
941  for( int i = 0; i < lc.SegmentCount(); i++ )
942  {
943  edgeList[i].index = i;
944  edgeList[i].next = &edgeList[ (i != lc.SegmentCount() - 1) ? i + 1 : 0 ];
945  }
946 
947  std::unordered_set<EDGE_LIST_ENTRY*> queue;
948 
949  for( int i = 0; i < lc.SegmentCount(); i++ )
950  {
951  EDGE e( &lc, i );
952  uniqueEdges.insert( e );
953  }
954 
955  for( int i = 0; i < lc.SegmentCount(); i++ )
956  {
957  EDGE e( &lc, i );
958  auto it = uniqueEdges.find( e );
959 
960  if( it != uniqueEdges.end() && it->m_index != i )
961  {
962  int e1 = it->m_index;
963  int e2 = i;
964 
965  if( e1 > e2 )
966  std::swap( e1, e2 );
967 
968  int e1_prev = e1 - 1;
969 
970  if( e1_prev < 0 )
971  e1_prev = lc.SegmentCount() - 1;
972 
973  int e2_prev = e2 - 1;
974 
975  if( e2_prev < 0 )
976  e2_prev = lc.SegmentCount() - 1;
977 
978  int e1_next = e1 + 1;
979 
980  if( e1_next == lc.SegmentCount() )
981  e1_next = 0;
982 
983  int e2_next = e2 + 1;
984 
985  if( e2_next == lc.SegmentCount() )
986  e2_next = 0;
987 
988  edgeList[e1_prev].next = &edgeList[ e2_next ];
989  edgeList[e2_prev].next = &edgeList[ e1_next ];
990  edgeList[i].next = nullptr;
991  edgeList[it->m_index].next = nullptr;
992  }
993  }
994 
995  for( int i = 0; i < lc.SegmentCount(); i++ )
996  {
997  if( edgeList[i].next )
998  queue.insert( &edgeList[i] );
999  }
1000 
1001  auto edgeBuf = std::make_unique<EDGE_LIST_ENTRY* []>( lc.SegmentCount() );
1002 
1003  int n = 0;
1004  int outline = -1;
1005 
1006  POLYGON result;
1007 
1008  while( queue.size() )
1009  {
1010  auto e_first = (*queue.begin() );
1011  auto e = e_first;
1012  int cnt = 0;
1013 
1014  do {
1015  edgeBuf[cnt++] = e;
1016  e = e->next;
1017  } while( e && e != e_first );
1018 
1019  SHAPE_LINE_CHAIN outl;
1020 
1021  for( int i = 0; i < cnt; i++ )
1022  {
1023  auto p = lc.CPoint( edgeBuf[i]->index );
1024  outl.Append( p );
1025  queue.erase( edgeBuf[i] );
1026  }
1027 
1028  outl.SetClosed( true );
1029 
1030  bool cw = outl.Area() > 0.0;
1031 
1032  if( cw )
1033  outline = n;
1034 
1035  result.push_back( outl );
1036  n++;
1037  }
1038 
1039  if( outline > 0 )
1040  std::swap( result[0], result[outline] );
1041 
1042  aPoly = result;
1043 }
1044 
1045 
1047 {
1048  // Iterate through all the polygons on the set
1049  for( const POLYGON& paths : m_polys )
1050  {
1051  // If any of them has more than one contour, it is a hole.
1052  if( paths.size() > 1 )
1053  return true;
1054  }
1055 
1056  // Return false if and only if every polygon has just one outline, without holes.
1057  return false;
1058 }
1059 
1060 
1062 {
1063  for( POLYGON& path : m_polys )
1064  {
1066  }
1067 
1068  Simplify( aFastMode ); // remove overlapping holes/degeneracy
1069 }
1070 
1071 
1073 {
1075 
1076  booleanOp( ctUnion, empty, aFastMode );
1077 }
1078 
1079 
1081 {
1082  // We are expecting only one main outline, but this main outline can have holes
1083  // if holes: combine holes and remove them from the main outline.
1084  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
1085  // calculations, but it is not mandatory. It is used mainly
1086  // because there is usually only very few vertices in area outlines
1087  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
1088  SHAPE_POLY_SET holesBuffer;
1089 
1090  // Move holes stored in outline to holesBuffer:
1091  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
1092  while( outline.size() > 1 )
1093  {
1094  holesBuffer.AddOutline( outline.back() );
1095  outline.pop_back();
1096  }
1097 
1099 
1100  // If any hole, substract it to main outline
1101  if( holesBuffer.OutlineCount() )
1102  {
1103  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST );
1105  }
1106 
1108 
1109  return OutlineCount();
1110 }
1111 
1112 
1113 const std::string SHAPE_POLY_SET::Format() const
1114 {
1115  std::stringstream ss;
1116 
1117  ss << "SHAPE_LINE_CHAIN poly; \n";
1118 
1119  for( unsigned i = 0; i < m_polys.size(); i++ )
1120  {
1121  for( unsigned j = 0; j < m_polys[i].size(); j++ )
1122  {
1123 
1124  ss << "{ auto tmp = " << m_polys[i][j].Format() << ";\n";
1125 
1126  SHAPE_POLY_SET poly;
1127 
1128  if( j == 0 )
1129  {
1130  ss << " poly.AddOutline(tmp); } \n";
1131  }
1132  else
1133  {
1134  ss << " poly.AddHole(tmp); } \n";
1135  }
1136 
1137  }
1138  }
1139 
1140  return ss.str();
1141 }
1142 
1143 
1144 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
1145 {
1146  std::string tmp;
1147 
1148  aStream >> tmp;
1149 
1150  if( tmp != "polyset" )
1151  return false;
1152 
1153  aStream >> tmp;
1154 
1155  int n_polys = atoi( tmp.c_str() );
1156 
1157  if( n_polys < 0 )
1158  return false;
1159 
1160  for( int i = 0; i < n_polys; i++ )
1161  {
1162  POLYGON paths;
1163 
1164  aStream >> tmp;
1165 
1166  if( tmp != "poly" )
1167  return false;
1168 
1169  aStream >> tmp;
1170  int n_outlines = atoi( tmp.c_str() );
1171 
1172  if( n_outlines < 0 )
1173  return false;
1174 
1175  for( int j = 0; j < n_outlines; j++ )
1176  {
1177  SHAPE_LINE_CHAIN outline;
1178 
1179  outline.SetClosed( true );
1180 
1181  aStream >> tmp;
1182  int n_vertices = atoi( tmp.c_str() );
1183 
1184  for( int v = 0; v < n_vertices; v++ )
1185  {
1186  VECTOR2I p;
1187 
1188  aStream >> tmp; p.x = atoi( tmp.c_str() );
1189  aStream >> tmp; p.y = atoi( tmp.c_str() );
1190  outline.Append( p );
1191  }
1192 
1193  paths.push_back( outline );
1194  }
1195 
1196  m_polys.push_back( paths );
1197  }
1198 
1199  return true;
1200 }
1201 
1202 
1203 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
1204 {
1205  BOX2I bb;
1206 
1207  for( unsigned i = 0; i < m_polys.size(); i++ )
1208  {
1209  if( i == 0 )
1210  bb = m_polys[i][0].BBox();
1211  else
1212  bb.Merge( m_polys[i][0].BBox() );
1213  }
1214 
1215  bb.Inflate( aClearance );
1216  return bb;
1217 }
1218 
1219 
1221 {
1222  BOX2I bb;
1223 
1224  for( unsigned i = 0; i < m_polys.size(); i++ )
1225  {
1226  if( i == 0 )
1227  bb = m_polys[i][0].BBoxFromCache();
1228  else
1229  bb.Merge( m_polys[i][0].BBoxFromCache() );
1230  }
1231 
1232  return bb;
1233 }
1234 
1235 
1236 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1237 {
1238  // Iterate through all the polygons in the set
1239  for( const POLYGON& polygon : m_polys )
1240  {
1241  // Iterate through all the line chains in the polygon
1242  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1243  {
1244  if( lineChain.PointOnEdge( aP ) )
1245  return true;
1246  }
1247  }
1248 
1249  return false;
1250 }
1251 
1252 
1253 bool SHAPE_POLY_SET::Collide( const SEG& aSeg, int aClearance, int* aActual,
1254  VECTOR2I* aLocation ) const
1255 {
1256  VECTOR2I nearest;
1257  ecoord dist_sq = SquaredDistance( aSeg, aLocation ? &nearest : nullptr );
1258 
1259  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1260  {
1261  if( aLocation )
1262  *aLocation = nearest;
1263 
1264  if( aActual )
1265  *aActual = sqrt( dist_sq );
1266 
1267  return true;
1268  }
1269 
1270  return false;
1271 }
1272 
1273 
1274 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance, int* aActual,
1275  VECTOR2I* aLocation ) const
1276 {
1277  VECTOR2I nearest;
1278  ecoord dist_sq = SquaredDistance( aP, aLocation ? &nearest : nullptr );
1279 
1280  if( dist_sq == 0 || dist_sq < SEG::Square( aClearance ) )
1281  {
1282  if( aLocation )
1283  *aLocation = nearest;
1284 
1285  if( aActual )
1286  *aActual = sqrt( dist_sq );
1287 
1288  return true;
1289  }
1290 
1291  return false;
1292 }
1293 
1294 
1295 bool SHAPE_POLY_SET::Collide( const SHAPE* aShape, int aClearance, int* aActual,
1296  VECTOR2I* aLocation ) const
1297 {
1298  // A couple of simple cases are worth trying before we fall back on triangulation.
1299 
1300  if( aShape->Type() == SH_SEGMENT )
1301  {
1302  const SHAPE_SEGMENT* segment = static_cast<const SHAPE_SEGMENT*>( aShape );
1303  int extra = segment->GetWidth() / 2;
1304 
1305  if( Collide( segment->GetSeg(), 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  if( aShape->Type() == SH_CIRCLE )
1317  {
1318  const SHAPE_CIRCLE* circle = static_cast<const SHAPE_CIRCLE*>( aShape );
1319  int extra = circle->GetRadius();
1320 
1321  if( Collide( circle->GetCenter(), aClearance + extra, aActual, aLocation ) )
1322  {
1323  if( aActual )
1324  *aActual = std::max( 0, *aActual - extra );
1325 
1326  return true;
1327  }
1328 
1329  return false;
1330  }
1331 
1332  const_cast<SHAPE_POLY_SET*>( this )->CacheTriangulation( true );
1333 
1334  int actual = INT_MAX;
1335  VECTOR2I location;
1336 
1337  for( const auto& tpoly : m_triangulatedPolys )
1338  {
1339  for ( const auto& tri : tpoly->Triangles() )
1340  {
1341  int triActual;
1342  VECTOR2I triLocation;
1343 
1344  if( aShape->Collide( &tri, aClearance, &triActual, &triLocation ) )
1345  {
1346  if( !aActual && !aLocation )
1347  return true;
1348 
1349  if( triActual < actual )
1350  {
1351  actual = triActual;
1352  location = triLocation;
1353  }
1354  }
1355  }
1356  }
1357 
1358  if( actual < INT_MAX )
1359  {
1360  if( aActual )
1361  *aActual = std::max( 0, actual );
1362 
1363  if( aLocation )
1364  *aLocation = location;
1365 
1366  return true;
1367  }
1368 
1369  return false;
1370 }
1371 
1372 
1374 {
1375  m_polys.clear();
1376 }
1377 
1378 
1379 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1380 {
1381  // Default polygon is the last one
1382  if( aPolygonIdx < 0 )
1383  aPolygonIdx += m_polys.size();
1384 
1385  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1386 }
1387 
1388 
1390 {
1391  int removed = 0;
1392 
1393  ITERATOR iterator = IterateWithHoles();
1394 
1395  VECTOR2I contourStart = *iterator;
1396  VECTOR2I segmentStart, segmentEnd;
1397 
1398  VERTEX_INDEX indexStart;
1399 
1400  while( iterator )
1401  {
1402  // Obtain first point and its index
1403  segmentStart = *iterator;
1404  indexStart = iterator.GetIndex();
1405 
1406  // Obtain last point
1407  if( iterator.IsEndContour() )
1408  {
1409  segmentEnd = contourStart;
1410 
1411  // Advance
1412  iterator++;
1413 
1414  if( iterator )
1415  contourStart = *iterator;
1416  }
1417  else
1418  {
1419  // Advance
1420  iterator++;
1421 
1422  if( iterator )
1423  segmentEnd = *iterator;
1424  }
1425 
1426  // Remove segment start if both points are equal
1427  if( segmentStart == segmentEnd )
1428  {
1429  RemoveVertex( indexStart );
1430  removed++;
1431 
1432  // Advance the iterator one position, as there is one vertex less.
1433  if( iterator )
1434  iterator++;
1435  }
1436  }
1437 
1438  return removed;
1439 }
1440 
1441 
1443 {
1444  m_polys.erase( m_polys.begin() + aIdx );
1445 }
1446 
1447 
1449 {
1450  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1451 }
1452 
1453 
1454 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1455 {
1456  Append( aP.x, aP.y, aOutline, aHole );
1457 }
1458 
1459 
1461  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex,
1462  int aClearance ) const
1463 {
1464  // Shows whether there was a collision
1465  bool collision = false;
1466 
1467  // Difference vector between each vertex and aPoint.
1468  VECTOR2D delta;
1469  double distance, clearance;
1470 
1471  // Convert clearance to double for precission when comparing distances
1472  clearance = aClearance;
1473 
1474  for( CONST_ITERATOR iterator = CIterateWithHoles(); iterator; iterator++ )
1475  {
1476  // Get the difference vector between current vertex and aPoint
1477  delta = *iterator - aPoint;
1478 
1479  // Compute distance
1480  distance = delta.EuclideanNorm();
1481 
1482  // Check for collisions
1483  if( distance <= clearance )
1484  {
1485  collision = true;
1486 
1487  // Update aClearance to look for closer vertices
1488  clearance = distance;
1489 
1490  // Store the indices that identify the vertex
1491  aClosestVertex = iterator.GetIndex();
1492  }
1493  }
1494 
1495  return collision;
1496 }
1497 
1498 
1500  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex,
1501  int aClearance ) const
1502 {
1503  // Shows whether there was a collision
1504  bool collision = false;
1505 
1506  for( CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles(); iterator; iterator++ )
1507  {
1508  const SEG currentSegment = *iterator;
1509  int distance = currentSegment.Distance( aPoint );
1510 
1511  // Check for collisions
1512  if( distance <= aClearance )
1513  {
1514  collision = true;
1515 
1516  // Update aClearance to look for closer edges
1517  aClearance = distance;
1518 
1519  // Store the indices that identify the vertex
1520  aClosestVertex = iterator.GetIndex();
1521  }
1522  }
1523 
1524  return collision;
1525 }
1526 
1527 
1529 {
1530  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1531  {
1532  COutline( polygonIdx ).GenerateBBoxCache();
1533 
1534  for( int holeIdx = 0; holeIdx < HoleCount( polygonIdx ); holeIdx++ )
1535  CHole( polygonIdx, holeIdx ).GenerateBBoxCache();
1536  }
1537 }
1538 
1539 
1540 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1541  bool aUseBBoxCaches ) const
1542 {
1543  if( m_polys.empty() )
1544  return false;
1545 
1546  // If there is a polygon specified, check the condition against that polygon
1547  if( aSubpolyIndex >= 0 )
1548  return containsSingle( aP, aSubpolyIndex, aAccuracy, aUseBBoxCaches );
1549 
1550  // In any other case, check it against all polygons in the set
1551  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1552  {
1553  if( containsSingle( aP, polygonIdx, aAccuracy, aUseBBoxCaches ) )
1554  return true;
1555  }
1556 
1557  return false;
1558 }
1559 
1560 
1561 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1562 {
1563  VERTEX_INDEX index;
1564 
1565  // Assure the to be removed vertex exists, abort otherwise
1566  if( GetRelativeIndices( aGlobalIndex, &index ) )
1567  RemoveVertex( index );
1568  else
1569  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1570 }
1571 
1572 
1574 {
1575  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1576 }
1577 
1578 
1579 void SHAPE_POLY_SET::SetVertex( int aGlobalIndex, const VECTOR2I& aPos )
1580 {
1581  VERTEX_INDEX index;
1582 
1583  if( GetRelativeIndices( aGlobalIndex, &index ) )
1584  SetVertex( index, aPos );
1585  else
1586  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1587 }
1588 
1589 
1590 void SHAPE_POLY_SET::SetVertex( const VERTEX_INDEX& aIndex, const VECTOR2I& aPos )
1591 {
1592  m_polys[aIndex.m_polygon][aIndex.m_contour].SetPoint( aIndex.m_vertex, aPos );
1593 }
1594 
1595 
1596 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex, int aAccuracy,
1597  bool aUseBBoxCaches ) const
1598 {
1599  // Check that the point is inside the outline
1600  if( m_polys[aSubpolyIndex][0].PointInside( aP, aAccuracy ) )
1601  {
1602  // Check that the point is not in any of the holes
1603  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1604  {
1605  const SHAPE_LINE_CHAIN& hole = CHole( aSubpolyIndex, holeIdx );
1606 
1607  // If the point is inside a hole it is outside of the polygon. Do not use aAccuracy
1608  // here as it's meaning would be inverted.
1609  if( hole.PointInside( aP, 1, aUseBBoxCaches ) )
1610  return false;
1611  }
1612 
1613  return true;
1614  }
1615 
1616  return false;
1617 }
1618 
1619 
1620 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1621 {
1622  for( POLYGON& poly : m_polys )
1623  {
1624  for( SHAPE_LINE_CHAIN& path : poly )
1625  path.Move( aVector );
1626  }
1627 
1628  for( std::unique_ptr<TRIANGULATED_POLYGON>& tri : m_triangulatedPolys )
1629  tri->Move( aVector );
1630 
1631  m_hash = checksum();
1632 }
1633 
1634 
1635 void SHAPE_POLY_SET::Mirror( bool aX, bool aY, const VECTOR2I& aRef )
1636 {
1637  for( POLYGON& poly : m_polys )
1638  {
1639  for( SHAPE_LINE_CHAIN& path : poly )
1640  path.Mirror( aX, aY, aRef );
1641  }
1642 
1643  if( m_triangulationValid )
1645 }
1646 
1647 
1648 void SHAPE_POLY_SET::Rotate( double aAngle, const VECTOR2I& aCenter )
1649 {
1650  for( POLYGON& poly : m_polys )
1651  {
1652  for( SHAPE_LINE_CHAIN& path : poly )
1653  path.Rotate( aAngle, aCenter );
1654  }
1655 
1656  // Don't re-cache if the triangulation is already invalid
1657  if( m_triangulationValid )
1659 }
1660 
1661 
1663 {
1664  int c = 0;
1665 
1666  for( const POLYGON& poly : m_polys )
1667  {
1668  for( const SHAPE_LINE_CHAIN& path : poly )
1669  c += path.PointCount();
1670  }
1671 
1672  return c;
1673 }
1674 
1675 
1676 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1677 {
1678  return chamferFilletPolygon( CHAMFERED, aDistance, aIndex, 0 );
1679 }
1680 
1681 
1682 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::FilletPolygon( unsigned int aRadius, int aErrorMax,
1683  int aIndex )
1684 {
1685  return chamferFilletPolygon( FILLETED, aRadius, aIndex, aErrorMax );
1686 }
1687 
1688 
1690  VECTOR2I* aNearest ) const
1691 {
1692  // We calculate the min dist between the segment and each outline segment. However, if the
1693  // segment to test is inside the outline, and does not cross any edge, it can be seen outside
1694  // the polygon. Therefore test if a segment end is inside (testing only one end is enough).
1695  // Use an accuracy of "1" to say that we don't care if it's exactly on the edge or not.
1696  if( containsSingle( aPoint, aPolygonIndex, 1 ) )
1697  {
1698  if( aNearest )
1699  *aNearest = aPoint;
1700 
1701  return 0;
1702  }
1703 
1704  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1705 
1706  SEG::ecoord minDistance = (*iterator).SquaredDistance( aPoint );
1707 
1708  for( iterator++; iterator && minDistance > 0; iterator++ )
1709  {
1710  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aPoint );
1711 
1712  if( currentDistance < minDistance )
1713  {
1714  if( aNearest )
1715  *aNearest = (*iterator).NearestPoint( aPoint );
1716 
1717  minDistance = currentDistance;
1718  }
1719  }
1720 
1721  return minDistance;
1722 }
1723 
1724 
1725 SEG::ecoord SHAPE_POLY_SET::SquaredDistanceToPolygon( const SEG& aSegment, int aPolygonIndex,
1726  VECTOR2I* aNearest ) const
1727 {
1728  // Check if the segment is fully-contained. If so, its midpoint is a good-enough nearest point.
1729  if( containsSingle( aSegment.A, aPolygonIndex, 1 ) &&
1730  containsSingle( aSegment.B, aPolygonIndex, 1 ) )
1731  {
1732  if( aNearest )
1733  *aNearest = ( aSegment.A + aSegment.B ) / 2;
1734 
1735  return 0;
1736  }
1737 
1738  CONST_SEGMENT_ITERATOR iterator = CIterateSegmentsWithHoles( aPolygonIndex );
1739  SEG::ecoord minDistance = (*iterator).SquaredDistance( aSegment );
1740 
1741  if( aNearest && minDistance == 0 )
1742  *aNearest = ( *iterator ).NearestPoint( aSegment );
1743 
1744  for( iterator++; iterator && minDistance > 0; iterator++ )
1745  {
1746  SEG::ecoord currentDistance = (*iterator).SquaredDistance( aSegment );
1747 
1748  if( currentDistance < minDistance )
1749  {
1750  if( aNearest )
1751  *aNearest = (*iterator).NearestPoint( aSegment );
1752 
1753  minDistance = currentDistance;
1754  }
1755  }
1756 
1757  // Return the maximum of minDistance and zero
1758  return minDistance < 0 ? 0 : minDistance;
1759 }
1760 
1761 
1763 {
1764  SEG::ecoord currentDistance_sq;
1765  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1766  VECTOR2I nearest;
1767 
1768  // Iterate through all the polygons and get the minimum distance.
1769  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1770  {
1771  currentDistance_sq = SquaredDistanceToPolygon( aPoint, polygonIdx,
1772  aNearest ? &nearest : nullptr );
1773 
1774  if( currentDistance_sq < minDistance_sq )
1775  {
1776  if( aNearest )
1777  *aNearest = nearest;
1778 
1779  minDistance_sq = currentDistance_sq;
1780  }
1781  }
1782 
1783  return minDistance_sq;
1784 }
1785 
1786 
1787 SEG::ecoord SHAPE_POLY_SET::SquaredDistance( const SEG& aSegment, VECTOR2I* aNearest ) const
1788 {
1789  SEG::ecoord currentDistance_sq;
1790  SEG::ecoord minDistance_sq = VECTOR2I::ECOORD_MAX;
1791  VECTOR2I nearest;
1792 
1793  // Iterate through all the polygons and get the minimum distance.
1794  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1795  {
1796  currentDistance_sq = SquaredDistanceToPolygon( aSegment, polygonIdx,
1797  aNearest ? &nearest : nullptr );
1798 
1799  if( currentDistance_sq < minDistance_sq )
1800  {
1801  if( aNearest )
1802  *aNearest = nearest;
1803 
1804  minDistance_sq = currentDistance_sq;
1805  }
1806  }
1807 
1808  return minDistance_sq;
1809 }
1810 
1811 
1812 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1813 {
1814  VERTEX_INDEX index;
1815 
1816  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1817  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1818  return false;
1819 
1820  // The contour is a hole if its index is greater than zero
1821  return index.m_contour > 0;
1822 }
1823 
1824 
1826 {
1827  SHAPE_POLY_SET chamfered;
1828 
1829  for( unsigned int idx = 0; idx < m_polys.size(); idx++ )
1830  chamfered.m_polys.push_back( ChamferPolygon( aDistance, idx ) );
1831 
1832  return chamfered;
1833 }
1834 
1835 
1836 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aErrorMax )
1837 {
1838  SHAPE_POLY_SET filleted;
1839 
1840  for( size_t idx = 0; idx < m_polys.size(); idx++ )
1841  filleted.m_polys.push_back( FilletPolygon( aRadius, aErrorMax, idx ) );
1842 
1843  return filleted;
1844 }
1845 
1846 
1848  unsigned int aDistance, int aIndex, int aErrorMax )
1849 {
1850  // Null segments create serious issues in calculations. Remove them:
1852 
1853  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1854  SHAPE_POLY_SET::POLYGON newPoly;
1855 
1856  // If the chamfering distance is zero, then the polygon remain intact.
1857  if( aDistance == 0 )
1858  {
1859  return currentPoly;
1860  }
1861 
1862  // Iterate through all the contours (outline and holes) of the polygon.
1863  for( SHAPE_LINE_CHAIN& currContour : currentPoly )
1864  {
1865  // Generate a new contour in the new polygon
1866  SHAPE_LINE_CHAIN newContour;
1867 
1868  // Iterate through the vertices of the contour
1869  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1870  {
1871  // Current vertex
1872  int x1 = currContour.CPoint( currVertex ).x;
1873  int y1 = currContour.CPoint( currVertex ).y;
1874 
1875  // Indices for previous and next vertices.
1876  int prevVertex;
1877  int nextVertex;
1878 
1879  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1880 
1881  // Previous vertex is the last one if the current vertex is the first one
1882  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1883 
1884  // next vertex is the first one if the current vertex is the last one.
1885  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1886 
1887  // Previous vertex computation
1888  double xa = currContour.CPoint( prevVertex ).x - x1;
1889  double ya = currContour.CPoint( prevVertex ).y - y1;
1890 
1891  // Next vertex computation
1892  double xb = currContour.CPoint( nextVertex ).x - x1;
1893  double yb = currContour.CPoint( nextVertex ).y - y1;
1894 
1895  // Compute the new distances
1896  double lena = hypot( xa, ya );
1897  double lenb = hypot( xb, yb );
1898 
1899  // Make the final computations depending on the mode selected, chamfered or filleted.
1900  if( aMode == CORNER_MODE::CHAMFERED )
1901  {
1902  double distance = aDistance;
1903 
1904  // Chamfer one half of an edge at most
1905  if( 0.5 * lena < distance )
1906  distance = 0.5 * lena;
1907 
1908  if( 0.5 * lenb < distance )
1909  distance = 0.5 * lenb;
1910 
1911  int nx1 = KiROUND( distance * xa / lena );
1912  int ny1 = KiROUND( distance * ya / lena );
1913 
1914  newContour.Append( x1 + nx1, y1 + ny1 );
1915 
1916  int nx2 = KiROUND( distance * xb / lenb );
1917  int ny2 = KiROUND( distance * yb / lenb );
1918 
1919  newContour.Append( x1 + nx2, y1 + ny2 );
1920  }
1921  else // CORNER_MODE = FILLETED
1922  {
1923  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1924 
1925  double radius = aDistance;
1926  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1927 
1928  // Do nothing in case of parallel edges
1929  if( std::isinf( denom ) )
1930  continue;
1931 
1932  // Limit rounding distance to one half of an edge
1933  if( 0.5 * lena * denom < radius )
1934  radius = 0.5 * lena * denom;
1935 
1936  if( 0.5 * lenb * denom < radius )
1937  radius = 0.5 * lenb * denom;
1938 
1939  // Calculate fillet arc absolute center point (xc, yx)
1940  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1941  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1942  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1943  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1944  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1945 
1946  // Calculate arc start and end vectors
1947  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1948  double xs = x1 + k * xa / lena - xc;
1949  double ys = y1 + k * ya / lena - yc;
1950  double xe = x1 + k * xb / lenb - xc;
1951  double ye = y1 + k * yb / lenb - yc;
1952 
1953  // Cosine of arc angle
1954  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1955 
1956  // Make sure the argument is in [-1,1], interval in which the acos function is
1957  // defined
1958  if( argument < -1 )
1959  argument = -1;
1960  else if( argument > 1 )
1961  argument = 1;
1962 
1963  double arcAngle = acos( argument );
1964  double arcAngleDegrees = arcAngle * 180.0 / M_PI;
1965  int segments = GetArcToSegmentCount( radius, aErrorMax, arcAngleDegrees );
1966 
1967  double deltaAngle = arcAngle / segments;
1968  double startAngle = atan2( -ys, xs );
1969 
1970  // Flip arc for inner corners
1971  if( xa * yb - ya * xb <= 0 )
1972  deltaAngle *= -1;
1973 
1974  double nx = xc + xs;
1975  double ny = yc + ys;
1976 
1977  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1978 
1979  // Store the previous added corner to make a sanity check
1980  int prevX = KiROUND( nx );
1981  int prevY = KiROUND( ny );
1982 
1983  for( int j = 0; j < segments; j++ )
1984  {
1985  nx = xc + cos( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1986  ny = yc - sin( startAngle + ( j + 1 ) * deltaAngle ) * radius;
1987 
1988  // Sanity check: the rounding can produce repeated corners; do not add them.
1989  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1990  {
1991  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1992  prevX = KiROUND( nx );
1993  prevY = KiROUND( ny );
1994  }
1995  }
1996  }
1997  }
1998 
1999  // Close the current contour and add it the new polygon
2000  newContour.SetClosed( true );
2001  newPoly.push_back( newContour );
2002  }
2003 
2004  return newPoly;
2005 }
2006 
2007 
2009 {
2010  static_cast<SHAPE&>(*this) = aOther;
2011  m_polys = aOther.m_polys;
2012  m_triangulatedPolys.clear();
2013  m_triangulationValid = false;
2014 
2015  if( aOther.IsTriangulationUpToDate() )
2016  {
2017  for( unsigned i = 0; i < aOther.TriangulatedPolyCount(); i++ )
2018  {
2019  const TRIANGULATED_POLYGON* poly = aOther.TriangulatedPolygon( i );
2020  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>( *poly ) );
2021  }
2022 
2023  m_hash = aOther.GetHash();
2024  m_triangulationValid = true;
2025  }
2026 
2027  return *this;
2028 }
2029 
2031 {
2032  if( !m_hash.IsValid() )
2033  return checksum();
2034 
2035  return m_hash;
2036 }
2037 
2038 
2040 {
2041  if( !m_triangulationValid )
2042  return false;
2043 
2044  if( !m_hash.IsValid() )
2045  return false;
2046 
2047  MD5_HASH hash = checksum();
2048 
2049  return hash == m_hash;
2050 }
2051 
2052 
2053 static void partitionPolyIntoRegularCellGrid( const SHAPE_POLY_SET& aPoly, int aSize,
2054  SHAPE_POLY_SET& aOut )
2055 {
2056  BOX2I bb = aPoly.BBox();
2057 
2058  double w = bb.GetWidth();
2059  double h = bb.GetHeight();
2060 
2061  if( w == 0.0 || h == 0.0 )
2062  return;
2063 
2064  int n_cells_x, n_cells_y;
2065 
2066  if( w > h )
2067  {
2068  n_cells_x = w / aSize;
2069  n_cells_y = floor( h / w * n_cells_x ) + 1;
2070  }
2071  else
2072  {
2073  n_cells_y = h / aSize;
2074  n_cells_x = floor( w / h * n_cells_y ) + 1;
2075  }
2076 
2077  SHAPE_POLY_SET ps1( aPoly ), ps2( aPoly ), maskSetOdd, maskSetEven;
2078 
2079  for( int yy = 0; yy < n_cells_y; yy++ )
2080  {
2081  for( int xx = 0; xx < n_cells_x; xx++ )
2082  {
2083  VECTOR2I p;
2084 
2085  p.x = bb.GetX() + w * xx / n_cells_x;
2086  p.y = bb.GetY() + h * yy / n_cells_y;
2087 
2088  VECTOR2I p2;
2089 
2090  p2.x = bb.GetX() + w * ( xx + 1 ) / n_cells_x;
2091  p2.y = bb.GetY() + h * ( yy + 1 ) / n_cells_y;
2092 
2093 
2094  SHAPE_LINE_CHAIN mask;
2095  mask.Append( VECTOR2I( p.x, p.y ) );
2096  mask.Append( VECTOR2I( p2.x, p.y ) );
2097  mask.Append( VECTOR2I( p2.x, p2.y ) );
2098  mask.Append( VECTOR2I( p.x, p2.y ) );
2099  mask.SetClosed( true );
2100 
2101  if( ( xx ^ yy ) & 1 )
2102  maskSetOdd.AddOutline( mask );
2103  else
2104  maskSetEven.AddOutline( mask );
2105  }
2106  }
2107 
2108  ps1.BooleanIntersection( maskSetOdd, SHAPE_POLY_SET::PM_FAST );
2109  ps2.BooleanIntersection( maskSetEven, SHAPE_POLY_SET::PM_FAST );
2110  ps1.Fracture( SHAPE_POLY_SET::PM_FAST );
2111  ps2.Fracture( SHAPE_POLY_SET::PM_FAST );
2112 
2113  aOut = ps1;
2114 
2115  for( int i = 0; i < ps2.OutlineCount(); i++ )
2116  aOut.AddOutline( ps2.COutline( i ) );
2117 
2118  if( !aOut.OutlineCount() )
2119  aOut = aPoly;
2120 }
2121 
2122 
2123 void SHAPE_POLY_SET::CacheTriangulation( bool aPartition )
2124 {
2125  bool recalculate = !m_hash.IsValid();
2126  MD5_HASH hash;
2127 
2128  if( !m_triangulationValid )
2129  recalculate = true;
2130 
2131  if( !recalculate )
2132  {
2133  hash = checksum();
2134 
2135  if( m_hash != hash )
2136  {
2137  m_hash = hash;
2138  recalculate = true;
2139  }
2140  }
2141 
2142  if( !recalculate )
2143  return;
2144 
2145  SHAPE_POLY_SET tmpSet;
2146 
2147  if( aPartition )
2148  {
2149  // This partitions into regularly-sized grids (1cm in pcbnew)
2150  partitionPolyIntoRegularCellGrid( *this, 1e7, tmpSet );
2151  }
2152  else
2153  {
2154  tmpSet = *this;
2155 
2156  if( tmpSet.HasHoles() )
2157  tmpSet.Fracture( PM_FAST );
2158  }
2159 
2160  m_triangulatedPolys.clear();
2161  m_triangulationValid = false;
2162 
2163  while( tmpSet.OutlineCount() > 0 )
2164  {
2165  m_triangulatedPolys.push_back( std::make_unique<TRIANGULATED_POLYGON>() );
2166  PolygonTriangulation tess( *m_triangulatedPolys.back() );
2167 
2168  // If the tesselation fails, we re-fracture the polygon, which will
2169  // first simplify the system before fracturing and removing the holes
2170  // This may result in multiple, disjoint polygons.
2171  if( !tess.TesselatePolygon( tmpSet.Polygon( 0 ).front() ) )
2172  {
2173  tmpSet.Fracture( PM_FAST );
2174  m_triangulationValid = false;
2175  continue;
2176  }
2177 
2178  tmpSet.DeletePolygon( 0 );
2179  m_triangulationValid = true;
2180  }
2181 
2182  if( m_triangulationValid )
2183  m_hash = checksum();
2184 }
2185 
2186 
2188 {
2189  MD5_HASH hash;
2190 
2191  hash.Hash( m_polys.size() );
2192 
2193  for( const auto& outline : m_polys )
2194  {
2195  hash.Hash( outline.size() );
2196 
2197  for( const auto& lc : outline )
2198  {
2199  hash.Hash( lc.PointCount() );
2200 
2201  for( int i = 0; i < lc.PointCount(); i++ )
2202  {
2203  hash.Hash( lc.CPoint( i ).x );
2204  hash.Hash( lc.CPoint( i ).y );
2205  }
2206  }
2207  }
2208 
2209  hash.Finalize();
2210 
2211  return hash;
2212 }
2213 
2214 
2216 {
2217  for( int i = 0; i < OutlineCount(); i++ )
2218  {
2219  if( hasTouchingHoles( CPolygon( i ) ) )
2220  {
2221  return true;
2222  }
2223  }
2224 
2225  return false;
2226 }
2227 
2228 
2229 bool SHAPE_POLY_SET::hasTouchingHoles( const POLYGON& aPoly ) const
2230 {
2231  std::set< long long > ptHashes;
2232 
2233  for( const auto& lc : aPoly )
2234  {
2235  for( const VECTOR2I& pt : lc.CPoints() )
2236  {
2237  const long long ptHash = (long long) pt.x << 32 | pt.y;
2238 
2239  if( ptHashes.count( ptHash ) > 0 )
2240  {
2241  return true;
2242  }
2243 
2244  ptHashes.insert( ptHash );
2245  }
2246  }
2247 
2248  return false;
2249 }
2250 
2251 
2253 {
2254  return IsTriangulationUpToDate();
2255 }
2256 
2257 
2259 {
2260  size_t n = 0;
2261 
2262  for( auto& t : m_triangulatedPolys )
2263  n += t->GetTriangleCount();
2264 
2265  return n;
2266 }
2267 
2268 
2269 void SHAPE_POLY_SET:: GetIndexableSubshapes( std::vector<SHAPE*>& aSubshapes )
2270 {
2271  aSubshapes.reserve( GetIndexableSubshapeCount() );
2272 
2273  for( auto& tpoly : m_triangulatedPolys )
2274  {
2275  for ( auto& tri : tpoly->Triangles() )
2276  {
2277  aSubshapes.push_back( &tri );
2278  }
2279  }
2280 }
2281 
2282 
2284 {
2285  BOX2I bbox( parent->m_vertices[a] );
2286  bbox.Merge( parent->m_vertices[b] );
2287  bbox.Merge( parent->m_vertices[c] );
2288 
2289  if( aClearance != 0 )
2290  bbox.Inflate( aClearance );
2291 
2292  return bbox;
2293 }
2294 
2295 
2297 {
2298  m_triangles.emplace_back( a, b, c, this );
2299 }
2300 
2301 
2303 {
2304  m_vertices = aOther.m_vertices;
2305  m_triangles = aOther.m_triangles;
2306 
2307  for( TRI& tri : m_triangles )
2308  tri.parent = this;
2309 }
2310 
2311 
2313 {
2314  m_vertices = aOther.m_vertices;
2315  m_triangles = aOther.m_triangles;
2316 
2317  for( TRI& tri : m_triangles )
2318  tri.parent = this;
2319 
2320  return *this;
2321 }
2322 
2323 
2325 {
2326 }
2327 
2328 
2330 {
2331 }
int TotalVertices() const
Delete aIdx-th polygon from 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)
This is the engine to execute all polygon boolean transforms (AND, OR, ...
CITER next(CITER it)
Definition: ptree.cpp:126
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
const POLYGON & CPolygon(int aIndex) const
int Distance(const SEG &aSeg) const
Compute minimum Euclidean distance to segment aSeg.
Definition: seg.h:239
virtual bool HasIndexableSubshapes() const override
int OutlineCount() const
Return the number of vertices in a given outline/hole.
All angles are chamfered.
void fractureSingle(POLYGON &paths)
int GetRadius() const
Definition: shape_circle.h:107
void unfractureSingle(POLYGON &path)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference 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
Return the aGlobalIndex-th vertex in the poly set.
bool Collide(const SEG &aSeg, int aClearance, int *aActual=nullptr) const
Definition: seg.cpp:172
VECTOR2I::extended_type ecoord
Definition: seg.h:44
CONST_SEGMENT_ITERATOR CIterateSegmentsWithHoles() const
Return an iterator object, for the aOutline-th outline in the set (with holes).
int NormalizeAreaOutlines()
Convert a self-intersecting polygon to one (or more) non self-intersecting polygon(s).
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of holes in a given outline.
bool Parse(std::stringstream &aStream) override
bool HasHoles() const
Return true if the polygon set has any holes that share a vertex.
CORNER_STRATEGY
< define how inflate transform build inflated polygon
Structure to hold the necessary information in order to index a vertex on a SHAPE_POLY_SET object: th...
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
double Area()
Appends a vertex at the end of the given outline/hole (default: the last outline)
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
MD5_HASH checksum() const
Base class for iterating over all segments in a given SHAPE_POLY_SET.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
const VECTOR2I GetCenter() const
Definition: shape_circle.h:112
SHAPE_POLY_SET Fillet(int aRadius, int aErrorMax)
Return a filleted version of the polygon set.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1, int aAccuracy=0, bool aUseBBoxCaches=false) const
Return true if a given subpolygon contains the point aP.
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Perform outline inflation/deflation.
bool operator==(const PART_LIB &aLibrary, const wxString &aName)
Case insensitive library name comparison.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
int PointCount() const
Function PointCount()
std::vector< std::unique_ptr< TRIANGULATED_POLYGON > > m_triangulatedPolys
static SEG::ecoord Square(int a)
Definition: seg.h:123
SEG::ecoord SquaredDistance(VECTOR2I aPoint, VECTOR2I *aNearest=nullptr) const
Compute the minimum distance squared between aPoint and all the polygons in the set.
bool PointOnEdge(const VECTOR2I &aP) const
Check if point aP lies on an edge or vertex of some of the outlines or holes.
virtual bool Collide(const VECTOR2I &aP, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const
Check if the boundary of shape (this) lies closer to the point aP than aClearance,...
Definition: shape.h:165
bool IsTriangulationUpToDate() const
void BuildBBoxCaches() const
Construct BBoxCaches for Contains(), below.
const SEG & GetSeg() const
void Mirror(bool aX=true, bool aY=false, const VECTOR2I &aRef={ 0, 0 })
Mirror the line points about y or x (or both)
bool hasTouchingHoles(const POLYGON &aPoly) const
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
#define SEG_CNT_MAX
bool IsVertexInHole(int aGlobalIdx)
Check whether the aGlobalIndex-th vertex belongs to a hole.
void DeletePolygon(int aIdx)
static void partitionPolyIntoRegularCellGrid(const SHAPE_POLY_SET &aPoly, int aSize, SHAPE_POLY_SET &aOut)
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Return the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a cont...
void SetVertex(const VERTEX_INDEX &aIndex, const VECTOR2I &aPos)
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:79
void Hash(uint8_t *data, uint32_t length)
Definition: md5_hash.cpp:65
Acute angles are rounded.
#define NULL
MD5_HASH GetHash() const
void Move(const VECTOR2I &aVector) override
bool IsClosed() const override
Function IsClosed()
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
coord_type GetWidth() const
Definition: box2.h:197
bool IsPolygonSelfIntersecting(int aPolygonIndex) const
Check whether the aPolygonIndex-th polygon in the set is self intersecting.
bool PointInside(const VECTOR2I &aPt, int aAccuracy=0, bool aUseBBoxCache=false) const
Check if point aP lies inside a polygon (any type) defined by the line chain.
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
An abstract shape on 2D plane.
Definition: shape.h:116
SEG::ecoord SquaredDistanceToPolygon(VECTOR2I aPoint, int aIndex, VECTOR2I *aNearest) const
Compute the minimum distance between the aIndex-th polygon and aPoint.
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)
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()
Look for null segments; ie, segments whose ends are exactly the same and deletes them.
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Convert a global vertex index —i.e., a number that globally identifies a vertex in a concatenated lis...
int NewOutline()
Creates a new hole in a given outline.
int HoleCount(int aOutline) const
Return the reference to aIndex-th outline in the set.
Acute angles are chamfered.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Return the area of this poly set.
circle
Definition: shape.h:46
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex)
Return a chamfered version of the aIndex-th polygon.
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
Definition: seg.h:41
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new hole to the given outline (default: last) and returns its index.
bool Collide(const SHAPE *aShape, int aClearance=0, int *aActual=nullptr, VECTOR2I *aLocation=nullptr) const override
Check if the boundary of shape (this) lies closer to the shape aShape than aClearance,...
coord_type GetY() const
Definition: box2.h:191
CORNER_MODE
Operation ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this ...
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any edge of any of the contours of the polygon.
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:302
virtual const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
set of polygons (with holes, etc.)
Definition: shape.h:48
TRIANGULATED_POLYGON & operator=(const TRIANGULATED_POLYGON &aOther)
SHAPE_POLY_SET Chamfer(int aDistance)
Return a chamfered version of the polygon set.
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx) const
Compute the global index of a vertex from the relative indices of polygon, contour and vertex.
void AddTriangle(int a, int b, int c)
const SEG CSegment(int aIndex) const
Function CSegment()
bool matches(int y) const
bool HasTouchingHoles() const
Simplify the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFastMo...
ITERATOR IterateWithHoles()
VECTOR2I::extended_type ecoord
Definition: shape.h:236
SHAPE_LINE_CHAIN.
virtual void GetIndexableSubshapes(std::vector< SHAPE * > &aSubshapes) override
const SHAPE_LINE_CHAIN & COutline(int aIndex) const
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Delete the aGlobalIndex-th vertex.
Base class for iterating over all vertices in a given SHAPE_POLY_SET.
unsigned int TriangulatedPolyCount() const
Return the number of outlines in the set.
POLYGON FilletPolygon(unsigned int aRadius, int aErrorMax, int aIndex)
Return a filleted version of the aIndex-th polygon.
VECTOR2I A
Definition: seg.h:49
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)
Return the chamfered or filleted version of the aIndex-th polygon in the set, depending on the aMode ...
coord_type GetHeight() const
Definition: box2.h:198
void InflateWithLinkedHoles(int aFactor, int aCircleSegmentsCount, POLYGON_MODE aFastMode)
Perform outline inflation/deflation, using round corners.
virtual size_t GetIndexableSubshapeCount() const override
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Adds a vertex in the globally indexed position aGlobalIndex.
void Finalize()
Definition: md5_hash.cpp:75
void CacheTriangulation(bool aPartition=true)
void GenerateBBoxCache() const
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
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)
Perform boolean polyset intersection For aFastMode meaning, see function booleanOp.
POLYGON & Polygon(int aIndex)
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther) const
bool IsValid() const
Definition: md5_hash.h:24
SHAPE * Clone() const override
Return a dynamically allocated copy of the shape.
FractureEdge(int y=0)
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex, int aAccuracy, bool aUseBBoxCaches=false) const
Check whether the point aP is inside the aSubpolyIndex-th polygon of the polyset.
int GetWidth() const
const BOX2I BBox(int aClearance=0) const override
Compute a bounding box of the shape, with a margin of aClearance a collision.
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
Return the type of the shape.
Definition: shape.h:94
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0) const
Check whether aPoint collides with any vertex of any of the contours of the polygon.
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)
Return a subset of the polygons in this set, the ones between aFirstPolygon and aLastPolygon.
line segment
Definition: shape.h:44
bool IsSelfIntersecting() const
Check whether any of the polygons in the set is self intersecting.
SHAPE_POLY_SET & operator=(const SHAPE_POLY_SET &aOther)
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Delete the aContourIdx-th contour of the aPolygonIdx-th polygon in the set.
void importTree(ClipperLib::PolyTree *tree)
VECTOR2I B
Definition: seg.h:50
void Unfracture(POLYGON_MODE aFastMode)
Return true if the polygon set has any holes.