Desenho de um mapa topográfico

StackOverflow https://stackoverflow.com/questions/263305

Pergunta

Eu tenho trabalhado em um projeto de visualização de dados contínuos 2-dimensionais. É o tipo de coisa que você poderia usar para estudar dados de elevação ou padrões de temperatura em um mapa 2D. Na sua essência, é realmente uma maneira de achatamento de 3 dimensões em duas dimensões-plus-color. Na minha área específica de estudo, eu não estou realmente trabalhando com dados de elevação geográficas, mas é uma boa metáfora, então eu vou ficar com ela ao longo deste post.

De qualquer forma, neste momento, tenho um renderizador de "cor contínua" que eu estou muito satisfeito com:

Renderer contínua a cores

O gradiente é a cor-de rodas padrão, onde pixels vermelhos indicar coordenadas com valores elevados, e violeta pixels indicam valores baixos.

A estrutura de dados subjacente usa alguns muito inteligente (se eu me dizê-lo) algoritmos de interpolação para permitir zoom em detalhes sobre o mapa arbitrariamente profunda.

Neste ponto, eu quero tirar algumas linhas de contorno topográficas (usando curvas de Bezier quadrática), mas eu não tenho sido capaz de encontrar qualquer boa literatura descrevendo algoritmos eficientes para encontrar essas curvas.

Para se ter uma ideia para o que eu estou pensando, aqui é a implementação de um pobre homem (onde o processador usa apenas um valor RGB preto sempre que encontra um pixel que cruza uma linha de contorno):

Cor contínua com Ghetto Topo Lines

Há vários problemas com esta abordagem, no entanto:

  • Áreas do gráfico com um resultado mais acentuada inclinação em mais fina (e frequentemente quebradas) topo linhas. Idealmente, todas as linhas de topo deve ser contínuo.

  • Áreas do gráfico com um resultado mais plana inclinação em linhas mais largas TOPO (e muitas vezes regiões inteiras de escuridão, especialmente no perímetro exterior da região de extracção de gordura).

Então, eu estou olhando para uma abordagem de desenho vetorial para obter os agradável, perfeito curvas 1 pixel de espessura. A estrutura básica do algoritmo terá de incluir estas etapas:

  1. Em cada elevação discreta onde quer desenhar uma linha de topo, encontrar um conjunto de coordenadas em que a elevação em que coordenada é extremamente estreita (dado um valor epsilon arbitrária) para a elevação desejada.

  2. Elimine pontos redundantes. Por exemplo, se três pontos estão em uma linha perfeitamente-linear, então o ponto de centro é redundante, uma vez que pode ser eliminado, sem alterar a forma da curva. Da mesma forma, com curvas de Bezier, ele muitas vezes é possível eliminar pontos de ancoragem cetain ajustando a posição dos pontos de controlo adjacentes.

  3. Montar os pontos restantes numa sequência, de tal modo que cada um dos segmentos entre dois pontos aproxima-se uma trajectória de elevação neutro, e tal que nenhum dois segmentos de linha sempre se cruzam. Cada ponto-sequência deve criar um polígono fechado, ou deve cruzar a caixa delimitadora da região de processamento.

  4. Para cada vértice, encontrar um par de pontos de controlo de tal forma que a curva resultante exibe um erro mínimo, no que diz respeito aos pontos redundantes eliminados no passo # 2.

  5. Certifique-se de que todas as características da topografia visíveis na escala de renderização atual são representados por linhas topográficas apropriadas. Por exemplo, se os dados contém um pico com altitude elevada, mas com um diâmetro extremamente pequeno, as linhas de topo ainda deve ser desenhada. características verticais só deve ser ignorada se o seu diâmetro recurso é menor do que a granularidade geral de renderização da imagem.

Mas mesmo sob essas restrições, ainda posso pensar em várias heurísticas diferentes para encontrar as linhas:

  • Encontre o ponto alto-dentro da caixa envolvente a prestação. A partir desse ponto alto, viajar para baixo ao longo de vários percursos diferentes. Toda vez que a linha transversal crossest um limite de elevação, acrescentar que apontam para uma b específicas de elevaçãoucket. Quando o caminho de passagem atinge um mínimo local, mudança de curso e as viagens para cima.

  • Realizar um percurso de alta resolução ao longo da caixa delimitadora retangular da região de renderização. Em cada limiar de elevação (e em pontos de inflexão, onde a direção reveses inclinação), adicionar esses pontos a um balde específicas de elevação. Depois de terminar a travessia de fronteira, iniciar o rastreamento para dentro dos pontos de fronteira nesses baldes.

  • Verificar a região de renderização inteira, tomando uma medida de elevação em um intervalo regular escassa. Para cada medição, usá-lo da proximidade com um limite de elevação como um mecanismo para decidir se quer ou não tomar uma medida interpolada de seus vizinhos. Usando esta técnica daria melhores garantias de cobertura em toda a região de renderização todo, mas seria difícil de montar os pontos resultantes em uma ordem sensata para a construção de caminhos.

Então, esses são alguns dos meus pensamentos ...

Antes de mergulhar profundamente em uma implementação, eu queria ver se alguém mais em StackOverflow tem experiência com este tipo de problema e poderia fornecer indicações para uma implementação rigorosa e eficiente.

Editar:

Estou especialmente interessado na sugestão "Gradient" feita por ellisbben. E a minha estrutura de dados núcleo (ignorando alguns dos atalhos de interpolação otimizando) pode ser representado como a soma de um conjunto de funções gaussianas 2D, que é totalmente diferenciável.

Acho que vou precisar de uma estrutura de dados para representar uma inclinação tridimensional, e uma função de cálculo que vector inclinação por pelo ponto arbitrário. Em cima da minha cabeça, eu não sei como fazer isso (embora parece que ele deve ser fácil), mas se você tem um link explicando a matemática, eu estaria muito obrigado!

UPDATE:

Graças às excelentes contribuições de ellisbben e Azim, agora eu posso calcular o ângulo de contorno para qualquer ponto arbitrário no campo. Desenhar as linhas topográficas reais seguirá em breve!

renderizações Aqui estão atualizados, com e sem o topo-processador baseado em raster gueto que eu tenho usado. Cada imagem inclui mil pontos de amostragem aleatória, representados por pontos vermelhos. O ângulo de contorno em que ponto é representado por uma linha branca. Em certos casos, nenhuma inclinação pode ser medida no ponto determinado (com base na granularidade de interpolação), de modo que o ponto vermelho ocorre sem uma linha de ângulo de contorno correspondente.

Aproveite!

(NOTA: Estas representações usar uma topografia de superfície diferente do que as representações anteriores - desde que eu gerar aleatoriamente as estruturas de dados em cada iteração, enquanto eu estou prototipagem - mas o método de renderização do núcleo é o mesmo, assim tenho certeza que você começa a idéia.)

text alt

text alt

Aqui está um fato interessante: mais na mão do lado direito dessas representações, você vai ver um monte de linhas de contorno estranho em ângulos horizontais e verticais perfeitas. Estes são artefactos do processo de interpolação, que utiliza uma grade de interpoladores para reduzir o número de computações (por cerca de 500%) necessário para realizar as operações de processamento do núcleo. Todas essas linhas de contorno estranhas ocorrem na fronteira entre células da grade de duas interpolador.

Felizmente, esses artefatos não realmente importa. Embora os artefatos são detectáveis ??durante o cálculo da inclinação, o renderizador final não vai notá-los, uma vez que opera a uma profundidade de bits diferente.

Update novamente:

Aaaaaaaand, como uma indulgência final antes de eu ir dormir, aqui está um outro par de representações, uma no old-school "cor contínua" estilo, e um com 20.000 amostras de gradiente. Neste conjunto de representações, eu eliminado o ponto vermelho para o ponto-amostras, uma vez que desnecessariamente tumultua a imagem.

Elere, você pode realmente ver esses artefatos de interpolação que me referi anteriormente, graças à rede-estrutura da coleção interpolador. Devo enfatizar que esses artefatos será completamente invisível na renderização contorno final (uma vez que a diferença de magnitude entre quaisquer duas células interpolador adjacentes é menor do que a profundidade da imagem renderizada bit).

Bom apetite !!

text alt

text alt

Foi útil?

Solução

O gradiente é um operador matemático que podem ajudá-lo.

Se você pode transformar sua interpolação em uma função diferenciável, o gradiente da altura será sempre apontar na direção de mais íngreme subida. Todas as curvas de igual altura são perpendiculares ao gradiente de altura avaliada nesse ponto.

A sua ideia sobre como iniciar a partir do ponto mais alto é sensata, mas pode perder recursos se houver mais do que um máximo local.

Eu sugiro

  1. escolher valores de altura em que você vai desenhar linhas
  2. criar um monte de pontos em uma multa, regularmente grade espaçados, em seguida, caminhar cada ponto em pequenos passos na direção do gradiente para a altura mais próxima em que você deseja desenhar uma linha
  3. criar curvas pisando cada ponto perpendicular ao gradiente; eliminar os pontos em excesso, matando um ponto em outra curva vem muito perto de ele--, mas para evitar a destruição do centro de ampulheta como figuras, pode ser necessário para verificar o ângulo entre a perpendicular vector orientada para o gradiente para ambos os pontos. (Quando eu digo orientado, I make média se de que o ângulo entre o gradiente eo valor perpendicular a calcular é sempre 90 graus na mesma direção.)

Outras dicas

Como alternativa, há a href="http://en.wikipedia.org/wiki/Marching_squares" rel="nofollow noreferrer"> algoritmo de marcha quadrados

As curvas de topo que você quer desenhar são isosuperfícies de um campo escalar mais de 2 dimensões. Para isosuperfícies em 3 dimensões, há a marchando cubos algoritmo.

Em resposta ao seu comentário a @erickson e para responder à questão sobre o cálculo do gradiente de sua função. Em vez de calcular os derivados da sua função 300 prazo, você poderia fazer uma diferenciação numérica como segue.

Dado um ponto [x, y] na sua imagem você pode calcular o gradiente (direção de mais íngreme decente) 

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy)

onde dx e dy poderia ser o espaçamento em sua grade. A linha de contorno irá ser perpendicular ao gradiente. Assim, para obter a direcção do contorno, C, podemos multiplicar g = [V, W] pela matriz, A = [0 -1, 1 0] dando 

c = [-w,v]

Eu queria algo como isso mesmo, mas não encontrou uma solução baseada em vetor.

Uma solução baseada em raster não é tão ruim, porém, especialmente se os seus dados estão baseados em raster. Se os seus dados é muito baseado em vetor (em outras palavras, você tem um modelo 3D de sua superfície), você deve ser capaz de fazer alguma matemática real para encontrar as curvas de interseção com planos horizontais em altitudes diferentes.

Para uma abordagem baseada em raster, eu olho para cada par de pixels vizinhos. Se alguém está acima de um nível de contorno, e um está abaixo, obviamente, uma linha de contorno corre entre eles. O truque que eu usei para anti-alias linha de contorno é misturar a cor da linha de contorno em ambos pixels, proporcional à sua proximidade com a linha de contorno idealizada.

Talvez alguns exemplos ajudarão. Suponha-se que o elemento de imagem corrente é a uma "elevação" de 12 pés, um vizinho é a uma altitude de 8 pés, e as linhas de contorno estão cada 10 pés Então, existe um meio caminho entre a linha de contorno.; pintar o pixel atual com a cor da linha de contorno a 50% de opacidade. Outra pixel é a 11 pés e tem um vizinho em 6 pés. Colorir o pixel atual em 80% de opacidade. 

alpha = (contour - neighbor) / (current - neighbor)

Infelizmente, eu não tenho o código à mão, e não poderia ter sido um pouco mais do que isso (Lembro-me vagamente olhando vizinhos diagonais também, e ajustando pelo sqrt(2) / 2). Eu espero que este o suficiente para dar-lhe a essência.

Ocorreu-me que o que você está tentando fazer seria muito fácil de fazer em MATLAB, utilizando a função de contorno. Fazer as coisas como fazer aproximações de baixa densidade a seus contornos provavelmente pode ser feito com alguns bastante simples de pós-processamento dos contornos.

Felizmente, GNU Octave, um clone MATLAB, tem implementações das várias funções de contorno de plotagem. Você poderia olhar para esse código para um algoritmo e implementação que é quase certamente matematicamente som. Ou, você pode apenas ser capaz de descarregar o processamento de Octave. Consulte a página sobre interface com outras linguagens para ver se isso seria mais fácil.

Divulgação: Eu não usei Octave muito, e eu realmente não tenho testado de contorno plotagem. No entanto, a partir de minha experiência com MATLAB, posso dizer que ele vai dar-lhe quase tudo o que você está pedindo em apenas algumas linhas de código, desde que você obter seus dados em MATLAB.

Além disso, parabéns por fazer um enredo Slopefield muito VanGough-esque.

Eu sempre verificar lugares como http://mathworld.wolfram.com antes de ir profundamente em meu próprio :)

Talvez href="http://mathworld.wolfram.com/topics/Curves.html" rel="nofollow sua seção ajudaria? Ou talvez a entrada em mapeia .

comparar o que você tem prestado com um mundo real topo mapa - eles parecem idênticos para mim! Eu não mudaria uma coisa ...

escrever os dados como um HGT arquivo (muito simples formato de dados de elevação digital usada por USGS) e usar o código-fonte aberto livre e gdal_contour ferramenta para criar contornos. Isso funciona muito bem para mapas terrestres, a restrição sendo que os pontos de dados são assinados números de 16 bits, o que se encaixa na faixa de terreno de altura em metros muito bem, mas pode não ser suficiente para os seus dados, que não assumem a ser um o mapa de terreno real -. embora você fazer menção terreno mapas

Não afiliado a StackOverflow
scroll top