Eventuali duplicati:
Greatest linear dimension 2d set of pointsDato un insieme di punti, come faccio a trovare i due punti più distanti l'uno dall'altro?
ho potuto calcolare la distanza tra ciascun punto e prendere il più grande, ma che non suona come un modo molto efficace per farlo quando ci sono un grande (> 1000) numero di punti.
Nota: questo è per iPhone, quindi non ho un sacco di potenza di elaborazione.
stai chiedendo di calcolare il diametro del set. La tecnica standard consiste nel calcolare prima lo scafo convesso, il che riduce il problema a trovare il diametro di un poligono convesso. Anche nel caso in cui non si eliminano tutti i punti, questo aggiunto informazioni è esattamente ciò che è necessario per risolvere il problema in modo efficiente. Tuttavia, trovare il diametro di un poligono convesso non è del tutto banale; diversi documenti pubblicati con algoritmi per questo compito risultano errati.
Ecco uno fairly readable discussion di un algoritmo O (n) corretto per l'attività (dove n è il numero di punti nello scafo convesso).
Inoltre, si noti che l'iphone non è quello limitato; un'implementazione scritto con cura anche di un algoritmo completamente ingenuo in grado di gestire 1000 punti in meno di un decimo di secondo. Ovviamente, l'utilizzo dell'algoritmo corretto ti consentirà di andare molto più rapidamente =)
Inizia con punto con x-coord più basso. (Chiamalo punto X) Costruisci set di "punti di confine" a partire dal punto x, e linea verticale attraverso il punto, non ci devono essere altri punti a sinistra di PointX) trova il punto successivo nel limite ruotando lentamente la linea in senso orario (O in senso antiorario) fino a quando la linea tocca un altro punto, (vedi sotto). Aggiungi quel punto al set e ripeti con quel punto successivo per ottenere quello successivo, fino a quando non ritorni al punto originale x. Hai npw una serie di punti che formano il confine del set completo. Confronta la distanza tra ciascuna coppia in questo set ridotto per trovare la coppia più lontana.
Per "ruotare la linea" (per trovare ogni punto di confine sequenziale), prendere il punto che è "più lontano" nella direzione perpendicolare alla linea utilizzata per l'ultimo punto di confine e costruire una nuova linea tra l'ultimo limite punto e quel punto "prossimo". Quindi verifica che non vi siano altri punti furth nella nuova direzione perpendicolare formata da quella nuova linea. Se non ci sono altri punti "furth out" nella dirtection perpendicolare a questa linea o all'ultima riga, allora questa è la giusta fattura per il prossimo punto di confine, se c'è un tale punto, passare a quello e ripetere il test.
Stesso commento di Chris. Non rendi niente di più facile se sul limite esterno non ci sono molti meno punti. –
Sembra un modo costoso per calcolare lo scafo complesso, seguito dal resto della risposta di Chris Bunch. – PanCrit
Non sapevo che esistesse un termine tecnico per questo ... (lo scafo convesso) ma è un confine di elastico. Controllerò altri algoritmi per calcolarlo ... Per quanto riguarda il numero di punti, per ogni raccolta casuale di punti, il numero di punti nel limite dovrebbe essere O (n) inferiore al numero totale di punti. (Il limite è una linea unidimensionale che delimita un'area bidimensionale.) –
Perché non solo calcolare lo convex hull dei punti? A seconda dello algorithm utilizzato, prende il tempo O(n) o O(n log n) ed elimina tutti i punti interni dalla considerazione. Quindi, controlla solo questi punti più esterni per trovare quelli che sono i più lontani.
Questo non rende le cose più facili. Se la quantità di punti in uno scafo convesso è O (n), la complessità rimane la stessa. –
Molto vero. Ma la speranza è che se ci sono> 1000 punti, allora molti di loro saranno all'interno dello scafo convesso. –
Ottima risposta. Stavo per dirlo. Inizia con l'euristica di Akl-Toussaint per eliminare più punti possibili prima di trovare lo scafo convesso. – Nosredna
Vedi these pages (quello collegato a e le pagine raggiungibili facendo clic sui collegamenti "successivo") sul calcolo del diametro dello scafo convesso di un set di punti.
mio sommario rapido:
È O (n) solo dopo aver trovato lo scafo convesso - se ti è stato assegnato un set di punti, potrebbe essere O (n log n) per trovare prima lo scafo convesso. – ShreevatsaR
@ShreevatsaR: Certo. La mia risposta dice esplicitamente "dove n è il numero di punti nello scafo convesso", il che rende abbastanza chiaro che è necessario trovare prima lo scafo convesso. –
Sì, forse è così. La chiarezza è negli occhi del lettore. :-) (L'algoritmo per l'attività nella domanda non è ovviamente O (n) dove n è il numero di punti nello scafo convesso, è la seconda parte che è, come dici tu.) Comunque, ho pensato che valesse la pena menzionare , solo per completezza: le persone possono arrivare a queste risposte anni dopo attraverso i motori di ricerca potrebbero non leggere attentamente, e possono confondersi, ecc. – ShreevatsaR