O que é uma maneira eficiente de detectar cruzamentos em um mapa?

14

Posso receber mapas de qualquer fonte para o meu projeto e para o algoritmo C ++ que estou criando, é imperativo que o algoritmo saiba onde estão os cruzamentos (nós onde mais de dois segmentos de estradas se encontram). Além disso, em muitos dos mapas que recebo, há estradas ultrapassando e ultrapassando (ou seja: estradas não estão conectadas corretamente). Uma maneira de corrigir o problema é 'limpando' a rede rodoviária usando o Autocad. As perguntas que tenho são:

  1. Existe uma maneira eficiente (qualquer software que possa fazer isso) de obter meu mapa em um formato GML, que contém informações sobre entroncamentos no mapa? (talvez tenha uma tag GML que diz que um nó específico é uma junção)
  2. Existe outra maneira de 'limpar' a rede rodoviária?

Os colegas sugeriram o FME, mas isso envolve escrever scripts e não temos certeza se o script seria flexível o suficiente para atender a todos os mapas. A única outra maneira de detectar junções é usar força bruta e descobrir quais segmentos de estrada têm nós comuns. O ArcGIS ajudaria? (não usei, mas já ouvi falar) Tenho certeza de que deve haver uma maneira melhor ...

Nav
fonte
2
Precisa encontrar estradas que se cruzam? Como ele deve lidar com geometrias degeneradas (polilinhas em que todos os vértices coincidem tendo, portanto, comprimento zero). Como ele deve lidar com linhas coincidentes onde a interseção é um segmento linear e não apenas um ponto?
Kirk Kuykendall
@ Kirk: Estou um pouco chocado com as situações que você mencionou. Sou novo no GIS e nem sabia que essas possibilidades existiam. 1.Self interseção requer vários segmentos. A menos que seja um viaduto, eu consideraria essas interseções como junções. 2. Nem consigo visualizar o que é geometria degenerada, então não sei o que responder. 3. As linhas de cooperação devem ser tratadas como duas estradas separadas, porque é assim que eu suponho que elas também estariam na vida real.
Nav

Respostas:

9

Se você tiver as estradas em uma forma espacial, como um Shapefile, poderá carregá-las no PostGIS e encontrar automaticamente as que utilizam uma consulta SQL. Eu já fiz isso antes - a instrução SQL foi projetada para encontrar para cada estrada as que se cruzam geograficamente e criar um ponto nodal para cada travessia.

Vou tentar limpar isso mais tarde, mas aqui está o fluxo básico que você pode tomar ...

for line in road_layer_lines:
    ilines = get_intersecting_objects(line)
    for iline in ilines:
        road_junctions.extend(get_intersection(line, iline))

As funções ST_ * são o que faz isso funcionar no PostGIS

  • ST_Envelope : agarra a caixa delimitadora de uma determinada geometria - isso é usado para acelerar o algoritmo. Pode-se restringir uma pesquisa geográfica com as caixas delimitadoras em um passe rápido, mas menos preciso, e depois digitalizar os resultados com as geometrias reais.
  • ST_Intersects : determina se duas geometrias se cruzam
  • ST_Intersection : retorna a interseção de duas geometrias

A seguir, são apenas trechos, já que não tenho tempo para terminar, talvez alguém possa editá-lo antes de eu voltar aqui ...

SELECT id, the_geom FROM road_lines
SELECT roads.id FROM road_lines roads WHERE ST_Intersects(roads.the_geom, my_geom)
SELECT ST_Intersection(roads.the_geom, my_geom) FROM road_lines roads WHERE roads.id = my_id
dmsnell
fonte
Compartilhando apenas: Outro banco de dados que encontrei é este - < oracle.com/technetwork/database/berkeleydb/overview/index.html >. Aparentemente, as consultas são muito rápidas porque estão disponíveis como bibliotecas que podem ser incorporadas no aplicativo.
Nav
1
@ dmsnell- Talvez você possa fornecer um exemplo do tipo de consulta SQL usada para realizar esta tarefa?
RyanKDalton
11

Você pode analisar polilinhas de maneiras surpreendentes usando buffers. Isso geralmente é ineficiente - os buffers criam muitos vértices adicionais - mas (a) é uma técnica disponível em muitos SIGs (baseados em vetor ou raster) e (b) às vezes pode produzir informações difíceis de obter.

Nesse caso, o buffer da estrada em uma pequena quantidade e, em seguida, o buffer pelo negativo da mesma quantidade deixam pequenas "ilhas" em todas as curvas e em todos os cruzamentos. É fácil provar geometricamente.

Aqui está um exemplo de um buffer de polilinha de 10 m (cinza) e seu buffer de-10 m (vermelho claro) em um mapa com 650 m de largura:

figura 1

Agora, cruze a camada de polilinha original com esses polígonos da ilha, mescle os segmentos pelo identificador da ilha e conte as peças:

Figura 2

Os segmentos amarelos claros designam as peças de alta contagem e os segmentos ciano escuro designam as peças de baixa contagem. Dessa maneira, (a) encontramos todas as curvas e interseções (incluindo auto-interseções) e junções próximas (veja a extrema esquerda, onde os dois segmentos não se encontram completamente)) e (b) diferenciamos as curvas das interseções. Podemos encontrar as quase junções selecionando as ilhas que contêm dois ou mais segmentos conectados: as dobras contêm apenas segmentos conectados.

Devido à simetria do buffer, os centróides das ilhas de interseção são os pontos de interseção.

Um aspecto bonito desse estilo de análise é que ele não se importa com a representação da polilinha subjacente: pode ser um recurso único, pode ser um recurso para cada segmento de linha ou qualquer outro meio.

whuber
fonte
6

Sim, você poderia fazer isso com o FME, com certeza. Existem muitos "transformadores" que lidam com limpeza, interseções e topologia; Eu tentaria o transformador TopologyBuilder neste caso.

Qualquer script é feito em um ambiente gráfico, por isso é muito simples.

Você sempre pode obter uma versão de teste em www.safe.com

(Divulgação: Mark Ireland, também conhecido como FME Evangelist, Safe Software Inc.)

Mark Ireland
fonte
Eu segundo isso. O FME é ótimo para esse problema específico, tanto na transformação do AutoCAD para GML quanto na limpeza topológica. Pode ser surpreendentemente universal em sua aplicação.
Blord-castillo
-1

O analista de rede da Arcgis, que você pode obter com uma avaliação gratuita, faz isso em menos de 10 segundos e com apenas alguns cliques.

Thad
fonte
-1

O processo pode ser feito no ArcGIS com o analista de rede.

Há também outra maneira no ArcGIS: você pode seguir as etapas a seguir: "Arctoolbox" → "Ferramentas de gerenciamento de dados" → "recursos" → "apresentam vértices aos pontos" e aí você pode fazer o que precisa.

Abed
fonte