Linhas para polígonos

11

Não consegui encontrar o "nome" do algoritmo que permitiria converter linhas em polígonos. Como esse problema cruza o SIG e os campos da geometria computacional e da ciência da computação. Não tenho certeza do que mais adicionar à mistura. Estou relutante em fornecer uma lista do que pesquisei, pois também gostaria de saber o que as outras pessoas considerariam sua primeira escolha de critérios de pesquisa.

O cenário ... Eu tenho linhas (dois pontos necessários para construir uma linha) ... cada linha está conectada a pelo menos uma outra linha. O espaço intermediário entre as linhas conectadas formaria um polígono. O cenário mais simples seria um triângulo ... um retângulo ... e seria possível ir além para recursos multissegmentados.

Desculpe por descrições vagas, mas como eu disse, não quero guiar as possíveis soluções por um caminho que já visitei, pois estou interessado no "primeiro pensamento" tanto quanto na solução final.

polygon algorithm geometry-conversion Germán Carrillo
fonte
As linhas podem coincidir? As linhas podem se cruzar? (ou seja, está limpo?) Em caso afirmativo, espero que chamar esse processo de Build não seja muito específico do aplicativo.
precisa saber é o seguinte
As linhas Kirk Coincident e outros "defeitos" teriam sido removidos antes da construção dos polígonos ... Estou tentando encontrar o "nome do algoritmo", que tenho certeza de que foi implementado em vários pacotes GIS (por exemplo, arcgis). Portanto, em resumo, considere que todas as condições degeneradas foram tratadas e você fica com linhas limpas (linhas de 2 pontos) que coincidem nos nós que você deve conseguir construir polígonos. A chave é que as linhas existem, não há condições degeneradas e o espaço intermediário precisa ser convertido em polígonos. Graças
Os pontos estão em um avião ou em uma esfera?
precisa saber é o seguinte
Kirk ... Em um plano, coordenadas métricas x, y, não coordenadas esféricas. Por exemplo, digamos que você tenha os segmentos de linha que formariam um diagrama de voronoi, mas tudo que você tem são os segmentos que o formam, mas não a estrutura de dados real que o levou a ele. Em resumo, cada segmento está conectado e cada segmento é único.

Respostas:

4

Talvez "área preenchida"? Veja aqui e aqui .

Editar

Outra possibilidade é a triangulação restrita . (O link é para um applet Java que permite desenhar um gráfico com o mouse e depois ilustra um algoritmo de varredura de avião para triangulá-lo.) O resultado de qualquer triangulação, independentemente de como é realizada, pode ser prontamente processado para crie os polígonos desejados: basta mesclar todos os triângulos vizinhos que compartilham uma aresta recém-criada.

Exemplo

Gráfico original:

Gráfico original

Gráfico triangulado:

insira a descrição da imagem aqui

whuber
fonte
Bill Vai votar desde que eu não tinha percebido isso ... não querendo limitar outros comentários de pessoas em várias disciplinas.
Embora, lidando amplamente com preenchimentos de varredura, esta seja a resposta mais próxima. Eu ainda não tenho um nome de algoritmo, a menos que esteja anexado a uma varredura ou vetor, mas um algoritmo de "varredura" pode ser suficiente, mas não consigo descobrir por toda a minha vida por que as coordenadas seriam classificadas por Y em vez de X ( fácil de implementar na maioria dos idiomas).
@ Dan Classificar por y ou x é irrelevante, como você sugere. Você também está certo de que os algoritmos de varredura plana ou de linha estão envolvidos, mas infelizmente essa é uma técnica geral que cobre quase todos os procedimentos de geometria computacional, portanto, não é um termo adequado para pesquisar especificamente por seu algoritmo. Observe que esse problema em particular não é puramente teórico dos grafos, porque envolve uma incorporação do complexo de polilinha em um plano (ou esfera) e, portanto, um bom algoritmo deve manter informações sobre a incorporação: é por isso que realmente é um problema de preenchimento de área no coração.
whuber
5

Na teoria dos grafos , essa operação é chamada de computação de faces . Está relacionado ao cálculo do dual de um dado gráfico.

Por exemplo, na biblioteca java GeOxygène , um gráfico (chamado CarteTopo ) possui um método getFaces para recuperar sua face .

Isso é chamado de poligonização no JTS

julien
fonte
Bons links. No entanto, todos eles presumem que o problema de @ Dan já foi resolvido: poder chamar um gráfico de "plano" significa que você já identificou as faces poligonais. Ele quer saber como se converte uma coleção arbitrária de arcos (no plano) em um gráfico planar de honestidade e bondade. Isso requer a construção de uma representação de sua "topologia", como um DCEL.
whuber
Muito obrigado whuber, você é uma fonte de conhecimento! Eu me pergunto como alguém pode ser tão brilhante.
julien
4

O software host RepRap converte uma lista de segmentos de linha (em alguma ordem aleatória desconhecida) em uma lista de polígonos, que soa semelhante ao que você está tentando fazer.

Em particular, o algoritmo RepRap "end matching" lida com vários casos patológicos.

Infelizmente, o software RepRap pressupõe que cada canto possui um número par de arestas - 2 linhas indo para um canto em um objeto normal; 4 linhas indo juntas quando o canto de um objeto toca o canto de outro objeto, etc. Não sei quão difícil seria adaptar esse algoritmo para lidar com diagramas de voronoi, que geralmente tem três arestas em cada canto.

David Cary
fonte
+1 Encontrar interessante! Cuidado: embora este software pareça capaz de resolver muitos problemas relacionados à conexão de linhas em polígonos, ele pode fazer muito : parece que tenta simplificar os recursos também, o que pode ser um efeito colateral indesejável. (Por exemplo, ele pode destruir a integridade topológica.)
whuber
3

você explorou a base de código do GRASS para uma solução para o seu problema? -> http://old.nabble.com/Polyline-to-Polygon-operation-td20257839.html

oeon
fonte
1
Obrigado ... mas não estou procurando uma solução "empacotada" específica, mas o algoritmo subjacente e / ou o nome que viria nas várias áreas do GIS, Comp Geom e / ou Comp Sci ... manter as idéias chegando
Eu estava pensando em olhar especificamente para o código-fonte por trás dos 2 processos mencionados no meu link para ajudá-lo.
oeon 14/01
Acho que teria que instalar o software para ver o código, pois não vejo nenhuma listagem nessas páginas, a menos que esteja faltando alguma coisa.
1
Você pode procurar a fonte do GRASS on-line: trac.osgeo.org/grass/browser
underdark
@underdark Obrigado pelo ponteiro. Tanto quanto posso dizer main.cna v.typefonte, tudo o que acontece é que os recursos são rotulados como limites: nenhum processamento real ocorre. Em retrospecto, isso não é muito surpreendente: se (não sei ao certo) os recursos são mantidos com informações topológicas 2D completas, todo o cálculo para identificar regiões poligonais ocorre automaticamente durante a criação ou importação de recursos e é mantido por toda parte todas as operações de geoprocessamento.
whuber
3

Hallo

Eu não acho que o que você está procurando é um algoritmo específico. A tarefa pode ser bastante difícil ou muito simples, dependendo do seu conjunto de dados.

Você deve dividir o problema em pelo menos 2 partes. 1) é mais um problema de rede, como encontrar anéis fechados de cadeias de linhas. 2) expressar a cadeia de linhas fechada como um polígono

A segunda parte, que é "converter linhas em polígonos", depende mais do formato que da representação de polígono / cadeia de linhas. Quero dizer, indo de:

LINESTRING (1 1, 2 2)
LINESTRING (2 2, 2 1)
LINESTRING (2 1, 1 1)

para:
POLÍGONO ((1 1,2 2,2 1,1 1))

está convertendo linha para polígono, mas acho que não é disso que você está falando. A parte mais difícil é a primeira. Se você tiver um espaguete de linhas, como solicitá-las como cadeias de linhas fechadas.

Eu acho que a resposta para essa pergunta depende muito do conjunto de dados. Como Kirk pergunta, se as linhas podem atravessar o problema é muito maior. Se você souber que todas as "coleções de linhas" fazem parte de uma cadeia de linhas fechada, está ficando mais fácil. Em seguida, você pode pegar qualquer linha e percorrer o caminho até voltar novamente e depois passar para o passo dois acima.

O que quero dizer é que a condição do conjunto de dados define todas as regras sobre como fazê-lo. Se você deseja encontrar todos os polígonos possíveis em um espaguete de cadeias de linhas, presumo que haverá muitos algoritmos diferentes envolvidos para colocar pontos de vértice em todos os cruzamentos, pesquisar todos os caminhos possíveis e assim por diante.

No PostGIS, a função é chamada ST_Polygonize Essa função cria todos os polígonos possíveis a partir das cadeias de linhas que você atribui.

Isso é realizado pelo GEOS, para que você possa encontrar os algoritmos existentes no código GEOS e JTS.

Apenas alguns pensamentos

/ Nicklas

Nicklas Avén
fonte
1

Você pode tentar procurar o algoritmo "Forward Star". Foi-me dito que é genérico, mas as únicas discussões sobre o assunto que eu já li foram sempre em referência ao arcgis. Talvez veja as referências citadas nestas notas de aula para a estrela em frente.

Kirk Kuykendall
fonte
1
Vou comentar aqui, mesmo que esse comentário aborde algumas outras soluções propostas: o problema não pode ser representado em uma rede (ou gráfico). Requer informações sobre como as linhas são conectadas dentro de uma superfície bidimensional . Assim, as representações estelares para frente / para trás seriam de pouca utilidade; um DCEL ou algo parecido é necessário.
whuber
@ whuber - Eu estava assumindo que o comentário de Dan de que todos os "defeitos" haviam sido removidos implicava que as linhas estavam limpas. Como tal, deve ser possível reduzi-lo a um problema transversal do gráfico de encontrar todos os ciclos em um gráfico. No começo, pensei que a estrela Forward ajudaria em algoritmos que andam em torno de um gráfico, fazendo a curva mais nítida possível em cada nó. No entanto, olhando um pouco mais, parece que existem maneiras melhores. stackoverflow.com/questions/261573/… Mas, ainda assim, isso pressupõe que o problema possa ser declarado como um gráfico.
Kirk Kuykendall
1
Encontrar ciclos em um gráfico não é o mesmo que encontrar faces em um gráfico plano. Considere o gráfico abstrato com vértices {a, b, c, d} e arestas {a, b}, {a, c}, {b, c}, {b, d}, {c, d}. Uma base para os ciclos consiste em a-> b-> d-> c-> a e a-> b-> c-> a. Na incorporação plana a -> (0,1), b -> (2,2), c -> (2,0), d -> (3,1) (onde todas as arestas são segmentos de linha), o ciclo a-> b-> d-> c-> a não é uma face, mas se movermos d para (1,1), ela será uma face. Isso mostra por que o conceito de "face" requer que o gráfico seja incorporado no plano e por que as faces não podem ser calculadas apenas a partir da estrutura abstrata do gráfico.
whuber