Criando polígonos de Thiessen (Voronoi) usando linhas (em vez de pontos) como os recursos de entrada?

24

Eu tenho um conjunto de recursos de linha dentro de um determinado limite poligonal. Para cada linha, eu gostaria de gerar um polígono dentro do qual todos os pontos possíveis estejam mais próximos da linha especificada do que qualquer outra linha na camada. Eu fiz isso no passado para recursos de entrada de ponto usando a triangulação de Delaunay, mas se houver um processo semelhante para fazê-lo com recursos de linha, não consegui encontrá-lo.

ETA: A solução da Geogeek me ocorreu, mas em seções mais retas, onde as linhas de entrada têm menos vértices, os polígonos resultantes ficam muito próximos (até sobrepostos) de uma linha que não deveriam. Aqui, as linhas vermelhas são minhas entradas, você pode ver os vértices e os polígonos de Thiessen gerados a partir deles.

insira a descrição da imagem aqui

Talvez uma solução rápida e (muito) suja possa ser converter cada linha em um conjunto abundante de pontos com espaçamento uniforme (em vez dos vértices da linha), gerar polígonos de Thiessen a partir deles e dissolvê-los com base no ID da linha de origem.

Dan C
fonte
4
Os diagramas de Voronoi que incluem segmentos de linha e pontos não são compostos de "polígonos"; em vez disso, suas células têm limites que podem incluir porções de parábolas. Por esse motivo, uma das maneiras mais eficientes e precisas de criar mosaicos Voronoi é usar uma representação raster. A ESRI chama esse procedimento de Alocação Euclidiana .
whuber

Respostas:

11

Para ilustrar uma solução de processamento de imagem / raster, comecei com a imagem postada. É de qualidade muito inferior aos dados originais, devido à sobreposição de pontos azuis, linhas cinzas, regiões coloridas e texto; e o espessamento das linhas vermelhas originais. Como tal, apresenta um desafio: no entanto, ainda podemos obter células Voronoi com alta precisão.

Extraí as partes visíveis dos recursos lineares vermelhos subtraindo o verde do canal vermelho e depois dilatando e corroendo as partes mais brilhantes em três pixels. Isso foi usado como base para o cálculo da distância euclidiana:

i = Import["http://i.stack.imgur.com/y8xlS.png"];
{r, g, b} = ColorSeparate[i];
string = With[{n = 3}, Erosion[Dilation[Binarize[ImageSubtract[r, g]], n], n]];
ReliefPlot[Reverse@ImageData@DistanceTransform[ColorNegate[string]]]

Gráfico de alívio

(Todo o código mostrado aqui é Mathematica 8.)

Identificar os "sulcos" evidentes - que devem incluir todos os pontos que separam duas células Voronoi adjacentes - e combiná-los novamente com a camada de linha fornece a maior parte do que precisamos para prosseguir:

ridges = Binarize[ColorNegate[
   LaplacianGaussianFilter[DistanceTransform[ColorNegate[string]], 2] // ImageAdjust], .65];
ColorCombine[{ridges, string}]

Imagens combinadas

A faixa vermelha representa o que eu poderia salvar da linha e a faixa ciana mostra os sulcos na transformação de distância. (Ainda há muito lixo devido às quebras na própria linha original.) Esses sulcos precisam ser limpos e fechados através de uma dilatação adicional - dois pixels serão suficientes - e então podemos identificar as regiões conectadas determinadas por as linhas originais e os sulcos entre eles (alguns dos quais precisam ser recombinados explicitamente):

Dilation[MorphologicalComponents[
  ColorNegate[ImageAdd[ridges, Dilation[string, 2]]]] /. {2 -> 5, 8 -> 0, 4 -> 3} // Colorize, 2]

O que isso conseguiu, com efeito, é identificar cinco características lineares orientadas . Podemos ver três características lineares separadas que emanam de um ponto de confluência. Cada um tem dois lados. Eu considerei o lado direito dos dois recursos mais à direita como sendo os mesmos, mas diferenciei todo o resto, fornecendo os cinco recursos. As áreas coloridas mostram o diagrama Voronoi desses cinco recursos.

Resultado

Um comando de alocação euclidiana baseado em uma camada que distingue os três recursos lineares (que eu não tinha disponível para esta ilustração) não distinguiria os diferentes lados de cada recurso linear e, portanto, combinaria as regiões verde e laranja que flanqueiam a linha mais à esquerda ; dividiria o recurso de cerceta mais à direita em dois; e combinaria essas peças divididas com as características bege e magenta correspondentes em seus outros lados.

Evidentemente, essa abordagem raster tem o poder de construir mosaicos Voronoi de recursos arbitrários - pontos, peças lineares e até polígonos, independentemente de suas formas - e pode distinguir os lados dos recursos lineares.

whuber
fonte
11
Uma solução semelhante é ilustrada em mathematica.stackexchange.com/questions/20696/… .
whuber
5

Eu acho que você pode:

  • Converta vértices de linha em pontos (line_points).
  • Faça polígonos voronoi usando os pontos (line_points).
  • Dissolva os polígonos resultantes usando um atributo id que foi salvo da camada de linha ou por uma junção espacial com a camada de linha.

Espero ter realmente entendido sua pergunta, caso contrário, você pode fornecer um desenho para explicar mais suas necessidades.

geogeek
fonte
2
Acho que você entendeu, e essa solução me ocorreu, mas você se depara com problemas em que as linhas têm menos vértices. Vou atualizar minha pergunta com uma captura de tela.
Dan C
3
Isso funcionaria bem se você tornasse os pontos mais densos ao longo da linha. Embora uma abordagem baseada em varredura (como whuber menciona nos comentários), eu suspeitaria que seria muito mais eficiente do que isso.
Andy W