Cálculo de intersecciones entre segmentos de línea

Hay muchas preguntas sobre intersecciones entre segmentos de línea aquí en stackowerflow y ¡aquí hay una más! Lo siento, pero necesito ayuda para entender cómo calcular intersecciones. He leído varias de las preguntas aquí y he visto varios ejemplos en otros sitios web, pero todavía estoy confundido y no lo entiendo. No me gusta copiar y pegar código sin cómo funcionan las cosas.

Hasta ahora sé que voy a comparar los puntos de cada segmento de línea como Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. ¿Podría alguien explicarme qué voy a calcular, cuál sería el resultado del cálculo si hay una intersección?

Este es uno de los códigos de ejemplo que he visto. Supongo que no necesito el punto de intersección, solo para saber si las líneas se cruzan o no.

public static Point lineIntersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1); if (denom == 0.0) { // Lines are parallel. return null; } double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3))/denom; double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3))/denom; if (ua >= 0.0f && ua = 0.0f && ub <= 1.0f) { // Get the intersection point. return new Point((int) (x1 + ua*(x2 - x1)), (int) (y1 + ua*(y2 - y1))); } return null; } 

¿También necesito calcular algún valor de mediana como en este ejemplo de código?

 For lines through points (x0,y0) and (x1,y1), let xm = (x0+x1)/2, ym = (y0+y1)/2 (median of line segment). Then a = (y1-y0) and b = (x0-x1). If you evaluate c = a(x-xm)+b(y-ym), c=0 for (x,y) on the line, and the sign(c) tells you which side a point is on 

La primera parte del código que muestra se basa en el producto cruzado vectorial, que se ha explicado aquí. ¿Cómo se detecta dónde se cruzan dos segmentos de línea? en un gran detalle.

OMI, una forma más fácil de entenderlo es mediante la resolución de un sistema de ecuaciones. En primer lugar, observe las líneas en general y luego corte segmentos de ellas. A continuación, uso anotaciones para segmentos determinados ((x1, x2), (y1, y2)) y ((x3, x4), (y3, y4)) .

  1. Compruebe si alguna de las líneas es vertical ( x1 == x2 o x3 == x4 ).

    a. Si ambos son verticales y x1 != x3 , entonces no hay intersección.

    segundo. Si ambos son verticales y x1 == x3 , verifique si (y1, y2) y (y3, y4) superponen.

    do. Si solo uno es vertical (digamos, primero), construya la ecuación de la segunda línea (como se describe a continuación), encuentre el punto donde se cruzan dos líneas (sustituyendo x1 en la ecuación de la segunda línea) y verifique si este punto está dentro de ambos segmentos (similar al paso 5).

    re. Si no, proceda.

  2. Usa las coordenadas de los puntos para construir ecuaciones de líneas en la forma y = a*x + b (como aquí ).

     a1 = (y2-y1)/(x2-x1) b1 = y1 - a1*x1 a2 = (y4-y3)/(x4-x3) b2 = y3 - a2*x3 
  3. Verifique si las líneas son paralelas (misma pendiente a ). En caso afirmativo, verifique si tienen el mismo intercepto b . En caso afirmativo, verifique si los segmentos 1D (x1, x2) y (x3, x4) superponen. En caso afirmativo, sus segmentos se superponen. El caso en que las líneas son paralelas puede ser ambiguo. Si se superponen, puede considerarlo como una intersección (incluso puede ser un punto si sus extremos se tocan), o no. Nota: si está trabajando con flotadores sería un poco más complicado, creo que querría ignorar esto. En caso de que solo tenga números enteros, verifique si a1 = a2 es equivalente a:

     if((y2-y1)*(x4-x3) == (x2-x1)*(y4-y3)) 
  4. Si las líneas no son paralelas El punto de intersección es equivalente a una solución de un sistema de ecuaciones que representa las dos líneas. Realmente, y = a1*x + b1 y = a2*x + b2 cruzan básicamente significa que ambas ecuaciones se mantienen. Resuelve este sistema igualando los dos lados derechos y te dará el punto de intersección. De hecho, solo necesita x coordenada de la intersección (dibuje y verá por qué):

     x0 = -(b1-b2)/(a1-a2) 
  5. El último paso es verificar si el punto de intersección x0 encuentra dentro de ambos segmentos. Es decir, min(x1, x2) < x0 < max(x1, x2) y min(x3, x4) < x0 < max(x3, x4) . Si es así, ¡sus líneas se cruzan!

 public void fixData() { slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX()); yInt = p1.getY() - slope * p1.getX(); xInt = (-yInt) / slope; } 

La respuesta es realmente @ sashkello y creo que es más intuitiva y fácil de explicar que la implementación del vector. Particularmente cuando se agrega este tipo de código a una base de código.

Lo advertiré diciendo que puedes utilizar el método de ayuda Line2D de Java.

 Line2D.linesIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) 

El único inconveniente es que requiere que considere los segmentos que se intersectan, incluso cuando solo se están tocando (en ambos puntos finales y la línea misma).

Por ejemplo, las líneas siguientes se consideran intersectadas porque comparten el punto (1,1).

 L1 = [(0,0),(1,1)] L2 = [(1,1),(2,3)] 

Si eso es un problema, puede agregar 4 controles para ver si los puntos son iguales.

Si le preocupa que un punto caiga en un punto dentro de la línea, eso requiere un poco más de trabajo y quizás sea mejor que lo implemente usted mismo para que pueda hacer las comprobaciones en el algoritmo mismo.

Si ninguno de esos casos Line2D.linesIntersect lo afecta, entonces Line2D.linesIntersect es para usted. 🙂