jueves, 4 de febrero de 2010

Intersección de rectángulos

Este es un artículo un tanto técnico que intenta explicar una idea muy simple que tuve hace años, cuando hacía pinitos programando como aficionado juegos en entornos arcaicos.

La intención es calcular de forma eficiente si dos rectángulos se tocan, algo que sirve para la detección de colisiones.



Consideraremos que internamente representamos cada rectángulo con cuatro números: 
    - Dos para las coordenadas de su esquina superior izquierda.
    - Un número para el ancho y otro para el alto.

Utilizaremos una letra mayúscula para nombrar un rectángulo y una letra minúscula para nombrar su esquina superior izquierda, punto que indicaremos también en las figuras que vamos a mostrar aquí.

Así pues, queremos saber si los rectángulos A y B -al menos uno de ellos será móvil- se tocan en el momento en el que preguntemos por ello. Los dos protagonistas se presentan en la figura 1.

- Figura 1 -

El problema es sencillo, pero si uno se hace un lío acaba imponiendo un montón de condiciones, intentando contemplar todas las posiciones posibles.

Existe una forma fácil de resolverlo, cambiar el problema por otro más inmediato: saber si un punto se encuentra dentro de un rectángulo. 

¿Y eso qué tiene que ver con lo anterior? Ahí está lo interesante, en que vamos a transformar el problema.

Empezamos creando un rectángulo más grande, uno que tendrá el alto de A más el alto de B, y que tendrá el ancho de A más el ancho de B, construido como se indica en la figura 2.

- Figura 2 -

Si dibujamos ahora un rectángulo que abarque a estos tres, obtenemos el rectángulo grande que buscábamos y que llamamos C en la figura 3.


- Figura 3 -


Realmente C puede calcularse de varias formas, la que he descrito en la figura 2 es sólo una de ellas. Lo importante son las dimensiones de C y que uno de los rectángulos, en este caso el A, queda en su parte inferior derecha.

Bien, pues ya hemos transformado el problema: Los rectángulos A y B se tocan si y sólo si el punto "b" del rectángulo B se encuentra dentro del rectángulo C.

No vamos a echar mano de demostraciones formales, primero porque no se me ocurre ninguna sencilla, y segundo porque es suficiente con echarle un ojo a la figura 4 para comprender la idea.

- Figura 4 -


Si movemos mentalmente el rectángulo B, observaremos que A y B se tocan sólo cuando el punto "b" está dentro de C. ¡Mola!

Implementar esto es más sencillo y eficiente que atacar el planteamiento original, puesto que la única complicación, que es transformar el problema, es también muy simple de calcular, de hecho se hace sobre la marcha.

Para ilustrarlo, muestro una implementación en Visual Basic, mediante una función que recibe directamente los cuatro datos que utilizamos para representar cada rectángulo.

Public Function intersec(x1 As Double, y1 As Double, _
                        ancho1 As Double, alto1 As Double, _
                        x2 As Double, y2 As Double, _
                        ancho2 As Double, alto2 As Double) _
                        As Boolean

    intersec = x1 >= x2 - ancho1 And _
               x1 <= x2 + ancho2 And _
               y1 >= y2 - alto1 And _
               y1 <= y2 + alto2


End Function


El rectángulo grande no se almacena, sino que sólo se calcula en las expresiones de comparación y luego se desecha. Después de todo es un rectángulo auxiliar que no tiene más utilidad que esa.

Puede observarse que las operaciones utilizadas son pocas y rápidas. 


Una implementación muy eficiente en C podría hacerse mediante una macro, que también recibiría los datos de representación directamente:

#define COLISIONAN(x1, y1, ancho1, alto1, x2, y2, ancho2, alto2) 
((x1)-(ancho2)<=(x2) && (x1)+(ancho1)>=(x2) && (y1)-(alto2)<=(y2) && (y1)+(alto1)>=(y2))



Y esta es otra implementación en C, esta vez esperando recibir los rectángulos en estructuras que almacenan sus datos de representación:

#define COLISIONAN_EST(est1, est2) 
((est1).x - (est2).ancho <= (est2).x && 
 (est1).x + (est1).ancho >= (est2).x && 
 (est1).y - (est2).alto  <= (est2).y && 
 (est1).y + (est1).alto  >= (est2).y)


En fin, no es una idea especial y seguramente carece de utilidad con las librerías actuales, pero me hacía ilusión exponerla para quien le pueda interesar, además de ser un pequeño homenaje a una época en la que un pixel era un mundo.


11 comentarios:

  1. Muy bonito, pero supongamos que los rectángulos no son paralelos a los ejes?, vamos que cada uno tiene su propio ángulo de rotación.

    Me explico: Imagina que el rectángulo está definpor tres puntos cualqesquiera del plano y que ninguno de ellos tiene en común ninguna coordenada con los otros...

    Por ejemplo pongamos que un rectangulo tiene sus cuatro vértices así:
    (0,0)-(3,3)-(2,4)-(-1,1)

    Como se pude ver, ninguno de sus lados es paralelo a ningún eje...

    Por lo que todas las simplificaciones no son válidas... es mucho más complejo...

    Para ver que dos de ellos se intersecten o toquen habría que ver si algún extremo de uno toca o está en el interior del otro -> en ese caso se tocan o intersectan, pero si no todavía no sabemos nada... después habría que ver si algún segmento de uno toca a algún segmento del otro... lo que no excluye la necesidad de la comprobación anterior en el caso de que uno esté completamente dentro del otro....

    ResponderEliminar
  2. ¡En primer lugar gracias por comentar! xD

    Tienes razón, la solución que expongo no es válida en cualquier situación teórica.

    Sin embargo este problema concreto se ciñe a rectángulos de lados paralelos a los ejes de coordenadas, junto con otras restricciones.

    El enfoque que tú comentas sin duda es más completo, pero precisamente se trata de aprovechar las restricciones anteriores para encontrar una solución fácil de implementar y rápida de ejecutar.

    Eso es lo interesante, que gracias a las características del problema, este puede ser transformado en otro más simplificado.

    ResponderEliminar
  3. Es una idea brillante pero tras darle vueltas me he dado cuenta de que no es correcta.

    No vale para todos los casos ya que el rectángulo auxiliar C debería ser más grande.

    Si miras la Figura 2, sólo contemplas que se toquen por la izquierda y por arriba pero ¿y por la izquierda y por debajo...?

    Así pues, el rectángulo C, teniendo al rectángulo A justo en el centro, sería:

    Ancho: dos veces el ancho de B + el ancho de A.
    Alto: dos veces el alto de B + el alto de A.

    Entonces sí que para cualquier rectangulo B incluido en el rectángulo C intersecaría con A.

    Espero haberme explicado bien y gracias por la idea, que es lo que cuenta :D

    ResponderEliminar
  4. ¡Hola! Gracias por comentar.

    La idea que expongo es correcta, te lo aseguro.

    La figura 2 no habla de intersecciones, sólo explica cómo construir un rectángulo auxiliar para transformar el problema inicial, el de la intersección de dos rectángulos, en el problema de detectar si un punto está dentro de un rectángulo. Para ello, y esto es importante, los rectángulos deben estar representados como se indica al principio de la entrada (los cuatro números).

    Fíjate bien, la figura 2 cuenta cómo construir el rectángulo C de la figura 3. Una vez ya lo tenemos, los rectángulos A y B se tocan si y sólo si el punto "b" (del rectángulo B) está dentro del rectángulo auxiliar C.

    Implementa esta idea en un programa (puedes servirte de cualquiera de los códigos que doy al final) y realiza pruebas. Verás como sí funciona.

    ¡Un saludo!

    ResponderEliminar
  5. Me ha sido de muchísima utilidad este método!!! Gracias. Lo voy a implementar en Javascript y lo pondré en los comentarios.

    ResponderEliminar
  6. gracias pro el apoyo me ayudo bastante!!
    publicare algo mejorado cundo tenga mas practica gracias

    ResponderEliminar
  7. Gracias a ti. ¡Ánimo para seguir practicando!

    ResponderEliminar
  8. muy bueno! hace poco me tomaron un examen con este problema para entrar a un trabajo que hubiera estado muy bueno entrar, pero termine haciendo una solucion de 150 lineas que no funcionaba :S ojala ubiera leido este post antes >D gracias!

    ResponderEliminar
  9. Siento tener abandonado el blog y haber publicado tu comentario tan tarde. Gracias y buena suerte con el trabajo. ¡Ánimo!

    ResponderEliminar