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