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