Clever Geek Handbook

كيف تجد عدد جميع الحروف على جميع علامات نوع "دخول المدينة X" في الدولة؟ الطريقة الدقيقة للإجابة على مثل هذه الأسئلة

في الآونة الأخيرة ، في إطار مقابلة واحدة ، كنت بحاجة إلى حل مشكلة ، بشرطها موضح أدناه:

أفضل مدير في العالم اسمه Penultimo لديه فكرة رائعة أخرى عليك إدراكها. إنه يعتقد أن تدفق السياح إلى Isla de Educados سيزداد إذا تمكن من إخبار العالم بأسره عن عدد إشارات الطرق الرائعة التي تحتوي على نقوش طويلة على الجزيرة. أنت مدعو للتوصل إلى خوارزمية تسمح لك بحساب العدد الإجمالي للأحرف على جميع العلامات "مدخل المدينة X" على الجزيرة ، ثم تطبيق المعرفة المكتسبة لحساب مقياس مماثل لجمهورية بيلاروسيا. انتبه إلى اللغة المستخدمة في تعيين المستوطنات ، فضلاً عن حقيقة أنه قد تكون هناك عدة مداخل للمدينة. يشجع Penultimo أيضًا المبادرة ، حتى تتمكن من البحث في هذه المشكلة لمناطق محددة ، ومقارنتها بعدد الأشخاص الذين يعيشون في المنطقة ،وأيضًا إجراء أي بحث آخر تجده ممتعًا.


في إطار الخفض ، سأوضح لك الحل الدقيق لهذه المشكلة وغيرها من المشكلات المماثلة ، على سبيل المثال: "كم عدد محطات الوقود الموجودة داخل موسكو؟"



طريقة الحل العام



إذا نظرت إلى خريطة OpenStreetMap ، تتبادر إلى ذهنك الفكرة التالية على الفور: دعنا نفهم لكل مدينة حدودها والطرق داخل حدودها ، ثم نجد تقاطعاتها ، حيث ستكون هناك علامات! كيف سنبحث عن التقاطعات: نأخذ جزءًا من الحدود ، ثم جزءًا من الطريق ونرى ما إذا كانت تتقاطع (مشكلة هندسية نموذجية). وهكذا حتى تنتهي جميع الأقسام والمدن.



حول هندسة بيانات OSM
, : , .

ID, .



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




OverPass



OverPass - هذه واجهة برمجة تطبيقات للحصول على البيانات من OpenStreetMap. لها لغتها الخاصة لتأليف الاستفسارات ، يمكنك أن تقرأ عنها بالتفصيل في هذه المقالة .



من أجل جعل تكوين الاستعلامات أسهل وأكثر ملاءمة ، توجد أداة Overpass-turbo ، حيث يمكن عرض نتيجة الاستعلام بشكل ملائم وتفاعلي.



استخدام واجهة برمجة تطبيقات OverPass في لغة بايثون



لمعالجة البيانات من OSM في Python ، يمكنك استخدام حزمة Overpy كغلاف.

لإرسال الطلبات واستلام البيانات ، عليك القيام بما يلي: 



import overpy

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


حيث يحتوي المتغير (؟) البيانات على كل ما قدمه لنا الخادم.



كيف يتم معالجة هذه البيانات؟ لنفترض أننا أدخلنا الطلب التالي للحصول على حدود مينسك: 



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


عند الإخراج ، لدينا ملف XML (يمكنك اختيار Json) بالهيكل التالي: 



<* *>
<     >
  <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>


دعنا نحصل على بعض البيانات: 



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)


من وجهة نظر العمل مع OpenStreetMap في Python ، هذا هو كل ما هو مطلوب للحصول على البيانات.



دعنا ننتقل مباشرة إلى المشكلة



لحلها ، تمت كتابة الكود بلغة Python ، ويمكنك رؤيته تحت المفسد. من فضلك لا تأنيب كثيرا لجودة الكود ، هذا هو أول مشروع كبير عليه.



رأس سبويلر 
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) #




ملاحظات التعليمات البرمجية



لقد تقدمت بطلب لفترة طويلة ، واخترت أنواعًا مختلفة من الطرق بحيث يكون احتسابها أقل وعدم تفويت العلامات. يزيل الاستعلام النهائي ببساطة تلك الطرق التي لا توجد عليها إشارات ، على سبيل المثال ، سكنية ، خدمية ، ممر مشاة ، مسار ، إلخ.



لقد قمت بتحليل قائمة المدن من ويكيبيديا وحفظتها بالتنسيق



. أعد كتابتها في C ++ ، لكنها قررت تركها كما هي. استغرق الأمر يومين ، كل ذلك بسبب مشاكل مع ديكتاتورية الإنترنت البيلاروسية والحمل الزائد على خادم OverPass. لحل المشكلة الثانية ، تحتاج إلى تقديم طلب واحد لجميع المدن ، لكني لم أتوصل بعد إلى معرفة كيفية القيام بذلك بشكل طبيعي.



جوابي على المشكلة

18981





ما أريد أن أقوله عن صحة الشكل: كل شيء يعتمد على جودة بيانات OSM نفسها ، أي ، هناك أماكن ، على سبيل المثال ، يمر فيها طريق واحد بخطين حدوديين ، أو في مكان ما عند التقاطع ، يتم رسم الحدود بشكل خاطئ قليلاً ، ونتيجة لذلك لدينا الكثير / التقاطع المفقود. لكن هذه ميزة لهذه المهمة بالذات ليس لها معنى عملي ، وإلا فإن OSM هي القوة.



المهمة الثانية



الآن دعونا نحسب عدد محطات الوقود في موسكو: 

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


الرمز 
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)) #




النتيجة - 489 حشوة:





More articles:


All Articles