Pretende-se construir uma rotina (densifica_grelha) que densifique as cotas de terreno dadas numa grelha regular (quadrada) G₁ de espaçamento h₁, numa grelha regular G₂ de espaçamento h₂. Esta densificação é construída a partir de uma interpolação polinomial bicúbica segmentada em cada malha da rede.

Por outras palavras, para cada malha da grelha G₁ pretende-se interpolar as cotas dos novos pontos que fazem parte da grelha G₂ (ver figura seguinte). Esta interpolação será calculada fazendo passar pela malha da grelha um polinómio de Hermite bicúbico, ou seja, de grau 3 em x e grau 3 em y.

1. Expressão matricial do polinómio de Hermite bicúbico segmentado

A expressão geral de um polinómio de grau n em x e grau m em y é

(1)

Em notação matricial esta expressão pode escrever-se na forma

(2)

com



No intervalo [x_i,x_i+1] x [y_j,y_j+1] o polinómio de Hermite bicúbico segmentado, é definido tomando n=m=3 na equação (1). Donde resulta que, os 16 coeficientes c_ij (i,j=0,...,3) determinam univocamente este polinómio bicúbico.

Por outro lado, designando por



é possível demonstrar que os coeficientes c_ij podem ser determinados a partir da equação

F = R C S^T

onde



2. Interpolação bicúbica no rectângulo elementar

O cálculo do polinómio bicúbico segmentado torna-se mais simples se utilizarmos um sistema de coordenadas local, isto é, de forma a que o rectângulo genérico [x_i,x_i+1] x [y_j,y_j+1], de espaçamento h x k, seja transformado no rectângulo elementar [0,1] x [0,1]. Para realiz esta transformação faz-se



De facto em R o polinómio interpolador de Hermite segmentado cúbico é dado por



onde



Neste caso os 16 coeficientes c_ij do polinómio bicúbico serão obtidos a partir da equação:



onde



Para determinar a linha i e coluna j correspondente ao ponto (x,y) utiliza-se as seguintes expressões:



onde (x₀,y₀) são as coordenadas do ponto origem da grelha (i.e. para i=0, j=0).

A rotina de densificação deverá ser devidamente comentada e estruturada.

1. Parâmetros de entrada

Os parâmetros de entrada são:

• a matriz A de dimensão (n₁,m₁) representando a grelha inicial;
• o factor de densificação d.

2. Parâmetros de saída

Os parâmetros de saída são:

• a matriz B de dimensão (n₂,m₂).

O relatório do trabalho, a entregar até final do semestre lectivo, deverá constar de:

• uma descrição do algoritmo;
• um fluxograma da rotina;
• um apêndice contendo o código da rotina (e do programa principal);
• uma disquete contendo o código do programa e o programa executável (em alternativa poderá enviar o seu código via email para o endereço email: alma@mat.uc.pt).