Bagaimana menemukan titik setengah jalan antara dua titik lainnya?

Saya sedang berupaya mengimplementasikan format OSM Mobile Binary untuk data peta, dan karena ia menggunakan delta 16 bit untuk setiap titik di sepanjang jalan, itu tidak dapat mewakili cara jika ada jarak yang besar antara dua titik.

Solusi yang terdokumentasi adalah menyuntikkan poin-poin baru ke dalam jalan, untuk menjaga jarak lebih kecil.

Inilah bagian yang relevan dari kode saya:

// calculate the distance between this point and the previous point,
// multiplied by 1,000,000 so it can be represented as an integer.
int32_t realNodeLatDelta = ((point.latitude - lastPoint.latitude) * 1000000);
int32_t realNodeLonDelta = ((point.longitude - lastPoint.longitude) * 1000000);

// cast as a 16 bit int (reduces filesize by about half)
int16_t nodeLatDelta = realNodeLatDiff;
int16_t nodeLonDelta = realNodeLonDiff;

// check if the cast caused corruption
if (realNodeLatDelta != nodeLatDelta || realNodeLatDelta != nodeLatDelta) {
  // if this point is reached, we need to add new points in the way,
  // which can be represented in a 16 bit delta
}

Saya tidak yakin bagaimana cara menghitung posisi poin baru di sepanjang jalan? Saya menganggap itu perlu lingkaran besar?

Poin yang terpisah cukup jauh untuk menyebabkan masalah ini jarang terjadi, tetapi ketika itu terjadi biasanya merupakan batas politik atau serupa, yang cenderung cukup panjang, dan perlu diwakili secara akurat.

Akurasi terbaik diperoleh dengan model ellipsoidal. Demi kesederhanaan, Anda ingin menghindarinya ketika Anda harus membuat kode jarak sendiri. Kami membayar harga: mengingat bahwa perataan bumi sekitar 1/300, menggunakan model bola murni berpotensi memperkenalkan kesalahan jarak relatif hingga 1/300 untuk rute yang sangat panjang: sekitar 3000 bagian per juta. Ini perlu ditelusuri.

Pertama, rumus bola : cukup konversi (lat, lon) ke koordinat kartesius, rata-rata dua titik kartesius, lalu konversikan kembali rata-rata ke koordinat bola. Inilah pseudocode:

function cartesian(f,l) { // f = latitude, l = longitude
    return (cos(f)*cos(l), cos(f)*sin(l), sin(f))
}
function spherical(x,y,z) {
    r = sqrt(x^2 + y^2)
    if (r == 0) {
        if (z > 0) return (90, 0) 
        elseif (z < 0) return (-90, 0)
        else return Undefined // (x,y,z) == (0,0,0)
    } else {
        return (atan2(r, z), atan2(x, y)) // atan2 must return *degrees*
    }
}
function midpoint(f0,l0, f1,l1) { 
    return spherical((cartesian(f0,l0) + cartesian(f1,l1))/2)
}

(Aritmatika untuk midpointmelibatkan jumlah vektor dan pembagian skalar dari jumlah itu, jadi itu benar-benar menyembunyikan tiga jumlah dan tiga divisi.)

Itulah titik tengah dalam geometri bola. Perhitungan membutuhkan dua cosinus, dua sinus, akar kuadrat, dua arctangents, dan beberapa perkalian dan penambahan: cukup cepat dan mudah. Tidak akan ada masalah di dekat kutub atau melintasi meridian + -180. Hasilnya akan tidak terdefinisi ketika kedua titik itu secara diametris berlawanan.

Salah satu cara untuk mengukur kesalahan adalah dengan menghitung peningkatan jarak yang ditempuh melalui titik tengah dibandingkan dengan jarak antara titik-titik asli. Jika kenaikannya kecil dibandingkan dengan jarak semula, kita hanya punya sedikit keluhan. Saya telah menghitung kesalahan ini menggunakan jarak ellipsoidal yang akurat untuk ellipsoid WGS84. Sebagai contoh khas dari hasil, berikut adalah plot kesalahan relatif ketika salah satu titik akhir diperbaiki pada (lat, lon) = (45, 0):

Konturnya berada pada skala logaritmik (basis 10): kontur -6 menunjukkan titik di mana kesalahan relatifnya adalah 10 ^ (- 6); yaitu, satu bagian per juta (ppm). Kontur -5 (hampir tidak terlihat dekat (-45, 180), titik yang berlawanan secara diametral) adalah 10 ppm. -7, -8, dll adalah sebagian kecil dari ppm: sangat akurat.

Terbukti, selama kita tidak mencoba menghitung titik tengah dari dua titik yang berlawanan secara diametris, kita akan baik-baik saja. (Ingat, perhitungannya benar untuk bola; kesalahan ini disebabkan oleh perataan bola.)

Mengingat bahwa presisi 16 bit adalah sekitar 16 ppm (basis-10 log sama dengan -4,8), tampaknya oke untuk menggunakan rumus bola untuk menemukan titik tengah asalkan dua titik lebih dari satu derajat dari kebalikan secara diametris.

Bagaimana dengan rumus linier yang lebih sederhana? Untuk mempelajari hal ini, mari kita bandingkan jarak antara titik tengah linier (diperoleh dengan rata-rata dua garis lintang dan dua garis bujur) ke titik tengah bola, relatif terhadap jarak antara dua titik akhir. Gambar berikut memperbaiki satu titik akhir di (45, 180) dan menjelajahi wilayah yang relatif kecil di sekitarnya.

Sebagian besar kontur ini (basis-10 logaritma sekali lagi) hampir -2: itu adalah satu bagian per seratus (1%) kesalahan. Untuk arah utara-selatan tidak ada kesalahan, tetapi untuk semua arah lainnya kesalahan tidak dapat diterima untuk banyak aplikasi .

Untuk melihat apakah perkiraan linier menjadi OK, mari perbesar ke peta sebelumnya dengan faktor 10. Sekarang lebarnya satu derajat (50 mil pada garis lintang ini) dan satu setengah derajat (35 mil): kita melihat pada skala kota besar atau kota kecil dan pinggirannya.

Sekarang konturnya sekitar -3 hingga -4: itu 100 hingga 1000 bagian per juta (0,01% hingga 0,1%). Cukup kasar dan nyaris tidak terlihat di layar komputer beresolusi tinggi jika Anda perhatikan dengan seksama.

Melihat ke belakang, jelas bahwa rumus bola yang sedikit lebih rumit - tetapi masih mudah diterapkan - mencapai akurasi yang lebih besar di seluruh dunia daripada rumus linear sederhana bahkan di lokasi terdekat. (Saya sedikit fudging, karena saya telah menggunakan dua cara berbeda untuk mengukur kesalahan, sehingga mereka tidak sebanding secara langsung.)

Garis bawah:

- Formula linier akan salah menempatkan titik tengah dengan kesalahan relatif 0,01% hingga 0,1% pada skala kota; di area yang lebih besar, misposisi bisa sangat keliru (1% hingga ratusan%).

- Formula bola benar-benar benar untuk model bumi bulat. Dibandingkan dengan formula ellipsoidal yang lebih akurat, ia seharusnya masih bekerja dengan baik kecuali untuk titik-titik yang berlawanan secara diametris.

Solusi Anda berfungsi untuk jarak kecil, tetapi tidak untuk yang lebih besar. Cara termudah untuk melihat alasannya adalah dengan melihat peta berikut (diambil dari sini ):

Ini adalah peta dunia dalam proyeksi berbentuk persegi panjang - bujur dan lintang hanya diproyeksikan secara linier ke sumbu X dan Y. Matematika Anda dapat diwakili oleh kotak biru . Namun, diagonal biru tidak mewakili "garis" terpendek antara dua titik di permukaan bumi. Yang Anda butuhkan adalah lingkaran besar (diwakili oleh kurva hitam ).

Meskipun Anda menggunakan C ++, saya sarankan untuk melihat Perpustakaan C # Geodesy milik Mike Gavaghan , itu open source dan kodenya berkualitas tinggi, Anda harus bisa mengetahui bagaimana melakukan perhitungan di sepanjang lingkaran besar. Anda juga dapat melihat rumus Vincenty jika Anda tertarik pada matematika di balik perhitungan.

Matematika linear sederhana tampaknya bekerja dengan baik:

double newLat = lastCoord.latitude + ((coord.latitude - lastCoord.latitude) / 2);
double newLon = lastCoord.longitude + ((coord.longitude - lastCoord.longitude) / 2);

Saya secara rekursif memasukkan setengah jalan poin baru di setiap bagian dari cara yang terlalu besar, sampai semuanya cukup kecil.

Saya tidak yakin apakah matematika yang lebih rumit diperlukan untuk jarak yang lebih jauh (adakah yang bisa mengonfirmasi ini untuk saya?), Tetapi ini berfungsi baik untuk yang ini (sekitar 5 km):