java - Cálculo de intersecciones entre segmentos de línea.

android math

Question

¡Hay muchas preguntas sobre las intersecciones entre los segmentos de línea aquí en stackowerflow y aquí hay una más! Lo siento, pero necesito ayuda para entender cómo calcular las 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 Axe, Ay, Bx, By, Cx, Cy, Dx, Dy. ¿Podría alguien explicarme lo que voy a calcular, cuál sería el resultado del cálculo si hay una intersección?

Este es uno de los ejemplos de código que he visto. Supongo que no necesito el punto de intersección, solo para saber si las líneas se intersecan 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 <= 1.0f && ub >= 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

Answer 1

La primera parte del código que muestra se basa en el producto cruzado vectorial, que se ha explicado aquí. ¿Cómo se detecta la intersección de 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. Primero mira las líneas en general y luego corta los segmentos de ellas. A continuación uso notaciones para segmentos dados ((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, el primero), luego construya la ecuación de la segunda línea (como se describe a continuación), encuentre el punto donde se intersectan 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 here ).

   a1 = (y2-y1)/(x2-x1)
   b1 = y1 - a1*x1 
   a2 = (y4-y3)/(x4-x3)
   b2 = y3 - a2*x3

3. Compruebe si las líneas son paralelas (misma pendiente a ). Si es así, compruebe si tienen la misma intercepción b . En caso afirmativo, compruebe si los segmentos 1D (x1, x2) y (x3, x4) superponen. Si es así, sus segmentos se superponen. El caso cuando las líneas son paralelas puede ser ambiguo. Si se superponen, puedes 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 ignorarlo. En caso de que solo tenga enteros, compruebe 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 representan las dos líneas. Realmente, y = a1*x + b1 y y = a2*x + b2 intersecan 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 necesitas la coordenada x de la intersección (dibújala y verás 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 intersectan!

Answer 2

Realmente la respuesta de @ sashkello y me parece más intuitiva y fácil de explicar que la implementación vectorial. Particularmente cuando se agrega este tipo de código a una base de código.

Lo advertiré diciendo que puedes usar 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)

La única desventaja es que requiere que usted considere que los segmentos se intersecan incluso cuando solo están tocando (en ambos puntos finales y en la línea en sí).

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

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

Si ese 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 realizar las comprobaciones en el algoritmo mismo.

Si ninguno de esos casos de borde te afecta, entonces Line2D.linesIntersect es para ti. :)

Answer 3

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