Mengapa hukum cosinus lebih disukai daripada haversine ketika menghitung jarak antara dua titik lintang-bujur?

41

Faktanya, ketika Sinnott menerbitkan formula haversine, ketepatan komputasi terbatas. Saat ini, JavaScript (dan sebagian besar komputer & bahasa modern) menggunakan nomor floating-point IEEE 754 64-bit, yang memberikan 15 angka presisi yang signifikan. Dengan presisi ini, hukum bola sederhana rumus cosinus ( cos c = cos a cos b + sin a sin b cos C) memberikan hasil yang terkondisi dengan baik hingga jarak sekecil 1 meter. Mengingat hal ini, dalam sebagian besar situasi, mungkin layak menggunakan hukum cosinus yang lebih sederhana atau formula Vincenty ellipsoidal yang lebih akurat daripada haversine! (dengan mengingat catatan di bawah ini tentang keterbatasan dalam akurasi model bola).
Sumber: http://www.movable-type.co.uk/scripts/latlong.html

Apa alasan mengapa hukum cosinus lebih disukai?

Catatan: Teks yang dikutip telah diperbarui oleh penulisnya sebagaimana disebutkan di bawah ini .

Afriza N. Arief
sumber
10
Bagaimana hukum kosinus "lebih disukai"? Kami dapat menjawab ini dengan dua cara: untuk komputer dan programmer. Untuk komputer, rumus haversine menggunakan lebih sedikit fungsi trigonometri tetapi membutuhkan dua akar kuadrat. Untuk efisiensi komputasi, maka itu adalah undian. Untuk programmer, rumus haversine sedikit lebih lama. Namun, rumus hukum cosinus mensyaratkan memiliki implementasi ACos, yang terlihat sedikit lebih jarang daripada implementasi ATan. Selanjutnya, untuk menulis kode antipeluru Anda harus memeriksa bahwa AC tidak akan gagal. Untuk alasan ini saja kita harus memilih haversine.
whuber
2
Saya baru saja menerapkan haversine dan cosinus dengan Python. Pada komputer ini haversine membutuhkan 3,3s dan cosinus mengambil 2,2s yang cukup signifikan jika Anda perlu melakukan banyak dari itu
gnibbler
1
Terima kasih kepada semua orang untuk beberapa pengamatan dan informasi yang baik. Saya telah memperbarui teks yang dikutip dalam pertanyaan menjadi, saya harap, lebih objektif dan bermanfaat.
ChrisV
@ ChrisV, terima kasih atas pembaruannya! Saya telah memindahkan ini ke komentar karena tidak langsung menjawab pertanyaan, terima kasih atas situs hebat Anda.
scw

Jawaban:

48

Masalahnya ditunjukkan oleh kata "terkondisi dengan baik." Ini masalah aritmatika komputer, bukan matematika.

Berikut adalah fakta dasar yang perlu dipertimbangkan:

  1. Satu radian di bumi membentang hampir 10 ^ 7 meter.

  2. Fungsi cosinus untuk argumen x dekat 0 kira-kira sama dengan 1 - x ^ 2/2.

  3. Titik apung presisi ganda memiliki sekitar 15 digit desimal presisi.

Poin (2) dan (3) menyiratkan bahwa ketika x sekitar satu meter, atau 10 ^ -7 radian (poin 1), hampir semua presisi hilang: 1 - (10 ^ -7) ^ 2 = 1 - 10 ^ - 14 adalah perhitungan di mana 14 dari 15 digit signifikan pertama dibatalkan, hanya menyisakan satu digit untuk mewakili hasilnya. Membalik-balik ini (yang artinya cosinus terbalik, "acos", artinya) menghitung komputasi untuk sudut yang sesuai dengan jarak meteran panjang tidak dapat dilakukan dengan akurasi yang berarti. (Dalam kasus-kasus buruk tertentu kehilangan presisi memberikan nilai di mana AC bahkan tidak didefinisikan, sehingga kode akan rusak dan tidak memberikan jawaban, jawaban omong kosong, atau crash mesin.) Pertimbangan serupa menyarankan Anda harus menghindari menggunakan cosinus terbalik jika jarak kurang dari beberapa ratus meter terlibat, tergantung pada seberapa presisi Anda bersedia kehilangan.

Peran yang dimainkan oleh ACOS dalam rumus law-of-cosines naif adalah untuk mengubah sudut ke jarak. Peran itu dimainkan oleh atan2 dalam formula haversine. Garis singgung dari sudut kecil x kira-kira sama dengan x itu sendiri. Akibatnya, garis singgung terbalik dari suatu bilangan, yaitu kira-kira bilangan itu, dihitung secara esensial tanpa kehilangan presisi. Inilah sebabnya mengapa rumus haversine, meskipun secara matematis setara dengan rumus hukum cosinus, jauh lebih unggul untuk jarak kecil (pada urutan 1 meter atau kurang).

Berikut ini adalah perbandingan dari dua rumus menggunakan 100 pasangan titik acak di dunia (menggunakan perhitungan presisi ganda Mathematica).

teks alternatif

Anda dapat melihat bahwa untuk jarak kurang dari 0,5 meter, kedua formula berbeda. Di atas 0,5 meter mereka cenderung setuju. Untuk menunjukkan seberapa dekat mereka sepakat, plot berikutnya menunjukkan rasio hukum cosinus: hasil haversine untuk 100 pasangan titik acak lainnya, dengan garis lintang dan bujur mereka secara acak berbeda hingga 5 meter.

teks alternatif

Ini menunjukkan bahwa rumus hukum cosinus baik untuk 3-4 tempat desimal setelah jarak melebihi 5-10 meter. Jumlah tempat desimal akurasi meningkat secara kuadrat; jadi pada 50-100 meter (satu urutan magnitudo) Anda mendapatkan akurasi 5-6 dp (dua orde magnitudo); pada 500-1000 meter Anda mendapatkan 7-8 dp, dll.

whuber
sumber
Apakah ada beberapa tes murah - misalnya delta latitude > .1 || delta longitude > .1untuk secara dinamis memilih cosinus (untuk besar) atau haversine (untuk jarak kecil)? Untuk mendapatkan kinerja terbaik dan presisi yang baik.
Anony-Mousse
@ Anony-Mousse Kedua formula dapat dimatikan dengan sepersepuluh dari satu persen untuk jarak seperempat di seluruh dunia, jadi pada saat itu kita tidak akan mempermasalahkan presisi! Oleh karena itu setiap tes yang dapat membedakan titik dekat (beberapa ratus meter) dari titik yang berlawanan secara diametral (sekitar 20 juta meter) dari semua yang ada di antaranya harus memadai.
whuber
Apakah atan2menawarkan manfaat numerik lebih asin? Saya melihat tolok ukur, di mana atan22-3x lebih lambat daripada asin, dan kami juga membutuhkan yang kedua sqrt.
Erich Schubert
@Erich Saya belum mempelajari perbedaannya, tetapi perhatikan bahwa asinpada dasarnya hal yang sama acosdan karenanya menderita kehilangan presisi yang sama untuk nilai-nilai tertentu - dalam hal ini, untuk argumen dekat 1 dan -1. Pada prinsipnya, atan2tidak ada masalah itu.
whuber
Itu akan berada pada jarak yang sangat besar? Menggabungkannya dengan saran @ Anony-Mousse di atas nampaknya menarik.
Erich Schubert
6

Catatan sejarah:

The haversine adalah cara untuk menghindari kesalahan pembulatan besar dalam perhitungan seperti

1 - cos(x)

ketika x kecil. Dalam hal haversine yang kita miliki

1 - cos(x) = 2*sin(x/2)^2
           = 2*haversin(x)

dan 2 * sin (x / 2) ^ 2 dapat dihitung secara akurat bahkan ketika x kecil.

Di masa lalu, formula haversine memiliki keuntungan tambahan untuk menghindari penambahan (yang memerlukan pencarian antilog, penambahan, dan pencarian log). Rumus trigonometik yang hanya memerlukan multiplikasi dikatakan dalam "bentuk logaritmik".

Saat ini, penggunaan formula haversine sedikit ketinggalan zaman. Mungkin saja sudut x diekspresikan dalam istilah sin(x)dan cos(x)(dan x mungkin tidak diketahui secara eksplisit). Dalam hal itu, komputasi 1 - cos(x)melalui rumus haversine memerlukan arctangent (untuk mendapatkan sudut x), membagi dua (untuk mendapatkan x/2), sinus (untuk mendapatkan sin(x/2)), kuadrat (untuk mendapatkan sin(x/2)^2) dan penggandaan akhir. Anda jauh lebih baik menggunakan evaluasi

1 - cos(x) = sin(x)^2/(1 + cos(x))

yang tidak memerlukan evaluasi fungsi trigonometri. (Tentunya gunakan sisi kanan hanya jika cos(x) > 0; jika tidak, boleh digunakan 1 - cos(x)secara langsung.)

cffk
sumber
1

Formula cosine dapat diimplementasikan dalam satu baris:

  Distance = acos(SIN(lat1)*SIN(lat2)+COS(lat1)*COS(lat2)*COS(lon2-lon1))*6371

Formula haversine mengambil banyak baris:

  dLat = (lat2-lat1)
  dLon = (lon2-lon1)
  a = sin(dLat/2) * sin(dLat/2) + cos(lat1) * cos(lat2) * sin(dLon/2) * sin(dLon/2)
  distance = 6371 * 2 * atan2(sqrt(a), sqrt(1-a))

Secara matematis, ada yang identik, jadi satu-satunya perbedaan adalah kepraktisan.

Tom W
sumber
Meskipun Haversine asli tidak menggunakan atan2formula yang berhubungan dengan komputer , tidak ada yang mencegah seseorang untuk menulis ulang 4 baris di atas menjadi satu formula.
Arjan
@Arjan, Benar, tapi itu akan menjadi tidak efisien karena Anda akan perlu untuk menghitung sebuah dua kali. Sangat penting bahwa rumus melibatkan Sqrt (a) dan Sqrt (1-a), karena meskipun salah satu dari ini tidak stabil secara numerik untuk jarak yang sangat kecil atau sangat besar, yang lain tidak akan: itulah yang membuat pendekatan ini bekerja.
whuber
Benar, @whuber, tapi tetap saja saya ragu jumlah garis akan membuat saya memilih satu dari yang lain. (Dan seperti yang sudah Anda jelaskan dalam jawaban Anda , ada alasan yang jauh lebih penting untuk mendukungnya.)
Arjan
3
@Arjan saya setuju. Prioritas pertama seseorang adalah kecukupan kode untuk tugas pemrograman. Setelah itu saya akan menempatkan kejelasan: yaitu, keterbacaan, pemeliharaan, dan dokumentasi melek. Tidak ada konteks seperti itu, menghitung jumlah baris kode tidak ada artinya.
whuber
1
atan2(sqrt(a), sqrt(1-a))sama denganasin(sqrt(a))
user102008