Lebih dari sekali saya harus mengimplementasikan fungsi penghitungan jarak dari titik geografis tertentu ke area pada peta - misalnya, ke Moscow Ring Road. Akibatnya, saya menemukan dua cara untuk menyelesaikan masalah yang menunjukkan hasil yang baik, dan sekarang kami menggunakannya secara teratur dalam produksi. Saya akan menjelaskannya di bagian pertama artikel. Dan di bagian kedua saya akan menunjukkan bagaimana Anda bisa men-cache geodata untuk menggunakan geocoder lebih sedikit.
Bagian Satu Dua cara untuk menemukan jarak dari satu titik ke area pada peta
Jika aplikasi seluler Anda benar-benar seluler, ia berfungsi dengan koordinat perangkat. Lokasi pengguna (dan perangkat) memengaruhi berbagai indikator bisnis dari aplikasi, seperti biaya pengiriman, faktor kompleksitas, dll.
Di bawah ini saya akan menunjukkan contoh implementasi algoritma dalam python menggunakan librari yang indah dan berbentuk.
Untuk geocoding kami menggunakan Google Maps. Sesuai dengan fungsionalitas dan biaya penggunaan. Pada saat penulisan ini, Google memungkinkan Anda untuk membuat 20.000 permintaan geocoding pertama per bulan secara gratis.
Metode 1. Kami menghitung rute berdasarkan simpul dari poligon
Misalkan kita perlu menemukan jarak dari titik di suatu tempat di wilayah Moskow ke Moskow Ring Road. Diperlukan jalur nyata, bukan jalur geometris. Karena itu, pertama-tama kita membangun tempat pembuangan sampah dari titik keluar dari Moscow Ring Road, dan mereka tidak bertepatan dengan simpul garis besar jalan pada peta.
exit_coordinates: List[Tuple[float, float]] latitude: float longitude: float
Untuk bekerja dengan geometri, kami menggunakan pustaka
rupawan. Dengan bantuannya mudah untuk menentukan apakah tempat menarik bagi kami ada di dalam poligon atau tidak. Jika ya, jaraknya jelas 0.
from shapely.geometry import Polygon, Point polygon = Polygon(exit_coordinates) polygon.contains(Point(latitude,longitude))
Kami tertarik pada kasus ketika titik di luar poligon. Tugas menemukan objek terdekat (keluar dari MKAD) ke titik awal cukup khas dalam matematika. Biasanya ini diselesaikan menggunakan pohon KD. Jadi mari kita lakukan. Dalam python, pohon tersebut diimplementasikan dalam pustaka
scipy. Kami akan menemukan puncak terdekat dari pintu keluar dari Moscow Ring Road ke titik kami.
from scipy.spatial import KDTree kd_tree = KDTree(exits_coordinates) dists, indexes = kd_tree.query((latitude, longitude), k=3) nearest_coordinates = list() for _, index in zip(dists, indexes): nearest_coordinates.append(exits_coordinates[index])
Jumlah
k - jumlah puncak - tidak boleh terlalu kecil, karena pintu keluar terdekat dari Moscow Ring Road untuk sementara dapat diblokir. Atau mungkin di suatu tempat di luar sungai dan tidak memiliki jalur langsung ke titik kami. Terlalu besar
k juga tidak berguna bagi kita, karena jalan keluar yang cocok terletak di beberapa puncak terdekat. Sekarang mari kita beralih ke layanan Google Maps. Itu sudah memiliki fungsi untuk menemukan jarak dari berbagai titik ke titik tertentu - Distance Matrix API.
Pembaruan: layanan Distance Matrix API menagih rute ke setiap puncak terdekat secara terpisah. Dengan demikian, metode ini lebih mahal daripada yang kedua, dijelaskan di bawah ini. Terima kasih
sovetnikov import googlemaps gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) gmaps_client.distance_matrix( origins=nearest_coordinates, destinations=(latitude, longitude), mode='driving', )
Kami hanya dapat menguraikan jawabannya. Biasanya memiliki beberapa rute, dan yang pertama tidak selalu yang terpendek. Karena itu, kami memilih nilai yang sesuai.
Metode 2. Kami menghitung rute dari pusat TPA
Sekarang, selain simpul poligon, kami menetapkan beberapa titik di dalamnya, dari mana kami akan membangun semua rute Google Maps. Kami akan menggunakan API Arah, yang akan membangun rute untuk kami, dan memilih yang paling pendek.
start_point: Tuple[float, float], destination: Tuple[float, float] polygon: shapely.geometry.Polygon gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) driving_path = gmaps_client.directions(start_point, destination)
Kita mulai secara iteratif dari akhir untuk menambahkan panjang segmen lintasan sampai koordinat awal segmen berada di dalam poligon (penguraian dihilangkan):
for step in reversed(driving_path): start_point = step['start_location']['lat'], step['start_location']['lng'] if is_inside_polygon(start_point, self.polygon): end_point = step['end_location']['lat'], step['end_location']['lng'] distance += get_part_outside_polygon( get_line(start_point, end_point), polygon ) * step['distance']['value'] break distance += step['distance']['value']
Kami hanya dapat menambahkan bagian segmen di luar poligon. Untuk melakukan ini, dengan menggunakan pustaka yang indah, kami membangun garis geometris antara koordinat awal dan akhir jalan dan menemukan berapa banyak panjangnya terletak di luar poligon. Persentase panjang yang sama dihitung untuk segmen jalan yang diperoleh.
Jalur adalah rute medan di jalan nyata dengan kelengkungan alami. Jika itu adalah garis lurus panjang (jalan atau jalan raya), maka perkiraan kami akan memungkinkan kami untuk menghitung rute dengan tepat dalam bentuk persentase.
Jika jalan yang melintasi TPA cukup melengkung, perkiraan seperti itu akan salah. Tetapi bagian melengkung dalam rute Google Maps itu sendiri biasanya pendek, dan kesalahan dalam perhitungannya tidak akan mempengaruhi hasilnya.
from shapely.geometry import LineString, Polygon line = LineString(point1, point2) part_outside_len = float(line.difference(polygon).length) / float(line.length)
Sejujurnya, saya tidak membandingkan kedua metode ini. Saya telah menggunakan mereka selama lebih dari setahun, keduanya bekerja tanpa kegagalan. Saya memutuskan untuk tidak melukis implementasi mereka secara rinci. Sebaliknya, ia membuka akses ke
perpustakaan geo- nya
. Liba juga dapat menggunakan geocoding biasa, termasuk dengan caching yang efisien. Masalah dan permintaan tarik dipersilahkan!
Bagian Dua Simpan Permintaan Geocoding Terbalik
Seringkali kita perlu menentukan alamat titik-titik yang dekat dan sesuai dengan satu objek di dunia nyata. Setiap kali, membuat permintaan ke sistem geocoding eksternal tidak keren, dan di sini muncul pertanyaan tentang caching.
Biasanya, klien mengirim koordinat dengan akurasi yang berlebihan, misalnya, 59.80447691, 30.39570337. Tetapi berapa banyak tanda di bagian fraksional akan signifikan bagi kita?
Bagi mereka yang malas dan terburu-buru, jawabannya adalah empat. Untuk semua orang, lihat penjelasan di bawah ini.
Pertama, geografi kecil.
- Ekuator memiliki panjang 40.075,696 km, dan garis lintang nol.
- Meridian adalah garis bujur, tegak lurus terhadap garis lintang. Panjang meridian apa pun adalah 40.008,55 km
- Derajat lintang - 40.008,55 km / 360 = 111.134861111 km. Jadi, seperseratus memberikan perubahan sekitar satu kilometer, dan seperseribu memberikan perubahan 10 meter.
- Lingkar garis lintang menurun dari garis khatulistiwa, dan dikalikan dengan kosinus sudut lintang, oleh karena itu, untuk 60 derajat lintang (lintang St. Petersburg), panjangnya kurang dari tepat 2 kali lebih sedikit. Maka derajat garis bujur adalah 40.075.696 * 0,5 / 360 = 55.66066888 km, atau seperseribu ribu adalah 5 meter.
Kesalahan 1/10000 derajat memberikan persegi panjang kesalahan 5-10 kali 10 meter. Ini akan memungkinkan kita untuk "masuk" ke gedung dengan tepat bangunannya jauh lebih besar dari intinya. Dan jika, karena kesalahan, intinya tidak jatuh ke gedung, Google akan tetap menentukan yang paling dekat dengannya.
Membulatkan hingga tiga karakter berisiko, akurasi sudah berkurang secara signifikan. Dan hingga lima - tidak masuk akal, karena keakuratan pemancar-GPS tidak melebihi hanya beberapa meter.
Dengan demikian, jika ada nilai dalam cache dengan kunci “address: 59.8045,30.3957”, maka semua koordinat, ketika dibulatkan menjadi 4 karakter, kunci yang sama diperoleh, sesuai dengan satu alamat yang di-geocode. Kami membuat lebih sedikit permintaan - kami bekerja lebih cepat dan membayar lebih sedikit untuk menggunakan layanan geocoding. Untung!