UPD: karena topiknya telah berjalan dengan baik dan telah menunjukkan bahwa ada permintaan untuk layanan seperti itu, saya akan mengembangkannya lebih lanjut. Saya memulai publik VKontakte untuk mengumpulkan umpan balik dan menerbitkan informasi pembaruan
https://vk.com/sightsafariDaerah kota yang asing, sejumlah kecil waktu luang dan kebutuhan (atau keinginan) untuk sampai ke stasiun metro / hotel / kereta dengan berjalan kaki - mungkin, setiap orang setidaknya pernah masuk ke dalam situasi ini. Pada saat yang sama, di satu sisi, saya ingin melihat beberapa tempat yang indah dan menarik, tetapi di sisi lain, waktu yang terbatas tidak memungkinkan saya untuk menyimpang terlalu banyak dari rute langsung.
Situasinya bahkan lebih rumit jika tidak ada atraksi utama di sekitarnya yang diketahui semua orang dan yang dapat dimasukkan dalam rute Anda setelah pencarian singkat di Internet. Apa yang harus dilakukan jika Anda terjebak dalam beberapa Kupchino, yang tentang itu Anda hanya mendengar bahwa lebih baik tidak terjebak di sana? Kita harus pergi dengan navigator, berharap bahwa di jalan akan ada sesuatu yang menarik. Namun, navigator populer hanya mempertimbangkan jarak dan waktu tempuh, tetapi tidak memperhitungkan keunikan rute tersebut. Saya menemukan lebih banyak proyek yang mencoba untuk mempertimbangkan kenyamanan rute jalan kaki (mengarah berkeliling melewati jalan raya yang bising), tetapi saya ingin pergi tidak hanya dengan nyaman, tetapi juga untuk melihat keindahan.
Berpikir sedikit, saya memutuskan untuk mengambil tugas ini sendiri. Seperti biasa, ide umum dari algoritma ini cukup sederhana, tetapi iblis ada dalam rinciannya. Dan dalam hal navigasi, hal-hal kecil bisa sangat signifikan dan dengan risiko kesehatan, karena tidak mungkin ada turis yang akan senang ketika navigator membawanya ke belantara zona industri setengah-ditinggalkan untuk tanda peringatan kecil (pekerjaan, begitu hal itu terjadi) .
Deskripsi algoritma dan contoh-contoh pekerjaan di bawah cut, tautan di akhir.
Ide utama
Ide awal saya adalah ini: unduh peta Open Street Map, parsing, sobek informasi tentang semua objek yang berpotensi menarik bagi pejalan kaki (kami masih harus memutuskan daftar mereka), menggambar beberapa zona penyangga di sekitar mereka. Kami mencari cara dengan kerangka kerja standar, sedikit proses membangun grafik navigasi, sehingga di area ini bobot tepi menjadi lebih rendah dan dengan demikian mengatur daya tarik rute pejalan kaki ke mereka.
Tidak lebih cepat dikatakan daripada dilakukan. Untuk menemukan jalannya, kami menggunakan perpustakaan GraphHopper, yang dapat membaca peta OSM dari kotak, membangun rute untuk berbagai jenis transportasi (mobil, pejalan kaki, sepeda), memiliki beberapa algoritma berbeda untuk menemukan jalan (pencarian sederhana, mencari rute alternatif, semua jenis akselerasi, opsi yang dioptimalkan) ) dan dapat memproses grafik navigasi untuk mempercepat pencarian (pencarian dasar di kota bekerja sangat cepat, dalam beberapa milidetik). Sebagai contoh pekerjaan saya, kota asal saya St. Petersburg dipilih - di sini saya dapat mengevaluasi sendiri kualitas dan ketertarikan rute yang dibangun.
Sebagai hasilnya, versi dasar dari algoritma itu terjebak bersama di atas lutut selama beberapa malam, dan kemudian sebuah perjalanan yang menyenangkan dimulai sepanjang menyapu dan hal-hal kecil, di mana iblis dikenal dan berbohong, yang akan saya bahas nanti.
Objek untuk wisatawan dan masalah dengan OSM
Dalam Open Street Map, setiap objek adalah geometri (Node, Way, atau Relation) ditambah sejumlah pasangan string nilai kunci.
Inilah Istana Musim Dingin di OSM:
Masalahnya adalah karena OSM adalah peta yang terbuka dan dapat diedit oleh peserta, standardisasi lumpuh pada kedua kaki. Untuk menunjuk jenis objek yang sama, satu set tag yang berbeda dan kombinasi objek yang berbeda dapat digunakan, beberapa tag dianggap "kanonik" dan dijelaskan pada wiki, tetapi masih ada banyak opsi, baik alternatif yang keliru atau tidak, tetapi tetap digunakan . Akibatnya, kode apa pun yang berfungsi dengan OSM (terutama navigator dan penyaji) dipaksa untuk mempertimbangkan semua ini dan berisi banyak kode untuk menangani kasus khusus semacam itu.
Sebagai contoh, tag highway = unspecified tidak berarti “semacam jalan dari jenis yang tidak dikenal”, seperti yang dipikirkan oleh banyak pembuat peta, tetapi jenis jalan yang sangat spesifik menurut klasifikasi Eropa, tetapi mereka mencetaknya di mana saja karena namanya. Selain itu, jenis jalan ini mengasumsikan adanya trotoar atau trotoar pejalan kaki, oleh karena itu navigator membangun rute pejalan kaki di sepanjang itu, sementara pejalan kaki tidak pergi ke jalan yang nyata di St. Petersburg (ini adalah jalan mobil). Atau contoh lain: addr: nama rumah kita kadang-kadang menggunakan tag untuk nama bangunan, misalnya, untuk beberapa alasan, sayap barat gedung Staf Umum di Palace Square dinamai setelah tag ini. Sementara panduan OSM mengatakan bahwa itu harus digunakan hanya di negara-negara di mana nama digunakan, bukan nomor rumah (di Jepang tampaknya menjadi kasus), dan untuk nama bangunan resmi menggunakan tag nama dan sejenisnya.
Momen lain yang membuatku kesal adalah menandai area hijau. Ada dua tag berbeda untuk tujuan ini, rekreasi = taman dan penggunaan lahan = rumput. Pada peta mereka terlihat hampir sama: hanya zona hijau, sedikit berbeda warnanya. Sebagai hasilnya, mereka dicampur bersama, seperti yang mereka inginkan. Karena hal ini, sering kali taman pemisah antara gerbong-gerbong jalan menjadi "taman" dan mulai menarik jalur pendakian.
Semua nuansa ini harus ditemukan untuk diri kita sendiri ketika kita membangun dan menganalisis rute.
Sebagai satu set objek yang menarik bagi pejalan kaki, daftar berikut akhirnya dipilih:
- Tempat wisata ditandai pariwisata
- Area hijau. kenyamanan = taman, taman. Setelah beberapa musyawarah, ditambahkan pemakaman landuse = kuburan. Di satu sisi, ada daya tarik begitu-begitu, di sisi lain, misalnya, di Pulau Vasilievsky di St. Petersburg, satu-satunya zona hijau adalah kuburan, yang digunakan penduduk lokal alih-alih taman, tetapi tidak ada taman nyata di sana.
- Air: sungai, danau, kolam. Ada kesalahan dalam air, tag jalur air, dan banyak nilai rangkap. Sangat menyenangkan untuk berjalan di sepanjang kawasan pejalan kaki di hari yang panas. Bagaimanapun, saya pikir begitu sampai saya mencoba memproses Smolensk - tiba-tiba ternyata di kedalaman tepi sungai itu bukan tanggul yang indah seperti milik kami di St. Petersburg, tetapi tanah kosong yang ditumbuhi sampah dan berserakan tempat para pejalan kaki lebih memilih untuk menjauh. Namun sejauh ini tidak mungkin membedakan situasi-situasi ini murni dari peta.
- Bangunan dan struktur bersejarah, ditandai bersejarah. Mereka biasanya hanya cantik
- Hal-hal kecil lainnya di kota ditandai dengan tag kemudahan. Ini memiliki banyak makna, saya memilih hanya beberapa, misalnya, jam jalan (jam) - sering indah, bangunan keagamaan (place_of_worship), semua orang seni jalanan (grafiti) dan beberapa lainnya
- Jalan-jalan pejalan kaki dan alun-alun jalan raya = pejalan kaki
Dalam perjalanan studi, saya menyadari bahwa selain area positif yang menarik pejalan kaki, perlu menambahkan area negatif yang mengusir mereka. Daftar ini sejauh ini meliputi:
- Landuse bangunan = konstruksi. Pejalan kaki tidak senang berjalan di bawah perancah, dalam debu terbang dari lokasi konstruksi
- Area industri dan garasi penggunaan lahan = industri, garasi. Saat itu, nuansa dengan institusi pejalan kaki itu terjadi (dan kami di Institut Desain dan Urbanisme ITMO mengujinya pada siswa yang berjalan di rute yang telah ditentukan dan kemudian menulis ulasan sebagai bagian dari studi tentang kenyamanan berjalan di wilayah Petrograd) di hutan kawasan industri Lenpolygraphmash. Ternyata di sana, tidak seluruh kuartal ditandai dengan tag ini (seperti yang biasanya dilakukan untuk menandai zona industri besar), tetapi setiap bangunan terpisah.
- Idealnya, saya juga ingin membawa pejalan kaki jauh dari jalan raya kota yang luas, tempat itu berdebu, berisik, banyak mobil dan biasanya tidak ada yang bisa dilihat. Namun sejauh ini tidak mungkin untuk mendeteksi mereka secara jelas. Di OSM, pada dasarnya hanya ada jumlah jalur mobil, tetapi kriteria ini tidak cukup (banyak jalan-jalan wisata penting, seperti Nevsky Prospect, juga multi-jalur)
Lenpolygraphmash yang sama, berisi monumen ke percetakan, dan di mana algoritma saya menyeret siswa miskin
Pentingnya Atraksi
Jelas, pemandangannya berbeda. Ada benda-benda besar yang terkenal di dunia - seperti Menara Eiffel atau Katedral St. Isaac di St. Petersburg, yang menarik banyak wisatawan, dan demi kunjungan, orang-orang dapat membuat kail yang layak. Dan ada beberapa dekorasi kota kecil - beberapa seni jalanan, patung kecil di halaman yang siap dilihat orang hanya di sepanjang jalan dan tidak ingin menyeretnya dari jauh. Untuk konstruksi yang benar dari rute yang menarik dan nyaman, perlu untuk belajar bagaimana memisahkan berbagai kategori atraksi, dan semua yang kita miliki di OSM adalah geometri tertentu dan satu set tag. Saya harus datang dengan seperangkat aturan praktis untuk menetapkan "pentingnya" tempat menarik yang selanjutnya menentukan perubahan bobot dalam grafik.
Pada awalnya, nilai penting adalah nol dan meningkat jika kondisi berikut ini benar:
- +3 jika ada tanda bersejarah - hanya bangunan bersejarah yang penting yang memilikinya, dan itupun tidak semuanya
- +3 untuk keberadaan tag wikipedia atau wikidata. Hanya objek-objek penting yang biasanya memiliki halaman wiki sendiri.
- +1 untuk keberadaan tautan atau url - lagi, tidak semua orang memiliki situs mereka sendiri, tetapi sering kali tag ini mengarah ke halaman beberapa katalog dan benda kecil memilikinya
- +1 untuk setiap tag nama. Nama dapat diatur dalam banyak cara, bisa ada segala macam old_name untuk nama atau nama historis yang diterjemahkan ke dalam bahasa lain. Sekali lagi, kehadiran banyak nama menunjukkan cukup pentingnya objek (karena seseorang sudah lelah meletakkan semuanya)
- bangunan: arsitektur - gaya arsitektur, biasanya memakai segala macam monumen arsitektur yang indah
Daftar ini ditentukan secara empiris dan paling tidak memungkinkan Anda untuk memisahkan Istana Musim Dingin dari grafiti tanpa nama di pinggiran kota. Akibatnya, pentingnya 0 berarti beberapa objek kecil tanpa nama lokal (serpihan tanaman hijau, grafiti), sekitar 3-4 sudah menjadi sesuatu yang menarik (gereja, alun-alun di mana Anda dapat duduk dan bersantai), lebih dekat ke 10, atraksi tingkat kota dimulai, Istana Musim Dingin yang sama.
Daftar ini tidak sempurna dan sangat bergantung pada data OSM, yang seringkali tidak lengkap. Misalnya, Gerbang Narva awalnya hanya memiliki satu unit penting, karena tidak ada apa pun selain nama yang ditempelkan pada mereka. Saya harus pergi ke OSM sendiri dan menambahkan nama, gaya, tahun konstruksi, tinggi (untuk menentukan visibilitas dengan benar, apa yang akan terjadi selanjutnya), dll. Secara umum, ada juga manfaat publik dalam hal ini - untuk meningkatkan kualitas rute, saya pergi ke OSM dari waktu ke waktu dan meletakkan tag yang hilang di sana, yang kemudian dapat digunakan oleh navigator atau program lain.
Area pengaruh
Atraksi datang dalam berbagai ukuran. Patung kecil harus dilihat dari jarak tidak lebih dari 5-7 meter. Penunggang Kuda Perunggu terlihat dari 20-30. Katedral St. Isaac, salah satu bangunan tertinggi di pusat kota, terlihat jelas dari 200-300 (dengan ini saya mengerti bahwa turis tidak perlu mendekat, tetapi cukup nyaman untuk menikmati pemandangan dari jarak ini, dapat dilihat bahkan satu kilometer dari bank Neva lainnya. , tetapi tanpa detail). Bagaimana menentukan pada jarak apa daya tarik harus mempengaruhi rute pejalan kaki?
Penunggang Kuda Perunggu dan kubah Katedral St. Isaac di kejauhan
Pertama, saya membangun jari-jari visibilitas empiris. Mereka bergantung pada semua informasi yang tersedia tentang objek wisata dan mengubahnya menjadi salah satu dari empat jari-jari: kecil 30 meter, sedang 100, besar 250 dan besar 350 meter.
Sedikit terpisah adalah visibilitas sungai dan taman. Bagi mereka, saya menetapkan 30 meter, yaitu kira-kira sesuai dengan lebar jalan atau jalan di sekitar taman. Karena melihat taman dari jauh agak tidak ada gunanya, Anda harus pergi ke sebelahnya.
Jenis visibilitas ditentukan oleh aturan:
- Objek titik (yaitu ditentukan oleh tipe Point OSM) adalah visibilitas kecil, ini biasanya monumen kecil dan seni jalanan
- Tetapi titik dan dengan tag bersejarah adalah Sedang, karena ini seringkali merupakan monumen besar di atas tumpuan tinggi, seperti Penunggang Kuda Perunggu yang sama
- Area kurang dari 20 * 20 meter (arah atau hubungan) adalah Sedang
- Lebih banyak - Besar
- Jika objek memiliki tinggi tag (tinggi dalam meter) atau bangunan: level (jumlah lantai), maka pada ketinggian lebih dari 50 meter itu dianggap Besar - ini hanya dibuat khusus untuk Ishak dan katedral besar lainnya serta bangunan yang terlihat dari jauh
Tetapi muncul masalah: dalam kondisi perkembangan padat pusat bersejarah St. Petersburg, pendekatan naif dengan jari-jari tidak berhasil, karena area nyata visibilitas beberapa kuil yang terletak di halaman belakang jauh lebih kecil, bahkan hanya terlihat dari bagian jalan yang berseberangan. Saya harus mulai membangun poligon visibilitas yang jujur.
Gereja St. Catherine berdiri di belakang halaman, dikelilingi oleh rumah-rumah di semua sisi:
Pertama, perlu untuk menentukan hambatan. Nah, semuanya sederhana, saya mengambil dan membaca dari data OSM semua poligon dengan tag bangunan. Ini akan menjadi poligon yang menghalangi visibilitas kami. Kemudian ia menulis algoritma naif sederhana untuk membangun poligon untuk visibilitas suatu titik menggunakan ray tracing. Saya tidak perlu akurasi tinggi di sana, selusin sinar per titik sudah cukup. Pada awalnya, saya mengambil pusat massa geometri tengara tanpa basa-basi lagi, tetapi ini tidak memberikan hasil terbaik untuk bangunan panjang (panjang dan sempit). Oleh karena itu, di masa depan, untuk atraksi besar, saya mulai mengambil tiga titik - pusat massa dan dua titik terjauh darinya dan dari satu sama lain di batas luar. Mengapa saya tidak membangun visibilitas secara jujur? Karena jika algoritme untuk membangun wilayah visibilitas suatu titik adalah sepele (kami membiarkan sinar keluar dari titik di semua arah, melihat di mana mereka melewati rintangan terdekat, menghubungkan titik-titik ini), maka jauh lebih sulit untuk membangun visibilitas jujur dari suatu sisi (dan, akhirnya, sebuah poligon) (yang pertama sampai ke titik keputusan kepala - untuk membangun visibilitas dua ujung tulang rusuk dan menggabungkan - jelas salah).
Hasilnya adalah perkiraan yang baik. Itu dibangun secara tidak sempurna, tetapi untuk kebutuhan navigasi pejalan kaki, akurasi seperti itu sudah cukup bagi kami. Satu-satunya masalah adalah bahwa itu tidak memperhitungkan ketinggian bangunan, mis. setiap stan kecil akan menghalangi pandangan kita tentang menara lonceng berlantai lima. Tetapi tidak ada yang bisa dilakukan - data OSM tidak selalu mengandung sejumlah lantai, dan jauh lebih sulit untuk membangun volume visibilitas dalam 3D. Meskipun mungkin aku akan kembali ke ini.
Membangun poligon visibilitas untuk ini dan gereja-gereja tetangga
Keindahan rute dan cara meningkatkannya
Jadi, kami telah belajar untuk mempertimbangkan pentingnya dan visibilitas objek wisata dan tampaknya sudah mulai membangun rute yang baik. Bagaimanapun, ini benar, ketika saya menguji di daerah pusat St Petersburg, yang memiliki kepadatan keindahan yang sangat tinggi per kilometer persegi.
Namun, ada baiknya bergerak sedikit menjauh dari pusat, ketika tiba-tiba algoritma mulai mengenali ketidakberdayaannya. Dan rute yang dia bangun mulai bertepatan dengan yang terpendek. Karena kucing itu menumpahkan banyak pemandangan di daerah-daerah ini, mereka berada jauh dari satu sama lain, oleh karena itu, ketika mencari jalan menggunakan metrik gabungan "keindahan + jarak", kontribusi istilah pertama ternyata mendekati nol, akibatnya, algoritma yang dibangun hanya rute terpendek.
Tentu saja, orang selalu bisa berkata, "Kami tidak seperti itu, ini adalah kota-kota kami yang membosankan," tetapi itu tidak akan benar. Karena itu, saya bertanya-tanya bagaimana cara mengevaluasi rute yang dibangun, dan bagaimana memperbaikinya. Solusi paling sederhana yang langsung terlintas dalam pikiran adalah untuk memperluas rute dengan memaksa kait ke dalamnya ke tempat menarik yang telah ditinggalkan.
Sekarang, dalam kasus di mana a) jumlah total kepentingan semua daya tarik rute adalah satu kilometer kurang dari nilai tertentu, atau b) pengguna sendiri memilih untuk membangun rute yang paling menarik, algoritma saya mencoba untuk memperbaikinya. Untuk melakukan ini, rute awal dibangun, buffer diambil di sekitarnya (ketebalannya ditentukan oleh panjangnya, semakin lama rute - semakin lama kail diperbolehkan), beberapa pemandangan baru (belum termasuk dalam rute) dengan skor> 2 dicari di dalam buffer ini (kami tidak ingin buat kait per kilometer ke taman umum noname) dan rute baru diletakkan dari titik awal ke target menengah ini, dan dari sana ke titik tujuan. Pada saat yang sama, panjangnya juga dikontrol, sebagai akibatnya, kita harus mendapatkan rute tidak lebih dari dua kali panjang jalur terpendek antara titik awal dan titik akhir.
Versi pertama dari algoritma (di sebelah kiri) tidak berdaya untuk menemukan sesuatu yang menarik dan membangun rute terpendek. Tetapi versi dengan penambahan daya tarik menengah (di sebelah kanan) termasuk
DOT KV-19 di dalamnya, ia berada di sudut kanan bawah rute (pada tingkat zoom ini tidak terlihat, tetapi layanan akan menampilkannya dalam daftar dan memungkinkan Anda menemukannya di peta dengan mengklik nama) .
Bunker yang sama. Secara umum, di Kupchino ada cukup banyak benda yang berhubungan dengan pertahanan Leningrad, karena di sanalah garis pertahanan kota dilewati:
Tentu saja, jauh dari pejalan kaki mana pun akan setuju untuk membuat jalan memutar demi beberapa orang yang tidak berarti dalam pendapatnya. Itulah sebabnya layanan ini menunjukkan panjang rute dibandingkan dengan yang terpendek dan daftar objek wisata di atasnya, dan hanya pengguna yang dapat memutuskan apakah ia tertarik pada rute tersebut. Plus ada slider yang memungkinkan Anda untuk mengurangi (atau sebaliknya meningkatkan) pengait maksimum yang diijinkan.
. - «» . . , , . , . «» ( ), , .
. , , . . . . , ( ), , . , — . . . , , .
sightsafari.city( OSM-, ), , . : , , , — .
. , :
. , , , .
. , .
: ( ) « » . , , , .
Kesimpulan
-, ( ). , . , ( ), - .
— , , , ( , , ), - . - OSM, - , ( , , 2-3 , ).
UPD: , , , , , , --, , , , , , , . , .
UPD 2: OSM, , ( , ), , . - , ( ) - , ( ).
UPD 3: ,
https://vk.com/public168028574