Estou desenvolvendo um quadtree para rastrear objetos em movimento para detecção de colisão. Cada objeto tem uma forma delimitadora, digamos que sejam todos círculos. (É um jogo 2D de cima para baixo)
Não tenho certeza se devo armazenar apenas a posição de cada objeto ou toda a forma delimitadora.
Se trabalhar com pontos, a inserção e a subdivisão são fáceis, porque os objetos nunca abrangem vários nós. Por outro lado, uma consulta de proximidade de um objeto pode perder colisões, porque não levará em consideração as dimensões dos objetos. Como calcular a região da consulta quando você tem apenas pontos?
Se estiver trabalhando com regiões, como lidar com um objeto que abrange vários nós? Ele deve ser inserido no nó pai mais próximo que o contém completamente, mesmo que isso exceda a capacidade do nó?
Obrigado.
Você deve armazená-lo no menor nó que o contém completamente, mesmo que isso exceda a capacidade (use um contêiner redimensionável).
fonte
Eu adicionaria isso como um comentário em resposta à resposta de @Nathan Reed, exceto que é muito grande para ser um comentário, e talvez seja, de qualquer forma, digno de ser uma resposta separada.
Estávamos fazendo exatamente o que foi proposto em sua resposta e, de fato, temos comentários na fonte que aponta para esta página. Na maioria das vezes, ele funcionou extremamente bem, exceto que a cada dois ou três meses, perdemos um servidor aleatoriamente que ficou sem resposta devido à grande duração das consultas de pesquisa.
A causa raiz do problema chamou minha atenção ao fazer uma verificação de desempenho para tentar descobrir o que estava causando isso. É provável que seja apenas uma preocupação se você permitir objetos sobrepostos. No nosso jogo, sim, e no pior dos casos, ocasionalmente, isso leva a um aumento na performance.
Tivemos um caso de borda em que cerca de 100 objetos, todos com discos delimitadores, foram agrupados em uma proximidade muito próxima. Isso levou ao problema de um pico muito profundo na árvore, porque chegamos ao ponto em que os objetos eram maiores que a área coberta pelos nós quadtree, de modo que cada novo objeto aparecia em vários nós, levando a uma subdivisão maciça do árvore, danificando o problema fora de controle.
A conclusão é que, se você permitir que as regiões de objetos se sobreponham, fique atento às coisas, se você conseguir agrupamentos apertados de objetos, para garantir que sua árvore não fique muito profunda.
A solução que estou investigando atualmente é armazenar objetos como pontos e, ao fazer uma pesquisa, aumentar os limites do retângulo de pesquisa pelo raio máximo armazenado na árvore. Isso deve funcionar para nós, porque a árvore é uma pesquisa de primeira passagem e, em seguida, fazemos uma verificação de intervalo baseada em círculo real, juntamente com algumas outras verificações de critérios, para que os alertas falsos extras sejam filtrados.
Sua milhagem real pode variar.
fonte