KiCad PCB EDA Suite
convert_basic_shapes_to_polygon.cpp
Go to the documentation of this file.
1 
4 /*
5  * This program source code file is part of KiCad, a free EDA CAD application.
6  *
7  * Copyright (C) 2018 Jean-Pierre Charras, jp.charras at wanadoo.fr
8  * Copyright (C) 1992-2021 KiCad Developers, see AUTHORS.txt for contributors.
9  *
10  * This program is free software; you can redistribute it and/or
11  * modify it under the terms of the GNU General Public License
12  * as published by the Free Software Foundation; either version 2
13  * of the License, or (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU General Public License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program; if not, you may find one here:
22  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
23  * or you may search the http://www.gnu.org website for the version 2 license,
24  * or you may write to the Free Software Foundation, Inc.,
25  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
26  */
27 
28 #include <algorithm> // for max, min
29 #include <bitset> // for bitset::count
30 #include <math.h> // for atan2
31 #include <type_traits> // for swap
32 
35 #include <geometry/shape_line_chain.h> // for SHAPE_LINE_CHAIN
36 #include <geometry/shape_poly_set.h> // for SHAPE_POLY_SET, SHAPE_POLY_SE...
37 #include <math/util.h>
38 #include <math/vector2d.h> // for VECTOR2I
39 #include <trigo.h>
40 
41 
42 void TransformCircleToPolygon( SHAPE_LINE_CHAIN& aCornerBuffer, const wxPoint& aCenter, int aRadius,
43  int aError, ERROR_LOC aErrorLoc, int aMinSegCount )
44 {
45  wxPoint corner_position;
46  int numSegs = GetArcToSegmentCount( aRadius, aError, 360.0 );
47  numSegs = std::max( aMinSegCount, numSegs );
48 
49  // The shape will be built with a even number of segs. Reason: the horizontal
50  // diameter begins and ends to points on the actual circle, or circle
51  // expanded by aError if aErrorLoc == ERROR_OUTSIDE.
52  // This is used by Arc to Polygon shape convert.
53  if( numSegs & 1 )
54  numSegs++;
55 
56  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
57  int radius = aRadius;
58 
59  if( aErrorLoc == ERROR_OUTSIDE )
60  {
61  // The outer radius should be radius+aError
62  // Recalculate the actual approx error, as it can be smaller than aError
63  // because numSegs is clamped to a minimal value
64  int actual_delta_radius = CircleToEndSegmentDeltaRadius( radius, numSegs );
65  radius += GetCircleToPolyCorrection( actual_delta_radius );
66  }
67 
68  for( int angle = 0; angle < 3600; angle += delta )
69  {
70  corner_position.x = radius;
71  corner_position.y = 0;
72  RotatePoint( &corner_position, angle );
73  corner_position += aCenter;
74  aCornerBuffer.Append( corner_position.x, corner_position.y );
75  }
76 
77  aCornerBuffer.SetClosed( true );
78 }
79 
80 
81 void TransformCircleToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aCenter, int aRadius,
82  int aError, ERROR_LOC aErrorLoc, int aMinSegCount )
83 {
84  wxPoint corner_position;
85  int numSegs = GetArcToSegmentCount( aRadius, aError, 360.0 );
86  numSegs = std::max( aMinSegCount, numSegs);
87 
88  // The shape will be built with a even number of segs. Reason: the horizontal
89  // diameter begins and ends to points on the actual circle, or circle
90  // expanded by aError if aErrorLoc == ERROR_OUTSIDE.
91  // This is used by Arc to Polygon shape convert.
92  if( numSegs & 1 )
93  numSegs++;
94 
95  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
96  int radius = aRadius;
97 
98  if( aErrorLoc == ERROR_OUTSIDE )
99  {
100  // The outer radius should be radius+aError
101  // Recalculate the actual approx error, as it can be smaller than aError
102  // because numSegs is clamped to a minimal value
103  int actual_delta_radius = CircleToEndSegmentDeltaRadius( radius, numSegs );
104  radius += GetCircleToPolyCorrection( actual_delta_radius );
105  }
106 
107  aCornerBuffer.NewOutline();
108 
109  for( int angle = 0; angle < 3600; angle += delta )
110  {
111  corner_position.x = radius;
112  corner_position.y = 0;
113  RotatePoint( &corner_position, angle );
114  corner_position += aCenter;
115  aCornerBuffer.Append( corner_position.x, corner_position.y );
116  }
117 
118  // Finish circle
119  corner_position.x = radius;
120  corner_position.y = 0;
121  corner_position += aCenter;
122  aCornerBuffer.Append( corner_position.x, corner_position.y );
123 }
124 
125 
126 void TransformOvalToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aStart,
127  const wxPoint& aEnd, int aWidth, int aError, ERROR_LOC aErrorLoc,
128  int aMinSegCount )
129 {
130  // To build the polygonal shape outside the actual shape, we use a bigger
131  // radius to build rounded ends.
132  // However, the width of the segment is too big.
133  // so, later, we will clamp the polygonal shape with the bounding box
134  // of the segment.
135  int radius = aWidth / 2;
136  int numSegs = GetArcToSegmentCount( radius, aError, 360.0 );
137  numSegs = std::max( aMinSegCount, numSegs );
138 
139  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
140 
141  if( aErrorLoc == ERROR_OUTSIDE )
142  {
143  // The outer radius should be radius+aError
144  // Recalculate the actual approx error, as it can be smaller than aError
145  // because numSegs is clamped to a minimal value
146  int actual_delta_radius = CircleToEndSegmentDeltaRadius( radius, numSegs );
147  int correction = GetCircleToPolyCorrection( actual_delta_radius );
148  radius += correction;
149  }
150 
151  // end point is the coordinate relative to aStart
152  wxPoint endp = aEnd - aStart;
153  wxPoint startp = aStart;
154  wxPoint corner;
155  SHAPE_POLY_SET polyshape;
156 
157  polyshape.NewOutline();
158 
159  // normalize the position in order to have endp.x >= 0
160  // it makes calculations more easy to understand
161  if( endp.x < 0 )
162  {
163  endp = aStart - aEnd;
164  startp = aEnd;
165  }
166 
167  // delta_angle is in radian
168  double delta_angle = atan2( (double)endp.y, (double)endp.x );
169  int seg_len = KiROUND( EuclideanNorm( endp ) );
170 
171  // Compute the outlines of the segment, and creates a polygon
172  // Note: the polygonal shape is built from the equivalent horizontal
173  // segment starting at {0,0}, and ending at {seg_len,0}
174 
175  // add right rounded end:
176 
177  for( int angle = 0; angle < 1800; angle += delta )
178  {
179  corner = wxPoint( 0, radius );
180  RotatePoint( &corner, angle );
181  corner.x += seg_len;
182  polyshape.Append( corner.x, corner.y );
183  }
184 
185  // Finish arc:
186  corner = wxPoint( seg_len, -radius );
187  polyshape.Append( corner.x, corner.y );
188 
189  // add left rounded end:
190  for( int angle = 0; angle < 1800; angle += delta )
191  {
192  corner = wxPoint( 0, -radius );
193  RotatePoint( &corner, angle );
194  polyshape.Append( corner.x, corner.y );
195  }
196 
197  // Finish arc:
198  corner = wxPoint( 0, radius );
199  polyshape.Append( corner.x, corner.y );
200 
201  // Now trim the edges of the polygonal shape which will be slightly outside the
202  // track width.
203  SHAPE_POLY_SET bbox;
204  bbox.NewOutline();
205  // Build the bbox (a horizontal rectangle).
206  int halfwidth = aWidth / 2; // Use the exact segment width for the bbox height
207  corner.x = -radius - 2; // use a bbox width slightly bigger to avoid
208  // creating useless corner at segment ends
209  corner.y = halfwidth;
210  bbox.Append( corner.x, corner.y );
211  corner.y = -halfwidth;
212  bbox.Append( corner.x, corner.y );
213  corner.x = radius + seg_len + 2;
214  bbox.Append( corner.x, corner.y );
215  corner.y = halfwidth;
216  bbox.Append( corner.x, corner.y );
217 
218  // Now, clamp the shape
220  // Note the final polygon is a simple, convex polygon with no hole
221  // due to the shape of initial polygons
222 
223  // Rotate and move the polygon to its right location
224  polyshape.Rotate( delta_angle, VECTOR2I( 0, 0 ) );
225  polyshape.Move( startp );
226 
227  aCornerBuffer.Append( polyshape);
228 }
229 
230 
232 {
234  int m_radius;
235  ROUNDED_CORNER( int x, int y ) : m_position( VECTOR2I( x, y ) ), m_radius( 0 ) {}
236  ROUNDED_CORNER( int x, int y, int radius ) : m_position( VECTOR2I( x, y ) ), m_radius( radius ) {}
237 };
238 
239 
240 // Corner List requirements: no concave shape, corners in clockwise order, no duplicate corners
241 void CornerListToPolygon( SHAPE_POLY_SET& outline, std::vector<ROUNDED_CORNER>& aCorners,
242  int aInflate, int aError, ERROR_LOC aErrorLoc )
243 {
244  assert( aInflate >= 0 );
245  outline.NewOutline();
246  VECTOR2I incoming = aCorners[0].m_position - aCorners.back().m_position;
247 
248  for( int n = 0, count = aCorners.size(); n < count; n++ )
249  {
250  ROUNDED_CORNER& cur = aCorners[n];
251  ROUNDED_CORNER& next = aCorners[( n + 1 ) % count];
252  VECTOR2I outgoing = next.m_position - cur.m_position;
253 
254  if( !( aInflate || cur.m_radius ) )
255  outline.Append( cur.m_position );
256  else
257  {
258  VECTOR2I cornerPosition = cur.m_position;
259  int endAngle, radius = cur.m_radius;
260  double tanAngle2;
261 
262  if( ( incoming.x == 0 && outgoing.y == 0 ) || ( incoming.y == 0 && outgoing.x == 0 ) )
263  {
264  endAngle = 900;
265  tanAngle2 = 1.0;
266  }
267  else
268  {
269  double cosNum = (double) incoming.x * outgoing.x + (double) incoming.y * outgoing.y;
270  double cosDen = (double) incoming.EuclideanNorm() * outgoing.EuclideanNorm();
271  double angle = acos( cosNum / cosDen );
272  tanAngle2 = tan( ( M_PI - angle ) / 2 );
273  endAngle = RAD2DECIDEG( angle );
274  }
275 
276  if( aInflate )
277  {
278  radius += aInflate;
279  cornerPosition += incoming.Resize( aInflate / tanAngle2 )
280  + incoming.Perpendicular().Resize( -aInflate );
281  }
282 
283  // Ensure 16+ segments per 360deg and ensure first & last segment are the same size
284  int numSegs = std::max( 16, GetArcToSegmentCount( radius, aError, 360.0 ) );
285  int angDelta = 3600 / numSegs;
286  int lastSegLen = endAngle % angDelta; // or 0 if last seg length is angDelta
287  int angPos = lastSegLen ? ( angDelta + lastSegLen ) / 2 : angDelta;
288 
289  double arcTransitionDistance = radius / tanAngle2;
290  VECTOR2I arcStart = cornerPosition - incoming.Resize( arcTransitionDistance );
291  VECTOR2I arcCenter = arcStart + incoming.Perpendicular().Resize( radius );
292  VECTOR2I arcEnd, arcStartOrigin;
293 
294  if( aErrorLoc == ERROR_INSIDE )
295  {
296  arcEnd = SEG( cornerPosition, arcCenter ).ReflectPoint( arcStart );
297  arcStartOrigin = arcStart - arcCenter;
298  outline.Append( arcStart );
299  }
300  else
301  {
302  // The outer radius should be radius+aError, recalculate because numSegs is clamped
303  int actualDeltaRadius = CircleToEndSegmentDeltaRadius( radius, numSegs );
304  int radiusExtend = GetCircleToPolyCorrection( actualDeltaRadius );
305  arcStart += incoming.Perpendicular().Resize( -radiusExtend );
306  arcStartOrigin = arcStart - arcCenter;
307 
308  // To avoid "ears", we only add segments crossing/within the non-rounded outline
309  // Note: outlineIn is short and must be treated as defining an infinite line
310  SEG outlineIn( cornerPosition - incoming, cornerPosition );
311  VECTOR2I prevPt = arcStart;
312  arcEnd = cornerPosition; // default if no points within the outline are found
313 
314  while( angPos < endAngle )
315  {
316  VECTOR2I pt = arcStartOrigin;
317  RotatePoint( pt, -angPos );
318  pt += arcCenter;
319  angPos += angDelta;
320 
321  if( outlineIn.Side( pt ) > 0 )
322  {
323  VECTOR2I intersect = outlineIn.IntersectLines( SEG( prevPt, pt ) ).get();
324  outline.Append( intersect );
325  outline.Append( pt );
326  arcEnd = SEG( cornerPosition, arcCenter ).ReflectPoint( intersect );
327  break;
328  }
329 
330  endAngle -= angDelta; // if skipping first, also skip last
331  prevPt = pt;
332  }
333  }
334 
335  for( ; angPos < endAngle; angPos += angDelta )
336  {
337  VECTOR2I pt = arcStartOrigin;
338  RotatePoint( pt, -angPos );
339  outline.Append( pt + arcCenter );
340  }
341 
342  outline.Append( arcEnd );
343  }
344 
345  incoming = outgoing;
346  }
347 }
348 
349 
350 void CornerListRemoveDuplicates( std::vector<ROUNDED_CORNER>& aCorners )
351 {
352  VECTOR2I prev = aCorners[0].m_position;
353 
354  for( int pos = aCorners.size() - 1; pos >= 0; pos-- )
355  {
356  if( aCorners[pos].m_position == prev )
357  aCorners.erase( aCorners.begin() + pos );
358  else
359  prev = aCorners[pos].m_position;
360  }
361 }
362 
363 
364 void TransformTrapezoidToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aPosition,
365  const wxSize& aSize, double aRotation, int aDeltaX, int aDeltaY,
366  int aInflate, int aError, ERROR_LOC aErrorLoc )
367 {
368  SHAPE_POLY_SET outline;
369  wxSize size( aSize / 2 );
370  std::vector<ROUNDED_CORNER> corners;
371 
372  if( aInflate < 0 )
373  {
374  if( !aDeltaX && !aDeltaY ) // rectangle
375  {
376  size.x = std::max( 1, size.x + aInflate );
377  size.y = std::max( 1, size.y + aInflate );
378  }
379  else if( aDeltaX ) // horizontal trapezoid
380  {
381  double slope = (double) aDeltaX / size.x;
382  int yShrink = KiROUND( ( std::hypot( size.x, aDeltaX ) * aInflate ) / size.x );
383  size.y = std::max( 1, size.y + yShrink );
384  size.x = std::max( 1, size.x + aInflate );
385  aDeltaX = KiROUND( size.x * slope );
386 
387  if( aDeltaX > size.y ) // shrinking turned the trapezoid into a triangle
388  {
389  corners.reserve( 3 );
390  corners.push_back( ROUNDED_CORNER( -size.x, -size.y - aDeltaX ) );
391  corners.push_back( ROUNDED_CORNER( KiROUND( size.y / slope ), 0 ) );
392  corners.push_back( ROUNDED_CORNER( -size.x, size.y + aDeltaX ) );
393  }
394  }
395  else // vertical trapezoid
396  {
397  double slope = (double) aDeltaY / size.y;
398  int xShrink = KiROUND( ( std::hypot( size.y, aDeltaY ) * aInflate ) / size.y );
399  size.x = std::max( 1, size.x + xShrink );
400  size.y = std::max( 1, size.y + aInflate );
401  aDeltaY = KiROUND( size.y * slope );
402 
403  if( aDeltaY > size.x )
404  {
405  corners.reserve( 3 );
406  corners.push_back( ROUNDED_CORNER( 0, -KiROUND( size.x / slope ) ) );
407  corners.push_back( ROUNDED_CORNER( size.x + aDeltaY, size.y ) );
408  corners.push_back( ROUNDED_CORNER( -size.x - aDeltaY, size.y ) );
409  }
410  }
411 
412  aInflate = 0;
413  }
414 
415  if( corners.empty() )
416  {
417  corners.reserve( 4 );
418  corners.push_back( ROUNDED_CORNER( -size.x + aDeltaY, -size.y - aDeltaX ) );
419  corners.push_back( ROUNDED_CORNER( size.x - aDeltaY, -size.y + aDeltaX ) );
420  corners.push_back( ROUNDED_CORNER( size.x + aDeltaY, size.y - aDeltaX ) );
421  corners.push_back( ROUNDED_CORNER( -size.x - aDeltaY, size.y + aDeltaX ) );
422 
423  if( aDeltaY == size.x || aDeltaX == size.y )
424  CornerListRemoveDuplicates( corners );
425  }
426 
427  CornerListToPolygon( outline, corners, aInflate, aError, aErrorLoc );
428 
429  if( aRotation != 0.0 )
430  outline.Rotate( DECIDEG2RAD( -aRotation ), VECTOR2I( 0, 0 ) );
431 
432  outline.Move( VECTOR2I( aPosition ) );
433  aCornerBuffer.Append( outline );
434 }
435 
436 
437 void TransformRoundChamferedRectToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aPosition,
438  const wxSize& aSize, double aRotation, int aCornerRadius,
439  double aChamferRatio, int aChamferCorners, int aInflate,
440  int aError, ERROR_LOC aErrorLoc )
441 {
442  SHAPE_POLY_SET outline;
443  wxSize size( aSize / 2 );
444  int chamferCnt = std::bitset<8>( aChamferCorners ).count();
445  double chamferDeduct = 0;
446 
447  if( aInflate < 0 )
448  {
449  size.x = std::max( 1, size.x + aInflate );
450  size.y = std::max( 1, size.y + aInflate );
451  chamferDeduct = aInflate * ( 2.0 - M_SQRT2 );
452  aCornerRadius = std::max( 0, aCornerRadius + aInflate );
453  aInflate = 0;
454  }
455 
456  std::vector<ROUNDED_CORNER> corners;
457  corners.reserve( 4 + chamferCnt );
458  corners.push_back( ROUNDED_CORNER( -size.x, -size.y, aCornerRadius ) );
459  corners.push_back( ROUNDED_CORNER( size.x, -size.y, aCornerRadius ) );
460  corners.push_back( ROUNDED_CORNER( size.x, size.y, aCornerRadius ) );
461  corners.push_back( ROUNDED_CORNER( -size.x, size.y, aCornerRadius ) );
462 
463  if( aChamferCorners )
464  {
465  int shorterSide = std::min( aSize.x, aSize.y );
466  int chamfer = std::max( 0, KiROUND( aChamferRatio * shorterSide + chamferDeduct ) );
469  int sign[8] = { 0, 1, -1, 0, 0, -1, 1, 0 };
470 
471  for( int cc = 0, pos = 0; cc < 4; cc++, pos++ )
472  {
473  if( !( aChamferCorners & chamId[cc] ) )
474  continue;
475 
476  corners[pos].m_radius = 0;
477 
478  if( chamfer == 0 )
479  continue;
480 
481  corners.insert( corners.begin() + pos + 1, corners[pos] );
482  corners[pos].m_position.x += sign[( 2 * cc ) & 7] * chamfer;
483  corners[pos].m_position.y += sign[( 2 * cc - 2 ) & 7] * chamfer;
484  corners[pos + 1].m_position.x += sign[( 2 * cc + 1 ) & 7] * chamfer;
485  corners[pos + 1].m_position.y += sign[( 2 * cc - 1 ) & 7] * chamfer;
486  pos++;
487  }
488 
489  if( chamferCnt > 1 && 2 * chamfer >= shorterSide )
490  CornerListRemoveDuplicates( corners );
491  }
492 
493  CornerListToPolygon( outline, corners, aInflate, aError, aErrorLoc );
494 
495  if( aRotation != 0.0 )
496  outline.Rotate( DECIDEG2RAD( -aRotation ), VECTOR2I( 0, 0 ) );
497 
498  outline.Move( VECTOR2I( aPosition ) );
499  aCornerBuffer.Append( outline );
500 }
501 
502 
503 int ConvertArcToPolyline( SHAPE_LINE_CHAIN& aPolyline, VECTOR2I aCenter, int aRadius,
504  double aStartAngleDeg, double aArcAngleDeg, double aAccuracy,
505  ERROR_LOC aErrorLoc )
506 {
507  double endAngle = aStartAngleDeg + aArcAngleDeg;
508  int n = 2;
509 
510  if( aRadius >= aAccuracy )
511  n = GetArcToSegmentCount( aRadius, aAccuracy, aArcAngleDeg )+1; // n >= 3
512 
513  if( aErrorLoc == ERROR_OUTSIDE )
514  {
515  int seg360 = std::abs( KiROUND( n * 360.0 / aArcAngleDeg ) );
516  int actual_delta_radius = CircleToEndSegmentDeltaRadius( aRadius, seg360 );
517  aRadius += actual_delta_radius;
518  }
519 
520  for( int i = 0; i <= n ; i++ )
521  {
522  double rot = aStartAngleDeg;
523  rot += ( aArcAngleDeg * i ) / n;
524 
525  double x = aCenter.x + aRadius * cos( rot * M_PI / 180.0 );
526  double y = aCenter.y + aRadius * sin( rot * M_PI / 180.0 );
527 
528  aPolyline.Append( KiROUND( x ), KiROUND( y ) );
529  }
530 
531  return n;
532 }
533 
534 
535 void TransformArcToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aStart,
536  const wxPoint& aMid, const wxPoint& aEnd, int aWidth,
537  int aError, ERROR_LOC aErrorLoc )
538 {
539  SHAPE_ARC arc( aStart, aMid, aEnd, aWidth );
540  // Currentlye have currently 2 algos:
541  // the first approximates the thick arc from its outlines
542  // the second approximates the thick arc from segments given by SHAPE_ARC
543  // using SHAPE_ARC::ConvertToPolyline
544  // The actual approximation errors are similar but not exactly the same.
545  //
546  // For now, both algorithms are kept, the second is the initial algo used in Kicad.
547 
548 #if 1
549  // This appproximation convert the 2 ends to polygons, arc outer to polyline
550  // and arc inner to polyline and merge shapes.
551  int radial_offset = ( aWidth + 1 ) / 2;
552 
553  SHAPE_POLY_SET polyshape;
554  std::vector<VECTOR2I> outside_pts;
555 
557  TransformCircleToPolygon( polyshape, aStart, radial_offset, aError, aErrorLoc );
558  TransformCircleToPolygon( polyshape, aEnd, radial_offset, aError, aErrorLoc );
559 
560  // The circle polygon is built with a even number of segments, so the
561  // horizontal diameter has 2 corners on the biggest diameter
562  // Rotate these 2 corners to match the start and ens points of inner and outer
563  // end points of the arc appoximation outlines, build below.
564  // The final shape is much better.
565  double arc_angle_start_deg = arc.GetStartAngle();
566  double arc_angle = arc.GetCentralAngle();
567  double arc_angle_end_deg = arc_angle_start_deg + arc_angle;
568 
569  if( arc_angle_start_deg != 0 && arc_angle_start_deg != 180.0 )
570  polyshape.Outline(0).Rotate( arc_angle_start_deg * M_PI/180.0, aStart );
571 
572  if( arc_angle_end_deg != 0 && arc_angle_end_deg != 180.0 )
573  polyshape.Outline(1).Rotate( arc_angle_end_deg * M_PI/180.0, aEnd );
574 
575  VECTOR2I center = arc.GetCenter();
576  int radius = arc.GetRadius();
577 
578  int arc_outer_radius = radius + radial_offset;
579  int arc_inner_radius = radius - radial_offset;
580  ERROR_LOC errorLocInner = ERROR_OUTSIDE;
581  ERROR_LOC errorLocOuter = ERROR_INSIDE;
582 
583  if( aErrorLoc == ERROR_OUTSIDE )
584  {
585  errorLocInner = ERROR_INSIDE;
586  errorLocOuter = ERROR_OUTSIDE;
587  }
588 
589  polyshape.NewOutline();
590 
591  ConvertArcToPolyline( polyshape.Outline(2), center, arc_outer_radius,
592  arc_angle_start_deg, arc_angle, aError, errorLocOuter );
593 
594  if( arc_inner_radius > 0 )
595  ConvertArcToPolyline( polyshape.Outline(2), center, arc_inner_radius,
596  arc_angle_end_deg, -arc_angle, aError, errorLocInner );
597  else
598  polyshape.Append( center );
599 #else
600  // This appproximation use SHAPE_ARC to convert the 2 ends to polygons,
601  // approximate arc to polyline, convert the polyline corners to outer and inner
602  // corners of outer and inner utliners and merge shapes.
603  double defaultErr;
605  &defaultErr);
606  int radius = arc.GetRadius();
607  int radial_offset = ( aWidth + 1 ) / 2;
608  SHAPE_POLY_SET polyshape;
609  std::vector<VECTOR2I> outside_pts;
610 
611  // delta is the effective error approximation to build a polyline from an arc
612  int segCnt360 = arcSpine.GetSegmentCount()*360.0/arc.GetCentralAngle();;
613  int delta = CircleToEndSegmentDeltaRadius( radius+radial_offset, std::abs(segCnt360) );
614 
616  TransformCircleToPolygon( polyshape, aStart, radial_offset, aError, aErrorLoc );
617  TransformCircleToPolygon( polyshape, aEnd, radial_offset, aError, aErrorLoc );
618 
619  // The circle polygon is built with a even number of segments, so the
620  // horizontal diameter has 2 corners on the biggest diameter
621  // Rotate these 2 corners to match the start and ens points of inner and outer
622  // end points of the arc appoximation outlines, build below.
623  // The final shape is much better.
624  double arc_angle_end_deg = arc.GetStartAngle();
625 
626  if( arc_angle_end_deg != 0 && arc_angle_end_deg != 180.0 )
627  polyshape.Outline(0).Rotate( arc_angle_end_deg * M_PI/180.0, arcSpine.GetPoint( 0 ) );
628 
629  arc_angle_end_deg = arc.GetEndAngle();
630 
631  if( arc_angle_end_deg != 0 && arc_angle_end_deg != 180.0 )
632  polyshape.Outline(1).Rotate( arc_angle_end_deg * M_PI/180.0, arcSpine.GetPoint( -1 ) );
633 
634  if( aErrorLoc == ERROR_OUTSIDE )
635  radial_offset += delta + defaultErr/2;
636  else
637  radial_offset -= defaultErr/2;
638 
639  if( radial_offset < 0 )
640  radial_offset = 0;
641 
642  polyshape.NewOutline();
643 
644  VECTOR2I center = arc.GetCenter();
645  int last_index = arcSpine.GetPointCount() -1;
646 
647  for( std::size_t ii = 0; ii <= last_index; ++ii )
648  {
649  VECTOR2I offset = arcSpine.GetPoint( ii ) - center;
650  int curr_rd = radius;
651 
652  polyshape.Append( offset.Resize( curr_rd - radial_offset ) + center );
653  outside_pts.emplace_back( offset.Resize( curr_rd + radial_offset ) + center );
654  }
655 
656  for( auto it = outside_pts.rbegin(); it != outside_pts.rend(); ++it )
657  polyshape.Append( *it );
658 #endif
659 
660  // Can be removed, but usefull to display the outline:
661  polyshape.Simplify( SHAPE_POLY_SET::PM_FAST );
662 
663  aCornerBuffer.Append( polyshape );
664 
665 }
666 
667 
668 void TransformRingToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aCentre, int aRadius,
669  int aWidth, int aError, ERROR_LOC aErrorLoc )
670 {
671  int inner_radius = aRadius - ( aWidth / 2 );
672  int outer_radius = inner_radius + aWidth;
673 
674  if( inner_radius <= 0 )
675  { //In this case, the ring is just a circle (no hole inside)
676  TransformCircleToPolygon( aCornerBuffer, aCentre, aRadius + ( aWidth / 2 ), aError,
677  aErrorLoc );
678  return;
679  }
680 
681  SHAPE_POLY_SET buffer;
682 
683  TransformCircleToPolygon( buffer, aCentre, outer_radius, aError, aErrorLoc );
684 
685  // Build the hole:
686  buffer.NewHole();
687  // The circle is the hole, so the approximation error location is the opposite of aErrorLoc
688  ERROR_LOC inner_err_loc = aErrorLoc == ERROR_OUTSIDE ? ERROR_INSIDE : ERROR_OUTSIDE;
689  TransformCircleToPolygon( buffer.Hole( 0, 0 ), aCentre, inner_radius,
690  aError, inner_err_loc );
691 
693  aCornerBuffer.Append( buffer );
694 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:146
CITER next(CITER it)
Definition: ptree.cpp:126
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
int sign(T val)
Definition: util.h:104
virtual size_t GetSegmentCount() const override
virtual size_t GetPointCount() const override
int CircleToEndSegmentDeltaRadius(int aInnerCircleRadius, int aSegCount)
VECTOR2< T > Perpendicular() const
Compute the perpendicular vector.
Definition: vector2d.h:314
double GetRadius() const
Definition: shape_arc.cpp:492
const VECTOR2I ReflectPoint(const VECTOR2I &aP) const
Reflect a point using this segment as axis.
Definition: seg.cpp:249
double RAD2DECIDEG(double rad)
Definition: trigo.h:234
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:209
double GetStartAngle() const
Definition: shape_arc.cpp:444
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
static double DefaultAccuracyForPCB()
Definition: shape_arc.h:220
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:229
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
static bool intersect(const SEGMENT_WITH_NORMALS &aSeg, const SFVEC2F &aStart, const SFVEC2F &aEnd)
Definition: polygon_2d.cpp:273
void Append(int aX, int aY, bool aAllowDuplication=false)
Append a new point at the end of the line chain.
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
void TransformRingToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aCentre, int aRadius, int aWidth, int aError, ERROR_LOC aErrorLoc)
Convert arcs to multiple straight segments.
void SetClosed(bool aClosed)
Mark the line chain as closed (i.e.
void Move(const VECTOR2I &aVector) override
ROUNDED_CORNER(int x, int y, int radius)
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
void TransformOvalToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aStart, const wxPoint &aEnd, int aWidth, int aError, ERROR_LOC aErrorLoc, int aMinSegCount)
Convert a oblong shape to a polygon, using multiple segments.
void TransformCircleToPolygon(SHAPE_LINE_CHAIN &aCornerBuffer, const wxPoint &aCenter, int aRadius, int aError, ERROR_LOC aErrorLoc, int aMinSegCount)
Convert a circle to a polygon, using multiple straight lines.
a few functions useful in geometry calculations.
void Simplify(POLYGON_MODE aFastMode)
int GetCircleToPolyCorrection(int aMaxError)
int ConvertArcToPolyline(SHAPE_LINE_CHAIN &aPolyline, VECTOR2I aCenter, int aRadius, double aStartAngleDeg, double aArcAngleDeg, double aAccuracy, ERROR_LOC aErrorLoc)
Generate a polyline to approximate a arc.
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
int NewOutline()
Creates a new hole in a given outline.
double GetEndAngle() const
Definition: shape_arc.cpp:454
virtual const VECTOR2I GetPoint(int aIndex) const override
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
void Rotate(double aAngle, const VECTOR2I &aCenter=VECTOR2I(0, 0)) override
Rotate all vertices by a given angle.
Definition: seg.h:40
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:404
void CornerListRemoveDuplicates(std::vector< ROUNDED_CORNER > &aCorners)
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=DefaultAccuracyForPCB(), double *aEffectiveAccuracy=nullptr) const
Construct a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:498
void TransformArcToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aStart, const wxPoint &aMid, const wxPoint &aEnd, int aWidth, int aError, ERROR_LOC aErrorLoc)
Convert arc to multiple straight segments.
Represent a polyline (an zero-thickness chain of connected line segments).
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
double GetCentralAngle() const
Definition: shape_arc.cpp:479
double DECIDEG2RAD(double deg)
Definition: trigo.h:233
void TransformTrapezoidToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aPosition, const wxSize &aSize, double aRotation, int aDeltaX, int aDeltaY, int aInflate, int aError, ERROR_LOC aErrorLoc)
Convert a rectangle or trapezoid to a polygon.
constexpr ret_type KiROUND(fp_type v)
Round a floating point number to an integer using "round halfway cases away from zero".
Definition: util.h:73
constexpr int delta
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
void CornerListToPolygon(SHAPE_POLY_SET &outline, std::vector< ROUNDED_CORNER > &aCorners, int aInflate, int aError, ERROR_LOC aErrorLoc)
void TransformRoundChamferedRectToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aPosition, const wxSize &aSize, double aRotation, int aCornerRadius, double aChamferRatio, int aChamferCorners, int aInflate, int aError, ERROR_LOC aErrorLoc)
Convert a rectangle with rounded corners and/or chamfered corners to a polygon.
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
VECTOR2I GetCenter() const
Definition: shape_arc.cpp:464
int Side(const VECTOR2I &aP) const
Determine on which side of directed line passing via segment ends point aP lies.
Definition: seg.h:142
int Append(int x, int y, int aOutline=-1, int aHole=-1, bool aAllowDuplication=false)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...