Algoritma untuk menemukan titik terdekat

Saya sudah daftar beberapa ratus kota dengan garis lintang / bujur. Diberikan lokasi lain (juga di lat / long) saya perlu menemukan kota terdekat.

Karena saya tidak menggunakan GIS, sekarang algoritma yang jelas adalah membuat lingkaran untuk semua kota, menghitung jarak antara titik-titik.

Membuat loop itu praktis untuk saya, tetapi ada beberapa algoritma yang mudah diimplementasikan untuk mencapainya dengan lebih efisien? Atau perpustakaan Java ringan yang dapat membantu menyelesaikannya?

Catatan : Saya tidak membutuhkan / menginginkan solusi GIS lengkap atau perpustakaan yang berat / rumit. Saya lebih suka solusi yang kurang baik tetapi lebih mudah dan lebih ringan karena itulah satu-satunya hal yang perlu saya pecahkan.

Saya menyelidiki pertanyaan ini persis 20 tahun yang lalu ketika merancang GIS desktop. Kami perlu menemukan jarak titik-ke-titik secara interaktif; target kami adalah melakukan perhitungan dalam waktu kurang dari 1/2 detik untuk ribuan poin. Pengujian (pada PC 25 MHz 486!) Menunjukkan bahwa kami dapat menghitung semua jarak, persis seperti yang Anda gambarkan (dengan algoritma sederhana yang jelas), begitu cepat sehingga tidak masuk akal untuk membuat solusi yang lebih canggih, seperti struktur quadtree. .

Untuk menghitung jarak ke titik "probe" tunggal, opsi Anda meliputi (a) memproyeksikan semua titik menggunakan proyeksi yang sama yang berpusat di titik pemeriksaan atau (b) mengadopsi model bumi berbentuk bola dan menggunakan rumus Haversine . Yang pertama sesuai jika Anda membutuhkan keakuratan model ellipsoidal. Dalam kedua kasus tersebut perhitungannya cukup cepat, mungkin mengambil kurang dari 1000 kutu: Anda dapat meminta sekitar satu juta poin per detik dengan satu prosesor.

Cukup cepat untukmu? Jika tidak, metode brute-force berparalel dengan mudah dan skala langsung dengan jumlah prosesor: hanya membagi poin di antara prosesor dan kemudian melakukan perbandingan akhir dari yang terdekat yang ditemukan oleh masing-masing prosesor.

Jika Anda harus melangkah lebih cepat, Anda dapat menggunakan berbagai perkiraan untuk menyaring poin. Misalnya, jika Anda berada di antara -88 dan +88 derajat lintang dan titik terdekat yang ditemukan sejauh ini adalah 200 km jauhnya, maka setiap titik yang garis lintangnya berbeda dari garis lintang titik pemeriksaan lebih dari 2 derajat tidak mungkin lebih dekat (karena di mana pun bumi, satu derajat garis lintang melebihi sekitar 110 km). Dalam banyak kasus pra-penyaringan semacam ini memungkinkan Anda untuk memproses ratusan juta poin per detik.

Saya setuju dengan yang lain bahwa perulangan sederhana harus efektif untuk "beberapa ratus kota".

Mengingat aplikasi Anda, berurusan dengan jarak ellipsoidal mungkin berlebihan - Anda mungkin berurusan dengan prediksi cuaca yang lokalitasnya hampir tidak sampai beberapa meter. Geometri bola cukup sederhana sehingga Anda bisa melakukannya dengan mudah di lingkaran Anda.

Itu bisa lebih sederhana (misalnya; gunakan delta lat sebagai y dan delta lon * cos (lat) sebagai x dan temukan minimum x ^ 2 + y ^ 2). Anda menggunakan cosinus dari garis lintang target, yang hanya Anda hitung satu kali. Ini akan semakin tidak akurat untuk kota-kota yang jauh, tetapi toh mereka akan ditolak jadi tidak masalah. Dengan asumsi bahwa kota terdekat Anda umumnya dalam beberapa ratus kilometer, kemungkinan hasil yang berbeda (kota terdekat) menggunakan ini vs menggunakan formula yang lebih akurat cukup kecil dan akan terjadi hanya ketika perbedaannya cukup kecil bahwa "yang perkiraannya lebih akurat "mungkin akan tergantung pada faktor-faktor lain (yaitu: hilang dalam kebisingan).

Kecuali jika Anda menggunakan sistem embedded atau interpreter lambat, Anda mungkin bisa menggunakan formal bola yang disarankan orang lain, tho.

Ini merupakan tambahan dari apa yang telah dikatakan, tetapi saya pikir saya akan mencatat pentingnya memilih struktur data yang sesuai. Saya menulis kode saya sendiri untuk Fungsi-K di .NET, dan menemukan bahwa menggunakan koleksi yang efisien mempercepat banyak hal. Maaf saya tidak tahu notasi O untuk kecepatan yang tepat. Saya menggunakan dua Kamus untuk koordinat x dan y dengan ID titik sebagai kunci. Saya tidak tahu Java jadi tidak bisa menyarankan apa pun.

Cheers, David