Je suis tombé sur cette question d'entrevue
De nombreux objets de forme irrégulière se déplacent dans des directions aléatoires. Fournissez une structure de données et un algorithme pour détecter les collisions. N'oubliez pas que le nombre d'objets est dans les millions.
Je suppose que chaque objet aurait une coordonnée X et Y. D'autres hypothèses sont les bienvenues. Un certain type d'arbre doit également être utilisé, je suppose, mais je n'ai pas de désempare l'algorithme.
Toute suggestion?
4 Réponses :
Je suppose qu'il devrait y avoir une boucle qui prend référence à 1 objet trouve des coordonnées, puis vérifie le reste de tous les autres objets pour voir s'il y a une collision. Je ne suis pas sûr de la qualité de ma solution pour des millions d'objets. PSEDEDO-CODE:
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;
Je ne sais pas à quel point ces formes sont "irrégulières". Cela ressemble plus à des rectangles.
L'algo ci-dessus de Natashad est complètement faux, ne le suivez pas. Vous devez donner une gamme d'objets d'objets et vérifier si la gamme OBJ1 est à Obj2 Rang et inversement que la collision est survenue autre chose.
J'y regarderais sur le algorithme de balayage d'avion ou le Algorithme Brent-Ottmann . Il utilise le balayage du plan pour déterminer dans O (n log (n)) heure (et O (n) espace) l'intersection des lignes sur un plan euclidian.
"Irrégulièrement formé" contre intersection de la ligne? Cela pourrait être une solution en 2D mais vous pouvez faire mieux que O (n log n). En 3D, cela ne fonctionne pas.
@knivil - L'algorithme peut être étendu au travail dans un espace 3D, c'est pourquoi il s'appelle le balayage de l'avion et non le balayage de la ligne. Les algorithmes étaient à référence.
Il existe de nombreuses solutions à ce problème. Premièrement: utilisez des boîtes de liaison ou des cercles (balles en 3D). Si les boîtes de sélection ne se croisent pas, aucun autre test n'est nécessaire. Deuxièmement: subdiviser votre espace. Vous n'avez pas à tester tous les objets contre tous les autres objets (c'est O (n ^ 2)). Vous pouvez avoir une complexité moyenne de O (n) avec Quadtrees.
Très probablement Ce que vous voulez, c'est sous-diviser l'avion avec une courbe de remplissage d'espace comme une courbe Z ou une courbe Hilbert et réduisant ainsi la complexité d'un problème 2D à un problème de 1D. Chercher quadtree.
Link: http://dmietry.com/texts/collision_detection_uce_z_order_curve_aka_morton_order.html
Je m'attendrais à ce que ces objets aient plus d'une coordonnée X et Y, pas seulement comme vous le mentionnez / attend. Avez-vous posté la question Verbatim? Je suppose que non, car de tout sifflement sont manquants, imo. Par exemple, quelle est la "forme irrégulière" exactement?