Encontrar el punto de intersección de dos líneas (y segmentos de línea)

Introducción

Muy a menudo, al desarrollar juegos, es necesario encontrar el punto de intersección de líneas rectas, segmentos, rayos, etc. Cómo implementar esto de la manera más simple posible, en este artículo.

Los métodos populares y su crítica

Quizás muchos recuerden una forma del álgebra escolar: hacer ecuaciones de dos líneas rectas, equiparar sus lados derechos, encontrar x y sustituirla en la ecuación de una línea recta para encontrar y ( más detalles aquí ).



Sin embargo, este método se vuelve bastante engorroso a la hora de escribir código (quizás por eso estás leyendo este artículo ahora), además, no es universal: si una de las rectas es paralela al eje Y, obtendremos una división por error cero al calcular la pendiente, y tenemos que registre un código para este caso; Si dos líneas son paralelas, también debe modificar el procesamiento de este caso. Este código se vuelve largo y feo.



En busca de una solución más elegante a este problema, me encontré con algunas formas muy interesantes basadas en la multiplicación de vectores (habr.com/ru/post/267037 ) y rayos castinging ( ru.wikipedia.org/wiki/Ray_casting#Concept ). Pero en mi opinión, son innecesariamente complejos computacionalmente. Por tanto, presento a su atención (y crítica) mi método.

Mi manera

Tarea

Se dan las coordenadas de dos segmentos. Debe averiguar si los segmentos se cruzan y, de ser así, en qué punto. Para ello, escribiremos una función.

Decisión

Leyenda para evitar malentendidos: a - vector a, a (y) - proyección del vector a sobre el eje Y, a {x1, y1} - vector a, especificado por las coordenadas x1, y1.



Representemos nuestros segmentos en forma de dos vectores: a {x2-x1; y2-y1} y b {x3-x4; y3-x4}. Tenga en cuenta que el vector b está en la dirección opuesta a la esperada. Introduzcamos un vector c {x3-x1; y3-y1}. Tenga en cuenta que a * k + b * n = c, donde k, n son algunos coeficientes. Así, obtenemos un sistema de ecuaciones:



a (x) * k + b (x) * n = c (x)

a (y) * k + b (y) * n = c (y)

Nuestra tarea se reduce a encontrar estos coeficientes (a decir verdad, basta con encontrar solo uno de ellos).



Propongo multiplicar ambos lados de la ecuación inferior por q = -a (x) / a (y). Entonces, después de sumar dos ecuaciones, inmediatamente nos deshacemos de k. Encontrar n se reduce a resolver una ecuación lineal ordinaria. Es importante tener en cuenta que n puede no tener una solución.



El lector atento notará que cuando a (y) = 0, obtenemos un error. Escribamos la ramificación en la etapa de encontrar a (y). Este caso es aún más simple, porque inmediatamente obtenemos una ecuación con una incógnita.



Recomiendo intentar imprimir n usted mismo, para que quede más claro de qué proviene el código a continuación.



Sabiendo n, puedes encontrar el punto de intersección, para esto restamos el vector b * n de la coordenada del punto (x3, y3)

Poniendo todo junto

float dot[2];  //  

bool cross(float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4) {
    float n;
    if (y2 - y1 != 0) {  // a(y)
        float q = (x2 - x1) / (y1 - y2);   
        float sn = (x3 - x4) + (y3 - y4) * q; if (!sn) { return 0; }  // c(x) + c(y)*q
        float fn = (x3 - x1) + (y3 - y1) * q;   // b(x) + b(y)*q
        n = fn / sn;
    }
    else {
        if (!(y3 - y4)) { return 0; }  // b(y)
        n = (y3 - y1) / (y3 - y4);   // c(y)/b(y)
    }
    dot[0] = x3 + (x4 - x3) * n;  // x3 + (-b(x))*n
    dot[1] = y3 + (y4 - y3) * n;  // y3 +(-b(y))*n
    return 1;
}

Esta función toma las coordenadas de los vértices y devuelve el valor 1 si las líneas rectas de los segmentos (es decir, las líneas rectas) se cruzan, de lo contrario 0. Si necesita las coordenadas de los vértices, puede tomarlas de la matriz de puntos [].



Importante: al introducir dos líneas coincidentes, el algoritmo no muestra ninguna intersección. El algoritmo encuentra el punto de intersección de las líneas en las que se encuentran los segmentos de línea, por lo que el punto puede estar fuera del segmento (que deberá verificar en su código).



Apliquemos la función:

int main() {
    if (cross(1,1,7,2, 7,3,5,6)) {
        std::cout << dot[0] << " " << dot[1] << std::endl;
    }
    else {
        std::cout<<"Not cross!"<<std::endl;
    }
    return 0;
}

Epílogo

Aunque no encontré este método en el proceso de buscar en Google mi problema y desarrollar el algoritmo yo mismo, no pretendo ser completamente original (y correcto). ¡Bienvenidos a los comentarios!