Como funcionam as formas (retângulos) em árvores quad?

10

Foi-me dito que uma árvore quádrupla é a estrutura de dados ideal para o meu jogo, mas estou tendo problemas para entender como exatamente as formas funcionam dentro das árvores quádruplas.

Estou fazendo isso em JavaScript, mas acho que essas perguntas podem se aplicar a árvores em qualquer idioma.

Eu acho que a maioria entender como básica (x, y) pontos e de inserção ponto de obras em árvores quad, e que eu poderia fazê-lo no papel.

Aqui está um JSfiddle da minha experiência com pontos.

pontos de árvore quad

Além de um caso, meus testes com pontos estão funcionando conforme o esperado.

Mas minha confusão começa quando formas como retângulos estão envolvidos. Quando você está recuperando de uma árvore quádrupla com formas, ele verifica cada ponto da forma e em quais nós eles se enquadram? E como as inserções de formas funcionam mesmo quando aceitam parâmetros (x, y, largura, altura) para cada forma? Ele usa a largura / altura do ponto de partida para calcular outros pontos de canto, que são dispensados ​​nos nós apropriados? Se uma forma inserida se estender em quatro nós, os dados dessa forma serão salvos nos quatro nós?

E quando um método de recuperação aceita uma forma como parâmetro (x, y, largura, altura), o que realmente está acontecendo? É primeiro ver em que nós a forma se estenderia se ela fosse inserida e depois recuperar todos os objetos desses nós?

Eu tenho um JSfiddle trabalhando com formas , mas estou totalmente confuso com os resultados dos meus testes. Estou recebendo objetos duplicados sendo devolvidos!

formas de árvore quad

Por exemplo, o quadrado vermelho é um equivalente desenhado dos parâmetros que estou inserindo no meu método de recuperação. Eu pensaria que, uma vez que esse quadrado vermelho abrange todos os quatro nós, ele deve retornar todos os objetos no quad tree! Mas isso não acontece, e estou tendo problemas para racionalizar o que retorna. Eu tenho vários outros testes atualmente comentados, mas você pode cancelar o comentário e executá-los para obter resultados mais confusos!

Por exemplo, se eu quiser retornar todos os pontos em uma árvore quádrupla, como eu faria isso? Um método de recuperação usando uma forma de todo o tamanho dos limites? Por exemplo, recuperar (0, 0, canvas.width, canvas.height)?

A biblioteca JavaScript QuadTree que estou usando já foi referida por várias outras fontes, portanto, presumo que a implementação real seja correta e respeitável.

Penso que grande parte da minha confusão pode resultar de um mal-entendido da terminologia de árvores quádruplas. Como, por que eles dizem limites em vez de dimensões, quando um "ponto" também tem parâmetros de largura / altura? É uma questão de convenção / mão curta, ou são conceitos completamente diferentes?

Obrigado pelo seu tempo!

user2736286
fonte
Eles são armazenados na árvore quádrupla normalmente, por sua posição. Normalmente, eles estão no centro, mas podem estar no canto, conforme você definiu. Sua pergunta pode ser uma duplicata desta: QuadTree: armazena apenas pontos ou regiões?
Michaelhouse
Eu li essa pergunta, mas ainda não entendi completamente as respostas :(. "Você deve armazená-lo no menor nó que o contém completamente - mesmo que isso exceda a capacidade (use um contêiner redimensionável)." - Quando ele diz que o nó mais pequeno que o contém COMPLETAMENTE, se o objeto for muito grande, esse nó geralmente não seria um nó não-folha? Como em um nó superior que consiste em apenas outros nós? Isso não parece certo me, pois isso significaria o nó contendo teria 1 folha e os 4 nós de menores dentro dele.
user2736286
11
@ user2736286 Se você olhar para o código da lib quadtree (não é muito longo), poderá ver que ela armazena retângulos em nós de nível superior para evitar que eles se espalhem pelas bordas dos nós. Veja as referências ao _stuckChildrencampo no código. Você também pode ver isso no exemplo "recuperando itens com limites" - sempre destaca em vermelho os nós que se estendem pelas bordas dos nós em que você clicou, até o nó raiz.
Nathan Reed
@ user2736286 Além disso, a lib quadtree parece ter um erro na recuperação de itens com limites - se você der um retângulo de consulta que se estende por algumas bordas do nó, ele não retornará todas as rects nos nós tocados pela consulta. Você pode ver isso facilmente também em "recuperando itens com limites", clicando próximo às bordas dos nós.
Nathan Reed
@NathanReed Anteriormente, tentei compreender o código, mas não sou qualificado o suficiente para entendê-lo sem uma base conceitual. Graças ao pseudocódigo de John McDonald, agora entendo como os retângulos são inseridos nos nós, mas acho que ainda não estou claro como a recuperação funciona. Quanto aos "recuperando itens com limites" - estou totalmente confuso com o exemplo. Por exemplo, quando clico em um retângulo que se encaixa perfeitamente em um dos menores nós, por que todas as outras rects fora desse nó também são destacadas?
user2736286

Respostas:

10

Quadríceps geralmente armazenam e recuperam retângulos. Um ponto é um caso específico em que largura e altura são zero. A lógica a seguir é usada para encontrar o local para novos retângulos na árvore, começando com o nó raiz:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Observe que os retângulos podem ser armazenados em qualquer profundidade, não precisa ser um quad-leaf. Se o retângulo ultrapassar o limite no nível da raiz, o quad raiz armazenará o retângulo.

Por exemplo, o quadrado vermelho é um equivalente desenhado dos parâmetros que estou inserindo no meu método de recuperação. Eu pensaria que, uma vez que esse quadrado vermelho abrange todos os quatro nós, ele deve retornar todos os objetos no quad tree! Mas isso não acontece, e estou tendo problemas para racionalizar o que retorna.

Ao consultar o quadtree, ele retornará apenas retângulos contidos na consulta. No seu exemplo, você força cada um dos quatro quadríceps filhos a serem vistos com mais detalhes, porque o retângulo de consulta vermelho cruza cada quadri filho. Como os filhos não têm mais filhos, cada um dos retângulos nesses quadríceps filhos será comparado ao retângulo vermelho. Como nenhum dos retângulos da árvore colide com o retângulo de consulta vermelho, nada deve ser retornado.

Você realmente começa a ver os benefícios dos quadríceps quando tem muitos objetos e muito espaço para os objetos existirem em comparação com a (s) área (s) de consulta. Nesses casos, uma pequena área de consulta pode eliminar rapidamente grandes pedaços da árvore quádrupla. Somente quads que se cruzam com o retângulo de consulta serão vistos com mais detalhes.

EDITAR

A recuperação geralmente é feita da seguinte maneira:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

Na sua biblioteca, no entanto, não parece verificar se os retângulos que estão retornando se cruzam com a consulta; portanto, você precisará adicioná-lo.

John McDonald
fonte
Depois de examinar sua biblioteca com mais detalhes, ela retornará uma lista de todos os possíveis candidatos a colisão para o retângulo de consulta que você especificar. Parece que é seu trabalho comparar o retângulo de consulta com cada candidato para ver se há uma colisão real. A maioria das bibliotecas faz o último passo para você e apenas retorna as colisões reais com a área de consulta. Portanto, tudo que você precisa fazer é adicionar alguma lógica ao seu retrievemétodo para remover a lista. Você pode ver o que está fazendo um pouco mais claramente aqui: mikechambers.com/html5/javascript/QuadTree/examples/…
John McDonald
11
@ user2736286 Caso você não tenha entendido, é importante tomar nota da recursão nas funções de Consulta e Armazenamento que JohnMcDonald escreveu. Não fará muito sentido se você não conseguir essa parte. Para ambos, cada recursão se aprofunda na árvore, ou seja, nos galhos e finalmente nas folhas.
TASagent
Obrigado John, seu pseudo-código é muito útil. Quando você diz "if (queryRect cruza com os limites childNode)", isso significa basicamente se o queryRect está contido nos limites - parcial ou totalmente? Só quero ser 100% claro. Além disso, no exemplo "recuperar item por limites" que está sendo discutido, tenho uma imagem do resultado do meu clique. Pic O ponto azul é onde eu cliquei. Então, por que apenas os dois retângulos dentro desse nó são destacados? Por que os retângulos distantes dele também são destacados? Eu acho que é isso que realmente está me confundindo.
user2736286
Parcial ou completo. Se os dois tocarem, ou um deles estiver completamente contido pelo outro. Você quer ler o wiki em Quadtrees , mas tirei sua foto e a codifiquei por cores para representar os diferentes limites filhos. Todos os retângulos azuis estão se cruzando com os limites dos primeiros quadríceps filhos, sendo magenta uma camada mais profunda e verde uma camada mais profunda ainda. Retângulos vermelhos se cruzam com o quadriculado clicado. Você retorna biblioteca todos os retângulos sobre limites criança mais todas contidas no quad criança final (vermelho): i.imgur.com/InB8KBj.png
John McDonald
Ok, então eu tentei o meu melhor para repassar o código fonte da lib e finalmente entendo o comportamento de stuckChildren, e que todos os retos extras na minha foto são simplesmente os stuckChildren. Originalmente, eu pensava que qualquer rects abrangendo vários nós teria seus dados duplicados e inseridos em cada nó menor. Agora percebo que stuckChildren não é inserido nos nós em que se estende, mas simplesmente permanece no nó que o contém, e é por isso que também preciso verificar todos os nós pais, e não apenas o menor nó que contém minha consulta correta. Obrigado pela foto; faz muito mais sentido agora :)
user2736286