Ao colocar objetos geométricos em um quadtree (ou octree), você pode colocar objetos maiores que um único nó de várias maneiras:
- Colocar a referência do objeto em todas as folhas nas quais está contido
- Colocar a referência do objeto no nó mais profundo para o qual está totalmente contido
- Ambos # 1 e # 2
Por exemplo:
Nesta imagem, você pode colocar o círculo nos quatro nós das folhas (método 1) ou apenas no nó raiz (método 2) ou em ambos (método 3).
Para fins de consulta ao quadtree, qual método é mais comum e por quê?
graphics
data-structures
computational-geometry
nsantorello
fonte
fonte
Respostas:
Supondo que você esteja armazenando uma referência, não o objeto em si, pode fazer sentido fazer isso de maneira diferente, dependendo do seu aplicativo.
Por exemplo, se você estivesse computando colisões com esse círculo (sólido) e a colisão ocorresse no canto inferior esquerdo, seria mais fácil se você tivesse acesso a toda geometria nessa folha diretamente dessa folha (método nº 3) (sem ter que percorrer a árvore para cima e determinar a geometria herdada). Mas, digamos que você estivesse usando quadríceps para desenhar geometria, você desejaria usar o método nº 1, porque faz sentido desenhar algo no nó para o qual está totalmente contido (seria mais difícil descobrir qual parte desenhar para cada nó da folha e onde).
Quanto ao que é mais comum, minha única experiência com quadríceps é escrever uma simulação de corpo n onde os objetos geométricos eram realmente apenas pontos que não tinham área, então não posso responder isso definitivamente.
fonte
Uma das vantagens de um Quadtree é que você não precisa dividir um nó em seus nós filhos, se todos os nós filhos contiverem as mesmas informações. Isso pode economizar bastante memória e acelerar o processamento.
Seguindo esse princípio, acho que faz mais sentido armazená-lo apenas no nó raiz (método # 2). Isso poderia economizar bastante memória e acho que também facilitaria o processamento. Por exemplo, se você tentasse encontrar interseções do círculo com uma linha que atravesse três dos nós da folha, seria necessário calcular a interseção separadamente para cada nó da folha ou lembre-se de que você já cruzou com esse círculo.
Por outro lado, se você tiver objetos em nós folha, isso poderá ajudá-lo a eliminar falsos positivos (objetos que você deve verificar se há interseção, porque eles estão no nó correto, mas na verdade não se cruzam).
Então, acho que ambas as abordagens têm seus usos e não tenho certeza de como escolher qual usar.
Eu provavelmente não usaria a abordagem nº 3, porque não vejo nenhum ponto positivo sobre isso.
fonte