Como faço para determinar qual cuboids um ponto está em sem iteração sobre todos eles?
-
18-09-2019 - |
Pergunta
Eu tenho um número de cuboids cujas posições e tamanhos são dadas com mínima e máxima x
, y
e z
coordenadas (para que eles são paralelos aos eixos principais).
por exemplo. Eu poderia ter os seguintes 3 cuboids:
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
Se eu, em seguida, dar um ponto (por exemplo (25.3,10.2,90.65)
), há uma maneira para determinar rapidamente quais cubóide (s) Estou em?
-
Obviamente, eu poderia apenas iterar sobre todos os cuboids, mas há potencialmente milhões deles, e eu preciso disso para ir mais rápido do que iteração simples (algo O (log n) ou melhor seria ótimo).
-
Este soa para mim como um tipo de problema "fuzzy matching", e noto que suportes Apache Lucene consultas alcance , mas isso parece para trabalhar o oposto forma redonda (encontrar um ponto em um cubóide ao invés de um cubóide contendo um ponto).
-
para matérias ligeiramente complicar ainda mais, o número de dimensões pode ser maior do que 3 (poderia ser de até 20); ou seja, eu poderia estar procurando "hypercuboids" em vez de cuboids.)
Solução
Uma forma simples de acelerar esta consulta é construindo a seguinte grade uniforme estrutura de dados (muitas vezes chamado de caixas) como uma etapa de pré-processamento: Coloque um n x n x n
(em 3d) grade sobre sua cena e para cada célula da grade armazenar um ponteiro para todos os cuboids cruzam essa célula. Agora, para um ponto de consulta você pode calcular directamente em que celular é na grade uniforme, e então você tem que verificar apenas os cuboids associados a essa célula, e não todos os cuboids.
Dependendo quão grande o espaço é e como variando os tamanhos cubóide são este método pode não ser muito eficiente porque você pode ser difícil de escolher uma resolução n
bom para acelerar o suficiente e não precisa de uma enorme quantidade de células. Para superar isso, você pode querer tentar olhar para formas mais adaptáveis ??para particionar o espaço, como kd-árvores (kd-árvores a Wikipedia) , que são basicamente árvores binárias de particionamento do espaço com eixo planos alinhados: Ver, por exemplo, aqui com clivagens plano vermelho a caixa em duas partes e em seguida, o verde em partes menores, então o azul ...
A consulta usando kd-árvore em primeiro lugar percorrer para baixo para a folha da árvore-kd onde o ponto a consulta está localizado e, em seguida, verificar com os cuboids locais em que a célula. estrutura de dados Outro espaço de particionamento opções podem ser encontradas aqui .
Outra opção seria a utilização de hierarquias Desconto delimitadora , que agrupar objetos em delimitadora volumes, e depois grupo delimitadora volumes em volumes delimitadoras maiores e assim por diante ... para obter uma hierarquia de volumes limitando . Estes se adaptam melhor a uma cena e pode mais fáceis cenas punho onde os objetos se movem, mas eu acho que para a configuração de espaço de particionamento poderia funcionar bem ... De qualquer forma, para mais detalhes veja este capítulo de livro .
Outras dicas
Você beirando no território de "Binary Space Partitioning" e "Detecção de Colisão"; essencialmente as idéias estão armazenando basicamente os cuboids em uma estrutura tipo árvore, que divide o espaço que ocupam em pequenas caixas puras. A decisão sobre qual "parte do espaço" cada cubóide ocupa é feito durante a inserção no strucutre árvore.
Faça uma pesquisa no Google sobre octrees.
efficently dividindo espaço 3D, e os objetos contidos dentro desse espaço é bastante uma grande parte da ciência da computação; usado principalmente no desenvolvimento de jogos de computador. Alguns dos algoritmos levam em consideração um fator de tempo, ou seja, que os objetos se movem entre os espaços de partição.