algorithm - ¿Algoritmo de detección de colisiones por segmento de línea circular?
math line (22)
Tengo una línea de A a B y un círculo posicionado en C con el radio R.
¿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ó?
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 allí, 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 .
// 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 (x-X)^2 + (y-Y)^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 = (-B-D)/(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 [];
}
De acuerdo, no te daré el código, pero como has etiquetado este algorithm , 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!
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 )
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 )
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 )
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 )
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.
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);
}
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 - c.x, y:p1.y - c.y} //shifted line points
var p4 = {x:p2.x - c.x, y:p2.y - c.y}
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.
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 - c.x, y:p1.y - c.y}; //shifted line points
var p4 = {x:p2.x - c.x, y:p2.y - c.y};
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+c.x, y:m*t1+b+c.y}; //intercept point 1
var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
return [i1, i2];
}
}
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:
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.
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 here 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.
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.
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
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:
/// <summary>
/// Intersects a line and a circle.
/// </summary>
/// <param name="location">the location of the circle</param>
/// <param name="radius">the radius of the circle</param>
/// <param name="lineFrom">the starting point of the line</param>
/// <param name="lineTo">the ending point of the line</param>
/// <returns>true if the line and circle intersect each other</returns>
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));
}
Tomando
- E es el punto de partida del rayo,
- L es el punto final del rayo,
- C es el centro de la esfera contra la que estás probando
- 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:
- Expandir
x 2 - 2xh + h 2 + y 2 - 2yk + k 2 - r 2 = 0 - 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 - 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 - 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 2 - 2 e x h - 2 e y k + h 2 + k 2 - r 2 = 0 - 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. * - Y entonces,
t 2 (_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r 2 = 0 - 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:
// -> o o -> | -> |
// 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 ;
}
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
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;
}
Another one in c# (partial Circle class). Tested and works like a charm.
public class Circle : IEquatable<Circle>
{
// ******************************************************************
// The center of a circle
private Point _center;
// The radius of a circle
private double _radius;
// ******************************************************************
/// <summary>
/// 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
/// </summary>
/// <param name="linePoint1"></param>
/// <param name="linePoint2"></param>
/// <returns></returns>
public List<Point> GetIntersections(Point linePoint1, Point linePoint2)
{
List<Point> intersections = new List<Point>();
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<Point> 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://.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre
/// <summary>
/// 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://.com/questions/2411392/double-epsilon-for-equality-greater-than-less-than-less-than-or-equal-to-gre
/// <summary>
/// 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.
/// </summary>
/// <param name="value1"></param>
/// <param name="value2"></param>
/// <param name="precalculatedContextualEpsilon"></param>
/// <returns></returns>
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;
}
// ******************************************************************
/// <summary>
/// Mathlab equivalent
/// </summary>
/// <param name="dividend"></param>
/// <param name="divisor"></param>
/// <returns></returns>
public static double Mod(this double dividend, double divisor)
{
return dividend - System.Math.Floor(dividend / divisor) * divisor;
}
// ******************************************************************
}
}
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 = B-A;
s0qp = C-A;
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. Here are the steps:
- Translate coordinates so that the circle is at the origin.
- 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.
- 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.
- Throw out solutions where t is < 0 or > 1 ( <= 0 or >= 1 for an open segment). Those points are not contained in the segment.
- 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.
Aquí está el código de golang para la función:
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*m-r*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
}
Lo probé con esta función, que confirma que los puntos de solución están dentro del segmento de línea y en el círculo. Hace un segmento de prueba y lo barre alrededor del círculo dado:
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.")
}
Aquí está el resultado de la prueba:
=== RUN TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
geom_test.go:105: Tested 40000 examples and found 7343 solutions.
Finalmente, el método es fácilmente extensible al caso de un rayo que comienza en un punto, pasa por el otro y se extiende hasta el infinito, al probar solo si t> 0 o t <1, pero no ambos.
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;
}
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;
}
'' 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