KiCad PCB EDA Suite
geometry_utils.h File Reference

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

#include <math.h>
#include <stdlib.h>
#include <math/box2.h>
#include <geometry/eda_angle.h>

Go to the source code of this file.

Classes

class  DISABLE_ARC_RADIUS_CORRECTION
 When creating polygons to create a clearance polygonal area, the polygon must be same or bigger than the original shape. More...
 

Enumerations

enum  ERROR_LOC { ERROR_OUTSIDE , ERROR_INSIDE }
 When approximating an arc or circle, should the error be placed on the outside or inside of the curve? (Generally speaking filled shape errors go on the inside and knockout errors go on the outside. More...
 

Functions

int GetArcToSegmentCount (int aRadius, int aErrorMax, const EDA_ANGLE &aArcAngle)
 
int CircleToEndSegmentDeltaRadius (int aInnerCircleRadius, int aSegCount)
 
int GetCircleToPolyCorrection (int aMaxError)
 
template<typename T >
VECTOR2< T > GetVectorSnapped45 (const VECTOR2< T > &aVec, bool only45=false)
 Snap a vector onto the nearest 0, 45 or 90 degree line. More...
 
template<typename in_type , typename ret_type = in_type, typename pad_type = unsigned int, typename = typename std::enable_if<std::is_unsigned<pad_type>::value>::type>
VECTOR2< ret_type > GetClampedCoords (const VECTOR2< in_type > &aCoords, pad_type aPadding=0u)
 Clamps a vector to values that can be negated, respecting numeric limits of coordinates data type with specified padding. More...
 
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. More...
 

Detailed Description

a few functions useful in geometry calculations.

Definition in file geometry_utils.h.

Enumeration Type Documentation

◆ ERROR_LOC

enum ERROR_LOC

When approximating an arc or circle, should the error be placed on the outside or inside of the curve? (Generally speaking filled shape errors go on the inside and knockout errors go on the outside.

This preserves minimum clearances.)

Enumerator
ERROR_OUTSIDE 
ERROR_INSIDE 

Definition at line 43 of file geometry_utils.h.

@ ERROR_OUTSIDE
@ ERROR_INSIDE

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 66 of file geometry_utils.cpp.

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

References delta, and KiROUND().

Referenced by ConvertArcToPolyline(), SHAPE_ARC::ConvertToPolyline(), CornerListToPolygon(), SCH_SHAPE::Plot(), LIB_SHAPE::Plot(), TransformCircleToPolygon(), TransformOvalToPolygon(), and PAD::TransformShapeToPolygon().

◆ ClipLine()

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.

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 136 of file geometry_utils.cpp.

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}
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
int clipOutCode(const BOX2I *aClipBox, int x, int y)

References clipOutCode(), BOX2< Vec >::GetBottom(), BOX2< Vec >::GetRight(), BOX2< Vec >::GetX(), and BOX2< Vec >::GetY().

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

◆ 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 42 of file geometry_utils.cpp.

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}
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::TransformShapeToPolygon(), PAD::TransformShapeToPolygon(), 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 105 of file geometry_utils.cpp.

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

References s_disable_arc_correction.

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

◆ GetClampedCoords()

template<typename in_type , typename ret_type = in_type, typename pad_type = unsigned int, typename = typename std::enable_if<std::is_unsigned<pad_type>::value>::type>
VECTOR2< ret_type > GetClampedCoords ( const VECTOR2< in_type > &  aCoords,
pad_type  aPadding = 0u 
)

Clamps a vector to values that can be negated, respecting numeric limits of coordinates data type with specified padding.

Numeric limits are (-2^31 + 1) to (2^31 - 1).

Takes care of rounding in case of floating point to integer conversion.

Parameters
aCoord- vector to clamp.
aPadding- padding from the limits. Must not be negative.
Returns
clamped vector.

Definition at line 148 of file geometry_utils.h.

149{
150 typedef std::numeric_limits<int> coord_limits;
151
152 long max = coord_limits::max() - aPadding;
153 long min = -max;
154
155 in_type x = aCoords.x;
156 in_type y = aCoords.y;
157
158 if( x < min )
159 x = min;
160 else if( x > max )
161 x = max;
162
163 if( y < min )
164 y = min;
165 else if( y > max )
166 y = max;
167
168 if( !std::is_integral<in_type>() && std::is_integral<ret_type>() )
169 return VECTOR2<ret_type>( KiROUND( x ), KiROUND( y ) );
170
171 return VECTOR2<ret_type>( x, y );
172}
Define a general 2D-vector/point.
Definition: vector2d.h:74

References KiROUND(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by DRAWING_TOOL::drawArc(), DRAWING_TOOL::DrawDimension(), DRAWING_TOOL::drawShape(), DRAWING_TOOL::DrawZone(), KIGFX::WX_VIEW_CONTROLS::ForceCursorPosition(), KIGFX::WX_VIEW_CONTROLS::GetCursorPosition(), KIGFX::WX_VIEW_CONTROLS::GetMousePosition(), EDIT_TOOL::getSafeMovement(), KIGFX::WX_VIEW_CONTROLS::onMotion(), DRAWING_TOOL::PlaceImage(), DRAWING_TOOL::PlaceImportedGraphics(), DRAWING_TOOL::PlaceText(), KIGFX::WX_VIEW_CONTROLS::refreshMouse(), KIGFX::WX_VIEW_CONTROLS::SetCrossHairCursorPosition(), KIGFX::WX_VIEW_CONTROLS::SetCursorPosition(), and KIGFX::WX_VIEW_CONTROLS::WarpMouseCursor().

◆ GetVectorSnapped45()

template<typename T >
VECTOR2< T > GetVectorSnapped45 ( const VECTOR2< T > &  aVec,
bool  only45 = false 
)

Snap a vector onto the nearest 0, 45 or 90 degree line.

The magnitude of the vector is NOT kept, instead the coordinates are set equal (and/or opposite) or to zero as needed. The effect of this is that if the starting vector is on a square grid, the resulting snapped vector will still be on the same grid.

Parameters
avector to be snapped
Returns
the snapped vector

Definition at line 105 of file geometry_utils.h.

106{
107 auto newVec = aVec;
108 const VECTOR2<T> absVec { std::abs( aVec.x ), std::abs( aVec.y ) };
109
110 if ( !only45 && absVec.x > absVec.y * 2 )
111 {
112 // snap along x-axis
113 newVec.y = 0;
114 }
115 else if ( !only45 && absVec.y > absVec.x * 2 )
116 {
117 // snap onto y-axis
118 newVec.x = 0;
119 }
120 else if ( absVec.x > absVec.y )
121 {
122 // snap away from x-axis towards 45
123 newVec.y = std::copysign( aVec.x, aVec.y );
124 } else
125 {
126 // snap away from y-axis towards 45
127 newVec.x = std::copysign( aVec.y, aVec.x );
128 }
129
130 return newVec;
131}
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401

References std::abs(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by EC_45DEGREE::Apply(), DRAWING_TOOL::constrainDimension(), EDIT_TOOL::doMoveSelection(), DRAWING_TOOL::drawShape(), KIGFX::PREVIEW::TWO_POINT_GEOMETRY_MANAGER::SetEnd(), and POLYGON_GEOM_MANAGER::updateLeaderPoints().