algorithm - Algoritmo para detectar la intersección de dos rectángulos

math graphics

Question

Estoy buscando un algoritmo para detectar si dos rectángulos se cruzan (uno en un ángulo arbitrario, el otro con solo líneas verticales / horizontales).

Probando si una esquina de uno está en la otra ALMOST funciona. Falla si los rectángulos forman una forma de cruz.

Parece una buena idea evitar el uso de pendientes en las líneas, lo que requeriría casos especiales para líneas verticales.

Answer 1

¿O me falta algo más por qué hacer esto tan complicado?

if (x1, y1) y (X1, Y1) son las esquinas de los rectángulos, entonces para encontrar la intersección do:

    xIntersect = false;
    yIntersect = false;
    if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
    if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
    if (xIntersect && yIntersect) {alert("Intersect");}

Answer 2

Aquí hay una implementación de matlab de la respuesta aceptada:

function olap_flag = ol(A,B,sub)

%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order

if nargin == 2
  olap_flag = ol(A,B,1) && ol(B,A,1);
  return;
end

urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl'' - repmat(s,[1 4]);

olap_flag = ~any(max(sdiff)<0);

Answer 3

Básicamente mira la siguiente imagen:

http://www.gamasutra.com/features/20000330/bobic_08.gif

Si las dos cajas colisionan, las líneas A y B se superpondrán.

Tenga en cuenta que esto tendrá que hacerse tanto en el eje X como en el eje Y, y ambos deben superponerse para que los rectángulos colisionen.

Hay un buen artículo en gamasutra.com que responde a la pregunta (la imagen es del artículo). Hice un algoritmo similar hace 5 años y tengo que encontrar mi fragmento de código para publicarlo aquí más tarde

Enmienda : El teorema del eje separador establece que dos formas convexas no se superponen si existe un eje separador (es decir, uno donde las proyecciones, tal como se muestran , no se superponen). Entonces, "existe un eje de separación" => "Sin superposición". Esto no es una implicación doble, así que no puedes concluir lo contrario.

Answer 4

Bueno, el método de fuerza bruta es caminar por los bordes del rectángulo horizontal y verificar cada punto a lo largo del borde para ver si cae o en el otro rectángulo.

La respuesta matemática es formar ecuaciones que describan cada borde de ambos rectángulos. Ahora puede simplemente encontrar si alguna de las cuatro líneas del rectángulo A se cruzan con alguna de las líneas del rectángulo B, que debería ser un solucionador de ecuaciones lineal simple (rápido).

-Adán

Answer 5

El método estándar sería hacer la prueba del eje de separación (hacer una búsqueda en google sobre eso).

En breve:

• Dos objetos no se cruzan si puede encontrar una línea que separe los dos objetos. por ejemplo, los objetos / todos los puntos de un objeto están en lados diferentes de la línea.

Lo divertido es que es suficiente con verificar todos los bordes de los dos rectángulos. Si los rectángulos no se superponen uno de los bordes será el eje de separación.

En 2D puede hacer esto sin usar pendientes. Un borde se define simplemente como la diferencia entre dos vértices, por ejemplo

  edge = v(n) - v(n-1)

Puede obtener una perpendicular a esto girándola 90 °. En 2D esto es fácil como:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

Entonces no hay trigonometría ni pendientes involucradas. Tampoco se requiere normalizar el vector a la longitud de la unidad.

Si quiere probar si un punto está en uno u otro lado de la línea, puede usar el producto punto. el letrero te dirá de qué lado estás:

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it''s on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

Ahora pruebe todos los puntos del rectángulo A contra los bordes del rectángulo B y viceversa. Si encuentra un borde de separación, los objetos no se cruzan (siempre que todos los demás puntos en B estén en el otro lado del borde que se está probando, vea el dibujo a continuación). Si no encuentra un borde de separación, los rectángulos se cruzan o un rectángulo está contenido en el otro.

La prueba funciona con cualquier polígono convexo por cierto.

Enmienda: Para identificar un borde de separación, no es suficiente probar todos los puntos de un rectángulo contra cada borde del otro. El candidato E (debajo) se identificaría como un borde separador, ya que todos los puntos en A están en el mismo semiplano de E. Sin embargo, no es un borde de separación porque los vértices Vb1 y Vb2 de B también están en ese medio plano. Solo hubiera sido un margen de separación si ese no hubiera sido el caso http://www.iassess.com/collision.png

Answer 6

En Cocoa, podría detectar fácilmente si la recta de selección seleccionada intersecta el marco rectificado de NSView girado. Ni siquiera necesita calcular polígonos, normales y similares. Simplemente agregue estos métodos a su subclase NSView. Por ejemplo, el usuario selecciona un área en la supervista de NSView y luego llama al método DoesThisRectSelectMe que pasa la selección seleccionada. La API convertRect: hará ese trabajo. El mismo truco funciona cuando haces clic en NSView para seleccionarlo. En ese caso, simplemente anule el método hitTest como se muestra a continuación. API convertPoint: hará ese trabajo ;-)

- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
    NSRect localArea = [self convertRect:selectedArea fromView:self.superview];

    return NSIntersectsRect(localArea, self.bounds);
}


- (NSView *)hitTest:(NSPoint)aPoint
{
    NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
    return NSPointInRect(localPoint, self.bounds) ? self : nil;
}

Answer 7

Este es el método convencional, ir línea por línea y verificar si las líneas se cruzan. Este es el código en MATLAB.

C1 = [0, 0];    % Centre of rectangle 1 (x,y)
C2 = [1, 1];    % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];

R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;

plot(R1(:,1),R1(:,2),''r'')
hold on
plot(R2(:,1),R2(:,2),''b'')


%% lines of Rectangles 
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
    line1 = reshape(L1(i,:),2,2) ;
    for j = 1:4
        line2 = reshape(L2(j,:),2,2) ;
        point = InterX(line1,line2) ;
        if ~isempty(point)
            count = count+1 ;
            P(:,count) = point ;
        end
    end
end
%%
if ~isempty(P)
    fprintf(''Given rectangles intersect at %d points:/n'',size(P,2))
    plot(P(1,:),P(2,:),''*k'')
end

la función InterX se puede descargar desde: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

Answer 8

Esto es lo que creo que se encargará de todos los casos posibles. Haz las siguientes pruebas.

1. Verifique que cualquiera de los vértices del rectángulo 1 resida dentro del rectángulo 2 y viceversa. Cada vez que encuentre un vértice que reside dentro del otro rectángulo, puede concluir que se cruzan y detienen la búsqueda. Esto cuidará de un rectángulo que resida completamente dentro del otro.
2. Si la prueba anterior no es concluyente, encuentre los puntos de intersección de cada línea de 1 rectángulo con cada línea del otro rectángulo. Una vez que se encuentra un punto de intersección, compruebe si se encuentra dentro del rectángulo imaginario creado por los 4 puntos correspondientes. Cuando se llega a tal punto, concluye que se cruzan y detienen la búsqueda.

Si las 2 pruebas anteriores devuelven false, estos 2 rectángulos no se superponen.

Answer 9

Esto es lo que haría, para la versión 3D de este problema:

Modele los 2 rectángulos como planos descritos por la ecuación P1 y P2, luego escriba P1 = P2 y derive de eso la línea de ecuación de intersección, que no existirá si los planos son paralelos (sin intersección), o están en el mismo plano, en cuyo caso obtienes 0 = 0. En ese caso, necesitará emplear un algoritmo de intersección de rectángulo 2D.

Entonces vería si esa línea, que está en el plano de ambos rectángulos, pasa a través de ambos rectángulos. Si lo hace, entonces tienes una intersección de 2 rectángulos, de lo contrario no lo harás (o no deberías, podría haber perdido un caso de esquina en mi cabeza).

Para encontrar si una línea pasa a través de un rectángulo en el mismo plano, encontraría los 2 puntos de intersección de la línea y los lados del rectángulo (modelándolos usando ecuaciones de línea), y luego me aseguraré de que los puntos de intersección estén en distancia.

Esas son las descripciones matemáticas, desafortunadamente no tengo un código para hacer lo anterior.

Answer 10

La respuesta de m_pGladiator es correcta y yo prefiero hacerlo. La prueba del eje separador es el método más simple y estándar para detectar la superposición de rectángulo. Una línea para la cual los intervalos de proyección no se superponen llamamos un eje de separación . La solución de Nils Pipenbrinck es demasiado general. Utiliza el producto de puntos para verificar si una forma está totalmente en un lado del borde del otro. Esta solución en realidad podría inducir a polígonos convexos n-edge. Sin embargo, no está optimizado para dos rectángulos.

el punto crítico de la respuesta de m_pGladiator es que debemos verificar la proyección de dos rectángulos en ambos ejes (xey). Si dos proyecciones se superponen, entonces podríamos decir que estos dos rectángulos están superpuestos. Entonces los comentarios de arriba a la respuesta de m_pGladiator son incorrectos.

para la situación simple, si dos rectángulos no se rotan, presentamos un rectángulo con estructura:

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

llamamos rectángulo A, B con rectA, rectB.

    if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
    then
        // A and B collide
    end if

si cualquiera de los dos rectángulos se rotan, puede necesitar algunos esfuerzos para determinar la proyección de ellos en los ejes xey. Defina struct RotatedRect de la siguiente manera:

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

la diferencia es cómo el ancho ''ahora es un poco diferente: widthA'' para rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle) widthB ''para rectB: Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)

    if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA'' + widthB'') / 2) 
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA'' + heightB'') / 2))
    then
        // A and B collide
    end if

Podría referirse a un GDC (Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt

Answer 11

Lo implementé así:

bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
    float Axmin = boundsA.origin.x;
    float Axmax = Axmin + boundsA.size.width;
    float Aymin = boundsA.origin.y;
    float Aymax = Aymin + boundsA.size.height;

    float Bxmin = boundsB.origin.x;
    float Bxmax = Bxmin + boundsB.size.width;
    float Bymin = boundsB.origin.y;
    float Bymax = Bymin + boundsB.size.height;

    // find location of B corners in A space
    float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
    float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);

    float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
    float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);

    float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
    float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);

    float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
    float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);

    if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
        return false;
    if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
        return false;
    if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
        return false;
    if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
        return false;

    float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
    float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
    float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);

    // find location of A corners in B space
    float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
    float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;

    float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
    float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;

    float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
    float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;

    float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
    float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;

    if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
        return false;
    if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
        return false;
    if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
        return false;
    if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
        return false;

    return true;
}

La matriz mB es cualquier matriz de transformación afín que convierte puntos en el espacio B a puntos en el espacio A. Esto incluye rotación simple y traslación, rotación más escala, y warps afines completos, pero no warps en perspectiva.

Puede no ser tan óptimo como sea posible. La velocidad no era una gran preocupación. Sin embargo, parece funcionar bien para mí.

Answer 12

Otra forma de hacer la prueba que es ligeramente más rápida que usar la prueba del eje separador, es usar el algoritmo de números de cuerda (solo en cuadrantes, no suma de ángulos que es terriblemente lento) en cada vértice de cualquier rectángulo (elegido arbitrariamente). Si alguno de los vértices tiene un número de devanado distinto de cero, los dos rectángulos se superponen.

Este algoritmo es algo más prolijo que la prueba del eje de separación, pero es más rápido porque solo requiere una prueba de semiplano si los bordes están cruzando dos cuadrantes (a diferencia de hasta 32 pruebas con el método del eje de separación)

El algoritmo tiene la ventaja adicional de que puede usarse para probar la superposición de cualquier polígono (convexo o cóncavo). Hasta donde yo sé, el algoritmo solo funciona en el espacio 2D.

Answer 13

Puede encontrar la intersección de cada lado del rectángulo en ángulo con cada lado del eje alineado. Haz esto encontrando la ecuación de la línea infinita en la que cada lado se encuentra (es decir, v1 + t (v2-v1) y v''1 + t ''(v''2-v''1) básicamente), encontrando el punto en el cual el las líneas se encuentran resolviendo para t cuando esas dos ecuaciones son iguales (si son paralelas, puedes probar eso) y luego probando si ese punto se encuentra en el segmento de línea entre los dos vértices, es decir, si es cierto que 0 <= t <= 1 y 0 <= t ''<= 1.

Sin embargo, esto no cubre el caso cuando un rectángulo cubre completamente al otro. Eso puede cubrir probando si los cuatro puntos de cualquier rectángulo se encuentran dentro del otro rectángulo.

Answer 14

Si está utilizando Java, todas las implementaciones de la interfaz Shape tienen un método intersects que toma un rectángulo.

Answer 15

Tengo un método simplier propio, si tenemos 2 rectángulos:

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

Se superponen si y solo si:

Superposición = (max_x1> min_x2) y (max_x2> min_x1) y (max_y1> min_y2) y (max_y2> min_y1)

También puede hacerlo para cuadros 3D, en realidad funciona para cualquier cantidad de dimensiones.

Answer 16

Una solución es usar algo llamado polígono No Fit. Este polígono se calcula a partir de los dos polígonos (conceptualmente deslizando uno alrededor del otro) y define el área para la cual los polígonos se superponen dado su desplazamiento relativo. Una vez que tiene este NFP, simplemente tiene que hacer una prueba de inclusión con un punto dado por el desplazamiento relativo de los dos polígonos. Esta prueba de inclusión es rápida y fácil, pero primero debe crear la NFP.

Haga una búsqueda de polígono No apto en la web y vea si puede encontrar un algoritmo para polígonos convexos (se vuelve MUCHO más complejo si tiene polígonos cóncavos). Si no puede encontrar nada, envíeme un correo electrónico a howard dot J dot may gmail dot com

Answer 17

Verifique si alguna de las líneas de un rectángulo se cruza con alguna de las líneas de la otra. La intersección del segmento de línea ingenua es fácil de codificar.

Si necesita más velocidad, existen algoritmos avanzados para la intersección del segmento de línea (línea de barrido). Ver http://en.wikipedia.org/wiki/Line_segment_intersection