Encontre vizinho mais próximo de um raio

Question

Eu tenho um conjunto de pontos a no meu espaço (pontos geográficos, mas posso assumir que eles estão em um plano 2D).

Eu tenho outro conjunto de pontos b .

Para cada ponto em b Eu quero encontrar todos os pontos em um dentro de um raio r com centro no ponto considerado de B set.

Eu fiz isso com o Kdtree, isso me fornece um algoritmo muito rápido e fácil para criar a estrutura de dados e encontrar vizinhos mas não encontrar cada ponto em um raio porque pode evitar um caminho que contém elemento no meu raio, mas não no mesmo subconjunto do Centro RADIUS.

Exemplo mínimo de kdtree falhando :

Ao explorar o Kdtree, o ponto de destino (vermelho) está sob a linha do ponto número 1. Isso procederá à exploração do ponto sob a linha, isso perderá o ponto real dentro do raio de ponto vermelho.

Qual algoritmo ou estrutura de dados permite 100% de correção?

Eu sei com certeza vou seduzir, mas eu procuro um equilíbrio entre a velocidade de pesquisa e a correção total.

Answer 1

A árvore K-D é uma boa estrutura de dados para resolver isso.No entanto, você não pode aplicar cegamente o procedimento de pesquisa apenas para o ponto central, você deve ser um pouco mais inteligente.

Ao procurar a árvore KD para seus pontos, toda vez que você deve escolher a criança esquerda ou direita para pesquisar, verifique se o plano de divisão é à esquerda do seu círculo, interseja ou é à direita do círculo.

Se o plano de divisão estiver à esquerda do seu círculo, você deve continuar pesquisando na criança certa e vice-versa.No entanto, quando o plano de divisão intersecta seu círculo, você deve pesquisar ambos crianças.