Encontre k vizinhos mais próximos em uma esfera

7

Dado um conjunto $S$ do $N$ pontos em uma esfera e outro ponto $P$ na esfera, eu quero encontrar o $k$ pontos em $S$ que são as mais próximas (distância euclidiana ou grande círculo).

Estou disposto a fazer uma quantidade razoável de pré-cálculo. A solução deve ser exata e eficiente (mais rápido que o tempo linear).

data-structures computational-geometry nearest-neighbour JohnJ
fonte

11

Parece que esta pergunta é mais fácil de resolver no

R^{2}

$\mathbb{R}^2$ avião. Você já pensou nisso, e as respostas se traduzem facilmente na esfera e por que (não)? Por exemplo, você pode calcular

A (v) = {p | \forall_{w \in S} d (p, v) \leq d (p, w)}

$A(v)=\{p | \forall_{w\in S} d(p,v) \leq d(p,w)\}$ , que é um polígono convexo definido por linhas ortogonais às linhas entre

v

$v$ e

w

$w$ , e use isso junto com o particionamento de espaço para encontrar o vizinho mais próximo e trabalhe a partir daí.

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen a topologia esférica é importante, pois o caso de uso é um problema de GIS. Eu tenho o que acho que fornecerá uma solução funcional, mas estou curioso sobre a arte anterior. Obrigado!

JohnJ

11

John J. Lieuwe não estava dizendo que a topologia esférica não é importante; acho que ele está dizendo que existem muitas técnicas padrão para resolver isso em

R^{2}

$\mathbb{R}^2$ , e suspeito que ele esteja recomendando que você comece estudando essas abordagens padrão e verifique se elas podem ser modificadas um pouco para levar em conta que você está realmente em uma esfera, e não em uma

R^{2}

$\mathbb{R}^2$ .

DW

4

Use a abordagem de particionamento de espaço para procurar vizinhos mais próximos .

Por exemplo, uma abordagem é usar um $k$ -d árvore na superfície da esfera. Você pode expressar todos os pontos da esfera usando coordenadas esféricas : cada ponto da esfera tem coordenadas $(1,\theta,\phi)$ . Assim, temos um espaço bidimensional com coordenadas $(\theta,\phi)$ . Agora organize seus pontos usando um $k$ -d tree, onde estamos aqui $k=2$ dimensões. Existem algoritmos padrão para a pesquisa de vizinhos mais próximos em um $k$ -d árvore; heuristicamente, o tempo de execução esperado é $O(\lg N)$ .

Você precisará fazer pequenas modificações na estrutura de dados para refletir que as coordenadas "envolvem" o módulo $2\pi$ , mas isso não é difícil. A sub-rotina principal usada na pesquisa de vizinhos mais próximos em um $k$ -d árvore é: dado um ponto $P$ e uma região "retangular" $R$ , encontre a distância de $P$ para o ponto mais próximo $R$ . No seu caso, a região $R$ é $[\theta_\ell,\theta_u] \times [\phi_\ell, \phi_u]$ , ou seja, o conjunto de pontos $\{(1,\theta,\phi) : \theta_\ell \le \theta \le \theta_u, \phi_\ell \le \phi \le \phi_u\}$ . É fácil calcular a distância entre $P$ para o ponto mais próximo $R$ . Isso permitirá que você use o algoritmo padrão para a pesquisa de vizinhos mais próximos em um $k$ -d árvore.

Como alternativa, em vez de um $k$ -d tree, você pode usar qualquer outra árvore de particionamento de espaço binário ou pode olhar para árvores métricas , embora eu não tenha nenhum motivo para esperar que elas sejam significativamente melhores.

DW
fonte

1

Aqui estão os links para dois pacotes de software diferentes que abordam sua pergunta. Pode valer a pena estudar cada um para ver se os métodos que eles empregam atendem às suas necessidades:

(1) Matlab GridSphere . "Uma grade geodésica é uma grade uniforme sobre a superfície de uma esfera. O algoritmo é otimizado para uma grade gerada pelo GridSphere e não funciona em uma grade geodésica arbitrária".

(2) DarkSkyApp . "fornece pesquisas rápidas de vizinhos mais próximos em uma esfera ... bem testadas e funcionam corretamente, independentemente de onde as coisas estejam localizadas na terra."

Joseph O'Rourke
fonte

Encontre k vizinhos mais próximos em uma esfera

Respostas: