Atualmente, estou escrevendo um KDTree para um mecanismo de física (projeto Hobby).

O KDTree não contém pontos. Em vez disso, ele contém caixas delimitadoras de eixo alinhadas que limitam os diferentes objetos no ambiente.

Meu problema é decidir como dividir os nós do KDTree quando eles ficarem cheios. Estou tentando 2 métodos:

Método1: sempre divida o nó exatamente ao meio no eixo maior.

Isso tem a vantagem de uma árvore bem espaçada.Grande desvantagem: se os objetos estiverem concentrados em uma pequena área do nó, serão criadas subdivisões redundantes. Isso ocorre porque todos os volumes são divididos exatamente ao meio.

Método2: Encontre a área do nó que contém objetos. Divida o nó no plano que divide a área ao meio no seu maior eixo. Exemplo - Se todos os objetos estiverem concentrados na parte inferior do nó, ele será dividido longitudinalmente, dividindo a parte inferior em duas.

Isso resolve o problema com o método acimaAo indexar algo que existe no mesmo plano (terreno, por exemplo), ele cria nós longos e estreitos. Se devo adicionar outros objetos posteriormente que não estão no mesmo plano, esses nós alongados fornecem uma indexação muito ruim.

Então, o que eu estou procurando aqui é uma maneira melhor de dividir meu nó KD-Tree. Considerando que este será um mecanismo de física, a decisão precisa ser simples o suficiente para ser tomada em tempo real.