I ont besoin d'un algorithme qui prend un tableau non trié de rectangles alignés axe et rendements toute paire de rectangles qui chevaucherectangles alignés axialement intersection
Chaque rectangle a deux variables, les coordonnées du coin supérieur gauche et le coin inférieur droit
Il est peut-être un peu compliqué pour une entrevue d'emploi, dépend quel genre de travail, Il est une sorte de calcul géométrique de l'algorithme,
la réponse se trouve ici: 0.123.http://www.cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
Voici une brève description de l'algorithme d'intersection présenté dans DuduAlul lien de.
La solution nécessite l'utilisation d'un arbre de recherche capable d'effectuer des interrogations de plage. Une requête de plage demande tous les éléments ayant des valeurs entre K1 et K2, et il doit s'agir d'une opération O (R + log N), où N est le nombre total d'éléments de l'arborescence et R le nombre de résultats.
L'algorithme utilise l'approche de balayage:
1) Tous les bords du rectangle à gauche et à droite, en fonction de leur valeur X, dans la liste L.
2) Créer un nouvel arbre recherche gamme vide T, pour la commande Y des sommets du rectangle/fond
3) Créer un nouveau RS jeu de résultats vide de paires rectangulaires uniques
4) Traverse de L dans un ordre croissant. Pour tous V L:
Si V.isRightEdge()
T.remove (V.rectangle.top)
T .remove (V.rectangle.bottom)
autre
Pour tous U T.getRange (V.rectangle.top, V.rectangle.bottom)
RS.add (< V.rectangle, U.rectangle>)
T.add (V.rectangle.haut)
T.add (V.rectangle.bottom)
5) retourner RS
La complexité en temps est O (R + N log N), où R est le nombre réel d'intersections.
- EDIT -
Je viens de comprendre que la solution n'est pas tout à fait correcte - le test d'intersection dans l'arbre T manque certains cas. L'arbre devrait conserver des intervalles Y plutôt que des valeurs Y, et il devrait idéalement être un Interval Tree.
Sweep and prune est la méthode que beaucoup de moteurs de physique pour résoudre ce genre de problème.
Il y a une bonne explication dans David Baraff's SIGGRAPH notes, dans la section 7.2 Boîtes de délimitation.
C'est une bonne réponse. Je l'ai également trouvé à la sortie de la classe _Hacking a Google Interview_ de csail.mit.edu –