Algorithme pour le test de frappe dans des rectangles ne se chevauchant pas

Question

J'ai une collection de rectangles qui ne se chevauchent pas et qui recouvrent un rectangle. Quel est le meilleur moyen de trouver le rectangle contenant pour un clic de souris?

La réponse évidente est d’avoir un tableau de rectangles et de les rechercher dans l’ordre, en faisant la recherche O (n). Existe-t-il un moyen de les classer par position de manière à ce que l’algorithme soit inférieur à O (n), disons O (log n) ou O (sqrt (n))?

Answer 1

Vous pouvez organiser vos rectangles en quad ou en kd-tree. Cela vous donne O (log n). C'est la méthode traditionnelle.

Une autre structure de données intéressante pour ce problème est l'arborescence R. Celles-ci peuvent être très efficaces si vous devez gérer de nombreux rectangles.

http://fr.wikipedia.org/wiki/R-tree

Ensuite, il existe la méthode O (1) qui consiste simplement à générer un bitmap de la même taille que votre écran et à le remplir avec un espace réservé pour "Aucun rectangle". et dessinez les index rectangle d'accès dans cette image bitmap. Une recherche devient aussi simple que:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

Évidemment, cette méthode ne fonctionne bien que si vos rectangles ne changent pas aussi souvent et si vous pouvez économiser de la mémoire pour le bitmap.

Answer 2

Créez un arbre d'intervalle. Interrogez l'arbre d'intervalle. Consultez "Algorithmes" dans la presse du MIT.

Un arbre d'intervalle est mieux implémenté en tant qu'arbre rouge-noir.

N'oubliez pas qu'il n'est conseillé de trier vos rectangles que si vous allez cliquer dessus plus généralement que vous changez leur position.

N'oubliez pas que vous avez construit construire vos index pour différents axes séparément. Par exemple, vous devez voir si vous chevauchez un intervalle sur X et sur Y. Une optimisation évidente consiste à vérifier uniquement le chevauchement sur l'un ou l'autre des intervalles X, puis de vérifier immédiatement le chevauchement sur Y.

De plus, la plupart des arbres d'intervalle stock ou 'classbook' ne vérifient qu'un seul intervalle et ne renvoient qu'un seul intervalle (mais vous avez dit "ne se chevauchent pas"? n'est-ce pas?)

Answer 3

Placez-les dans un quadtree .

Answer 4

Utilisez une arborescence BSP pour stocker les rectangles.