Return to Answer

Revert to correct and simpler code and fix comments

edited Oct 26, 2018 at 12:03

22.4k
22
86
117

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct points and that R is not 0.

Here is the algorithm

// compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the direction vector D from A to B Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB // Nowthe equation of the line equationAB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1LAB. // compute the value tdistance ofbetween the closestpoints A and E, where // E is the point toof AB closest the circle center (Cx, Cy) t = Dx*(Cx-Ax) + Dy*(Cy-Ay) // This is the projection of C on the line from A to B. // compute the coordinates of the point E on line and closest to C Ex = t*Dx+Ax Ey = t*Dy+Ay // compute the euclidean distance frombetween E toand C LEC = sqrt( (Ex-Cx)²+(Ey-Cy)² ) // test if the line intersects the circle if( LEC < R ) { // compute distance from t to circle intersection point dt = sqrt( R² - LEC²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

Here is the algorithm

// compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the direction vector D from A to B Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1. // compute the value t of the closest point to the circle center (Cx, Cy) t = Dx*(Cx-Ax) + Dy*(Cy-Ay) // This is the projection of C on the line from A to B. // compute the coordinates of the point E on line and closest to C Ex = t*Dx+Ax Ey = t*Dy+Ay // compute the euclidean distance from E to C LEC = sqrt( (Ex-Cx)²+(Ey-Cy)² ) // test if the line intersects the circle if( LEC < R ) { // compute distance from t to circle intersection point dt = sqrt( R² - LEC²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct points and that R is not 0.

Here is the algorithm

// compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the direction vector D from A to B Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB // the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB. // compute the distance between the points A and E, where // E is the point of AB closest the circle center (Cx, Cy) t = Dx*(Cx-Ax) + Dy*(Cy-Ay) // compute the coordinates of the point E Ex = t*Dx+Ax Ey = t*Dy+Ay // compute the euclidean distance between E and C LEC = sqrt((Ex-Cx)²+(Ey-Cy)²) // test if the line intersects the circle if( LEC < R ) { // compute distance from t to circle intersection point dt = sqrt( R² - LEC²) // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

Rollback to Revision 3

Source Link

edited Oct 26, 2018 at 11:54

chmike

22.4k
22
86
117

EDIT: There was an error in the code that I corrected.

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct and that R is not 0.

// compute the parameterseuclidean fordistance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the parametricdirection equationvector ofD linefrom segmentA ABto B ABxDx = (Bx-Ax)/LAB AByDy = (By-Ay)/LAB  // Now the line isequation thenis x = ABx*tDx*t + Ax, y = ABy*tDy*t + Ay with 0 <= t <= 1. // compute the euclidean distance between A andvalue B LABt =of sqrt(ABx²the +closest ABy²) //point computeto the euclidean distance betweencircle Acenter and(Cx, CCy) ACxt = Dx*(Cx-Ax ACy) =+ Dy*(Cy-Ay LAC) = sqrt(ACx² + ACy²) // compute the cosineThis ofis the angle between ABprojection andof ACC usingon the scalar product tline =from (ABx*ACxA +to ABy*ACy)/(LAC*LAB)B. // compute the coordinates of the point E on the line ABand closest to C Ex = ABx*t + Axt*Dx+Ax Ey = ABy*t + Ayt*Dy+Ay // compute the euclidean distance betweenfrom CE andto EC LLEC = sqrt( (Ex-Cx)² + ²+(Ey-Cy)²) if L > R) {  // no intersection points } elsetest if L == R { // the circle touches the line at exactly one point which is E } else { //intersects the circle crosses the line in if( twoLEC points< F andR G) { // compute the distance offrom t to circle intersection pointspoint dt = sqrt( R² - L²LEC²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

EDIT: There was an error in the code that I corrected.

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct and that R is not 0.

// compute the parameters for the parametric equation of line segment AB ABx = Bx-Ax ABy = By-Ay // the line is then x = ABx*t + Ax, y = ABy*t + Ay with 0 <= t <= 1 // compute the euclidean distance between A and B LAB = sqrt(ABx² + ABy²) // compute the euclidean distance between A and C ACx = Cx-Ax ACy = Cy-Ay LAC = sqrt(ACx² + ACy²) // compute the cosine of the angle between AB and AC using the scalar product t = (ABx*ACx + ABy*ACy)/(LAC*LAB) // compute the coordinates of the point E on the line AB closest to C Ex = ABx*t + Ax Ey = ABy*t + Ay // compute the distance between C and E L = sqrt((Ex-Cx)² + (Ey-Cy)²) if L > R {  // no intersection points } else if L == R { // the circle touches the line at exactly one point which is E } else { // the circle crosses the line in two points F and G // compute the distance of intersection points dt = sqrt(R² - L²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay }

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

// compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the direction vector D from A to B Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB  // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1. // compute the value t of the closest point to the circle center (Cx, Cy) t = Dx*(Cx-Ax) + Dy*(Cy-Ay) // This is the projection of C on the line from A to B. // compute the coordinates of the point E on line and closest to C Ex = t*Dx+Ax Ey = t*Dy+Ay // compute the euclidean distance from E to C LEC = sqrt( (Ex-Cx)²+(Ey-Cy)² ) // test if the line intersects the circle if( LEC < R ) { // compute distance from t to circle intersection point dt = sqrt( R² - LEC²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

Fix error in computation of t

Source Link

edited Oct 26, 2018 at 11:27

chmike

22.4k
22
86
117

EDIT: There was an error in the code that I corrected.

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct and that R is not 0.

// compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) //parameters computefor the direction vectorparametric Dequation fromof Aline tosegment BAB DxABx = (Bx-Ax)/LAB DyABy = (By-Ay)/LAB  // Now the line equation is then x = Dx*tABx*t + Ax, y = Dy*tABy*t + Ay with 0 <= t <= 1. // compute the valueeuclidean tdistance ofbetween theA closestand pointB LAB to= sqrt(ABx² + ABy²) // compute the circleeuclidean centerdistance (Cx,between Cy)A and C tACx = Dx*(Cx-Ax) ACy += Dy*(Cy-Ay) LAC = sqrt(ACx² + ACy²) // This iscompute the projectioncosine of Cthe onangle between AB and AC using the linescalar fromproduct t A= to(ABx*ACx B.+ ABy*ACy)/(LAC*LAB) // compute the coordinates of the point E on the line andAB closest to C Ex = t*Dx+AxABx*t + Ax Ey = t*Dy+AyABy*t + Ay // compute the euclidean distance frombetween EC toand CE LECL = sqrt( (Ex-Cx)²+² + (Ey-Cy)² ) if L > R {  // testno intersection points } else if theL line== intersectsR { // the circle if( LECtouches <the Rline )at exactly one point which is E  } else { // computethe distancecircle fromcrosses tthe toline circlein two points F and G  // compute the distance of intersection pointpoints dt = sqrt( R² - LEC²L²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

// compute the euclidean distance between A and B LAB = sqrt( (Bx-Ax)²+(By-Ay)² ) // compute the direction vector D from A to B Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB  // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1. // compute the value t of the closest point to the circle center (Cx, Cy) t = Dx*(Cx-Ax) + Dy*(Cy-Ay) // This is the projection of C on the line from A to B. // compute the coordinates of the point E on line and closest to C Ex = t*Dx+Ax Ey = t*Dy+Ay // compute the euclidean distance from E to C LEC = sqrt( (Ex-Cx)²+(Ey-Cy)² ) // test if the line intersects the circle if( LEC < R ) { // compute distance from t to circle intersection point dt = sqrt( R² - LEC²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay } // else test if the line is tangent to circle else if( LEC == R ) // tangent point to circle is E else // line doesn't touch circle

EDIT: There was an error in the code that I corrected.

I would use the algorithm to compute the distance between a point (circle center) and a line (line AB). This can then be used to determine the intersection points of the line with the circle.

Let say we have the points A, B, C. Ax and Ay are the x and y components of the A points. Same for B and C. The scalar R is the circle radius.

This algorithm requires that A, B and C are distinct and that R is not 0.

// compute the parameters for the parametric equation of line segment AB ABx = Bx-Ax ABy = By-Ay // the line is then x = ABx*t + Ax, y = ABy*t + Ay with 0 <= t <= 1 // compute the euclidean distance between A and B LAB = sqrt(ABx² + ABy²) // compute the euclidean distance between A and C ACx = Cx-Ax ACy = Cy-Ay LAC = sqrt(ACx² + ACy²) // compute the cosine of the angle between AB and AC using the scalar product t = (ABx*ACx + ABy*ACy)/(LAC*LAB) // compute the coordinates of the point E on the line AB closest to C Ex = ABx*t + Ax Ey = ABy*t + Ay // compute the distance between C and E L = sqrt((Ex-Cx)² + (Ey-Cy)²) if L > R {  // no intersection points } else if L == R { // the circle touches the line at exactly one point which is E  } else { // the circle crosses the line in two points F and G  // compute the distance of intersection points dt = sqrt(R² - L²)/LAB // compute first intersection point Fx = (t-dt)*Dx + Ax Fy = (t-dt)*Dy + Ay // compute second intersection point Gx = (t+dt)*Dx + Ax Gy = (t+dt)*Dy + Ay }