Em 2D, como encontro eficientemente o objeto mais próximo de um ponto?

35

Eu tenho um mecanismo de jogo considerável e gostaria de um recurso para encontrar o mais próximo de uma lista de pontos.

Eu poderia simplesmente usar o teorema de Pitágoras para encontrar cada distância e escolher a mínima, mas isso requer iteração em todas elas.

Eu também tenho um sistema de colisão, onde essencialmente transformo objetos em objetos menores em uma grade menor (como um minimapa) e somente se os objetos existirem no mesmo espaço de grade eu verifico se há colisões. Eu poderia fazer isso, apenas aumentar o espaçamento da grade para verificar a proximidade. (Em vez de verificar todos os objetos.) No entanto, isso exigiria configuração adicional na minha classe base e desorganizaria o objeto já confuso. Vale a pena?

Existe algo eficiente e preciso que eu possa usar para detectar qual objeto está mais próximo, com base em uma lista de pontos e tamanhos?

ultifinito
fonte
Armazene versões quadradas das posições x e y para que você possa executar o teorema de pitágoras sem precisar fazer o sqrt caro no final.
11131 Jonathan Connell
3
Isso é chamado de pesquisa de vizinho mais próximo . Há muita escrita na internet sobre isso. A solução usual é usar algum tipo de árvore de particionamento de espaço .
BlueRaja - Danny Pflughoeft 01/07

Respostas:

38

O problema com um quad / octree nas pesquisas de vizinhos mais próximos é que o objeto mais próximo pode estar localizado do outro lado da divisão entre os nós. Para colisões, tudo bem, porque se não estiver no nó, não nos importamos com isso. Mas considere este exemplo 2D com um quadtree:

Exemplo de Quadtree

Aqui, mesmo que o item preto e o item verde estejam no mesmo nó, o item preto está mais próximo do item azul. A resposta do ultifinitus pode garantir apenas ao vizinho mais próximo, apenas todos os itens da sua árvore são colocados no menor nó possível que o possa conter ou em um único nó - isso leva a quadrtrees mais ineficientes. (Observe que existem muitas maneiras diferentes de implementar uma estrutura que poderia ser chamada de quad / octree - implementações mais rigorosas podem funcionar melhor neste aplicativo.)

Uma opção melhor seria uma árvore kd . As árvores Kd têm um algoritmo de pesquisa do vizinho mais próximo muito eficiente que você pode implementar e pode conter qualquer número de dimensões (daí as dimensões "k").

Uma ótima e informativa animação da Wikipedia: kd-tree pesquisa do vizinho mais próximo

O maior problema com o uso de árvores kd, se bem me lembro, é que elas são mais difíceis de inserir / remover itens enquanto mantêm o equilíbrio. Portanto, eu recomendaria o uso de uma árvore kd para objetos estáticos, como casas e árvores que são altamente equilibradas, e outra que contém jogadores e veículos, que precisam ser equilibrados regularmente. Encontre o objeto estático mais próximo e o objeto móvel mais próximo e compare esses dois.

Por fim, o kd-trees é relativamente simples de implementar, e tenho certeza de que você pode encontrar uma infinidade de bibliotecas C ++ com eles. Pelo que me lembro, as árvores R são muito mais complicadas e provavelmente exageram se tudo o que você precisa é de uma simples pesquisa no vizinho mais próximo.

dlras2
fonte
11
Ótima resposta, pequenos detalhes "e apenas garantir que o vizinho mais próximo apenas todos os itens de sua árvore sejam colocados no menor nó possível", eu quis dizer na minha resposta, iterando todos os itens nos mesmos e nos vizinhos, para que você faça um loop sobre 10 em vez de 10.000.
Roy T.
11
Muito verdade - suponho que "apenas" fosse uma palavra bastante dura. Definitivamente, existem maneiras de persuadir os quadríceps nas pesquisas de vizinhos mais próximos, dependendo de como você os implementa, mas se você não os estiver usando por outros motivos (como detecção de colisão), eu ficaria com a kd-tree mais otimizada.
#
Eu queria observar que fiz uma implementação que lida com o problema do preto verde azul. Verifique o fundo.
precisa saber é o seguinte
18

sqrt() é monotônico, ou preserva a ordem, para argumentos não negativos, portanto:

sqrt(x) < sqrt(y) iff x < y

E vice versa.

Portanto, se você quiser comparar apenas duas distâncias, mas não estiver interessado em seus valores reais, basta recortar o sqrt()passo do material de Pitágoras:

pseudoDistanceB = (A.x - B.x + (A.y - B.y
pseudoDistanceC = (A.x - C.x + (A.y - C.y
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

Não é tão eficiente quanto a coisa da árvore de outubro, mas é mais fácil de implementar e aumenta a velocidade pelo menos um pouco

HumanCatfood
fonte
11
Essa métrica também é chamada de distância euclidiana ao quadrado .
31414 moooeeeep
10

Você precisa fazer o particionamento espacial; nesse caso, você cria uma estrutura de dados eficiente (geralmente uma octree). Nesse caso, cada objeto está dentro de um ou mais espaços (cubos). E se você souber em quais espaços você está, pode procurar O (1) quais espaços são seus vizinhos.

Nesse caso, o objeto mais próximo pode ser encontrado iterando primeiro todos os objetos em seu próprio espaço, procurando qual deles é o mais próximo. Se não houver ninguém lá, você poderá verificar seus primeiros vizinhos, se não houver ninguém, poderá verificar seus vizinhos, etc.

Dessa forma, você pode encontrar facilmente o objeto mais próximo sem precisar percorrer todos os objetos do seu mundo. Como sempre, esse ganho de velocidade exige um pouco de contabilidade, mas é realmente útil para todos os tipos de coisas; portanto, se você tem um mundo grande, definitivamente vale a pena implementar o particionamento espacial e um octree.

Como sempre, consulte também o artigo da wikipedia: http://en.wikipedia.org/wiki/Octree

Roy T.
fonte
7
@ultifinitus Para adicionar isso: Se o seu jogo é 2D, você pode usar o QuadTrees em vez do Octrees.
TravisG
1

Talvez tente organizar seus dados espaciais em um RTree, que é como uma btree para coisas no espaço e permite consultas como "N vizinhos mais próximos" etc ... http://en.wikipedia.org/wiki/Rtree

Patrick Hughes
fonte
0

Aqui está minha implementação em java para obter a mais próxima de um quadTree. Ele lida com o problema que o dlras2 está descrevendo:

insira a descrição da imagem aqui

Eu acho que a operação é realmente eficiente. Baseia-se na distância de um quad para evitar a busca em quads mais além da corrente mais próxima.

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

public T getClosest(float x, float y) {

    Closest closest = new Closest();
    getClosest(x, y, closest);

    return closest.item;
}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

protected void getClosest(float x, float y, Closest closestInfo) {


    if (hasQuads) {

        // we have no starting point yet
        // so get one
        if (closestInfo.item == null) {
            // check all 4 cause there could be a empty one
            for (int i = 0; i < 4; i++) {
                quads[i].getClosest(x, y, closestInfo);
                if (closestInfo.item != null) {
                    // now we have a starting point
                    getClosest(x, y, closestInfo);
                    return;
                }

            }
        }
        else {

            // we have a item set as closest
            // we should check if this quad is
            // closer then the current closest distance
            // let's start with the closest from index

            int closestIndex = getIndex(x, y);

            float d = quads[closestIndex].bounds.distToPointSQ(x, y);

            if (d < closestInfo.dist) {
                quads[closestIndex].getClosest(x, y, closestInfo);
            }

            // check the others
            for (int i = 0; i < 4; i++) {
                if (i == closestIndex) continue;

                d = quads[i].bounds.distToPointSQ(x, y);

                if (d < closestInfo.dist) {
                    quads[i].getClosest(x, y, closestInfo);
                }

            }

        }

    }
    else {

        for (int i = 0; i < items.size(); i++) {

            T item = items.get(i);

            float dist = distSQ(x, y, getXY.x(item), getXY.y(item));

            if (dist < closestInfo.dist) {
                closestInfo.dist = dist;
                closestInfo.item = item;
                closestInfo.tree = this;
            }

        }
    }

}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


class Closest {

    QuadTree<T> tree;
    T item;
    float dist = Float.MAX_VALUE;

}
clankill3r
fonte
ps Ainda acho que é melhor usar uma árvore kd ou algo assim, mas isso pode ajudar as pessoas.
precisa saber é o seguinte
também olhar para isto: bl.ocks.org/llb4ll/8709363
clankill3r