Algoritmo de detección de colisión de segmento de línea circular

196

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

Imagen

¿Cuál es un buen algoritmo para verificar si la línea se cruza con el círculo? ¿Y en qué coordenada se produjo el borde de los círculos?

Mizipzor
fuente
44
Hmm Una pregunta: ¿estás hablando de la línea infinita a través de A y B, o el segmento de línea finita de A a B?
Jason S
2
En este caso, es el segmento de línea finita. ¿Se llama "línea" a otra cosa dependiendo de si es finita o infinita?
Mizipzor
1
¿Hay algún requisito de rendimiento? ¿Debería ser un método rápido?
chmike
En este punto, no, todos los algoritmos aquí que he probado no ralentizan notablemente la aplicación.
Mizipzor
13
@Mizipzor sí, se llaman algo más: segmentos de línea . Si solo dice "línea", implica una infinita.
MestreLion

Respuestas:

200

Tomando

  1. mi 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 inicio del rayo)

Luego, la intersección se encuentra mediante ...
Plugging:
P = E + t * d
Esta es una ecuación paramétrica:
P x = E x + td x
P y = E y + td y
en
(x - h) 2 + (y - k) 2 = r 2
(h, k) = centro del círculo.

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

Llegar:

  1. Expandir
    x 2 - 2xh + h 2 + y 2 - 2yk + k 2 - r 2 = 0
  2. Plug
    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 2 - 2e x h - 2e 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 punto. *
  6. Y luego,
    t 2 (_d * _d) + 2t (_d * (_e - _c)) + (_e - _c) * (_e - _c) - r 2 = 0
  7. Dejar _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 ;
}
bobobobo
fuente
1
Parece funcionar si copio y pego directamente, pero estoy tratando de entenderlo. En (xh) ^ 2 + (yk) ^ 2 = r ^ 2 ¿qué es h y k? ¿Es k constante por la cual la línea / rayo aumenta en y sobre x? ¿Y qué es t? Al mirar el código, parece que has asumido que es 1 (por lo que simplemente se "eliminó"). ¿Estas fórmulas tienen un nombre o algo así? Tal vez pueda buscarlos en detalle en Wolfram.
Mizipzor
3
h y k son el centro del círculo con el que se cruzan. t es el parámetro de la ecuación de línea. En el código, t1 y t2 son las soluciones. t1 y t2 le dicen "qué tan lejos a lo largo del rayo" ocurrió la intersección.
bobobobo
1
Ok lo tengo. El producto punto simplemente se calcula sobre los vectores de tres elementos (x, y, z). Cambiaré mi código a este algoritmo.
chmike
21
P = E + t * d¿Qué es t?
Derek 朕 會 功夫
3
No estoy seguro de por qué, pero el código no parece funcionar para el caso Impale. Lo hace cuando agrego si t1 <= 0 && t1> = -1 && t2 <= 0 && t2> = -1 como condición verdadera, pero luego también da un falso positivo en un lado de la línea finita, cuando el círculo está en la parte "infinita". Todavía no entiendo las matemáticas, pero copia / pega, ten cuidado.
Nicolas Mommaerts
142

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

Proyecta el vector ACsobre AB. El vector proyectado AD, da el nuevo punto D.
Si la distancia entre Dy Ces menor que (o igual a)R tenemos una intersección.

Me gusta esto:
Image by SchoolBoy

Mizipzor
fuente
9
Hay muchos detalles a tener en cuenta: ¿D se encuentra entre AB? ¿La distancia perpendicular de C a la línea es mayor que el radio? Todos estos implican la magnitud del vector, es decir, la raíz cuadrada.
ADB
15
Buena idea, pero ¿cómo calculas los dos puntos de intersección?
Ben
44
@ Spider no importa. En general, dado que esta es una variante del problema de intersección esfera-línea, la estrategia de Mizipzor es perfectamente válida. CDes una proyección, es perpendicular por definición.
2
Es una pregunta antigua, pero hay un buen recurso sobre este y los algoritmos relacionados en este sitio web: paulbourke.net/geometry/pointlineplane
Andrew
1
Una gran explicación de esta respuesta: scratchapixel.com/lessons/3d-basic-rendering/…
ShawnFeatherly
50

Usarí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. Ax y Ay son los componentes x e y de los puntos A. Lo mismo para B y C. El escalar R es el radio del círculo.

Este algoritmo requiere que A, B y C sean puntos distintos y que R no sea 0.

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

// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.

// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

    // compute first intersection point
    Fx = (t-dt)*Dx + Ax
    Fy = (t-dt)*Dy + Ay

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle
chmike
fuente
si alguna línea que no se cruza con el círculo y sus puntos p1 y p2 están dentro del círculo en este caso, ¿cómo funciona tu algoritmo?
Prashant
1
Tienes que probar t-dt y t + dt. Si t-dt <0, entonces p1 está dentro del círculo. Si t + dt> 1, entonces p2 está dentro del círculo. Esto es cierto si LEC <R, por supuesto.
Chmike
Gracias. Me gustaron estos comentarios de PGM como explicación porque no había uso de las palabras "producto de punto" ya que mis matemáticas están oxidadas. Sin embargo, t y dt no están entre 0..1, así que al cambiar esto a python cambié t para dividirlo por LAB ** 2. Entiendo que la primera división por LAB es proyectar el centro del círculo a la línea AB, y la segunda división por LAB es normalizarlo en el rango 0..1. Además, el dt debe dividirse por LAB para que también se normalice. Por lo tanto, "if (t-dt> = 0.0)" existe la primera intersección "if (t + dt <= 1.0)" existe la segunda intersección. Esto funcionó con las pruebas.
tarjeta perforada
2
Porque el punto de intersección con el círculo está a "distancia" t+dty t-dten la línea. tes el punto en la línea más cercana al centro del círculo. Los puntos de intersección con el círculo están a una distancia simétrica de t. Los puntos de intersección están a "distancias" t-dty t+dt. Cité la distancia porque no es la distancia euclidiana. Para obtener la distancia euclidiana desde Adonde t=0, tienes que multiplicar el valor por LAB.
Chmike
1
@Matt W ¿Quiere decir "Cómo determinar si la intersección ocurre fuera de los puntos finales de la sección de línea AB"? Solo piense en t como una medida de la distancia a lo largo de la línea. El punto A está en t=0. Punto B en t=LAB. Cuando ambos puntos de intersección ( t1=t-tdy t2=t+td) tienen valores negativos, las intersecciones están fuera de la sección (detrás del punto A mirando desde el lado de la sección del punto). Cuando t1 y t2 son más grandes que LAB, también están afuera (esta vez detrás del punto B). La intersección t1 (o t2) ocurre entre A y B solo cuando t1 (o t2) está entre 0 y LAB.
Marconius
20

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

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

Es decir,
conecte la ubicación del centro del círculo a la ecuación de línea y resuelva c.
Luego calcule el punto de intersección de la línea original y su normalidad.

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!

a_m0d
fuente
2
Eso era, de hecho, lo que quería. Quiero la teoría, una búsqueda en Google del algoritmo de colisión línea-círculo solo muestra código hasta donde puedo ver.
Mizipzor
Ok, c es desconocido en tu ecuación, pero ¿qué es "a"? Las otras respuestas parecen referirse a esa variable como "alfa" y "t". Aunque, esto es solo una función lineal (y = kx + m), matemática bastante básica, por lo que de repente me siento un poco oxidado. ¿No es k también desconocido? ¿O quiere decir que podemos asumir m = 0 y resolver k? ¿No sería entonces m (es decir, c) siempre cero para nuestra k resuelta?
Mizipzor
1
Oh, lo siento, estoy usando la ecuación simple de una línea con un gradiente y un desplazamiento (la ecuación cartesiana). Supuse que estabas almacenando la línea como tal ecuación, en cuyo caso usas el negativo del gradiente para k. Si no tiene la línea almacenada de esta manera, puede calcular k como (y2-y1) / (x2-x1)
a_m0d
1
No suponemos que m es cero; calculamos primero el gradiente (de modo que la ecuación de la línea luego se vea como y = 2x + m como ejemplo), y luego, una vez que tengamos el gradiente, podemos resolver m conectando el centro del círculo para y y x .
a_m0d el
1
+1 Explicación impresionante! Pero creo que esto supone una línea, no un segmento de línea. Entonces, si el punto más cercano en esta línea al centro del círculo no estuviera entre los puntos A y B, todavía se contaría.
Hassan
12

Otro método utiliza 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 requerido.

La fórmula para calcular el área del triángulo es: área = 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 puede ser calculada por un producto de puntos vectoriales, 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 rápido de la raíz cuadrada inversa 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.

Debe verificar que A sea diferente de B y que la longitud del segmento no sea nula si esto puede suceder en su aplicación.

chmike
fuente
2
Me gusta la simplicidad en este método. Tal vez podría adaptar parte del código circundante para no necesitar el punto de colisión real. Veré qué sucede si uso A o B en lugar del punto calculado en el medio.
Mizipzor
1
t = Dx * (Cx-Ax) + Dy * (Cy-Ax) debería leer t = Dx * (Cx-Ax) + Dy * (Cy-Ay)
Stonetip
Esto es correcto. Gracias por señalarlo. Lo corregí en la publicación.
Chmike
recién editado: la primera línea calcula el área del triángulo utilizando un producto cruzado , no un producto de puntos. verificado con código aquí: stackoverflow.com/questions/2533011/…
ericsoco
44
tenga en cuenta también que la primera mitad de esta respuesta prueba la intersección con una línea, no un segmento de línea (como se preguntó en la pregunta).
ericsoco
8

Escribí un pequeño guión para probar la intersección proyectando el punto central del círculo en una 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 finalización.

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/

ercang
fuente
5

Esta solución que encontré parecía un poco más fácil de seguir que algunas de las 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 de pendiente-intersección. Sin embargo, no quería tener que lidiar con ecuaciones difíciles ccomo un punto, así que simplemente cambié el sistema de coordenadas para que el círculo esté en0,0

p3 = p1 - c
p4 = p2 - c

Por cierto, cada vez que resta puntos el uno del otro estoy restando los x's y luego restando losy ' s, y poniéndolos en un nuevo punto, en caso de que alguien no lo supiera.

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

Okay. Ahora necesito establecer estas ecuaciones iguales. Primero necesito resolver la ecuación del círculo parax

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 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, by c.

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

Así que pongo 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 se simplificará. Finalmente, separe las ecuaciones con ±:

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

Entonces sólo tiene que conectar el resultado de estos dos ecuaciones en el xen 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 agradezco toda ayuda / sugerencia.

multitaskPro
fuente
Si es posible, también publique con algunos valores de muestra para que podamos captar rápidamente el flujo.
Prabindh
Con underRadicalextra ')'
porJeevan
4

Puede encontrar un punto en una línea infinita más cercana al 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 se puede calcular 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 realmente están dentro del segmento de línea.

Juozas Kontvainis
fuente
Te perdiste un caso ya que estamos hablando de un segmento de línea: cuando el segmento termina en el círculo.
ADB
@ADB en realidad mi algoritmo solo funciona para líneas infinitas, no para segmentos de línea. Hay muchos casos que no maneja con segmentos de línea.
Juozas Kontvainis
La pregunta original era sobre segmentos de línea, no intersección de línea circular, que es un problema mucho más fácil.
msumme
4

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 en el origen. Lamentablemente, hay dos problemas en su código. Primero, en la parte debajo de la raíz cuadrada, debe 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 olvidarse de la solución. Entonces no:

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

pero:

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

Toda la función 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];
    }
}
Duq
fuente
1
sugerencias: Primero, haga que maneje el caso donde el segmento de línea es vertical (es decir, tiene pendiente infinita). En segundo lugar, haga que solo devuelva los puntos que realmente se encuentran dentro del rango del segmento de línea original; creo que felizmente devuelve todos los puntos que caen en la línea infinita, incluso si esos puntos se encuentran fuera del segmento de línea.
Gino
Nota: Esto funciona bien para líneas, pero no funciona para segmentos de línea.
Mike
3

Necesitarás algunas matemáticas aquí:

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

Martijn
fuente
3

Si encuentra la distancia entre el centro de la esfera (dado que es 3D, supongo que quiere decir esfera y no círculo) y la línea, luego 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 calcules 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

Martín
fuente
1
Está en 2D, no en 3D; como dices, esto realmente no importa
Martijn
No soy matemático, así que pensé que estaría delineando mejor un enfoque general y dejando a los demás para averiguar las matemáticas específicas (aunque tiene un aspecto bastante trivial)
Martin
2
+1 con un fuerte voto a favor. (aunque me hubiera vinculado a otro sitio, el sitio pbourke parece confuso) Todas las otras respuestas hasta ahora son demasiado complicadas. Aunque su comentario "Ese punto también es el punto de intersección en la línea" es incorrecto, no hay ningún punto que se haya construido en el proceso de cálculo.
Jason S
Le expliqué un poco mejor sobre el punto más cercano, y está conectado con Mathworld en lugar de pbourke :)
Martin
3

Aquí hay una implementación en Javascript. Mi enfoque es convertir primero el segmento de línea en una línea infinita y luego encontrar los puntos de intersección. Desde allí verifico si los puntos encontrados están en el segmento de línea. El código está bien documentado, debería poder seguirlo.

Puede probar el código aquí en esta demostración en vivo . El código fue tomado de mi repositorio de algoritmos .

ingrese la descripción de la imagen aquí

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

}
will.fiset
fuente
3

En esta publicación, la colisión de línea circular se verificará verificando la distancia entre el centro del círculo y el punto en el segmento de línea (Ipoint) que representa el punto de intersección entre el N normal (Imagen 2) del centro del círculo al segmento de línea.

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

En la imagen 1 se muestran un círculo y una línea, el punto de inicio del vector A al punto de línea, el punto final del vector B al final de la línea, el punto del vector C al centro del círculo. Ahora debemos encontrar el vector E (desde el punto inicial de la línea hasta el centro del círculo) y el vector D (desde el punto inicial 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 en el Vector D por el "producto de punto" del vector E y el vector de unidad D, el resultado del producto de punto es el escalar Xp que representa la distancia entre el punto inicial de la línea y el punto de intersección (Ipoint) de vector N y vector D. El siguiente vector X se encuentra multiplicando el vector unitario D y el escalar Xp.

Ahora necesitamos encontrar el vector Z (vector a Ipoint), es fácil su simple adición de vector del vector A (punto de inicio en la línea) y el vector X. A continuación, debemos tratar con casos especiales que debemos verificar es Ipoint en el segmento de línea, si no debemos averiguar si está a la izquierda o a la derecha, 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 está a la izquierda del segmento de línea, el vector más cercano es igual al vector del punto 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 y el vector más cercano es igual al vector del final de línea punto en cualquier otro caso, el vector más cercano es igual al vector Z.

Ahora, cuando tenemos el vector más cercano, necesitamos encontrar el vector desde el centro del círculo hasta Ipoint (vector dist), es simple, solo necesitamos restar el vector más cercano del vector central. A continuación, verifique si la magnitud de la distancia del vector es menor que el radio del círculo si es así, entonces 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 forma más fácil es devolver la superposición de la 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.

FunDeveloper89
fuente
2

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 círculo es

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

si sustituye las fórmulas x e y de la línea en la fórmula de los círculos, obtiene una ecuación de segundo orden de t y sus soluciones son los puntos de intersección (si los hay). Si obtiene que es 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.

Gábor Hargitai
fuente
2

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 arreglado 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));
    }
Robar
fuente
En C # / XNA puedes usarRay.Intersects(BoundingSphere)
bobobobo
2

ingrese la descripción de la imagen aquí

' 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
AJBauer
fuente
2

He creado 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;
}
Aqib Mumtaz
fuente
2

Otro en c # (clase de círculo parcial). Probado y funciona a las mil maravillas.

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

Necesario:

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

        /// <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://stackoverflow.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;
        }

        // ******************************************************************
    }
}
Eric Ouellet
fuente
2

Aquí hay una buena solución en JavaScript (con todas las matemáticas y la ilustración en vivo necesarias) https://bl.ocks.org/milkbread/11000965

Aunque la is_onfunción en esa solución necesita modificaciones:

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

nazar kuliyev
fuente
2

Circle es realmente un chico malo :) Entonces, una buena manera es evitar un círculo verdadero, si puedes. Si está haciendo una verificación de colisión para juegos, puede realizar algunas simplificaciones y tener solo 3 productos de puntos, y algunas comparaciones.

Yo llamo a esto "punto gordo" o "círculo delgado". Es una especie de elipse con radio cero en una dirección paralela a un segmento. pero radio completo en una dirección perpendicular a un segmento

Primero, consideraría renombrar y cambiar el sistema de coordenadas para evitar datos excesivos:

s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;

Segundo, el índice h en hvec2f significa que el vector debe favorecer las operaciones horizontales, como dot () / det (). Lo que significa que sus componentes deben colocarse en registros xmm separados, para evitar barajar / hadd'ing / hsub'ing. Y aquí vamos, con la versión más eficiente de la detección de colisión más simple para juegos 2D:

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

Dudo que puedas optimizarlo más. Lo estoy usando para la detección de colisiones de carreras de autos impulsadas por redes neuronales, para procesar millones de millones de pasos de iteración.

xakepp35
fuente
Si el segmento de línea se cruza con el círculo pero solo ligeramente para que no pase su punto central, ¿esta función no devolverá falso cuando debería devolver verdadero? El valor t podría estar fuera del rango 0..1.
Chris
1

Esta función Java devuelve un objeto DVec2. Se necesita un DVec2 para el centro del círculo, el radio del círculo y una línea.

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;
}
pahlevan
fuente
1

Aquí está mi solución en TypeScript, siguiendo la idea que @Mizipzor sugirió (usando proyección):

/**
 * Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
 * @param a the start point of the line segment
 * @param b the end point of the line segment
 * @param c the center point of the sphere
 * @param r the radius of the sphere
 */
export function lineSphereIntersects(
  a: IPoint,
  b: IPoint,
  c: IPoint,
  r: number
): boolean {
  // find the three sides of the triangle formed by the three points
  const ab: number = distance(a, b);
  const ac: number = distance(a, c);
  const bc: number = distance(b, c);

  // check to see if either ends of the line segment are inside of the sphere
  if (ac < r || bc < r) {
    return true;
  }

  // find the angle between the line segment and the center of the sphere
  const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
  const denominator: number = 2 * ac * ab;
  const cab: number = Math.acos(numerator / denominator);

  // find the distance from the center of the sphere and the line segment
  const cd: number = Math.sin(cab) * ac;

  // if the radius is at least as long as the distance between the center and the line
  if (r >= cd) {
    // find the distance between the line start and the point on the line closest to
    // the center of the sphere
    const ad: number = Math.cos(cab) * ac;
    // intersection occurs when the point on the line closest to the sphere center is
    // no further away than the end of the line
    return ad <= ab;
  }
  return false;
}

export function distance(a: IPoint, b: IPoint): number {
  return Math.sqrt(
    Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
  );
}

export interface IPoint {
  x: number;
  y: number;
  z: number;
}
Joe Skeen
fuente
1

Sé que ha pasado un tiempo desde que este hilo estuvo abierto. De la respuesta dada por chmike y mejorada por Aqib Mumtaz. Dan una buena respuesta, pero solo funciona para una línea infinita, como dijo Aqib. Entonces agrego algunas comparaciones para saber si el segmento de línea toca el círculo, lo escribo en Python.

def LineIntersectCircle(c, r, p1, p2):
    #p1 is the first line point
    #p2 is the second line point
    #c is the circle's center
    #r is the circle's radius

    p3 = [p1[0]-c[0], p1[1]-c[1]]
    p4 = [p2[0]-c[0], p2[1]-c[1]]

    m = (p4[1] - p3[1]) / (p4[0] - p3[0])
    b = p3[1] - m * p3[0]

    underRadical = math.pow(r,2)*math.pow(m,2) + math.pow(r,2) - math.pow(b,2)

    if (underRadical < 0):
        print("NOT")
    else:
        t1 = (-2*m*b+2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        t2 = (-2*m*b-2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        i1 = [t1+c[0], m * t1 + b + c[1]]
        i2 = [t2+c[0], m * t2 + b + c[1]]

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i1[0] < p1[0]) and (i1[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i1[0] > p1[0]) and (i1[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i2[0] < p1[0]) and (i2[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i2[0] > p1[0]) and (i2[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")
Jorge Eduardo G
fuente
0

Aquí hay una solución escrita en golang. El método es similar a algunas otras respuestas publicadas aquí, pero no es lo mismo. Es fácil de implementar y ha sido probado. Aquí están los pasos:

  1. Traduzca las coordenadas para que el círculo esté en el origen.
  2. Exprese el segmento de línea como funciones parametrizadas de t para las coordenadas x e y. Si t es 0, los valores de la función son un punto final del segmento, y si t es 1, los valores de la función son el otro punto final.
  3. Resuelva, si es posible, la ecuación cuadrática resultante de los valores de restricción de t que producen coordenadas x, y con distancias desde el origen igual al radio del círculo.
  4. Deseche las soluciones donde t es <0 o> 1 (<= 0 o> = 1 para un segmento abierto). Esos puntos no están contenidos en el segmento.
  5. Volver a traducir a coordenadas originales.

Los valores para A, B y C para la cuadrática se derivan aquí, donde (n-et) y (m-dt) son las ecuaciones para las coordenadas x e y de la línea, respectivamente. r es el radio del círculo.

(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

Por lo tanto, A = ee + dd, B = - 2 (en + dm) y 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, atraviesa el otro y se extiende hasta el infinito, solo probando si t> 0 o t <1 pero no ambos.

Steller
fuente
0

Solo necesitaba eso, así que se me ocurrió esta solución. El idioma es maxscript, pero debe traducirse fácilmente a cualquier otro idioma. sideA, sideB y CircleRadius son escalares, el resto de las variables son puntos como [x, y, z]. Supongo que z = 0 para resolver en el plano 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 v p)*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)
)
martín
fuente
0

Solución en python, basada en @Joe Skeen

def check_line_segment_circle_intersection(line, point, radious):
    """ Checks whether a point intersects with a line defined by two points.

    A `point` is list with two values: [2, 3]

    A `line` is list with two points: [point1, point2]

    """
    line_distance = distance(line[0], line[1])
    distance_start_to_point = distance(line[0], point)
    distance_end_to_point = distance(line[1], point)

    if (distance_start_to_point <= radious or distance_end_to_point <= radious):
        return True

    # angle between line and point with law of cosines
    numerator = (math.pow(distance_start_to_point, 2)
                 + math.pow(line_distance, 2)
                 - math.pow(distance_end_to_point, 2))
    denominator = 2 * distance_start_to_point * line_distance
    ratio = numerator / denominator
    ratio = ratio if ratio <= 1 else 1  # To account for float errors
    ratio = ratio if ratio >= -1 else -1  # To account for float errors
    angle = math.acos(ratio)

    # distance from the point to the line with sin projection
    distance_line_to_point = math.sin(angle) * distance_start_to_point

    if distance_line_to_point <= radious:
        point_projection_in_line = math.cos(angle) * distance_start_to_point
        # Intersection occurs whent the point projection in the line is less
        # than the line distance and positive
        return point_projection_in_line <= line_distance and point_projection_in_line >= 0
    return False

def distance(point1, point2):
    return math.sqrt(
        math.pow(point1[1] - point2[1], 2) +
        math.pow(point1[0] - point2[0], 2)
    )
Ian Douglas
fuente
0
Function lineCircleCollision(p1,p2,c,r,precision){
Let dx = (p2.x-p1.x)/precision
Let dy = (p2.y-p1.y)/precision
Let collision=false
For(let i = 0;i<precision:i++){
If(Math.sqrt((p1.x+dx*i-c.x)**2+(p1.y+dy*i-c.y)**2).<r {
Collision=true
}
}

Puede tomar X puntos espaciados uniformemente de la línea y si alguno está dentro del círculo, hay una colisión

Matthew Perlman
fuente