Esta página apresenta uma síntese sobre a geração de grades retangulares e triangulares e seus respectivos interpoladores, a partir de amostras (pontos e isolinhas) e outras grades que são utilizadas pelo SPRING.
As grades retangulares são geralmente utilizadas em aplicações qualitativas, ou seja, para vizualização da superfície. Enquanto o modelo de grade irregular é utilizado quando se requer maior precisão na análise quantitativa dos dados.
Os interpoladores de grade retangular e triangular, utilizados no SPRING para a
geração de modelos numéricos de terreno, foram especificados de acordo com os tipos de
dados de entrada, ou seja, amostras (pontos e isolinhas), grade retangular ou triangular.
Consulte também:
Como gerar grade Retangular
Como gerar Grade Triangular
Produtos de MNT no SPRING - Quais são e como executar ?
Processos de Modelagem
A grade retangular ou regular é um modelo digital que aproxima superfícies através de um poliédro de faces retangulares (Figura abaixo). Os vértices desses poliedros podem ser os próprios pontos amostrados, caso estes tenham sido adquiridos nas mesmas localizações xy que definem a grade desejada.
Modelo de superfície gerada por uma grade retangular.
A geração de grade regular ou retangular
deve ser efetuada quando os dados amostrados na superfície não são obtidos com
espaçamento regular. Assim, a partir das informações contidas nas isolinhas ou nos
pontos amostrados, gera-se uma grade que representa de maneira mais fiel possível a
superfície. Os valores iniciais a serem determinados são os espaçamentos nas direções
x e y de forma que possam representar os valores próximos aos pontos da grade em regiões
com grande variação. Ao mesmo tempo, devem reduzir redundâncias em regiões quase
planas.
O espaçamento da grade, ou seja, a resolução em x ou y, deve ser idealmente menor ou igual a menor distância entre duas amostras com cotas diferentes. Ao se gerar uma grade muito fina (densa), com distância entre os pontos muito pequena, existirá um maior número de informações sobre a superfície analisada, porém necessitará maior tempo para sua geração. Ao contrário, considerando distâncias grandes entre os pontos, será criada uma grade grossa, que poderá acarretar perda de informação. Desta forma para a resolução final da grade, deve haver um compromisso entre a precisão dos dados e do tempo de geração da grade.
Uma vez definida a resolução e consequentemente as coordenadas de cada ponto da grade, pode-se aplicar um dos métodos de interpolação para calcular o valor aproximado da elevação.
No SPRING a grade regular pode ser gerada a partir de amostras, ou seja pontos e linhas, grade regular ou irregular. No caso de pontos e linhas podem ser utilizados os seguintes interpoladores: vizinho mais próximo, média simples, média ponderada, média ponderada por quadrante e média ponderada por cota e por quadrante. Para a geração de uma nova grade regular, a partir de outra grade retangular podem ser utilizados os interpoladores linear e bicúbico. Para a geração de grade retangular a partir de um TIN (“Triangular Irregular Network”) encontra-se disponível o interpolador linear.
Grades
Para a geração de grade regular ou retangular a partir de amostra (pontos e isolinhas), os métodos de interpolação mais utilizados são descritos e representados a seguir:
O valor de cota (+) equivale ao valor amostrado mais próximo (*).
onde:
n
= número de vizinhos
O valor da cota (+) obtido a partir dos 4 vizinhos amostrados mais próximos (*).
d = ((x - x0)2 + (y - y0)2)1/2 d = distância euclidiana do ponto interpolante ao vizinho i
w(x,y) = (1/d)u=1 u = 1 = expoente da função de ponderação
onde:
w(x,y) = função de ponderação
f(x,y) - função de interpolação
Este interpolador produz resultados intermediários entre o interpolador de média simples e os outros interpoladores mais sofisticados, com tempo de processamento menor.
O valor de cota por quadrante com peso é proporcional ao inverso da distância dos
valores amostrados.
O valor da cota é obtido pela média ponderada de cotas das isolinhas por quadrante.
Grades
A geração de uma nova grade retangular a partir de uma grade retangular anteriormente elaborada, ou seja, o refinamento da grade, consiste em diminuir o espaçamento entre pontos da grade, adensando-a. Estes pontos internos ao retalho, apresentam valor de cota z da nova grade estimados através dos interpoladores bicúbico e bilinear.
Para realizar um refinamento bicúbico, segundo a relação de vizinhança, o número de vizinhos a serem considerados será igual a 16 (Veja figura a seguir).
Interpolador bicúbico.
O refinamento bicúbico, apesar de ser mais lento computacionalmente que o bilinear, fornece resultados mais interessantes, pois garante continuidade de primeira e segunda ordem entre as funções que representam cada célula do modelo. Desta forma, a superfície resultante é suave nos pontos da grade e também ao longo dos segmentos que formam os retângulos, ou seja, a grade é mais suave e cada retalho da grade é contínuo e suave em relação aos seus vizinhos.
Para se calcular a superfície bilinear para uma célula da grade, aproveita-se as características de ordenação das posições dos elementos das células e otimiza-se o procedimento que implementa este interpolador.
Considera-se uma célula da grade formada pelos pontos vértices A, B, C e D, e um ponto
genérico situado no interior da célula. M=f(u,v), (u,v) em (0,1), A interpolação
bilinear sobre a célula ABCD é realizada pela seguinte sequência: inicialmente
interpola-se linearmente os pontos E e F, a partir dos pontos C e D, e A e B,
respectivamente; por último
interpola-se o ponto M, linearmente, a partir dos pontos E e F (Veja Figura abaixo).
Assim, o valor de cota Z, calculada no ponto M é:
Interpolador bilinear.
Este método é muito rápido computacionalmente em relação ao interpolador bicúbico. Sua maior desvantagem é a produção de superfícies pouco suavizadas. Portanto, deve ser usado quando uma aparência suave da superfície não for necessária..
Grades
A conversão da grade triangular para a grade retangular pode ser necessária quando se deseja uma forma matricial para o modelo numérico de terreno. Deste modo, as informações do terreno que foram modeladas por um interpolador de grade triangular podem ser analisadas por outras informações do tipo matricial. O processo de conversão pode utilizar os seguintes interpoladores: Linear, Quíntico com linhas de quebra e Quíntico sem linhas de quebra, os quais são descritos a seguir.
Na interpolação linear, um plano é ajustado para cada retalho triangular da grade, para determinar os valores de z em cada posição xy dentro do triângulo. A equação de uma superfície plana pode ser expressa por Ax +By +Cz +D=0.
Nesta abordagem linear as superfícies de retalhos diferentes encontram-se no lado comum destes triângulos. Isto significa que as bordas não têm continuidades suaves.
O interpolador quíntico sem linhas de quebras ajusta uma superfície ao retalho da grade, utilizando um polinômio do quinto grau. A utilização deste interpolador permite gerar uma superfície mais suave quando comparada com outra grade gerada pelo interpolador linear.
Linhas de quebra são linhas que definem descontinuidades na superfície para os dois diferentes lados da linha, como linhas de vale ou de crista. Um rio, por exemplo, pode ser editado como uma linha de quebra em que ao longo de suas margens há uma descontinuidade de relevo, sem nenhum valor de cota a ele associado.
Estas linhas de quebra podem ser, ou não, consideradas na geração de uma grade triangular. O interpolador quíntico sem linhas de quebra obviamente não considera estas linhas de quebra (Veja exemplo na figura abaixo).
Interpolador quíntico sem linha de quebra.
Este interpolador é recomendado quando deseja-se uma superfície suave e não há linhas de vale ou crista muito realçadas (linhas de quebra) no modelo numérico do terreno.
Este interpolador difere do anterior apenas no que se refere às linhas de quebra. Utiliza a mesma superfície de quinto grau para ajustar os retalhos da grade, porém o algoritmo reconhece a linha de quebra e a superfície al longo dela não será suavizada (Veja exemplo na figura abaixo).
Grade gerada por interpolador quíntico com linhas de quebra.
Este interpolador é recomendado para situações onde as linhas de quebra são editadas para salientar feições lineares de relevo e drenagem e deseja-se uma superfície suave.
Grades
Na modelagem da superfície por meio de grade irregular triangular, cada polígono que forma uma face do poliedro é um triângulo (Figura abaixo). Os vértices do triângulo são geralmente os pontos amostrados da superfície. Esta modelagem, considerando as arestas dos triângulos, permite que as informações morfológicas importantes, como as descontinuidades representadas por feições lineares de relevo (cristas) e drenagem (vales), sejam consideradas durante a geração da grade triangular, possibilitando assim, modelar a superfície do terreno preservando as feições geomórficas da superfície.
Modelo de superfície gerada por grade triangular.
O número de redundâncias é bastante reduzido se comparado à grade retangular, uma vez
que a malha é mais fina em regiões de grandes variações e mais espaçada em regiões
quase planas. As descontinuidades da superfície podem ser modeladas através de linhas e
pontos característicos.
Esta grade tem a vantagem de utilizar os próprios pontos amostrados para modelar a superfície, sem a necessidade de qualquer tipo de interpolação sobre os mesmos. A desvantagem da grade irregular é que os procedimentos para obtenção de dados derivados de grades triangulares tendem a ser mais complexos e consequentemente mais demorados que os da grade retangular.
A entrada de isolinhas na modelagem numérica, seja pela sensibilidade da mesa digitalizadora, ou pela resolução do scanner e o algoritmo de conversão, produz muitas vezes um número excessivo de pontos para representar a isolinha. O espaçamento ideal entre pontos de uma mesma isolinha deve ser a distância média entre a isolinha e as isolinhas vizinhas. Este espaçamento ideal permite gerar triângulos mais equiláteros, que permitem modelar o terreno de maneira mais eficiente.
Outra fonte de pontos redundantes ocorre quando uma linha não é digitalizada continuamente, desde de seu início até seu final. Nestes casos, o primeiro ponto de uma linha pode ser o último da linha anterior, ou estar tão próximo a ela que pode ser interpretado como se estivesse posicionado na mesma localização geográfica. O último problema pode ser resolvido com a comparação entre os valores iniciais e finais das isolinhas. Um dos pontos, assim duplicados, pode ser removido do conjunto de amostras.
Os pontos em excesso, ao longo de uma linha, são eliminados utilizando um procedimento de simplificação, baseado no algoritmo de Douglas-Peucker. O procedimento de Douglas-Peucker elimina pontos, analisando a distância de cada ponto à uma reta que une o primeiro e o último ponto da linha. Se todos os pontos estão à uma distância menor que uma dada tolerância, a linha será representada apenas pelos primeiro e último ponto. Se algum ponto está à uma distância maior, o ponto mais distante da reta é considerado o último e o algoritmo reinicia calculando as distâncias.
Procedimento especial é tomado quando a linha representa uma ilha, isto é, quando o primeiro ponto é igual ao último. Neste caso, o penúltimo ponto é utilizado. Uma vez que as linhas tratadas representam isolinhas e seus pontos são utilizados como amostras de elevação na geração de grade triangular, deve-se manter uma distância máxima entre pontos ao longo das linhas. Idealmente, esta distância deve ser a média entre a distância entre a linha analisada e as linhas paralelas mais próximas.
O valor de tolerância é calculado considerando a escala original dos dados. Sabe-se que a precisão dos dados disponíveis em mapas é em torno de 0.2 mm. O valor de 0.4 mm de tolerância para eliminação de pontos foi utilizado em testes que mostraram que este valor permite gerar grades triangulares bem comportadas (procura-se triângulos o mais equiláteros possível). A distância máxima entre pontos da isolinha é definida a partir da tolerância do algoritmo de Douglas-Peucker e testes indicaram que o valor dado por 20 vezes a tolerância pode ser utilizado. Estes valores são apresentados como 'default', na janela de geração da grade triangular.
As linhas de drenagem podem ser utilizadas como fontes de informações adicionais e podem melhorar a qualidade do modelo de terreno. Estas linhas são representadas por meio de um conjunto de pontos e, da mesma forma que as isolinhas, devem ser processadas de modo a ter apenas os pontos necessários para uma boa representação. O mesmo procedimento baseado no algoritmo de Douglas-Peucker é utilizado, mas com a diferença de não ser necessário manter uma distância máxima entre pontos.
O acesso à triangulação a ser gerada deve ser o mais eficiente possível, devido ao grande volume de dados que é armazenado. Uma triangulação típica para modelagem de elevação tem entre 10000 a 100000 triângulos, que devem ser continuamente modificados durante a fase de criação, e acessados regularmente quando necessita-se extrair dados derivados do modelo. As estruturas escolhidas são baseadas em vetores, sendo uma para armazenar os vértices, outra para as arestas e a última para os triângulos.
Cada vértice contém os valores de x, y e de elevação z correspondentes à uma amostra da superfície. Estes valores são armazenados na classe TinNode, sendo que x e y formam o ponto (TNpoint).
Além destes dados, a informação de procedência da amostra é armazenada. Os vértices são classificados e obtidos a partir dos pontos das isolinhas, de pontos das linhas de quebra (linhas de drenagem), de amostras isoladas e pontos eliminados no processo.
Os vértices de linhas de quebra podem ser classificados também em função da forma de obtenção do valor de elevação. Como linhas de quebra não têm valores de elevação associados, algum método de estimativa deve ser utilizado. Quando a linha de quebra intersepta uma isolinha, o valor é estimado como sendo o da isolinha e é classificado como sendo de um tipo diferente de outro vértice com elevação calculada por outro método. Cada unidade básica de armazenamento constitui uma posição em um vetor de tamanho igual ao número de vértices, sendo acessível diretamente pelo índice da linha do vetor.
O tamanho inicial do vetor é igual ao número de amostras (pontos cotados mais o número de pontos sobre isolinhas depois da simplificação) acrescido de 4. Estes 4 elementos adicionais correspondem aos pontos extremos do retângulo envolvente das amostras, necessário durante o processo de geração da triangulação.
As arestas da triangulação contêm as informações relativas aos vértices aos quais estão conectados e aos triângulos que compartilham esta aresta.
A unidade utilizada para armazenar a aresta é orientada, sendo os dois vértices classificados com DE e PARA, e os triângulos como sendo da DIREITA e da ESQUERDA.
Cada unidade básica de armazenamento constitui uma posição em um vetor de tamanho igual ao número de arestas, sendo acessível diretamente pelo índice da linha do vetor.
O tamanho inicial do vetor é igual ao número de amostras (pontos cotados mais o número de pontos sobre isolinhas depois da simplificação) multiplicado por 3.
Os triângulos contêm a informação de quais são as três arestas que o compõem. Para acessar as coordenadas dos vértices do triângulo, é necessário consultar o índice das arestas e o índice dos vértices das arestas, obtendo então as coordenadas desejadas.
As arestas dos triângulos são numeradas de 0 a 2, obedecendo a ordem com que são armazenados em cada unidade básica. O tamanho inicial do vetor é igual ao número de amostras (pontos cotados mais o número de pontos sobre isolinhas depois da simplificação) multiplicado por 2.
Criação da Triangulação de Delaunay
Os pontos amostrados são utilizados para criar a grade irregular. O método utilizado é o incremental, onde os pontos são inseridos um a um na triangulação, modificando a triangulação existente, executando testes de Delaunay nos triângulos gerados e modificados com seus vizinhos. Na última fase do processo, todos os triângulos são testados e modificados, se necessário, para respeitar as restrições de Delaunay.
Para iniciar o procedimento de inserção de pontos na triangulação é necessário que haja um conjunto de triângulos iniciais. Estes triângulos são baseados no retângulo que envolve todos os dados amostrais a serem utilizados (veja figura ao lado). Os quatro pontos que definem os dois triângulos iniciais são obtidos nos vértices do retângulo envolvente, acrescido de uma distância em cada um destes vértices. O valor utilizado é o de tolerância calculado em função da escala, e é de 0.4 mm vezes a escala.
Os vértices dos triângulos iniciais são diferentes dos outros vértices que correspondem as amostras. Para permitir sua identificação, o valor de elevação a eles atribuído é correspondente ao maior valor possível de ser representado (MAXFLOAT) em notação de ponto flutuante de 4 bytes. O valor utilizado é de 3.4E37. Este valor é padronizado e todos os procedimentos devem conhecer este valor para que possam distinguir um vértice inválido de outros normais.
A inserção de amostras é feita sobre os triângulos existentes. Cada amostra a ser inserida está contida em apenas um dos triângulos da triangulação. Uma vez que os dois triângulos iniciais são criados, contendo todo o espaço de amostras, toda amostra deve pertencer a um dos triângulos existentes. As amostras são inseridas uma a uma, sendo que são inseridas inicialmente as amostras pontuais e depois as obtidas de isolinhas. Pontos de isolinhas que coincidem com outros pontos já inseridos não são utilizados. Este caso ocorre no início ou no final de uma isolinha, quando esta é representada por mais de uma linha. Cada amostra é inserida por um processo que consta da definição de qual triângulo o contém, da modificação deste triângulo e de seus vizinhos, teste do critério de Delaunay e da modificação dos novos triângulos e seus vizinhos, caso seja necessário para atender a restrição imposta pelo critério de Delaunay.
Uma vez inseridas todas as amostras, uma triangulação está disponível. No entanto, esta triangulação pode não ter todos os triângulos respeitando o critério de Delaunay. Para garantir que a triangulação seja Delaunay, todos os triângulos são testados em relação a seus vizinhos. Os triângulos são testados na mesma seqüência em que foram criados.
O teste em um triângulo é efetuado com seus 3 vizinhos. Caso o triângulo testado T e seu vizinho TV sejam alterados para obedecer o critério, é verificado se o triângulo vizinho já havia sido testado, ou seja, se TV está antes de T na seqüência. Quando o triângulo vizinho TV está antes de T, TV deve ser testado em relação a seus vizinhos. Se o triângulo TV esta depois de T na seqüência, os novos vizinhos de T são testados em relação a T e o teste continua a partir de T. Em cada um destes testes, quando algum triângulo é alterado e está antes de T na seqüência, este triângulo é novamente testado.
Sobre a triangulação Delaunay criada, alterações podem ser executadas para que ela obedeça a critérios adicionais. Entre as alterações implementadas estão a criação de triangulação com envoltório convexa, triangulação onde as arestas não interseptam isolinhas, triangulação onde triângulos vizinhos têm a menor diferença de ângulo entre as normais.
Na geração da triangulação, as isolinhas são utilizadas como sendo um conjunto de amostras, onde cada ponto que forma uma linha é uma amostra isolada. No entanto, a isolinha representa toda a região do espaço x,y entre dois pontos consecutivos de uma isolinha que tem o valor de elevação constante e igual ao valor da isolinha. A triangulação deve considerar este fato na geração, mantendo uma aresta sobre a isolinha que conecta dois pontos amostrados sobre ela.
Para obter a triangulação onde arestas não interseptam isolinhas, a triangulação Delaunay deve ser modificada. As isolinhas são analisadas uma a uma, para cada segmento que une as amostras extraídas da isolinha. Se o número de arestas interseptadas para cada segmento é 1 ou 2, a alteração da aresta para conectar os vértices dos triângulos que compartilham esta aresta e que são diferentes dos atuais vértices da aresta pode ser suficiente.
Se o número de arestas interseptadas é maior que 2, os pontos de interseção são inseridos na triangulação.
A geração de triangulação leva em conta apenas as coordenadas em X e Y. A triangulação obtida deste modo pode conter distorções devido ao valor de elevação, ou seja, em análises onde a elevação é utilizada, os resultados podem ser mais corretos se a triangulação considerar também a coordenada Z.
Uma das maneiras de inserir a informação de elevação é modificar a triangulação utilizando como critério de restrição o menor ângulo possível entre normais as superfícies dos triângulos. A modificação da triangulação é feita em processo semelhante ao da modificação para obedecer ao critério de Delaunay, ou seja, todos os triângulos são testados em relação a seus vizinhos na mesma seqüência em que foram criados e o teste em dado triângulo é efetuado com seus 3 vizinhos. Caso o triângulo testado T e seu vizinho TV sejam alterados no teste, é verificado se o triângulo vizinho já havia sido testado, ou seja, se TV está antes de T na seqüência. Quando o triângulo vizinho TV está antes de T, todos os triângulos vizinhos a TV devem ser novamente testados. Se o triângulo TV está depois de T na seqüência, os vizinhos de T são testados em relação a T e o teste continua a partir de T. Em cada um destes testes, é verificado se os triângulos alterados estão antes de T na seqüência e todos que estão antes são novamente testados.
A triangulação criada a partir das amostras pode ser modificada com a inserção de linhas de quebra. As linhas de quebra podem estar no mesmo plano de informação das isolinhas ou podem estar em outro plano. Para o caso de linhas de quebra no mesmo plano, elas são diferenciadas com o uso de um identificador que define o tipo de linha. Quando as linhas de quebra estão em outro plano de informação, a categoria deste plano deve ser diferente da categoria Numérica, de modo que todas as linhas do plano serão consideradas de quebra. As linhas de quebra do plano de entrada são copiadas e inseridas na triangulação.
Durante a geração de grades triangulares com as linhas de quebra, estas linhas de quebra são incorporadas à triangulação, constituindo arestas de triângulos. O modelo final ou seja, a grade triangular irregular, terá estas informações adicionais de linha de quebra incorporadas, possibilitando assim uma representação mais fiel do terreno, uma vez que não suaviza feições como vales e cristas.
NOTA : No SPRING esta modelagem pode ser elaborada a partir de amostras
(pontos e isolinhas), grades regulares ou outra grade triangular (TIN). Uma vez que a
grade triangular tenha sido gerada, é possível a geração de isolinhas, cálcular
declividade e gerar grade regular a partir do TIN.
Veja também :
Como gerar uma Grade Triangular.
Grades