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-2020 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 <math.h> // for atan2
30 #include <type_traits> // for swap
31 
34 #include <geometry/shape_line_chain.h> // for SHAPE_LINE_CHAIN
35 #include <geometry/shape_poly_set.h> // for SHAPE_POLY_SET, SHAPE_POLY_SE...
36 #include <math/util.h>
37 #include <math/vector2d.h> // for VECTOR2I
38 #include <trigo.h>
39 
40 
41 void TransformCircleToPolygon( SHAPE_LINE_CHAIN& aCornerBuffer, wxPoint aCenter, int aRadius,
42  int aError )
43 {
44  wxPoint corner_position;
45  int numSegs = std::max( GetArcToSegmentCount( aRadius, aError, 360.0 ), 6 );
46  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
47  double correction = GetCircletoPolyCorrectionFactor( numSegs );
48  int radius = aRadius * correction; // make segments outside the circles
49  double halfstep = delta/2.0; // the starting value for rot angles
50 
51  for( int ii = 0; ii < numSegs; ii++ )
52  {
53  corner_position.x = radius;
54  corner_position.y = 0;
55  double angle = (ii * delta) + halfstep;
56  RotatePoint( &corner_position, angle );
57  corner_position += aCenter;
58  aCornerBuffer.Append( corner_position.x, corner_position.y );
59  }
60 
61  aCornerBuffer.SetClosed( true );
62 }
63 
64 
65 void TransformCircleToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCenter, int aRadius,
66  int aError )
67 {
68  wxPoint corner_position;
69  int numSegs = std::max( GetArcToSegmentCount( aRadius, aError, 360.0 ), 6 );
70  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
71  double correction = GetCircletoPolyCorrectionFactor( numSegs );
72  int radius = aRadius * correction; // make segments outside the circles
73  double halfstep = delta/2.0; // the starting value for rot angles
74 
75  aCornerBuffer.NewOutline();
76 
77  for( int ii = 0; ii < numSegs; ii++ )
78  {
79  corner_position.x = radius;
80  corner_position.y = 0;
81  double angle = (ii * delta) + halfstep;
82  RotatePoint( &corner_position, angle );
83  corner_position += aCenter;
84  aCornerBuffer.Append( corner_position.x, corner_position.y );
85  }
86 }
87 
88 
89 void TransformOvalToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aStart, wxPoint aEnd,
90  int aWidth, int aError )
91 {
92  // To build the polygonal shape outside the actual shape, we use a bigger
93  // radius to build rounded ends.
94  // However, the width of the segment is too big.
95  // so, later, we will clamp the polygonal shape with the bounding box
96  // of the segment.
97  int radius = aWidth / 2;
98  int numSegs = std::max( GetArcToSegmentCount( radius, aError, 360.0 ), 6 );
99 
100  // Because we want to create 2 arcs (one at each segment end) numSegs must be
101  // a even value (we will used numSegs/2 later)
102  if( numSegs % 2 != 0 )
103  numSegs++;
104 
105  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
106  double correction = GetCircletoPolyCorrectionFactor( numSegs );
107 
108  radius = radius * correction; // make segments outside the circles
109 
110  // end point is the coordinate relative to aStart
111  wxPoint endp = aEnd - aStart;
112  wxPoint startp = aStart;
113  wxPoint corner;
114  SHAPE_POLY_SET polyshape;
115 
116  polyshape.NewOutline();
117 
118  // normalize the position in order to have endp.x >= 0
119  // it makes calculations more easy to understand
120  if( endp.x < 0 )
121  {
122  endp = aStart - aEnd;
123  startp = aEnd;
124  }
125 
126  // delta_angle is in radian
127  double delta_angle = atan2( (double)endp.y, (double)endp.x );
128  int seg_len = KiROUND( EuclideanNorm( endp ) );
129 
130 
131  // Compute the outlines of the segment, and creates a polygon
132  // Note: the polygonal shape is built from the equivalent horizontal
133  // segment starting ar 0,0, and ending at seg_len,0
134 
135  // add right rounded end:
136  for( int ii = 0; ii < numSegs / 2; ii++ )
137  {
138  corner = wxPoint( 0, radius );
139  RotatePoint( &corner, delta * ii );
140  corner.x += seg_len;
141  polyshape.Append( corner.x, corner.y );
142  }
143 
144  // Finish arc:
145  corner = wxPoint( seg_len, -radius );
146  polyshape.Append( corner.x, corner.y );
147 
148  // add left rounded end:
149  for( int ii = 0; ii < numSegs / 2; ii++ )
150  {
151  corner = wxPoint( 0, -radius );
152  RotatePoint( &corner, delta * ii );
153  polyshape.Append( corner.x, corner.y );
154  }
155 
156  // Finish arc:
157  corner = wxPoint( 0, radius );
158  polyshape.Append( corner.x, corner.y );
159 
160  // Now, clamp the polygonal shape (too big) with the segment bounding box
161  // the polygonal shape bbox equivalent to the segment has a too big height,
162  // and the right width
163  if( correction > 1.0 )
164  {
165  SHAPE_POLY_SET bbox;
166  bbox.NewOutline();
167  // Build the bbox (a horizontal rectangle).
168  int halfwidth = aWidth / 2; // Use the exact segment width for the bbox height
169  corner.x = -radius - 2; // use a bbox width slightly bigger to avoid
170  // creating useless corner at segment ends
171  corner.y = halfwidth;
172  bbox.Append( corner.x, corner.y );
173  corner.y = -halfwidth;
174  bbox.Append( corner.x, corner.y );
175  corner.x = radius + seg_len + 2;
176  bbox.Append( corner.x, corner.y );
177  corner.y = halfwidth;
178  bbox.Append( corner.x, corner.y );
179 
180  // Now, clamp the shape
182  // Note the final polygon is a simple, convex polygon with no hole
183  // due to the shape of initial polygons
184  }
185 
186  // Rotate and move the polygon to its right location
187  polyshape.Rotate( delta_angle, VECTOR2I( 0, 0 ) );
188  polyshape.Move( startp );
189 
190  aCornerBuffer.Append( polyshape);
191 }
192 
193 
194 void GetRoundRectCornerCenters( wxPoint aCenters[4], int aRadius, const wxPoint& aPosition,
195  const wxSize& aSize, double aRotation )
196 {
197  wxSize size( aSize/2 );
198 
199  size.x -= aRadius;
200  size.y -= aRadius;
201 
202  // Ensure size is > 0, to avoid generating unusable shapes
203  // which can crash kicad.
204  size.x = std::max( 1, size.x );
205  size.y = std::max( 1, size.y );
206 
207  aCenters[0] = wxPoint( -size.x, size.y );
208  aCenters[1] = wxPoint( size.x, size.y );
209  aCenters[2] = wxPoint( size.x, -size.y );
210  aCenters[3] = wxPoint( -size.x, -size.y );
211 
212  // Rotate the polygon
213  if( aRotation != 0.0 )
214  {
215  for( int ii = 0; ii < 4; ii++ )
216  RotatePoint( &aCenters[ii], aRotation );
217  }
218 
219  // move the polygon to the position
220  for( int ii = 0; ii < 4; ii++ )
221  aCenters[ii] += aPosition;
222 }
223 
224 
225 void TransformRoundChamferedRectToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aPosition,
226  const wxSize& aSize, double aRotation,
227  int aCornerRadius, double aChamferRatio,
228  int aChamferCorners, int aError )
229 {
230  // Build the basic shape in orientation 0.0, position 0,0 for chamfered corners
231  // or in actual position/orientation for round rect only
232  wxPoint corners[4];
233  GetRoundRectCornerCenters( corners, aCornerRadius,
234  aChamferCorners ? wxPoint( 0, 0 ) : aPosition,
235  aSize, aChamferCorners ? 0.0 : aRotation );
236 
237  SHAPE_POLY_SET outline;
238  outline.NewOutline();
239 
240  for( const wxPoint& corner : corners)
241  outline.Append( corner );
242 
243  // These are small radius corners (of which there may be many), so peg the segs-per-circle
244  // to no more than 16.
245  int numSegs = std::max( GetArcToSegmentCount( aCornerRadius, aError, 360.0 ), 16 );
246 
247  // To build the polygonal shape outside the actual shape, we use a bigger
248  // radius to build rounded corners.
249  // However, the size of the shape is too large.
250  // so, we also clamp the polygonal shape with the bounding box
251  // of the initial shape.
252 
253  double correction = GetCircletoPolyCorrectionFactor( numSegs );
254  int radius = aCornerRadius * correction; // make segments outside the circles
255  outline.Inflate( radius, numSegs );
256 
257  if( correction > 1.0 )
258  {
259  // Refinement: clamp the inflated polygonal shape by the rectangular shape
260  // containing the rounded polygon
261  SHAPE_POLY_SET bbox; // the rectangular shape
262  bbox.NewOutline();
263 
264  for( const wxPoint& corner : corners )
265  bbox.Append( corner );
266 
267  // Just build the rectangular bbox
268  bbox.Inflate( aCornerRadius, 1, SHAPE_POLY_SET::CORNER_STRATEGY::ALLOW_ACUTE_CORNERS );
269 
270  // Now, clamp the shape
272  // Note the final polygon is a simple, convex polygon with no hole
273  // due to the shape of initial polygons
274  }
275 
276  if( aChamferCorners == RECT_NO_CHAMFER ) // no chamfer
277  {
278  // Add the outline:
279  aCornerBuffer.Append( outline );
280  return;
281  }
282 
283  // Now we have the round rect outline, in position 0,0 orientation 0.0.
284  // Chamfer the corner(s).
285  int chamfer_value = aChamferRatio * std::min( aSize.x, aSize.y );
286 
287  SHAPE_POLY_SET chamfered_corner; // corner shape for the current corner to chamfer
288 
289  int corner_id[4] =
290  {
293  };
294  // Depending on the corner position, signX[] and signY[] give the sign of chamfer
295  // coordinates relative to the corner position
296  // The first corner is the top left corner, then top right, bottom left and bottom right
297  int signX[4] = {1, -1, 1,-1 };
298  int signY[4] = {1, 1, -1,-1 };
299 
300  for( int ii = 0; ii < 4; ii++ )
301  {
302  if( (corner_id[ii] & aChamferCorners) == 0 )
303  continue;
304 
305  VECTOR2I corner_pos( -signX[ii]*aSize.x/2, -signY[ii]*aSize.y/2 );
306 
307  if( aCornerRadius )
308  {
309  // We recreate a rectangular area covering the full rounded corner (max size = aSize/2)
310  // to rebuild the corner before chamfering, to be sure the rounded corner shape does not
311  // overlap the chamfered corner shape:
312  chamfered_corner.RemoveAllContours();
313  chamfered_corner.NewOutline();
314  chamfered_corner.Append( 0, 0 );
315  chamfered_corner.Append( 0, signY[ii] * aSize.y / 2 );
316  chamfered_corner.Append( signX[ii] * aSize.x / 2, signY[ii] * aSize.y / 2 );
317  chamfered_corner.Append( signX[ii] * aSize.x / 2, 0 );
318  chamfered_corner.Move( corner_pos );
319  outline.BooleanAdd( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
320  }
321 
322  // Now chamfer this corner
323  chamfered_corner.RemoveAllContours();
324  chamfered_corner.NewOutline();
325  chamfered_corner.Append( 0, 0 );
326  chamfered_corner.Append( 0, signY[ii] * chamfer_value );
327  chamfered_corner.Append( signX[ii] * chamfer_value, 0 );
328  chamfered_corner.Move( corner_pos );
329  outline.BooleanSubtract( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
330  }
331 
332  // Rotate and move the outline:
333  if( aRotation != 0.0 )
334  outline.Rotate( DECIDEG2RAD( -aRotation ), VECTOR2I( 0, 0 ) );
335 
336  outline.Move( VECTOR2I( aPosition ) );
337 
338  // Add the outline:
339  aCornerBuffer.Append( outline );
340 }
341 
342 
343 void TransformSegmentToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aStart, wxPoint aEnd,
344  int aError, int aWidth )
345 {
346  int radius = aWidth / 2;
347  wxPoint endp = aEnd - aStart; // end point coordinate for the same segment starting at (0,0)
348  wxPoint startp = aStart;
349  wxPoint corner;
350  VECTOR2I polypoint;
351  int numSegs = std::max( GetArcToSegmentCount( radius, aError, 360.0 ), 6 );
352  double correction = GetCircletoPolyCorrectionFactor( numSegs );
353  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
354 
355  radius = KiROUND( radius * correction );
356  aCornerBuffer.NewOutline();
357 
358  // normalize the position in order to have endp.x >= 0;
359  if( endp.x < 0 )
360  {
361  endp = aStart - aEnd;
362  startp = aEnd;
363  }
364 
365  double delta_angle = ArcTangente( endp.y, endp.x ); // delta_angle is in 0.1 degrees
366  int seg_len = KiROUND( EuclideanNorm( endp ) );
367 
368  // Compute the outlines of the segment, and creates a polygon
369 
370  // add right rounded end:
371  for( int ii = 0; ii < 1800; ii += delta )
372  {
373  corner = wxPoint( 0, radius );
374  RotatePoint( &corner, ii );
375  corner.x += seg_len;
376  RotatePoint( &corner, -delta_angle );
377  corner += startp;
378  polypoint.x = corner.x;
379  polypoint.y = corner.y;
380  aCornerBuffer.Append( polypoint.x, polypoint.y );
381  }
382 
383  // Finish arc:
384  corner = wxPoint( seg_len, -radius );
385  RotatePoint( &corner, -delta_angle );
386  corner += startp;
387  polypoint.x = corner.x;
388  polypoint.y = corner.y;
389  aCornerBuffer.Append( polypoint.x, polypoint.y );
390 
391  // add left rounded end:
392  for( int ii = 0; ii < 1800; ii += delta )
393  {
394  corner = wxPoint( 0, -radius );
395  RotatePoint( &corner, ii );
396  RotatePoint( &corner, -delta_angle );
397  corner += startp;
398  polypoint.x = corner.x;
399  polypoint.y = corner.y;
400  aCornerBuffer.Append( polypoint.x, polypoint.y );
401  }
402 
403  // Finish arc:
404  corner = wxPoint( 0, radius );
405  RotatePoint( &corner, -delta_angle );
406  corner += startp;
407  polypoint.x = corner.x;
408  polypoint.y = corner.y;
409  aCornerBuffer.Append( polypoint.x, polypoint.y );
410 }
411 
412 
413 void TransformArcToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCentre, wxPoint aStart,
414  double aArcAngle, int aError, int aWidth )
415 {
416  wxPoint arc_start, arc_end;
417  int dist = EuclideanNorm( aCentre - aStart );
418  int numSegs = std::max( GetArcToSegmentCount( dist, aError, 360.0 ), 6 );
419  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
420 
421  arc_end = arc_start = aStart;
422 
423  if( aArcAngle != 3600 )
424  RotatePoint( &arc_end, aCentre, -aArcAngle );
425 
426  if( aArcAngle < 0 )
427  {
428  std::swap( arc_start, arc_end );
429  aArcAngle = -aArcAngle;
430  }
431 
432  // Compute the ends of segments and creates poly
433  wxPoint curr_end = arc_start;
434  wxPoint curr_start = arc_start;
435 
436  for( int ii = delta; ii < aArcAngle; ii += delta )
437  {
438  curr_end = arc_start;
439  RotatePoint( &curr_end, aCentre, -ii );
440  TransformSegmentToPolygon( aCornerBuffer, curr_start, curr_end, aError, aWidth );
441  curr_start = curr_end;
442  }
443 
444  if( curr_end != arc_end )
445  TransformSegmentToPolygon( aCornerBuffer, curr_end, arc_end, aError, aWidth );
446 }
447 
448 
449 void TransformRingToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCentre, int aRadius,
450  int aError, int aWidth )
451 {
452  int inner_radius = aRadius - ( aWidth / 2 );
453  int outer_radius = inner_radius + aWidth;
454 
455  if( inner_radius <= 0 )
456  { //In this case, the ring is just a circle (no hole inside)
457  TransformCircleToPolygon( aCornerBuffer, aCentre, aRadius + ( aWidth / 2 ), aError );
458  return;
459  }
460 
461  SHAPE_POLY_SET buffer;
462 
463  TransformCircleToPolygon( buffer, aCentre, outer_radius, aError );
464 
465  // Build the hole:
466  buffer.NewHole();
467  TransformCircleToPolygon( buffer.Hole( 0, 0 ), aCentre, inner_radius, aError );
468 
470  aCornerBuffer.Append( buffer );
471 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:128
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
void TransformArcToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aCentre, wxPoint aStart, double aArcAngle, int aError, int aWidth)
Function TransformArcToPolygon Creates a polygon from an Arc Convert arcs to multiple straight segmen...
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
void TransformRingToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aCentre, int aRadius, int aError, int aWidth)
Function TransformRingToPolygon Creates a polygon from a ring Convert arcs to multiple straight segme...
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Function Rotate rotates all vertices by a given angle.
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:208
void Inflate(int aAmount, int aCircleSegmentsCount, CORNER_STRATEGY aCornerStrategy=ROUND_ALL_CORNERS)
Performs outline inflation/deflation.
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
void SetClosed(bool aClosed)
Function SetClosed()
void Move(const VECTOR2I &aVector) override
double GetCircletoPolyCorrectionFactor(int aSegCountforCircle)
SHAPE_POLY_SET.
void TransformCircleToPolygon(SHAPE_LINE_CHAIN &aCornerBuffer, wxPoint aCenter, int aRadius, int aError)
a few functions useful in geometry calculations.
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...
SHAPE_LINE_CHAIN.
void TransformSegmentToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aStart, wxPoint aEnd, int aError, int aWidth)
Function TransformRoundedEndsSegmentToPolygon convert a segment with rounded ends to a polygon Conver...
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void TransformOvalToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aStart, wxPoint aEnd, int aWidth, int aError)
convert a oblong shape to a polygon, using multiple segments It is similar to TransformRoundedEndsSeg...
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
double DECIDEG2RAD(double deg)
Definition: trigo.h:218
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:68
void GetRoundRectCornerCenters(wxPoint aCenters[4], int aRadius, const wxPoint &aPosition, const wxSize &aSize, double aRotation)
Helper function GetRoundRectCornerCenters Has meaning only for rounded rect Returns the centers of th...
void TransformRoundChamferedRectToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aPosition, const wxSize &aSize, double aRotation, int aCornerRadius, double aChamferRatio, int aChamferCorners, int aError)
convert a rectangle with rounded corners and/or chamfered corners to a polygon Convert rounded corner...
void BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
double ArcTangente(int dy, int dx)
Definition: trigo.cpp:162
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
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)