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

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

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

84 {
85  int code;
86 
87  if( y < aClipBox->GetY() )
88  code = 2;
89  else if( y > aClipBox->GetBottom() )
90  code = 1;
91  else
92  code = 0;
93 
94  if( x < aClipBox->GetX() )
95  code |= 4;
96  else if( x > aClipBox->GetRight() )
97  code |= 8;
98 
99  return code;
100 }
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().

◆ 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:61

References KiROUND(), and MIN_SEGCOUNT_FOR_CIRCLE.

Referenced by ZONE_FILLER::addKnockout(), D_PAD::buildCustomPadPolygon(), SHAPE_POLY_SET::chamferFilletPolygon(), ZONE_FILLER::computeRawFilledArea(), ConvertOutlineToPolygon(), SHAPE_ARC::ConvertToPolyline(), export_vrml_polygon(), ZONE_FILLER::fillSingleZone(), gen_arc(), CINFO3D_VISU::GetNrSegmentsCircle(), EAGLE_PLUGIN::loadPolygon(), EAGLE_PLUGIN::loadSignals(), DSN::SPECCTRA_DB::makeIMAGE(), EAGLE_PLUGIN::packagePolygon(), PlotSolderMaskLayer(), PlotStandardLayer(), D_PAD::PrintShape(), 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
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 64 of file geometry_utils.cpp.

65 {
66  /* calculates the coeff to compensate radius reduction of circle
67  * due to the segment approx.
68  * For a circle the min radius is radius * cos( 2PI / aSegCountforCircle / 2)
69  * this is the distance between the center and the middle of the segment.
70  * therefore, to move the middle of the segment to the circle (distance = radius)
71  * the correctionFactor is 1 /cos( PI/aSegCountforCircle )
72  */
73  aSegCountforCircle = std::max( MIN_SEGCOUNT_FOR_CIRCLE, aSegCountforCircle );
74 
75  return 1.0 / cos( M_PI / aSegCountforCircle );
76 }
#define MIN_SEGCOUNT_FOR_CIRCLE

References MIN_SEGCOUNT_FOR_CIRCLE.

Referenced by ZONE_FILLER::addKnockout(), CINFO3D_VISU::GetCircleCorrectionFactor(), TransformCircleToPolygon(), TransformOvalToPolygon(), TransformSegmentToPolygon(), and D_PAD::TransformShapeWithClearanceToPolygon().