Algorithme de détection de collision de segments de lignes en cercle?

J’ai une ligne de A à B et un cercle positionné à C avec le rayon R.

Image

Quel est le bon algorithme à utiliser pour vérifier si la ligne coupe le cercle? Et à quelle coordonnée le long du bord des cercles il s’est produit?

Prise

  1. E est le sharepoint départ du rayon,
  2. L est le point final du rayon,
  3. C est le centre de la sphère contre laquelle vous testez
  4. r est le rayon de cette sphère

Calculer:
d = L – E (Vecteur de direction de rayon, du début à la fin)
f = E – C (Vecteur de la sphère centrale au début du rayon)

Ensuite, l’intersection est trouvée par ..
Bouchage:
P = E + t * d
Ceci est une équation paramésortingque:
P x = E x + td x
P y = E y + td y
dans
(x – h) 2 + (y – k) 2 = r 2
(h, k) = centre du cercle.

Remarque: Nous avons simplifié le problème en 2D ici, la solution que nous obtenons s’applique également en 3D

obtenir:

  1. Développer
    x 2 – 2xh + h 2 + y 2 – 2yk + k 2 – r 2 = 0
  2. Prise de courant
    x = e x + td x
    y = e y + td y
    (e x + td x ) 2 – 2 (e x + td x ) h + h 2 + (ey + td y ) 2 – 2 (e + td y ) k + k 2 – r 2 = 0
  3. Exploser
    e x 2 + 2e x td x + t 2 d x 2 – 2e x h – 2td x h + h 2 + e y 2 + 2e y td y + t 2 d y 2 – 2e y k – 2td y k + k 2 – r 2 = 0
  4. Groupe
    t 2 (d x 2 + d y 2 ) + 2 t (e x d x + e y d y – d x h – d y k) + e x 2 + e y 2 – 2e x h – 2e y k + h 2 + k 2 – r 2 = 0
  5. Finalement,
    t 2 (_d * _d) + 2t (_e * _d – _d * _c) + _e * _e – 2 (_e * _c) + _c * _c – r 2 = 0
    * Où _d est le vecteur d et * est le produit scalaire. *
  6. Et alors,
    t 2 (_d * _d) + 2t (_d * (_e – _c)) + (_e – _c) * (_e – _c) – r 2 = 0
  7. Laisser _f = _e – _c
    t 2 (_d * _d) + 2t (_d * _f) + _f * _f – r 2 = 0

Nous obtenons donc:
t 2 * (d DOT d) + 2t * (f DOT d) + (f DOT f – r 2 ) = 0
Donc, en résolvant l’équation quadratique:

float a = d.Dot( d ) ; float b = 2*f.Dot( d ) ; float c = f.Dot( f ) - r*r ; float discriminant = b*b-4*a*c; if( discriminant < 0 ) { // no intersection } else { // ray didn't totally miss sphere, // so there is a solution to // the equation. discriminant = sqrt( discriminant ); // either solution may be on or off the ray so need to test both // t1 is always the smaller value, because BOTH discriminant and // a are nonnegative. float t1 = (-b - discriminant)/(2*a); float t2 = (-b + discriminant)/(2*a); // 3x HIT cases: // -o-> --|--> | | --|-> // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), // 3x MISS cases: // -> oo -> | -> | // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1) if( t1 >= 0 && t1 <= 1 ) { // t1 is the intersection, and it's closer than t2 // (since t1 uses -b - discriminant) // Impale, Poke return true ; } // here t1 didn't intersect so we are either started // inside the sphere or completely past it if( t2 >= 0 && t2 <= 1 ) { // ExitWound return true ; } // no intn: FallShort, Past, CompletelyInside return false ; } 

Personne ne semble envisager la projection, suis-je complètement hors de propos ici?

Projetez le vecteur AC sur AB . Le vecteur projeté, AD , donne le nouveau point D
Si la distance entre D et C est inférieure à (ou égale à) R nous avons une intersection.

Comme ça:
Image par SchoolBoy

J’utiliserais l’algorithme pour calculer la distance entre un point (centre du cercle) et une ligne (ligne AB). Cela peut ensuite être utilisé pour déterminer les points d’intersection de la ligne avec le cercle.

Disons que nous avons les points A, B, C. Ax et Ay sont les composantes x et y des points A. Idem pour B et C. Le scalaire R est le rayon du cercle.

Voici l’algorithme

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

Ok, je ne vous donnerai pas de code, mais comme vous avez tagué cet algorithme , je ne pense pas que cela vous importera. Tout d’abord, vous devez obtenir un vecteur perpendiculaire à la ligne.

Vous aurez une variable inconnue dans y = ax + c ( c sera inconnu )
Pour résoudre cela, calculez sa valeur lorsque la ligne passe par le centre du cercle.

C’est,
Branchez l’emplacement du centre du cercle sur l’équation de la ligne et résolvez pour c .
Calculez ensuite le point d’intersection de la ligne d’origine et sa normale.

Cela vous donnera le point le plus proche de la ligne du cercle.
Calculez la distance entre ce point et le centre du cercle (en utilisant la magnitude du vecteur).
Si c’est moins que le rayon du cercle – voilà, nous avons une intersection!

Une autre méthode utilise la formule sortingangular ABC. Le test d’intersection est plus simple et plus efficace que la méthode de projection, mais la recherche des coordonnées du point d’intersection nécessite plus de travail. Au moins, il sera retardé au point où il est requirejs.

La formule pour calculer la zone du sortingangle est la suivante: area = bh / 2

où b est la longueur de base et h la hauteur. Nous avons choisi le segment AB comme base de sorte que h soit la distance la plus courte entre C, le centre du cercle et la ligne.

Comme la zone du sortingangle peut aussi être calculée par un produit vectoriel, nous pouvons déterminer h.

 // compute the sortingangle area times 2 (area = area2/2) area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) ) // compute the AB segment length LAB = sqrt( (Bx-Ax)² + (By-Ay)² ) // compute the sortingangle height h = area2/LAB // if the line intersects the circle if( h < R ) { ... } 

MISE À JOUR 1:

Vous pouvez optimiser le code en utilisant le calcul rapide de la racine carrée inverse décrit ici pour obtenir une bonne approximation de 1 / LAB.

Calculer le point d'intersection n'est pas si difficile. Ça y va

 // compute the line AB direction vector components Dx = (Bx-Ax)/LAB Dy = (By-Ay)/LAB // compute the distance from A toward B of closest point to C t = Dx*(Cx-Ax) + Dy*(Cy-Ay) // t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² ) // compute the intersection point distance from t dt = sqrt( R² - h² ) // compute first intersection point coordinate Ex = Ax + (t-dt)*Dx Ey = Ay + (t-dt)*Dy // compute second intersection point coordinate Fx = Ax + (t+dt)*Dx Fy = Ay + (t+dt)*Dy 

Si h = R alors la ligne AB est tangente au cercle et la valeur dt = 0 et E = F. Les coordonnées des points sont celles de E et F.

Vous devriez vérifier que A est différent de B et que la longueur du segment n'est pas nulle si cela peut se produire dans votre application.

J’ai écrit un petit script pour tester l’intersection en projetant le centre du cercle sur une ligne.

 vector distVector = centerPoint - projectedPoint; if(distVector.length() < circle.radius) { double distance = circle.radius - distVector.length(); vector moveVector = distVector.normalize() * distance; circle.move(moveVector); } 

http://jsfiddle.net/ercang/ornh3594/1/

Si vous devez vérifier la collision avec le segment, vous devez également tenir compte de la distance du centre du cercle aux points de départ et d'arrivée.

 vector distVector = centerPoint - startPoint; if(distVector.length() < circle.radius) { double distance = circle.radius - distVector.length(); vector moveVector = distVector.normalize() * distance; circle.move(moveVector); } 

https://jsfiddle.net/ercang/menp0991/

Cette solution m’a semblé un peu plus facile à suivre que d’autres.

Prise:

 p1 and p2 as the points for the line, and c as the center point for the circle and r for the radius 

Je voudrais résoudre l’équation de la ligne en forme de pente-interception. Cependant, je ne voulais pas avoir à gérer des équations difficiles avec c comme point, donc j’ai simplement déplacé le système de coordonnées pour que le cercle soit à 0,0

 p3 = p1 - c p4 = p2 - c 

Au fait, chaque fois que je soustrais des points les uns des autres, je soustrais les x , puis soustrais les y et les place dans un nouveau point, au cas où quelqu’un ne le sache pas.

Quoi qu’il en soit, je résous maintenant l’équation de la ligne avec p3 et p4 :

 m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript) y = mx + b y - mx = b (just put in a point for x and y, and insert the m we found) 

D’accord. Maintenant, je dois définir ces équations égales. Je dois d’abord résoudre l’équation du cercle pour x

 x^2 + y^2 = r^2 y^2 = r^2 - x^2 y = sqrt(r^2 - x^2) 

Alors je les mets à égalité:

 mx + b = sqrt(r^2 - x^2) 

Et résoudre l’équation quadratique ( 0 = ax^2 + bx + c ):

 (mx + b)^2 = r^2 - x^2 (mx)^2 + 2mbx + b^2 = r^2 - x^2 0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2 0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2 

Maintenant, j’ai mes a , b et c .

 a = m^2 + 1 b = 2mb c = b^2 - r^2 

Donc je mets ça dans la formule quadratique:

 (-b ± sqrt(b^2 - 4ac)) / 2a 

Et substituer par des valeurs puis simplifier autant que possible:

 (-2mb ± sqrt(b^2 - 4ac)) / 2a (-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1) (-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2 (-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2 (-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2 (-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2 (-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2 (-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2 (-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2 (-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 

C’est presque aussi loin que cela simplifiera. Enfin, séparez les équations avec ±:

 (-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or (-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 

Ensuite, twigz simplement le résultat de ces deux équations dans le x dans mx + b . Pour plus de clarté, j’ai écrit du code JavaScript pour montrer comment utiliser ceci:

 function interceptOnCircle(p1,p2,c,r){ //p1 is the first line point //p2 is the second line point //c is the circle's center //r is the circle's radius var p3 = {x:p1.x - cx, y:p1.y - cy} //shifted line points var p4 = {x:p2.x - cx, y:p2.y - cy} var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line var b = p3.y - m * p3.x; //y-intercept of line var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign if (underRadical < 0){ //line completely missed return false; } else { var t1 = (-2*m*b+2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //one of the intercept x's var t2 = (-2*m*b-2*Math.sqrt(underRadical))/(2 * Math.pow(m,2) + 2); //other intercept's x var i1 = {x:t1,y:m*t1+b} //intercept point 1 var i2 = {x:t2,y:m*t2+b} //intercept point 2 return [i1,i2]; } } 

J'espère que ça aide!

PS Si quelqu'un trouve des erreurs ou a des suggestions, s'il vous plaît commenter. Je suis très nouveau et bienvenue à toute aide / suggestion.

Vous pouvez trouver un point sur une ligne infinie le plus proche du centre du cercle en projetant le vecteur AC sur le vecteur AB. Calculez la distance entre ce point et le centre du cercle. S’il est plus grand que R, il n’y a pas d’intersection. Si la distance est égale à R, la ligne est une tangente du cercle et le point le plus proche du centre du cercle est en fait le point d’intersection. Si la distance est inférieure à R, alors il y a 2 points d’intersection. Ils se trouvent à la même distance du point le plus proche du centre du cercle. Cette distance peut facilement être calculée en utilisant le théorème de Pythagore. Voici l’algorithme en pseudocode:

 { dX = bX - aX; dY = bY - aY; if ((dX == 0) && (dY == 0)) { // A and B are the same points, no way to calculate intersection return; } dl = (dX * dX + dY * dY); t = ((cX - aX) * dX + (cY - aY) * dY) / dl; // point on a line nearest to circle center nearestX = aX + t * dX; nearestY = aY + t * dY; dist = point_dist(nearestX, nearestY, cX, cY); if (dist == R) { // line segment touches circle; one intersection point iX = nearestX; iY = nearestY; if (t < 0 || t > 1) { // intersection point is not actually within line segment } } else if (dist < R) { // two possible intersection points dt = sqrt(R * R - dist * dist) / sqrt(dl); // intersection point nearest to A t1 = t - dt; i1X = aX + t1 * dX; i1Y = aY + t1 * dY; if (t1 < 0 || t1 > 1) { // intersection point is not actually within line segment } // intersection point farthest from A t2 = t + dt; i2X = aX + t2 * dX; i2Y = aY + t2 * dY; if (t2 < 0 || t2 > 1) { // intersection point is not actually within line segment } } else { // no intersection } } 

EDIT: ajout de code pour vérifier si les points d’intersection trouvés se trouvent réellement dans le segment de ligne.

Bizarrement, je peux répondre mais pas commenter… J’ai aimé l’approche de Multitaskpro qui consistait à tout déplacer pour que le centre du cercle tombe sur l’origine. Malheureusement, il y a deux problèmes dans son code. D’abord dans la partie sous la racine carrée, vous devez supprimer le double pouvoir. Donc pas:

var underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));

mais:

var underRadical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);

Dans les coordonnées finales, il oublie de déplacer la solution. Donc pas:

var i1 = {x:t1,y:m*t1+b}

mais:

var i1 = {x:t1+cx, y:m*t1+b+cy};

La fonction entière devient alors:

 function interceptOnCircle(p1, p2, c, r) { //p1 is the first line point //p2 is the second line point //c is the circle's center //r is the circle's radius var p3 = {x:p1.x - cx, y:p1.y - cy}; //shifted line points var p4 = {x:p2.x - cx, y:p2.y - cy}; var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line var b = p3.y - m * p3.x; //y-intercept of line var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign if (underRadical < 0) { //line completely missed return false; } else { var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x var i1 = {x:t1+cx, y:m*t1+b+cy}; //intercept point 1 var i2 = {x:t2+cx, y:m*t2+b+cy}; //intercept point 2 return [i1, i2]; } } 

Vous aurez besoin de quelques maths ici:

Supposons que A = (Xa, Ya), B = (Xb, Yb) et C = (Xc, Yc). Tout point sur la ligne de A à B a des coordonnées (alpha * Xa + (1-alpha) Xb, alpha Ya + (1-alpha) * Yb) = P

Si le point P a la distance R à C, il doit être sur le cercle. Ce que tu veux c’est résoudre

 distance(P, C) = R 

C’est

 (alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2 alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2 (Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0 

Si vous appliquez la formule ABC à cette équation pour la résoudre en alpha et calculez les coordonnées de P en utilisant la ou les solutions pour alpha, vous obtenez les éventuels points d’intersection.

Si vous trouvez la distance entre le centre de la sphère (puisque c’est 3D, je suppose que vous voulez dire sphère et non cercle) et la ligne, vérifiez si cette distance est inférieure au rayon qui fera l’affaire.

Le sharepoint collision est évidemment le point le plus proche entre la ligne et la sphère (qui sera calculé lorsque vous calculerez la distance entre la sphère et la ligne)

Distance entre un point et une ligne:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Voici une implémentation en Javascript. Mon approche consiste d’abord à convertir le segment de droite en une ligne infinie, puis à trouver le ou les points d’intersection. De là, je vérifie si le ou les points trouvés se trouvent sur le segment de ligne. Le code est bien documenté, vous devriez pouvoir suivre.

Vous pouvez essayer le code ici sur cette démonstration en direct . Le code a été extrait de mon repo d’algorithmes .

entrer la description de l'image ici

 // Small epsilon value var EPS = 0.0000001; // point (x, y) function Point(x, y) { this.x = x; this.y = y; } // Circle with center at (x,y) and radius r function Circle(x, y, r) { this.x = x; this.y = y; this.r = r; } // A line segment (x1, y1), (x2, y2) function LineSegment(x1, y1, x2, y2) { var d = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ); if (d < EPS) throw 'A point is not a line segment'; this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } // An infinite line defined as: ax + by = c function Line(a, b, c) { this.a = a; this.b = b; this.c = c; // Normalize line for good measure if (Math.abs(b) < EPS) { c /= a; a = 1; b = 0; } else { a = (Math.abs(a) < EPS) ? 0 : a / b; c /= b; b = 1; } } // Given a line in standard form: ax + by = c and a circle with // a center at (x,y) with radius r this method finds the intersection // of the line and the circle (if any). function circleLineIntersection(circle, line) { var a = line.a, b = line.b, c = line.c; var x = circle.x, y = circle.y, r = circle.r; // Solve for the variable x with the formulas: ax + by = c (equation of line) // and (xX)^2 + (yY)^2 = r^2 (equation of circle where X,Y are known) and expand to obtain quadratic: // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0 // Then use quadratic formula X = (-b +- sqrt(a^2 - 4ac))/2a to find the // roots of the equation (if they exist) and this will tell us the intersection points // In general a quadratic is written as: Ax^2 + Bx + C = 0 // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0 var A = a*a + b*b; var B = 2*a*b*y - 2*a*c - 2*b*b*x; var C = b*b*x*x + b*b*y*y - 2*b*c*y + c*c - b*b*r*r; // Use quadratic formula x = (-b +- sqrt(a^2 - 4ac))/2a to find the // roots of the equation (if they exist). var D = B*B - 4*A*C; var x1,y1,x2,y2; // Handle vertical line case with b = 0 if (Math.abs(b) < EPS) { // Line equation is ax + by = c, but b = 0, so x = c/a x1 = c/a; // No intersection if (Math.abs(x-x1) > r) return []; // Vertical line is tangent to circle if (Math.abs((x1-r)-x) < EPS || Math.abs((x1+r)-x) < EPS) return [new Point(x1, y)]; var dx = Math.abs(x1 - x); var dy = Math.sqrt(r*r-dx*dx); // Vertical line cuts through circle return [ new Point(x1,y+dy), new Point(x1,y-dy) ]; // Line is tangent to circle } else if (Math.abs(D) < EPS) { x1 = -B/(2*A); y1 = (c - a*x1)/b; return [new Point(x1,y1)]; // No intersection } else if (D < 0) { return []; } else { D = Math.sqrt(D); x1 = (-B+D)/(2*A); y1 = (c - a*x1)/b; x2 = (-BD)/(2*A); y2 = (c - a*x2)/b; return [ new Point(x1, y1), new Point(x2, y2) ]; } } // Converts a line segment to a line in general form function segmentToGeneralForm(x1,y1,x2,y2) { var a = y1 - y2; var b = x2 - x1; var c = x2*y1 - x1*y2; return new Line(a,b,c); } // Checks if a point 'pt' is inside the rect defined by (x1,y1), (x2,y2) function pointInRectangle(pt,x1,y1,x2,y2) { var x = Math.min(x1,x2), X = Math.max(x1,x2); var y = Math.min(y1,y2), Y = Math.max(y1,y2); return x - EPS <= pt.x && pt.x <= X + EPS && y - EPS <= pt.y && pt.y <= Y + EPS; } // Finds the intersection(s) of a line segment and a circle function lineSegmentCircleIntersection(segment, circle) { var x1 = segment.x1, y1 = segment.y1, x2 = segment.x2, y2 = segment.y2; var line = segmentToGeneralForm(x1,y1,x2,y2); var pts = circleLineIntersection(circle, line); // No intersection if (pts.length === 0) return []; var pt1 = pts[0]; var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2); // Check for unique intersection if (pts.length === 1) { if (includePt1) return [pt1]; return []; } var pt2 = pts[1]; var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2); // Check for remaining intersections if (includePt1 && includePt2) return [pt1, pt2]; if (includePt1) return [pt1]; if (includePt2) return [pt2]; return []; } 

Dans cette post-cercle, la collision de lignes sera vérifiée en vérifiant la distance entre le centre du cercle et le point sur le segment de ligne (Ipoint) qui représente le point d’intersection entre N normal (Image 2) du centre du cercle au segment de ligne.

( https://i.stack.imgur.com/3o6do.png ) Image 1. Recherche des vecteurs E et D

Sur l’image 1, un cercle et une ligne sont affichés, vector Un sharepoint départ point à ligne, le vecteur B pointe vers le point final de la ligne, le vecteur C pointe vers le centre du cercle. Maintenant, nous devons trouver le vecteur E (du sharepoint départ de la ligne au centre du cercle) et le vecteur D (du sharepoint départ de la ligne au sharepoint fin de la ligne), ce calcul est montré sur l’image 1.

( https://i.stack.imgur.com/7098a.png ) Image 2. Trouver le vecteur X

À l’image 2, on peut voir que le vecteur E est projeté sur le vecteur D par “produit scalaire” du vecteur E et du vecteur unitaire D, le résultat du produit scalaire est le scalaire Xp qui représente la distance entre le sharepoint départ et le point d’intersection vecteur N et vecteur D. Le vecteur suivant X est trouvé en multipliant le vecteur unitaire D et le scalaire Xp.

Il nous faut maintenant trouver le vecteur Z (vecteur à Ipoint), sa simple addition vectorielle simple du vecteur A (sharepoint départ sur la ligne) et du vecteur X. Ensuite, nous devons traiter des cas particuliers que nous devons vérifier si Ipoint est un segment de ligne Nous ne devons pas savoir s’il en rest ou à droite, nous utiliserons le vecteur le plus proche pour déterminer quel point est le plus proche du cercle.

( https://i.stack.imgur.com/p9WIr.png ) Image 3. Trouver le point le plus proche

Lorsque la projection Xp est négative Ipoint est à gauche du segment de ligne, le vecteur le plus proche est le vecteur du sharepoint départ de la ligne, lorsque la projection Xp est supérieure au vecteur D alors Ipoint est à droite du segment de droite point dans tout autre cas, le vecteur le plus proche est égal au vecteur Z.

Maintenant, quand nous avons le vecteur le plus proche, nous devons trouver le vecteur du centre du cercle à Ipoint (vecteur distal), il suffit simplement de soustraire le vecteur le plus proche du vecteur central. Ensuite, vérifiez si la magnitude vectorielle est inférieure à celle du cercle si c’est le cas, alors ils entrent en collision, s’il n’y a pas de collision.

( https://i.stack.imgur.com/QJ63q.png ) Image 4. Vérification de la collision

Pour finir, on peut retourner quelques valeurs pour résoudre la collision, le plus simple est de retourner le chevauchement (soustraire le rayon de la magnitude vectorielle) et de retourner l’axe de collision, son vecteur D. Le point d’intersection est également le vecteur Z si nécessaire.

Si les coordonnées de la ligne sont Ax, Ay et Bx, By et le centre des cercles sont Cx, Cy alors les formules des lignes sont:

x = Axe * t + Bx * (1 – t)

y = Ay * t + par * (1 – t)

où 0 <= t <= 1

et le cercle est

(Cx – x) ^ 2 + (Cy-y) ^ 2 = R ^ 2

Si vous substituez des formules x et y de la ligne dans la formule de cercles, vous obtenez une équation de second ordre de t et ses solutions sont les points d’intersection (s’il y en a). Si vous obtenez à ce qui est inférieur à 0 ou supérieur à 1, ce n’est pas une solution, mais cela montre que la ligne pointe vers la direction du cercle.

Juste un ajout à ce fil… Voici une version du code publiée par pahlevan, mais pour C # / XNA et rangée un peu:

  ///  /// Intersects a line and a circle. ///  /// the location of the circle /// the radius of the circle /// the starting point of the line /// the ending point of the line /// true if the line and circle intersect each other public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo) { float ab2, acab, h2; Vector2 ac = location - lineFrom; Vector2 ab = lineTo - lineFrom; Vector2.Dot(ref ab, ref ab, out ab2); Vector2.Dot(ref ac, ref ab, out acab); float t = acab / ab2; if (t < 0) t = 0; else if (t > 1) t = 1; Vector2 h = ((ab * t) + lineFrom) - location; Vector2.Dot(ref h, ref h, out h2); return (h2 <= (radius * radius)); } 

entrer la description de l'image ici

 ' VB.NET - Code Function CheckLineSegmentCircleIntersection(x1 As Double, y1 As Double, x2 As Double, y2 As Double, xc As Double, yc As Double, r As Double) As Boolean Static xd As Double = 0.0F Static yd As Double = 0.0F Static t As Double = 0.0F Static d As Double = 0.0F Static dx_2_1 As Double = 0.0F Static dy_2_1 As Double = 0.0F dx_2_1 = x2 - x1 dy_2_1 = y2 - y1 t = ((yc - y1) * dy_2_1 + (xc - x1) * dx_2_1) / (dy_2_1 * dy_2_1 + dx_2_1 * dx_2_1) If 0 <= t And t <= 1 Then xd = x1 + t * dx_2_1 yd = y1 + t * dy_2_1 d = Math.Sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc)) Return d <= r Else d = Math.Sqrt((xc - x1) * (xc - x1) + (yc - y1) * (yc - y1)) If d <= r Then Return True Else d = Math.Sqrt((xc - x2) * (xc - x2) + (yc - y2) * (yc - y2)) If d <= r Then Return True Else Return False End If End If End If End Function 

J’ai créé cette fonction pour iOS à la suite de la réponse donnée par chmike

 + (NSArray *)intersectionPointsOfCircleWithCenter:(CGPoint)center withRadius:(float)radius toLinePoint1:(CGPoint)p1 andLinePoint2:(CGPoint)p2 { NSMutableArray *intersectionPoints = [NSMutableArray array]; float Ax = p1.x; float Ay = p1.y; float Bx = p2.x; float By = p2.y; float Cx = center.x; float Cy = center.y; float R = radius; // compute the euclidean distance between A and B float LAB = sqrt( pow(Bx-Ax, 2)+pow(By-Ay, 2) ); // compute the direction vector D from A to B float Dx = (Bx-Ax)/LAB; float 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) float 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 float Ex = t*Dx+Ax; float Ey = t*Dy+Ay; // compute the euclidean distance from E to C float LEC = sqrt( pow(Ex-Cx, 2)+ pow(Ey-Cy, 2) ); // test if the line intersects the circle if( LEC < R ) { // compute distance from t to circle intersection point float dt = sqrt( pow(R, 2) - pow(LEC,2) ); // compute first intersection point float Fx = (t-dt)*Dx + Ax; float Fy = (t-dt)*Dy + Ay; // compute second intersection point float Gx = (t+dt)*Dx + Ax; float Gy = (t+dt)*Dy + Ay; [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Fx, Fy)]]; [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Gx, Gy)]]; } // else test if the line is tangent to circle else if( LEC == R ) { // tangent point to circle is E [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Ex, Ey)]]; } else { // line doesn't touch circle } return intersectionPoints; } 

This Java Function returns a DVec2 Object. It takes a DVec2 for the center of the circle, the radius of the circle, and a Line.

 public static DVec2 CircLine(DVec2 C, double r, Line line) { DVec2 A = line.p1; DVec2 B = line.p2; DVec2 P; DVec2 AC = new DVec2( C ); AC.sub(A); DVec2 AB = new DVec2( B ); AB.sub(A); double ab2 = AB.dot(AB); double acab = AC.dot(AB); double t = acab / ab2; if (t < 0.0) t = 0.0; else if (t > 1.0) t = 1.0; //P = A + t * AB; P = new DVec2( AB ); P.mul( t ); P.add( A ); DVec2 H = new DVec2( P ); H.sub( C ); double h2 = H.dot(H); double r2 = r * r; if(h2 > r2) return null; else return P; } 

Another one in c# (partial Circle class). Tested and works like a charm.

 public class Circle : IEquatable { // ****************************************************************** // The center of a circle private Point _center; // The radius of a circle private double _radius; // ****************************************************************** ///  /// Find all intersections (0, 1, 2) of the circle with a line defined by its 2 points. /// Using: http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle /// Note: p is the Center.X and q is Center.Y ///  ///  ///  ///  public List GetIntersections(Point linePoint1, Point linePoint2) { List intersections = new List(); double dx = linePoint2.X - linePoint1.X; if (dx.AboutEquals(0)) // Straight vertical line { if (linePoint1.X.AboutEquals(Center.X - Radius) || linePoint1.X.AboutEquals(Center.X + Radius)) { Point pt = new Point(linePoint1.X, Center.Y); intersections.Add(pt); } else if (linePoint1.X > Center.X - Radius && linePoint1.X < Center.X + Radius) { double x = linePoint1.X - Center.X; Point pt = new Point(linePoint1.X, Center.Y + Math.Sqrt(Radius * Radius - (x * x))); intersections.Add(pt); pt = new Point(linePoint1.X, Center.Y - Math.Sqrt(Radius * Radius - (x * x))); intersections.Add(pt); } return intersections; } // Line function (y = mx + b) double dy = linePoint2.Y - linePoint1.Y; double m = dy / dx; double b = linePoint1.Y - m * linePoint1.X; double A = m * m + 1; double B = 2 * (m * b - m * _center.Y - Center.X); double C = Center.X * Center.X + Center.Y * Center.Y - Radius * Radius - 2 * b * Center.Y + b * b; double discriminant = B * B - 4 * A * C; if (discriminant < 0) { return intersections; // there is no intersections } if (discriminant.AboutEquals(0)) // Tangeante (touch on 1 point only) { double x = -B / (2 * A); double y = m * x + b; intersections.Add(new Point(x, y)); } else // Secant (touch on 2 points) { double x = (-B + Math.Sqrt(discriminant)) / (2 * A); double y = m * x + b; intersections.Add(new Point(x, y)); x = (-B - Math.Sqrt(discriminant)) / (2 * A); y = m * x + b; intersections.Add(new Point(x, y)); } return intersections; } // ****************************************************************** // Get the center [XmlElement("Center")] public Point Center { get { return _center; } set { _center = value; } } // ****************************************************************** // Get the radius [XmlElement] public double Radius { get { return _radius; } set { _radius = value; } } //// ****************************************************************** //[XmlArrayItemAttribute("DoublePoint")] //public List Coordinates //{ // get { return _coordinates; } //} // ****************************************************************** // Construct a circle without any specification public Circle() { _center.X = 0; _center.Y = 0; _radius = 0; } // ****************************************************************** // Construct a circle without any specification public Circle(double radius) { _center.X = 0; _center.Y = 0; _radius = radius; } // ****************************************************************** // Construct a circle with the specified circle public Circle(Circle circle) { _center = circle._center; _radius = circle._radius; } // ****************************************************************** // Construct a circle with the specified center and radius public Circle(Point center, double radius) { _center = center; _radius = radius; } // ****************************************************************** // Construct a circle based on one point public Circle(Point center) { _center = center; _radius = 0; } // ****************************************************************** // Construct a circle based on two points public Circle(Point p1, Point p2) { Circle2Points(p1, p2); } 

Required:

 using System; namespace Mathematic { public static class DoubleExtension { // ****************************************************************** // Base on Hans Passant Answer on: // http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre ///  /// Compare two double taking in account the double precision potential error. /// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon. public static bool AboutEquals(this double value1, double value2) { if (double.IsPositiveInfinity(value1)) return double.IsPositiveInfinity(value2); if (double.IsNegativeInfinity(value1)) return double.IsNegativeInfinity(value2); if (double.IsNaN(value1)) return double.IsNaN(value2); double epsilon = Math.Max(Math.Abs(value1), Math.Abs(value2)) * 1E-15; return Math.Abs(value1 - value2) <= epsilon; } // ****************************************************************** // Base on Hans Passant Answer on: // http://stackoverflow.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre ///  /// Compare two double taking in account the double precision potential error. /// Take care: truncation errors accumulate on calculation. More you do, more you should increase the epsilon. /// You get really better performance when you can determine the contextual epsilon first. ///  ///  ///  ///  ///  public static bool AboutEquals(this double value1, double value2, double precalculatedContextualEpsilon) { if (double.IsPositiveInfinity(value1)) return double.IsPositiveInfinity(value2); if (double.IsNegativeInfinity(value1)) return double.IsNegativeInfinity(value2); if (double.IsNaN(value1)) return double.IsNaN(value2); return Math.Abs(value1 - value2) <= precalculatedContextualEpsilon; } // ****************************************************************** public static double GetContextualEpsilon(this double biggestPossibleContextualValue) { return biggestPossibleContextualValue * 1E-15; } // ****************************************************************** ///  /// Mathlab equivalent ///  ///  ///  ///  public static double Mod(this double dividend, double divisor) { return dividend - System.Math.Floor(dividend / divisor) * divisor; } // ****************************************************************** } } 

Here is good solution in JavaScript (with all required mathematics and live illustration) https://bl.ocks.org/milkbread/11000965

Though is_on function in that solution needs modifications:

 function is_on(a, b, c) { return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001; } 

Circle is really a bad guy 🙂 So a good way is to avoid true circle, if you can. If you are doing collision check for games you can go with some simplifications and have just 3 dot products, and a few comparisons.

I call this “fat point” or “thin circle”. its kind of a ellipse with zero radius in a direction parallel to a segment. but full radius in a direction perpendicular to a segment

First, i would consider renaming and switching coordinate system to avoid excessive data:

 s0s1 = BA; s0qp = CA; rSqr = r*r; 

Second, index h in hvec2f means than vector must favor horisontal operations, like dot()/det(). Which means its components are to be placed in a separate xmm registers, to avoid shuffling/hadd’ing/hsub’ing. And here we go, with most performant version of simpliest collision detection for 2D game:

 bool fat_point_collides_segment(const hvec2f& s0qp, const hvec2f& s0s1, const float& rSqr) { auto a = dot(s0s1, s0s1); //if( a != 0 ) // if you haven't zero-length segments omit this, as it would save you 1 _mm_comineq_ss() instruction and 1 memory fetch { auto b = dot(s0s1, s0qp); auto t = b / a; // length of projection of s0qp onto s0s1 //std::cout << "t = " << t << "\n"; if ((t >= 0) && (t <= 1)) // { auto c = dot(s0qp, s0qp); auto r2 = c - a * t * t; return (r2 <= rSqr); // true if collides } } return false; } 

I doubt you can optimize it any further. I am using it for neural-network driven car racing collision detection, to process millions of millions iteration steps.

Here is a solution written in golang. The method is similar to some other answers posted here, but not quite the same. It is easy to implement, and has been tested. Voici les étapes:

  1. Translate coordinates so that the circle is at the origin.
  2. Express the line segment as paramesortingzed functions of t for both the x and y coordinates. If t is 0, the function’s values are one end point of the segment, and if t is 1, the function’s values are the other end point.
  3. Solve, if possible, the quadratic equation resulting from constraining values of t that produce x, y coordinates with distances from the origin equal to the circle’s radius.
  4. Throw out solutions where t is < 0 or > 1 ( <= 0 or >= 1 for an open segment). Those points are not contained in the segment.
  5. Translate back to original coordinates.

The values for A, B, and C for the quadratic are derived here, where (n-et) and (m-dt) are the equations for the line’s x and y coordinates, respectively. r is the radius of the circle.

 (n-et)(n-et) + (m-dt)(m-dt) = rr nn - 2etn + etet + mm - 2mdt + dtdt = rr (ee+dd)tt - 2(en + dm)t + nn + mm - rr = 0 

Therefore A = ee+dd, B = – 2(en + dm), and C = nn + mm – rr.

Here is the golang code for the function:

 package geom import ( "math" ) // SegmentCircleIntersection return points of intersection between a circle and // a line segment. The Boolean intersects returns true if one or // more solutions exist. If only one solution exists, // x1 == x2 and y1 == y2. // s1x and s1y are coordinates for one end point of the segment, and // s2x and s2y are coordinates for the other end of the segment. // cx and cy are the coordinates of the center of the circle and // r is the radius of the circle. func SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r float64) (x1, y1, x2, y2 float64, intersects bool) { // (n-et) and (m-dt) are expressions for the x and y coordinates // of a parameterized line in coordinates whose origin is the // center of the circle. // When t = 0, (n-et) == s1x - cx and (m-dt) == s1y - cy // When t = 1, (n-et) == s2x - cx and (m-dt) == s2y - cy. n := s2x - cx m := s2y - cy e := s2x - s1x d := s2y - s1y // lineFunc checks if the t parameter is in the segment and if so // calculates the line point in the unshifted coordinates (adds back // cx and cy. lineFunc := func(t float64) (x, y float64, inBounds bool) { inBounds = t >= 0 && t <= 1 // Check bounds on closed segment // To check bounds for an open segment use t > 0 && t < 1 if inBounds { // Calc coords for point in segment x = n - e*t + cx y = m - d*t + cy } return } // Since we want the points on the line distance r from the origin, // (n-et)(n-et) + (m-dt)(m-dt) = rr. // Expanding and collecting terms yeilds the following quadratic equation: A, B, C := e*e+d*d, -2*(e*n+m*d), n*n+m*mr*r D := B*B - 4*A*C // discriminant of quadratic if D < 0 { return // No solution } D = math.Sqrt(D) var p1In, p2In bool x1, y1, p1In = lineFunc((-B + D) / (2 * A)) // First root if D == 0.0 { intersects = p1In x2, y2 = x1, y1 return // Only possible solution, quadratic has one root. } x2, y2, p2In = lineFunc((-B - D) / (2 * A)) // Second root intersects = p1In || p2In if p1In == false { // Only x2, y2 may be valid solutions x1, y1 = x2, y2 } else if p2In == false { // Only x1, y1 are valid solutions x2, y2 = x1, y1 } return } 

I tested it with this function, which confirms that solution points are within the line segment and on the circle. It makes a test segment and sweeps it around the given circle:

 package geom_test import ( "testing" . "**put your package path here**" ) func CheckEpsilon(t *testing.T, v, epsilon float64, message ssortingng) { if v > epsilon || v < -epsilon { t.Error(message, v, epsilon) t.FailNow() } } func TestSegmentCircleIntersection(t *testing.T) { epsilon := 1e-10 // Something smallish x1, y1 := 5.0, 2.0 // segment end point 1 x2, y2 := 50.0, 30.0 // segment end point 2 cx, cy := 100.0, 90.0 // center of circle r := 80.0 segx, segy := x2-x1, y2-y1 testCntr, solutionCntr := 0, 0 for i := -100; i < 100; i++ { for j := -100; j < 100; j++ { testCntr++ s1x, s2x := x1+float64(i), x2+float64(i) s1y, s2y := y1+float64(j), y2+float64(j) sc1x, sc1y := s1x-cx, s1y-cy seg1Inside := sc1x*sc1x+sc1y*sc1y < r*r sc2x, sc2y := s2x-cx, s2y-cy seg2Inside := sc2x*sc2x+sc2y*sc2y < r*r p1x, p1y, p2x, p2y, intersects := SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r) if intersects { solutionCntr++ //Check if points are on circle c1x, c1y := p1x-cx, p1y-cy deltaLen1 := (c1x*c1x + c1y*c1y) - r*r CheckEpsilon(t, deltaLen1, epsilon, "p1 not on circle") c2x, c2y := p2x-cx, p2y-cy deltaLen2 := (c2x*c2x + c2y*c2y) - r*r CheckEpsilon(t, deltaLen2, epsilon, "p2 not on circle") // Check if points are on the line through the line segment // "cross product" of vector from a segment point to the point // and the vector for the segment should be near zero vp1x, vp1y := p1x-s1x, p1y-s1y crossProd1 := vp1x*segy - vp1y*segx CheckEpsilon(t, crossProd1, epsilon, "p1 not on line ") vp2x, vp2y := p2x-s1x, p2y-s1y crossProd2 := vp2x*segy - vp2y*segx CheckEpsilon(t, crossProd2, epsilon, "p2 not on line ") // Check if point is between points s1 and s2 on line // This means the sign of the dot prod of the segment vector // and point to segment end point vectors are opposite for // either end. wp1x, wp1y := p1x-s2x, p1y-s2y dp1v := vp1x*segx + vp1y*segy dp1w := wp1x*segx + wp1y*segy if (dp1v < 0 && dp1w < 0) || (dp1v > 0 && dp1w > 0) { t.Error("point not contained in segment ", dp1v, dp1w) t.FailNow() } wp2x, wp2y := p2x-s2x, p2y-s2y dp2v := vp2x*segx + vp2y*segy dp2w := wp2x*segx + wp2y*segy if (dp2v < 0 && dp2w < 0) || (dp2v > 0 && dp2w > 0) { t.Error("point not contained in segment ", dp2v, dp2w) t.FailNow() } if s1x == s2x && s2y == s1y { //Only one solution // Test that one end of the segment is withing the radius of the circle // and one is not if seg1Inside && seg2Inside { t.Error("Only one solution but both line segment ends inside") t.FailNow() } if !seg1Inside && !seg2Inside { t.Error("Only one solution but both line segment ends outside") t.FailNow() } } } else { // No intersection, check if both points outside or inside if (seg1Inside && !seg2Inside) || (!seg1Inside && seg2Inside) { t.Error("No solution but only one point in radius of circle") t.FailNow() } } } } t.Log("Tested ", testCntr, " examples and found ", solutionCntr, " solutions.") } 

Here is the output of the test:

 === RUN TestSegmentCircleIntersection --- PASS: TestSegmentCircleIntersection (0.00s) geom_test.go:105: Tested 40000 examples and found 7343 solutions. 

Finally, the method is easily extendable to the case of a ray starting at one point, going through the other and extending to infinity, by only testing if t > 0 or t < 1 but not both.

I just needed that, so I came up with this solution. The language is maxscript, but it should be easily translated to any other language. sideA, sideB and CircleRadius are scalars, the rest of the variables are points as [x,y,z]. I’m assuming z=0 to solve on the plane XY

 fn projectPoint p1 p2 p3 = --project p1 perpendicular to the line p2-p3 ( local v= normalize (p3-p2) local p= (p1-p2) p2+((dot vp)*v) ) fn findIntersectionLineCircle CircleCenter CircleRadius LineP1 LineP2= ( pp=projectPoint CircleCenter LineP1 LineP2 sideA=distance pp CircleCenter --use pythagoras to solve the third side sideB=sqrt(CircleRadius^2-sideA^2) -- this will return NaN if they don't intersect IntersectV=normalize (pp-CircleCenter) perpV=[IntersectV.y,-IntersectV.x,IntersectV.z] --project the point to both sides to find the solutions solution1=pp+(sideB*perpV) solution2=pp-(sideB*perpV) return #(solution1,solution2) )