Clever Geek Handbook

¿Cómo encontrar el número de todas las letras en todos los letreros del tipo "entrada a la ciudad X" en el país? La forma exacta de responder a tales preguntas.

Recientemente, en el marco de una entrevista, necesitaba resolver un problema, cuya condición se detalla a continuación:

El mejor entrenador del mundo, Penultimo, tiene otra idea brillante, de la que debes darte cuenta. Él cree que el flujo de turistas hacia la Isla de Educados aumentará si puede decirle al mundo entero cuántas señales de tráfico maravillosas con largas inscripciones tienen en la isla. Se le invita a crear un algoritmo que le permita calcular el número total de letras en todas las señales "Entrada a la ciudad X" en la isla, y luego aplicar el conocimiento adquirido para calcular una métrica similar para la República de Bielorrusia. Preste atención al lenguaje utilizado para designar los asentamientos, así como al hecho de que puede haber varias entradas a la ciudad. Penultimo también fomenta la iniciativa, por lo que puede investigar este tema para áreas específicas, comparar con el número de personas que viven en el área,y también realice cualquier otra investigación que le parezca interesante.


Debajo del corte les mostraré la solución exacta a este y otros problemas similares, por ejemplo: "¿Cuántas gasolineras hay dentro de Moscú?"



Método de solución general



Si miras el mapa de OpenStreetMap, inmediatamente te viene a la mente la siguiente idea: obtengamos para cada ciudad sus fronteras y las carreteras dentro de sus fronteras, y luego busquemos sus intersecciones, en las que habrá señales. Cómo buscaremos las intersecciones: tomamos un segmento del borde, luego un segmento de la carretera y vemos si se cruzan (un problema geométrico típico). Y así sucesivamente hasta que se acaben todas las secciones y ciudades.



Acerca de la arquitectura de datos de OSM
, : , .

ID, .



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




Paso superior



OverPass: esta es una API para obtener datos de OpenStreetMap. Tiene su propio lenguaje para escribir consultas, puedes leerlo en detalle en este artículo .



Para facilitar y hacer más conveniente la redacción de consultas, existe una herramienta Overpass-turbo , donde el resultado de la consulta se puede visualizar de forma conveniente e interactiva.



Usando la API OverPass en Python



Para procesar datos de OSM en Python, puede usar el paquete Overpy como contenedor.

Para enviar solicitudes y recibir datos, debe hacer lo siguiente: 



import overpy

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


donde la variable (?) Data contiene todo lo que nos dio el servidor.



¿Cómo procesar estos datos? Supongamos que ingresamos la siguiente solicitud para obtener los límites de Minsk: 



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


En la salida, tenemos un archivo XML (puede elegir Json) con la siguiente estructura: 



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


Consigamos algunos datos: 



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)


Desde el punto de vista de trabajar con OpenStreetMap en Python, esto es todo lo que necesita para obtener los datos.



Vayamos directamente al problema



Para solucionarlo, el código fue escrito en Python, lo puedes ver debajo del spoiler. Por favor, no critique fuertemente la calidad del código, este es el primer proyecto tan grande en él.



Encabezado de 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) #




Notas de código



Hice una solicitud durante mucho tiempo, eligiendo diferentes tipos de carreteras para que fuera menos contar y no perder las señales. La consulta final simplemente elimina aquellas carreteras en las que no hay señales, por ejemplo, residencial, de servicio, acera, pista, etc.



Analicé la lista de ciudades de Wikipedia y la guardé en el formato.tht



El código se está ejecutando durante mucho tiempo, incluso tuve un deseo una vez reescribirlo en C ++, pero decidió dejarlo como está. Me tomó dos días, todo por problemas con la dictadura de Internet bielorrusa y la sobrecarga del servidor OverPass. Para resolver el segundo problema, debe realizar una solicitud para todas las ciudades, pero todavía no he descubierto cómo hacerlo normalmente.



Mi respuesta al problema

18981





Lo que quiero decir sobre la exactitud de la figura: todo se basa en la calidad de los datos del propio OSM, es decir, hay lugares donde, por ejemplo, una carretera cruza dos líneas fronterizas, o en algún lugar de un cruce, la frontera se dibuja un poco mal y, como resultado, tenemos demasiado / intersección faltante. Pero esta es una característica de esta tarea en particular que no tiene un significado práctico, de lo contrario, OSM es una fortaleza.



Segunda tarea



Ahora calculemos la cantidad de estaciones de servicio dentro de Moscú: 

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


El código 
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)) #




Resultado - 489 empastes:





More articles:


All Articles