Construindo um polígono sobre uma área acessível

10

Atualmente, estou trabalhando no campo de isócronas e nos algoritmos subjacentes. O que agora causa problemas não é o cálculo da própria isócrona, mas a visualização dos resultados.
O resultado do meu algoritmo de isócrona são pontos e arestas. Na verdade, eu tenho uma solução funcional, mas para 3873 bordas e para 1529 nós as coisas parecem durar uma eternidade (cerca de 2,0 segundos no meu laptop Lenovo T440s, que contém uma CPU Core i7 2015 e um SSD bastante rápido). Em vez de segundos, quero algo mais como msec :-).

Talvez alguém possa me ajudar a reduzir o tempo de cálculo necessário para construir os polígonos que visualizam as áreas acessíveis.

Mas espere ... as primeiras coisas primeiro!
Aqui está uma visualização das arestas que são o resultado do cálculo da minha isócrona: Resultado do cálculo de isocrono (esqueleto existente de cadeias de linhas) essas arestas são armazenadas em uma tabela de banco de dados PostGIS e são cadeias de linhas simples.

O que quero mostrar ao usuário é o seguinte: insira a descrição da imagem aqui Observe as áreas desconectadas no sul e leste da imagem. Elas devem ser desenhadas como áreas separadas (portanto, nenhuma fusão é permitida aqui :-))

Atualmente, estou usando esta consulta:

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_MakePolygon(ST_ExteriorRing(ST_GeometryN(segments, generate_series(1, ST_NumGeometries(segments))))) AS polygons FROM (
        SELECT ST_Union(ST_Buffer("GEOMETRY", 20, 'quad_segs=2')) AS segments FROM my_edges AS a
    ) AS b
) AS c

Eu já fiz algumas experiências e também li muita documentação, mas simplesmente não consigo encontrar uma solução melhor.
A meu ver, o grande problema é o uso do ST_Union (conforme declarado nos documentos, essa função pode ser lenta). O mais interessante é que substituí-lo por ST_Collect parece desacelerar o cálculo ST_Buffer para que a consulta a seguir leve mais tempo, embora não preencha as áreas entre as bordas (apenas cria um buffer ao redor das linhas ):

SELECT ST_AsGeoJson(St_Transform(ST_Multi(ST_Collect(polygons)), 4326)) AS coverage FROM (
    SELECT ST_Buffer(ST_Collect(ST_LineMerge("GEOMETRY")), 20, 'quad_segs=2') AS polygons FROM my_edges AS a
) AS b

Isso leva cerca de 3,8 segundos no meu sistema (quase o dobro do tempo). Minha primeira conclusão dessa pequena referência é que ST_Buffer fica inesperadamente lento quando se trata de MultiLineStrings (ainda mais lento do que ao criar buffers para cada linha e mesclar os buffers - o que aos meus olhos é estranho)

Também tentei usar formas alfa (usando a implementação de pgRouting), mas como não há valor alfa a ser definido (e, na verdade, não seria agora a que valor definir esse valor), apenas recebo um ótimo polígono ( então eu perderia as regiões no sul e leste como regiões separadas, e não é isso que eu quero).
O ST_Polygonize (que foi a primeira coisa que me veio à cabeça) não produziu nenhum resultado utilizável, mas talvez eu tenha perdido algo aqui ...

Existe uma maneira melhor de criar a área mostrada no PostGIS? Talvez também usando o código java (jts) ou o código javascript do lado do cliente (jsts)? Na verdade, eu poderia perder alguns detalhes, desde que as áreas mostradas em meu resultado permaneçam separadas e o cálculo fique (muito) mais rápido.

Nikolaus Krismer
fonte
Você não pode apenas usar ST_Exteriorring (ST_Dump (ST_Union (ST_Buffer (geom, ....))). Geom, visto como algo em buffer, será um polígono de qualquer maneira, e ST_Union conectará todas as geometrias que se cruzam, portanto, não é necessário MakePolygon ou GeometryN. Pode ser necessário testar Linestrings que às vezes resultam de ST_Union após um buffer, mas isso é fácil com ST_GeometryType (geom). Quanto ao uso de Java ou jsts, você pode, mas é improvável que seja mais rápido, uma vez que grande parte das funções (GEOS) Postgis são portas de JTS C / C ++, em primeiro lugar.
John Powell
Você está certo, isso funciona, mas, na verdade, não é mais rápido (leva ~ 3,1 segundos, enquanto o uso de GeometryN leva 2 segundos). Aqui está o que eu usei: SELECT ST_AsGeoJson (ST_Transform (ST_Exteriorring ((ST_Dump (ST_Union (ST_Buffer ("GEOMETRY", 20)))). Geom), 4326)) FROM my_edges;
Nikolaus Krismer
@ john-barça: Oh .. eu misturo o quad_segs = 2 partes no ST_Buffer ao tentar sua abordagem ... com essa alteração, as consultas são pares (ambas em torno de 2 segundos). No entanto, isso ainda é muito lento (aos meus olhos), existe outra maneira de tentar?
Nikolaus Krismer 13/07/2015
Problema interessante .... você deseja compartilhar alguns dados de teste?
Dbaston 15/07
Se ajudar, fico feliz em compartilhar alguns dados. Todas as coisas que faço aqui são de código aberto, portanto isso não deve ser um grande problema. Primeira coisa a notar: Um aplicativo da web para teste está localizado em dbis-isochrone.uibk.ac.at:8080/testing . Mais informações sobre as coisas em que trabalho podem ser encontradas em dbis-isochrone.uibk.ac.at . Na seção "ligações" do site existem algumas outras referências (incluindo alguns dados de teste)
Nikolaus Krismer

Respostas:

5

Deixando de lado a serialização GeoJSON, o seguinte leva cerca de 6,3 segundos no meu laptop:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(geom, 20, 2)))).geom))
FROM bz_edges

Observando os dados no OpenJUMP, notei bastante detalhe nos segmentos das ruas, em relação ao nível de detalhe desejado na saída. Parece que mesmo uma simplificação on-the-fly dessas linhas pode produzir uma grande aceleração no PostGIS:

SELECT
  ST_MakePolygon(
    ST_ExteriorRing(
      (ST_Dump(
        ST_Union(
          ST_Buffer(ST_Simplify(geom, 10), 20, 2)))).geom))
FROM bz_edges

o que reduz as coisas para 2,3 segundos. Eu pensei que talvez pudesse fazer melhor armazenando a geometria generalizada em uma coluna separada, em vez de calculá-la em tempo real, mas isso realmente não forneceu nenhum benefício adicional.

Dependendo da quantidade de código que você deseja escrever, é quase certo que você pode se sair melhor em Java, se nada mais, porque você pode tirar proveito de vários núcleos. (Pelo que vale a pena, o JTS executa a operação acima em 2,8 segundos). Uma abordagem pode ser estender CascadedPolygonUnionpara que algumas das operações sindicais ocorram paralelamente. (atualização - aqui está um ParallelCascadedPolygonUnion )

Percebi nos dados da amostra que as bordas são armazenadas com referências aos nós iniciais e finais, ou seja, você tem um gráfico pré-construído. Suspeito que você possa gerar esses polígonos muito mais rapidamente se trabalhar com o gráfico em vez de usar operações de geometria genérica. Por exemplo, acho que você poderia fazer algo assim:

  1. identificar os componentes conectados do gráfico
  2. para cada componente conectado, localize o nó com a coordenada X mínima (com garantia de estar do lado de fora do componente)
  3. passe pelas bordas do componente, sempre virando para a esquerda (ou direita) quando possível. Isso fornecerá o anel externo de cada componente.
  4. poligonize o anel externo e tampe adequadamente.
dbaston
fonte
Obrigado ... a simplificação é uma melhoria excelente e até "simples". O tempo necessário no meu laptop foi reduzido a 1,5 segundo. Não é onde eu quero estar, mas um pouco melhor.
Nikolaus Krismer
Em relação à sua solução sugerida (pontos 1 a 4). Parece também muito simples e vale a pena tentar. Pensei em algo semelhante, mas estou preso no ponto1 (muito cedo :-)). Como identificar os componentes conectados (a única coisa em que consigo pensar é em uma consulta recursiva que também pode ser muito lenta).
Nikolaus Krismer
@NikolausKrismer Eu uso o JGraphT e o tear para tarefas como essa. Se você escrever seus próprios métodos gráficos (não é uma má idéia para obter o melhor desempenho), uma pesquisa aprofundada encontrará os componentes. (Você pode encontrá-los no próximo PostGIS 2.2 com, ST_ClusterIntersectingmas acho que você deseja que qualquer tipo de processamento de gráfico aconteça fora do banco de dados, portanto isso provavelmente não é útil).
dbaston
estas são algumas ótimas dicas. Eu olhei para o JGraphT e isso certamente poderia ajudar a resolver o meu problema. No entanto, também observei o Postgis 2.2 e a função ST_ClusterIntersecting -> são necessários cerca de 200-250 ms para identificar os diferentes clusters no caso acima. Tudo bem para mim (o JGraphT certamente poderia fazer melhor). Agora eu tenho que lidar com a criação do exteriorRing (ST_ExteriorRing falhar, uma vez ST_MakePolygon diz minhas Linkes não são shell)
Nikolaus Krismer
Vejo duas complicações: (a) você precisa não apenas do anel externo, mas também de todos os segmentos que se estendem para fora desse anel; e (b) parece que suas linhas não se cruzam em alguns cruzamentos. Você precisará corrigir (b) se tentar construir uma geometria a partir dos resultados de uma caminhada de gráfico.
Dbaston 16/07/2015