Intersección rápida de rectángulo a rectángulo

81

¿Cuál es una forma rápida de probar si 2 rectángulos se cruzan?

Una búsqueda en Internet dio como resultado este resumen (¡WOOT!), Pero no entiendo cómo escribirlo en Javascript, parece estar escrito en una forma antigua de C ++.

struct
{
    LONG    left;
    LONG    top;
    LONG    right;
    LONG    bottom;
} RECT; 

bool IntersectRect(const RECT * r1, const RECT * r2)
{
    return ! ( r2->left > r1->right
        || r2->right < r1->left
        || r2->top > r1->bottom
        || r2->bottom < r1->top
        );
}
javascript c++ language-agnostic graphics Robin Rodricks
fuente
5
Creo que ha cometido un error tipográfico en su copia / pegado
fmark
5
El artículo original tiene un error tipográfico. r2->right leftno tiene sentido. Es posible que esté roto debido a problemas de escape de HTML.
Marcelo Cantos
42
Tengo curiosidad por saber cómo cree que el código anterior sería diferente en una forma "moderna" de C ++.
jamesdlin
3
Estoy seguro de que los caracteres que faltan son <símbolos debido al escape de html.
devios1
1
@jamesdlin haría que la función sea una función miembro de la estructura, tomando un parámetro. En segundo lugar, normalmente usaría const & en lugar de const *. Puede usar plantillas para tener versiones int, long y double, en lugar de usar alguna macro de Win32 ... (Tampoco se compila, ya que RECT termina siendo una instancia de una estructura sin nombre, no un nombre de tipo). : ideone.com/bnzwl3
Sebastian Wahl

Respuestas:

142

Así es como ese código se puede traducir a JavaScript. Tenga en cuenta que hay un error tipográfico en su código y en el del artículo, como sugieren los comentarios. Específicamente r2->right leftdebería ser r2->right < r1->lefty r2->bottom topdebería ser r2->bottom < r1->toppara que la función funcione.

function intersectRect(r1, r2) {
  return !(r2.left > r1.right || 
           r2.right < r1.left || 
           r2.top > r1.bottom ||
           r2.bottom < r1.top);
}

Caso de prueba:

var rectA = {
  left:   10,
  top:    10,
  right:  30,
  bottom: 30
};

var rectB = {
  left:   20,
  top:    20,
  right:  50,
  bottom: 50
};

var rectC = {
  left:   70,
  top:    70,
  right:  90,
  bottom: 90
};

intersectRect(rectA, rectB);  // returns true
intersectRect(rectA, rectC);  // returns false
Daniel Vassallo
fuente
Solo para agregar / confirmar: esto está probando tres cajas que son 20px x 20px, excepto rectB, que es 30px x 30px
verenion
6
si r1 y r2 son idénticos, la función intersectRect devolvería falso
zumalifeguard
Fantástica implementación elocuente. ¡Quiéralo! +1, funcionó perfectamente para mi juego.
Unome
1
@zumalifeguard ¿Por qué piensas eso?
Minix
Esta función es tan genial. Nunca habría pensado en eso, sino que habría intentado que las dos cajas se cruzaran.
Nikk Wong
69 
function intersect(a, b) {
  return (a.left <= b.right &&
          b.left <= a.right &&
          a.top <= b.bottom &&
          b.top <= a.bottom)
}

Esto supone que topnormalmente es menor que bottom(es decir, que las ycoordenadas aumentan hacia abajo).

DS.
fuente
Solución buena y funcional, pero debería ser un poco más lenta ya que se deben evaluar todas las condiciones. La otra solución se realiza tan pronto como una de las condiciones se evalúa como verdadera.
Gigo
21
Este también se realiza tan pronto como una de las condiciones se evalúa como falsa. Es decir, en los mismos casos exactos que el otro.
DS.
3
Esto es mejor ya que elimina la acción de negación.
Discipol
4
+1, mucho más ordenado que la respuesta aceptada. si usa rangos semiabiertos (es decir, el rectángulo incluye la parte superior e izquierda, pero no incluye la parte inferior y la derecha, como es común en muchos sistemas gráficos), debería funcionar cambiar <=a <.
Jules
Me gusta esta solución porque puedo eliminar el =para cada condición y permite que los rectángulos se "toquen" en los bordes.
prograhammer
19

Así es como .NET Framework implementa Rectangle.Intersect

public bool IntersectsWith(Rectangle rect)
{
  if (rect.X < this.X + this.Width && this.X < rect.X + rect.Width && rect.Y < this.Y + this.Height)
    return this.Y < rect.Y + rect.Height;
  else
    return false;
}

O la versión estática:

public static Rectangle Intersect(Rectangle a, Rectangle b)
{
  int x = Math.Max(a.X, b.X);
  int num1 = Math.Min(a.X + a.Width, b.X + b.Width);
  int y = Math.Max(a.Y, b.Y);
  int num2 = Math.Min(a.Y + a.Height, b.Y + b.Height);
  if (num1 >= x && num2 >= y)
    return new Rectangle(x, y, num1 - x, num2 - y);
  else
    return Rectangle.Empty;
}
Schwarrior
fuente
6

Otra forma más sencilla. (Esto supone que el eje y aumenta hacia abajo).

function intersect(a, b) {
  return Math.max(a.left, b.left) < Math.min(a.right, b.right) &&
          Math.max(a.top, b.top) < Math.min(a.bottom, b.bottom);
}

Los 4 números (máximos y mínimos) en la condición anterior también dan los puntos de intersección.

Duque
fuente
0

Usé una combinación de métodos para detectar un rectángulo más pequeño dentro de un rectángulo grande. Este es un método de nodejs y usa ancho / alto, pero se puede adaptar fácilmente.

            isIntersectingRect: function (r1, r2) {
              var quickCheck = (r1.x <= r2.x + r2.w &&
                      r2.x <= r1.x + r1.w &&
                      r1.y <= r2.y + r2.h &&
                      r2.y <= r1.y + r1.h)
              if (quickCheck) return true;
              var x_overlap = Math.max(0, Math.min(r1.x + r1.w, r2.x + r2.w) - Math.max(r1.x, r2.x));
              var y_overlap = Math.max(0, Math.min(r1.y + r1.h, r2.y + r2.h) - Math.max(r1.y, r2.y));
              var overlapArea = x_overlap * y_overlap;
              return overlapArea == 0;
            }
Langerz
fuente