Clever Geek Handbook

Bagaimana menemukan jumlah semua huruf pada semua tanda tipe "masuk ke kota X" di negara? Cara yang tepat untuk menjawab pertanyaan semacam itu

Baru-baru ini, dalam rangka satu wawancara, saya perlu menyelesaikan suatu masalah, yang syaratnya diberikan di bawah ini:

Manajer terbaik di dunia bernama Penultimo memiliki ide cemerlang lainnya, yang harus Anda sadari. Dia percaya bahwa arus wisatawan ke Isla de Educados akan meningkat jika dia dapat memberitahu seluruh dunia berapa banyak rambu-rambu jalan yang indah dengan tulisan panjang yang mereka miliki di pulau itu. Anda diundang untuk membuat algoritme yang memungkinkan Anda menghitung jumlah total huruf pada semua tanda "Pintu masuk ke kota X" di pulau itu, dan kemudian menerapkan pengetahuan yang diperoleh untuk menghitung metrik serupa untuk Republik Belarus. Perhatikan bahasa yang digunakan untuk menunjukkan permukiman, serta fakta bahwa mungkin ada beberapa pintu masuk ke kota. Penultimo juga mendorong inisiatif, sehingga Anda dapat meneliti masalah ini untuk wilayah tertentu, bandingkan dengan jumlah orang yang tinggal di wilayah tersebut,dan juga melakukan penelitian lain yang menurut Anda menarik.


Di bawah potongan tersebut, saya akan menunjukkan solusi yang tepat untuk ini dan masalah serupa lainnya, misalnya: "Berapa banyak pompa bensin yang terletak di Moskow?"



Metode solusi umum



Jika Anda melihat pada peta OpenStreetMap, maka ide berikut segera muncul di benak: mari kita tentukan perbatasannya dan jalan di dalam kota untuk setiap kota, dan kemudian temukan persimpangan mereka, di mana akan ada tanda! Bagaimana kita akan mencari persimpangan: kita ambil satu ruas perbatasan, lalu ruas jalan dan lihat apakah mereka berpotongan (masalah geometris tipikal). Begitu seterusnya sampai semua bagian dan kota selesai.



Tentang arsitektur data OSM
, : , .

ID, .



  • — , ID
  • — ,
  • — , , ,




Jembatan penyeberangan



OverPass - Ini adalah API untuk mendapatkan data dari OpenStreetMap. Ini memiliki bahasa sendiri untuk menulis kueri, Anda dapat membacanya secara rinci di artikel ini .



Untuk membuatnya lebih mudah dan nyaman untuk membuat kueri, ada alat Overpass-turbo , di mana hasil kueri dapat dilihat dalam bentuk yang nyaman dan interaktif.



Menggunakan OverPass API dengan Python



Untuk memproses data dari OSM dengan Python, Anda dapat menggunakan paket Overpy sebagai pembungkusnya.

Untuk mengirim permintaan dan menerima data, Anda perlu melakukan hal berikut: 



import overpy

api = overpy.Overpass()
Data = api.query("""
* *
""")


dimana variabel (?) Data berisi semua yang diberikan server kepada kita.



Bagaimana cara memproses data ini? Misalkan kita memasukkan permintaan berikut untuk mendapatkan batas Minsk: 



relation["type"="boundary"]["boundary"="administrative"]["name:be"="і"];
//:      
>; out skel qt;


Pada output, kami memiliki file XML (Anda dapat memilih Json) dengan struktur berikut: 



<* *>
<     >
  <node id="277218521" lat="53.8605688" lon="27.3946601"/>
  <node id="4623647835" lat="53.8603938" lon="27.3966685"/>
  <node id="4713906615" lat="53.8605343" lon="27.3998220"/>
  <node id="4713906616" lat="53.8605398" lon="27.3966820"/>
  <node id="4713906617" lat="53.8605986" lon="27.3947987"/>
  <node id="277050633" lat="53.8463790" lon="27.4431241"/>
  <node id="277050634" lat="53.8455797" lon="27.4452681"/>
  <node id="4713906607" lat="53.8460017" lon="27.4439797"/>
<    ID ,    >
<way id="572768148">
    <nd ref="5502433452"/>
    <nd ref="277218520"/>
    <nd ref="4713906620"/>
    <nd ref="277218521"/>
    <nd ref="4713906617"/>
    <nd ref="4623647835"/>
    <nd ref="4713906616"/>
</way>
<way id="29079842">
    <nd ref="277212682"/>
    <nd ref="277051005"/>
    <nd ref="4739822889"/>
    <nd ref="4739822888"/>
    <nd ref="4739845423"/>
    <nd ref="4739845422"/>
    <nd ref="4739845421"/>
</way>


Mari dapatkan beberapa data: 



import overpy

api = overpy.Overpass()
Data = api.query("""
relation["type"="boundary"]["boundary"="administrative"]["name:be"="і"];
>; out skel qt;
""")
Xa=Data.ways[0].nodes[0].lon #     
Ya=Data.ways[0].nodes[0].lat # 
Xb=Data.ways[0].nodes[1].lon
Yb=Data.ways[0].nodes[1].lat
NodeID=Data.ways[0]._node_ids[0] # ID    
print(len(Data.nodes)) #   
print(NodeID)
print(Xa,Ya)
print(Xb,Yb)


Dari sudut pandang bekerja dengan OpenStreetMap dengan python, ini semua yang diperlukan untuk mendapatkan data.



Mari langsung ke masalahnya



Untuk mengatasinya, kodenya ditulis dengan Python, Anda bisa melihatnya di bawah spoiler. Harap jangan mengkritik keras untuk kualitas kode, ini adalah proyek besar pertama di atasnya.



Header spoiler 
import overpy


###########################
def line_intersection(line1, line2): #  
    ax1 = line1[0][0]
    ay1 = line1[0][1]
    ax2 = line1[1][0]
    ay2 = line1[1][1]
    bx1 = line2[0][0]
    by1 = line2[0][1]
    bx2 = line2[1][0]
    by2 = line2[1][1]
    v1 = (bx2 - bx1) * (ay1 - by1) - (by2 - by1) * (ax1 - bx1)
    v2 = (bx2 - bx1) * (ay2 - by1) - (by2 - by1) * (ax2 - bx1)
    v3 = (ax2 - ax1) * (by1 - ay1) - (ay2 - ay1) * (bx1 - ax1)
    v4 = (ax2 - ax1) * (by2 - ay1) - (ay2 - ay1) * (bx2 - ax1)
    return (v1 * v2 < 0) & (v3 * v4 < 0)


#######################################
citytmp = []
city = []
Borderway = []
Roadway = []
Total = 0
A = [0, 0]
B = [0, 0]
C = [0, 0]
D = [0, 0]
amount = 0
progressbar = 0 
ReadyData = open(' .txt','w')
with open(" .txt", "r", encoding='utf8') as file:
    for i in range(115):
        citytmp.append(file.readline())
citytmp = [line.rstrip() for line in citytmp]
for i in range(115):
    city.append('"' + citytmp[i] + '"')
city[0]='"і"'

api = overpy.Overpass()
for number in range(0,115):#  ,  
    borderstring = """(
relation["type"="boundary"]["boundary"="administrative"]["name:be"=""" + city[number] + """][place=town]; 
relation["type"="boundary"]["boundary"="administrative"]["name:be"=""" + city[number] + """][place=city];
);
>; out skel qt;"""
    roadstring = """(
area[place=town]["name:be"=""" + city[number] + """]; 
way["highway"][highway!=service]["highway"!="footway"]["highway"!="track"]["highway"!="path"]
    ["highway"!="cycleway"]["highway"!="pedestrian"]["highway"!="steps"]["highway"!="residential"](area);
area[place=city]["name:be"=""" + city[number] + """]; 
way["highway"][highway!=service]["highway"!="footway"]["highway"!="track"]["highway"!="path"]
    ["highway"!="cycleway"]["highway"!="pedestrian"]["highway"!="steps"]["highway"!="residential"](area);
);
out body; >; out skel qt;"""
    print('Getting data about', city[number],'...')
        road = api.query(roadstring)
        border = api.query(borderstring)
    print('got data!, city:', city[number]) # 
    for w in range(len(border.ways)): #  
        for i in range(len(border.ways[w]._node_ids)):#    
            progressbar = i / len(border.ways[w]._node_ids) * 100
            print(progressbar, "%;", w, "of", len(border.ways), "parts ready; city-", city[number])
            A[0] = border.ways[w].nodes[i].lon
            A[1] = border.ways[w].nodes[i].lat
            if i == len(border.ways[w]._node_ids) - 1:
                break
            B[0] = border.ways[w].nodes[i+1].lon
            B[1] = border.ways[w].nodes[i+1].lat
            for j in range(len(road.ways)):
                for k in range(len(road.ways[j]._node_ids)):
                    C[0] = road.ways[j].nodes[k].lon
                    C[1] = road.ways[j].nodes[k].lat
                    if k == len(road.ways[j]._node_ids) - 1:
                        break
                    D[0] = road.ways[j].nodes[k+1].lon
                    D[1] = road.ways[j].nodes[k+1].lat
                    if line_intersection((A, B), (C, D)) == 1:
                        amount += 1
                        print(road.ways[j]._node_ids[k])
    print(amount)
    Total += amount * len(city[number])
    ReadyData.write(str(city[number]))
    ReadyData.write(str(amount))
    ReadyData.write('\n')
    amount = 0
print('Total', Total) #




Catatan kode



Lama-lama saya bikin request, memilih jenis jalan yang berbeda-beda supaya lebih sedikit menghitung dan tidak ketinggalan rambu-rambu. Kueri terakhir hanya menghapus jalan-jalan yang tidak ada rambu-rambu, misalnya perumahan, layanan, jalan setapak, trek, dll.



Saya mengurai daftar kota dari Wikipedia dan menyimpannya dalam format. Bahwa



Kode tersebut memakan waktu lama, saya bahkan pernah berkeinginan sekali menulis ulang dalam C ++, tetapi memutuskan untuk membiarkannya apa adanya. Saya butuh waktu dua hari, semua karena masalah dengan kediktatoran Internet Belarusia dan kelebihan beban server OverPass. Untuk mengatasi masalah kedua, Anda perlu membuat satu permintaan untuk semua kota, tetapi saya belum menemukan cara melakukannya secara normal.



Jawaban saya untuk masalah tersebut

18981





Apa yang ingin saya katakan tentang kebenaran gambar: semuanya bergantung pada kualitas data OSM itu sendiri, yaitu, ada tempat di mana, misalnya, satu jalan melintasi dua garis perbatasan, atau di suatu tempat di persimpangan perbatasan digambar sedikit salah, dan akibatnya kami memiliki terlalu banyak / persimpangan yang hilang. Tetapi ini adalah fitur dari tugas khusus ini yang tidak memiliki arti praktis, selain itu OSM adalah kekuatan.



Tugas kedua



Sekarang mari kita hitung jumlah pompa bensin di Moskow: 

area[name=""];
(
  node["amenity"="fuel"](area);
  way["amenity"="fuel"](area);
  relation["amenity"="fuel"](area);
);
out body;
>;
out skel qt;


Kode 
import overpy

api = overpy.Overpass()
Data = api.query("""
area[name=""];
(
  node["amenity"="fuel"](area);
  way["amenity"="fuel"](area);
  relation["amenity"="fuel"](area);
);
out body;
>;
out skel qt;
""")
print(len(Data.nodes)) #




Hasil - 489 isian:





More articles:


All Articles