ponto mais próximo para um determinado ponto

Question

Eu tenho um K conjunto de pixels selecionados aleatoriamente em uma imagem 2D. Para todos os outros pixel da imagem que eu preciso para descobrir qual pixel no conjunto K é o mais próximo a ele (usando o sqrt padrão (dx ^ 2 + dy ^ 2) medida de distância). Estou ciente de que pode haver mais de uma solução para cada pixel. Obviamente, isso pode ser feito pela força bruta contra cada pixel no conjunto, mas eu prefiro evitar isso, pois não é eficiente. Qualquer outra sugestão boa?

Felicidades.

Answer 1

Não se esqueça que você não precisa se preocupar com a raiz quadrada.

Se você quiser apenas para encontrar o mais próximo (e não é a distância real) apenas uso dx^2 + dy^2, o que lhe dará a distância quadrado para cada item, que é tão útil.

Se você não tem nenhuma estrutura de dados envolvendo esta lista de pixels, você terá de teste apenas contra todos eles.

Se você tem alguma flexibilidade, há um monte de boas maneiras de reduzir a carga de trabalho. Faça um Quadtree , ou mantê-lista ordenada dos pixels (classificado por x e ordenadas por y) restringir a pesquisa mais rapidamente.

Answer 2

Eu tenho que concordar com jk e Ewan com fazer um Voronoi Diagram . Isto irá dividir o espaço em polígonos. Cada ponto no K terá um polígono que descreve todos os pontos que estão mais próximos a ele. Agora, quando você recebe uma consulta de um ponto, você precisa encontrar em que polígono ela se encontra. Este problema é chamado Ponto Localização e pode ser resolvido através da construção de um trapezoidal Mapa .

jk já ligado à criação do Voronoi Diagram usando o Fortune algoritmo que leva o (n log n) passos computacionais Custos o espaço (n). Este site mostra como fazer um mapa trapezoidal e como consultá-lo. Você também pode encontrar alguns limites lá:
tempo de criação esperado: O (n log n)
Espera complexidade de espaço: O (n)

Mas o mais importante, o tempo de consulta esperado: O (log n). Este é (teoricamente) melhor do que O (vn) da árvore-kd.

A minha fonte (excepto nos links acima) é: Geometria Computacional:. algoritmos e aplicações , capítulos seis e sete

Lá você encontrará informações detalhadas sobre as duas estruturas de dados (incluindo provas detalhadas). A versão do Google livros tem apenas uma parte do que você precisa, mas os outros links deve ser suficiente para a sua finalidade. Basta comprar o livro se você estiver interessado nesse tipo de coisa (que é um bom livro).

Answer 3

A construção de Voronoi Diagrams é um ramo da Computational Geometry . A construção de Delaunay Triangulações envolve considerações semelhantes. Você pode ser capaz de se adaptar um dos seguintes Delaunay algoritmos para atender às suas necessidades.

• algoritmos Virar
• Incremental
• Dividir para conquistar
• Sweepline

Answer 4

Coloque os pontos em uma árvore KD, após este é muito rápido para encontrar o vizinho mais próximo. Consulte este artigo na wikipedia para mais detalhes.

Answer 5

Esta é a chamada busca vizinho mais próximo. Donald Knuth chamou-lhe o problema pós-office.

Há uma série de soluções:. Busca linear, localidade hashing sensível, arquivos vector de aproximação e particionamento de espaço

pesquisando aqueles devem ajudar.

Answer 6

o que você está tentando fazer é construir um voronoi diagrama isso pode ser feito em O ( n log n) usando um plano de varrimento

Answer 7

Outra dica:. A distância é sempre maior ou igual a cada diferença de cotas, e sempre menor ou igual à sua soma, ou seja

d >= dx, d >= dy, d <= dx + dy.

Isso pode ajudá-lo a fazer a triagem de forma mais eficiente.

Answer 8

Dependendo de como densamente este gráfico é preenchido com pixels, você pode ser melhor fora apenas procurando para fora do seu pixel de origem.

I programado algo assim para uma emulação de terminal gráfico. O que eu acabei fazendo era programar um padrão de pesquisa na forma de uma espiral quadrada-sided que cresceu a partir do ponto central, e eu deixá-lo crescer até atingir algo. Isso foi suficientemente rápido para o efeito, mesmo em uma CPU de idade.