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