estructura de datos y el algoritmo para detectar colisiones de mover objetos de forma irregular

Question

me encontré con esta pregunta de la entrevista

Muchos objetos de forma irregular se mueven en direcciones aleatorias. Proporcione una estructura de datos y un algoritmo para detectar colisiones. Recuerde que la cantidad de objetos es de millones.

Supongo que cada objeto tendrá una coordenada xey. Otras suposiciones son bienvenidas. También se debería usar cierto tipo de árbol, supongo, pero no tengo ni idea del algoritmo.

¿Alguna sugerencia?

Answer 1

me gustaría tener un vistazo a la Plane Sweep Algorithm o la Bently-Ottmann Algorithm. Utiliza el barrido de plano para determinar en el tiempo O(n log(n)) (y el espacio O(n)) la intersección de las líneas en un plano euclidiano.

Answer 2

Supongo que debe haber un bucle que toma referencia de 1 objeto encontrar coordenadas y luego comprueba con el resto de todos los demás objetos para ver si hay una colisión. No estoy seguro de cuán buena es mi solución para millones de objetos. Psuedo-código:

For each irregular shaped object1  

int left1, left2; 
int right1, right2; 
int top1, top2; 
int bottom1, bottom2; 
bool bRet = 1; // No collision 

left1 = object1->x; 
right1 = object1->x + object1->width; 
top1 = object1->y; 
bottom1 = object1->y + object1->height; 

For each irregular shaped object2 
{ 
    left2 = object2->x; 
    right2 = object2->x + object2->width; 
    top2 = object2->y; 
    bottom2 = object2->y + object2->height; 

    if (bottom1 < top2) bRet =0; 
    if (top1 > bottom2) bRet = 0; 

    if (right1 < left2) bRet = 0; 
    if (left1 > right2) bRet = 0; 
} 

return bRet; 

Answer 3

Existen muchas soluciones a este problema. Primero: use cuadros o círculos delimitadores (bolas en 3D). Si los cuadros delimitadores no se cruzan, entonces no se necesitan más pruebas. Segundo: subdivida tu espacio. No tiene que probar cada objeto contra todos los demás objetos (es decir, O (n^2)). Puede tener una complejidad promedio de O (n) con quadtrees.

Answer 4

Lo más probable es que lo que quiere es subdividir el plano con una curva de relleno de espacio como una curva z o una curva de hilbert y así reducir la complejidad de un problema 2D a un problema 1D. Busque quadtree.

Enlace: http://dmytry.com/texts/collision_detection_using_z_order_curve_aka_Morton_order.html