Algoritmo para encontrar pontos próximos?

Question

Dado um conjunto de vários milhões de pontos com coordenadas x, y, o que é o algoritmo de escolha para encontrar rapidamente os top 1000 pontos mais próximos de um local? "Rapidamente" aqui significa cerca de 100ms em um computador em casa.

A força bruta significaria fazendo milhões de multiplicações e, em seguida, classificá-los. Embora até mesmo um simples aplicativo Python poderia fazer isso em menos de um minuto, ele ainda é muito longo para uma aplicação interactiva.

A caixa delimitadora para os pontos será conhecido, então particionar o espaço em uma grade simples seria possível. No entanto, os pontos são distribuídos um pouco desigual, então eu suspeito que a maioria das quadrículas estaria vazio e, de repente alguns deles contêm uma grande parte dos pontos.

Edit: Não tem para ser exato, na verdade, pode ser muito impreciso. Não seria um grande negócio se o top 1000 são na verdade apenas alguns pontos aleatórios do topo 2000 por exemplo.

Edit:. Conjunto de pontos raramente muda

Answer 1

Que tal usar quadtree ?

Você dividir a área de retângulos, se a área tem baixa densidade de pontos, retângulos são grandes, e se a área tem alta densidade de pontos, retângulos será pequeno. Você recursivamente subdivida cada retângulo de quatro sub retângulos até retângulos são pequenos o suficiente ou conter alguns pontos suficientes.

Você pode então começar a olhar para os pontos em retângulos perto do local, e mover-se para fora até encontrar seus 1000 pontos.

código para isso pode ficar um pouco complexo, então talvez você deve tentar primeiro com a grade simples e ver se ele é rápido o suficiente.

Answer 2

Quadtrees são agradáveis, mas BSP árvores são garantidos para ser executado em O (log n) . Acho quadtrees requerem um volume delimitadora finito e e há alguns casos degenerados onde quadtrees falhar miseravelmente, como quando um grande número de pontos de ocupar o mesmo espaço relativamente pequeno.

Dito isto, Quadtrees são sem dúvida mais fácil de implementar e bastante eficaz na maioria das situações comuns. É o que os usos da UPS em seus algoritmos de roteamento, porque é inconvenientes não representam problemas significativos na prática, provavelmente porque as cidades tendem a ser distribuída ao longo da região de interesse.

Answer 3

Você quer usar uma estrutura como uma árvore Quad, ou um RTree. Estes são estruturas de índice multidimensionais.

A chave é usar um bom "curva espaço enchimento", que é o que ajuda a definir a proximidade de pontos. Uma curva espaço enchimento simples é uma Zorder, mas você estaria mais interessado em algo como uma curva de Hilbert.

http://en.wikipedia.org/wiki/Space_filling_curve

Eu não sei de qualquer implementações pré-embalados deste material. Eu recentemente implementado minha própria RTree em 2 dimensões que só suporta o carregamento granel e pesquisas (através de uma caixa delimitadora fornecido).

Uma desvantagem aqui é que os pontos têm de ser contido em uma região finita. Não sei que existem curvas espaço de enchimento que o trabalho para espaços que não são finitos, mas eu não sei nada sobre eles.

Answer 4

Além das sugestões de árvores Quadtree e BSP, você deve olhar para cima mais próximo vizinho pesquisa . A escolha do algoritmo é baseado em quantas vezes você está adicionando ao seu conjunto de dados de base. Se você está adicionando e removendo muitas vezes, soluções de árvores são superiores. Se os dados forem mais diagramas estáticos, buscando mais próximo vizinho e Voronoi pode ser muito mais rápido e escala melhor.

Answer 5

Se o conjunto de pontos raramente muda, você também pode considerar o uso de um diagrama de Voronoi. Eu não tenho certeza se isso ajuda encontrar o primeiro ponto mais rápido, mas deve torná-lo muito mais fácil encontrar os próximos 999 pontos.

Answer 6

Eu assumo os pontos estão em um banco de dados ou algum local indexada pesquisado? Se por isso deve ser muito rápido. Do ponto dado você pode ter uma gama de eixos X e Y e obter todas as localidades dentro desse intervalo (ou seja, especificar o canto superior esquerdo canto mais x (a) e y (b) e inferior mais à direita canto x (c) e y (d)).

Em seguida, faça uma consulta onde por pontos onde y> = b e Y <= d E x> = A e X <= c. esta será rápido supondo que você tem índices nas coordenadas xey seperatly. (Assumindo origem é 0,0 no canto superior esquerdo).

Você pode então aumentar (ou diminuir se o resultado é enorme) nesta faixa por z até que o número de pontos dentro do conjunto de resultados é> = 1000. Através de algumas corridas de teste você deve ser capaz de chegar a um desvio-padrão e outros números estatísticos que ajudarão a determinar o tamanho do retângulo para começar. Seu programa também pode sintonizar a sua auto para este com base nos resultados que ele recebe.

Depois de ter os dados brutos definir suas matemática simples bonito trabalhar fora a distância entre cada ponto e o ponto de origem.

Answer 7

eu sei que foi dito como não sendo o mais rápido se você quer resultados realmente muito rápido, vendo que eu encontrei este post do google eu pensei que eu gostaria de acrescentar a minha solução SQL que eu usei um tempo atrás na forma de um proc armazenados . Ele procura por locais fechar pelo um coord e devolve-os por distância.

Espero que ajude alguém:)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

Nota: Eu já disse que isso não é a melhor solução para Esta questão simplesmente talvez para alguém que achei essa mensagem em google como eu