KiCad PCB EDA Suite
geometry_utils.cpp File Reference

a few functions useful in geometry calculations. More...

#include <cstdint>
#include <algorithm>
#include <eda_rect.h>
#include <geometry/geometry_utils.h>
#include <math/util.h>

Go to the source code of this file.

Macros

#define MIN_SEGCOUNT_FOR_CIRCLE   8
 

Functions

int GetArcToSegmentCount (int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
 
int CircleToEndSegmentDeltaRadius (int aRadius, int aSegCount)
 
int GetCircleToPolyCorrection (int aMaxError)
 
int clipOutCode (const EDA_RECT *aClipBox, int x, int y)
 
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. More...
 

Variables

static bool s_disable_arc_correction = false
 

Detailed Description

a few functions useful in geometry calculations.

Definition in file geometry_utils.cpp.

Macro Definition Documentation

◆ MIN_SEGCOUNT_FOR_CIRCLE

#define MIN_SEGCOUNT_FOR_CIRCLE   8

Definition at line 41 of file geometry_utils.cpp.

Function Documentation

◆ CircleToEndSegmentDeltaRadius()

int CircleToEndSegmentDeltaRadius ( int  aInnerCircleRadius,
int  aSegCount 
)
Returns
the radius diffence of the circle defined by segments inside the circle and the radius of the circle tangent to the middle of segments (defined by segments outside this circle)
Parameters
aInnerCircleRadiusis the radius of the circle tangent to the middle of segments
aSegCountis the seg count to approximate the circle

Definition at line 67 of file geometry_utils.cpp.

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}
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

References delta, and KiROUND().

Referenced by ConvertArcToPolyline(), SHAPE_ARC::ConvertToPolyline(), CornerListToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), and PAD::TransformShapeWithClearanceToPolygon().

◆ ClipLine()

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.

Please note that this is only accurate for lines that are one pixel wide.

Parameters
aClipBox- The rectangle to test.
x1- X coordinate of one end of a line.
y1- Y coordinate of one end of a line.
x2- X coordinate of the other end of a line.
y2- Y coordinate of the other end of a line.
Returns
- False if any part of the line lies within the rectangle.

Definition at line 137 of file geometry_utils.cpp.

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}
int GetY() const
Definition: eda_rect.h:113
int GetX() const
Definition: eda_rect.h:112
int GetRight() const
Definition: eda_rect.h:125
int GetBottom() const
Definition: eda_rect.h:128
int clipOutCode(const EDA_RECT *aClipBox, int x, int y)

References clipOutCode(), EDA_RECT::GetBottom(), EDA_RECT::GetRight(), EDA_RECT::GetX(), and EDA_RECT::GetY().

Referenced by KIGFX::PCB_PAINTER::draw(), STROKE_PARAMS::Stroke(), KIGFX::ORIGIN_VIEWITEM::ViewDraw(), and PCB_TRACK::ViewGetLOD().

◆ clipOutCode()

int clipOutCode ( const EDA_RECT aClipBox,
int  x,
int  y 
)
inline

Definition at line 117 of file geometry_utils.cpp.

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}

References EDA_RECT::GetBottom(), and EDA_RECT::GetRight().

Referenced by ClipLine().

◆ GetArcToSegmentCount()

int GetArcToSegmentCount ( int  aRadius,
int  aErrorMax,
const EDA_ANGLE aArcAngle 
)
Returns
the number of segments to approximate a arc by segments with a given max error (this number is >= 1)
Parameters
aRadiusis the radius od the circle or arc
aErrorMaxis the max error This is the max distance between the middle of a segment and the circle.
aArcAngleDegreeis the arc angle

Definition at line 43 of file geometry_utils.cpp.

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( aArcAngle.AsDegrees() ) / arc_increment );
61
62 // Ensure at least two segments are used for algorithmic safety
63 return std::max( segCount, 2 );
64}
double AsDegrees() const
Definition: eda_angle.h:149
#define MIN_SEGCOUNT_FOR_CIRCLE

References EDA_ANGLE::AsDegrees(), KiROUND(), and MIN_SEGCOUNT_FOR_CIRCLE.

Referenced by PDF_PLOTTER::Arc(), DRC_TEST_PROVIDER_SOLDER_MASK::buildRTrees(), SHAPE_POLY_SET::chamferFilletPolygon(), ConvertArcToPolyline(), ConvertOutlineToPolygon(), SHAPE_ARC::ConvertToPolyline(), CornerListToPolygon(), BOARD_ADAPTER::createTrack(), KIGFX::PCB_PAINTER::draw(), KIGFX::OPENGL_GAL::DrawArcSegment(), EXPORTER_PCB_VRML::ExportVrmlPadHole(), EXPORTER_PCB_VRML::ExportVrmlViaHoles(), ZONE_FILLER::fillCopperZone(), ZONE_FILLER::fillNonCopperZone(), gen_arc(), BOARD_ADAPTER::GetCircleSegmentCount(), EAGLE_PLUGIN::loadPlain(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), EAGLE_PLUGIN::packageCircle(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PlotStandardLayer(), TEARDROP_MANAGER::SetTeardrops(), TransformCircleToPolygon(), TransformOvalToPolygon(), ZONE::TransformShapeWithClearanceToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), and ZONE::TransformSmoothedOutlineToPolygon().

◆ GetCircleToPolyCorrection()

int GetCircleToPolyCorrection ( int  aMaxError)
Returns
the radius correction to approximate a circle.
Parameters
aMaxErroris the same error value used to calculate the number of segments.

When creating a polygon from a circle, the polygon is inside the circle. Only corners are on the circle. This is incorrect when building clearance areas of circles, that need to build the equivalent polygon outside the circle.

Definition at line 106 of file geometry_utils.cpp.

107{
108 // Push all the error to the outside by increasing the radius
109 return s_disable_arc_correction ? 0 : aMaxError;
110}
static bool s_disable_arc_correction

References s_disable_arc_correction.

Referenced by CornerListToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), and PAD::TransformShapeWithClearanceToPolygon().

Variable Documentation

◆ s_disable_arc_correction