Comment puis-je déterminer qui parallélépipèdes un point est en sans itérer sur tous?

Question

I ai un certain nombre de parallélépipèdes dont les positions et les tailles sont données avec les coordonnées x minimale et maximale, et y z (de sorte qu'ils 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 puis donner 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 cela pour aller plus vite que l'itération simple (quelque chose O (log n) ou mieux serait génial).

• Ce me semble un problème de type "correspondance floue", et je remarque que Apache Lucene soutient requêtes de gamme , mais cela semble de travailler autour de la manière opposée (trouver un point dans un parallélépipède plutôt que d'un parallélépipède contenant un point).

• Pour compliquer un peu les choses, le nombre de dimensions peut être supérieur à 3 (il pourrait être jusqu'à 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 les éléments suivants grille uniforme structure de données (bacs souvent appelés) comme une étape de pré-traitement: grille Mettre n x n x n (en 3D) sur scène et pour chaque cellule de la grille de stocker un pointeur vers tous les parallélépipèdes se coupant cette cellule. Maintenant, pour un point d'interrogation, vous pouvez calculer directement dans quelle cellule il est dans la grille uniforme, et vous devez vérifier que les parallélépipèdes associés à cette cellule, et non tous les parallélépipèdes.

En fonction de la taille de l'espace et comment varier les tailles cuboïde sont cette méthode pourrait ne pas être très efficace parce que vous il peut être difficile de choisir une bonne résolution de n pour accélérer suffisamment et pas besoin d'une énorme quantité de cellules. Pour remédier à cela, vous voudrez peut-être essayer de chercher des moyens plus adaptés pour partitionner l'espace, comme kd arbres

Une requête en utilisant 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. Autre structure de données de partitionnement de l'espace options peuvent être trouvées .

Une autre option serait d'utiliser englobante hiérarchies de volume regrouper des objets en volumes englobants, puis volumes englobants de groupe en volumes englobants plus grandes et ainsi de suite ... pour obtenir une hiérarchie de volumes englobants . Ceux-ci adaptent mieux à une scène et peut gérer des scènes plus facile où les objets se déplacent, mais je pense que pour pourrait bien fonctionner votre partitionnement de l'espace de réglage ... Quoi qu'il en soit, pour plus de détails, voir ce chapitre du livre .

Answer 2

frisant sur le territoire de « binaire Espace Cloisonnement » et « détection de collision »; essentiellement les idées stockent essentiellement les parallélépipèdes dans une structure de type arbre, qui divise l'espace qu'ils occupent dans des boîtes peu soignées. La décision sur laquelle « une partie de l'espace » chaque parallélépipède occupe est faite lors de l'insertion dans la strucutre de l'arbre.

Faites une recherche Google sur octrees.

divisant efficently espace 3D, et les objets contenus dans cet espace est tout à fait une grande partie de la science informatique; la plupart du temps utilisé dans le développement de jeux informatiques. Certains de ces algorithmes tiennent compte d'un facteur de temps, à savoir que les objets se déplacent entre les espaces de séparation.