algorithm - ¿Cómo comprobar si el segmento de línea se interseca con un rectángulo?

language-agnostic geometry

Question

Si tiene 2 puntos, (x1, y1) y (x2, y2), que representan dos esquinas opuestas de un rectángulo, y 2 otros puntos, (x3, y3) y (x4, y4), que representan 2 puntos finales de un segmento de línea, ¿cómo puedes verificar si el segmento de línea se interseca con el rectángulo?

(El segmento de línea es solo el segmento contenido entre los puntos finales dados. No es una línea de longitud infinita definida por esos dos puntos).

Answer 1

Obtenga el producto puntual de los 4 vértices (las esquinas del rectángulo) con el vector de dirección del segmento de línea. Si los 4 tienen valores del mismo signo, entonces todos los vértices se encuentran en el mismo lado de la línea (no en el segmento de línea, sino en la línea infinita) y, por lo tanto, la línea no se interseca con el rectángulo. Este enfoque solo es viable para la detección de intersecciones 2D. Esto se puede usar para filtrar a través de la mayoría de ellos rápidamente (usando solo multiplicaciones y adiciones). Tendrá que hacer comprobaciones adicionales para los segmentos de línea en lugar de las líneas.

Answer 2

Para comprender cómo derivar la fórmula para probar si un segmento de línea se interseca con un rectángulo, es importante recordar las propiedades del producto vectorial de puntos .

Representa el segmento de línea como un vector unitario y una distancia entre el punto de inicio y el origen del segmento de línea. Aquí hay un código C # para calcular eso a partir de las variables a_ptStart y a_ptEnd , usando un Vector :

Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y);
double dLengthLine = vecLine.Length;
vecLine /= dLengthLine;
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y));

También deberá calcular el vector perpendicular, y su distancia desde el origen, para el segmento de línea. Girar un vector unitario en 90 ° es easy .

Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X);
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y));

Suponiendo que las cuatro esquinas del rectángulo están en las variables Vector denominadas vecRect1 , vecRect2 , vecRect3 y vecRect4 , calcule la distance entre el segmento de línea y las cuatro esquinas del rectángulo delimitador del objetivo:

double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine;
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine;
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine;
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine;
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2,
    Math.Min(dPerpLineDist3, dPerpLineDist4)));
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2,
    Math.Max(dPerpLineDist3, dPerpLineDist4)));

Si todas las distancias son positivas, o todas las distancias son negativas, entonces el rectángulo está en un lado de la línea o en el otro, por lo que no hay intersección. (Se considera que los rectángulos de extensión cero no se intersecan con ningún segmento de línea).

if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0
        || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0)
    /* no intersection */;

A continuación, proyecte las cuatro esquinas del rectángulo delimitador del objetivo en el segmento de línea. Esto nos da la distancia entre el origen de la línea y la proyección de la esquina del rectángulo en esa línea.

double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine;
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine;
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine;
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine;
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2,
    Math.Min(dDistLine3, dDistLine4)));
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2,
    Math.Max(dDistLine3, dDistLine4)));

Si los puntos del rectángulo no caen dentro de la extensión del segmento de línea, entonces no hay intersección.

if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine)
    /* no intersection */;

Creo que eso es suficiente.

Answer 3

Una opción muy simple sería usar un algoritmo estándar para verificar si dos segmentos de línea se intersecan para verificar si los segmentos de línea intersectan cualquiera de los cuatro segmentos de línea que forman las esquinas de la caja. Es computacionalmente muy eficiente verificar si dos segmentos de línea se intersecan, así que espero que esto pueda ejecutarse muy rápidamente.

¡Espero que esto ayude!