Trovare la coppia più vicina di punti su una sfera

Question

So come implementare l'algoritmo n coppia di punti più vicino (Shamos e Hoey) per i casi 2D (xey). Tuttavia, per un problema in cui la latitudine e la longitudine vengono fornite, questo approccio non può essere utilizzato. La distanza tra due punti viene calcolata usando la formula haversine.

Vorrei sapere se esiste un modo per convertire queste latitudini e longitudini alle rispettive coordinate xey e trovare la coppia di punti più vicina o se esiste un'altra tecnica che può essere utilizzata per farlo.

Answer 1

Vorrei tradurli in coordinate tridimensionali e quindi utilizzare lo divide and conquer approach utilizzando un piano anziché una linea. Questo funzionerà sicuramente correttamente. Possiamo essere certi di questo perché quando si esaminano solo i punti sulla sfera, i due punti più vicini per distanza dell'arco (distanza che percorre la superficie) saranno anche i due più vicini per distanza cartesiana 3-d. Questo avrà tempo di esecuzione O (nlogn).

Per tradurre in coordinate 3-d, il modo più semplice è di fare (0,0,0) il centro della terra e quindi le coordinate sono (cos (lat) * cos (lon), cos (lat) * sin (lan), sin (lat)). Per questi scopi sto usando una scala per la quale il raggio della Terra è 1 al fine di semplificare i calcoli. Se vuoi la distanza in qualche altra unità, moltiplica tutte le quantità per il raggio della Terra quando viene misurata in quell'unità.

Devo notare che tutto ciò presuppone che la terra sia una sfera. Non è esattamente uno e anche i punti potrebbero avere un'altitudine, quindi queste risposte non saranno completamente esatte, ma saranno quasi sempre corrette in quasi tutti i casi.