Comment déterminer les cuboïdes d'un point sans les parcourir tous?

Question

J'ai un certain nombre de cuboïdes dont les positions et les tailles sont données avec les coordonnées minimum et maximum x, y et z (donc elles sont parallèles aux axes principaux).

par exemple. Je pourrais avoir les 3 parallélépipèdes suivants:

 
10.5 <= x <= 39.4, 90.73 <= y <= 110.2, 90.23 <= z <= 95.87 
20.1 <= x <= 30.05, 9.4 <= y <= 37.6, 0.1 <= z <= 91.2 
10.2 <= x <= 10.3, 0.1 <= y <= 99.8, 23.7 <= z <= 24.9 

Si je donne alors un point (par exemple (25.3,10.2,90.65)), est-il un moyen de déterminer rapidement les cuboïde (s) je suis?

• Il est évident que je pouvais itérer sur tous les parallélépipèdes, mais il y a potentiellement des millions d'entre eux, et je besoin de ceci pour aller plus vite que l'itération simple (quelque chose O (log n) ou mieux serait génial).

• Cela me semble un problème de type « correspondance floue », et je remarque que Apache Lucene soutient range queries, mais cela semble fonctionner dans le sens opposé rond (trouver un point dans un parallélépipède plutôt que d'un parallélépipède contenant un point) . Pour compliquer légèrement les choses, le nombre de dimensions peut être supérieur à 3 (il pourrait être supérieur à 20); dire que je pourrais être à la recherche de « hypercuboids » plutôt que parallélépipèdes)

Answer 1

Une façon simple d'accélérer cette requête est en construisant la grille uniforme structure de données (bacs souvent appelés) après une étape de pré-traitement: Mettez une grille sur votre scène et pour chaque cellule de la grille n x n x n (en 3D) stocker un pointeur sur tous les cuboïdes qui coupent cette cellule. Maintenant, pour un point de requête, vous pouvez calculer directement dans quelle cellule il se trouve dans la grille uniforme, et ensuite vous devez vérifier seulement les cuboïdes associés à cette cellule, et pas tous les cuboïdes. En fonction de la taille de l'espace et de la variation de la taille des cuboïdes, cette méthode risque de ne pas être très efficace car il vous sera difficile de choisir une bonne résolution pour accélérer suffisamment et ne pas avoir besoin d'une énorme quantité de cellules. Pour surmonter cela, vous pouvez essayer de trouver des façons plus adaptatives de partitionner l'espace, comme kd-trees(kd-trees at wikipedia), qui sont essentiellement des arbres binaires qui partitionnent l'espace avec des plans alignés sur l'axe: Voir un exemple ici où le plan rouge divise la boîte en deux parties, puis le vert en petites parties, puis le bleu ...

Une requête à l'aide kd-arbre serait d'abord traverser vers le bas à la feuille de l'arbre kd où le point d'interrogation se trouve, puis vérifiez les parallélépipèdes locales dans cette cellule. Vous pouvez trouver d'autres options de structure de données de partitionnement de l'espacehere. Une autre option consisterait à utiliser les hiérarchies de volume englobant, qui regroupent les objets dans des volumes englobants, puis regroupent les volumes englobants dans des volumes de délimitation plus grands, et ainsi de suite ... pour obtenir une hiérarchie de volumes englobants. Ceux-ci s'adaptent mieux à une scène et peuvent gérer plus facilement les scènes où les objets bougent, mais je pense que pour votre espace de partitionnement, le partitionnement pourrait bien fonctionner ... Quoi qu'il en soit, pour plus de détails voir this book chapter.

Answer 2

vous confinant sur le territoire de « binaire Espace Cloisonnement » et « détection de collision ». essentiellement les idées stockent essentiellement les cuboïdes dans une structure de type arbre, qui divise l'espace qu'ils occupent en petites boîtes bien rangées. La décision de savoir quelle «partie d'espace» occupe chaque cuboïde est prise lors de l'insertion dans la structure de l'arbre.

Effectuez une recherche google sur Octrees.

Diviser efficacement l'espace 3D, et les objets contenus dans cet espace est une grande partie de l'informatique; principalement utilisé dans le développement de jeux informatiques. Certains des algorithmes prennent en compte un facteur temporel, c'est-à-dire que les objets se déplacent entre des espaces de partition.