KiCad PCB EDA Suite
geometry_utils.cpp
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2018 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 1992-2021 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
30 #include <cstdint>
31 #include <algorithm> // for max, min
32 
33 #include <eda_rect.h>
35 #include <math/util.h> // for KiROUND
36 
37 // To approximate a circle by segments, a minimal seg count is mandatory.
38 // Note that this is rarely used as the maxError constraint will yield a higher
39 // segment count on everything but very small circles. (Even a 0.125mm track
40 // with a 0.01mm maximum deviation yields 11 segments.)
41 #define MIN_SEGCOUNT_FOR_CIRCLE 8
42 
43 int GetArcToSegmentCount( int aRadius, int aErrorMax, double aArcAngleDegree )
44 {
45  // calculate the number of segments to approximate a circle by segments
46  // given the max distance between the middle of a segment and the circle
47 
48  // avoid divide-by-zero
49  aRadius = std::max( 1, aRadius );
50 
51  // error relative to the radius value:
52  double rel_error = (double)aErrorMax / aRadius;
53  // minimal arc increment in degrees:
54  double arc_increment = 180 / M_PI * acos( 1.0 - rel_error ) * 2;
55 
56  // Ensure a minimal arc increment reasonable value for a circle
57  // (360.0 degrees). For very small radius values, this is mandatory.
58  arc_increment = std::min( 360.0/MIN_SEGCOUNT_FOR_CIRCLE, arc_increment );
59 
60  int segCount = KiROUND( fabs( aArcAngleDegree ) / arc_increment );
61 
62  // Ensure at least two segments are used for algorithmic safety
63  return std::max( segCount, 2 );
64 }
65 
66 
67 int CircleToEndSegmentDeltaRadius( int aRadius, int aSegCount )
68 {
69  // The minimal seg count is 3, otherwise we cannot calculate the result
70  // in practice, the min count is clamped to 8 in kicad
71  if( aSegCount <= 2 )
72  aSegCount = 3;
73 
74  // The angle between the center of the segment and one end of the segment
75  // when the circle is approximated by aSegCount segments
76  double alpha = M_PI / aSegCount;
77 
78  // aRadius is the radius of the circle tangent to the middle of each segment
79  // and aRadius/cos(aplha) is the radius of the circle defined by seg ends
80  int delta = KiROUND( aRadius * ( 1/cos(alpha) - 1 ) );
81 
82  return delta;
83 }
84 
85 // When creating polygons to create a clearance polygonal area, the polygon must
86 // be same or bigger than the original shape.
87 // Polygons are bigger if the original shape has arcs (round rectangles, ovals,
88 // circles...). However, when building the solder mask layer modifying the shapes
89 // when converting them to polygons is not acceptable (the modification can break
90 // calculations).
91 // So one can disable the shape expansion within a particular scope by allocating
92 // a DISABLE_ARC_CORRECTION.
93 
94 static bool s_disable_arc_correction = false;
95 
97 {
99 }
100 
102 {
103  s_disable_arc_correction = false;
104 }
105 
106 int GetCircleToPolyCorrection( int aMaxError )
107 {
108  // Push all the error to the outside by increasing the radius
109  return s_disable_arc_correction ? 0 : aMaxError;
110 }
111 
112 
113 /***
114  * Utility for the line clipping code, returns the boundary code of
115  * a point. Bit allocation is arbitrary
116  */
117 inline int clipOutCode( const EDA_RECT *aClipBox, int x, int y )
118 {
119  int code;
120 
121  if( y < aClipBox->GetY() )
122  code = 2;
123  else if( y > aClipBox->GetBottom() )
124  code = 1;
125  else
126  code = 0;
127 
128  if( x < aClipBox->GetX() )
129  code |= 4;
130  else if( x > aClipBox->GetRight() )
131  code |= 8;
132 
133  return code;
134 }
135 
136 
137 bool ClipLine( const EDA_RECT *aClipBox, int &x1, int &y1, int &x2, int &y2 )
138 {
139  // Stock Cohen-Sutherland algorithm; check *any* CG book for details
140  int outcode1 = clipOutCode( aClipBox, x1, y1 );
141  int outcode2 = clipOutCode( aClipBox, x2, y2 );
142 
143  while( outcode1 || outcode2 )
144  {
145  // Fast reject
146  if( outcode1 & outcode2 )
147  return true;
148 
149  // Choose a side to clip
150  int thisoutcode, x, y;
151 
152  if( outcode1 )
153  thisoutcode = outcode1;
154  else
155  thisoutcode = outcode2;
156 
157  /* One clip round
158  * Since we use the full range of 32 bit ints, the proportion
159  * computation has to be done in 64 bits to avoid horrible
160  * results */
161  if( thisoutcode & 1 ) // Clip the bottom
162  {
163  y = aClipBox->GetBottom();
164  x = x1 + (x2 - x1) * std::int64_t(y - y1) / (y2 - y1);
165  }
166  else if( thisoutcode & 2 ) // Clip the top
167  {
168  y = aClipBox->GetY();
169  x = x1 + ( x2 - x1 ) * std::int64_t( y - y1 ) / ( y2 - y1 );
170  }
171  else if( thisoutcode & 8 ) // Clip the right
172  {
173  x = aClipBox->GetRight();
174  y = y1 + ( y2 - y1 ) * std::int64_t( x - x1 ) / ( x2 - x1 );
175  }
176  else // if( thisoutcode & 4), obviously, clip the left
177  {
178  x = aClipBox->GetX();
179  y = y1 + ( y2 - y1 ) * std::int64_t( x - x1 ) / ( x2 - x1 );
180  }
181 
182  // Put the result back and update the boundary code
183  // No ambiguity, otherwise it would have been a fast reject
184  if( thisoutcode == outcode1 )
185  {
186  x1 = x;
187  y1 = y;
188  outcode1 = clipOutCode( aClipBox, x1, y1 );
189  }
190  else
191  {
192  x2 = x;
193  y2 = y;
194  outcode2 = clipOutCode( aClipBox, x2, y2 );
195  }
196  }
197  return false;
198 }
199 
int GetArcToSegmentCount(int aRadius, int aErrorMax, double aArcAngleDegree)
int clipOutCode(const EDA_RECT *aClipBox, int x, int y)
int CircleToEndSegmentDeltaRadius(int aRadius, int aSegCount)
int GetCircleToPolyCorrection(int aMaxError)
int GetX() const
Definition: eda_rect.h:98
int GetBottom() const
Definition: eda_rect.h:114
int GetRight() const
Definition: eda_rect.h:111
static bool s_disable_arc_correction
#define MIN_SEGCOUNT_FOR_CIRCLE
a few functions useful in geometry calculations.
bool ClipLine(const EDA_RECT *aClipBox, int &x1, int &y1, int &x2, int &y2)
Test if any part of a line falls within the bounds of a rectangle.
Handle the component boundary box.
Definition: eda_rect.h:42
int GetY() const
Definition: eda_rect.h:99
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:73
constexpr int delta