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-2019 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 
42  wxPoint aCenter, int aRadius,
43  int aError )
44 {
45  wxPoint corner_position;
46  int numSegs = std::max( GetArcToSegmentCount( aRadius, aError, 360.0 ), 6 );
47  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
48  double correction = GetCircletoPolyCorrectionFactor( numSegs );
49  int radius = aRadius * correction; // make segments outside the circles
50  double halfstep = delta/2.0; // the starting value for rot angles
51 
52  for( int ii = 0; ii < numSegs; ii++ )
53  {
54  corner_position.x = radius;
55  corner_position.y = 0;
56  double angle = (ii * delta) + halfstep;
57  RotatePoint( &corner_position, angle );
58  corner_position += aCenter;
59  aBuffer.Append( corner_position.x, corner_position.y );
60  }
61 
62  aBuffer.SetClosed( true );
63 }
64 
65 
66 void TransformCircleToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCenter, int aRadius,
67  int aError )
68 {
69  wxPoint corner_position;
70  int numSegs = std::max( GetArcToSegmentCount( aRadius, aError, 360.0 ), 6 );
71  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
72  double correction = GetCircletoPolyCorrectionFactor( numSegs );
73  int radius = aRadius * correction; // make segments outside the circles
74  double halfstep = delta/2.0; // the starting value for rot angles
75 
76  aCornerBuffer.NewOutline();
77 
78  for( int ii = 0; ii < numSegs; ii++ )
79  {
80  corner_position.x = radius;
81  corner_position.y = 0;
82  double angle = (ii * delta) + halfstep;
83  RotatePoint( &corner_position, angle );
84  corner_position += aCenter;
85  aCornerBuffer.Append( corner_position.x, corner_position.y );
86  }
87 }
88 
89 
90 void TransformOvalToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aStart, wxPoint aEnd,
91  int aWidth, int aError )
92 {
93  // To build the polygonal shape outside the actual shape, we use a bigger
94  // radius to build rounded ends.
95  // However, the width of the segment is too big.
96  // so, later, we will clamp the polygonal shape with the bounding box
97  // of the segment.
98  int radius = aWidth / 2;
99  int numSegs = std::max( GetArcToSegmentCount( radius, aError, 360.0 ), 6 );
100 
101  // Because we want to create 2 arcs (one at each segment end) numSegs must be
102  // a even value (we will used numSegs/2 later)
103  if( numSegs % 2 != 0 )
104  numSegs++;
105 
106  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
107  double correction = GetCircletoPolyCorrectionFactor( numSegs );
108 
109  radius = radius * correction; // make segments outside the circles
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 
132  // Compute the outlines of the segment, and creates a polygon
133  // Note: the polygonal shape is built from the equivalent horizontal
134  // segment starting ar 0,0, and ending at seg_len,0
135 
136  // add right rounded end:
137  for( int ii = 0; ii < numSegs / 2; ii++ )
138  {
139  corner = wxPoint( 0, radius );
140  RotatePoint( &corner, delta * ii );
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 ii = 0; ii < numSegs / 2; ii++ )
151  {
152  corner = wxPoint( 0, -radius );
153  RotatePoint( &corner, delta * ii );
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, clamp the polygonal shape (too big) with the segment bounding box
162  // the polygonal shape bbox equivalent to the segment has a too big height,
163  // and the right width
164  if( correction > 1.0 )
165  {
166  SHAPE_POLY_SET bbox;
167  bbox.NewOutline();
168  // Build the bbox (a horizontal rectangle).
169  int halfwidth = aWidth / 2; // Use the exact segment width for the bbox height
170  corner.x = -radius - 2; // use a bbox width slightly bigger to avoid
171  // creating useless corner at segment ends
172  corner.y = halfwidth;
173  bbox.Append( corner.x, corner.y );
174  corner.y = -halfwidth;
175  bbox.Append( corner.x, corner.y );
176  corner.x = radius + seg_len + 2;
177  bbox.Append( corner.x, corner.y );
178  corner.y = halfwidth;
179  bbox.Append( corner.x, corner.y );
180 
181  // Now, clamp the shape
183  // Note the final polygon is a simple, convex polygon with no hole
184  // due to the shape of initial polygons
185  }
186 
187  // Rotate and move the polygon to its right location
188  polyshape.Rotate( delta_angle, VECTOR2I( 0, 0 ) );
189  polyshape.Move( startp );
190 
191  aCornerBuffer.Append( polyshape);
192 }
193 
194 
195 void GetRoundRectCornerCenters( wxPoint aCenters[4], int aRadius,
196  const wxPoint& aPosition, const wxSize& aSize, double aRotation )
197 {
198  wxSize size( aSize/2 );
199 
200  size.x -= aRadius;
201  size.y -= aRadius;
202 
203  // Ensure size is > 0, to avoid generating unusable shapes
204  // which can crash kicad.
205  if( size.x <= 1 )
206  size.x = 1;
207  if( size.y <= 1 )
208  size.y = 1;
209 
210  aCenters[0].x = -size.x;
211  aCenters[0].y = size.y;
212 
213  aCenters[1].x = size.x;
214  aCenters[1].y = size.y;
215 
216  aCenters[2].x = size.x;
217  aCenters[2].y = -size.y;
218 
219  aCenters[3].x = -size.x;
220  aCenters[3].y = -size.y;
221 
222  // Rotate the polygon
223  if( aRotation )
224  {
225  for( int ii = 0; ii < 4; ii++ )
226  RotatePoint( &aCenters[ii], aRotation );
227  }
228 
229  // move the polygon to the position
230  for( int ii = 0; ii < 4; ii++ )
231  aCenters[ii] += aPosition;
232 }
233 
234 
236  const wxPoint& aPosition, const wxSize& aSize,
237  double aRotation, int aCornerRadius,
238  double aChamferRatio, int aChamferCorners,
239  int aApproxErrorMax, int aMinSegPerCircleCount )
240 {
241  // Build the basic shape in orientation 0.0, position 0,0 for chamfered corners
242  // or in actual position/orientation for round rect only
243  wxPoint corners[4];
244  GetRoundRectCornerCenters( corners, aCornerRadius,
245  aChamferCorners ? wxPoint( 0, 0 ) : aPosition,
246  aSize, aChamferCorners ? 0.0 : aRotation );
247 
248  SHAPE_POLY_SET outline;
249  outline.NewOutline();
250 
251  for( int ii = 0; ii < 4; ++ii )
252  outline.Append( corners[ii].x, corners[ii].y );
253 
254  int numSegs = std::max( GetArcToSegmentCount( aCornerRadius, aApproxErrorMax, 360.0 ),
255  aMinSegPerCircleCount );
256  outline.Inflate( aCornerRadius, numSegs );
257 
258  if( aChamferCorners == RECT_NO_CHAMFER ) // no chamfer
259  {
260  // Add the outline:
261  aCornerBuffer.Append( outline );
262  return;
263  }
264 
265  // Now we have the round rect outline, in position 0,0 orientation 0.0.
266  // Chamfer the corner(s).
267  int chamfer_value = aChamferRatio * std::min( aSize.x, aSize.y );
268 
269  SHAPE_POLY_SET chamfered_corner; // corner shape for the current corner to chamfer
270 
271  int corner_id[4] =
272  {
275  };
276  // Depending on the corner position, signX[] and signY[] give the sign of chamfer
277  // coordinates relative to the corner position
278  // The first corner is the top left corner, then top right, bottom left and bottom right
279  int signX[4] = {1, -1, 1,-1 };
280  int signY[4] = {1, 1, -1,-1 };
281 
282  for( int ii = 0; ii < 4; ii++ )
283  {
284  if( (corner_id[ii] & aChamferCorners) == 0 )
285  continue;
286 
287  VECTOR2I corner_pos( -signX[ii]*aSize.x/2, -signY[ii]*aSize.y/2 );
288 
289  if( aCornerRadius )
290  {
291  // We recreate a rectangular area covering the full rounded corner (max size = aSize/2)
292  // to rebuild the corner before chamfering, to be sure the rounded corner shape does not
293  // overlap the chamfered corner shape:
294  chamfered_corner.RemoveAllContours();
295  chamfered_corner.NewOutline();
296  chamfered_corner.Append( 0, 0 );
297  chamfered_corner.Append( 0, signY[ii] * aSize.y / 2 );
298  chamfered_corner.Append( signX[ii] * aSize.x / 2, signY[ii] * aSize.y / 2 );
299  chamfered_corner.Append( signX[ii] * aSize.x / 2, 0 );
300  chamfered_corner.Move( corner_pos );
301  outline.BooleanAdd( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
302  }
303 
304  // Now chamfer this corner
305  chamfered_corner.RemoveAllContours();
306  chamfered_corner.NewOutline();
307  chamfered_corner.Append( 0, 0 );
308  chamfered_corner.Append( 0, signY[ii] * chamfer_value );
309  chamfered_corner.Append( signX[ii] * chamfer_value, 0 );
310  chamfered_corner.Move( corner_pos );
311  outline.BooleanSubtract( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
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 
326  wxPoint aStart, wxPoint aEnd,
327  int aError, int aWidth )
328 {
329  int radius = aWidth / 2;
330  wxPoint endp = aEnd - aStart; // end point coordinate for the same segment starting at (0,0)
331  wxPoint startp = aStart;
332  wxPoint corner;
333  VECTOR2I polypoint;
334  int numSegs = std::max( GetArcToSegmentCount( radius, aError, 360.0 ), 6 );
335  double correction = GetCircletoPolyCorrectionFactor( numSegs );
336  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
337 
338  radius = KiROUND( radius * correction );
339  aCornerBuffer.NewOutline();
340 
341  // normalize the position in order to have endp.x >= 0;
342  if( endp.x < 0 )
343  {
344  endp = aStart - aEnd;
345  startp = aEnd;
346  }
347 
348  double delta_angle = ArcTangente( endp.y, endp.x ); // delta_angle is in 0.1 degrees
349  int seg_len = KiROUND( EuclideanNorm( endp ) );
350 
351  // Compute the outlines of the segment, and creates a polygon
352  // add right rounded end:
353  for( int ii = 0; ii < 1800; ii += delta )
354  {
355  corner = wxPoint( 0, radius );
356  RotatePoint( &corner, ii );
357  corner.x += seg_len;
358  RotatePoint( &corner, -delta_angle );
359  corner += startp;
360  polypoint.x = corner.x;
361  polypoint.y = corner.y;
362  aCornerBuffer.Append( polypoint.x, polypoint.y );
363  }
364 
365  // Finish arc:
366  corner = wxPoint( seg_len, -radius );
367  RotatePoint( &corner, -delta_angle );
368  corner += startp;
369  polypoint.x = corner.x;
370  polypoint.y = corner.y;
371  aCornerBuffer.Append( polypoint.x, polypoint.y );
372 
373  // add left rounded end:
374  for( int ii = 0; ii < 1800; ii += delta )
375  {
376  corner = wxPoint( 0, -radius );
377  RotatePoint( &corner, ii );
378  RotatePoint( &corner, -delta_angle );
379  corner += startp;
380  polypoint.x = corner.x;
381  polypoint.y = corner.y;
382  aCornerBuffer.Append( polypoint.x, polypoint.y );
383  }
384 
385  // Finish arc:
386  corner = wxPoint( 0, radius );
387  RotatePoint( &corner, -delta_angle );
388  corner += startp;
389  polypoint.x = corner.x;
390  polypoint.y = corner.y;
391  aCornerBuffer.Append( polypoint.x, polypoint.y );
392 }
393 
394 
396  wxPoint aCentre, wxPoint aStart, double aArcAngle,
397  int aError, int aWidth )
398 {
399  wxPoint arc_start, arc_end;
400  int dist = EuclideanNorm( aCentre - aStart );
401  int numSegs = std::max( GetArcToSegmentCount( dist, aError, 360.0 ), 6 );
402  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
403 
404  arc_end = arc_start = aStart;
405 
406  if( aArcAngle != 3600 )
407  {
408  RotatePoint( &arc_end, aCentre, -aArcAngle );
409  }
410 
411  if( aArcAngle < 0 )
412  {
413  std::swap( arc_start, arc_end );
414  aArcAngle = -aArcAngle;
415  }
416 
417  // Compute the ends of segments and creates poly
418  wxPoint curr_end = arc_start;
419  wxPoint curr_start = arc_start;
420 
421  for( int ii = delta; ii < aArcAngle; ii += delta )
422  {
423  curr_end = arc_start;
424  RotatePoint( &curr_end, aCentre, -ii );
425  TransformSegmentToPolygon( aCornerBuffer, curr_start, curr_end, aError,
426  aWidth );
427  curr_start = curr_end;
428  }
429 
430  if( curr_end != arc_end )
431  TransformSegmentToPolygon( aCornerBuffer, curr_end, arc_end, aError, aWidth );
432 }
433 
434 
436  wxPoint aCentre, int aRadius,
437  int aError, int aWidth )
438 {
439  // Compute the corners positions and creates the poly
440  wxPoint curr_point;
441  int inner_radius = aRadius - ( aWidth / 2 );
442  int outer_radius = inner_radius + aWidth;
443 
444  if( inner_radius <= 0 )
445  { //In this case, the ring is just a circle (no hole inside)
446  TransformCircleToPolygon( aCornerBuffer, aCentre, aRadius + ( aWidth / 2 ), aError );
447  return;
448  }
449 
450  SHAPE_POLY_SET buffer;
451 
452  TransformCircleToPolygon( buffer, aCentre, outer_radius, aError );
453 
454  // Build the hole:
455  buffer.NewHole();
456  TransformCircleToPolygon( buffer.Hole( 0, 0 ), aCentre, inner_radius, aError );
457 
459  aCornerBuffer.Append( buffer );
460 }
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 Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 })
Function Rotate rotates all vertices by a given angle.
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 TransformCircleToPolygon(SHAPE_LINE_CHAIN &aBuffer, wxPoint aCenter, int aRadius, int aError)
static const int dist[10][10]
Definition: ar_matrix.cpp:326
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 aApproxErrorMax, int aMinSegPerCircleCount)
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
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 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.
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:61
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 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)