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/vector2d.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...
 

Macros

#define DOT_WIDTH_MILS   0.0254
 Dashed and dotted line patterns. More...
 
#define DOT_MARK_LEN(aLineWidth)   ( std::max( 1.0, IU_PER_MILS * DOT_WIDTH_MILS - aLineWidth ) )
 
#define DASH_GAP_LEN(aLineWidth)   ( 3.0 * DOT_MARK_LEN( aLineWidth ) + ( 2.0 * aLineWidth ) )
 
#define DASH_MARK_LEN(aLineWidth)   ( std::max( DASH_GAP_LEN( aLineWidth ), 5.0 * DOT_MARK_LEN( aLineWidth ) ) )
 

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, double aArcAngleDegree)
 
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...
 
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...
 

Detailed Description

a few functions useful in geometry calculations.

Definition in file geometry_utils.h.

Macro Definition Documentation

◆ DASH_GAP_LEN

#define DASH_GAP_LEN (   aLineWidth)    ( 3.0 * DOT_MARK_LEN( aLineWidth ) + ( 2.0 * aLineWidth ) )

Definition at line 164 of file geometry_utils.h.

◆ DASH_MARK_LEN

#define DASH_MARK_LEN (   aLineWidth)    ( std::max( DASH_GAP_LEN( aLineWidth ), 5.0 * DOT_MARK_LEN( aLineWidth ) ) )

Definition at line 167 of file geometry_utils.h.

◆ DOT_MARK_LEN

#define DOT_MARK_LEN (   aLineWidth)    ( std::max( 1.0, IU_PER_MILS * DOT_WIDTH_MILS - aLineWidth ) )

Definition at line 161 of file geometry_utils.h.

◆ DOT_WIDTH_MILS

#define DOT_WIDTH_MILS   0.0254

Dashed and dotted line patterns.

Note: these are all macros because they're included from files with different IU definitions.

Definition at line 159 of 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 45 of file geometry_utils.h.

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

References delta, and KiROUND().

Referenced by ConvertArcToPolyline(), SHAPE_ARC::ConvertToPolyline(), CornerListToPolygon(), TransformArcToPolygon(), 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 clipOutCode(const EDA_RECT *aClipBox, int x, int y)
int GetX() const
Definition: eda_rect.h:98
int GetBottom() const
Definition: eda_rect.h:114
int GetRight() const
Definition: eda_rect.h:111
int GetY() const
Definition: eda_rect.h:99

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

Referenced by KIGFX::SCH_PAINTER::draw(), GRCSegm(), GRLineArray(), SCH_BUS_ENTRY_BASE::Print(), SCH_LINE::Print(), KIGFX::ORIGIN_VIEWITEM::ViewDraw(), and WinClipAndDrawLine().

◆ GetArcToSegmentCount()

int GetArcToSegmentCount ( int  aRadius,
int  aErrorMax,
double  aArcAngleDegree 
)
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 in degrees

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( aArcAngleDegree ) / arc_increment );
61 
62  // Ensure at least two segments are used for algorithmic safety
63  return std::max( segCount, 2 );
64 }
#define MIN_SEGCOUNT_FOR_CIRCLE
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

References KiROUND(), and MIN_SEGCOUNT_FOR_CIRCLE.

Referenced by SHAPE_POLY_SET::chamferFilletPolygon(), ZONE_FILLER::computeRawFilledArea(), 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::fillSingleZone(), gen_arc(), BOARD_ADAPTER::GetCircleSegmentCount(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PlotStandardLayer(), TransformCircleToPolygon(), TransformOvalToPolygon(), PAD::TransformShapeWithClearanceToPolygon(), ZONE::TransformShapeWithClearanceToPolygon(), ZONE::TransformSmoothedOutlineToPolygon(), and ZONE::TransformSolidAreasShapesToPolygon().

◆ 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().

◆ 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 107 of file geometry_utils.h.

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

References VECTOR2< T >::x, and VECTOR2< T >::y.

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