c++ - puntos - punto en comun entre dos rectas

Obtener los puntos de intersección de 2 rectángulos

Question

Digamos que tenemos dos rectángulos, definidos con sus esquinas inferior izquierda y superior derecha. Por ejemplo: rect1 (x1, y1) (x2, y2) y rect2 (x3, y3) (x4, y4) . Estoy tratando de encontrar las coordenadas (abajo a la izquierda y arriba a la derecha) del rectángulo intersectado.

Cualquier idea, algoritmo, pseudo código, sería muy apreciado.

pd encontré preguntas similares pero solo verifican si 2 rectángulos se intersecan.

Answer 1

Digamos que una caja tiene un radio X y un radio Y (sé que no lo tiene, pero este término es útil aquí).

Usted tendrá:

rect1_x_radius = (x2-x1)/2
rect1_y_radius = (y2-y1)/2

y

rect2_x_radius = (x4-x3)/2
rect2_y_radius = (y4-y3)/2

Ahora, si los puntos medios rectos están más alejados que la suma de sus radios en la dirección apropiada, no colisionan. De lo contrario lo hacen - esta sugerencia debería ser suficiente.

Ahora deberías poder terminar tu tarea.

ACTUALIZAR:

Bien, resolvámoslo para 1D. Más tarde lo resolveremos para 2D. Mira esta pieza de ... arte ;-)

Ves 2 segmentos - ahora algunos cálculos:

rA = (maxA-minA) / 2
rB = (maxB-minB) / 2

midA = minA + rA
midB = minB + rB

mid_dist = |midA - midB|

Ahora, ¿cómo comprobar si se produce una colisión? Como dije, si la suma de ''radios'' es menor que la distancia de los segmentos, no hay colisión:

if ( mid_dist > fabs(rA+rB) )
{
    // no intersection
}
else
{
    // segments intersect
}

Ahora es su trabajo calcular la intersección / parte común en 1D y 2D. Depende de usted ahora (o puede leer la respuesta de Andrey).

Aquí está la misma situación pero en 2D - dos situaciones 1D:

Answer 2

Para buscar una intersección, tendrá que hacer una comparación simple de los puntos:

Entonces, como podemos ver en la imagen si x3, y3 es mayor o igual a x1, y1 y menor o igual a x2, y2, entonces está dentro del primer rectángulo, de manera similar, deberá verificar si x4, y4 cae dentro de la rango de x1, y1 a x2, y2 también.

si ambas condiciones resultan ser ciertas, entonces puede estar seguro de que el segundo rectángulo está totalmente abarcado por el primero.

También tendrá que revisar al revés, si encuentra cuál es el interior que es importante para usted.

También debe alinear los rectángulos con el eje, de lo contrario esto no funcionará de manera confiable.

Déjeme saber si necesita más detalles, aunque creo que una búsqueda rápida en Google descubrirá muchos más detalles para usted muy fácilmente, pero hágamelo saber y puedo hacer un tutorial de colisión de rectángulo si lo desea.

Con más detalle:

Para averiguar si los rectángulos tienen alguna intersección, puede verificar las coordenadas de sus puntos de definición, para nuestros propósitos usaremos las coordenadas de las esquinas superior izquierda e inferior derecha. Podemos utilizar una clase para que esto sea más fácil para nosotros, y para maximizar la facilidad de uso del código, podemos usar un Vector 2d y un 2d Point: 2dVectorPoint.h

#include <cmath>

class Vector2D
{
    public:
        float   x;
        float   y;

        Vector2D() {}    
        Vector2D(float inX, float inY)
        {
            x = inX;
            y = inY;
        }

        Vector2D& Set(float inX, float inY)
        {
            x = inX;
            y = inY;
            return (*this);
        }

        float& operator [](long k)        {            return ((&x)[k]);        }

        const float& operator [](long k) const        {            return ((&x)[k]);        }

        Vector2D& operator +=(const Vector2D& v)
        {
            x += v.x;
            y += v.y;
            return (*this);
        }

        Vector2D& operator -=(const Vector2D& v)
        {
            x -= v.x;
            y -= v.y;
            return (*this);
        }

        Vector2D& operator *=(float t)
        {
            x *= t;
            y *= t;
            return (*this);
        }

        Vector2D& operator /=(float t)
        {
            float f = 1.0F / t;
            x *= f;
            y *= f;
            return (*this);
        }

        Vector2D& operator &=(const Vector2D& v)
        {
            x *= v.x;
            y *= v.y;
            return (*this);
        }

        Vector2D operator -(void) const        {            return (Vector2D(-x, -y));        }

        Vector2D operator +(const Vector2D& v) const        {            return (Vector2D(x + v.x, y + v.y));        }

        Vector2D operator -(const Vector2D& v) const        {  return (Vector2D(x - v.x, y - v.y));        }

        Vector2D operator *(float t) const        {            return (Vector2D(x * t, y * t));        }

        Vector2D operator /(float t) const        {     float f = 1.0F / t; return (Vector2D(x * , y * f));        }

        float operator *(const Vector2D& v) const        {            return (x * v.x + y * v.y);        }

        Vector2D operator &(const Vector2D& v) const     {            return (Vector2D(x * v.x, y * v.y));        }

        bool operator ==(const Vector2D& v) const        {            return ((x == v.x) && (y == v.y));        }

        bool operator !=(const Vector2D& v) const        {            return ((x != v.x) || (y != v.y));        }

        Vector2D& Normalize(void)                        {            return (*this /= sqrtf(x * x + y * y));        }

        Vector2D& Rotate(float angle);
};


class Point2D : public Vector2D
{
    public:

        Point2D() {}

        Point2D(float r, float s) : Vector2D(r, s) {}

        Point2D& operator =(const Vector2D& v)
        {
            x = v.x;
            y = v.y;
            return (*this);
        }

        Point2D& operator *=(float t)
        {
            x *= t;
            y *= t;
            return (*this);
        }

        Point2D& operator /=(float t)
        {
            float f = 1.0F / t;
            x *= f;
            y *= f;
            return (*this);
        }

        Point2D operator -(void) const{            return (Point2D(-x, -y));        }

        Point2D operator +(const Vector2D& v) const        {            return (Point2D(x + v.x, y + v.y));        }

        Point2D operator -(const Vector2D& v) const        {            return (Point2D(x - v.x, y - v.y));        }

        Vector2D operator -(const Point2D& p) const        {            return (Vector2D(x - p.x, y - p.y));        }

        Point2D operator *(float t) const        {            return (Point2D(x * t, y * t));        }

        Point2D operator /(float t) const
        {
            float f = 1.0F / t;
            return (Point2D(x * f, y * f));
        }
};


inline Vector2D operator *(float t, const Vector2D& v){    return (Vector2D(t * v.x, t * v.y));}

inline Point2D operator *(float t, const Point2D& p){    return (Point2D(t * p.x, t * p.y));}

inline float Dot(const Vector2D& v1, const Vector2D& v2){    return (v1 * v2);}

inline float Magnitude(const Vector2D& v){    return (sqrtf(v.x * v.x + v.y * v.y));}

inline float InverseMag(const Vector2D& v){    return (1.0F / sqrtf(v.x * v.x + v.y * v.y));}

inline float SquaredMag(const Vector2D& v){    return (v.x * v.x + v.y * v.y);}

struct Origin2D_
{
    const Point2D& operator +(const Vector2D& v)    {        return (static_cast<const Point2D&>(v));    }

    Point2D operator -(const Vector2D& v)    {        return (Point2D(-v.x, -v.y));    }
};

2dVectorPoint.cpp

#include "2dVectorPoint.h"

Origin2D_ Origin2D;

Vector2D& Vector2D::Rotate(float angle)
{
    float s = sinf(angle);
    float c = cosf(angle);

    float nx = c * x - s * y;
    float ny = s * x + c * y;

    x = nx;
    y = ny;

    return (*this);
}
extern Origin2D_ Origin2D;

El código utilizado se adapta desde here para salvar mis dedos.

Luego podemos utilizar esto para comparar fácilmente: podemos definir el rectángulo 1 como teniendo P1 y P2 como límites y el rectángulo 2 como P3 y P4 como límites, dándonos la siguiente comparación:

if ( P2.y <= P3.y && P1.y >= P4.y && P2.x>= P3.x && P1.x <= P4.x )
{
    return true;
}

Esto devolverá un valor verdadero para cualquier instancia de intersección o para el rectángulo 1 que abarca el rectángulo 2 totalmente.

Para verificar solo las intersecciones, simplemente elimine la verificación de igualdad (quite todas las = fuera de la ecuación anterior), y solo revisará las intersecciones. Si tiene una intersección, entonces podría usar el álgebra lineal para evaluar las coordenadas exactas.

Answer 3

Puedes tratar con las direcciones x e y separado.

Supongamos que x1 <= x3 (el primer cuadro está al menos tan a la izquierda como el segundo). Entonces, hay una superposición si y solo si x1 <= x3 <= x2 .

De manera similar, suponga que y1 <= y3 (la primera casilla está al menos tan lejos como la segunda). Luego, hay una superposición si y solo si y1 <= y3 <= y2 .

Si hay superposición en ambas direcciones, hay una superposición de rectángulo. Puede encontrar las coordenadas ordenando las coordenadas x e y seleccionando las dos del medio.

En pseudocódigo:

if (((x1 <= x3 && x3 <= x2) || (x3 <= x1 && x1 <= x4)) // x-overlap
    &&
    ((y1 <= y3 && y3 <= y2) || (y3 <= y1 && y1 <= y4)) // y-overlap
) {
    int[] xs = {x1, x2, x3, x4};
    int[] ys = {y1, y2, y3, y4};
    sort(xs);
    sort(ys);

    // bottom-left: xs[1], ys[1]
    // top-right:   xs[2], ys[2]
}

Answer 4

Si los rectángulos de entrada están normalizados, es decir, ya sabe que x1 < x2 , y1 < y2 (y lo mismo para el segundo rectángulo), todo lo que necesita hacer es calcular

int x5 = max(x1, x3);
int y5 = max(y1, y3);
int x6 = min(x2, x4);
int y6 = min(y2, y4);

y te dará tu intersección como rectángulo (x5, y5)-(x6, y6) . Si los rectángulos originales no se intersecan, el resultado será un rectángulo "degenerado" (con x5 >= x6 y / o y5 >= y6 ), que puede verificar fácilmente.

PS Como es habitual, los pequeños detalles dependerán de si tiene que considerar tocar rectángulos como intersección.