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