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  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
101  double correction = GetCircletoPolyCorrectionFactor( numSegs );
102 
103  radius = radius * correction; // make segments outside the circles
104 
105  // end point is the coordinate relative to aStart
106  wxPoint endp = aEnd - aStart;
107  wxPoint startp = aStart;
108  wxPoint corner;
109  SHAPE_POLY_SET polyshape;
110 
111  polyshape.NewOutline();
112 
113  // normalize the position in order to have endp.x >= 0
114  // it makes calculations more easy to understand
115  if( endp.x < 0 )
116  {
117  endp = aStart - aEnd;
118  startp = aEnd;
119  }
120 
121  // delta_angle is in radian
122  double delta_angle = atan2( (double)endp.y, (double)endp.x );
123  int seg_len = KiROUND( EuclideanNorm( endp ) );
124 
125 
126  // Compute the outlines of the segment, and creates a polygon
127  // Note: the polygonal shape is built from the equivalent horizontal
128  // segment starting ar 0,0, and ending at seg_len,0
129 
130  // add right rounded end:
131  for( int ii = 0; ii < numSegs / 2; ii++ )
132  {
133  corner = wxPoint( 0, radius );
134  RotatePoint( &corner, delta * ii );
135  corner.x += seg_len;
136  polyshape.Append( corner.x, corner.y );
137  }
138 
139  // Finish arc:
140  corner = wxPoint( seg_len, -radius );
141  polyshape.Append( corner.x, corner.y );
142 
143  // add left rounded end:
144  for( int ii = 0; ii < numSegs / 2; ii++ )
145  {
146  corner = wxPoint( 0, -radius );
147  RotatePoint( &corner, delta * ii );
148  polyshape.Append( corner.x, corner.y );
149  }
150 
151  // Finish arc:
152  corner = wxPoint( 0, radius );
153  polyshape.Append( corner.x, corner.y );
154 
155  // Now, clamp the polygonal shape (too big) with the segment bounding box
156  // the polygonal shape bbox equivalent to the segment has a too big height,
157  // and the right width
158  if( correction > 1.0 )
159  {
160  SHAPE_POLY_SET bbox;
161  bbox.NewOutline();
162  // Build the bbox (a horizontal rectangle).
163  int halfwidth = aWidth / 2; // Use the exact segment width for the bbox height
164  corner.x = -radius - 2; // use a bbox width slightly bigger to avoid
165  // creating useless corner at segment ends
166  corner.y = halfwidth;
167  bbox.Append( corner.x, corner.y );
168  corner.y = -halfwidth;
169  bbox.Append( corner.x, corner.y );
170  corner.x = radius + seg_len + 2;
171  bbox.Append( corner.x, corner.y );
172  corner.y = halfwidth;
173  bbox.Append( corner.x, corner.y );
174 
175  // Now, clamp the shape
177  // Note the final polygon is a simple, convex polygon with no hole
178  // due to the shape of initial polygons
179  }
180 
181  // Rotate and move the polygon to its right location
182  polyshape.Rotate( delta_angle, VECTOR2I( 0, 0 ) );
183  polyshape.Move( startp );
184 
185  aCornerBuffer.Append( polyshape);
186 }
187 
188 
189 void GetRoundRectCornerCenters( wxPoint aCenters[4], int aRadius,
190  const wxPoint& aPosition, const wxSize& aSize, double aRotation )
191 {
192  wxSize size( aSize/2 );
193 
194  size.x -= aRadius;
195  size.y -= aRadius;
196 
197  // Ensure size is > 0, to avoid generating unusable shapes
198  // which can crash kicad.
199  if( size.x <= 1 )
200  size.x = 1;
201  if( size.y <= 1 )
202  size.y = 1;
203 
204  aCenters[0].x = -size.x;
205  aCenters[0].y = size.y;
206 
207  aCenters[1].x = size.x;
208  aCenters[1].y = size.y;
209 
210  aCenters[2].x = size.x;
211  aCenters[2].y = -size.y;
212 
213  aCenters[3].x = -size.x;
214  aCenters[3].y = -size.y;
215 
216  // Rotate the polygon
217  if( aRotation )
218  {
219  for( int ii = 0; ii < 4; ii++ )
220  RotatePoint( &aCenters[ii], aRotation );
221  }
222 
223  // move the polygon to the position
224  for( int ii = 0; ii < 4; ii++ )
225  aCenters[ii] += aPosition;
226 }
227 
228 
230  const wxPoint& aPosition, const wxSize& aSize,
231  double aRotation, int aCornerRadius,
232  double aChamferRatio, int aChamferCorners,
233  int aApproxErrorMax, int aMinSegPerCircleCount )
234 {
235  // Build the basic shape in orientation 0.0, position 0,0 for chamfered corners
236  // or in actual position/orientation for round rect only
237  wxPoint corners[4];
238  GetRoundRectCornerCenters( corners, aCornerRadius,
239  aChamferCorners ? wxPoint( 0, 0 ) : aPosition,
240  aSize, aChamferCorners ? 0.0 : aRotation );
241 
242  SHAPE_POLY_SET outline;
243  outline.NewOutline();
244 
245  for( int ii = 0; ii < 4; ++ii )
246  outline.Append( corners[ii].x, corners[ii].y );
247 
248  int numSegs = std::max( GetArcToSegmentCount( aCornerRadius, aApproxErrorMax, 360.0 ),
249  aMinSegPerCircleCount );
250  outline.Inflate( aCornerRadius, numSegs );
251 
252  if( aChamferCorners == RECT_NO_CHAMFER ) // no chamfer
253  {
254  // Add the outline:
255  aCornerBuffer.Append( outline );
256  return;
257  }
258 
259  // Now we have the round rect outline, in position 0,0 orientation 0.0.
260  // Chamfer the corner(s).
261  int chamfer_value = aChamferRatio * std::min( aSize.x, aSize.y );
262 
263  SHAPE_POLY_SET chamfered_corner; // corner shape for the current corner to chamfer
264 
265  int corner_id[4] =
266  {
269  };
270  // Depending on the corner position, signX[] and signY[] give the sign of chamfer
271  // coordinates relative to the corner position
272  // The first corner is the top left corner, then top right, bottom left and bottom right
273  int signX[4] = {1, -1, 1,-1 };
274  int signY[4] = {1, 1, -1,-1 };
275 
276  for( int ii = 0; ii < 4; ii++ )
277  {
278  if( (corner_id[ii] & aChamferCorners) == 0 )
279  continue;
280 
281  VECTOR2I corner_pos( -signX[ii]*aSize.x/2, -signY[ii]*aSize.y/2 );
282 
283  if( aCornerRadius )
284  {
285  // We recreate a rectangular area covering the full rounded corner (max size = aSize/2)
286  // to rebuild the corner before chamfering, to be sure the rounded corner shape does not
287  // overlap the chamfered corner shape:
288  chamfered_corner.RemoveAllContours();
289  chamfered_corner.NewOutline();
290  chamfered_corner.Append( 0, 0 );
291  chamfered_corner.Append( 0, signY[ii] * aSize.y / 2 );
292  chamfered_corner.Append( signX[ii] * aSize.x / 2, signY[ii] * aSize.y / 2 );
293  chamfered_corner.Append( signX[ii] * aSize.x / 2, 0 );
294  chamfered_corner.Move( corner_pos );
295  outline.BooleanAdd( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
296  }
297 
298  // Now chamfer this corner
299  chamfered_corner.RemoveAllContours();
300  chamfered_corner.NewOutline();
301  chamfered_corner.Append( 0, 0 );
302  chamfered_corner.Append( 0, signY[ii] * chamfer_value );
303  chamfered_corner.Append( signX[ii] * chamfer_value, 0 );
304  chamfered_corner.Move( corner_pos );
305  outline.BooleanSubtract( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
306  }
307 
308  // Rotate and move the outline:
309  if( aRotation != 0.0 )
310  outline.Rotate( DECIDEG2RAD( -aRotation ), VECTOR2I( 0, 0 ) );
311 
312  outline.Move( VECTOR2I( aPosition ) );
313 
314  // Add the outline:
315  aCornerBuffer.Append( outline );
316 }
317 
318 
320  wxPoint aStart, wxPoint aEnd,
321  int aError, int aWidth )
322 {
323  int radius = aWidth / 2;
324  wxPoint endp = aEnd - aStart; // end point coordinate for the same segment starting at (0,0)
325  wxPoint startp = aStart;
326  wxPoint corner;
327  VECTOR2I polypoint;
328  int numSegs = std::max( GetArcToSegmentCount( radius, aError, 360.0 ), 6 );
329  double correction = GetCircletoPolyCorrectionFactor( numSegs );
330  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
331 
332  radius = KiROUND( radius * correction );
333  aCornerBuffer.NewOutline();
334 
335  // normalize the position in order to have endp.x >= 0;
336  if( endp.x < 0 )
337  {
338  endp = aStart - aEnd;
339  startp = aEnd;
340  }
341 
342  double delta_angle = ArcTangente( endp.y, endp.x ); // delta_angle is in 0.1 degrees
343  int seg_len = KiROUND( EuclideanNorm( endp ) );
344 
345  // Compute the outlines of the segment, and creates a polygon
346  // add right rounded end:
347  for( int ii = 0; ii < 1800; ii += delta )
348  {
349  corner = wxPoint( 0, radius );
350  RotatePoint( &corner, ii );
351  corner.x += seg_len;
352  RotatePoint( &corner, -delta_angle );
353  corner += startp;
354  polypoint.x = corner.x;
355  polypoint.y = corner.y;
356  aCornerBuffer.Append( polypoint.x, polypoint.y );
357  }
358 
359  // Finish arc:
360  corner = wxPoint( seg_len, -radius );
361  RotatePoint( &corner, -delta_angle );
362  corner += startp;
363  polypoint.x = corner.x;
364  polypoint.y = corner.y;
365  aCornerBuffer.Append( polypoint.x, polypoint.y );
366 
367  // add left rounded end:
368  for( int ii = 0; ii < 1800; ii += delta )
369  {
370  corner = wxPoint( 0, -radius );
371  RotatePoint( &corner, ii );
372  RotatePoint( &corner, -delta_angle );
373  corner += startp;
374  polypoint.x = corner.x;
375  polypoint.y = corner.y;
376  aCornerBuffer.Append( polypoint.x, polypoint.y );
377  }
378 
379  // Finish arc:
380  corner = wxPoint( 0, radius );
381  RotatePoint( &corner, -delta_angle );
382  corner += startp;
383  polypoint.x = corner.x;
384  polypoint.y = corner.y;
385  aCornerBuffer.Append( polypoint.x, polypoint.y );
386 }
387 
388 
390  wxPoint aCentre, wxPoint aStart, double aArcAngle,
391  int aError, int aWidth )
392 {
393  wxPoint arc_start, arc_end;
394  int dist = EuclideanNorm( aCentre - aStart );
395  int numSegs = std::max( GetArcToSegmentCount( dist, aError, 360.0 ), 6 );
396  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
397 
398  arc_end = arc_start = aStart;
399 
400  if( aArcAngle != 3600 )
401  {
402  RotatePoint( &arc_end, aCentre, -aArcAngle );
403  }
404 
405  if( aArcAngle < 0 )
406  {
407  std::swap( arc_start, arc_end );
408  aArcAngle = -aArcAngle;
409  }
410 
411  // Compute the ends of segments and creates poly
412  wxPoint curr_end = arc_start;
413  wxPoint curr_start = arc_start;
414 
415  for( int ii = delta; ii < aArcAngle; ii += delta )
416  {
417  curr_end = arc_start;
418  RotatePoint( &curr_end, aCentre, -ii );
419  TransformSegmentToPolygon( aCornerBuffer, curr_start, curr_end, aError,
420  aWidth );
421  curr_start = curr_end;
422  }
423 
424  if( curr_end != arc_end )
425  TransformSegmentToPolygon( aCornerBuffer, curr_end, arc_end, aError, aWidth );
426 }
427 
428 
430  wxPoint aCentre, int aRadius,
431  int aError, int aWidth )
432 {
433  // Compute the corners positions and creates the poly
434  wxPoint curr_point;
435  int inner_radius = aRadius - ( aWidth / 2 );
436  int outer_radius = inner_radius + aWidth;
437 
438  if( inner_radius <= 0 )
439  { //In this case, the ring is just a circle (no hole inside)
440  TransformCircleToPolygon( aCornerBuffer, aCentre, aRadius + ( aWidth / 2 ), aError );
441  return;
442  }
443 
444  SHAPE_POLY_SET buffer;
445 
446  TransformCircleToPolygon( buffer, aCentre, outer_radius, aError );
447 
448  // Build the hole:
449  buffer.NewHole();
450  TransformCircleToPolygon( buffer.Hole( 0, 0 ), aCentre, inner_radius, aError );
451 
453  aCornerBuffer.Append( buffer );
454 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:123
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:214
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)