¿Algoritmo para detectar la intersección de dos rectángulos?
https://stackoverflow.com/questions/115426
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy buscando un algoritmo para detectar si dos rectángulos se cruzan (uno en un ángulo arbitrario y el otro solo con líneas verticales/horizontales).
Probar si una esquina de uno está en el otro CASI funciona.Falla si los rectángulos tienen forma de cruz.
Parece una buena idea evitar el uso de pendientes de las líneas, lo que requeriría casos especiales para las líneas verticales.
Solución
El método estándar sería hacer el prueba del eje separador (haz una búsqueda en Google sobre eso).
En breve:
- Dos objetos no se cruzan si puedes encontrar una línea que los separe.p.ej.los objetos/todos los puntos de un objeto están en diferentes lados de la línea.
Lo divertido es que basta con comprobar 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 puedes hacer esto sin usar pendientes.Una arista se define simplemente como la diferencia entre dos vértices, p.
edge = v(n) - v(n-1)
Puedes obtener una perpendicular a esto girándolo 90°.En 2D esto es tan fácil como:
rotated.x = -unrotated.y
rotated.y = unrotated.x
Así que no hay trigonometría ni pendientes involucradas.Tampoco es necesario normalizar el vector a una unidad de longitud.
Si desea probar si un punto está en uno u otro lado de la línea, puede usar el producto escalar.el cartel te indicará 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 prueba 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; consulte el dibujo a continuación).Si no encuentra ningún borde de separación, los rectángulos se están intersectando o un rectángulo está contenido en el otro.
Por cierto, la prueba funciona con cualquier polígono convexo.
Enmienda: Para identificar un borde de separación, no basta con comparar todos los puntos de un rectángulo con cada borde del otro.La arista candidata E (abajo) se identificaría como tal como una arista de separación, ya que todos los puntos en A están en el mismo semiplano de E.Sin embargo, no es una arista de separación porque los vértices Vb1 y Vb2 de B también están en ese semiplano.Sólo habría sido una línea divisoria si no hubiera sido así.http://www.iassess.com/collision.png
Otros consejos
Básicamente mira la siguiente imagen:
Si los dos cuadros chocan, las líneas A y B se superpondrán.
Tenga en cuenta que esto deberá hacerse tanto en el eje X como en el 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 de separación establece que dos formas convexas no superponerse si existe un eje de separación (es decir,uno donde las proyecciones como se muestran no superposición).Entonces "Existe un eje de separación" => "Sin superposición".Esta no es una doble implicación, por lo que no se puede concluir lo contrario.
La respuesta de m_pGladiator es correcta y la prefiero.Prueba del eje separador Es el método más simple y estándar para detectar la superposición de rectángulos.Una línea para la cual los intervalos de proyección no se superponen la llamamos eje de separación.La solución de Nils Pipenbrinck es demasiado general.se utiliza producto escalar para comprobar si una forma está totalmente en un lado del borde de la otra.En realidad, esta solución podría inducir a polígonos convexos de n bordes.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 (x e y).Si dos proyecciones se superponen, entonces podríamos decir que estos dos rectángulos se superponen.Entonces los comentarios anteriores a la respuesta de m_pGladiator son incorrectos.
Para la situación simple, si no se giran dos rectángulos, presentamos un rectángulo con estructura:
struct Rect {
x, // the center in x axis
y, // the center in y axis
width,
height
}
llamamos al 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 se giran cualquiera de los dos rectángulos, puede necesitar algunos esfuerzos para determinar la proyección de ellos en las axisas X e Y.Defina la estructura RotatedRect de la siguiente manera:
struct RotatedRect : Rect {
double angle; // the rotating angle oriented to its center
}
la diferencia es que el ancho ahora es un poco diferente:anchoA' para rectA: Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle)anchoB' 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 PPT de la GDC (Conferencia de desarrollo de juegos 2007). www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt
En Cocoa, puede detectar fácilmente si el área seleccionada se cruza con el marco recto de su NSView girado.Ni siquiera necesitas 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, luego llama al método DoesThisRectSelectMe pasando el área seleccionada rect.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.La 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;
}
Verifique si alguna de las líneas de un rectángulo se cruza con alguna de las líneas del otro.La intersección ingenua de segmentos de línea es fácil de codificar.
Si necesita más velocidad, existen algoritmos avanzados para la intersección de segmentos de línea (línea de barrido).Ver http://en.wikipedia.org/wiki/Line_segment_intersection
Una solución es utilizar algo llamado Polígono sin ajuste.Este polígono se calcula a partir de los dos polígonos (conceptualmente deslizando uno alrededor del otro) y define el área en la que los polígonos se superponen dado su desplazamiento relativo.Una vez que tenga este NFP, simplemente tendrá 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 sencilla, pero primero debe crear el NFP.
Busque No Fit Polygon 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
Esto es lo que creo que se encargará de todos los casos posibles.Haz las siguientes pruebas.
- 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 se encuentre dentro del otro rectángulo, podrá concluir que se cruzan y detener la búsqueda.Esto se encargará de que un rectángulo quede completamente dentro del otro.
- 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, verifique si se encuentra dentro del rectángulo imaginario creado por los 4 puntos correspondientes.Cuando se encuentre un punto así, se concluirá que se cruzan y se detendrá la búsqueda.
Si las 2 pruebas anteriores devuelven falso, entonces estos 2 rectángulos no se superponen.
Si está utilizando Java, todas las implementaciones de la interfaz Shape tienen una se cruza método que toma un rectángulo.
Bueno, el método de fuerza bruta consiste en recorrer los bordes del rectángulo horizontal y comprobar cada punto a lo largo del borde para ver si cae sobre o dentro del otro rectángulo.
La respuesta matemática es formar ecuaciones que describan cada borde de ambos rectángulos.Ahora puedes simplemente encontrar si alguna de las cuatro líneas del rectángulo A se cruza con alguna de las líneas del rectángulo B, lo que debería ser un solucionador de ecuaciones lineales simple (rápido).
-Adán
Podrías encontrar la intersección de cada lado del rectángulo en ángulo con cada lado del alineado con el eje.Haga esto encontrando la ecuación de la línea infinita en la que se encuentra cada lado (es decir,v1 + t(v2-v1) y v'1 + t'(v'2-v'1) básicamente), encontrar el punto en el que se encuentran las líneas resolviendo t cuando esas dos ecuaciones son iguales (si son paralelo, puedes probar eso) y luego probar si ese punto se encuentra en el segmento de línea entre los dos vértices, es decir,¿Es cierto que 0 <= t <= 1 y 0 <= t' <= 1?
Sin embargo, esto no cubre el caso en el que un rectángulo cubre completamente al otro.Esto lo puedes cubrir probando si los cuatro puntos de cada rectángulo se encuentran dentro del otro rectángulo.
Esto es lo que yo haría, por el 3D versión de este problema:
Modele los 2 rectángulos como planos descritos por las ecuaciones P1 y P2, luego escriba P1=P2 y derive de ahí la ecuación de la línea 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ás emplear un algoritmo de intersección de rectángulos 2D.
Entonces vería si esa recta, que está en el plano de ambos rectángulos, pasa por ambos rectángulos.Si es así, entonces tienes una intersección de 2 rectángulos; de lo contrario, no la tienes (o no debería, es posible que me haya perdido un caso de esquina en mi cabeza).
Para saber si una línea pasa por 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 lineales), y luego me aseguraría de que los puntos de intersección estén dentro rango.
Esas son las descripciones matemáticas, desafortunadamente no tengo ningún código para hacer lo anterior.
Otra forma de realizar la prueba, que es ligeramente más rápida que utilizar la prueba del eje de separación, es utilizar el algoritmo de números de bobinado (solo en cuadrantes). no suma de ángulos que es terriblemente lenta) en cada vértice de cualquiera de los rectángulos (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 largo que la prueba del eje de separación, pero es más rápido porque solo requiere una prueba de medio plano si los bordes cruzan dos cuadrantes (a diferencia de hasta 32 pruebas usando 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 sólo funciona en un espacio 2D.
O me falta algo más, ¿por qué hacer esto tan complicado?
Si (x1,y1) y (X1,Y1) son esquinas de los rectángulos, entonces para encontrar la intersección haga:
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");}
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 en puntos en el espacio A.Esto incluye rotación y traslación simples, rotación más escalado y deformaciones afines completas, pero no deformaciones en perspectiva.
Puede que no sea lo más óptimo posible.La velocidad no era una gran preocupación.Sin embargo, parece funcionar bien para mí.
Aquí hay una implementación en 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);
Este es el método convencional, vaya línea por línea y verifique 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
Tengo un método propio más simple, si tenemos 2 rectángulos:
R1 = (mín_x1, máx_x1, mín_y1, máx_y1)
R2 = (mín_x2, máx_x2, mín_y2, máx_y2)
Se superponen si y sólo si:
Superposición = (max_x1 > min_x2) y (max_x2 > min_x1) y (max_y1 > min_y2) y (max_y2 > min_y1)
También puedes hacerlo para cajas 3D; de hecho, funciona para cualquier número de dimensiones.
Ya se ha dicho suficiente en otras respuestas, así que simplemente agregaré un pseudocódigo de una sola línea:
!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
