KiCad PCB EDA Suite
geometry_utils.cpp File Reference

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

#include <stdint.h>
#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   6
 

Functions

int GetArcToSegmentCount (int aRadius, int aErrorMax, double aArcAngleDegree)
 
void DisableArcRadiusCorrection (bool aDisable)
 When creating polygons to create a clearance polygonal area, the polygon must be same or bigger than the original shape. More...
 
double GetCircletoPolyCorrectionFactor (int aSegCountforCircle)
 
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   6

Definition at line 38 of file geometry_utils.cpp.

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

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

◆ clipOutCode()

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

Definition at line 99 of file geometry_utils.cpp.

100 {
101  int code;
102 
103  if( y < aClipBox->GetY() )
104  code = 2;
105  else if( y > aClipBox->GetBottom() )
106  code = 1;
107  else
108  code = 0;
109 
110  if( x < aClipBox->GetX() )
111  code |= 4;
112  else if( x > aClipBox->GetRight() )
113  code |= 8;
114 
115  return code;
116 }
int GetBottom() const
Definition: eda_rect.h:124
int GetRight() const
Definition: eda_rect.h:121

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

Referenced by ClipLine().

◆ DisableArcRadiusCorrection()

void DisableArcRadiusCorrection ( bool  aDisable)

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

Polygons are bigger if the original shape has arcs (round rectangles, ovals, circles...) In some cases (in fact only one: when building layer solder mask) modifying shapes when converting them to polygons is not acceptable (the modification can break calculations) so one can disable the shape expansion by calling DisableArcRadiusCorrection( true ) Important: calling DisableArcRadiusCorrection( false ) after calculations is mandatory to break oher calculations

Parameters
aDisable= false to create polygons same or outside the original shape = true to create polygons same or inside the original shape and minimize shape geometric changes

Definition at line 76 of file geometry_utils.cpp.

77 {
78  s_disable_arc_correction = aDisable;
79 }
static bool s_disable_arc_correction

References s_disable_arc_correction.

Referenced by PlotSolderMaskLayer().

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

41 {
42  // calculate the number of segments to approximate a circle by segments
43  // given the max distance between the middle of a segment and the circle
44 
45  // avoid divide-by-zero
46  aRadius = std::max( 1, aRadius );
47 
48  // error relative to the radius value:
49  double rel_error = (double)aErrorMax / aRadius;
50  // minimal arc increment in degrees:
51  double arc_increment = 180 / M_PI * acos( 1.0 - rel_error ) * 2;
52 
53  // Ensure a minimal arc increment reasonable value for a circle
54  // (360.0 degrees). For very small radius values, this is mandatory.
55  arc_increment = std::min( 360.0/MIN_SEGCOUNT_FOR_CIRCLE, arc_increment );
56 
57  int segCount = KiROUND( fabs( aArcAngleDegree ) / arc_increment );
58 
59  // Ensure at least one segment is used (can happen for small arcs)
60  return std::max( segCount, 1 );
61 }
#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(), ZONE_CONTAINER::TransformOutlinesShapeWithClearanceToPolygon(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), TransformSegmentToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

◆ GetCircletoPolyCorrectionFactor()

double GetCircletoPolyCorrectionFactor ( int  aSegCountforCircle)
Returns
the correction factor to approximate a circle by segments or 1.0 depending on the last call to DisableArcRadiusCorrection()
Parameters
aSegCountforCircleis the number of segments to approximate the circle

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 The correction factor is a scaling factor to apply to the radius to build a polygon outside the circle (only the middle of each segment is on the circle

Definition at line 81 of file geometry_utils.cpp.

82 {
83  /* calculates the coeff to compensate radius reduction of circle
84  * due to the segment approx.
85  * For a circle the min radius is radius * cos( 2PI / aSegCountforCircle / 2)
86  * this is the distance between the center and the middle of the segment.
87  * therefore, to move the middle of the segment to the circle (distance = radius)
88  * the correctionFactor is 1 /cos( PI/aSegCountforCircle )
89  */
90  aSegCountforCircle = std::max( MIN_SEGCOUNT_FOR_CIRCLE, aSegCountforCircle );
91  return s_disable_arc_correction ? 1.0 : 1.0 / cos( M_PI / aSegCountforCircle );
92 }
static bool s_disable_arc_correction
#define MIN_SEGCOUNT_FOR_CIRCLE

References MIN_SEGCOUNT_FOR_CIRCLE, and s_disable_arc_correction.

Referenced by BOARD_ADAPTER::GetCircleCorrectionFactor(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformRoundChamferedRectToPolygon(), TransformSegmentToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().

Variable Documentation

◆ s_disable_arc_correction

bool s_disable_arc_correction = false
static