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, ERROR_LOC aErrorLoc )
43 {
44  wxPoint corner_position;
45  int numSegs = GetArcToSegmentCount( aRadius, aError, 360.0 );
46  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
47  int radius = aRadius;
48 
49  if( aErrorLoc == ERROR_OUTSIDE )
50  radius += GetCircleToPolyCorrection( aError );
51 
52  for( int angle = 0; angle < 3600; angle += delta )
53  {
54  corner_position.x = radius;
55  corner_position.y = 0;
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, ERROR_LOC aErrorLoc )
67 {
68  wxPoint corner_position;
69  int numSegs = GetArcToSegmentCount( aRadius, aError, 360.0 );
70  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
71  int radius = aRadius;
72 
73  if( aErrorLoc == ERROR_OUTSIDE )
74  radius += GetCircleToPolyCorrection( aError );
75 
76  aCornerBuffer.NewOutline();
77 
78  for( int angle = 0; angle < 3600; angle += delta )
79  {
80  corner_position.x = radius;
81  corner_position.y = 0;
82  RotatePoint( &corner_position, angle );
83  corner_position += aCenter;
84  aCornerBuffer.Append( corner_position.x, corner_position.y );
85  }
86 
87  // Finish circle
88  corner_position.x = radius;
89  corner_position.y = 0;
90  corner_position += aCenter;
91  aCornerBuffer.Append( corner_position.x, corner_position.y );
92 }
93 
94 
95 void TransformOvalToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aStart, wxPoint aEnd,
96  int aWidth, int aError, ERROR_LOC aErrorLoc )
97 {
98  // To build the polygonal shape outside the actual shape, we use a bigger
99  // radius to build rounded ends.
100  // However, the width of the segment is too big.
101  // so, later, we will clamp the polygonal shape with the bounding box
102  // of the segment.
103  int radius = aWidth / 2;
104  int numSegs = GetArcToSegmentCount( radius, aError, 360.0 );
105  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
106  int correction = GetCircleToPolyCorrection( aError );
107 
108  if( aErrorLoc == ERROR_OUTSIDE )
109  radius += correction;
110 
111  // end point is the coordinate relative to aStart
112  wxPoint endp = aEnd - aStart;
113  wxPoint startp = aStart;
114  wxPoint corner;
115  SHAPE_POLY_SET polyshape;
116 
117  polyshape.NewOutline();
118 
119  // normalize the position in order to have endp.x >= 0
120  // it makes calculations more easy to understand
121  if( endp.x < 0 )
122  {
123  endp = aStart - aEnd;
124  startp = aEnd;
125  }
126 
127  // delta_angle is in radian
128  double delta_angle = atan2( (double)endp.y, (double)endp.x );
129  int seg_len = KiROUND( EuclideanNorm( endp ) );
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 at {0,0}, and ending at {seg_len,0}
134 
135  // add right rounded end:
136 
137  for( int angle = 0; angle < 1800; angle += delta )
138  {
139  corner = wxPoint( 0, radius );
140  RotatePoint( &corner, angle );
141  corner.x += seg_len;
142  polyshape.Append( corner.x, corner.y );
143  }
144 
145  // Finish arc:
146  corner = wxPoint( seg_len, -radius );
147  polyshape.Append( corner.x, corner.y );
148 
149  // add left rounded end:
150  for( int angle = 0; angle < 1800; angle += delta )
151  {
152  corner = wxPoint( 0, -radius );
153  RotatePoint( &corner, angle );
154  polyshape.Append( corner.x, corner.y );
155  }
156 
157  // Finish arc:
158  corner = wxPoint( 0, radius );
159  polyshape.Append( corner.x, corner.y );
160 
161  // Now trim the edges of the polygonal shape which will be slightly outside the
162  // track width.
163  SHAPE_POLY_SET bbox;
164  bbox.NewOutline();
165  // Build the bbox (a horizontal rectangle).
166  int halfwidth = aWidth / 2; // Use the exact segment width for the bbox height
167  corner.x = -radius - 2; // use a bbox width slightly bigger to avoid
168  // creating useless corner at segment ends
169  corner.y = halfwidth;
170  bbox.Append( corner.x, corner.y );
171  corner.y = -halfwidth;
172  bbox.Append( corner.x, corner.y );
173  corner.x = radius + seg_len + 2;
174  bbox.Append( corner.x, corner.y );
175  corner.y = halfwidth;
176  bbox.Append( corner.x, corner.y );
177 
178  // Now, clamp the shape
180  // Note the final polygon is a simple, convex polygon with no hole
181  // due to the shape of initial polygons
182 
183  // Rotate and move the polygon to its right location
184  polyshape.Rotate( delta_angle, VECTOR2I( 0, 0 ) );
185  polyshape.Move( startp );
186 
187  aCornerBuffer.Append( polyshape);
188 }
189 
190 
191 // Return a polygon representing a round rect centered at {0,0}
192 void TransformRoundRectToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxSize& aSize,
193  int aCornerRadius, int aError, ERROR_LOC aErrorLoc )
194 {
195  wxPoint centers[4];
196  wxSize size( aSize / 2 );
197 
198  size.x -= aCornerRadius;
199  size.y -= aCornerRadius;
200 
201  // Ensure size is > 0, to avoid generating unusable shapes which can crash kicad.
202  size.x = std::max( 1, size.x );
203  size.y = std::max( 1, size.y );
204 
205  centers[0] = wxPoint( -size.x, size.y );
206  centers[1] = wxPoint( size.x, size.y );
207  centers[2] = wxPoint( size.x, -size.y );
208  centers[3] = wxPoint( -size.x, -size.y );
209 
210  int numSegs = GetArcToSegmentCount( aCornerRadius, aError, 360.0 );
211 
212  // Choppy corners on rounded-corner rectangles look awful so enforce a minimum of
213  // 4 segments per corner.
214  if( numSegs < 16 )
215  numSegs = 16;
216 
217  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
218  int radius = aCornerRadius;
219 
220  if( aErrorLoc == ERROR_OUTSIDE )
221  radius += GetCircleToPolyCorrection( aError );
222 
223  auto genArc =
224  [&]( const wxPoint& aCenter, int aStart, int aEnd )
225  {
226  for( int angle = aStart + delta; angle < aEnd; angle += delta )
227  {
228  wxPoint pt( -radius, 0 );
229  RotatePoint( &pt, angle );
230  pt += aCenter;
231  aCornerBuffer.Append( pt.x, pt.y );
232  }
233  };
234 
235  aCornerBuffer.NewOutline();
236 
237  aCornerBuffer.Append( centers[0] + wxPoint( -radius, 0 ) );
238  genArc( centers[0], 0, 900 );
239  aCornerBuffer.Append( centers[0] + wxPoint( 0, radius ) );
240  aCornerBuffer.Append( centers[1] + wxPoint( 0, radius ) );
241  genArc( centers[1], 900, 1800 );
242  aCornerBuffer.Append( centers[1] + wxPoint( radius, 0 ) );
243  aCornerBuffer.Append( centers[2] + wxPoint( radius, 0 ) );
244  genArc( centers[2], 1800, 2700 );
245  aCornerBuffer.Append( centers[2] + wxPoint( 0, -radius ) );
246  aCornerBuffer.Append( centers[3] + wxPoint( 0, -radius ) );
247  genArc( centers[3], 2700, 3600 );
248  aCornerBuffer.Append( centers[3] + wxPoint( -radius, 0 ) );
249 
250  aCornerBuffer.Outline( 0 ).SetClosed( true );
251 }
252 
253 
254 void TransformRoundChamferedRectToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aPosition,
255  const wxSize& aSize, double aRotation,
256  int aCornerRadius, double aChamferRatio,
257  int aChamferCorners, int aError, ERROR_LOC aErrorLoc )
258 {
259  SHAPE_POLY_SET outline;
260  TransformRoundRectToPolygon( outline, aSize, aCornerRadius, aError, aErrorLoc );
261 
262  if( aChamferCorners )
263  {
264  // Now we have the round rect outline, in position 0,0 orientation 0.0.
265  // Chamfer the corner(s).
266  int chamfer_value = aChamferRatio * std::min( aSize.x, aSize.y );
267 
268  SHAPE_POLY_SET chamfered_corner; // corner shape for the current corner to chamfer
269 
270  int corner_id[4] =
271  {
274  };
275  // Depending on the corner position, signX[] and signY[] give the sign of chamfer
276  // coordinates relative to the corner position
277  // The first corner is the top left corner, then top right, bottom left and bottom right
278  int signX[4] = {1, -1, 1,-1 };
279  int signY[4] = {1, 1, -1,-1 };
280 
281  for( int ii = 0; ii < 4; ii++ )
282  {
283  if( (corner_id[ii] & aChamferCorners) == 0 )
284  continue;
285 
286  VECTOR2I corner_pos( -signX[ii]*aSize.x/2, -signY[ii]*aSize.y/2 );
287 
288  if( aCornerRadius )
289  {
290  // We recreate a rectangular area covering the full rounded corner
291  // (max size = aSize/2) to rebuild the corner before chamfering, to be sure
292  // the rounded corner shape does not overlap the chamfered corner shape:
293  chamfered_corner.RemoveAllContours();
294  chamfered_corner.NewOutline();
295  chamfered_corner.Append( 0, 0 );
296  chamfered_corner.Append( 0, signY[ii] * aSize.y / 2 );
297  chamfered_corner.Append( signX[ii] * aSize.x / 2, signY[ii] * aSize.y / 2 );
298  chamfered_corner.Append( signX[ii] * aSize.x / 2, 0 );
299  chamfered_corner.Move( corner_pos );
300  outline.BooleanAdd( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
301  }
302 
303  // Now chamfer this corner
304  chamfered_corner.RemoveAllContours();
305  chamfered_corner.NewOutline();
306  chamfered_corner.Append( 0, 0 );
307  chamfered_corner.Append( 0, signY[ii] * chamfer_value );
308  chamfered_corner.Append( signX[ii] * chamfer_value, 0 );
309  chamfered_corner.Move( corner_pos );
310  outline.BooleanSubtract( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
311  }
312  }
313 
314  // Rotate and move the outline:
315  if( aRotation != 0.0 )
316  outline.Rotate( DECIDEG2RAD( -aRotation ), VECTOR2I( 0, 0 ) );
317 
318  outline.Move( VECTOR2I( aPosition ) );
319 
320  // Add the outline:
321  aCornerBuffer.Append( outline );
322 }
323 
324 
325 void TransformArcToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCentre, wxPoint aStart,
326  double aArcAngle, int aWidth, int aError, ERROR_LOC aErrorLoc )
327 {
328  wxPoint arc_start, arc_end;
329  int dist = EuclideanNorm( aCentre - aStart );
330  int numSegs = GetArcToSegmentCount( dist, aError, 360.0 );
331  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
332 
333  arc_end = arc_start = aStart;
334 
335  if( aArcAngle != 3600 )
336  RotatePoint( &arc_end, aCentre, -aArcAngle );
337 
338  if( aArcAngle < 0 )
339  {
340  std::swap( arc_start, arc_end );
341  aArcAngle = -aArcAngle;
342  }
343 
344  // Compute the ends of segments and creates poly
345  wxPoint curr_end = arc_start;
346  wxPoint curr_start = arc_start;
347 
348  for( int ii = delta; ii < aArcAngle; ii += delta )
349  {
350  curr_end = arc_start;
351  RotatePoint( &curr_end, aCentre, -ii );
352  TransformOvalToPolygon( aCornerBuffer, curr_start, curr_end, aWidth, aError, aErrorLoc );
353  curr_start = curr_end;
354  }
355 
356  if( curr_end != arc_end )
357  TransformOvalToPolygon( aCornerBuffer, curr_end, arc_end, aWidth, aError, aErrorLoc );
358 }
359 
360 
361 void TransformRingToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCentre, int aRadius,
362  int aWidth, int aError, ERROR_LOC aErrorLoc )
363 {
364  int inner_radius = aRadius - ( aWidth / 2 );
365  int outer_radius = inner_radius + aWidth;
366 
367  if( inner_radius <= 0 )
368  { //In this case, the ring is just a circle (no hole inside)
369  TransformCircleToPolygon( aCornerBuffer, aCentre, aRadius + ( aWidth / 2 ), aError,
370  aErrorLoc );
371  return;
372  }
373 
374  SHAPE_POLY_SET buffer;
375 
376  TransformCircleToPolygon( buffer, aCentre, outer_radius, aError, aErrorLoc );
377 
378  // Build the hole:
379  buffer.NewHole();
380  TransformCircleToPolygon( buffer.Hole( 0, 0 ), aCentre, inner_radius, aError, aErrorLoc );
381 
383  aCornerBuffer.Append( buffer );
384 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:134
int NewHole(int aOutline=-1)
Creates a new hole in a given outline
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset union For aFastMode meaning, see function booleanOp
void TransformRoundChamferedRectToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxPoint &aPosition, const wxSize &aSize, double aRotation, int aCornerRadius, double aChamferRatio, int aChamferCorners, int aError, ERROR_LOC aErrorLoc)
convert a rectangle with rounded corners and/or chamfered corners to a polygon Convert rounded corner...
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61
void TransformCircleToPolygon(SHAPE_LINE_CHAIN &aCornerBuffer, wxPoint aCenter, int aRadius, int aError, ERROR_LOC aErrorLoc)
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Returns the reference to aHole-th hole in the aIndex-th outline
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 TransformRoundRectToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxSize &aSize, int aCornerRadius, int aError, ERROR_LOC aErrorLoc)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:594
void TransformRingToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aCentre, int aRadius, int aWidth, int aError, ERROR_LOC aErrorLoc)
Function TransformRingToPolygon Creates a polygon from a ring Convert arcs to multiple straight segme...
void Append(int aX, int aY, bool aAllowDuplication=false)
Function Append()
ERROR_LOC
When approximating an arc or circle, should the error be placed on the outside or inside of the curve...
void TransformArcToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aCentre, wxPoint aStart, double aArcAngle, int aWidth, int aError, ERROR_LOC aErrorLoc)
Function TransformArcToPolygon Creates a polygon from an Arc Convert arcs to multiple straight segmen...
void SetClosed(bool aClosed)
Function SetClosed()
void Move(const VECTOR2I &aVector) override
SHAPE_POLY_SET.
SHAPE_LINE_CHAIN & Outline(int aIndex)
Returns the reference to aIndex-th outline in the set
a few functions useful in geometry calculations.
int GetCircleToPolyCorrection(int aMaxError)
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.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
void RemoveAllContours()
Removes all outlines & holes (clears) the polygon set.
double DECIDEG2RAD(double deg)
Definition: trigo.h:224
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 BooleanSubtract(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Performs boolean polyset difference For aFastMode meaning, see function booleanOp
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
void TransformOvalToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aStart, wxPoint aEnd, int aWidth, int aError, ERROR_LOC aErrorLoc)
convert a oblong shape to a polygon, using multiple segments It is similar to TransformRoundedEndsSeg...
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)