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

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?

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:

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:

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.

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

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

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

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:

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;

}