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

Functions

int GetArcToSegmentCount (int aRadius, int aErrorMax, double aArcAngleDegree)
 
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 147 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 150 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 144 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 142 of file geometry_utils.h.

Function Documentation

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

119 {
120  // Stock Cohen-Sutherland algorithm; check *any* CG book for details
121  int outcode1 = clipOutCode( aClipBox, x1, y1 );
122  int outcode2 = clipOutCode( aClipBox, x2, y2 );
123 
124  while( outcode1 || outcode2 )
125  {
126  // Fast reject
127  if( outcode1 & outcode2 )
128  return true;
129 
130  // Choose a side to clip
131  int thisoutcode, x, y;
132 
133  if( outcode1 )
134  thisoutcode = outcode1;
135  else
136  thisoutcode = outcode2;
137 
138  /* One clip round
139  * Since we use the full range of 32 bit ints, the proportion
140  * computation has to be done in 64 bits to avoid horrible
141  * results */
142  if( thisoutcode & 1 ) // Clip the bottom
143  {
144  y = aClipBox->GetBottom();
145  x = x1 + (x2 - x1) * int64_t(y - y1) / (y2 - y1);
146  }
147  else if( thisoutcode & 2 ) // Clip the top
148  {
149  y = aClipBox->GetY();
150  x = x1 + (x2 - x1) * int64_t(y - y1) / (y2 - y1);
151  }
152  else if( thisoutcode & 8 ) // Clip the right
153  {
154  x = aClipBox->GetRight();
155  y = y1 + (y2 - y1) * int64_t(x - x1) / (x2 - x1);
156  }
157  else // if( thisoutcode & 4), obviously, clip the left
158  {
159  x = aClipBox->GetX();
160  y = y1 + (y2 - y1) * int64_t(x - x1) / (x2 - x1);
161  }
162 
163  // Put the result back and update the boundary code
164  // No ambiguity, otherwise it would have been a fast reject
165  if( thisoutcode == outcode1 )
166  {
167  x1 = x;
168  y1 = y;
169  outcode1 = clipOutCode( aClipBox, x1, y1 );
170  }
171  else
172  {
173  x2 = x;
174  y2 = y;
175  outcode2 = clipOutCode( aClipBox, x2, y2 );
176  }
177  }
178  return false;
179 }
int clipOutCode(const EDA_RECT *aClipBox, int x, int y)
int GetX() const
Definition: eda_rect.h:111
int GetBottom() const
Definition: eda_rect.h:124
int GetRight() const
Definition: eda_rect.h:121
int GetY() const
Definition: eda_rect.h:112

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

Referenced by KIGFX::SCH_PAINTER::draw(), GRCSegm(), GRLineArray(), 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:68

References KiROUND(), and MIN_SEGCOUNT_FOR_CIRCLE.

Referenced by SHAPE_POLY_SET::chamferFilletPolygon(), ZONE_FILLER::computeRawFilledArea(), ConvertOutlineToPolygon(), SHAPE_ARC::ConvertToPolyline(), BOARD_ADAPTER::createNewTrack(), export_vrml_polygon(), ZONE_FILLER::fillSingleZone(), gen_arc(), BOARD_ADAPTER::GetNrSegmentsCircle(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), DSN::SPECCTRA_DB::makeIMAGE(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PlotStandardLayer(), TransformArcToPolygon(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), D_PAD::TransformShapeWithClearanceToPolygon(), ZONE_CONTAINER::TransformSmoothedOutlineWithClearanceToPolygon(), and ZONE_CONTAINER::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 87 of file geometry_utils.cpp.

88 {
89  // Push all the error to the outside by increasing the radius
90  return s_disable_arc_correction ? 0 : aMaxError;
91 }
static bool s_disable_arc_correction

References s_disable_arc_correction.

Referenced by TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), and D_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 co-ordinates 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 90 of file geometry_utils.h.

91 {
92  auto newVec = aVec;
93  const VECTOR2<T> absVec { std::abs( aVec.x ), std::abs( aVec.y ) };
94 
95  if ( !only45 && absVec.x > absVec.y * 2 )
96  {
97  // snap along x-axis
98  newVec.y = 0;
99  }
100  else if ( !only45 && absVec.y > absVec.x * 2 )
101  {
102  // snap onto y-axis
103  newVec.x = 0;
104  }
105  else if ( absVec.x > absVec.y )
106  {
107  // snap away from x-axis towards 45
108  newVec.y = std::copysign( aVec.x, aVec.y );
109  } else
110  {
111  // snap away from y-axis towards 45
112  newVec.x = std::copysign( aVec.y, aVec.x );
113  }
114 
115  return newVec;
116 }
VECTOR2 defines a general 2D-vector/point.
Definition: vector2d.h:61

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

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