Melhor Performance-Critical algoritmo para resolver vizinho mais próximo

Question

Nós temos uma lista de pares x, y. Cada par representa um ponto em um espaço 2D. Eu quero encontrar o ponto mais próximo nesta lista, a uma xq ponto específico, yq. Qual é o melhor algoritmo de desempenho crítico para este problema? Lisp de pontos não vai mudar; o que significa que não precisa executar a inserção e exclusão. Quero apenas para encontrar o vizinho mais próximo de um xq alvo, ponto yq neste conjunto.

Editar 1: Obrigado a todos! Como Stephan202 adivinhou corretamente, eu quero fazer isso várias vezes; como uma função. Uma lista não é necessariamente classificadas (Na verdade eu não entendo como isso pode ser resolvido? Como uma tabela com uma chave primária de 2 colunas A e Y? Se isso ajuda, então eu vou classificá-lo).

I vai construir a estrutura de dados com base na lista de um tempo, e então vai utilizar esta estrutura de dados gerado na função (se este processo em si é relevante).

Obrigado Jacob; Parece que a estrutura de dados KD-Tree é um bom candidato para ser a resposta (E eu sinto que é. Eu irei atualizar quando eu obter alguns resultados relevantes).

Edit 2: Eu descobri que, este problema é chamado de "vizinho mais próximo"

!

Editar 3: Primeiro título era "Em Busca de um algoritmo (do Ordenamento-Consultando e Ordenamento-Indexing) (vizinho mais próximo)"; Tenho escolheu um novo título: "Algoritmo de Melhor Performance-crítica para resolver vizinho mais próximo". Desde que eu não deseja executar a inserção e operação de exclusão em meus dados iniciais e eu quero apenas o mais próximo deles para um novo ponto (que não vai ser inserido), eu escolhi (atualmente) trabalhando em KD-árvores. Obrigado a todos!

Answer 1

Como Stephan202 observado, se você pretende encontrar o mais próximo do jogo para mais de um ponto, você deve usar uma árvore.

Gostaria de recomendar um KD-árvore, cuja implementação pode ser facilmente encontrado em vários pacotes como OpenCV 2.0 . Ou você poderia implementar um você mesmo!

EDIT: eu tinha uma pergunta sobre implementações kd-árvores aqui -. pode ser útil

EDIT: KD-árvores têm sido amplamente utilizados com sucesso para pesquisas NN :) - Além disso, se você estiver disposto a aceitar correspondências aproximadas, você pode usar Biblioteca rápido para aproximado mais próxima neigbor (FLANN) . A implementação FLANN está presente em OpenCV 2,0 .

Se você não quer respostas aproximadas você pode ajustar os parâmetros de Flann para pesquisar a árvore inteira.

Answer 2

Se o ponto de consulta (xq, yq) varia e a lista não faz, você precisa calcular o Voronoi diagrama da lista de pontos. Isto lhe dará um conjunto de polígonos ou "células" (alguns dos quais são infinitos); cada polígono corresponde a um ponto da lista original, chamado o "Site" da célula. Qualquer ponto que fica inteiramente dentro de um polígono é mais perto do local desse polígono que é para os outros sites na lista original. Qualquer ponto de uma fronteira entre dois polígonos mentiras igualmente distantes de cada site.

Uma vez que você chegou tão longe, você precisa de uma maneira fácil de descobrir qual o polígono em que está. Isto é conhecido como o ponto problema de localização .

Um realmente, realmente bom livro para este tipo de coisa é Geometria Computacional: Algoritmos e Aplicações . Discutem tanto o cálculo diagrama de Voronoi e o método trapezoidal laje de localização do ponto em pormenor.

Se você não quiser fazer o código você mesmo, e você não deve, em seguida, tentar obter uma biblioteca como CGAL que vai fazer a maior parte do trabalho para você. Isso provavelmente se aplica à resposta KD-árvore bem, mas eu não especificamente saber.

Answer 3

Você precisa de um espacial índice .

Se você rolar o seu próprio, você pode fazer muito pior do que escolher o R-Tree ou Quad-árvores algoritmos.

Answer 4

Eu iria com um quadtree. É a estrutura espacial mais simples. Em 2 dimensões Gostaria geralmente recomendam quadtree vez de kd-árvore, porque é mais simples, mais rápido. O seu inconveniente é mais consumo de memória, se o número de dimensões é elevado, mas no caso de 2 dimensões, a diferença não é significativa.

Existe um truque de otimização bom ponto se suas coordenadas estão flutuando digitado: Em uma consulta primeiro você tem que encontrar a folha-nó que contém o ponto para o qual é pedido o ponto mais próximo. Para fazer isso você terá que ir na árvore a partir da raiz para a folha - em cada iteração decidir qual criança-nó para pisar. Armazenar os identificadores / endereços das crianças-nodes em uma matriz 4 de tamanho na estrutura Node. Digitalizar as coordenadas do ponto no algoritmo de consulta. Em seguida, você será capaz de encontrar o sub-node adequada apenas por indexar a matriz por 2 bits adequados das coordenadas dos pontos digitalizados. Digitalização é rápido: implementá-lo com um simples static_cast.

Mas primeiro implementar o quadtree sem otimização, porque é fácil fazer um bug com o bit-operações. Mesmo sem essa otimização, ainda será a solução mais rápida.

Answer 5

Iterate através de todos os outros pontos utilizando a fórmula de distância para encontrar a distância mínima entre Q (xq, yq).

No entanto, você não tenha dado informações suficientes para uma resposta de desempenho crítico.

Por exemplo, se Q é um ponto muito comum, você pode querer calcular a distância até Q e armazená-lo com cada ponto.

Segundo exemplo, se você tem um grande número de pontos, você pode organizar os pontos em seções e começar com pontos apenas na mesma seção e seções adjacentes para a seção que contém Q.