algorithme rapide pour détecter si une forme rectangulaire croise une limite rectangulaire

Question

Imaginez que vous avez une cour avec une clôture autour d'elle, ce qui pourrait ressembler à ceci:

______ ________ 
|  |_|  _| 
|    |_ 
|  _ ___| 
|__  |_| | 
    |   |__ 
___|  _  | 
|  | | |_ 
|________| |______| 

Don't ask why it's a weird shape, it's your yard, I didn't make it. 

..where cette petite boîte au milieu est un peu arbitraire objet carré. Si cet objet se déplaçait dans n'importe quelle direction vers le bord de votre jardin, comment le détecteriez-vous lorsque l'objet entrerait en collision avec votre clôture?

Et si votre cour était des milliers de fois plus grande et qu'il y avait beaucoup d'arêtes à surveiller? Comment pourriez-vous résoudre efficacement ce problème alors?

Answer 1

Voir la cour comme un grand rectangle avec plusieurs carrés "négatifs" retirés de celui-ci.

Stockez les emplacements de ces carrés négatifs dans un quad tree.

Pour vérifier la collision, sonder l'arbre pour les quatre carrés adjacents à l'objet.

La complexité temporelle de l'opération de détection dépend du choix de la variante de quadrillage, mais vous pouvez vous attendre à un temps logarithmique dans le nombre de carrés négatifs.