Andamos pela cidade com sabedoria: como eu fiz o serviço para construir percursos pedestres interessantes

UPD: como o tópico correu bem e mostrou que existe uma demanda por esse serviço, vou desenvolvê-lo ainda mais. Iniciei um público do VKontakte para coletar feedback e publicar informações de atualização https://vk.com/sightsafari

Uma área desconhecida da cidade, uma pequena quantidade de tempo livre e a necessidade (ou desejo) de chegar a pé da estação de metrô / hotel / trem - provavelmente todos pelo menos uma vez entraram nessa situação. Ao mesmo tempo, por um lado, quero ver alguns lugares bonitos e interessantes, mas, por outro lado, o tempo limitado não me permite desviar muito da rota direta.

A situação é ainda mais complicada se não houver grandes atrações nas proximidades que todos conheçam e que possam ser incluídas no seu percurso após uma breve pesquisa na Internet. O que fazer se você estiver preso em algum Kupchino, sobre o qual você ouviu apenas que é melhor não ficar preso lá? Temos que seguir o navegador, esperando que no caminho haja algo interessante. No entanto, os navegadores populares apenas consideram a distância e o tempo de viagem, mas não levam em consideração a interessante do percurso. Me deparei com mais projetos tentando levar em conta a conveniência de uma rota a pé (contornando estradas barulhentas), mas quero ir não apenas confortavelmente, mas também para ver um pouco de beleza.



Pensando um pouco, decidi assumir essa tarefa pessoalmente. Como sempre, a idéia geral do algoritmo é bastante simples, mas o diabo está nos detalhes. E, no caso da navegação, as pequenas coisas podem ser bastante significativas e com risco para a saúde, porque é improvável que qualquer turista fique feliz quando o navegador o levar até a natureza de uma zona industrial semi-abandonada para um pequeno sinal em memória (trabalho, uma vez que aconteceu) .

Descrição do algoritmo e exemplos de trabalho sob o corte, link no final.

Ideia principal

Minha idéia inicial foi a seguinte: faça o download do mapa do Open Street Map, analise-o, retire informações sobre todos os objetos potencialmente interessantes para os pedestres (ainda tivemos que decidir sobre a lista deles), desenhe algumas zonas de amortecimento em volta deles. Estamos procurando maneiras com alguma estrutura padrão, um pouco do processo de construção de um gráfico de navegação, para que nessas áreas os pesos das bordas se tornem mais baixos e, assim, organizem a atração de rotas de pedestres para elas.

Mal disse o que fez. Para encontrar o caminho, usamos a biblioteca GraphHopper, que pode ler mapas OSM da caixa, criar rotas para diferentes tipos de transporte (carro, pedestre, bicicleta), possui vários algoritmos diferentes para encontrar o caminho (pesquisa simples, pesquisa de rotas alternativas, todos os tipos de opções otimizadas e aceleradas) ) e pode pré-processar o gráfico de navegação para acelerar a pesquisa (a pesquisa básica na cidade funciona muito rapidamente, em alguns milissegundos). Para o meu exemplo de trabalho, minha cidade natal de São Petersburgo foi escolhida - aqui eu pude avaliar a qualidade e o interesse das rotas construídas.

Como resultado, a versão básica do algoritmo ficou presa no joelho por algumas noites e, em seguida, uma emocionante jornada começou ao longo do rake e pequenas coisas, nas quais o diabo é conhecido e mente, que discutirei mais adiante.

Objetos para turistas e problemas com OSM

No Open Street Map, cada objeto é uma geometria (Nó, Caminho ou Relação) mais um número de pares de cadeias de valores-chave.

Aqui está o Palácio de Inverno em OSM:



O problema é que, como o OSM é um mapa aberto e editável pelos participantes, a padronização é esfarrapada nas duas pernas. Para designar o mesmo tipo de objetos, um conjunto diferente de tags e uma combinação diferente de objetos podem ser usados, algumas das tags são consideradas "canônicas" e descritas no wiki, mas ainda existem várias opções, simplesmente alternativas e francamente errôneas, mas usadas . Como resultado, qualquer código que funcione com o OSM (especialmente navegadores e renderizadores) é forçado a levar tudo isso em conta e conter um monte de código para lidar com casos especiais.

Por exemplo, a tag highway = não especificada não significa “algum tipo de estrada de um tipo desconhecido”, como muitos mapeadores pensam, mas um tipo muito específico de estrada de acordo com a classificação européia, mas eles a moldam em qualquer lugar por causa do nome. Além disso, esse tipo de estrada assume a presença de uma calçada ou calçada de pedestres; portanto, o navegador constrói rotas de pedestres ao longo dela, enquanto os pedestres não vão para uma estrada tão real em São Petersburgo (essa é a faixa de rodagem da rua). Ou outro exemplo: addr: housename às vezes usamos uma tag para o nome dos edifícios; por exemplo, por algum motivo, a ala oeste do edifício da Casa Geral na Palace Square recebe esse nome. Enquanto os guias OSM dizem que ele deve ser usado apenas em países onde nomes são usados ​​em vez de números de casas (no Japão, parece ser o caso), e para nomes oficiais de edifícios, use o crachá e similares.

Outro momento que me irrita é a marcação de áreas verdes. Existem duas tags diferentes para esse fim: lazer = parque e uso da terra = grama. No mapa, eles têm a mesma aparência: apenas uma zona verde, um pouco diferente na cor. Como resultado, eles são misturados, como querem. Por esse motivo, muitas vezes o gramado que divide as faixas de rodagem da rua se torna um "parque" e começa a atrair trilhas para caminhadas.

Todas essas nuances tiveram que ser descobertas por nós mesmos quando construímos e analisamos rotas.
Como um conjunto de objetos de interesse dos pedestres, a seguinte lista foi finalmente selecionada:

• Atrações turísticas etiquetadas turismo
• Áreas verdes. lazer = parque, jardim. Após alguma deliberação, foram adicionados cemitérios landuse = cemetry. Por um lado, há uma atração mais ou menos, por outro lado, na Ilha Vasilievsky em São Petersburgo, a única grande zona verde é o cemitério, que os habitantes locais usam em vez do parque, mas não há parques reais lá.
• Água: rios, lagos, lagoas. Há uma mistura de água, tags de cursos d'água e vários valores duplicados. É tão bom caminhar ao longo da avenida em um dia quente. De qualquer forma, pensei assim até tentar processar Smolensk - de repente, descobriu-se que nas profundezas da margem do rio não era um aterro bonito como o nosso em São Petersburgo, mas um terreno baldio cheio de vegetação e cheio de lixo, do qual os pedestres preferiam ficar longe. Mas até agora não foi possível distinguir essas situações apenas do mapa.
• Edifícios e estruturas históricos, com a tag histórico. Eles geralmente são apenas bonitos
• Quaisquer outras pequenas coisas na cidade marcadas com etiqueta de cortesia. Tem muitos significados, escolhi apenas alguns, por exemplo, um relógio de rua (relógio) - geralmente é bonito, edifícios religiosos (local_de_ adoração), arte de rua para todos (grafite) e outros
• Ruas e praças de pedestres rodovia = pedestre

No decorrer do estudo, percebi que, além das áreas positivas que atraem os pedestres, é necessário adicionar as negativas que os repelem. Esta lista até agora inclui:

• Landuse de edifícios = construção. Os peões não têm muito prazer em andar sob andaimes, em pó que voa de um canteiro de obras
• Áreas industriais e garagens landuse = industrial, garages. Naquele momento, essa nuance com a instituição de um pedestre aconteceu (e nós, no Instituto de Design e Urbanismo do ITMO, testamos em estudantes que percorreram rotas estabelecidas e depois escrevemos críticas como parte de um estudo sobre o conforto de caminhar na região de Petrogrado) na selva da área industrial de Lenpolygraphmash. Aconteceu que lá, nem todo o trimestre é marcado com essa tag (como é normalmente feito para marcar grandes zonas industriais), mas cada edifício é separado.
• Idealmente, também quero afastar os pedestres das grandes rodovias da cidade, onde é poeirento, barulhento, muitos carros e, geralmente, não há nada para olhar. Mas até agora não foi possível detectá-los sem ambiguidade. No OSM, existe essencialmente apenas o número de faixas de carros, mas esse critério não é suficiente (muitas ruas turísticas importantes, como a Nevsky Prospect, também são de várias faixas)

O mesmo Lenpolygraphmash, contendo em algum lugar um monumento à imprensa e onde meu algoritmo arrastou o pobre aluno

A importância das atrações

Obviamente, as vistas são diferentes. Existem objetos grandes e mundialmente famosos - como a Torre Eiffel ou a Catedral de Santo Isaac em São Petersburgo, que atraem um grande número de turistas e para visitar quais pessoas podem fazer um gancho decente. E há algumas pequenas decorações de cidades pequenas - alguma arte de rua, uma pequena escultura no pátio que as pessoas estão prontas para ver apenas ao longo do caminho e não querem arrastá-las de longe. Para a correta construção de rotas interessantes e convenientes, foi necessário aprender a separar diferentes categorias de atrações, e tudo o que temos no OSM é uma determinada geometria e um conjunto de tags. Eu tive que criar um conjunto de regras práticas para atribuir a “importância” de um ponto de interesse que determina ainda mais as mudanças de peso no gráfico.

Inicialmente, a importância é zero e aumenta se as seguintes condições forem verdadeiras:

• +3 se houver uma etiqueta histórica - apenas os edifícios históricos importantes a possuem e, mesmo assim, nem todas
• +3 pela presença de tags da wikipedia ou da wikidata. Somente objetos importantes geralmente têm suas próprias páginas wiki.
• +1 pela presença de um link ou URL - novamente, nem todo mundo tem seu próprio site, mas geralmente essa tag leva a uma página de algum catálogo e pequenos objetos
• +1 para cada crachá. O nome pode ser definido de várias maneiras; pode haver todos os tipos de old_name para nomes históricos ou nomes traduzidos para outros idiomas. Novamente, a presença de muitos nomes indica a importância suficiente do objeto (já que alguém estava cansado de colocar todos eles no chão)
• edifício: arquitetura - estilo arquitetônico, geralmente usado em todos os tipos de belos monumentos arquitetônicos

Essa lista é determinada empiricamente e, no mínimo, permite que você separe o Palácio de Inverno dos grafites sem nome nos arredores. Como resultado, uma importância de 0 significa algum objeto pequeno e sem nome local (um pedaço de vegetação, grafite), cerca de 3-4 já são algo interessante (uma igreja, uma praça onde você pode sentar e relaxar), perto de 10, começam as atrações no nível da cidade, o mesmo palácio de inverno.

A lista não é perfeita e depende muito de dados OSM, que geralmente são incompletos. Por exemplo, o Portão Narva inicialmente tinha apenas uma unidade de importância, uma vez que nada, exceto o nome, era afixado a eles. Eu tive que ir ao OSM e adicionar nomes, estilo, anos de construção, altura (para determinar corretamente a visibilidade, o que vem a seguir) etc. Em geral, também há um benefício público nisso - para melhorar a qualidade das rotas, eu vou ao OSM de tempos em tempos e coloco tags ausentes lá, que podem ser usadas por outros navegadores ou programas.

Áreas de influência

Atrações vêm em tamanhos diferentes. Uma pequena escultura deve ser vista a uma distância não superior a 5-7 metros. O Cavaleiro de Bronze é bem visível de 20 a 30. A Catedral de Santo Isaac, um dos edifícios mais altos do centro da cidade, é decentemente visível de 200 a 300 (por isso entendo que não é necessário que um turista se aproxime, mas é bastante confortável apreciar a vista a essa distância, pois pode ser vista a um quilômetro do outro lado do Neva , mas sem detalhes). Como determinar a que distância a atração deve afetar as rotas dos pedestres?

O Cavaleiro de Bronze e a cúpula da Catedral de Santo Isaac à distância



Primeiro, criei raios empíricos de visibilidade. Eles dependem de todas as informações disponíveis sobre a atração e a transformam em um dos quatro raios: pequenos 30 metros, médio 100, grande 250 e enormes 350 metros.

Um pouco distante é a visibilidade de rios e parques. Para eles, defino 30 metros, ou seja, corresponde aproximadamente à largura do passeio ou da rua ao redor do parque. Como olhar para o parque de longe é um tanto inútil, você precisa ir ao lado dele.

O tipo de visibilidade é determinado pelas regras:

• Objetos de ponto (ou seja, especificados pelo tipo OSM de ponto) têm pequena visibilidade, geralmente são pequenos monumentos e arte de rua
• Mas aponte e com a tag histórica é Médio, porque geralmente são grandes monumentos em pedestais altos, como o mesmo cavaleiro de bronze
• Áreas com menos de 20 * 20 metros (caminho ou relação) são Médias
• Mais - Grande
• Se o objeto tem uma altura de tag (altura em metros) ou prédio: níveis (número de andares), a uma altura de mais de 50 metros é considerado Enorme - isso foi feito especificamente para Isaac e outras grandes catedrais e edifícios visíveis à distância

Mas surgiu um problema: nas condições de desenvolvimento denso do centro histórico de São Petersburgo, a abordagem ingênua com raios não funcionou, uma vez que a área real de visibilidade de algum templo localizado no quintal era muito menor, na verdade, era visível apenas a partir da seção da rua diretamente à sua frente. Eu tive que começar a construir polígonos honestos (bem, quase) de visibilidade.

A Igreja de Santa Catarina fica nos fundos do pátio, cercada por casas por todos os lados:



Primeiro, foi necessário determinar os obstáculos. Bem, tudo é simples, tirei e li dos dados do OSM todos os polígonos com a tag de construção. Estes serão polígonos que bloqueiam nossa visibilidade. Em seguida, ele escreveu um algoritmo simples e ingênuo para a construção de um polígono para a visibilidade de um ponto usando o traçado de raios. Não preciso de alta precisão lá, uma dúzia de raios por ponto foi suficiente. No começo, peguei o centróide da geometria do ponto de referência sem mais delongas, mas isso não deu os melhores resultados para edifícios longos (longos e estreitos). Portanto, no futuro, para grandes atrações, comecei a ter três pontos - o centróide e os dois pontos mais distantes e um do outro na fronteira externa. Por que não construí visibilidade honestamente? Como se o algoritmo para construir a região de visibilidade de um ponto é trivial (deixe os raios irem do ponto em todas as direções, veja onde eles cruzaram os obstáculos mais próximos, conectem esses pontos), será muito mais difícil criar visibilidade honesta de uma aresta (e, finalmente, de um polígono) (o primeiro trata de decisão principal - construir a visibilidade das duas extremidades das costelas e combinar - obviamente errado).

O resultado é uma boa aproximação. Constrói imperfeitamente, mas para as necessidades de navegação de pedestres, essa precisão é suficiente para nós. O único problema é que ele não leva em consideração a altura dos edifícios, ou seja, qualquer pequeno estande bloqueará nossa visão da torre sineira de cinco andares. Mas não há nada a ser feito - os dados do OSM nem sempre contêm vários andares e é muito mais difícil criar volumes de visibilidade em 3D. Embora talvez eu volte a isso.

Polígonos de visibilidade construídos para esta e igrejas vizinhas

A beleza da rota e como aumentá-la

Assim, aprendemos a considerar a importância e a visibilidade das atrações e parece que começamos a construir boas rotas. De qualquer forma, foi o que aconteceu enquanto eu estava testando nas regiões centrais de São Petersburgo, que têm uma densidade muito alta de belezas por quilômetro quadrado.

No entanto, valeu a pena se afastar um pouco do centro, quando de repente o algoritmo começou a reconhecer sua impotência. E a rota que ele construiu começou a coincidir com a mais curta. Como o gato exibe muitos pontos de vista nessas áreas, eles estão localizados distantes um do outro, portanto, ao procurar um caminho usando a métrica combinada "beleza + distância", a contribuição do primeiro termo acabou por ser quase zero, como resultado, o algoritmo construiu simplesmente as rotas mais curtas.

É claro que sempre se pode dizer: "Não somos assim, são nossas cidades chatas", mas isso não seria muito correto. Portanto, eu me perguntava como avaliar a rota construída e como melhorá-la. A solução mais simples que vem imediatamente à mente é estender a rota forçando um gancho até qualquer ponto de interesse deixado de fora.

Agora, nos casos em que a) a importância total de todas as atrações da rota é um quilômetro a menos que um determinado valor, ou b) o próprio usuário optou por construir a rota mais interessante, meu algoritmo tenta aprimorá-la. Para fazer isso, a rota inicial é construída, um buffer é contornado (sua espessura é determinada pelo comprimento, quanto mais longa a rota - quanto mais o gancho é permitido), várias novas vistas (ainda não incluídas na rota) com pontuação> 2 são pesquisadas dentro dessa reserva (não queremos fazer ganchos por quilômetro para jardins públicos que não sejam o mesmo) e novas rotas são estabelecidas desde o ponto de partida até esse destino intermediário e até o ponto de destino. Ao mesmo tempo, o comprimento é controlado adicionalmente, como resultado, devemos obter uma rota não mais do que o dobro do caminho mais curto entre os pontos inicial e final.

A primeira versão do algoritmo (à esquerda) foi impotente para encontrar algo interessante e construiu a rota mais curta. Mas a versão com a adição de uma atração intermediária (à direita) incluía o DOT KV-19 , está no canto inferior direito da rota (nesse nível de zoom, não é visível, mas o serviço o mostrará na lista e permitirá encontrá-lo no mapa clicando no nome) .



O mesmo bunker. Em geral, em Kupchino existem objetos suficientes relacionados à defesa de Leningrado, pois foi lá que as linhas defensivas da cidade passaram:



É claro que, longe de qualquer pedestre, concordará em fazer um desvio em nome de alguém insignificante em sua opinião. É por isso que o serviço mostra a extensão da rota em comparação com a menor e a lista de atrações, e apenas o usuário pode decidir se está interessado nessa rota. Além disso, existe um controle deslizante que permite reduzir (ou vice-versa aumentar) o gancho máximo permitido.

. - «» . . , , . , . «» ( ), , .

. , , . . . . , ( ), , . , — . . . , , .

sightsafari.city
( OSM-, ), , . : , , , — .

. , :



. , , , .



. , .



: ( ) « » . , , , .

Conclusão

-, ( ). , . , ( ), - .

— , , , ( , , ), - . - OSM, - , ( , , 2-3 , ).

UPD: , , , , , , --, , , , , , , . , .

UPD 2: OSM, , ( , ), , . - , ( ) - , ( ).

UPD 3: , https://vk.com/public168028574