Encontrar Pontos Remotos em 2D

Question

Eu tenho um conjunto de pontos no infinito (bem, precisão dupla) plano 2D.

Dado o casco convexo para este conjunto, como pode encontrar alguns pontos sobre o dentro do casco convexo que são relativamente longe de todos os pontos no conjunto de entrada?

Na imagem abaixo, os pontos negros são parte do conjunto original ea área tracejada representa o espaço ocupado por todos os pontos se nós "crescer"-los com raio R.

Os pontos laranja são exemplos do que eu gostaria de ter. Realmente não importa onde exatamente eles são, contanto que eles são relativamente longe de todos os pontos negros.

ponto mais Pesquisa http: //en.wiki.mcneel. com / content / upload / images / point_far_search.png

---

Update: Usando um algoritmo de Delaunay para encontrar grandes triângulos vazios parece ser uma excelente abordagem para isso: Delaunay Solution http://en.wiki.mcneel.com/content/ upload / images / DelaunaySolutionToInternalFurthestPoints.png

Answer 1

Este é um bom exemplo de um problema que pode ser resolvido usando KD-Árvores ... existem algumas boas notas no Numerical Recipes 3 Adição.

Se você está tentando encontrar locais de pontos que estão relativamente isolados ... talvez o centro dos maiores elementos quad seria um bom candidato.

A complexidade seria O (n log ^ 2 n) para criar o KD-Tree ... e criar uma lista ordenada de tamanhos quad seria O (n log n). Parece razoável, mesmo para um grande número de pontos (claro, dependendo de suas necessidades).

Answer 2

Este é um algoritmo ingênuo:

1. Obter a lista de pontos dentro da forma convexa.
2. Destes, encontrar a distância mínima a qualquer outro ponto.
3. Ranking todos os pontos por seus respectivos valores de R
4. Selecione os pontos de topo x.

Para (2), pensando nisso como um raio de busca ainda significa que você acaba calcular a distância de cada ponto ao outro ponto, porque descobrir se um ponto está dentro de um determinado raio de outro ponto é a mesma coisa que encontrar a distância entre os pontos.

Para otimizar a busca, você pode dividir o espaço em uma grade, e atribuir a cada ponto para um local grid. Então, a sua busca para (2) acima iria verificar primeiro dentro da mesma praça e os cercam 8 quadrados. Se a distância mínima para outro ponto está dentro do mesma quadrado, retornar esse valor. Se for de um dos 8 e a distância é tal que um ponto fora do 9 poderia estar mais perto, você tem que verificar então o próximo esboço de locais de grade fora os 9 para mais perto do que aqueles encontrados dentro do 9. Lavar / repetição .