Stocker des points 2D pour une récupération rapide de ceux qui se trouvent dans un rectangle

Question

J'ai un grand nombre de points 2D et je souhaite obtenir rapidement ceux qui se trouvent dans un certain rectangle. Disons un '.' n’importe quel point et "X" est un point que je souhaite trouver dans un rectangle qui a "T" en tant que TopLeft et "B" en tant que points BottomRight:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

J'ai essayé un std :: set avec un foncteur de tri qui trie le point TopLeft au début et le BottomRight à la fin du set. Lors du tri par valeur X en premier, les points suivants seront trouvés:

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

Cela signifie que je devrais vérifier chaque point trouvé, s'il se trouve vraiment à l'intérieur du rectangle. Pas vraiment bien.

Quel serait un meilleur moyen de le faire?

Mon langage est le C ++ (Windows) et je dispose de la STL et de la boost.

Mettre à jour

Après avoir lu les réponses jusqu’à présent, j’ai remarqué que je n’avais pas pris en compte tous les paramètres de mon problème: il n’existe pas de rectangle fixe. Les rectangles peuvent être définis par l'utilisateur lors de l'exécution. Cela signifie que le tri de l'ensemble des points promet d'être plus efficace qu'une recherche linéaire parmi tous les points suggérée par Artelius avant cette mise à jour. Je vais quand même essayer! Je ne m'attends pas à ce que l'utilisateur définisse un rectangle très fréquent. Donc, en ce qui concerne les efforts de mise en œuvre, cela pourrait être une bonne solution pour moi.

Answer 1

Vous pouvez stocker les points dans un index spatial à l'aide de quad ou de r-trees. Puis, étant donné le rectangle que vous pouvez trouver tous les nœuds de l’arbre qui le chevauchent, vous devrez alors comparer chaque point de ce sous-ensemble pour voir s’il tombe dans le rectangle.

En substance, l’arborescence spatiale vous aide à élaguer l’espace de recherche.

Vous pourrez peut-être utiliser une solution plus simple, telle que la partition des points dans des plages. Dites où x est compris entre 0,10 et 11,20. Toute solution permettant d'élaguer l'espace de recherche vous aidera.

Answer 2

Veuillez consulter cette question . Le référentiel d'algorithmes Stony Brook contient des implémentations de KDTrees dans C ++, bien qu'ils ne fassent pas partie de STL ni de Boost.

Answer 3

Le tri d'un tableau prend O ( n log n ). Vérifier simplement chaque point individuellement (sans trier) prend un temps O ( n ).

Ergo, il est plus rapide de vérifier et de vérifier chaque point que de trier. Et c'est plus rapide que de construire un arbre à quatre aussi.

EDIT: Si vous avez plusieurs rectangles à vérifier, la situation est différente. Mais si vous n’avez besoin que de vérifier un petit nombre fixe de rectangles, faites-le simplement "évident". chemin!

Answer 4

utilisez un quadtree et vous avez 3 types de nœuds qtree:

1. noeud est en dehors du rectangle cible: ignorer
2. noeud est à l'intérieur du rectangle cible: inclure tous les points à l'intérieur du noeud
3. le noeud est partiellement en dehors du rectangle: faites une vérification des limites des points à l'intérieur du noeud

Answer 5

Après le lien de Yuval F, j'ai trouvé Recherche par plage , qui semble être exactement le genre de chose que vous recherchez. À partir de là, j'ai suivi des liens et trouvé la CGAL , une bibliothèque open source C ++, qui implémente une recherche par plage, avec des exemples ici .

Answer 6

Votre fonction de tri peut vérifier les points au fur et à mesure de leur ajout dans l'intérieur du rectangle et trier tous les points à l'intérieur du rectangle avant tous les points à l'extérieur du rectangle. Vous devez savoir combien il en existe ou utiliser une recherche binaire sur l’ensemble du jeu pour trouver le point de coupure au moment de la recherche.