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  SHAPE_POLY_SET outline;
196 
197  wxPoint centers[4];
198  wxSize size( aSize / 2 );
199 
200  size.x -= aCornerRadius;
201  size.y -= aCornerRadius;
202 
203  // Ensure size is > 0, to avoid generating unusable shapes which can crash kicad.
204  size.x = std::max( 1, size.x );
205  size.y = std::max( 1, size.y );
206 
207  centers[0] = wxPoint( -size.x, size.y );
208  centers[1] = wxPoint( size.x, size.y );
209  centers[2] = wxPoint( size.x, -size.y );
210  centers[3] = wxPoint( -size.x, -size.y );
211 
212  int numSegs = GetArcToSegmentCount( aCornerRadius, aError, 360.0 );
213 
214  // Choppy corners on rounded-corner rectangles look awful so enforce a minimum of
215  // 4 segments per corner.
216  if( numSegs < 16 )
217  numSegs = 16;
218 
219  int delta = 3600 / numSegs; // rotate angle in 0.1 degree
220  int radius = aCornerRadius;
221 
222  if( aErrorLoc == ERROR_OUTSIDE )
223  radius += GetCircleToPolyCorrection( aError );
224 
225  auto genArc =
226  [&]( const wxPoint& aCenter, int aStart, int aEnd )
227  {
228  for( int angle = aStart + delta; angle < aEnd; angle += delta )
229  {
230  wxPoint pt( -radius, 0 );
231  RotatePoint( &pt, angle );
232  pt += aCenter;
233  outline.Append( pt.x, pt.y );
234  }
235  };
236 
237  outline.NewOutline();
238 
239  outline.Append( centers[0] + wxPoint( -radius, 0 ) );
240  genArc( centers[0], 0, 900 );
241  outline.Append( centers[0] + wxPoint( 0, radius ) );
242  outline.Append( centers[1] + wxPoint( 0, radius ) );
243  genArc( centers[1], 900, 1800 );
244  outline.Append( centers[1] + wxPoint( radius, 0 ) );
245  outline.Append( centers[2] + wxPoint( radius, 0 ) );
246  genArc( centers[2], 1800, 2700 );
247  outline.Append( centers[2] + wxPoint( 0, -radius ) );
248  outline.Append( centers[3] + wxPoint( 0, -radius ) );
249  genArc( centers[3], 2700, 3600 );
250  outline.Append( centers[3] + wxPoint( -radius, 0 ) );
251 
252  outline.Outline( 0 ).SetClosed( true );
253 
254  // The created outlines are bigger than the actual outlines, due to the fact
255  // the corner radius is bigger than the initial value when building a shape outside the
256  // actual shape.
257  // However the bounding box shape does not need to be bigger: only rounded corners must
258  // be modified.
259  // So clamp the too big shape by the actual bounding box
260  if( aErrorLoc == ERROR_OUTSIDE )
261  {
262  SHAPE_POLY_SET bbox;
263  bbox.NewOutline();
264  wxSize bbox_size = aSize/2;
265 
266  bbox.Append( wxPoint( -bbox_size.x, -bbox_size.y ) );
267  bbox.Append( wxPoint( bbox_size.x, -bbox_size.y ) );
268  bbox.Append( wxPoint( bbox_size.x, bbox_size.y ) );
269  bbox.Append( wxPoint( -bbox_size.x, bbox_size.y ) );
270  bbox.Outline( 0 ).SetClosed( true );
271 
273  // The result is a convex polygon, no need to simplify or fracture.
274  }
275 
276  // Add the outline:
277  aCornerBuffer.Append( outline );
278 }
279 
280 
281 void TransformRoundChamferedRectToPolygon( SHAPE_POLY_SET& aCornerBuffer, const wxPoint& aPosition,
282  const wxSize& aSize, double aRotation,
283  int aCornerRadius, double aChamferRatio,
284  int aChamferCorners, int aError, ERROR_LOC aErrorLoc )
285 {
286  SHAPE_POLY_SET outline;
287  TransformRoundRectToPolygon( outline, aSize, aCornerRadius, aError, aErrorLoc );
288 
289  if( aChamferCorners )
290  {
291  // Now we have the round rect outline, in position 0,0 orientation 0.0.
292  // Chamfer the corner(s).
293  int chamfer_value = aChamferRatio * std::min( aSize.x, aSize.y );
294 
295  SHAPE_POLY_SET chamfered_corner; // corner shape for the current corner to chamfer
296 
297  int corner_id[4] =
298  {
301  };
302  // Depending on the corner position, signX[] and signY[] give the sign of chamfer
303  // coordinates relative to the corner position
304  // The first corner is the top left corner, then top right, bottom left and bottom right
305  int signX[4] = {1, -1, 1,-1 };
306  int signY[4] = {1, 1, -1,-1 };
307 
308  for( int ii = 0; ii < 4; ii++ )
309  {
310  if( (corner_id[ii] & aChamferCorners) == 0 )
311  continue;
312 
313  VECTOR2I corner_pos( -signX[ii]*aSize.x/2, -signY[ii]*aSize.y/2 );
314 
315  if( aCornerRadius )
316  {
317  // We recreate a rectangular area covering the full rounded corner
318  // (max size = aSize/2) to rebuild the corner before chamfering, to be sure
319  // the rounded corner shape does not overlap the chamfered corner shape:
320  chamfered_corner.RemoveAllContours();
321  chamfered_corner.NewOutline();
322  chamfered_corner.Append( 0, 0 );
323  chamfered_corner.Append( 0, signY[ii] * aSize.y / 2 );
324  chamfered_corner.Append( signX[ii] * aSize.x / 2, signY[ii] * aSize.y / 2 );
325  chamfered_corner.Append( signX[ii] * aSize.x / 2, 0 );
326  chamfered_corner.Move( corner_pos );
327  outline.BooleanAdd( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
328  }
329 
330  // Now chamfer this corner
331  chamfered_corner.RemoveAllContours();
332  chamfered_corner.NewOutline();
333  chamfered_corner.Append( 0, 0 );
334  chamfered_corner.Append( 0, signY[ii] * chamfer_value );
335  chamfered_corner.Append( signX[ii] * chamfer_value, 0 );
336  chamfered_corner.Move( corner_pos );
337  outline.BooleanSubtract( chamfered_corner, SHAPE_POLY_SET::PM_STRICTLY_SIMPLE );
338  }
339  }
340 
341  // Rotate and move the outline:
342  if( aRotation != 0.0 )
343  outline.Rotate( DECIDEG2RAD( -aRotation ), VECTOR2I( 0, 0 ) );
344 
345  outline.Move( VECTOR2I( aPosition ) );
346 
347  // Add the outline:
348  aCornerBuffer.Append( outline );
349 }
350 
351 
352 void TransformArcToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aStart, wxPoint aMid,
353  wxPoint aEnd, int aWidth, int aError, ERROR_LOC aErrorLoc )
354 {
355  SHAPE_ARC arc( aStart, aMid, aEnd, aWidth );
356  SHAPE_LINE_CHAIN arcSpine = arc.ConvertToPolyline( aError );
357 
358  if( aErrorLoc == ERROR_OUTSIDE )
359  aWidth += 2 * aError;
360  else
361  aWidth -= 2 * aError;
362 
363  for( int ii = 0; ii < arcSpine.GetSegmentCount(); ++ii )
364  {
365  SEG seg = arcSpine.GetSegment( ii );
366 
367  // Note that the error here is only for the rounded ends; we still need to shrink or
368  // expand the width above for the segments themselves.
369  TransformOvalToPolygon( aCornerBuffer, (wxPoint) seg.A, (wxPoint) seg.B, aWidth, aError,
370  aErrorLoc );
371  }
372 }
373 
374 
375 void TransformRingToPolygon( SHAPE_POLY_SET& aCornerBuffer, wxPoint aCentre, int aRadius,
376  int aWidth, int aError, ERROR_LOC aErrorLoc )
377 {
378  int inner_radius = aRadius - ( aWidth / 2 );
379  int outer_radius = inner_radius + aWidth;
380 
381  if( inner_radius <= 0 )
382  { //In this case, the ring is just a circle (no hole inside)
383  TransformCircleToPolygon( aCornerBuffer, aCentre, aRadius + ( aWidth / 2 ), aError,
384  aErrorLoc );
385  return;
386  }
387 
388  SHAPE_POLY_SET buffer;
389 
390  TransformCircleToPolygon( buffer, aCentre, outer_radius, aError, aErrorLoc );
391 
392  // Build the hole:
393  buffer.NewHole();
394  TransformCircleToPolygon( buffer.Hole( 0, 0 ), aCentre, inner_radius, aError, aErrorLoc );
395 
397  aCornerBuffer.Append( buffer );
398 }
double EuclideanNorm(const wxPoint &vector)
Euclidean norm of a 2D vector.
Definition: trigo.h:148
int NewHole(int aOutline=-1)
Adds a new outline to the set and returns its index.
virtual size_t GetSegmentCount() const override
void BooleanAdd(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset difference For aFastMode meaning, see function booleanOp.
void TransformArcToPolygon(SHAPE_POLY_SET &aCornerBuffer, wxPoint aStart, wxPoint aMid, wxPoint aEnd, int aWidth, int aError, ERROR_LOC aErrorLoc)
Function TransformArcToPolygon Creates a polygon from an Arc Convert arcs to multiple straight segmen...
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...
Define a general 2D-vector/point.
Definition: vector2d.h:61
void TransformCircleToPolygon(SHAPE_LINE_CHAIN &aCornerBuffer, wxPoint aCenter, int aRadius, int aError, ERROR_LOC aErrorLoc)
Function TransformCircleToPolygon convert a circle to a polygon, using multiple straight lines.
SHAPE_LINE_CHAIN & Hole(int aOutline, int aHole)
Return the aIndex-th subpolygon in the set.
void Rotate(double aAngle, const VECTOR2I &aCenter={ 0, 0 }) override
Rotate all vertices by a given angle.
void RotatePoint(int *pX, int *pY, double angle)
Definition: trigo.cpp:228
void TransformRoundRectToPolygon(SHAPE_POLY_SET &aCornerBuffer, const wxSize &aSize, int aCornerRadius, int aError, ERROR_LOC aErrorLoc)
VECTOR2< int > VECTOR2I
Definition: vector2d.h:623
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 SetClosed(bool aClosed)
Function SetClosed()
const SHAPE_LINE_CHAIN ConvertToPolyline(double aAccuracy=0.005 *PCB_IU_PER_MM) const
Constructs a SHAPE_LINE_CHAIN of segments from a given arc.
Definition: shape_arc.cpp:388
void Move(const VECTOR2I &aVector) override
Represent a set of closed polygons.
SHAPE_LINE_CHAIN & Outline(int aIndex)
virtual const SEG GetSegment(int aIndex) const override
a few functions useful in geometry calculations.
int GetCircleToPolyCorrection(int aMaxError)
void BooleanIntersection(const SHAPE_POLY_SET &b, POLYGON_MODE aFastMode)
Perform boolean polyset union between a and b, store the result in it self For aFastMode meaning,...
int NewOutline()
Creates a new hole in a given outline.
void Fracture(POLYGON_MODE aFastMode)
Convert a single outline slitted ("fractured") polygon into a set ouf outlines with holes.
Definition: seg.h:41
SHAPE_LINE_CHAIN.
static DIRECTION_45::AngleType angle(const VECTOR2I &a, const VECTOR2I &b)
VECTOR2I A
Definition: seg.h:49
double DECIDEG2RAD(double deg)
Definition: trigo.h:235
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)
Perform boolean polyset intersection 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)
Add a new vertex to the contour indexed by aOutline and aHole (defaults to the outline of the last po...
VECTOR2I B
Definition: seg.h:50