Convertendo regiões contornada por vetores (fronteiras) a um mapa raster (grade de pixels)

Question

Eu tenho um mapa que é cortado em várias regiões por fronteiras (contornos) como países em um mapa do mundo. Cada região tem uma certa classe de superfície de cobertura S (por exemplo 0 para a água, 0,03 para a grama ...). As fronteiras são definidas por:

• o valor de S é em ambos os lados da mesma (0,03 de um lado, 0,0 por outro lado, no exemplo abaixo)
• quantos pontos da fronteira é feita de ( n = 7 no exemplo abaixo), e
• n pares de coordenadas ( x , y ).

Este é um exemplo.

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

Eu quero fazer um mapa raster em que cada pixel tem o valor de S correspondente à região em que o centro do pixel cai.

Note que as fronteiras representam passo mudanças no S . Os vários valores de S representam as classes discretas (por exemplo, grama) ou para a água, e não são valores que podem ser calculadas (isto é, sem campo molhado!).

Observe também que nem todas as fronteiras são circuitos fechados, como no exemplo acima. Isto é um pouco como fronteiras do país: por exemplo, da fronteira EUA-Canadá não é um circuito fechado, mas sim uma linha que une-se em cada extremidade com duas outras fronteiras: Canadá-mar e o US-mar "fronteiras". (Fronteiras de circuito fechado existem no entanto!)

Pode alguém me aponte para um algoritmo que pode fazer isso? Eu não quero reinventar a roda!

Answer 1

A maneira que eu tenho resolvido este é o seguinte:

1. Março ao longo de cada segmento; parada em intervalos regulares L .
2. Em cada parada, colocar um ponto tracer imediatamente à esquerda e à direita do segmento (a uma certa distância pequena d do segmento). Os pontos de traçador são atribuídas a S-valor esquerda e direita, respectivamente.
3. Faça uma interpolação por vizinho mais próximo. Cada ponto na grade raster é atribuído a S do palpador mais próximo.

Isso funciona mesmo quando existem linhas não fechadas, por exemplo na borda do mapa.

Este não é um algoritmo de análise "perfeita". Existem dois parâmetros: L e d . O algoritmo funciona bem, desde que d << L . Caso contrário, você pode obter imprecisões (geralmente single-pixel) perto de junções de segmentos, especialmente aqueles com ângulos agudos.

Answer 2

O caso geral para processar este tipo de geometria em forma de vector pode ser bastante difícil, especialmente porque nada sobre a estrutura que você descreve requer a geometria a ser consistente. No entanto, desde que você só quer rasterize-lo, em seguida, tratar o problema como um diagrama de Voronoi de segmentos de linha podem ser mais robusto.

Aproximando o diagrama de Voronoi pode ser feito graficamente em OpenGL extraindo cada segmento de linha como um par de quadriláteros fazendo uma forma de tenda. O z-buffer é usado para fazer o mais próximo quad têm precedência, e assim colorir o pixel baseada em qualquer linha é mais próximo. A diferença aqui é que você vai querer colorir os polígonos com base em qual lado da linha em que estão, em vez de qual linha que representam. Um bom papel discute um algoritmo semelhante é rápido Computação da Hoff et al de generalizadas Voronoi Diagrams Usando Gráficos Hardware

A geometria 3D será algo parecido com este esboço com 3 segmentos vermelhos / amarelos e 1 azul / verde segmento:

Este procedimento não exige que você para converter qualquer coisa em um circuito fechado, e não requer nenhuma biblioteca de geometria fantasia. Tudo é tratado pelo z-buffer, e deve ser rápido o suficiente para ser executado em tempo real, em qualquer placa gráfica moderna. Um refinamento seria a utilização de coordenadas homogêneas para fazer as bases do projeto até o infinito.

Eu implementei este algoritmo em um script Python em http://www.pasteall.org/9062/ python. Uma advertência interessante é que a utilização de cones para tampar as extremidades das linhas não funcionou sem distorcer a forma de cone, porque os cones que representam os pontos de extremidade dos segmentos eram z-luta. Para a geometria da amostra que você forneceu, os olhares de saída como esta:

Answer 3

Eu recomendo que você use uma biblioteca de algoritmo de geometria como CGAL . Especialmente o segundo exemplo nos polígonos "2D" página do manual de referência deve fornecer-lhe o que você precisa. Você pode definir cada "fronteira" como um polígono e verificar se determinados pontos estão dentro dos polígonos. Então, basicamente, seria algo como

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

Eu não tenho tanta certeza sobre o que fazer com o outside_color porque as regiões fora se sobrepõem, não é? De qualquer forma, olhando para o seu exemplo, cada região fora poderia ser água, assim você só poderia fazer uma final

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

(ou como uma alternativa, conjunto de pixels [X] [Y] para water_value antes a iteração através da lista polígono)

Answer 4

• em primeiro lugar, converter todos os seus limites em circuitos fechados (possivelmente incluindo as bordas do seu mapa), e identificar a cor interna. isso tem que ser possível, caso contrário, você tem uma inconsistência em seus dados
• algoritmo uso de Bresenham para desenhar todas as linhas de fronteira em seu mapa, em uma única cor não utilizado
  • armazenar uma lista de todos os "pixels de fronteira" como você faz isso
• , em seguida, para cada fronteira
  • triangular-lo (delaunay)
  • percorrer os triângulos até encontrar aquele cujo centro está dentro de sua fronteira (teste de ponto no polígono)
  • FloodFill seu mapa naquele ponto da cor do interior da fronteira
• Depois de ter preenchido em todas as regiões do interior, percorrer a lista de pixels de fronteira, vendo a cor que cada um deve ser

Answer 5

• escolha duas cores não utilizadas como marcadores de "vazio" e "fronteira"
• preencha toda a área com o "vazio" cor
• desenhar todas as fronteiras da região de "fronteira" cor
• iterate através de pontos de encontrar primeiro com "esvaziar" cor
• determinar qual região a que pertence (google "ponto dentro polígono", provavelmente você vai precisar para fazer suas fronteiras fechadas como Martin DeMello sugerido)
• executar algoritmo de inundação-fill a partir deste ponto com a cor da região
• ir para a próxima "esvaziar" ponto (sem necessidade de pesquisa restart - apenas continuar)
• e assim por diante até que há pontos "vazios" permanecerá