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