Como faço para determinar qual cuboids um ponto está em sem iteração sobre todos eles?

Question

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.)

Answer 1

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 .

Answer 2

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.