¿Algoritmo de detección de colisiones por segmento de línea circular?

Tengo una línea de A a B y un círculo posicionado en C con el radio R.

Imagen

¿Qué es un buen algoritmo para verificar si la línea se cruza con el círculo? ¿Y en qué coordenadas a lo largo del borde del círculo ocurrió?

Tomando

  1. E es el punto de partida del rayo,
  2. L es el punto final del rayo,
  3. C es el centro de la esfera contra la que estás probando
  4. r es el radio de esa esfera

Calcular:
d = L – E (Vector de dirección del rayo, de principio a fin)
f = E – C (Vector de la esfera central al comienzo del rayo)

Entonces la intersección se encuentra por ..
Taponamiento
P = E + t * d
Esta es una ecuación paramétrica:
P x = E x + td x
P y = E y + td y
dentro
(x – h) 2 + (y – k) 2 = r 2
(h, k) = centro del círculo.

Nota: aquí simplificamos el problema a 2D, la solución que obtenemos también se aplica en 3D

Llegar:

  1. Expandir
    x 2 – 2xh + h 2 + y 2 – 2yk + k 2 – r 2 = 0
  2. Enchufe
    x = e x + td x
    y = e y + td y
    (e x + td x ) 2 – 2 (e x + td x ) h + h 2 + (e y + td y ) 2 – 2 (e y + td y ) k + k 2 – r 2 = 0
  3. Explotar
    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. Grupo
    t 2 (d x 2 + d y 2 ) + 2t (e x d x + e y d y – d x h – d y k) + e x 2 + e y 22 e x h – 2 e y k + h 2 + k 2 – r 2 = 0
  5. Finalmente,
    t 2 (_d * _d) + 2t (_e * _d – _d * _c) + _e * _e – 2 (_e * _c) + _c * _c – r 2 = 0
    * Donde _d es el vector d y * es el producto escalar. *
  6. Y entonces,
    t 2 (_d * _d) + 2t (_d * (_e – _c)) + (_e – _c) * (_e – _c) – r 2 = 0
  7. Dejando _f = _e – _c
    t 2 (_d * _d) + 2t (_d * _f) + _f * _f – r 2 = 0

Entonces obtenemos:
t 2 * (d DOT d) + 2t * (f DOT d) + (f DOT f – r 2 ) = 0
Entonces resolviendo la ecuación cuadrática:

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 ; } 

Nadie parece considerar la proyección, ¿estoy completamente fuera de pista aquí?

Proyecte el vector AC sobre AB . El vector proyectado, AD , da el nuevo punto D
Si la distancia entre D y C es menor que (o igual a) R , tenemos una intersección.

Me gusta esto:
Imagen de SchoolBoy

Utilizaría el algoritmo para calcular la distancia entre un punto (centro del círculo) y una línea (línea AB). Esto se puede usar para determinar los puntos de intersección de la línea con el círculo.

Digamos que tenemos los puntos A, B, C. Axe y Ay son los componentes xey de los puntos A. Lo mismo para B y C. El escalar R es el radio del círculo.

Aquí está el algoritmo

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

De acuerdo, no te daré el código, pero como has etiquetado este algoritmo , no creo que eso te importe. Primero, debes obtener un vector perpendicular a la línea.

Tendrás una variable desconocida en y = ax + c ( c será desconocido )
Para resolver eso, calcula su valor cuando la línea pase por el centro del círculo.

Es decir,
Conecta la ubicación del centro del círculo a la ecuación de la línea y resuelve para c .
Luego calcule el punto de intersección de la línea original y su punto normal.

Esto le dará el punto más cercano en la línea al círculo.
Calcule la distancia entre este punto y el centro del círculo (usando la magnitud del vector).
Si esto es menor que el radio del círculo – ¡voila, tenemos una intersección!

Otro método usa la fórmula del área del triángulo ABC. La prueba de intersección es más simple y más eficiente que el método de proyección, pero encontrar las coordenadas del punto de intersección requiere más trabajo. Al menos se retrasará hasta el punto en que se requiera.

La fórmula para calcular el área del triángulo es: area = bh / 2

donde b es la longitud de la base y h es la altura. Elegimos el segmento AB como base para que h sea la distancia más corta desde C, el centro del círculo, hasta la línea.

Dado que el área del triángulo también se puede calcular mediante un producto vectorial en puntos, podemos determinar h.

 // compute the triangle 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 triangle height h = area2/LAB // if the line intersects the circle if( h < R ) { ... } 

ACTUALIZACIÓN 1:

Puede optimizar el código utilizando el cálculo de raíz cuadrada inversa rápida descrito aquí para obtener una buena aproximación de 1 / LAB.

Calcular el punto de intersección no es tan difícil. Aquí 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, entonces la línea AB es tangente al círculo y el valor dt = 0 y E = F. Las coordenadas del punto son las de E y F.

Debería verificar que A es diferente de B y que la longitud del segmento no es nula si esto puede suceder en su aplicación.

Escribí un pequeño guión para probar la intersección al proyectar el punto central del círculo sobre la línea.

 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 necesita verificar la colisión con el segmento, también debe considerar la distancia del centro del círculo a los puntos de inicio y fin.

 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/

Esta solución que encontré parecía un poco más fácil de seguir que algunas otras.

Tomando:

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

Resolvería la ecuación de la línea en forma pendiente-intersección. Sin embargo, no quería tener que lidiar con ecuaciones difíciles con c como punto, así que cambié el sistema de coordenadas para que el círculo esté a 0,0

 p3 = p1 - c p4 = p2 - c 

Por cierto, siempre que restamos puntos el uno del otro, estoy restando las x y luego restando las y , y poniéndolas en un nuevo punto, por si alguien no lo sabía.

De todos modos, ahora resuelvo la ecuación de la línea con p3 y 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) 

De acuerdo. Ahora necesito establecer estas ecuaciones iguales. Primero necesito resolver la ecuación del círculo para x

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

Luego los puse iguales:

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

Y resuelve para la ecuación cuadrática ( 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 

Ahora tengo mi a , b y c .

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

Así que puse esto en la fórmula cuadrática:

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

Y sustitúyalo por valores y luego simplifique lo más posible:

 (-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 

Esto es casi tan lejos como simplificará. Finalmente, separe las ecuaciones con el ±:

 (-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 

Luego simplemente conecte el resultado de ambas ecuaciones en la x en mx + b . Para mayor claridad, escribí un código JavaScript para mostrar cómo usar esto:

 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]; } } 

¡Espero que esto ayude!

PD. Si alguien encuentra algún error o tiene alguna sugerencia, por favor comente. Soy muy nuevo y bienvenido a toda ayuda / sugerencia.

Puede encontrar un punto en una línea infinita que esté más cerca del centro del círculo proyectando el vector AC sobre el vector AB. Calcule la distancia entre ese punto y el centro del círculo. Si es mayor que R, no hay intersección. Si la distancia es igual a R, la línea es una tangente del círculo y el punto más cercano al centro del círculo es en realidad el punto de intersección. Si la distancia es menor que R, entonces hay 2 puntos de intersección. Se encuentran a la misma distancia del punto más cercano al centro del círculo. Esa distancia puede calcularse fácilmente usando el teorema de Pitágoras. Aquí está el algoritmo en pseudocódigo:

 { 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 } } 

EDITAR: código agregado para verificar si los puntos de intersección encontrados están realmente dentro del segmento de línea.

Extrañamente puedo responder pero no comentar … Me gustó el enfoque de Multitaskpro de cambiar todo para hacer que el centro del círculo caiga sobre el origen. Desafortunadamente hay dos problemas en su código. Primero en la parte de la raíz debajo de la raíz cuadrada, necesita eliminar la doble potencia. Entonces no:

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

pero:

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

En las coordenadas finales, olvida cambiar la solución. Entonces no:

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

pero:

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

La función completa se convierte en:

 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]; } } 

Necesitarás algunas matemáticas aquí:

Supongamos que A = (Xa, Ya), B = (Xb, Yb) y C = (Xc, Yc). Cualquier punto en la línea de A a B tiene coordenadas (alfa * Xa + (1-alfa) Xb, alfa Ya + (1-alfa) * Yb) = P

Si el punto P tiene una distancia de R a C, debe estar en el círculo. Lo que quieres es resolver

 distance(P, C) = R 

es decir

 (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 aplicas la fórmula ABC a esta ecuación para resolverla en alfa, y calculas las coordenadas de P usando la (s) solución (es) para alfa, obtienes los puntos de intersección, si existen.

Si encuentra la distancia entre el centro de la esfera (ya que es 3D supongo que quiere decir esfera y no círculo) y la línea, entonces verifique si esa distancia es menor que el radio que hará el truco.

El punto de colisión es obviamente el punto más cercano entre la línea y la esfera (que se calculará cuando se calcula la distancia entre la esfera y la línea)

Distancia entre un punto y una línea:
http://mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

Aquí hay una implementación en Javascript. Mi enfoque es convertir primero el segmento de línea en una línea infinita y luego buscar el (los) punto (s) de intersección. A partir de ahí, verifico si el / los punto (s) encontrado (s) están en el segmento de línea. El código está bien documentado, debería poder seguirlo.

Puedes probar el código aquí en esta demostración en vivo . El código fue tomado de mi algoritmo repo .

enter image description here

 // 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 []; } 

En esta línea de círculo posterior se comprobará la colisión comprobando la distancia entre el centro del círculo y el segmento de punto en línea (Ipoint) que representa el punto de intersección entre N normal (Imagen 2) desde el centro del círculo hasta el segmento de línea.

( https://i.stack.imgur.com/3o6do.png ) Imagen 1. Encontrar vectores E y D

En la imagen 1 se muestran un círculo y una línea, vector A punto para inicio de línea, vector B punto para línea final, vector C apunta al centro del círculo. Ahora debemos encontrar el vector E (desde el punto de inicio de la línea hasta el centro del círculo) y el vector D (desde el punto de inicio de la línea hasta el punto final de la línea) este cálculo se muestra en la imagen 1.

( https://i.stack.imgur.com/7098a.png ) Imagen 2. Encontrar el vector X

En la imagen 2 podemos ver que el vector E se proyecta sobre el Vector D mediante el “producto punto” del vector E y el vector unitario D, el resultado del producto escalar es Xp escalar que representa la distancia entre el punto de inicio de la línea y el punto de intersección (Ipoint) vector N y vector D. El siguiente vector X se encuentra multiplicando el vector unitario D y el escalar Xp.

Ahora tenemos que encontrar el vector Z (vector a Ipoint), es fácil su simple vector de vector A (punto de inicio en línea) y vector X. A continuación tenemos que tratar con casos especiales que debemos verificar es Ipoint en segmento de línea, si no es así, tenemos que averiguar si queda de ella o no, usaremos el vector más cercano para determinar qué punto está más cerca del círculo.

( https://i.stack.imgur.com/p9WIr.png ) Imagen 3. Encontrar el punto más cercano

Cuando la proyección Xp es negativa Ipoint queda del segmento de línea, el vector más cercano es igual al vector de inicio de línea, cuando la proyección Xp es mayor que la magnitud del vector D, entonces Ipoint está a la derecha del segmento de línea, entonces el vector más cercano es el vector de línea final señalar en cualquier otro caso que el vector más cercano es igual al vector Z.

Ahora, cuando tenemos el vector más cercano, necesitamos encontrar el vector del centro del círculo a Ipoint (vector dist), es simple, solo tenemos que restar el vector más cercano del vector central. A continuación, simplemente compruebe si la magnitud del vector dist es menor que el radio del círculo si es entonces cuando colisionan, si no es así, no hay colisión.

( https://i.stack.imgur.com/QJ63q.png ) Imagen 4. Comprobación de colisión

Para finalizar, podemos devolver algunos valores para resolver la colisión, la manera más fácil es devolver la superposición de colisión (restar el radio de la magnitud del vector dist) y devolver el eje de colisión, su vector D. También el punto de intersección es el vector Z si es necesario.

Si las coordenadas de la línea son Ax, Ay y Bx, By y el centro de los círculos es Cx, Cy, entonces las fórmulas de las líneas son:

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

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

donde 0 <= t <= 1

y el circulo es

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

si sustituyes las fórmulas xey de la línea en la fórmula de círculos obtienes una ecuación de segundo orden de t y sus soluciones son los puntos de intersección (si hay alguno). Si obtiene un valor menor que 0 o mayor que 1, entonces no es una solución, pero muestra que la línea está “apuntando” a la dirección del círculo.

Solo una adición a este hilo … A continuación se muestra una versión del código publicado por pahlevan, pero para C # / XNA y se arregló un poco:

  ///  /// 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)); } 

enter image description here

 ' 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 

chmike esta función para iOS siguiendo la respuesta dada por 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. Estos son los pasos:

  1. Translate coordinates so that the circle is at the origin.
  2. Express the line segment as parametrized 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 string) { 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) )