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
34#include <math/util.h> // for KiROUND
35
36// To approximate a circle by segments, a minimal seg count is mandatory.
37// Note that this is rarely used as the maxError constraint will yield a higher
38// segment count on everything but very small circles. (Even a 0.125mm track
39// with a 0.01mm maximum deviation yields 11 segments.)
40#define MIN_SEGCOUNT_FOR_CIRCLE 8
41
42int GetArcToSegmentCount( int aRadius, int aErrorMax, const EDA_ANGLE& aArcAngle )
43{
44 // calculate the number of segments to approximate a circle by segments
45 // given the max distance between the middle of a segment and the circle
46
47 // avoid divide-by-zero
48 aRadius = std::max( 1, aRadius );
49
50 // error relative to the radius value:
51 double rel_error = (double)aErrorMax / aRadius;
52 // minimal arc increment in degrees:
53 double arc_increment = 180 / M_PI * acos( 1.0 - rel_error ) * 2;
54
55 // Ensure a minimal arc increment reasonable value for a circle
56 // (360.0 degrees). For very small radius values, this is mandatory.
57 arc_increment = std::min( 360.0/MIN_SEGCOUNT_FOR_CIRCLE, arc_increment );
58
59 int segCount = KiROUND( fabs( aArcAngle.AsDegrees() ) / arc_increment );
60
61 // Ensure at least two segments are used for algorithmic safety
62 return std::max( segCount, 2 );
63}
64
65
66int CircleToEndSegmentDeltaRadius( int aRadius, int aSegCount )
67{
68 // The minimal seg count is 3, otherwise we cannot calculate the result
69 // in practice, the min count is clamped to 8 in kicad
70 if( aSegCount <= 2 )
71 aSegCount = 3;
72
73 // The angle between the center of the segment and one end of the segment
74 // when the circle is approximated by aSegCount segments
75 double alpha = M_PI / aSegCount;
76
77 // aRadius is the radius of the circle tangent to the middle of each segment
78 // and aRadius/cos(aplha) is the radius of the circle defined by seg ends
79 int delta = KiROUND( aRadius * ( 1/cos(alpha) - 1 ) );
80
81 return delta;
82}
83
84// When creating polygons to create a clearance polygonal area, the polygon must
85// be same or bigger than the original shape.
86// Polygons are bigger if the original shape has arcs (round rectangles, ovals,
87// circles...). However, when building the solder mask layer modifying the shapes
88// when converting them to polygons is not acceptable (the modification can break
89// calculations).
90// So one can disable the shape expansion within a particular scope by allocating
91// a DISABLE_ARC_CORRECTION.
92
93static bool s_disable_arc_correction = false;
94
96{
98}
99
101{
103}
104
105int GetCircleToPolyCorrection( int aMaxError )
106{
107 // Push all the error to the outside by increasing the radius
108 return s_disable_arc_correction ? 0 : aMaxError;
109}
110
111
112/***
113 * Utility for the line clipping code, returns the boundary code of
114 * a point. Bit allocation is arbitrary
115 */
116inline int clipOutCode( const BOX2I *aClipBox, int x, int y )
117{
118 int code;
119
120 if( y < aClipBox->GetY() )
121 code = 2;
122 else if( y > aClipBox->GetBottom() )
123 code = 1;
124 else
125 code = 0;
126
127 if( x < aClipBox->GetX() )
128 code |= 4;
129 else if( x > aClipBox->GetRight() )
130 code |= 8;
131
132 return code;
133}
134
135
136bool ClipLine( const BOX2I *aClipBox, int &x1, int &y1, int &x2, int &y2 )
137{
138 // Stock Cohen-Sutherland algorithm; check *any* CG book for details
139 int outcode1 = clipOutCode( aClipBox, x1, y1 );
140 int outcode2 = clipOutCode( aClipBox, x2, y2 );
141
142 while( outcode1 || outcode2 )
143 {
144 // Fast reject
145 if( outcode1 & outcode2 )
146 return true;
147
148 // Choose a side to clip
149 int thisoutcode, x, y;
150
151 if( outcode1 )
152 thisoutcode = outcode1;
153 else
154 thisoutcode = outcode2;
155
156 /* One clip round
157 * Since we use the full range of 32 bit ints, the proportion
158 * computation has to be done in 64 bits to avoid horrible
159 * results */
160 if( thisoutcode & 1 ) // Clip the bottom
161 {
162 y = aClipBox->GetBottom();
163 x = x1 + (x2 - x1) * std::int64_t(y - y1) / (y2 - y1);
164 }
165 else if( thisoutcode & 2 ) // Clip the top
166 {
167 y = aClipBox->GetY();
168 x = x1 + ( x2 - x1 ) * std::int64_t( y - y1 ) / ( y2 - y1 );
169 }
170 else if( thisoutcode & 8 ) // Clip the right
171 {
172 x = aClipBox->GetRight();
173 y = y1 + ( y2 - y1 ) * std::int64_t( x - x1 ) / ( x2 - x1 );
174 }
175 else // if( thisoutcode & 4), obviously, clip the left
176 {
177 x = aClipBox->GetX();
178 y = y1 + ( y2 - y1 ) * std::int64_t( x - x1 ) / ( x2 - x1 );
179 }
180
181 // Put the result back and update the boundary code
182 // No ambiguity, otherwise it would have been a fast reject
183 if( thisoutcode == outcode1 )
184 {
185 x1 = x;
186 y1 = y;
187 outcode1 = clipOutCode( aClipBox, x1, y1 );
188 }
189 else
190 {
191 x2 = x;
192 y2 = y;
193 outcode2 = clipOutCode( aClipBox, x2, y2 );
194 }
195 }
196
197 return false;
198}
199
coord_type GetY() const
Definition: box2.h:181
coord_type GetX() const
Definition: box2.h:180
coord_type GetRight() const
Definition: box2.h:189
coord_type GetBottom() const
Definition: box2.h:190
double AsDegrees() const
Definition: eda_angle.h:149
int GetCircleToPolyCorrection(int aMaxError)
static bool s_disable_arc_correction
int CircleToEndSegmentDeltaRadius(int aRadius, int aSegCount)
int clipOutCode(const BOX2I *aClipBox, int x, int y)
bool ClipLine(const BOX2I *aClipBox, int &x1, int &y1, int &x2, int &y2)
Test if any part of a line falls within the bounds of a rectangle.
int GetArcToSegmentCount(int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
#define MIN_SEGCOUNT_FOR_CIRCLE
a few functions useful in geometry calculations.
constexpr int delta
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:80