UPD: dado que el tema ha ido bien y ha demostrado que existe una demanda de dicho servicio, lo desarrollaré más. Comencé un público de VKontakte para recopilar comentarios y publicar información de actualización
https://vk.com/sightsafariUn área desconocida de la ciudad, una pequeña cantidad de tiempo libre y la necesidad (o deseo) de llegar a la estación de metro / hotel / tren a pie, probablemente, al menos una vez, todos se metieron en esta situación. Al mismo tiempo, por un lado, quiero ver algunos lugares hermosos e interesantes, pero por otro lado, el tiempo limitado no me permite desviarme demasiado de la ruta directa.
La situación es aún más complicada si no hay atracciones importantes cercanas que todos conozcan y que puedan incluirse en su ruta después de una breve búsqueda en Internet. ¿Qué hacer si estás atrapado en algún Kupchino, sobre el cual solo escuchaste que es mejor no quedarte atrapado allí? Tenemos que ir en el navegador, esperando que en el camino haya algo interesante. Sin embargo, los navegadores populares solo consideran la distancia y el tiempo de viaje, pero no tienen en cuenta lo interesante de la ruta. Encontré más proyectos tratando de tener en cuenta la conveniencia de una ruta a pie (que conduce sin pasar por carreteras ruidosas), pero quiero ir no solo cómodamente, sino también para ver algo de belleza.
Pensando un poco, decidí emprender esta tarea yo mismo. Como siempre, la idea general del algoritmo es bastante simple, pero el diablo está en los detalles. Y en el caso de la navegación, las pequeñas cosas pueden ser bastante significativas y con un riesgo para la salud, porque es poco probable que cualquier turista esté contento cuando el navegante lo lleve al desierto de una zona industrial medio abandonada para un pequeño letrero conmemorativo (trabajo, una vez que sucedió) .
Descripción del algoritmo y ejemplos de trabajo bajo el corte, enlace al final.
Idea principal
Mi idea inicial fue esta: descargar un mapa de Open Street Map, analizarlo, extraer información sobre todos los objetos potencialmente interesantes para los peatones (aún teníamos que determinar su lista), dibujar algunas zonas de amortiguación a su alrededor. Estamos buscando formas con algún marco estándar, un poco del proceso de construcción de un gráfico de navegación, de modo que en estas áreas los pesos de los bordes se reduzcan y, por lo tanto, organicen la atracción de las rutas peatonales hacia ellos.
Apenas dicho que hecho. Para encontrar el camino, utilizamos la biblioteca GraphHopper, que puede leer mapas OSM desde el cuadro, construir rutas para diferentes tipos de transporte (automóvil, peatón, bicicleta), tiene varios algoritmos diferentes para encontrar el camino (búsqueda simple, búsqueda de rutas alternativas, todo tipo de opciones aceleradas y optimizadas ) y puede preprocesar el gráfico de navegación para acelerar la búsqueda (la búsqueda básica en la ciudad funciona muy rápidamente, en unos pocos milisegundos). Para mi ejemplo de trabajo, elegí a mi nativo San Petersburgo, aquí pude evaluar la calidad e interés de las rutas construidas por mí mismo.
Como resultado, la versión básica del algoritmo estuvo atrapada en una rodilla por un par de noches, y luego comenzó un viaje emocionante a lo largo del rastrillo y las cosas pequeñas, en las que se conoce al diablo y las mentiras, que discutiré más adelante.
Objetos para turistas y problemas con OSM
En el Open Street Map, cada objeto es una geometría (Nodo, Camino o Relación) más una serie de pares de cadenas clave-valor.
Aquí está el Palacio de Invierno en OSM:
El problema es que, dado que OSM es un mapa abierto y editable por los participantes, la estandarización es poco convincente en ambas partes. Para designar el mismo tipo de objetos, se puede usar un conjunto diferente de etiquetas y una combinación diferente de objetos, algunas de las etiquetas se consideran "canónicas" y se describen en la wiki, pero todavía hay un montón de opciones, tanto alternativas simples como francamente erróneas, pero no obstante utilizadas . Como resultado, cualquier código que funcione con OSM (especialmente cualquier navegador y renderizador) se ve obligado a tener todo esto en cuenta y contiene un montón de código para manejar estos casos especiales.
Por ejemplo, la etiqueta carretera = no especificada no significa "algún tipo de camino de un tipo desconocido", como piensan muchos mapeadores, sino un tipo de camino muy específico de acuerdo con la clasificación europea, pero lo moldean en cualquier lugar debido al nombre. Además, este tipo de carretera supone la presencia de una acera o acera peatonal, por lo tanto, el navegador construye rutas peatonales a lo largo de la misma, mientras que los peatones no van a una carretera tan real en San Petersburgo (esta es la calzada de la calle). O otro ejemplo: addr: housename a veces usamos una etiqueta para el nombre de los edificios, por ejemplo, por alguna razón, el ala oeste del edificio del Estado Mayor en la Plaza del Palacio lleva el nombre de esta etiqueta. Si bien las guías de OSM dicen que debe usarse solo en países donde se usan nombres en lugar de números de casa (en Japón parece ser el caso), y para los nombres de edificios oficiales, use la etiqueta de nombre y similares.
Otro momento que me molesta es el marcado de las áreas verdes. Hay dos etiquetas diferentes para este propósito, ocio = parque y uso de la tierra = pasto. En el mapa se ven casi iguales: solo una zona verde, un poco diferente en color. Como resultado, se mezclan, como quieren. Debido a esto, a menudo el césped divisorio entre las calzadas de la calle se convierte en un "parque" y comienza a atraer senderos para caminatas.
Todos estos matices tuvieron que ser descubiertos por nosotros mismos al construir y analizar rutas.
Como conjunto de objetos de interés para los peatones, finalmente se seleccionó la siguiente lista:
- Atracciones turísticas etiquetadas turismo
- Zonas verdes ocio = parque, jardín. Después de algunas deliberaciones, se agregaron cementerios de uso de la tierra = cementerio. Por un lado, hay una atracción regular, por otro, por ejemplo, en la isla Vasilievsky en San Petersburgo, la única zona verde grande es el cementerio, que los lugareños usan en lugar del parque, pero no hay parques reales allí.
- Agua: ríos, lagos, estanques. Hay una mezcla de agua, etiquetas de vías navegables y un montón de valores duplicados. Es muy agradable caminar por el paseo marítimo en un día caluroso. En cualquier caso, pensé que sí hasta que intenté procesar Smolensk: de repente resultó que en las profundidades de la orilla del río no era un hermoso terraplén como el nuestro en San Petersburgo, sino un páramo cubierto de vegetación y basura del que los peatones preferirían mantenerse alejados. Pero hasta ahora no ha sido posible distinguir estas situaciones únicamente del mapa.
- Edificios y estructuras históricos, etiquetados como históricos. Por lo general son simplemente hermosas
- Cualquier otra cosa pequeña en la ciudad marcada con una etiqueta de servicio. Tiene muchos significados, elegí solo unos pocos, por ejemplo, un reloj de calle (reloj): a menudo es hermoso, edificios religiosos (lugar de adoración), arte callejero para todos (graffiti) y algunos otros
- Calles y plazas peatonales autopista = peatonal
En el curso del estudio, me di cuenta de que, además de las áreas positivas que atraen a los peatones, es necesario agregar áreas negativas que los repelen. Esta lista hasta ahora incluye:
- Edificios landuse = construcción. Los peatones no están muy contentos de caminar debajo de andamios, en polvo volando desde un sitio de construcción.
- Zonas industriales y garajes landuse = industrial, garajes. En ese momento, ese matiz con la institución de un peatón sucedió (y nosotros, en el Instituto de Diseño y Urbanismo de ITMO, lo probamos en estudiantes que caminaron por rutas establecidas y luego escribieron reseñas como parte de un estudio de la comodidad para caminar de la región de Petrogrado) en la selva del área industrial de Lenpolygraphmash. Resultó que allí, no todo el trimestre está marcado con esta etiqueta (como generalmente se hace para marcar grandes zonas industriales), pero cada edificio está separado.
- Idealmente, también quiero alejar a los peatones de las amplias carreteras de la ciudad, donde hay mucho polvo, mucho ruido, muchos automóviles y, por lo general, no hay nada que mirar. Pero hasta ahora no ha sido posible detectarlos sin ambigüedades. En OSM, esencialmente solo existe el número de carriles para automóviles, pero este criterio no es suficiente (muchas calles turísticas importantes, como Nevsky Prospect, también son de varios carriles)
La misma Lenpolygraphmash, que contiene en algún lugar de su naturaleza un monumento a la imprenta, y donde mi algoritmo arrastró al pobre estudiante
La importancia de las atracciones
Obviamente, las vistas son diferentes. Hay grandes objetos de fama mundial, como la Torre Eiffel o la Catedral de San Isaac en San Petersburgo, que atraen a una gran cantidad de turistas, y por el simple hecho de visitar, las personas pueden hacer un gancho decente. Y hay algunas decoraciones pequeñas y pequeñas de la ciudad: algo de arte callejero, una pequeña escultura en el patio que la gente está lista para ver solo en el camino y no quiere arrastrarlos desde lejos. Para la correcta construcción de rutas interesantes y convenientes, era necesario aprender a separar diferentes categorías de atracciones, y todo lo que tenemos en OSM es una cierta geometría y un conjunto de etiquetas. Tuve que elaborar un conjunto de reglas generales para asignar la "importancia" de un punto de interés que determina aún más los cambios en los pesos en el gráfico.
Inicialmente, la importancia es cero y aumenta si se cumplen las siguientes condiciones:
- +3 si hay una etiqueta histórica: solo los edificios históricos importantes la tienen, e incluso entonces no todos
- +3 por la presencia de etiquetas de wikipedia o wikidata. Solo los objetos importantes suelen tener sus propias páginas wiki.
- +1 por la presencia de un enlace o una URL: de nuevo, no todos tienen su propio sitio, pero a menudo esta etiqueta lleva a una página de algún catálogo y los objetos pequeños lo tienen
- +1 para cada etiqueta de nombre. El nombre se puede establecer de muchas maneras, puede haber todo tipo de nombre_antiguo para nombres históricos o nombres traducidos a otros idiomas. Una vez más, la presencia de muchos nombres indica la importancia suficiente del objeto (ya que alguien estaba cansado de dejarlos todos)
- edificio: arquitectura - estilo arquitectónico, generalmente se coloca en todo tipo de hermosos monumentos arquitectónicos
Esta lista se determina empíricamente y, como mínimo, le permite separar el Palacio de Invierno del graffiti sin nombre en las afueras. Como resultado, una importancia de 0 significa un pequeño objeto local sin nombre (una pizca de vegetación, graffiti), alrededor de 3-4 ya son algo interesante (una iglesia, una plaza donde puede sentarse y relajarse), más cerca de 10, comienzan las atracciones a nivel de la ciudad, El mismo Palacio de Invierno.
La lista no es perfecta y depende en gran medida de los datos de OSM, que a menudo están incompletos. Por ejemplo, la Puerta de Narva inicialmente tenía solo una unidad de importancia, ya que nada, excepto el nombre, se les asignó. Tuve que ir a OSM y agregar los nombres, el estilo, los años de construcción, la altura (para determinar correctamente la visibilidad, lo que sigue), etc. En general, también hay un beneficio público en esto: para mejorar la calidad de las rutas, voy a OSM de vez en cuando y coloco etiquetas faltantes allí, que luego pueden ser utilizadas por otros navegadores o programas.
Areas de influencia
Las atracciones vienen en diferentes tamaños. Una pequeña escultura debe verse desde una distancia de no más de 5-7 metros. El Jinete de Bronce es bien visible desde 20-30. La Catedral de San Isaac, uno de los edificios más altos del centro de la ciudad, es decentemente visible desde 200 hasta 300 (por esto entiendo que no es necesario que un turista se acerque, pero es bastante cómodo disfrutar de la vista desde esta distancia, se puede ver incluso a un kilómetro de la otra orilla del Neva , pero sin detalles). ¿Cómo determinar a qué distancia la atracción debería afectar las rutas de los peatones?
El jinete de bronce y la cúpula de la catedral de San Isaac en la distancia
Primero, construí radios empíricos de visibilidad. Dependen de toda la información disponible sobre la atracción y la convierten en uno de los cuatro radios: pequeño de 30 metros, mediano de 100, grande de 250 y enorme de 350 metros.
Un poco aparte es la visibilidad de ríos y parques. Para ellos, establezco 30 metros, es decir corresponde aproximadamente al ancho del paseo marítimo o calle alrededor del parque. Ya que mirar el parque desde lejos no tiene sentido, debes ir al lado.
El tipo de visibilidad está determinado por las reglas:
- Los objetos de punto (es decir, especificados por el tipo de OSM de punto) son de poca visibilidad, generalmente son pequeños monumentos y arte callejero
- Pero el punto y con la etiqueta histórica es Medio, porque estos son a menudo grandes monumentos en pedestales altos, como el mismo Jinete de Bronce
- Las áreas de menos de 20 * 20 metros (camino o relación) son medianas
- Más - Grande
- Si el objeto tiene una altura de etiqueta (altura en metros) o edificio: niveles (número de pisos), entonces a una altura de más de 50 metros se considera enorme: esto está hecho específicamente para Isaac y otras grandes catedrales y edificios visibles desde lejos
Pero surgió un problema: en las condiciones de desarrollo denso del centro histórico de San Petersburgo, el enfoque ingenuo con radios no funcionó, ya que el área real de visibilidad de algún templo ubicado en el patio trasero era mucho más pequeña, de hecho, era visible solo desde la sección de la calle justo enfrente de él. Tuve que comenzar a construir polígonos de visibilidad honestos (bueno, casi).
La Iglesia de Santa Catalina se encuentra en la parte posterior del patio, rodeada de casas por todos lados:
Primero, era necesario determinar los obstáculos. Bueno, todo es simple, tomé y leí de los datos de OSM todos los polígonos con la etiqueta de construcción. Estos serán polígonos que bloquean nuestra visibilidad. Luego escribió un algoritmo ingenuo simple para construir un polígono para la visibilidad de un punto usando el trazado de rayos. No necesito alta precisión allí, una docena de rayos por punto fueron suficientes. Al principio, tomé el centroide de la geometría del hito sin más preámbulos, pero esto no dio los mejores resultados para edificios largos (largos y estrechos). Por lo tanto, en el futuro, para grandes atracciones, comencé a tomar tres puntos: el centroide y los dos puntos más alejados de él y el uno del otro en el límite exterior. ¿Por qué no construí la visibilidad honestamente? Porque si el algoritmo para construir la región de visibilidad de un punto es trivial (dejamos que los rayos salgan del punto en todas las direcciones, vemos dónde cruzaron los obstáculos más cercanos, conectamos estos puntos), entonces es mucho más difícil construir una visibilidad honesta de un borde (y, finalmente, un polígono) (el primero llega a decisión de la cabeza: construir la visibilidad de los dos extremos de las costillas y combinarlas, obviamente mal).
El resultado es una buena aproximación. Se construye imperfectamente, pero para las necesidades de la navegación peatonal, tal precisión es suficiente para nosotros. El único problema es que no tiene en cuenta la altura de los edificios, es decir cualquier cabina pequeña bloqueará nuestra vista del campanario de cinco pisos. Pero no hay nada que hacer: los datos de OSM no siempre contienen una serie de pisos, y es mucho más difícil construir volúmenes de visibilidad en 3D. Aunque quizás volveré a esto.
Polígonos de visibilidad construidos para esta y las iglesias vecinas.
La belleza de la ruta y cómo aumentarla.
Entonces, hemos aprendido a considerar la importancia y visibilidad de las atracciones y parece que hemos comenzado a construir buenas rutas. En cualquier caso, esto fue así, mientras estaba probando en las regiones centrales de San Petersburgo, que tienen una densidad muy alta de bellezas por kilómetro cuadrado.
Sin embargo, valía la pena alejarse un poco del centro, cuando de repente el algoritmo comenzó a reconocer su impotencia. Y la ruta que construyó comenzó a coincidir con la más corta. Dado que el gato arrojó muchas vistas en estas áreas, están ubicadas lejos una de la otra, por lo tanto, al buscar una ruta utilizando la métrica combinada "belleza + distancia", la contribución del primer término resultó ser cercana a cero, como resultado, el algoritmo construyó simplemente las rutas más cortas.
Por supuesto, uno siempre podría decir: "No somos así, estas son nuestras ciudades aburridas", pero eso no sería muy correcto. Por lo tanto, me preguntaba cómo evaluar la ruta construida y cómo mejorarla. La solución más simple que viene a la mente de inmediato es extender la ruta forzando un gancho en ella a cualquier punto de interés que haya quedado fuera.
Ahora, en los casos en que a) la cantidad total de importancia de todas las atracciones de la ruta es un kilómetro menos que un cierto valor, ob) el usuario mismo eligió construir la ruta más interesante, mi algoritmo intenta mejorarla. Para hacer esto, se construye la ruta inicial, se toma un búfer a su alrededor (su grosor se determina por la longitud, cuanto más larga sea la ruta, más tiempo se permite hacer el gancho), se buscan varias vistas nuevas (aún no incluidas en la ruta) con puntaje> 2 dentro de este búfer (no queremos haga ganchos por kilómetro a jardines públicos que no sean el mismo) y se establecen nuevas rutas desde el punto de partida hasta este objetivo intermedio, y desde este hasta el punto de destino. Al mismo tiempo, la longitud se controla adicionalmente, como resultado, debemos obtener una ruta que no sea más del doble que la ruta más corta entre los puntos inicial y final.
La primera versión del algoritmo (a la izquierda) fue incapaz de encontrar algo interesante y construyó la ruta más corta. Pero la versión con la adición de una atracción intermedia (a la derecha) incluía el
DOT KV-19 , está en la esquina inferior derecha de la ruta (a este nivel de zoom no es visible, pero el servicio lo mostrará en la lista y le permitirá encontrarlo en el mapa haciendo clic en el nombre) .
El mismo búnker. En general, en Kupchino hay suficientes objetos relacionados con la defensa de Leningrado, ya que fue allí donde pasaron las líneas defensivas de la ciudad:
Por supuesto, lejos de cualquier peatón estará de acuerdo en hacer un desvío por el bien de algunos insignificantes en su opinión. Es por eso que el servicio muestra la longitud de la ruta en comparación con la más corta y la lista de atracciones, y solo el usuario puede decidir si está interesado en dicha ruta. Además, hay un control deslizante que le permite reducir (o viceversa aumentar) el gancho máximo permitido.
. - «» . . , , . , . «» ( ), , .
. , , . . . . , ( ), , . , — . . . , , .
sightsafari.city( OSM-, ), , . : , , , — .
. , :
. , , , .
. , .
: ( ) « » . , , , .
Conclusión
-, ( ). , . , ( ), - .
— , , , ( , , ), - . - OSM, - , ( , , 2-3 , ).
UPD: , , , , , , --, , , , , , , . , .
UPD 2: OSM, , ( , ), , . - , ( ) - , ( ).
UPD 3: ,
https://vk.com/public168028574