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  {
207  Append( aNewVertex );
208  }
209  else
210  {
211  // Assure the position to be inserted exists; throw an exception otherwise
212  if( GetRelativeIndices( aGlobalIndex, &index ) )
213  m_polys[index.m_polygon][index.m_contour].Insert( index.m_vertex, aNewVertex );
214  else
215  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
216  }
217 
218 }
219 
220 
221 int SHAPE_POLY_SET::VertexCount( int aOutline , int aHole ) const
222 {
223  if( aOutline < 0 )
224  aOutline += m_polys.size();
225 
226  int idx;
227 
228  if( aHole < 0 )
229  idx = 0;
230  else
231  idx = aHole + 1;
232 
233  assert ( aOutline < (int)m_polys.size() );
234  assert ( idx < (int)m_polys[aOutline].size() );
235 
236  return m_polys[aOutline][idx].PointCount();
237 }
238 
239 
240 SHAPE_POLY_SET SHAPE_POLY_SET::Subset( int aFirstPolygon, int aLastPolygon )
241 {
242  assert( aFirstPolygon >= 0 && aLastPolygon <= OutlineCount() );
243 
244  SHAPE_POLY_SET newPolySet;
245 
246  for( int index = aFirstPolygon; index < aLastPolygon; index++ )
247  {
248  newPolySet.m_polys.push_back( Polygon( index ) );
249  }
250 
251  return newPolySet;
252 }
253 
254 
255 VECTOR2I& SHAPE_POLY_SET::Vertex( int aIndex, int aOutline, int aHole )
256 {
257  if( aOutline < 0 )
258  aOutline += m_polys.size();
259 
260  int idx;
261 
262  if( aHole < 0 )
263  idx = 0;
264  else
265  idx = aHole + 1;
266 
267  assert( aOutline < (int)m_polys.size() );
268  assert( idx < (int)m_polys[aOutline].size() );
269 
270  return m_polys[aOutline][idx].Point( aIndex );
271 }
272 
273 
274 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aIndex, int aOutline, int aHole ) const
275 {
276  if( aOutline < 0 )
277  aOutline += m_polys.size();
278 
279  int idx;
280 
281  if( aHole < 0 )
282  idx = 0;
283  else
284  idx = aHole + 1;
285 
286  assert( aOutline < (int)m_polys.size() );
287  assert( idx < (int)m_polys[aOutline].size() );
288 
289  return m_polys[aOutline][idx].CPoint( aIndex );
290 }
291 
292 
293 VECTOR2I& SHAPE_POLY_SET::Vertex( int aGlobalIndex )
294 {
296 
297  // Assure the passed index references a legal position; abort otherwise
298  if( !GetRelativeIndices( aGlobalIndex, &index ) )
299  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
300 
301  return m_polys[index.m_polygon][index.m_contour].Point( index.m_vertex );
302 }
303 
304 
305 const VECTOR2I& SHAPE_POLY_SET::CVertex( int aGlobalIndex ) const
306 {
308 
309  // Assure the passed index references a legal position; abort otherwise
310  if( !GetRelativeIndices( aGlobalIndex, &index ) )
311  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
312 
313  return m_polys[index.m_polygon][index.m_contour].CPoint( index.m_vertex );
314 }
315 
316 
318 {
319  return Vertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
320 }
321 
322 
324 {
325  return CVertex( index.m_vertex, index.m_polygon, index.m_contour - 1 );
326 }
327 
328 bool SHAPE_POLY_SET::GetNeighbourIndexes( int aGlobalIndex, int* aPrevious, int* aNext )
329 {
331 
332  // If the edge does not exist, throw an exception, it is an illegal access memory error
333  if( !GetRelativeIndices( aGlobalIndex, &index ) )
334  return false;
335 
336  // Calculate the previous and next index of aGlobalIndex, corresponding to
337  // the same contour;
338  VERTEX_INDEX inext = index;
339  int lastpoint = m_polys[index.m_polygon][index.m_contour].SegmentCount();
340 
341  if( index.m_vertex == 0 )
342  {
343  index.m_vertex = lastpoint;
344  inext.m_vertex = 1;
345  }
346  else if( index.m_vertex == lastpoint )
347  {
348  index.m_vertex--;
349  inext.m_vertex = 0;
350  }
351  else
352  {
353  inext.m_vertex++;
354  index.m_vertex--;
355  }
356 
357  if( aPrevious )
358  {
359  int previous;
360  GetGlobalIndex( index, previous );
361  *aPrevious = previous;
362  }
363 
364  if( aNext )
365  {
366  int next;
367  GetGlobalIndex( inext, next );
368  *aNext = next;
369  }
370 
371  return true;
372 }
373 
374 
376 {
377  // Get polygon
378  const POLYGON poly = CPolygon( aPolygonIndex );
379 
380  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
381  SEGMENT_ITERATOR innerIterator;
382 
383  for( iterator = IterateSegmentsWithHoles( aPolygonIndex ); iterator; iterator++ )
384  {
385  SEG firstSegment = *iterator;
386 
387  // Iterate through all remaining segments.
388  innerIterator = iterator;
389 
390  // Start in the next segment, we don't want to check collision between a segment and itself
391  for( innerIterator++; innerIterator; innerIterator++ )
392  {
393  SEG secondSegment = *innerIterator;
394 
395  // Check whether the two segments built collide, only when they are not adjacent.
396  if( !iterator.IsAdjacent( innerIterator ) && firstSegment.Collide( secondSegment, 0 ) )
397  return true;
398  }
399  }
400 
401  return false;
402 }
403 
404 
406 {
407  for( unsigned int polygon = 0; polygon < m_polys.size(); polygon++ )
408  {
409  if( IsPolygonSelfIntersecting( polygon ) )
410  return true;
411  }
412 
413  return false;
414 }
415 
416 
418 {
419  assert( aOutline.IsClosed() );
420 
421  POLYGON poly;
422 
423  poly.push_back( aOutline );
424 
425  m_polys.push_back( poly );
426 
427  return m_polys.size() - 1;
428 }
429 
430 
431 int SHAPE_POLY_SET::AddHole( const SHAPE_LINE_CHAIN& aHole, int aOutline )
432 {
433  assert ( m_polys.size() );
434 
435  if( aOutline < 0 )
436  aOutline += m_polys.size();
437 
438  POLYGON& poly = m_polys[aOutline];
439 
440  assert( poly.size() );
441 
442  poly.push_back( aHole );
443 
444  return poly.size() - 1;
445 }
446 
447 
448 const Path SHAPE_POLY_SET::convertToClipper( const SHAPE_LINE_CHAIN& aPath, bool aRequiredOrientation )
449 {
450  Path c_path;
451 
452  for( int i = 0; i < aPath.PointCount(); i++ )
453  {
454  const VECTOR2I& vertex = aPath.CPoint( i );
455  c_path.push_back( IntPoint( vertex.x, vertex.y ) );
456  }
457 
458  if( Orientation( c_path ) != aRequiredOrientation )
459  ReversePath( c_path );
460 
461  return c_path;
462 }
463 
464 
466 {
467  SHAPE_LINE_CHAIN lc;
468 
469  for( unsigned int i = 0; i < aPath.size(); i++ )
470  lc.Append( aPath[i].X, aPath[i].Y );
471 
472  lc.SetClosed( true );
473 
474  return lc;
475 }
476 
477 
478 void SHAPE_POLY_SET::booleanOp( ClipType aType, const SHAPE_POLY_SET& aOtherShape,
479  POLYGON_MODE aFastMode )
480 {
481  Clipper c;
482 
483  if( aFastMode == PM_STRICTLY_SIMPLE )
484  c.StrictlySimple( true );
485 
486  for( const POLYGON& poly : m_polys )
487  {
488  for( unsigned int i = 0; i < poly.size(); i++ )
489  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
490  }
491 
492  for( const POLYGON& poly : aOtherShape.m_polys )
493  {
494  for( unsigned int i = 0; i < poly.size(); i++ )
495  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
496  }
497 
498  PolyTree solution;
499 
500  c.Execute( aType, solution, pftNonZero, pftNonZero );
501 
502  importTree( &solution );
503 }
504 
505 
506 void SHAPE_POLY_SET::booleanOp( ClipperLib::ClipType aType,
507  const SHAPE_POLY_SET& aShape,
508  const SHAPE_POLY_SET& aOtherShape,
509  POLYGON_MODE aFastMode )
510 {
511  Clipper c;
512 
513  if( aFastMode == PM_STRICTLY_SIMPLE )
514  c.StrictlySimple( true );
515 
516  for( const POLYGON& poly : aShape.m_polys )
517  {
518  for( unsigned int i = 0; i < poly.size(); i++ )
519  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptSubject, true );
520  }
521 
522  for( const POLYGON& poly : aOtherShape.m_polys )
523  {
524  for( unsigned int i = 0; i < poly.size(); i++ )
525  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), ptClip, true );
526  }
527 
528  PolyTree solution;
529 
530  c.Execute( aType, solution, pftNonZero, pftNonZero );
531 
532  importTree( &solution );
533 }
534 
535 
537 {
538  booleanOp( ctUnion, b, aFastMode );
539 }
540 
541 
543 {
544  booleanOp( ctDifference, b, aFastMode );
545 }
546 
547 
549 {
550  booleanOp( ctIntersection, b, aFastMode );
551 }
552 
553 
555 {
556  booleanOp( ctUnion, a, b, aFastMode );
557 }
558 
559 
561 {
562  booleanOp( ctDifference, a, b, aFastMode );
563 }
564 
565 
567 {
568  booleanOp( ctIntersection, a, b, aFastMode );
569 }
570 
571 
572 void SHAPE_POLY_SET::Inflate( int aFactor, int aCircleSegmentsCount )
573 {
574  // A static table to avoid repetitive calculations of the coefficient
575  // 1.0 - cos( M_PI/aCircleSegmentsCount)
576  // aCircleSegmentsCount is most of time <= 64 and usually 8, 12, 16, 32
577  #define SEG_CNT_MAX 64
578  static double arc_tolerance_factor[SEG_CNT_MAX+1];
579 
580  ClipperOffset c;
581 
582  for( const POLYGON& poly : m_polys )
583  {
584  for( unsigned int i = 0; i < poly.size(); i++ )
585  c.AddPath( convertToClipper( poly[i], i > 0 ? false : true ), jtRound, etClosedPolygon );
586  }
587 
588  PolyTree solution;
589 
590  // Calculate the arc tolerance (arc error) from the seg count by circle.
591  // the seg count is nn = M_PI / acos(1.0 - c.ArcTolerance / abs(aFactor))
592  // see:
593  // www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Classes/ClipperOffset/Properties/ArcTolerance.htm
594 
595  if( aCircleSegmentsCount < 6 ) // avoid incorrect aCircleSegmentsCount values
596  aCircleSegmentsCount = 6;
597 
598  double coeff;
599 
600  if( aCircleSegmentsCount > SEG_CNT_MAX || arc_tolerance_factor[aCircleSegmentsCount] == 0 )
601  {
602  coeff = 1.0 - cos( M_PI/aCircleSegmentsCount);
603 
604  if( aCircleSegmentsCount <= SEG_CNT_MAX )
605  arc_tolerance_factor[aCircleSegmentsCount] = coeff;
606  }
607  else
608  coeff = arc_tolerance_factor[aCircleSegmentsCount];
609 
610  c.ArcTolerance = std::abs( aFactor ) * coeff;
611 
612  c.Execute( solution, aFactor );
613 
614  importTree( &solution );
615 }
616 
617 
618 void SHAPE_POLY_SET::importTree( PolyTree* tree )
619 {
620  m_polys.clear();
621 
622  for( PolyNode* n = tree->GetFirst(); n; n = n->GetNext() )
623  {
624  if( !n->IsHole() )
625  {
626  POLYGON paths;
627  paths.reserve( n->Childs.size() + 1 );
628  paths.push_back( convertFromClipper( n->Contour ) );
629 
630  for( unsigned int i = 0; i < n->Childs.size(); i++ )
631  paths.push_back( convertFromClipper( n->Childs[i]->Contour ) );
632 
633  m_polys.push_back( paths );
634  }
635  }
636 }
637 
638 // Polygon fracturing code. Work in progress.
639 
641 {
642  FractureEdge( bool connected, SHAPE_LINE_CHAIN* owner, int index ) :
643  m_connected( connected ),
644  m_next( NULL )
645  {
646  m_p1 = owner->CPoint( index );
647  m_p2 = owner->CPoint( index + 1 );
648  }
649 
650  FractureEdge( int y = 0 ) :
651  m_connected( false ),
652  m_next( NULL )
653  {
654  m_p1.x = m_p2.y = y;
655  }
656 
657  FractureEdge( bool connected, const VECTOR2I& p1, const VECTOR2I& p2 ) :
658  m_connected( connected ),
659  m_p1( p1 ),
660  m_p2( p2 ),
661  m_next( NULL )
662  {
663  }
664 
665  bool matches( int y ) const
666  {
667  int y_min = std::min( m_p1.y, m_p2.y );
668  int y_max = std::max( m_p1.y, m_p2.y );
669 
670  return ( y >= y_min ) && ( y <= y_max );
671  }
672 
676 };
677 
678 
679 typedef std::vector<FractureEdge*> FractureEdgeSet;
680 
681 
682 static int processEdge( FractureEdgeSet& edges, FractureEdge* edge )
683 {
684  int x = edge->m_p1.x;
685  int y = edge->m_p1.y;
686  int min_dist = std::numeric_limits<int>::max();
687  int x_nearest = 0;
688 
689  FractureEdge* e_nearest = NULL;
690 
691  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
692  {
693  if( !(*i)->matches( y ) )
694  continue;
695 
696  int x_intersect;
697 
698  if( (*i)->m_p1.y == (*i)->m_p2.y ) // horizontal edge
699  x_intersect = std::max ( (*i)->m_p1.x, (*i)->m_p2.x );
700  else
701  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 );
702 
703  int dist = ( x - x_intersect );
704 
705  if( dist >= 0 && dist < min_dist && (*i)->m_connected )
706  {
707  min_dist = dist;
708  x_nearest = x_intersect;
709  e_nearest = (*i);
710  }
711  }
712 
713  if( e_nearest && e_nearest->m_connected )
714  {
715  int count = 0;
716 
717  FractureEdge* lead1 = new FractureEdge( true, VECTOR2I( x_nearest, y ), VECTOR2I( x, y ) );
718  FractureEdge* lead2 = new FractureEdge( true, VECTOR2I( x, y ), VECTOR2I( x_nearest, y ) );
719  FractureEdge* split_2 = new FractureEdge( true, VECTOR2I( x_nearest, y ), e_nearest->m_p2 );
720 
721  edges.push_back( split_2 );
722  edges.push_back( lead1 );
723  edges.push_back( lead2 );
724 
725  FractureEdge* link = e_nearest->m_next;
726 
727  e_nearest->m_p2 = VECTOR2I( x_nearest, y );
728  e_nearest->m_next = lead1;
729  lead1->m_next = edge;
730 
731  FractureEdge*last;
732  for( last = edge; last->m_next != edge; last = last->m_next )
733  {
734  last->m_connected = true;
735  count++;
736  }
737 
738  last->m_connected = true;
739  last->m_next = lead2;
740  lead2->m_next = split_2;
741  split_2->m_next = link;
742 
743  return count + 1;
744  }
745 
746  return 0;
747 }
748 
749 
751 {
752  FractureEdgeSet edges;
753  FractureEdgeSet border_edges;
754  FractureEdge* root = NULL;
755 
756  bool first = true;
757 
758  if( paths.size() == 1 )
759  return;
760 
761  int num_unconnected = 0;
762 
763  for( SHAPE_LINE_CHAIN& path : paths )
764  {
765  int index = 0;
766 
767  FractureEdge *prev = NULL, *first_edge = NULL;
768 
769  int x_min = std::numeric_limits<int>::max();
770 
771  for( int i = 0; i < path.PointCount(); i++ )
772  {
773  const VECTOR2I& p = path.CPoint( i );
774 
775  if( p.x < x_min )
776  x_min = p.x;
777  }
778 
779  for( int i = 0; i < path.PointCount(); i++ )
780  {
781  FractureEdge* fe = new FractureEdge( first, &path, index++ );
782 
783  if( !root )
784  root = fe;
785 
786  if( !first_edge )
787  first_edge = fe;
788 
789  if( prev )
790  prev->m_next = fe;
791 
792  if( i == path.PointCount() - 1 )
793  fe->m_next = first_edge;
794 
795  prev = fe;
796  edges.push_back( fe );
797 
798  if( !first )
799  {
800  if( fe->m_p1.x == x_min )
801  border_edges.push_back( fe );
802  }
803 
804  if( !fe->m_connected )
805  num_unconnected++;
806  }
807  first = false; // first path is always the outline
808  }
809 
810  // keep connecting holes to the main outline, until there's no holes left...
811  while( num_unconnected > 0 )
812  {
813  int x_min = std::numeric_limits<int>::max();
814 
815  FractureEdge* smallestX = NULL;
816 
817  // find the left-most hole edge and merge with the outline
818  for( FractureEdgeSet::iterator i = border_edges.begin(); i != border_edges.end(); ++i )
819  {
820  int xt = (*i)->m_p1.x;
821 
822  if( ( xt < x_min ) && ! (*i)->m_connected )
823  {
824  x_min = xt;
825  smallestX = *i;
826  }
827  }
828 
829  num_unconnected -= processEdge( edges, smallestX );
830  }
831 
832  paths.clear();
833  SHAPE_LINE_CHAIN newPath;
834 
835  newPath.SetClosed( true );
836 
837  FractureEdge* e;
838 
839  for( e = root; e->m_next != root; e = e->m_next )
840  newPath.Append( e->m_p1 );
841 
842  newPath.Append( e->m_p1 );
843 
844  for( FractureEdgeSet::iterator i = edges.begin(); i != edges.end(); ++i )
845  delete *i;
846 
847  paths.push_back( newPath );
848 }
849 
850 
852 {
853  Simplify( aFastMode ); // remove overlapping holes/degeneracy
854 
855  for( POLYGON& paths : m_polys )
856  {
857  fractureSingle( paths );
858  }
859 }
860 
861 
863 {
864  // Iterate through all the polygons on the set
865  for( const POLYGON& paths : m_polys )
866  {
867  // If any of them has more than one contour, it is a hole.
868  if( paths.size() > 1 )
869  return true;
870  }
871 
872  // Return false if and only if every polygon has just one outline, without holes.
873  return false;
874 }
875 
876 
878 {
880 
881  booleanOp( ctUnion, empty, aFastMode );
882 }
883 
884 
886 {
887  // We are expecting only one main outline, but this main outline can have holes
888  // if holes: combine holes and remove them from the main outline.
889  // Note also we are using SHAPE_POLY_SET::PM_STRICTLY_SIMPLE in polygon
890  // calculations, but it is not mandatory. It is used mainly
891  // because there is usually only very few vertices in area outlines
892  SHAPE_POLY_SET::POLYGON& outline = Polygon( 0 );
893  SHAPE_POLY_SET holesBuffer;
894 
895  // Move holes stored in outline to holesBuffer:
896  // The first SHAPE_LINE_CHAIN is the main outline, others are holes
897  while( outline.size() > 1 )
898  {
899  holesBuffer.AddOutline( outline.back() );
900  outline.pop_back();
901  }
902 
904 
905  // If any hole, substract it to main outline
906  if( holesBuffer.OutlineCount() )
907  {
908  holesBuffer.Simplify( SHAPE_POLY_SET::PM_FAST);
910  }
911 
913 
914  return OutlineCount();
915 }
916 
917 
918 const std::string SHAPE_POLY_SET::Format() const
919 {
920  std::stringstream ss;
921 
922  ss << "polyset " << m_polys.size() << "\n";
923 
924  for( unsigned i = 0; i < m_polys.size(); i++ )
925  {
926  ss << "poly " << m_polys[i].size() << "\n";
927  for( unsigned j = 0; j < m_polys[i].size(); j++ )
928  {
929  ss << m_polys[i][j].PointCount() << "\n";
930  for( int v = 0; v < m_polys[i][j].PointCount(); v++ )
931  ss << m_polys[i][j].CPoint( v ).x << " " << m_polys[i][j].CPoint( v ).y << "\n";
932  }
933  ss << "\n";
934  }
935 
936  return ss.str();
937 }
938 
939 
940 bool SHAPE_POLY_SET::Parse( std::stringstream& aStream )
941 {
942  std::string tmp;
943 
944  aStream >> tmp;
945 
946  if( tmp != "polyset" )
947  return false;
948 
949  aStream >> tmp;
950 
951  int n_polys = atoi( tmp.c_str() );
952 
953  if( n_polys < 0 )
954  return false;
955 
956  for( int i = 0; i < n_polys; i++ )
957  {
958  POLYGON paths;
959 
960  aStream >> tmp;
961 
962  if( tmp != "poly" )
963  return false;
964 
965  aStream >> tmp;
966  int n_outlines = atoi( tmp.c_str() );
967 
968  if( n_outlines < 0 )
969  return false;
970 
971  for( int j = 0; j < n_outlines; j++ )
972  {
973  SHAPE_LINE_CHAIN outline;
974 
975  outline.SetClosed( true );
976 
977  aStream >> tmp;
978  int n_vertices = atoi( tmp.c_str() );
979  for( int v = 0; v < n_vertices; v++ )
980  {
981  VECTOR2I p;
982 
983  aStream >> tmp; p.x = atoi( tmp.c_str() );
984  aStream >> tmp; p.y = atoi( tmp.c_str() );
985  outline.Append( p );
986  }
987 
988  paths.push_back( outline );
989  }
990 
991  m_polys.push_back( paths );
992  }
993  return true;
994 }
995 
996 
997 const BOX2I SHAPE_POLY_SET::BBox( int aClearance ) const
998 {
999  BOX2I bb;
1000 
1001  for( unsigned i = 0; i < m_polys.size(); i++ )
1002  {
1003  if( i == 0 )
1004  bb = m_polys[i][0].BBox();
1005  else
1006  bb.Merge( m_polys[i][0].BBox() );
1007  }
1008 
1009  bb.Inflate( aClearance );
1010  return bb;
1011 }
1012 
1013 
1014 bool SHAPE_POLY_SET::PointOnEdge( const VECTOR2I& aP ) const
1015 {
1016  // Iterate through all the polygons in the set
1017  for( const POLYGON& polygon : m_polys )
1018  {
1019  // Iterate through all the line chains in the polygon
1020  for( const SHAPE_LINE_CHAIN& lineChain : polygon )
1021  {
1022  if( lineChain.PointOnEdge( aP ) )
1023  return true;
1024  }
1025  }
1026 
1027  return false;
1028 }
1029 
1030 
1031 bool SHAPE_POLY_SET::Collide( const VECTOR2I& aP, int aClearance ) const
1032 {
1033  SHAPE_POLY_SET polySet = SHAPE_POLY_SET( *this );
1034 
1035  // Inflate the polygon if necessary.
1036  if( aClearance > 0 )
1037  {
1038  // fixme: the number of arc segments should not be hardcoded
1039  polySet.Inflate( aClearance, 8 );
1040  }
1041 
1042  // There is a collision if and only if the point is inside of the polygon.
1043  return polySet.Contains( aP );
1044 }
1045 
1046 
1048 {
1049  m_polys.clear();
1050 }
1051 
1052 
1053 void SHAPE_POLY_SET::RemoveContour( int aContourIdx, int aPolygonIdx )
1054 {
1055  // Default polygon is the last one
1056  if( aPolygonIdx < 0 )
1057  aPolygonIdx += m_polys.size();
1058 
1059  m_polys[aPolygonIdx].erase( m_polys[aPolygonIdx].begin() + aContourIdx );
1060 }
1061 
1062 
1064 {
1065  int removed = 0;
1066 
1067  ITERATOR iterator = IterateWithHoles();
1068 
1069  VECTOR2I contourStart = *iterator;
1070  VECTOR2I segmentStart, segmentEnd;
1071 
1072  VERTEX_INDEX indexStart;
1073 
1074  while( iterator )
1075  {
1076  // Obtain first point and its index
1077  segmentStart = *iterator;
1078  indexStart = iterator.GetIndex();
1079 
1080  // Obtain last point
1081  if( iterator.IsEndContour() )
1082  {
1083  segmentEnd = contourStart;
1084 
1085  // Advance
1086  iterator++;
1087 
1088  if( iterator )
1089  contourStart = *iterator;
1090  }
1091  else
1092  {
1093  // Advance
1094  iterator++;
1095 
1096  if( iterator )
1097  segmentEnd = *iterator;
1098  }
1099 
1100  // Remove segment start if both points are equal
1101  if( segmentStart == segmentEnd )
1102  {
1103  RemoveVertex( indexStart );
1104  removed++;
1105 
1106  // Advance the iterator one position, as there is one vertex less.
1107  if( iterator )
1108  iterator++;
1109  }
1110  }
1111 
1112  return removed;
1113 }
1114 
1115 
1117 {
1118  m_polys.erase( m_polys.begin() + aIdx );
1119 }
1120 
1121 
1123 {
1124  m_polys.insert( m_polys.end(), aSet.m_polys.begin(), aSet.m_polys.end() );
1125 }
1126 
1127 
1128 void SHAPE_POLY_SET::Append( const VECTOR2I& aP, int aOutline, int aHole )
1129 {
1130  Append( aP.x, aP.y, aOutline, aHole );
1131 }
1132 
1133 
1135  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1136 {
1137  // Shows whether there was a collision
1138  bool collision = false;
1139 
1140  // Difference vector between each vertex and aPoint.
1141  VECTOR2D delta;
1142  double distance, clearance;
1143 
1144  // Convert clearance to double for precission when comparing distances
1145  clearance = aClearance;
1146 
1147  for( ITERATOR iterator = IterateWithHoles(); iterator; iterator++ )
1148  {
1149  // Get the difference vector between current vertex and aPoint
1150  delta = *iterator - aPoint;
1151 
1152  // Compute distance
1153  distance = delta.EuclideanNorm();
1154 
1155  // Check for collisions
1156  if( distance <= clearance )
1157  {
1158  collision = true;
1159 
1160  // Update aClearance to look for closer vertices
1161  clearance = distance;
1162 
1163  // Store the indices that identify the vertex
1164  aClosestVertex = iterator.GetIndex();
1165  }
1166  }
1167 
1168  return collision;
1169 }
1170 
1171 
1173  SHAPE_POLY_SET::VERTEX_INDEX& aClosestVertex, int aClearance )
1174 {
1175  // Shows whether there was a collision
1176  bool collision = false;
1177 
1178  SEGMENT_ITERATOR iterator;
1179 
1180  for( iterator = IterateSegmentsWithHoles(); iterator; iterator++ )
1181  {
1182  SEG currentSegment = *iterator;
1183  int distance = currentSegment.Distance( aPoint );
1184 
1185  // Check for collisions
1186  if( distance <= aClearance )
1187  {
1188  collision = true;
1189 
1190  // Update aClearance to look for closer edges
1191  aClearance = distance;
1192 
1193  // Store the indices that identify the vertex
1194  aClosestVertex = iterator.GetIndex();
1195  }
1196  }
1197 
1198  return collision;
1199 }
1200 
1201 
1202 bool SHAPE_POLY_SET::Contains( const VECTOR2I& aP, int aSubpolyIndex ) const
1203 {
1204  if( m_polys.size() == 0 ) // empty set?
1205  return false;
1206 
1207  // If there is a polygon specified, check the condition against that polygon
1208  if( aSubpolyIndex >= 0 )
1209  return containsSingle( aP, aSubpolyIndex );
1210 
1211  // In any other case, check it against all polygons in the set
1212  for( int polygonIdx = 0; polygonIdx < OutlineCount(); polygonIdx++ )
1213  {
1214  if( containsSingle( aP, polygonIdx ) )
1215  return true;
1216  }
1217 
1218  return false;
1219 
1220 }
1221 
1222 
1223 void SHAPE_POLY_SET::RemoveVertex( int aGlobalIndex )
1224 {
1225  VERTEX_INDEX index;
1226 
1227  // Assure the to be removed vertex exists, abort otherwise
1228  if( GetRelativeIndices( aGlobalIndex, &index ) )
1229  RemoveVertex( index );
1230  else
1231  throw( std::out_of_range( "aGlobalIndex-th vertex does not exist" ) );
1232 }
1233 
1234 
1236 {
1237  m_polys[aIndex.m_polygon][aIndex.m_contour].Remove( aIndex.m_vertex );
1238 }
1239 
1240 
1241 bool SHAPE_POLY_SET::containsSingle( const VECTOR2I& aP, int aSubpolyIndex ) const
1242 {
1243  // Check that the point is inside the outline
1244  if( pointInPolygon( aP, m_polys[aSubpolyIndex][0] ) )
1245  {
1246  // Check that the point is not in any of the holes
1247  for( int holeIdx = 0; holeIdx < HoleCount( aSubpolyIndex ); holeIdx++ )
1248  {
1249  const SHAPE_LINE_CHAIN hole = CHole( aSubpolyIndex, holeIdx );
1250  // If the point is inside a hole (and not on its edge),
1251  // it is outside of the polygon
1252  if( pointInPolygon( aP, hole ) && !hole.PointOnEdge( aP ) )
1253  return false;
1254  }
1255 
1256  return true;
1257  }
1258 
1259  return false;
1260 }
1261 
1262 
1263 bool SHAPE_POLY_SET::pointInPolygon( const VECTOR2I& aP, const SHAPE_LINE_CHAIN& aPath ) const
1264 {
1265  int result = 0;
1266  int cnt = aPath.PointCount();
1267 
1268  if ( !aPath.BBox().Contains( aP ) ) // test with bounding box first
1269  return false;
1270 
1271  if( cnt < 3 )
1272  return false;
1273 
1274  VECTOR2I ip = aPath.CPoint( 0 );
1275 
1276  for( int i = 1; i <= cnt; ++i )
1277  {
1278  VECTOR2I ipNext = ( i == cnt ? aPath.CPoint( 0 ) : aPath.CPoint( i ) );
1279 
1280  if( ipNext.y == aP.y )
1281  {
1282  if( ( ipNext.x == aP.x ) || ( ip.y == aP.y &&
1283  ( ( ipNext.x > aP.x ) == ( ip.x < aP.x ) ) ) )
1284  return true;
1285  }
1286 
1287  if( ( ip.y < aP.y ) != ( ipNext.y < aP.y ) )
1288  {
1289  if( ip.x >= aP.x )
1290  {
1291  if( ipNext.x > aP.x )
1292  result = 1 - result;
1293  else
1294  {
1295  int64_t d = (int64_t)( ip.x - aP.x ) * (int64_t)( ipNext.y - aP.y ) -
1296  (int64_t)( ipNext.x - aP.x ) * (int64_t)( ip.y - aP.y );
1297 
1298  if( !d )
1299  return true;
1300 
1301  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1302  result = 1 - result;
1303  }
1304  }
1305  else
1306  {
1307  if( ipNext.x > aP.x )
1308  {
1309  int64_t d = (int64_t)( ip.x - aP.x ) * (int64_t)( ipNext.y - aP.y ) -
1310  (int64_t)( ipNext.x - aP.x ) * (int64_t)( ip.y - aP.y );
1311 
1312  if( !d )
1313  return true;
1314 
1315  if( ( d > 0 ) == ( ipNext.y > ip.y ) )
1316  result = 1 - result;
1317  }
1318  }
1319  }
1320 
1321  ip = ipNext;
1322  }
1323 
1324  return result ? true : false;
1325 }
1326 
1327 
1328 void SHAPE_POLY_SET::Move( const VECTOR2I& aVector )
1329 {
1330  for( POLYGON &poly : m_polys )
1331  {
1332  for( SHAPE_LINE_CHAIN &path : poly )
1333  {
1334  path.Move( aVector );
1335  }
1336  }
1337 }
1338 
1339 
1341 {
1342  int c = 0;
1343 
1344  for( const POLYGON& poly : m_polys )
1345  {
1346  for( const SHAPE_LINE_CHAIN& path : poly )
1347  {
1348  c += path.PointCount();
1349  }
1350  }
1351 
1352  return c;
1353 }
1354 
1355 
1356 SHAPE_POLY_SET::POLYGON SHAPE_POLY_SET::ChamferPolygon( unsigned int aDistance, int aIndex )
1357 {
1358  return chamferFilletPolygon( CORNER_MODE::CHAMFERED, aDistance, aIndex );
1359 }
1360 
1361 
1363  unsigned int aSegments,
1364  int aIndex )
1365 {
1366  return chamferFilletPolygon(CORNER_MODE::FILLETED, aRadius, aIndex, aSegments );
1367 }
1368 
1369 
1370 int SHAPE_POLY_SET::DistanceToPolygon( VECTOR2I aPoint, int aPolygonIndex )
1371 {
1372  // We calculate the min dist between the segment and each outline segment
1373  // However, if the segment to test is inside the outline, and does not cross
1374  // any edge, it can be seen outside the polygon.
1375  // Therefore test if a segment end is inside ( testing only one end is enough )
1376  if( containsSingle( aPoint, aPolygonIndex ) )
1377  return 0;
1378 
1379  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1380 
1381  SEG polygonEdge = *iterator;
1382  int minDistance = polygonEdge.Distance( aPoint );
1383 
1384  for( iterator++; iterator && minDistance > 0; iterator++ )
1385  {
1386  polygonEdge = *iterator;
1387 
1388  int currentDistance = polygonEdge.Distance( aPoint );
1389 
1390  if( currentDistance < minDistance )
1391  minDistance = currentDistance;
1392  }
1393 
1394  return minDistance;
1395 }
1396 
1397 
1398 int SHAPE_POLY_SET::DistanceToPolygon( SEG aSegment, int aPolygonIndex, int aSegmentWidth )
1399 {
1400  // We calculate the min dist between the segment and each outline segment
1401  // However, if the segment to test is inside the outline, and does not cross
1402  // any edge, it can be seen outside the polygon.
1403  // Therefore test if a segment end is inside ( testing only one end is enough )
1404  if( containsSingle( aSegment.A, aPolygonIndex ) )
1405  return 0;
1406 
1407  SEGMENT_ITERATOR iterator = IterateSegmentsWithHoles( aPolygonIndex );
1408 
1409  SEG polygonEdge = *iterator;
1410  int minDistance = polygonEdge.Distance( aSegment );
1411 
1412  for( iterator++; iterator && minDistance > 0; iterator++ )
1413  {
1414  polygonEdge = *iterator;
1415 
1416  int currentDistance = polygonEdge.Distance( aSegment );
1417 
1418  if( currentDistance < minDistance )
1419  minDistance = currentDistance;
1420  }
1421 
1422  // Take into account the width of the segment
1423  if( aSegmentWidth > 0 )
1424  minDistance -= aSegmentWidth/2;
1425 
1426  // Return the maximum of minDistance and zero
1427  return minDistance < 0 ? 0 : minDistance;
1428 }
1429 
1430 
1432 {
1433  int currentDistance;
1434  int minDistance = DistanceToPolygon( aPoint, 0 );
1435 
1436  // Iterate through all the polygons and get the minimum distance.
1437  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1438  {
1439  currentDistance = DistanceToPolygon( aPoint, polygonIdx );
1440 
1441  if( currentDistance < minDistance )
1442  minDistance = currentDistance;
1443  }
1444 
1445  return minDistance;
1446 }
1447 
1448 
1449 int SHAPE_POLY_SET::Distance( SEG aSegment, int aSegmentWidth )
1450 {
1451  int currentDistance;
1452  int minDistance = DistanceToPolygon( aSegment, 0 );
1453 
1454  // Iterate through all the polygons and get the minimum distance.
1455  for( unsigned int polygonIdx = 1; polygonIdx < m_polys.size(); polygonIdx++ )
1456  {
1457  currentDistance = DistanceToPolygon( aSegment, polygonIdx, aSegmentWidth );
1458 
1459  if( currentDistance < minDistance )
1460  minDistance = currentDistance;
1461  }
1462 
1463  return minDistance;
1464 }
1465 
1466 
1467 bool SHAPE_POLY_SET::IsVertexInHole( int aGlobalIdx )
1468 {
1469  VERTEX_INDEX index;
1470 
1471  // Get the polygon and contour where the vertex is. If the vertex does not exist, return false
1472  if( !GetRelativeIndices( aGlobalIdx, &index ) )
1473  return false;
1474 
1475  // The contour is a hole if its index is greater than zero
1476  return index.m_contour > 0;
1477 }
1478 
1479 
1481 {
1482  SHAPE_POLY_SET chamfered;
1483 
1484  for( unsigned int polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1485  chamfered.m_polys.push_back( ChamferPolygon( aDistance, polygonIdx ) );
1486 
1487  return chamfered;
1488 }
1489 
1490 
1491 SHAPE_POLY_SET SHAPE_POLY_SET::Fillet( int aRadius, int aSegments )
1492 {
1493  SHAPE_POLY_SET filleted;
1494 
1495  for( size_t polygonIdx = 0; polygonIdx < m_polys.size(); polygonIdx++ )
1496  filleted.m_polys.push_back( FilletPolygon( aRadius, aSegments, polygonIdx ) );
1497 
1498  return filleted;
1499 }
1500 
1501 
1503  unsigned int aDistance,
1504  int aIndex,
1505  int aSegments )
1506 {
1507  // Null segments create serious issues in calculations. Remove them:
1509 
1510  SHAPE_POLY_SET::POLYGON currentPoly = Polygon( aIndex );
1511  SHAPE_POLY_SET::POLYGON newPoly;
1512 
1513  // If the chamfering distance is zero, then the polygon remain intact.
1514  if( aDistance == 0 )
1515  {
1516  return currentPoly;
1517  }
1518 
1519  // Iterate through all the contours (outline and holes) of the polygon.
1520  for( SHAPE_LINE_CHAIN &currContour : currentPoly )
1521  {
1522  // Generate a new contour in the new polygon
1523  SHAPE_LINE_CHAIN newContour;
1524 
1525  // Iterate through the vertices of the contour
1526  for( int currVertex = 0; currVertex < currContour.PointCount(); currVertex++ )
1527  {
1528  // Current vertex
1529  int x1 = currContour.Point( currVertex ).x;
1530  int y1 = currContour.Point( currVertex ).y;
1531 
1532  // Indices for previous and next vertices.
1533  int prevVertex;
1534  int nextVertex;
1535 
1536  // Previous and next vertices indices computation. Necessary to manage the edge cases.
1537 
1538  // Previous vertex is the last one if the current vertex is the first one
1539  prevVertex = currVertex == 0 ? currContour.PointCount() - 1 : currVertex - 1;
1540 
1541  // next vertex is the first one if the current vertex is the last one.
1542  nextVertex = currVertex == currContour.PointCount() - 1 ? 0 : currVertex + 1;
1543 
1544  // Previous vertex computation
1545  double xa = currContour.Point( prevVertex ).x - x1;
1546  double ya = currContour.Point( prevVertex ).y - y1;
1547 
1548  // Next vertex computation
1549  double xb = currContour.Point( nextVertex ).x - x1;
1550  double yb = currContour.Point( nextVertex ).y - y1;
1551 
1552  // Compute the new distances
1553  double lena = hypot( xa, ya );
1554  double lenb = hypot( xb, yb );
1555 
1556  // Make the final computations depending on the mode selected, chamfered or filleted.
1557  if( aMode == CORNER_MODE::CHAMFERED )
1558  {
1559  double distance = aDistance;
1560 
1561  // Chamfer one half of an edge at most
1562  if( 0.5 * lena < distance )
1563  distance = 0.5 * lena;
1564 
1565  if( 0.5 * lenb < distance )
1566  distance = 0.5 * lenb;
1567 
1568  int nx1 = KiROUND( distance * xa / lena );
1569  int ny1 = KiROUND( distance * ya / lena );
1570 
1571  newContour.Append( x1 + nx1, y1 + ny1 );
1572 
1573  int nx2 = KiROUND( distance * xb / lenb );
1574  int ny2 = KiROUND( distance * yb / lenb );
1575 
1576  newContour.Append( x1 + nx2, y1 + ny2 );
1577  }
1578  else // CORNER_MODE = FILLETED
1579  {
1580  double cosine = ( xa * xb + ya * yb ) / ( lena * lenb );
1581 
1582  double radius = aDistance;
1583  double denom = sqrt( 2.0 / ( 1 + cosine ) - 1 );
1584 
1585  // Do nothing in case of parallel edges
1586  if( std::isinf( denom ) )
1587  continue;
1588 
1589  // Limit rounding distance to one half of an edge
1590  if( 0.5 * lena * denom < radius )
1591  radius = 0.5 * lena * denom;
1592 
1593  if( 0.5 * lenb * denom < radius )
1594  radius = 0.5 * lenb * denom;
1595 
1596  // Calculate fillet arc absolute center point (xc, yx)
1597  double k = radius / sqrt( .5 * ( 1 - cosine ) );
1598  double lenab = sqrt( ( xa / lena + xb / lenb ) * ( xa / lena + xb / lenb ) +
1599  ( ya / lena + yb / lenb ) * ( ya / lena + yb / lenb ) );
1600  double xc = x1 + k * ( xa / lena + xb / lenb ) / lenab;
1601  double yc = y1 + k * ( ya / lena + yb / lenb ) / lenab;
1602 
1603  // Calculate arc start and end vectors
1604  k = radius / sqrt( 2 / ( 1 + cosine ) - 1 );
1605  double xs = x1 + k * xa / lena - xc;
1606  double ys = y1 + k * ya / lena - yc;
1607  double xe = x1 + k * xb / lenb - xc;
1608  double ye = y1 + k * yb / lenb - yc;
1609 
1610  // Cosine of arc angle
1611  double argument = ( xs * xe + ys * ye ) / ( radius * radius );
1612 
1613  // Make sure the argument is in [-1,1], interval in which the acos function is
1614  // defined
1615  if( argument < -1 )
1616  argument = -1;
1617  else if( argument > 1 )
1618  argument = 1;
1619 
1620  double arcAngle = acos( argument );
1621 
1622  // Calculate the number of segments
1623  unsigned int segments = ceil( (double) aSegments * ( arcAngle / ( 2 * M_PI ) ) );
1624 
1625  double deltaAngle = arcAngle / segments;
1626  double startAngle = atan2( -ys, xs );
1627 
1628  // Flip arc for inner corners
1629  if( xa * yb - ya * xb <= 0 )
1630  deltaAngle *= -1;
1631 
1632  double nx = xc + xs;
1633  double ny = yc + ys;
1634 
1635  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1636 
1637  // Store the previous added corner to make a sanity check
1638  int prevX = KiROUND( nx );
1639  int prevY = KiROUND( ny );
1640 
1641  for( unsigned int j = 0; j < segments; j++ )
1642  {
1643  nx = xc + cos( startAngle + (j + 1) * deltaAngle ) * radius;
1644  ny = yc - sin( startAngle + (j + 1) * deltaAngle ) * radius;
1645 
1646  // Sanity check: the rounding can produce repeated corners; do not add them.
1647  if( KiROUND( nx ) != prevX || KiROUND( ny ) != prevY )
1648  {
1649  newContour.Append( KiROUND( nx ), KiROUND( ny ) );
1650  prevX = KiROUND( nx );
1651  prevY = KiROUND( ny );
1652  }
1653  }
1654  }
1655  }
1656 
1657  // Close the current contour and add it the new polygon
1658  newContour.SetClosed( true );
1659  newPoly.push_back( newContour );
1660  }
1661 
1662  return newPoly;
1663 }
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, ...
CITER next(CITER it)
Definition: ptree.cpp:130
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
bool GetNeighbourIndexes(int aGlobalIndex, int *aPrevious, int *aNext)
Returns the global indexes of the previous and the next corner of the aGlobalIndex-th corner of a con...
void SetClosed(bool aClosed)
Function SetClosed()
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.
int Distance(VECTOR2I point)
Function DistanceToPolygon computes the minimum distance between aPoint and all the polygons in the s...
VECTOR2I A
Definition: seg.h:47
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:185
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)