Gere polígonos a partir de um conjunto de linhas que se cruzam

10

Esta é uma pergunta simples e bastante comum, que já foi feita para propósitos diferentes (veja este link e também este , por exemplo). Aqui, no entanto, estamos procurando não um pacote de software, mas algoritmos que poderíamos tentar implementar, digamos em Python .

Portanto, como mostrado abaixo, um conjunto de linhas é mapeado (elas já estão aparadas, entre outras).
Algoritmos / idéias para gerar polígonos (como os vermelhos mostrados) ?

insira a descrição da imagem aqui

algorithm polygonize geometry-conversion Desenvolvedor
fonte
O limite do quadrado externo é conhecido ou também deve ser lido nas linhas de entrada?
Devdatta Tengshe

Respostas:

5

Bem, colocamos aqui uma resposta que não é uma resposta completa à nossa pergunta, ou seja, a pergunta permanecerá " aberta para resposta ". No entanto, é uma solução para o problema em questão. Aqui está o truque que usamos:

Primeiro vamos ver os resultados :
insira a descrição da imagem aqui

Portanto, as linhas fornecidas nos leftpolígonos construídos mostradas na middle. Eles são polígonos reais, como mostrado na right;)

Para o algoritmo dado abaixo, usamos o Shapelypacote em Python .

  • linhas ==> MultiLineString {:: M}
  • adicione um pequeno buffer, digamos eps{:: MB}
  • region ==> Polygon {:: P} (a região aqui é um quadrado)
  • P.difference(MB) {polígonos resultantes}

Observe que ele está silencioso rapidamente em operação. No entanto, o ponto que falta é que o algoritmo não é um método original para criar polígonos a partir de linhas . No entanto, funcionou perfeitamente para o problema que tínhamos em nossas mãos.

Desenvolvedor
fonte
4

O JTS Topology Suite possui uma classe Polygonizer, que praticamente faz isso.

Você pode dar uma olhada no código fonte, disponível aqui , e convertê-lo em Python.

Devdatta Tengshe
fonte
Como a descrição do código diz que não funcionará conforme o esperado pelo autor da pergunta: "as bordas devem ser assentidas corretamente; ou seja, elas devem se encontrar apenas em seus pontos finais. O Polygonizer será executado na entrada assentida incorretamente, mas não formará polígonos a partir de bordas com nó "
Pablo
1
Existe uma operação no JTS para dividir corretamente as linhas nos vértices. Talvez o OP também possa ver isso.
Devdatta Tengshe
3

Você pode dar uma olhada no pacote Python Shapely, particularmente polygonize ()

Dave
fonte
Uma observação rápida de que polygonize em Shapely ( from shapely.ops import polygonize) usa GEOS.Polygonize de GEOS . Portanto, este é um link em que existe um link para um link ...: |
Desenvolvedor
Nossas tentativas com polygonizenão foram bem-sucedidas. No entanto, obrigado por nos lembrar Shapelycom o qual poderíamos encontrar uma solução (um truque, na verdade) postada como resposta.
Desenvolvedor
2

Aqui está outra solução que poderíamos encontrar.

Usando DCELpodemos fazer blocos de tocar linhas.

Para Python, há um pacote {aqui} . É uma pequena implementação com alguns bugs. No entanto, com algum esforço, ele pode ser usado para esse problema. Observe também os seguintes estágios:

Um estágio de pré-processamento com o qual todas as interseções entre linhas são encontradas. Portanto, todas as linhas são divididas em segmentos nos pontos de interação. Uma lista de pontos de interseção e uma lista de arestas associadas são as necessárias para o DCEL.

Desenvolvedor
fonte
Como esse método é uma solução original e oferece desempenho muito melhor em comparação com o outro método no qual a differenceoperação está sendo usada.
Desenvolvedor