KiCad PCB EDA Suite
CIRCLE Class Reference

Represent basic circle geometry with utility geometry functions. More...

#include <circle.h>

Public Member Functions

 CIRCLE ()
 
 CIRCLE (const VECTOR2I &aCenter, int aRadius)
 
 CIRCLE (const CIRCLE &aOther)
 
CIRCLEConstructFromTanTanPt (const SEG &aLineA, const SEG &aLineB, const VECTOR2I &aP)
 Construct this circle such that it is tangent to the given segments and passes through the given point, generating the solution which can be used to fillet both segments. More...
 
bool Contains (const VECTOR2I &aP) const
 Return true if aP is on the circumference of this circle. More...
 
VECTOR2I NearestPoint (const VECTOR2I &aP) const
 Compute the point on the circumference of the circle that is the closest to aP. More...
 
std::vector< VECTOR2IIntersect (const CIRCLE &aCircle) const
 Compute the intersection points between this circle and aCircle. More...
 
std::vector< VECTOR2IIntersect (const SEG &aSeg) const
 Compute the intersection points between this circle and aSeg. More...
 
std::vector< VECTOR2IIntersectLine (const SEG &aLine) const
 Compute the intersection points between this circle and aLine. More...
 
bool Contains (const VECTOR2I &aP)
 Check whether point aP is inside this circle. More...
 

Public Attributes

int Radius
 Public to make access simpler. More...
 
VECTOR2I Center
 Public to make access simpler. More...
 

Detailed Description

Represent basic circle geometry with utility geometry functions.

Definition at line 32 of file circle.h.

Constructor & Destructor Documentation

◆ CIRCLE() [1/3]

CIRCLE::CIRCLE ( )

Definition at line 30 of file circle.cpp.

31{
32 Center = { 0, 0 };
33 Radius = 0;
34}
VECTOR2I Center
Public to make access simpler.
Definition: circle.h:116
int Radius
Public to make access simpler.
Definition: circle.h:115

References Center, and Radius.

◆ CIRCLE() [2/3]

CIRCLE::CIRCLE ( const VECTOR2I aCenter,
int  aRadius 
)

Definition at line 37 of file circle.cpp.

38{
39 Center = aCenter;
40 Radius = aRadius;
41}

References Center, and Radius.

◆ CIRCLE() [3/3]

CIRCLE::CIRCLE ( const CIRCLE aOther)

Definition at line 44 of file circle.cpp.

45{
46 Center = aOther.Center;
47 Radius = aOther.Radius;
48}

References Center, and Radius.

Member Function Documentation

◆ ConstructFromTanTanPt()

CIRCLE & CIRCLE::ConstructFromTanTanPt ( const SEG aLineA,
const SEG aLineB,
const VECTOR2I aP 
)

Construct this circle such that it is tangent to the given segments and passes through the given point, generating the solution which can be used to fillet both segments.

The caller is responsible for ensuring it is providing a solvable problem. This function will assert if this is not the case.

Parameters
aLineAis the first tangent line. Treated as an infinite line except for the purpose of selecting the solution to return.
aLineBis the second tangent line. Treated as an infinite line except for the purpose of selecting the solution to return.
aPis the point to pass through.
Returns
this circle.

Definition at line 51 of file circle.cpp.

52{
53 //fixme: There might be more efficient / accurate solution than using geometrical constructs
54
55 SEG anglebisector;
56 VECTOR2I intersectPoint;
57
58 auto furthestFromIntersect =
59 [&]( VECTOR2I aPt1, VECTOR2I aPt2 ) -> VECTOR2I
60 {
61 if( ( aPt1 - intersectPoint ).EuclideanNorm()
62 > ( aPt2 - intersectPoint ).EuclideanNorm() )
63 {
64 return aPt1;
65 }
66 else
67 {
68 return aPt2;
69 }
70 };
71
72 auto closestToIntersect =
73 [&]( VECTOR2I aPt1, VECTOR2I aPt2 ) -> VECTOR2I
74 {
75 if( ( aPt1 - intersectPoint ).EuclideanNorm()
76 <= ( aPt2 - intersectPoint ).EuclideanNorm() )
77 {
78 return aPt1;
79 }
80 else
81 {
82 return aPt2;
83 }
84 };
85
86 if( aLineA.ApproxParallel( aLineB ) )
87 {
88 // Special case, no intersection point between the two lines
89 // The center will be in the line equidistant between the two given lines
90 // The radius will be half the distance between the two lines
91 // The possible centers can be found by intersection
92
93 SEG perpendicularAtoB( aLineA.A, aLineB.LineProject( aLineA.A ) );
94 VECTOR2I midPt = perpendicularAtoB.Center();
95 Radius = ( midPt - aLineA.A ).EuclideanNorm();
96
97 anglebisector = aLineA.ParallelSeg( midPt );
98
99 Center = aP; // use this circle as a construction to find the actual centers
100 std::vector<VECTOR2I> possibleCenters = IntersectLine( anglebisector );
101
102 wxCHECK_MSG( possibleCenters.size() > 0, *this, wxT( "No solutions exist!" ) );
103 intersectPoint = aLineA.A; // just for the purpose of deciding which solution to return
104
105 // For the special case of the two segments being parallel, we will return the solution
106 // whose center is closest to aLineA.A
107 Center = closestToIntersect( possibleCenters.front(), possibleCenters.back() );
108 }
109 else
110 {
111 // General case, using homothety.
112 // All circles inscribed in the same angle are homothetic with center at the intersection
113 // In this code, the prefix "h" denotes "the homothetic image"
114 OPT_VECTOR2I intersectCalc = aLineA.IntersectLines( aLineB );
115 wxCHECK_MSG( intersectCalc, *this, wxT( "Lines do not intersect but are not parallel?" ) );
116 intersectPoint = *intersectCalc;
117
118 if( aP == intersectPoint )
119 {
120 //Special case: The point is at the intersection of the two lines
121 Center = aP;
122 Radius = 0;
123 return *this;
124 }
125
126 // Calculate bisector
127 VECTOR2I lineApt = furthestFromIntersect( aLineA.A, aLineA.B );
128 VECTOR2I lineBpt = furthestFromIntersect( aLineB.A, aLineB.B );
129 VECTOR2I bisectorPt = CalcArcMid( lineApt, lineBpt, intersectPoint, true );
130
131 anglebisector.A = intersectPoint;
132 anglebisector.B = bisectorPt;
133
134 // Create an arbitrary circle that is tangent to both lines
135 CIRCLE hSolution;
136 hSolution.Center = anglebisector.LineProject( aP );
137 hSolution.Radius = aLineA.LineDistance( hSolution.Center );
138
139 // Find the homothetic image of aP in the construction circle (hSolution)
140 SEG throughaP( intersectPoint, aP );
141 std::vector<VECTOR2I> hProjections = hSolution.IntersectLine( throughaP );
142 wxCHECK_MSG( hProjections.size() > 0, *this, wxT( "No solutions exist!" ) );
143
144 // We want to create a fillet, so the projection of homothetic projection of aP
145 // should be the one closest to the intersection
146 VECTOR2I hSelected = closestToIntersect( hProjections.front(), hProjections.back() );
147
148 VECTOR2I hTanLineA = aLineA.LineProject( hSolution.Center );
149 VECTOR2I hTanLineB = aLineB.LineProject( hSolution.Center );
150
151 // To minimise errors, use the furthest away tangent point from aP
152 if( ( hTanLineA - aP ).EuclideanNorm() > ( hTanLineB - aP ).EuclideanNorm() )
153 {
154 // Find the tangent at line A by homothetic inversion
155 SEG hT( hTanLineA, hSelected );
156 OPT_VECTOR2I actTanA = hT.ParallelSeg( aP ).IntersectLines( aLineA );
157 wxCHECK_MSG( actTanA, *this, wxT( "No solutions exist!" ) );
158
159 // Find circle center by perpendicular intersection with the angle bisector
160 SEG perpendicularToTanA = aLineA.PerpendicularSeg( *actTanA );
161 OPT_VECTOR2I actCenter = perpendicularToTanA.IntersectLines( anglebisector );
162 wxCHECK_MSG( actCenter, *this, wxT( "No solutions exist!" ) );
163
164 Center = *actCenter;
165 Radius = aLineA.LineDistance( Center );
166 }
167 else
168 {
169 // Find the tangent at line B by inversion
170 SEG hT( hTanLineB, hSelected );
171 OPT_VECTOR2I actTanB = hT.ParallelSeg( aP ).IntersectLines( aLineB );
172 wxCHECK_MSG( actTanB, *this, wxT( "No solutions exist!" ) );
173
174 // Find circle center by perpendicular intersection with the angle bisector
175 SEG perpendicularToTanB = aLineB.PerpendicularSeg( *actTanB );
176 OPT_VECTOR2I actCenter = perpendicularToTanB.IntersectLines( anglebisector );
177 wxCHECK_MSG( actCenter, *this, wxT( "No solutions exist!" ) );
178
179 Center = *actCenter;
180 Radius = aLineB.LineDistance( Center );
181 }
182 }
183
184 return *this;
185}
Represent basic circle geometry with utility geometry functions.
Definition: circle.h:33
std::vector< VECTOR2I > IntersectLine(const SEG &aLine) const
Compute the intersection points between this circle and aLine.
Definition: circle.cpp:288
Definition: seg.h:42
VECTOR2I A
Definition: seg.h:49
int LineDistance(const VECTOR2I &aP, bool aDetermineSide=false) const
Return the closest Euclidean distance between point aP and the line defined by the ends of segment (t...
Definition: seg.cpp:331
VECTOR2I B
Definition: seg.h:50
bool ApproxParallel(const SEG &aSeg, int aDistanceThreshold=1) const
Definition: seg.cpp:393
SEG ParallelSeg(const VECTOR2I &aP) const
Compute a segment parallel to this one, passing through point aP.
Definition: seg.cpp:208
OPT_VECTOR2I IntersectLines(const SEG &aSeg) const
Compute the intersection point of lines passing through ends of (this) and aSeg.
Definition: seg.h:210
VECTOR2I LineProject(const VECTOR2I &aP) const
Compute the perpendicular projection point of aP on a line passing through ends of the segment.
Definition: seg.cpp:302
SEG PerpendicularSeg(const VECTOR2I &aP) const
Compute a segment perpendicular to this one, passing through point aP.
Definition: seg.cpp:199
std::optional< VECTOR2I > OPT_VECTOR2I
Definition: seg.h:39
const VECTOR2I CalcArcMid(const VECTOR2I &aStart, const VECTOR2I &aEnd, const VECTOR2I &aCenter, bool aMinArcAngle=true)
Return the middle point of an arc, half-way between aStart and aEnd.
Definition: trigo.cpp:163
double EuclideanNorm(const VECTOR2I &vector)
Definition: trigo.h:129

References SEG::A, SEG::ApproxParallel(), SEG::B, CalcArcMid(), Center, SEG::Center(), EuclideanNorm(), IntersectLine(), SEG::IntersectLines(), SEG::LineDistance(), SEG::LineProject(), SEG::ParallelSeg(), SEG::PerpendicularSeg(), and Radius.

Referenced by BOOST_AUTO_TEST_CASE(), and EDIT_TOOL::DragArcTrack().

◆ Contains() [1/2]

bool CIRCLE::Contains ( const VECTOR2I aP)

Check whether point aP is inside this circle.

Parameters
aPThe point to check.
Returns
true if the point is inside, false otherwise.

Definition at line 343 of file circle.cpp.

344{
345 return ( aP - Center ).EuclideanNorm() < Radius;
346}

References Center, and Radius.

◆ Contains() [2/2]

bool CIRCLE::Contains ( const VECTOR2I aP) const

Return true if aP is on the circumference of this circle.

Note that there is an accepted margin of error of SHAPE::MIN_PRECISION_IU to account for integer rounding errors.

Parameters
aPA point to test
Returns
true if aP is on the circumference.

Definition at line 188 of file circle.cpp.

189{
190 int distance = ( aP - Center ).EuclideanNorm();
191
192 return distance <= ( (int64_t) Radius + SHAPE::MIN_PRECISION_IU )
193 && distance >= ( (int64_t) Radius - SHAPE::MIN_PRECISION_IU );
194}
static const int MIN_PRECISION_IU
This is the minimum precision for all the points in a shape.
Definition: shape.h:128
static float distance(const SFVEC2UI &a, const SFVEC2UI &b)

References Center, distance(), EuclideanNorm(), SHAPE::MIN_PRECISION_IU, and Radius.

Referenced by PCB_DIMENSION_BASE::segCircleIntersection().

◆ Intersect() [1/2]

std::vector< VECTOR2I > CIRCLE::Intersect ( const CIRCLE aCircle) const

Compute the intersection points between this circle and aCircle.

Parameters
aCircleThe other circle to intersect with this.
Returns
std::vector containing:
  • 0 elements if the circles do not intersect.
  • 1 element if the circles are tangent.
  • 2 elements if the circles intersect.

Definition at line 209 of file circle.cpp.

210{
211 // From https://mathworld.wolfram.com/Circle-CircleIntersection.html
212 //
213 // Simplify the problem:
214 // Let this circle be centered at (0,0), with radius r1
215 // Let aCircle be centered at (d, 0), with radius r2
216 // (i.e. d is the distance between the two circle centers)
217 //
218 // The equations of the two circles are
219 // (1) x^2 + y^2 = r1^2
220 // (2) (x - d)^2 + y^2 = r2^2
221 //
222 // Combining (1) into (2):
223 // (x - d)^2 + r1^2 - x^2 = r2^2
224 // Expanding:
225 // x^2 - 2*d*x + d^2 + r1^2 - x^2 = r2^2
226 // Rearranging for x:
227 // (3) x = (d^2 + r1^2 - r2^2) / (2 * d)
228 //
229 // Rearranging (1) gives:
230 // (4) y = sqrt(r1^2 - x^2)
231
232 std::vector<VECTOR2I> retval;
233
234 VECTOR2I vecCtoC = aCircle.Center - Center;
235 int64_t d = vecCtoC.EuclideanNorm();
236 int64_t r1 = Radius;
237 int64_t r2 = aCircle.Radius;
238
239 if( d > ( r1 + r2 ) || ( d < ( std::abs( r1 - r2 ) ) ) )
240 return retval; //circles do not intersect
241
242 if( d == 0 )
243 return retval; // circles are co-centered. Don't return intersection points
244
245 // Equation (3)
246 int64_t x = ( ( d * d ) + ( r1 * r1 ) - ( r2 * r2 ) ) / ( int64_t( 2 ) * d );
247 int64_t r1sqMinusXsq = ( r1 * r1 ) - ( x * x );
248
249 if( r1sqMinusXsq < 0 )
250 return retval; //circles do not intersect
251
252 // Equation (4)
253 int64_t y = KiROUND( sqrt( r1sqMinusXsq ) );
254
255 // Now correct back to original coordinates
256 EDA_ANGLE rotAngle( vecCtoC );
257 VECTOR2I solution1( x, y );
258 RotatePoint( solution1, -rotAngle );
259 solution1 += Center;
260 retval.push_back( solution1 );
261
262 if( y != 0 )
263 {
264 VECTOR2I solution2( x, -y );
265 RotatePoint( solution2, -rotAngle );
266 solution2 += Center;
267 retval.push_back( solution2 );
268 }
269
270 return retval;
271}
T EuclideanNorm() const
Compute the Euclidean norm of the vector, which is defined as sqrt(x ** 2 + y ** 2).
Definition: vector2d.h:293
EDA_ANGLE abs(const EDA_ANGLE &aAngle)
Definition: eda_angle.h:401
void RotatePoint(int *pX, int *pY, const EDA_ANGLE &aAngle)
Definition: trigo.cpp:183
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 std::abs(), Center, VECTOR2< T >::EuclideanNorm(), KiROUND(), Radius, and RotatePoint().

Referenced by SHAPE_ARC::Collide(), SHAPE_ARC::Intersect(), and PCB_DIMENSION_BASE::segCircleIntersection().

◆ Intersect() [2/2]

std::vector< VECTOR2I > CIRCLE::Intersect ( const SEG aSeg) const

Compute the intersection points between this circle and aSeg.

Parameters
aSegThe segment to intersect with this circle (end points ignored).
Returns
std::vector containing up to two intersection points.

Definition at line 274 of file circle.cpp.

275{
276 std::vector<VECTOR2I> retval;
277
278 for( VECTOR2I& intersection : IntersectLine( aSeg ) )
279 {
280 if( aSeg.Contains( intersection ) )
281 retval.push_back( intersection );
282 }
283
284 return retval;
285}
bool Contains(const SEG &aSeg) const
Definition: seg.h:307

References SEG::Contains(), and IntersectLine().

◆ IntersectLine()

std::vector< VECTOR2I > CIRCLE::IntersectLine ( const SEG aLine) const

Compute the intersection points between this circle and aLine.

Parameters
aLineThe line to intersect with this circle (end points ignored).
Returns
std::vector containing:
  • 0 elements if there is no intersection.
  • 1 element if the line is tangent to the circle.
  • 2 elements if the line intersects the circle.

Definition at line 288 of file circle.cpp.

289{
290 std::vector<VECTOR2I> retval;
291
292 //
293 // . * .
294 // * *
295 // -----1-------m-------2----
296 // * *
297 // * O *
298 // * *
299 // * *
300 // * *
301 // * *
302 // ' * '
303 // Let O be the center of this circle, 1 and 2 the intersection points of the line
304 // and M be the center of the chord connecting points 1 and 2
305 //
306 // M will be O projected perpendicularly to the line since a chord is always perpendicular
307 // to the radius.
308 //
309 // The distance M1 = M2 can be computed by pythagoras since O1 = O2 = Radius
310 //
311 // M1= M2 = sqrt( Radius^2 - OM^2)
312 //
313
314 VECTOR2I m = aLine.LineProject( Center ); // O projected perpendicularly to the line
315 int64_t omDist = ( m - Center ).EuclideanNorm();
316
317 if( omDist > ( (int64_t) Radius + SHAPE::MIN_PRECISION_IU ) )
318 {
319 return retval; // does not intersect
320 }
321 else if( omDist <= ( (int64_t) Radius + SHAPE::MIN_PRECISION_IU )
322 && omDist >= ( (int64_t) Radius - SHAPE::MIN_PRECISION_IU ) )
323 {
324 retval.push_back( m );
325 return retval; //tangent
326 }
327
328 int64_t radiusSquared = (int64_t) Radius * (int64_t) Radius;
329 int64_t omDistSquared = omDist * omDist;
330
331 int mTo1dist = sqrt( radiusSquared - omDistSquared );
332
333 VECTOR2I mTo1vec = ( aLine.B - aLine.A ).Resize( mTo1dist );
334 VECTOR2I mTo2vec = -mTo1vec;
335
336 retval.push_back( mTo1vec + m );
337 retval.push_back( mTo2vec + m );
338
339 return retval;
340}

References SEG::A, SEG::B, Center, EuclideanNorm(), SEG::LineProject(), SHAPE::MIN_PRECISION_IU, and Radius.

Referenced by ConstructFromTanTanPt(), Intersect(), and SHAPE_ARC::IntersectLine().

◆ NearestPoint()

VECTOR2I CIRCLE::NearestPoint ( const VECTOR2I aP) const

Compute the point on the circumference of the circle that is the closest to aP.

In other words: finds the intersection point of this circle and a line that passes through both this circle's center and aP.

Parameters
aP.
Returns
nearest point to aP.

Definition at line 197 of file circle.cpp.

198{
199 VECTOR2I vec = aP - Center;
200
201 // Handle special case where aP is equal to this circle's center
202 if( vec.x == 0 && vec.y == 0 )
203 vec.x = 1; // Arbitrary, to ensure the return value is always on the circumference
204
205 return vec.Resize( Radius ) + Center;
206}
VECTOR2< T > Resize(T aNewLength) const
Return a vector of the same direction, but length specified in aNewLength.
Definition: vector2d.h:378

References Center, Radius, VECTOR2< T >::Resize(), VECTOR2< T >::x, and VECTOR2< T >::y.

Referenced by SHAPE_ARC::Collide(), and EDIT_TOOL::DragArcTrack().

Member Data Documentation

◆ Center

◆ Radius


The documentation for this class was generated from the following files: