Lokasi proyek di jalur (lingkaran besar)

Saya telah mencari situs SE ini selama beberapa jam sekarang, dan saya masih berjuang untuk menemukan solusi untuk pertanyaan saya. Tujuan saya adalah memberikan cara pada OSM dan lokasi saya (koordinat lat / lon), saya ingin mencari lokasi terdekat (koordinat lat / lon) dengan cara itu. Titik bisa di mana saja di jalan, tidak terbatas pada titik yang digunakan untuk menentukan jalan.

Jadi saya sedang memikirkan algoritma berikut:

1. Pisahkan Path menjadi tepi yang terpisah, masing-masing tepi hanya menghubungkan dua titik.
2. Pilih tepi terdekat.
3. Proyeksikan lokasi saya ke tepi itu.

Sekarang ada banyak pertanyaan tentang menghitung jarak antara lokasi dan jalur:

• Titik WGS ke jarak segmen garis WGS (lingkaran besar)
• Menghitung jarak antara titik dan garis virtual dari dua lat / lngs
• Bagaimana cara memperkirakan titik ke jarak segmen pada bola?

Juga pertanyaan yang sangat mirip di mana saya tidak bisa mendapatkan perhitungan yang benar atau diverifikasi:

• Temukan titik terdekat pada sebuah garis

Ada juga beberapa info dari Dr. Math tentang subjek itu. Namun saya tidak bisa menemukan algoritma untuk menghitung lokasi pada langkah 3. Karena saya belum menyentuh aljabar (vektor) cukup lama, saya tidak begitu mengerti logika dalam jawaban itu.

Adakah yang bisa menunjukkan algoritma untuk melakukan ini? Sebuah solusi dalam bahasa pemrograman yang masuk akal tidak masalah bagi saya.

Menggunakan model bola bumi dapat memberikan akurasi yang memadai dan mengarah ke perhitungan cepat sederhana.

Ubah semua koordinat menjadi koordinat kartesian yang berpusat pada bumi (3D). Misalnya rumusnya

(cos(lon)*cos(lat), sin(lon)*cos(lat), sin(lat))

akan melakukan. (Ini menggunakan ukuran jarak di mana jari-jari bumi adalah satu unit, yang nyaman.)

Menulis X0 = (x0, y0, z0) untuk titik awal dan X1 = (x1, y1, z1) untuk titik tujuan, yang menentukan lingkaran besar (asalkan X0 berbeda dari X1 dan keduanya tidak berlawanan secara diametris), biarkan U menjadi produk silang yang dinormalisasi dari X0 dan X1. Ini dihitung dalam dua langkah:

V = (xv, yv, zv) = (y0*z1 - z0*y1, z0*x1 - x0*z1, x0*y1 - y0*x1)

Panjang V adalah

|V| = sqrt(xv^2 + yv^2 + zv^2)

Normalisasi membentang V ke satuan panjang:

U = (xu, yu, zu) = V / |V| = (xv/|V|, yv/|V|, zv/|V|).

Jarak 3D berorientasi antara titik X = (x, y, z) dan bidang lingkaran besar ini hanyalah produk titik X dengan Z, yang diberikan oleh

d = X * U = x*xu + y*yu + z*zu

Titik terdekat dalam hal jarak pada permukaan bumi adalah titik yang paling dekat dengan bidang: dengan demikian, ia memiliki nilai absolut terkecil d .

Gambar ini menunjukkan lingkaran besar (hitam) yang ditentukan oleh dua titik putih dan 2000 titik acak pada bola yang diwarnai dan diarsir menurut jarak 3D absolut mereka ke bidang lingkaran besar itu; itu adalah | d |

Setelah menemukan titik terdekat, proyeksikannya ke lingkaran besar dengan terlebih dahulu memproyeksikannya ke bidang lingkaran besar (dalam 3D) dan kemudian memperluasnya secara radial ke arah luar ke permukaan bumi. Proyeksi hanya mengurangi d * U:

X' = (x', y', z') = X - d*U = (x - d*xu, y - d*yu, z - d*zu).

Proyeksi radial hanya melakukan renormalisasi X 'dengan cara yang sama dengan V dinormalisasi ulang ke U:

X'' = X' / |X'|.

(Ini akan bermasalah jika | X '| = 0, yang terjadi ketika titik terdekat adalah salah satu kutub dari lingkaran besar. Sertakan tes dalam kode untuk kondisi ini, jika itu bisa terjadi, dan tangani secara terpisah, menggunakan tanda d untuk mengidentifikasi kutub mana.)

Jika diinginkan, konversikan koordinat X 'kembali ke (lat, lon) menggunakan rumus biasa .