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-2017 CERN
5  * @author Tomasz Wlostowski <tomasz.wlostowski@cern.ch>
6  * @author Alejandro GarcĂ­a Montoro <alejandro.garciamontoro@gmail.com>
7  *
8  * Point in polygon algorithm adapted from Clipper Library (C) Angus Johnson,
9  * subject to Clipper library license.
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, you may find one here:
23  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
24  * or you may search the http://www.gnu.org website for the version 2 license,
25  * or you may write to the Free Software Foundation, Inc.,
26  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
27  */
28 
29 
30 #include <vector>
31 #include <cstdio>
32 #include <set>
33 #include <list>
34 #include <algorithm>
35 
36 #include <common.h>
37 
38 #include <geometry/shape.h>
41 
42 using namespace ClipperLib;
43 
46 {
47 }
48 
49 
51  SHAPE( SH_POLY_SET ), m_polys( aOther.m_polys )
52 {
53 }
54 
55 
57 {
58 }
59 
60 
62 {
63  return new SHAPE_POLY_SET( *this );
64 }
65 
66 
68  SHAPE_POLY_SET::VERTEX_INDEX* aRelativeIndices ) const
69 {
70  int polygonIdx = 0;
71  unsigned int contourIdx = 0;
72  int vertexIdx = 0;
73 
74  int currentGlobalIdx = 0;
75 
76  for( polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
77  {
78  const POLYGON currentPolygon = CPolygon( polygonIdx );
79 
80  for( contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
81  {
82  SHAPE_LINE_CHAIN currentContour = currentPolygon[contourIdx];
83  int totalPoints = currentContour.PointCount();
84 
85  for( vertexIdx = 0; vertexIdx < totalPoints; vertexIdx++ )
86  {
87  // Check if the current vertex is the globally indexed as aGlobalIdx
88  if( currentGlobalIdx == aGlobalIdx )
89  {
90  aRelativeIndices->m_polygon = polygonIdx;
91  aRelativeIndices->m_contour = contourIdx;
92  aRelativeIndices->m_vertex = vertexIdx;
93 
94  return true;
95  }
96 
97  // Advance
98  currentGlobalIdx++;
99  }
100  }
101  }
102 
103  return false;
104 }
105 
106 
108  int& aGlobalIdx )
109 {
110  int selectedVertex = aRelativeIndices.m_vertex;
111  unsigned int selectedContour = aRelativeIndices.m_contour;
112  unsigned int selectedPolygon = aRelativeIndices.m_polygon;
113 
114  // Check whether the vertex indices make sense in this poly set
115  if( selectedPolygon < m_polys.size() && selectedContour < m_polys[selectedPolygon].size() &&
116  selectedVertex < m_polys[selectedPolygon][selectedContour].PointCount() )
117  {
118  POLYGON currentPolygon;
119 
120  aGlobalIdx = 0;
121 
122  for( unsigned int polygonIdx = 0; polygonIdx < selectedPolygon; polygonIdx++ )
123  {
124  currentPolygon = Polygon( polygonIdx );
125 
126  for( unsigned int contourIdx = 0; contourIdx < currentPolygon.size(); contourIdx++ )
127  {
128  aGlobalIdx += currentPolygon[contourIdx].PointCount();
129  }
130  }
131 
132  currentPolygon = Polygon( selectedPolygon );
133 
134  for( unsigned int contourIdx = 0; contourIdx < selectedContour; contourIdx ++ )
135  {
136  aGlobalIdx += currentPolygon[contourIdx].PointCount();
137  }
138 
139  aGlobalIdx += selectedVertex;
140 
141  return true;
142  }
143  else
144  {
145  return false;
146  }
147 }
148 
149 
151 {
152  SHAPE_LINE_CHAIN empty_path;
153  POLYGON poly;
154  empty_path.SetClosed( true );
155  poly.push_back( empty_path );
156  m_polys.push_back( poly );
157  return m_polys.size() - 1;
158 }
159 
160 
161 int SHAPE_POLY_SET::NewHole( int aOutline )
162 {
163  SHAPE_LINE_CHAIN empty_path;
164  empty_path.SetClosed( true );
165 
166  // Default outline is the last one
167  if( aOutline < 0 )
168  aOutline += m_polys.size();
169 
170  // Add hole to the selected outline
171  m_polys[aOutline].push_back( empty_path );
172 
173  return m_polys.back().size() - 2;
174 }
175 
176 
177 int SHAPE_POLY_SET::Append( int x, int y, int aOutline, int aHole, bool aAllowDuplication )
178 {
179  if( aOutline < 0 )
180  aOutline += m_polys.size();
181 
182  int idx;
183 
184  if( aHole < 0 )
185  idx = 0;
186  else
187  idx = aHole + 1;
188 
189  assert( aOutline < (int)m_polys.size() );
190  assert( idx < (int)m_polys[aOutline].size() );
191 
192  m_polys[aOutline][idx].Append( x, y, aAllowDuplication );
193 
194  return m_polys[aOutline][idx].PointCount();
195 }
196 
197 
198 void SHAPE_POLY_SET::InsertVertex( int aGlobalIndex, VECTOR2I aNewVertex )
199 {
200  VERTEX_INDEX index;
201 
202  if( aGlobalIndex < 0 )
203  aGlobalIndex = 0;
204 
205  if( aGlobalIndex >= TotalVertices() ){
206  Append( aNewVertex );
207  }
208  else
209  {
210  // Assure the position to be inserted exists; throw an exception otherwise
211  if( GetRelativeIndices( aGlobalIndex, &index ) )
212  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
213  else
214  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
215  }
216 
217 }
218 
219 
220 int SHAPE_POLY_SET::VertexCount( int aOutline , int aHole ) const
221 {
222  if( aOutline < 0 )
223  aOutline += m_polys.size();
224 
225  int idx;
226 
227  if( aHole < 0 )
228  idx = 0;
229  else
230  idx = aHole + 1;
231 
232  assert ( aOutline < (int)m_polys.size() );
233  assert ( idx < (int)m_polys[aOutline].size() );
234 
235  return m_polys[aOutline][idx].PointCount();
236 }
237 
238 
239 SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
240 {
241  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
242 
243  SHAPE_POLY_SET newPolySet;
244 
245  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
246  {
247  newPolySet.m_polys.push_back( Polygon( index ) );
248  }
249 
250  return newPolySet;
251 }
252 
253 
254 VECTOR2I& SHAPE_POLY_SET::Vertex( int aIndex, int aOutline, int aHole )
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  return m_polys[aOutline][idx].Point( aIndex );
270 }
271 
272 
273 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
274 {
275  if( aOutline < 0 )
276  aOutline += m_polys.size();
277 
278  int idx;
279 
280  if( aHole < 0 )
281  idx = 0;
282  else
283  idx = aHole + 1;
284 
285  assert( aOutline < (int)m_polys.size() );
286  assert( idx < (int)m_polys[aOutline].size() );
287 
288  return m_polys[aOutline][idx].CPoint( aIndex );
289 }
290 
291 
292 VECTOR2I& SHAPE_POLY_SET::Vertex( int aGlobalIndex )
293 {
295 
296  // Assure the passed index references a legal position; abort otherwise
297  if( !GetRelativeIndices( aGlobalIndex, &index ) )
298  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
299 
300  return m_polys[index.m_polygon][index.m_contour].Point( index.m_vertex );
301 }
302 
303 
304 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
305 {
307 
308  // Assure the passed index references a legal position; abort otherwise
309  if( !GetRelativeIndices( aGlobalIndex, &index ) )
310  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
311 
312  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
313 }
314 
315 
317 {
318  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
319 }
320 
321 
323 {
324  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
325 }
326 
327 
328 SEG SHAPE_POLY_SET::Edge( int aGlobalIndex )
329 {
331 
332  // If the edge does not exist, throw an exception, it is an illegal access memory error
333  if( !GetRelativeIndices( aGlobalIndex, &indices ) )
334  throw( std::out_of_range( "aGlobalIndex-th edge does not exist" ) );
335 
336  return m_polys[indices.m_polygon][indices.m_contour].Segment( indices.m_vertex );
337 }
338 
339 
341 {
342  // Get polygon
343  const POLYGON poly = CPolygon( aPolygonIndex );
344 
345  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
346  SEGMENT_ITERATOR innerIterator;
347 
348  for( iterator = IterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
349  {
350  SEG firstSegment = *iterator;
351 
352  // Iterate through all remaining segments.
353  innerIterator = iterator;
354 
355  // Start in the next segment, we don't want to check collision between a segment and itself
356  for( innerIterator++; innerIterator; innerIterator++ )
357  {
358  SEG secondSegment = *innerIterator;
359 
360  // Check whether the two segments built collide, only when they are not adjacent.
361  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
362  return true;
363  }
364  }
365 
366  return false;
367 }
368 
369 
371 {
372  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
373  {
374  if( IsPolygonSelfIntersecting( polygon ) )
375  return true;
376  }
377 
378  return false;
379 }
380 
381 
383 {
384  assert( aOutline.IsClosed() );
385 
386  POLYGON poly;
387 
388  poly.push_back( aOutline );
389 
390  m_polys.push_back( poly );
391 
392  return m_polys.size() - 1;
393 }
394 
395 
396 int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
397 {
398  assert ( m_polys.size() );
399 
400  if( aOutline < 0 )
401  aOutline += m_polys.size();
402 
403  POLYGON& poly = m_polys[aOutline];
404 
405  assert( poly.size() );
406 
407  poly.push_back( aHole );
408 
409  return poly.size() - 1;
410 }
411 
412 
413 const Path SHAPE_POLY_SET::convertToClipper( const SHAPE_LINE_CHAIN& aPath, bool aRequiredOrientation )
414 {
415  Path c_path;
416 
417  for( int i = 0; i < aPath.PointCount(); i++ )
418  {
419  const VECTOR2I& vertex = aPath.CPoint( i );
420  c_path.push_back( IntPoint( vertex.x, vertex.y ) );
421  }
422 
423  if( Orientation( c_path ) != aRequiredOrientation )
424  ReversePath( c_path );
425 
426  return c_path;
427 }
428 
429 
431 {
432  SHAPE_LINE_CHAIN lc;
433 
434  for( unsigned int i = 0; i < aPath.size(); i++ )
435  lc.Append( aPath[i].X, aPath[i].Y );
436 
437  lc.SetClosed( true );
438 
439  return lc;
440 }
441 
442 
443 void SHAPE_POLY_SET::booleanOp( ClipType aType, const SHAPE_POLY_SET& aOtherShape,
444  POLYGON_MODE aFastMode )
445 {
446  Clipper c;
447 
448  if( aFastMode == PM_STRICTLY_SIMPLE )
449  c.StrictlySimple( true );
450 
451  for( const POLYGON& poly : m_polys )
452  {
453  for( unsigned int i = 0; i < poly.size(); i++ )
454  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
455  }
456 
457  for( const POLYGON& poly : aOtherShape.m_polys )
458  {
459  for( unsigned int i = 0; i < poly.size(); i++ )
460  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
461  }
462 
463  PolyTree solution;
464 
465  c.Execute( aType, solution, pftNonZero, pftNonZero );
466 
467  importTree( &solution );
468 }
469 
470 
471 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
472  const SHAPE_POLY_SET& aShape,
473  const SHAPE_POLY_SET& aOtherShape,
474  POLYGON_MODE aFastMode )
475 {
476  Clipper c;
477 
478  if( aFastMode == PM_STRICTLY_SIMPLE )
479  c.StrictlySimple( true );
480 
481  for( const POLYGON& poly : aShape.m_polys )
482  {
483  for( unsigned int i = 0; i < poly.size(); i++ )
484  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
485  }
486 
487  for( const POLYGON& poly : aOtherShape.m_polys )
488  {
489  for( unsigned int i = 0; i < poly.size(); i++ )
490  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
491  }
492 
493  PolyTree solution;
494 
495  c.Execute( aType, solution, pftNonZero, pftNonZero );
496 
497  importTree( &solution );
498 }
499 
500 
502 {
503  booleanOp( ctUnion, b, aFastMode );
504 }
505 
506 
508 {
509  booleanOp( ctDifference, b, aFastMode );
510 }
511 
512 
514 {
515  booleanOp( ctIntersection, b, aFastMode );
516 }
517 
518 
520 {
521  booleanOp( ctUnion, a, b, aFastMode );
522 }
523 
524 
526 {
527  booleanOp( ctDifference, a, b, aFastMode );
528 }
529 
530 
532 {
533  booleanOp( ctIntersection, a, b, aFastMode );
534 }
535 
536 
537 void SHAPE_POLY_SET::Inflate( int aFactor, int aCircleSegmentsCount )
538 {
539  // A static table to avoid repetitive calculations of the coefficient
540  // 1.0 - cos( M_PI/aCircleSegmentsCount)
541  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
542  #define SEG_CNT_MAX 64
543  static double arc_tolerance_factor[SEG_CNT_MAX+1];
544 
545  ClipperOffset c;
546 
547  for( const POLYGON& poly : m_polys )
548  {
549  for( unsigned int i = 0; i < poly.size(); i++ )
550  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), jtRound, etClosedPolygon );
551  }
552 
553  PolyTree solution;
554 
555  // Calculate the arc tolerance (arc error) from the seg count by circle.
556  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
557  // see:
558  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
559 
560  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
561  aCircleSegmentsCount = 6;
562 
563  double coeff;
564 
565  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
566  {
567  coeff = 1.0 - cos( M_PI/aCircleSegmentsCount);
568 
569  if( aCircleSegmentsCount <= SEG_CNT_MAX )
570  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
571  }
572  else
573  coeff = arc_tolerance_factor[aCircleSegmentsCount];
574 
575  c.ArcTolerance = std::abs( aFactor ) * coeff;
576 
577  c.Execute( solution, aFactor );
578 
579  importTree( &solution );
580 }
581 
582 
583 void SHAPE_POLY_SET::importTree( PolyTree* tree )
584 {
585  m_polys.clear();
586 
587  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
588  {
589  if( !n->IsHole() )
590  {
591  POLYGON paths;
592  paths.reserve( n->Childs.size() + 1 );
593  paths.push_back( convertFromClipper( n->Contour ) );
594 
595  for( unsigned int i = 0; i < n->Childs.size(); i++ )
596  paths.push_back( convertFromClipper( n->Childs[i]->Contour ) );
597 
598  m_polys.push_back( paths );
599  }
600  }
601 }
602 
603 // Polygon fracturing code. Work in progress.
604 
606 {
607  FractureEdge( bool connected, SHAPE_LINE_CHAIN* owner, int index ) :
608  m_connected( connected ),
609  m_next( NULL )
610  {
611  m_p1 = owner->CPoint( index );
612  m_p2 = owner->CPoint( index + 1 );
613  }
614 
615  FractureEdge( int y = 0 ) :
616  m_connected( false ),
617  m_next( NULL )
618  {
619  m_p1.x = m_p2.y = y;
620  }
621 
622  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
623  m_connected( connected ),
624  m_p1( p1 ),
625  m_p2( p2 ),
626  m_next( NULL )
627  {
628  }
629 
630  bool matches( int y ) const
631  {
632  int y_min = std::min( m_p1.y, m_p2.y );
633  int y_max = std::max( m_p1.y, m_p2.y );
634 
635  return ( y >= y_min ) && ( y <= y_max );
636  }
637 
641 };
642 
643 
644 typedef std::vector<FractureEdge*> FractureEdgeSet;
645 
646 
647 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
648 {
649  int x = edge->m_p1.x;
650  int y = edge->m_p1.y;
651  int min_dist = std::numeric_limits<int>::max();
652  int x_nearest = 0;
653 
654  FractureEdge* e_nearest = NULL;
655 
656  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
657  {
658  if( !(*i)->matches( y ) )
659  continue;
660 
661  int x_intersect;
662 
663  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
664  x_intersect = std::max ( (*i)->m_p1.x, (*i)->m_p2.x );
665  else
666  x_intersect = (*i)->m_p1.x + rescale((*i)->m_p2.x - (*i)->m_p1.x, y - (*i)->m_p1.y, (*i)->m_p2.y - (*i)->m_p1.y );
667 
668  int dist = ( x - x_intersect );
669 
670  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
671  {
672  min_dist = dist;
673  x_nearest = x_intersect;
674  e_nearest = (*i);
675  }
676  }
677 
678  if( e_nearest && e_nearest->m_connected )
679  {
680  int count = 0;
681 
682  FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
683  FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
684  FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
685 
686  edges.push_back( split_2 );
687  edges.push_back( lead1 );
688  edges.push_back( lead2 );
689 
690  FractureEdge* link = e_nearest->m_next;
691 
692  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
693  e_nearest->m_next = lead1;
694  lead1->m_next = edge;
695 
696  FractureEdge*last;
697  for( last = edge; last->m_next != edge; last = last->m_next )
698  {
699  last->m_connected = true;
700  count++;
701  }
702 
703  last->m_connected = true;
704  last->m_next = lead2;
705  lead2->m_next = split_2;
706  split_2->m_next = link;
707 
708  return count + 1;
709  }
710 
711  return 0;
712 }
713 
714 
716 {
717  FractureEdgeSet edges;
718  FractureEdgeSet border_edges;
719  FractureEdge* root = NULL;
720 
721  bool first = true;
722 
723  if( paths.size() == 1 )
724  return;
725 
726  int num_unconnected = 0;
727 
728  for( SHAPE_LINE_CHAIN& path : paths )
729  {
730  int index = 0;
731 
732  FractureEdge *prev = NULL, *first_edge = NULL;
733 
734  int x_min = std::numeric_limits<int>::max();
735 
736  for( int i = 0; i < path.PointCount(); i++ )
737  {
738  const VECTOR2I& p = path.CPoint( i );
739 
740  if( p.x < x_min )
741  x_min = p.x;
742  }
743 
744  for( int i = 0; i < path.PointCount(); i++ )
745  {
746  FractureEdge* fe = new FractureEdge( first, &path, index++ );
747 
748  if( !root )
749  root = fe;
750 
751  if( !first_edge )
752  first_edge = fe;
753 
754  if( prev )
755  prev->m_next = fe;
756 
757  if( i == path.PointCount() - 1 )
758  fe->m_next = first_edge;
759 
760  prev = fe;
761  edges.push_back( fe );
762 
763  if( !first )
764  {
765  if( fe->m_p1.x == x_min )
766  border_edges.push_back( fe );
767  }
768 
769  if( !fe->m_connected )
770  num_unconnected++;
771  }
772  first = false; // first path is always the outline
773  }
774 
775  // keep connecting holes to the main outline, until there's no holes left...
776  while( num_unconnected > 0 )
777  {
778  int x_min = std::numeric_limits<int>::max();
779 
780  FractureEdge* smallestX = NULL;
781 
782  // find the left-most hole edge and merge with the outline
783  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
784  {
785  int xt = (*i)->m_p1.x;
786 
787  if( ( xt < x_min ) && ! (*i)->m_connected )
788  {
789  x_min = xt;
790  smallestX = *i;
791  }
792  }
793 
794  num_unconnected -= processEdge( edges, smallestX );
795  }
796 
797  paths.clear();
798  SHAPE_LINE_CHAIN newPath;
799 
800  newPath.SetClosed( true );
801 
802  FractureEdge* e;
803 
804  for( e = root; e->m_next != root; e = e->m_next )
805  newPath.Append( e->m_p1 );
806 
807  newPath.Append( e->m_p1 );
808 
809  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
810  delete *i;
811 
812  paths.push_back( newPath );
813 }
814 
815 
817 {
818  Simplify( aFastMode ); // remove overlapping holes/degeneracy
819 
820  for( POLYGON& paths : m_polys )
821  {
822  fractureSingle( paths );
823  }
824 }
825 
826 
828 {
829  // Iterate through all the polygons on the set
830  for( const POLYGON& paths : m_polys )
831  {
832  // If any of them has more than one contour, it is a hole.
833  if( paths.size() > 1 )
834  return true;
835  }
836 
837  // Return false if and only if every polygon has just one outline, without holes.
838  return false;
839 }
840 
841 
843 {
845 
846  booleanOp( ctUnion, empty, aFastMode );
847 }
848 
849 
851 {
852  // We are expecting only one main outline, but this main outline can have holes
853  // if holes: combine holes and remove them from the main outline.
854  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
855  // calculations, but it is not mandatory. It is used mainly
856  // because there is usually only very few vertices in area outlines
857  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
858  SHAPE_POLY_SET holesBuffer;
859 
860  // Move holes stored in outline to holesBuffer:
861  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
862  while( outline.size() > 1 )
863  {
864  holesBuffer.AddOutline( outline.back() );
865  outline.pop_back();
866  }
867 
869 
870  // If any hole, substract it to main outline
871  if( holesBuffer.OutlineCount() )
872  {
873  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST);
875  }
876 
878 
879  return OutlineCount();
880 }
881 
882 
883 const std::string SHAPE_POLY_SET::Format() const
884 {
885  std::stringstream ss;
886 
887  ss << "polyset " << m_polys.size() << "\n";
888 
889  for( unsigned i = 0; i < m_polys.size(); i++ )
890  {
891  ss << "poly " << m_polys[i].size() << "\n";
892  for( unsigned j = 0; j < m_polys[i].size(); j++ )
893  {
894  ss << m_polys[i][j].PointCount() << "\n";
895  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
896  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
897  }
898  ss << "\n";
899  }
900 
901  return ss.str();
902 }
903 
904 
905 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
906 {
907  std::string tmp;
908 
909  aStream >> tmp;
910 
911  if( tmp != "polyset" )
912  return false;
913 
914  aStream >> tmp;
915 
916  int n_polys = atoi( tmp.c_str() );
917 
918  if( n_polys < 0 )
919  return false;
920 
921  for( int i = 0; i < n_polys; i++ )
922  {
923  POLYGON paths;
924 
925  aStream >> tmp;
926 
927  if( tmp != "poly" )
928  return false;
929 
930  aStream >> tmp;
931  int n_outlines = atoi( tmp.c_str() );
932 
933  if( n_outlines < 0 )
934  return false;
935 
936  for( int j = 0; j < n_outlines; j++ )
937  {
938  SHAPE_LINE_CHAIN outline;
939 
940  outline.SetClosed( true );
941 
942  aStream >> tmp;
943  int n_vertices = atoi( tmp.c_str() );
944  for( int v = 0; v < n_vertices; v++ )
945  {
946  VECTOR2I p;
947 
948  aStream >> tmp; p.x = atoi( tmp.c_str() );
949  aStream >> tmp; p.y = atoi( tmp.c_str() );
950  outline.Append( p );
951  }
952 
953  paths.push_back( outline );
954  }
955 
956  m_polys.push_back( paths );
957  }
958  return true;
959 }
960 
961 
962 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
963 {
964  BOX2I bb;
965 
966  for( unsigned i = 0; i < m_polys.size(); i++ )
967  {
968  if( i == 0 )
969  bb = m_polys[i][0].BBox();
970  else
971  bb.Merge( m_polys[i][0].BBox() );
972  }
973 
974  bb.Inflate( aClearance );
975  return bb;
976 }
977 
978 
979 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
980 {
981  // Iterate through all the polygons in the set
982  for( const POLYGON& polygon : m_polys )
983  {
984  // Iterate through all the line chains in the polygon
985  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
986  {
987  if( lineChain.PointOnEdge( aP ) )
988  return true;
989  }
990  }
991 
992  return false;
993 }
994 
995 
996 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
997 {
998  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
999 
1000  // Inflate the polygon if necessary.
1001  if( aClearance > 0 )
1002  {
1003  // fixme: the number of arc segments should not be hardcoded
1004  polySet.Inflate( aClearance, 8 );
1005  }
1006 
1007  // There is a collision if and only if the point is inside of the polygon.
1008  return polySet.Contains( aP );
1009 }
1010 
1011 
1013 {
1014  m_polys.clear();
1015 }
1016 
1017 
1018 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1019 {
1020  // Default polygon is the last one
1021  if( aPolygonIdx < 0 )
1022  aPolygonIdx += m_polys.size();
1023 
1024  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1025 }
1026 
1027 
1029 {
1030  int removed = 0;
1031 
1032  ITERATOR iterator = IterateWithHoles();
1033 
1034  VECTOR2I contourStart = *iterator;
1035  VECTOR2I segmentStart, segmentEnd;
1036 
1037  VERTEX_INDEX indexStart;
1038 
1039  while( iterator )
1040  {
1041  // Obtain first point and its index
1042  segmentStart = *iterator;
1043  indexStart = iterator.GetIndex();
1044 
1045  // Obtain last point
1046  if( iterator.IsEndContour() )
1047  {
1048  segmentEnd = contourStart;
1049 
1050  // Advance
1051  iterator++;
1052 
1053  if( iterator )
1054  contourStart = *iterator;
1055  }
1056  else
1057  {
1058  // Advance
1059  iterator++;
1060 
1061  if( iterator )
1062  segmentEnd = *iterator;
1063  }
1064 
1065  // Remove segment start if both points are equal
1066  if( segmentStart == segmentEnd )
1067  {
1068  RemoveVertex( indexStart );
1069  removed++;
1070 
1071  // Advance the iterator one position, as there is one vertex less.
1072  if( iterator )
1073  iterator++;
1074  }
1075  }
1076 
1077  return removed;
1078 }
1079 
1080 
1082 {
1083  m_polys.erase( m_polys.begin() + aIdx );
1084 }
1085 
1086 
1088 {
1089  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1090 }
1091 
1092 
1093 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1094 {
1095  Append( aP.x, aP.y, aOutline, aHole );
1096 }
1097 
1098 
1100  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1101 {
1102  // Shows whether there was a collision
1103  bool collision = false;
1104 
1105  // Difference vector between each vertex and aPoint.
1106  VECTOR2D delta;
1107  double distance, clearance;
1108 
1109  // Convert clearance to double for precission when comparing distances
1110  clearance = aClearance;
1111 
1112  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1113  {
1114  // Get the difference vector between current vertex and aPoint
1115  delta = *iterator - aPoint;
1116 
1117  // Compute distance
1118  distance = delta.EuclideanNorm();
1119 
1120  // Check for collisions
1121  if( distance <= clearance )
1122  {
1123  collision = true;
1124 
1125  // Update aClearance to look for closer vertices
1126  clearance = distance;
1127 
1128  // Store the indices that identify the vertex
1129  aClosestVertex = iterator.GetIndex();
1130  }
1131  }
1132 
1133  return collision;
1134 }
1135 
1136 
1138  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1139 {
1140  // Shows whether there was a collision
1141  bool collision = false;
1142 
1143  SEGMENT_ITERATOR iterator;
1144 
1145  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1146  {
1147  SEG currentSegment = *iterator;
1148  int distance = currentSegment.Distance( aPoint );
1149 
1150  // Check for collisions
1151  if( distance <= aClearance )
1152  {
1153  collision = true;
1154 
1155  // Update aClearance to look for closer edges
1156  aClearance = distance;
1157 
1158  // Store the indices that identify the vertex
1159  aClosestVertex = iterator.GetIndex();
1160  }
1161  }
1162 
1163  return collision;
1164 }
1165 
1166 
1167 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex ) const
1168 {
1169  if( m_polys.size() == 0 ) // empty set?
1170  return false;
1171 
1172  // If there is a polygon specified, check the condition against that polygon
1173  if( aSubpolyIndex >= 0 )
1174  return containsSingle( aP, aSubpolyIndex );
1175 
1176  // In any other case, check it against all polygons in the set
1177  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1178  {
1179  if( containsSingle( aP, polygonIdx ) )
1180  return true;
1181  }
1182 
1183  return false;
1184 
1185 }
1186 
1187 
1188 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1189 {
1190  VERTEX_INDEX index;
1191 
1192  // Assure the to be removed vertex exists, abort otherwise
1193  if( GetRelativeIndices( aGlobalIndex, &index ) )
1194  RemoveVertex( index );
1195  else
1196  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1197 }
1198 
1199 
1201 {
1202  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1203 }
1204 
1205 
1206 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex ) const
1207 {
1208  // Check that the point is inside the outline
1209  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1210  {
1211  // Check that the point is not in any of the holes
1212  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1213  {
1214  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1215  // If the point is inside a hole (and not on its edge),
1216  // it is outside of the polygon
1217  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1218  return false;
1219  }
1220 
1221  return true;
1222  }
1223 
1224  return false;
1225 }
1226 
1227 
1228 bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
1229 {
1230  int result = 0;
1231  int cnt = aPath.PointCount();
1232 
1233  if ( !aPath.BBox().Contains( aP ) ) // test with bounding box first
1234  return false;
1235 
1236  if( cnt < 3 )
1237  return false;
1238 
1239  VECTOR2I ip = aPath.CPoint( 0 );
1240 
1241  for( int i = 1; i <= cnt; ++i )
1242  {
1243  VECTOR2I ipNext = ( i == cnt ? aPath.CPoint( 0 ) : aPath.CPoint( i ) );
1244 
1245  if( ipNext.y == aP.y )
1246  {
1247  if( ( ipNext.x == aP.x ) || ( ip.y == aP.y &&
1248  ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
1249  return true;
1250  }
1251 
1252  if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
1253  {
1254  if( ip.x >= aP.x )
1255  {
1256  if( ipNext.x > aP.x )
1257  result = 1 - result;
1258  else
1259  {
1260  int64_t d = (int64_t)( ip.x - aP.x ) * (int64_t)( ipNext.y - aP.y ) -
1261  (int64_t)( ipNext.x - aP.x ) * (int64_t)( ip.y - aP.y );
1262 
1263  if( !d )
1264  return true;
1265 
1266  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1267  result = 1 - result;
1268  }
1269  }
1270  else
1271  {
1272  if( ipNext.x > aP.x )
1273  {
1274  int64_t d = (int64_t)( ip.x - aP.x ) * (int64_t)( ipNext.y - aP.y ) -
1275  (int64_t)( ipNext.x - aP.x ) * (int64_t)( ip.y - aP.y );
1276 
1277  if( !d )
1278  return true;
1279 
1280  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1281  result = 1 - result;
1282  }
1283  }
1284  }
1285 
1286  ip = ipNext;
1287  }
1288 
1289  return result ? true : false;
1290 }
1291 
1292 
1293 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1294 {
1295  for( POLYGON &poly : m_polys )
1296  {
1297  for( SHAPE_LINE_CHAIN &path : poly )
1298  {
1299  path.Move( aVector );
1300  }
1301  }
1302 }
1303 
1304 
1306 {
1307  int c = 0;
1308 
1309  for( const POLYGON& poly : m_polys )
1310  {
1311  for( const SHAPE_LINE_CHAIN& path : poly )
1312  {
1313  c += path.PointCount();
1314  }
1315  }
1316 
1317  return c;
1318 }
1319 
1320 
1321 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1322 {
1323  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1324 }
1325 
1326 
1328  unsigned int aSegments,
1329  int aIndex )
1330 {
1331  return chamferFilletPolygon(CORNER_MODE::FILLETED, aRadius, aIndex, aSegments );
1332 }
1333 
1334 
1335 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1336 {
1337  // We calculate the min dist between the segment and each outline segment
1338  // However, if the segment to test is inside the outline, and does not cross
1339  // any edge, it can be seen outside the polygon.
1340  // Therefore test if a segment end is inside ( testing only one end is enough )
1341  if( containsSingle( aPoint, aPolygonIndex ) )
1342  return 0;
1343 
1344  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1345 
1346  SEG polygonEdge = *iterator;
1347  int minDistance = polygonEdge.Distance( aPoint );
1348 
1349  for( iterator++; iterator && minDistance > 0; iterator++ )
1350  {
1351  polygonEdge = *iterator;
1352 
1353  int currentDistance = polygonEdge.Distance( aPoint );
1354 
1355  if( currentDistance < minDistance )
1356  minDistance = currentDistance;
1357  }
1358 
1359  return minDistance;
1360 }
1361 
1362 
1363 int SHAPE_POLY_SET::DistanceToPolygon( SEG aSegment, int aPolygonIndex, int aSegmentWidth )
1364 {
1365  // We calculate the min dist between the segment and each outline segment
1366  // However, if the segment to test is inside the outline, and does not cross
1367  // any edge, it can be seen outside the polygon.
1368  // Therefore test if a segment end is inside ( testing only one end is enough )
1369  if( containsSingle( aSegment.A, aPolygonIndex ) )
1370  return 0;
1371 
1372  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1373 
1374  SEG polygonEdge = *iterator;
1375  int minDistance = polygonEdge.Distance( aSegment );
1376 
1377  for( iterator++; iterator && minDistance > 0; iterator++ )
1378  {
1379  polygonEdge = *iterator;
1380 
1381  int currentDistance = polygonEdge.Distance( aSegment );
1382 
1383  if( currentDistance < minDistance )
1384  minDistance = currentDistance;
1385  }
1386 
1387  // Take into account the width of the segment
1388  if( aSegmentWidth > 0 )
1389  minDistance -= aSegmentWidth/2;
1390 
1391  // Return the maximum of minDistance and zero
1392  return minDistance < 0 ? 0 : minDistance;
1393 }
1394 
1395 
1397 {
1398  int currentDistance;
1399  int minDistance = DistanceToPolygon( aPoint, 0 );
1400 
1401  // Iterate through all the polygons and get the minimum distance.
1402  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1403  {
1404  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1405 
1406  if( currentDistance < minDistance )
1407  minDistance = currentDistance;
1408  }
1409 
1410  return minDistance;
1411 }
1412 
1413 
1414 int SHAPE_POLY_SET::Distance( SEG aSegment, int aSegmentWidth )
1415 {
1416  int currentDistance;
1417  int minDistance = DistanceToPolygon( aSegment, 0 );
1418 
1419  // Iterate through all the polygons and get the minimum distance.
1420  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1421  {
1422  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1423 
1424  if( currentDistance < minDistance )
1425  minDistance = currentDistance;
1426  }
1427 
1428  return minDistance;
1429 }
1430 
1431 
1432 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1433 {
1434  VERTEX_INDEX index;
1435 
1436  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1437  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1438  return false;
1439 
1440  // The contour is a hole if its index is greater than zero
1441  return index.m_contour > 0;
1442 }
1443 
1444 
1446 {
1447  SHAPE_POLY_SET chamfered;
1448 
1449  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1450  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1451 
1452  return chamfered;
1453 }
1454 
1455 
1456 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aSegments )
1457 {
1458  SHAPE_POLY_SET filleted;
1459 
1460  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1461  filleted.m_polys.push_back( FilletPolygon( aRadius, aSegments, polygonIdx ) );
1462 
1463  return filleted;
1464 }
1465 
1466 
1468  unsigned int aDistance,
1469  int aIndex,
1470  int aSegments )
1471 {
1472  // Null segments create serious issues in calculations. Remove them:
1474 
1475  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1476  SHAPE_POLY_SET::POLYGON newPoly;
1477 
1478  // If the chamfering distance is zero, then the polygon remain intact.
1479  if( aDistance == 0 )
1480  {
1481  return currentPoly;
1482  }
1483 
1484  // Iterate through all the contours (outline and holes) of the polygon.
1485  for( SHAPE_LINE_CHAIN &currContour : currentPoly )
1486  {
1487  // Generate a new contour in the new polygon
1488  SHAPE_LINE_CHAIN newContour;
1489 
1490  // Iterate through the vertices of the contour
1491  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1492  {
1493  // Current vertex
1494  int x1 = currContour.Point( currVertex ).x;
1495  int y1 = currContour.Point( currVertex ).y;
1496 
1497  // Indices for previous and next vertices.
1498  int prevVertex;
1499  int nextVertex;
1500 
1501  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1502 
1503  // Previous vertex is the last one if the current vertex is the first one
1504  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1505 
1506  // next vertex is the first one if the current vertex is the last one.
1507  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1508 
1509  // Previous vertex computation
1510  double xa = currContour.Point( prevVertex ).x - x1;
1511  double ya = currContour.Point( prevVertex ).y - y1;
1512 
1513  // Next vertex computation
1514  double xb = currContour.Point( nextVertex ).x - x1;
1515  double yb = currContour.Point( nextVertex ).y - y1;
1516 
1517  // Compute the new distances
1518  double lena = hypot( xa, ya );
1519  double lenb = hypot( xb, yb );
1520 
1521  // Make the final computations depending on the mode selected, chamfered or filleted.
1522  if( aMode == CORNER_MODE::CHAMFERED )
1523  {
1524  double distance = aDistance;
1525 
1526  // Chamfer one half of an edge at most
1527  if( 0.5 * lena < distance )
1528  distance = 0.5 * lena;
1529 
1530  if( 0.5 * lenb < distance )
1531  distance = 0.5 * lenb;
1532 
1533  int nx1 = KiROUND( distance * xa / lena );
1534  int ny1 = KiROUND( distance * ya / lena );
1535 
1536  newContour.Append( x1 + nx1, y1 + ny1 );
1537 
1538  int nx2 = KiROUND( distance * xb / lenb );
1539  int ny2 = KiROUND( distance * yb / lenb );
1540 
1541  newContour.Append( x1 + nx2, y1 + ny2 );
1542  }
1543  else // CORNER_MODE = FILLETED
1544  {
1545  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1546 
1547  double radius = aDistance;
1548  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1549 
1550  // Do nothing in case of parallel edges
1551  if( std::isinf( denom ) )
1552  continue;
1553 
1554  // Limit rounding distance to one half of an edge
1555  if( 0.5 * lena * denom < radius )
1556  radius = 0.5 * lena * denom;
1557 
1558  if( 0.5 * lenb * denom < radius )
1559  radius = 0.5 * lenb * denom;
1560 
1561  // Calculate fillet arc absolute center point (xc, yx)
1562  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1563  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1564  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1565  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1566  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1567 
1568  // Calculate arc start and end vectors
1569  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1570  double xs = x1 + k * xa / lena - xc;
1571  double ys = y1 + k * ya / lena - yc;
1572  double xe = x1 + k * xb / lenb - xc;
1573  double ye = y1 + k * yb / lenb - yc;
1574 
1575  // Cosine of arc angle
1576  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1577 
1578  // Make sure the argument is in [-1,1], interval in which the acos function is
1579  // defined
1580  if( argument < -1 )
1581  argument = -1;
1582  else if( argument > 1 )
1583  argument = 1;
1584 
1585  double arcAngle = acos( argument );
1586 
1587  // Calculate the number of segments
1588  unsigned int segments = ceil( (double) aSegments * ( arcAngle / ( 2 * M_PI ) ) );
1589 
1590  double deltaAngle = arcAngle / segments;
1591  double startAngle = atan2( -ys, xs );
1592 
1593  // Flip arc for inner corners
1594  if( xa * yb - ya * xb <= 0 )
1595  deltaAngle *= -1;
1596 
1597  double nx = xc + xs;
1598  double ny = yc + ys;
1599 
1600  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1601 
1602  // Store the previous added corner to make a sanity check
1603  int prevX = KiROUND( nx );
1604  int prevY = KiROUND( ny );
1605 
1606  for( unsigned int j = 0; j < segments; j++ )
1607  {
1608  nx = xc + cos( startAngle + (j + 1) * deltaAngle ) * radius;
1609  ny = yc - sin( startAngle + (j + 1) * deltaAngle ) * radius;
1610 
1611  // Sanity check: the rounding can produce repeated corners; do not add them.
1612  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1613  {
1614  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1615  prevX = KiROUND( nx );
1616  prevY = KiROUND( ny );
1617  }
1618  }
1619  }
1620  }
1621 
1622  // Close the current contour and add it the new polygon
1623  newContour.SetClosed( true );
1624  newPoly.push_back( newContour );
1625  }
1626 
1627  return newPoly;
1628 }
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)
Function booleanOp this is the engine to execute all polygon boolean transforms (AND, OR, ...
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
POLYGON ChamferPolygon(unsigned int aDistance, int aIndex=0)
Function Chamfer returns a chamfered version of the aIndex-th polygon.
bool HasHoles() const
Returns true if the polygon set has any holes.
const VECTOR2I & CVertex(int aIndex, int aOutline, int aHole) const
Returns the index-th vertex in a given hole outline within a given outline
bool matches(int y) const
void fractureSingle(POLYGON &paths)
static int KiROUND(double v)
KiROUND rounds a floating point number to an int using "round halfway cases away from zero"...
Definition: common.h:107
SEGMENT_ITERATOR IterateSegmentsWithHoles()
Returns an iterator object, for all outlines in the set (with holes)
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
bool CollideEdge(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideEdge Checks whether aPoint collides with any edge of any of the contours of the polyg...
int PointCount() const
Function PointCount()
const ClipperLib::Path convertToClipper(const SHAPE_LINE_CHAIN &aPath, bool aRequiredOrientation)
bool Contains(const Vec &aPoint) const
Function Contains.
Definition: box2.h:139
bool IsPolygonSelfIntersecting(int aPolygonIndex)
Function IsPolygonSelfIntersecting.
int NormalizeAreaOutlines()
Function NormalizeAreaOutlines Convert a self-intersecting polygon to one (or more) non self-intersec...
int HoleCount(int aOutline) const
Returns the number of holes in a given outline
static const int dist[10][10]
Definition: dist.cpp:57
bool Parse(std::stringstream &aStream) override
int TotalVertices() const
Returns total number of vertices stored in the set.
Struct VERTEX_INDEX.
static int processEdge(FractureEdgeSet &edges, FractureEdge *edge)
Class SEGMENT_ITERATOR_TEMPLATE.
const SHAPE_LINE_CHAIN & CHole(int aOutline, int aHole) const
POLYGON chamferFilletPolygon(CORNER_MODE aMode, unsigned int aDistance, int aIndex, int aSegments=-1)
Function chamferFilletPolygon Returns the camfered or filleted version of the aIndex-th polygon in th...
int OutlineCount() const
Returns the number of outlines in the set
FractureEdge(bool connected, SHAPE_LINE_CHAIN *owner, int index)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:590
#define abs(a)
Definition: auxiliary.h:84
VERTEX_INDEX GetIndex()
Function GetIndex.
static const int delta[8][2]
Definition: solve.cpp:112
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
bool IsEndContour() const
Function IsEndContour.
#define SEG_CNT_MAX
bool IsVertexInHole(int aGlobalIdx)
Function IsVertexInHole.
VECTOR2I & Vertex(int aIndex, int aOutline, int aHole)
Returns the index-th vertex in a given hole outline within a given outline
void DeletePolygon(int aIdx)
Deletes aIdx-th polygon from the set
void SetClosed(bool aClosed)
Function SetClosed()
VECTOR2I & A
Definition: seg.h:51
const BOX2I BBox(int aClearance=0) const override
Function BBox()
T EuclideanNorm() const
Destructor.
Definition: vector2d.h:295
void Inflate(int aFactor, int aCircleSegmentsCount)
Performs outline inflation/deflation, using round corners.
SHAPE_POLY_SET Fillet(int aRadius, int aSegments)
Function Fillet returns a filleted version of the polygon set.
void Move(const VECTOR2I &aVector) override
Class SHAPE_POLY_SET.
bool containsSingle(const VECTOR2I &aP, int aSubpolyIndex) const
containsSingle function Checks whether the point aP is inside the aSubpolyIndex-th polygon of the pol...
bool GetRelativeIndices(int aGlobalIdx, VERTEX_INDEX *aRelativeIndices) const
Function GetRelativeIndices.
bool IsAdjacent(SEGMENT_ITERATOR_TEMPLATE< T > aOther)
Function IsAdjacent.
bool CollideVertex(const VECTOR2I &aPoint, VERTEX_INDEX &aClosestVertex, int aClearance=0)
Function CollideVertex Checks whether aPoint collides with any vertex of any of the contours of the p...
bool PointOnEdge(const VECTOR2I &aP) const
Function PointOnEdge()
void Simplify(POLYGON_MODE aFastMode)
Simplifies the polyset (merges overlapping polys, eliminates degeneracy/self-intersections) For aFast...
Class SHAPE.
Definition: shape.h:57
bool Collide(const VECTOR2I &aP, int aClearance=0) const override
Function Collide Checks whether the point aP collides with the inside of the polygon set; if the poin...
BOX2< Vec > & Merge(const BOX2< Vec > &aRect)
Function Merge modifies the position and size of the rectangle in order to contain aRect...
Definition: box2.h:350
const std::string Format() const override
int RemoveNullSegments()
Function RemoveNullSegments looks for null segments; ie, segments whose ends are exactly the same and...
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset intersection For aFastMode meaning, see function booleanOp ...
int NewOutline()
Creates a new empty polygon in the set and returns its index
void Fracture(POLYGON_MODE aFastMode)
Converts a set of polygons with holes to a singe outline with "slits"/"fractures" connecting the oute...
int AddHole(const SHAPE_LINE_CHAIN &aHole, int aOutline=-1)
Adds a new hole to the given outline (default: last) and returns its index
VECTOR2I & vertex(int aCornerId)
FractureEdge(bool connected, const VECTOR2I &p1, const VECTOR2I &p2)
int rescale(int aNumerator, int aValue, int aDenominator)
Definition: math_util.cpp:32
bool pointInPolygon(const VECTOR2I &aP, const SHAPE_LINE_CHAIN &aPath) const
bool GetGlobalIndex(VERTEX_INDEX aRelativeIndices, int &aGlobalIdx)
Function GetGlobalIndex computes the global index of a vertex from the relative indices of polygon...
Definition: seg.h:37
int DistanceToPolygon(VECTOR2I aPoint, int aIndex)
Function DistanceToPolygon computes the minimum distance between the aIndex-th polygon and aPoint...
int AddOutline(const SHAPE_LINE_CHAIN &aOutline)
Adds a new outline to the set and returns its index
CORNER_MODE
Operations ChamferPolygon and FilletPolygon are computed under the private chamferFillet method; this...
BOX2< Vec > & Inflate(coord_type dx, coord_type dy)
Function Inflate inflates the rectangle horizontally by dx and vertically by dy.
Definition: box2.h:266
convex polygon
Definition: shape.h:48
SHAPE_POLY_SET Chamfer(int aDistance)
Function Chamfer returns a chamfered version of the polygon set.
const SHAPE_LINE_CHAIN convertFromClipper(const ClipperLib::Path &aPath)
#define max(a, b)
Definition: auxiliary.h:86
ITERATOR IterateWithHoles()
Function IterateWithHoles.
Class SHAPE_LINE_CHAIN.
FractureEdge * m_next
void RemoveVertex(int aGlobalIndex)
Function RemoveVertex deletes the aGlobalIndex-th vertex.
int VertexCount(int aOutline=-1, int aHole=-1) const
Returns the number of vertices in a given outline/hole
Class ITERATOR_TEMPLATE.
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
SEG Edge(int aGlobalIndex)
Function Edge Returns a reference to the aGlobalIndex-th segment in the polygon set.
int Distance(VECTOR2I point)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
static bool empty(const wxTextEntryBase *aCtrl)
The common library.
bool IsClosed() const
Function IsClosed()
const POLYGON & CPolygon(int aIndex) const
void InsertVertex(int aGlobalIndex, VECTOR2I aNewVertex)
Function InsertVertex Adds a vertex in the globally indexed position aGlobalIndex.
VECTOR2I & Point(int aIndex)
Function Point()
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)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp ...
POLYGON & Polygon(int aIndex)
Returns the aIndex-th subpolygon in the set
bool Collide(const SEG &aSeg, int aClearance) const
Definition: seg.cpp:134
POLYGON FilletPolygon(unsigned int aRadius, unsigned int aSegments, int aIndex=0)
Function Fillet returns a filleted version of the aIndex-th polygon.
SHAPE * Clone() const override
Function Clone()
bool IsSelfIntersecting()
Function IsSelfIntersecting Checks whether any of the polygons in the set is self intersecting...
FractureEdge(int y=0)
const VECTOR2I & CPoint(int aIndex) const
Function CPoint()
int Distance(const SEG &aSeg) const
Function Distance()
Definition: seg.h:228
const BOX2I BBox(int aClearance=0) const override
Function BBox()
VERTEX_INDEX GetIndex()
Function GetIndex.
bool Contains(const VECTOR2I &aP, int aSubpolyIndex=-1) const
Returns true if a given subpolygon contains the point aP.
std::vector< FractureEdge * > FractureEdgeSet
SHAPE_POLY_SET Subset(int aFirstPolygon, int aLastPolygon)
Function Subset returns a subset of the polygons in this set, the ones between aFirstPolygon and aLas...
#define min(a, b)
Definition: auxiliary.h:85
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Appends a vertex at the end of the given outline/hole (default: the last outline) ...
void RemoveContour(int aContourIdx, int aPolygonIdx=-1)
Function RemoveContour deletes the aContourIdx-th contour of the aPolygonIdx-th polygon in the set...
void importTree(ClipperLib::PolyTree *tree)