Dato un insieme di punti, come posso trovare i due punti più distanti l'uno dall'altro? [duplicare]

Question

  

Possibile duplicato:
   Set di punti 2d della dimensione lineare più grande

Potrei calcolare la distanza tra ogni punto e prendere il massimo, ma questo non sembra un modo molto efficiente per farlo quando ci sono molti (> 1000) punti.

Nota: questo è per iPhone, quindi non ho un sacco di potenza di elaborazione.

Answer 1

Stai chiedendo di calcolare il diametro dell'insieme. La tecnica standard consiste innanzitutto nel calcolare lo scafo convesso, il che riduce il problema nel trovare il diametro di un poligono convesso. Anche nel caso in cui non si eliminino punti, queste informazioni aggiuntive sono esattamente ciò che è necessario per risolvere il problema in modo efficiente. Tuttavia, trovare il diametro di un poligono convesso non è del tutto banale; diversi articoli pubblicati con algoritmi per questo compito risultano errati.

Ecco una una discussione abbastanza leggibile di un algoritmo O (n) corretto per l'attività (dove n è il numero di punti nello scafo convesso).

Inoltre, nota che l'iPhone non è che limitato; un'implementazione accuratamente scritta anche dell'algoritmo completamente ingenuo può gestire 1000 punti in meno di un decimo di secondo. Naturalmente, l'utilizzo dell'algoritmo corretto ti consentirà di andare molto più velocemente =)

Answer 2

Perché non calcolare semplicemente il scafo convesso dei punti? A seconda dell'algoritmo che usi, richiede O (n) o O (n log n) ed elimina tutti i punti interni dalla considerazione. Quindi, controlla solo questi punti più esterni per trovare i due più lontani.

Answer 3

Inizia con il punto con il valore x-coord più basso. (Chiamalo punto X) Costruire un insieme di "punti di confine"    iniziando con il punto xe la linea verticale attraverso il punto, non dovrebbero esserci altri punti a sinistra di PointX) trova il punto successivo nel limite ruotando lentamente la linea in senso orario (o antiorario) fino a quando la linea tocca un altro punto (vedi sotto ). Aggiungi quel punto al set e ripeti con il punto successivo per ottenere il prossimo, fino a quando alla fine non torni al punto originale x. Hai un set di punti che formano il confine del set completo. Confronta la distanza tra ogni coppia in questo set ridotto per trovare la coppia più lontana.

Per " ruotare la linea " (per trovare ogni punto limite sequenziale), prendi il punto che è "più lontano" nella direzione perpendicolare alla linea utilizzata per l'ultimo punto limite e costruisci una nuova linea tra l'ultimo punto limite e quello "successivo"; punto. Quindi verifica che non vi siano altri punti più avanti nella nuova direzione perpendicolare formata da quella nuova linea. Se non ci sono altri punti "furthur out" nella sporcizia perpendicolare a questa linea o all'ultima linea, allora questa è la scelta giusta per il punto di confine successivo, se esiste un punto del genere, passare a quella e ripetere il test.

Answer 4

Vedi queste pagine (quella collegati e le pagine raggiungibili facendo clic sui collegamenti "successivo") per calcolare il diametro dello scafo convesso di una serie di punti.

Il mio breve riepilogo:

1. calcola l'insieme di punti nello scafo convesso (= O (n log n), l'unica volta che ottieni O (n) è se ordini prima l'elenco che prende comunque O (n log n))
2. ordina lungo il confine (ottieni questo gratuitamente se usi una Graham scan per # 1)
3. usa uno degli algoritmi di diametro O (n) per cercare punti antipodali con diametro maggiore. Algoritmo Shamos mi sta bene perché è uno dei calibri rotanti .