Dado um conjunto de pontos, como faço para encontrar os dois pontos que estão mais distantes umas das outras? [duplicado]

Question

Duplicate possíveis:
maior dimensão linear 2D ajustados de pontos

Eu poderia calcular a distância entre cada ponto e tirar o maior, mas isso não soar como uma maneira muito eficiente de fazê-lo quando há um grande (> 1000) número de pontos.

Nota:. Isto é para iPhone, então eu não tenho uma tonelada de poder de processamento

Answer 1

Você está pedindo para calcular o diâmetro do conjunto. A técnica padrão é a primeira computação do casco convexo, o que reduz o problema de encontrar o diâmetro de um polígono convexo. Mesmo no caso em que você não eliminar quaisquer pontos, esta informação adicional é exatamente o que é necessário para resolver o problema de forma eficiente. No entanto, encontrar o diâmetro de um polígono convexo não é inteiramente trivial; vários artigos publicados com algoritmos para esta tarefa vir a ser incorreta.

Aqui está um discussão bastante legível de um algoritmo correcto o (n) para a tarefa (em que n é o número de pontos do casco convexo).

Além disso, observe o iphone não é que limitado; uma implementação cuidadosamente escrito do mesmo o algoritmo completamente ingênuo pode lidar com 1000 pontos em menos de um décimo de segundo. Claro, usando o algoritmo correta vai deixar você ir muito mais rápido =)

Answer 2

Porque não basta calcular a convexo casco dos pontos? Dependendo do algoritmo que você usa, é preciso tanto O(n) ou O(n log n) tempo e elimina todos os pontos internos de consideração. Em seguida, verificar apenas estes pontos extremos para encontrar os dois que são o mais distante.

Answer 3

Iniciar com o ponto com menor x-coord. (Chamemos-lhe Ponto X) conjunto de construção de "pontos de fronteira" começando com o ponto x, e linha vertical através do ponto, Não deve haver outros pontos para a esquerda de PointX) encontrar o próximo ponto na fronteira girando lentamente no sentido horário line (ou anti-horário) até que a linha toca algum outro ponto, (veja abaixo ). Adicionar que apontam para o conjunto e repita com o próximo ponto para obter o próximo, até que, eventualmente, voltar ao ponto original x. Você NPW tem um conjunto de pontos que formam o contorno do conjunto completo. Compare distância entre cada par deste conjunto reduzido de encontrar o par que estão mais afastadas.

Para "girar a linha" (para encontrar cada ponto limite seqüencial), tomar o ponto que é "mais distante" no perpindicular direção à linha usada para o último ponto de fronteira, e construir uma nova linha entre o último ponto de fronteira e que "próximo" ponto. Em seguida, verifique se não existem outros pontos furthur na nova direção perpindicular formada por essa nova linha. Se não há outros pontos "furthur fora" no perpindicular dirtection a esta linha ou para a última linha, então este é o cjhoice certo para o próximo ponto limite, se houver tal ponto um, mude para que um e reteste.

Answer 4

estas páginas (aquele ligada e as páginas acessíveis clicando nos links "próximos") em computação o diâmetro do casco convexo de um conjunto de pontos.

Meu rápido resumo:

1. conjunto de computação de pontos no casco convexo (= O (n log n), a única vez que você começa O (n) é se você classificar a lista primeira que leva O (n log n) de qualquer maneira)
2. ordem ao longo de fronteira (você recebe isso de graça se você usar um Graham varredura para # 1)
3. Use um dos S algoritmos (n) de diâmetro para procurar pontos antípodas com maior diâmetro. Shamos algoritmo parece ser bom para mim, pois é um dos rotativo pinças algoritmos.