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