¿Cuál es la forma más rápida de resolver la intersección del cuadro delimitador 2D?

62

Suponga que cada objeto Box tiene las propiedades x, y, ancho, alto y tiene su origen en su centro, y que ni los objetos ni los cuadros delimitadores giran.

Iain
fuente
¿Son estos ejes o cuadros delimitadores alineados con objetos?
Tenpn
3
Cuando haga esta pregunta, seguramente necesitará probar otros tipos de intersecciones en el futuro;). Por lo tanto, sugiero LA LISTA sobre la intersección Objeto / Objeto. La tabla proporciona intersecciones entre todos los tipos de objetos populares (cajas, esferas, triángulos, cilindros, conos, ...) en situaciones estáticas y dinámicas.
Dave O.
2
Por favor, reformule su pregunta a las referencias limitantes. Desde mi punto de vista, el cuadro implica un objeto 3d.
Dave O.

Respuestas:

55

(Seudocódigo C-ish: adapte las optimizaciones de idioma según corresponda)

bool DoBoxesIntersect(Box a, Box b) {
  return (abs(a.x - b.x) * 2 < (a.width + b.width)) &&
         (abs(a.y - b.y) * 2 < (a.height + b.height));
}

En inglés: en cada eje, verifique si los centros de los cuadros están lo suficientemente cerca como para que se crucen. Si se cruzan en ambos ejes, entonces las cajas se cruzan. Si no lo hacen, entonces no lo hacen.

Puede cambiar los <'s a <= si desea contar el toque de borde como intersección. Si desea una fórmula específica de solo toque de borde, no puede usar ==, eso le dirá si las esquinas se tocan, no si los bordes se tocan. Te gustaría hacer algo lógicamente equivalente a return DoBoxesIntersectOrTouch(a, b) && !DoBoxesIntersect(a, b).

Vale la pena mencionar que puede obtener un aumento de velocidad pequeño pero significativo almacenando el ancho medio y la altura media además de (o en lugar de) el ancho completo y la altura completa. Por otro lado, es raro que la intersección del cuadro delimitador 2D sea el cuello de botella del rendimiento.

ZorbaTHut
fuente
99
Obviamente, esto supone que los cuadros están alineados con los ejes.
Tenpn
1
Los abdominales no deberían ser particularmente lentos, no más lento que un condicional, al menos, y la única forma de hacerlo sin abdominales (que yo sepa) implica condicionales adicionales.
ZorbaTHut
44
Sí, asume cajas alineadas con ejes. Sin embargo, las estructuras descritas no tienen ninguna forma de indicar la rotación, así que sentí que era seguro.
ZorbaTHut
3
Aquí hay algunos buenos consejos para acelerar los cálculos en Actionscript (principalmente, calc de enteros): lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math Estoy publicando esto, porque también contiene reemplazo para Math.abs (), que tiende a ralentizar las cosas en Actionscript (hablando de cosas críticas de rendimiento, por supuesto).
bummzack
2
Te falta que tengan el origen en el centro, no en el borde izquierdo. Un cuadro que va de 0 a 10 tendrá "x = 5", mientras que un cuadro que va de 8 a 12 tendrá "x = 10". Terminas con abs(5 - 10) * 2 < (10 + 4)=> 10 < 14. Tendrá que hacer algunos ajustes simples para que funcione con topleft-corner-and-size.
ZorbaTHut
37

Esto funciona para dos rectángulos alineados con los ejes X e Y.
Cada rectángulo tiene las propiedades:
"izquierda", la coordenada x de su lado izquierdo,
"arriba", la coordenada y de su lado superior,
"derecha", la coordenada x de su lado derecho,
"abajo", la coordenada y de su lado inferior

function IntersectRect(r1:Rectangle, r2:Rectangle):Boolean {
    return !(r2.left > r1.right
        || r2.right < r1.left
        || r2.top > r1.bottom
        || r2.bottom < r1.top);
}

Tenga en cuenta que esto está diseñado para un sistema de coordenadas en el que el eje + y apunta hacia abajo y el eje + x se dirige hacia la derecha (es decir, coordenadas de pantalla / píxel típicas). Para adaptar esto a un sistema cartesiano típico en el que + y se dirige hacia arriba, las comparaciones a lo largo de los ejes verticales se invertirían, por ejemplo:

return !(r2.left > r1.right
    || r2.right < r1.left
    || r2.top < r1.bottom
    || r2.bottom > r1.top);

La idea es capturar todas las condiciones posibles sobre los que los rectángulos se no se superponen, y luego negar la respuesta para ver si se superponían. Independientemente de la dirección de los ejes, es fácil ver que dos rectángulos no se superpondrán si:

  • el borde izquierdo de r2 está más a la derecha que el borde derecho de r1

     ________     ________
    |        |   |        |
    |   r1   |   |   r2   |
    |        |   |        |
    |________|   |________|
  • o el borde derecho de r2 está más a la izquierda que el borde izquierdo de r1

     ________     ________
    |        |   |        |
    |   r2   |   |   r1   |
    |        |   |        |
    |________|   |________|
  • o el borde superior de r2 está debajo del borde inferior de r1

     ________ 
    |        |
    |   r1   |
    |        |
    |________|
     ________ 
    |        |
    |   r2   |
    |        |
    |________|
  • o el borde inferior de r2 está por encima del borde superior de r1

     ________ 
    |        |
    |   r2   |
    |        |
    |________|
     ________ 
    |        |
    |   r1   |
    |        |
    |________|

La función original, y una descripción alternativa de por qué funciona, se puede encontrar aquí: http://tekpool.wordpress.com/2006/10/11/rectangle-intersection-determine-if-two-given-rectangles-intersect- uno al otro o no /

Ponkadoodle
fuente
1
Sorprendentemente intuitivo y muestra una vez más que cuando encontrar la respuesta es demasiado difícil, tratar de encontrar la respuesta a una pregunta opuesta podría ayudarlo. ¡Gracias!
Lodewijk
1
Debe mencionar que el eje y apunta hacia abajo (como en una imagen). De lo contrario, las desigualdades r2.top> r1.bottom y r2.bottom <r1.top deben revertirse.
user1443778
@ user1443778 buena captura! Seguí adelante y expliqué libremente la lógica detrás de este algoritmo de una manera independiente del sistema de coordenadas.
Ponkadoodle
11

Si desea cuadros delimitadores alineados a objetos, pruebe este tutorial sobre el teorema del eje de separación por metanet: http://www.metanetsoftware.com/technique/tutorialA.html

SAT no es la solución más rápida, pero es relativamente simple. Estás tratando de encontrar una sola línea (o un plano si es 3D) que separe tus objetos. Si esta línea existe, se garantiza que esté paralela al borde de una de sus cajas, por lo que debe iterar a través de todas las pruebas de bordes para ver si separa las cajas.

Esto también funciona para cajas alineadas por eje al restringir solo el eje x / y.

tenpn
fuente
No estaba pensando en la rotación, pero gracias, ese es un enlace interesante.
Iain
5

El DoBoxesIntersect anterior es una buena solución por pares. Sin embargo, si tiene muchas cajas, todavía tiene un problema O (N ^ 2), y es posible que necesite hacer algo además de eso, como lo que Kaj se refiere. (En la literatura de detección de colisiones en 3D, esto se conoce como tener un algoritmo de fase amplia y uno de fase estrecha. Haremos algo realmente rápido para encontrar todos los posibles pares de superposiciones, y luego algo más costoso para ver si es posible los pares son pares reales)

El algoritmo de fase amplia que he usado antes es "barrer y podar"; para 2D, mantendría dos listas ordenadas del inicio y el final de cada cuadro. Mientras el movimiento de la caja no sea >> escala de la caja de cuadro a cuadro, el orden de estas listas no cambiará mucho, por lo que puede usar la clasificación de burbuja o inserción para mantenerlo. El libro "Real-Time Rendering" tiene un buen resumen sobre las optimizaciones que puede hacer, pero se reduce a tiempo O (N + K) en la fase amplia, para N cajas, K de las cuales se superponen, y con un excelente mundo real rendimiento si puede permitirse N ^ 2 booleanos para realizar un seguimiento de qué pares de cajas se cruzan de cuadro a cuadro. Luego tiene O (N + K ^ 2) en general, que es << O (N ^ 2) si tiene muchas casillas pero solo unas pocas superposiciones.

Tom Hudson
fuente
5

Muchas matemáticas aquí para un problema muy simple, supongamos que tenemos 4 puntos determinados para un rect, arriba, izquierda, abajo, derecha ...

En el caso de determinar si 2 rectos colisionan, solo necesitamos observar que todos los extremos posibles evitarían colisiones, si ninguno de estos se cumple, entonces los 2 rectos DEBEN colisionar, si desea incluir colisiones límite, simplemente reemplace los> y < con apropiado> = y = <.

struct aRect{
  float top;
  float left;
  float bottom;
  float right;
};

bool rectCollision(rect a, rect b)
{
  return ! ( b.left > a.right || b.right < a.left || b.top < a.bottom || b.bottom > a.top);
}
usuario35189
fuente
Sinceramente, no estoy seguro de por qué esta no es la respuesta más votada. Es simple, correcto y eficiente.
3Dave
3

Versión alternativa de la respuesta de ZorbaTHut:

bool DoBoxesIntersect(Box a, Box b) {
     return (abs(a.x - b.x) < (a.width + b.width) / 2) &&
     (abs(a.y - b.y) < (a.height + b.height) / 2);
}
Iain
fuente
En realidad, esa aritmética funciona bien de cualquier manera. Puede hacer cualquier operación aritmética a ambos lados de <y no la cambia (la multiplicación por un negativo significa que debe cambiar el menor que, sin embargo). En ese ejemplo, las cajas no deberían colisionar. Si el centro del recuadro A está en 1, abarca de -4 a 6. El recuadro b se centra en 10 y abarca de 7,5 a 12,5, no hay colisión allí ... Ahora, el método que Wallacoloo publicó no solo es correcto, pero se ejecutará más rápido en los idiomas que implementan cortocircuito, ya que la mayoría de las comprobaciones volverán falsas de todos modos, el cortocircuito puede cortarse después de
Deleter
Sí, me di cuenta de esto cuando me desperté esta mañana. Chris me engañó con su <> confusión.
Iain el
1
Dos problemas: primero, la división tiende a ser significativamente más lenta que la multiplicación. En segundo lugar, si los valores involucrados son enteros, esto podría generar algunos problemas de truncamiento de enteros (ax = 0, bx = 9, a.width = 9, b.width = 10: abs (0-9) <(9 + 10) / 2, 9 <19/2, 9 <9, la función devuelve falso a pesar de que las casillas se cruzan definitivamente.)
ZorbaTHut
2

Dependiendo del problema que intente resolver, es mejor que haga un seguimiento de su objeto mientras lo mueve, es decir, mantenga una lista de las posiciones ordenadas x de inicio y final y una para las posiciones de inicio y final. Si tiene que hacer MUCHAS verificaciones de superposición y, por lo tanto, necesita optimizar, puede usar esto para su ventaja, ya que puede buscar inmediatamente quién está terminando se cierra a su izquierda, todos los que están a la izquierda pueden ser podados. inmediatamente. Lo mismo aplica para arriba, abajo y derecha.
La contabilidad cuesta tiempo, por supuesto, por lo que es más adecuada para una situación con pocos objetos en movimiento pero muchos controles de superposición.
Otra opción es el hash espacial, donde se agrupan los objetos en función de la posición aproximada (el tamaño puede ponerlos en varios cubos), pero de nuevo, solo si hay muchos objetos, con relativamente pocos de ellos moviéndose por iteración debido al costo de la contabilidad.
Básicamente, todo lo que evita (n * n) / 2 (si verifica el objeto a contra b, obviamente no tendrá que verificar b contra a) ayuda más que a optimizar las casillas de verificación. Si los controles de cuadro delimitador son un cuello de botella, aconsejaría seriamente buscar soluciones alternativas al problema.

Kaj
fuente
2

La distancia entre los centros no es la misma que la distancia entre las esquinas (cuando una caja está dentro de la otra, por ejemplo), por lo que EN GENERAL, esta solución es la correcta (creo).

distancia entre centros (para, por ejemplo, x): abs(x1+1/2*w1 - x2+1/2*w2)o1/2 * abs(2*(x1-x2)+(w1-w2)

La distancia mínima es 1/2 w1 + 1/2 w2 or 1/2 (w1+w2). las mitades se cancelan así que ...

return 
ABS(2*(x1 - x2) + (w1-w2) ) < (w1+w2)) &&
ABS(2*(y1 - y2) + (h1-h2) ) < (h1+h2));
Vladimir Dizhoor
fuente
1
¿Qué pasa con la declaración de "retorno" allí?
doppelgreener
1

Aquí está mi implementación en Java asumiendo una arquitectura de dos complementos . Si no está en el complemento de dos, utilice en su lugar una llamada de función estándar Math.abs :

boolean intersects(IntAxisAlignedBox left, IntAxisAlignedBox right) {
    return
        (
            lineDeltaFactor(left.min.x, left.max.x, right.min.x, right.max.x) |
            lineDeltaFactor(left.min.y, left.max.y, right.min.y, right.max.y) |
            lineDeltaFactor(left.min.z, left.max.z, right.min.z, right.max.z)
        ) == 0;
}

int lineDeltaFactor(int leftMin, int leftMax, int rightMin, int rightMax) {
    final int
            leftWidth = leftMax - leftMin,
            rightWidth = rightMax - rightMin,

            leftMid = leftMin + ((leftMax - leftMin) >> 1),
            rightMid = rightMin + ((rightMax - rightMin) >> 1);

    return (abs(leftMid - rightMid) << 1) / (leftWidth + rightWidth + 1);
}

int abs(int value) {
    final int mask = value >> (Integer.SIZE - 1);

    value ^= mask;
    value += mask & 1;
    return value;
}

Suponiendo que un compilador medio decente / LLVM en línea expande estas funciones para evitar el malabarismo de pila costoso y las búsquedas de tabla v. Esto fallará para los valores de entrada que están cerca de los extremos de 32 bits (es decir, Integer.MAX_VALUEy Integer.MIN_VALUE).

MadMartian
fuente
0

La forma más rápida es combinar los 4 valores en un único registro vectorial.

Almacene los cuadros en un vector con los siguientes valores [ min.x, min.y, -max.x, -max.y ]. Si almacena cajas como esta, la prueba de intersección solo toma 3 instrucciones de CPU:

_mm_shuffle_ps para reordenar la segunda caja volteando las mitades mínimas y máximas.

_mm_xor_pscon número mágico _mm_set1_ps(-0.0f)para voltear signos de los 4 valores en el segundo cuadro.

_mm_cmple_ps para comparar los 4 valores entre sí, comparando los siguientes dos registros:

[ a.min.x, a.min.y, -a.max.x, -a.max.y ] < [ b.max.x, b.max.y, -b.min.x, -b.min.y ]

Finalmente, si es necesario, _mm_movemask_psobtener el resultado de la unidad vectorial en un registro escalar. El valor 0 significa los cuadros intersectados. O si tiene más de 2 cuadros, esto no es necesario, deje los valores en registros vectoriales y utilice operaciones bit a bit para combinar resultados de varios cuadros.

No ha especificado el idioma ni la plataforma, pero el soporte para SIMD como este, o muy similar, está disponible en todas las plataformas e idiomas. En dispositivos móviles, ARM tiene NEON SIMD con cosas muy similares. .NET tiene Vector128 en el espacio de nombres System.Runtime.Intrinsics, y así sucesivamente.

Soonts
fuente