Teoria : Estruturas de Dados

Estrutura Vetorial

Quais tipos de dados são representados por estruturas vetoriais?

• Mapa temático:
  • Contém regiões geograficamente definidas por um ou mais polígonos como os cartografados em mapas de uso do solo e de vegetação. As informações qualitativas são sobre um único tema obtidos, ou a partir de levantamentos de campo e posteriormente inseridos no sistema por digitalização ou a partir da classificação automática de imagens.
  • Associado a uma categoria do modelo temático, onde o processo de modelagem espacial é definido por geocampos, representados por áreas homogêneas com limites definidos (polígonos). Cada área de um geocampo está associada a um e somente um valor de variável espacial representada. Por exemplo, em um mapa de solo, cada posição do espaço está associado a um tipo específico de solo.
• Mapa Cadastral
  • Distingue-se de um mapa temático por não possuir temas e considerar seus elementos como objetos geográficos que possuem atributos e podem estar representados em vários mapas de diferentes escalas e projeções. Por exemplo, os lotes de uma cidade são elementos do espaço geográfico que possuem atributos (dono, localização, IPTU, etc.) e que podem ter representações gráficas em mapas de escalas distintas.
  • Associado a categoria do modelo cadastral, onde o processo de modelagem espacial é definido por objetos geográficos. Os objetos têm existência independente de sua representação num mapa e são usualmente criados a partir de seus atributos e só depois localizados no espaço. Por exemplo, a classe de objeto de um mapa cadastral indicada por hospital pode estar especializada em hospital público e hospital privado e os atributos da classe hospital são herdados pela subclasses hospital público e hospital privado, que podem ter atributos próprios.
  • De forma similar ao mapa temático, no mapa cadastral a representação dos dados usualmente se apresentam na forma vetorial e utiliza a topologia arco-nó-polígono para armazenamento dos dados.
• Mapa de Rede:
  • Mapa que utiliza a topologia arco-nó e armazena a localização e a simbologia associadas à estruturas linearmente conectadas. Pode ser associado à informações referentes à:
    • Serviço de utilidade pública, água, luz e telefone;
    • Redes de drenagem (bacias hidrográficas);
    • Rodovias.
  • Este mapa deverá estar associado a categoria do modelo e similarmente ao modelo cadastral, o processo de modelagem espacial é definido por objetos geográficos rede. Cada objeto geográfico do mapa de rede (ex. cabo telefônico, transformador de rede elétrica, cano de água) possui uma localização geográfica exata e está sempre associado a atributos descritivos, presentes no banco de dados.
  • As informações gráficas de redes são armazenadas em coordenadas vetoriais, com topologia arco-nó e podem conter atributos. Os atributos de arcos, indicam o sentido de fluxo enquanto os atributos dos nós indicam a impedância (custo de percorrimento). A topologia de redes constitui um grafo, que armazena informações sobre recursos que fluem entre localizações geográficas distintas. Para citar um exemplo, tome-se uma rede elétrica , que tem entre os componentes: postes, transformadores, subestações, linhas de transmissão e chaves. As linhas de transmissão serão representadas topologicamente como os arcos de um grafo orientado, estando as demais informações concentradas em seus nós.
• Modelos Numéricos de Terreno
  • Representação matemática da distribuição espacial de uma determinada característica vinculada a uma superfície real.
  • Associado a uma categoria do modelo numérico, onde o processo de modelagem espacial é definido por geocampos, assim para uma dada área geográfica , um geocampo numérico associa, a cada ponto do espaço, um valor real.
  • Uma mapa de MNT pode ser armazenado na forma vetorial ou matricial. Na representação vetorial a topologia pode ser do tipo arco-nó, com arcos que se conectam entre si através de nós (ponto inicial e final) ou Grade Triangular (TIN), onde os arcos se conectam através de pontos formando uma malha triangular. A representação matricial é do tipo grande retangular, na qual uma área é dividida em células de tamanho fixo e cada célula tem o valor as superfície.

Quais os elementos básicos da estrutura vetorial?

• Pontos, linhas e áreas (ou polígonos) são os elementos que permitem a estrutura vetorial representar os dados da forma mais precisa uma vez que suas coordenadas geográficas estão em um espaço contínuo e possibilitam descrição exata de posição, tamanho e dimensão.

O que é ponto?

• Definido para toda entidade geográfica que pode ser localizada por um par de coordenadas xy, é utilizada para representar a localização de um fenômeno geográfico, ou para representar uma feição do mapa que é muito pequena para ser mostrada como uma área ou linha. Exemplos: localização de uma cidade, uma pista de pouso, o pico de uma montanha ou um ponto cotado (quando este além das coordenadas XY, tem-se um atributo Z, que pode ser a cota altimétrica ou outro parâmetro qualquer).

O que é linha?

• Definida por no mínimo dois pares de coordenadas xy (dois pontos) é utilizada para representar feições do mapa que são muito estreitas para serem mostradas como área ou que teoricamente não têm espessura. Exemplos: um rio, uma rodovia, linha de costa de um continente, uma linha de contorno ou um limite administrativo.

• Quando uma linha passa a ter um atributo Z qualquer, além das coordenadas XY dos pontos que a constitui, é chamada de isolinha. Ao longo de uma isolinha todos os pontos têm o mesmo valor de Z.

O que são áreas?

• Definidas como série de coordenadas (x,y), formando segmentos de linhas que fecham uma área e freqüentemente representam-se elementos de área por polígonos. Exemplos: extensão geográfica de uma cidade, um lago, uma área desmatada.

O que são representações vetoriais?

• Os três elementos básicos são traduzidos em objetos geográficos com representações conhecidas como Nós, Pontos, Arcos, Isolinhas, Ilhas, Linhas poligonais e Polígonos. Dependendo dos objetos geográficos que serão representados nos mapas, os pontos correspondem à arcos, nós, linhas poligonais, polígonos ou ilhas.

O que é arco?

• Conjunto de pontos interligados por segmentos de reta que começa e termina em um nó. Exemplos:

• Arcos são usados para modelar as fronteiras dos polígonos delimitando objetos que definem áreas.
• Um nó é um tipo especial de ponto que tem por objetivo definir o ponto de interseção de dois ou mais arcos. Dois polígonos adjacentes podem compartilhar o mesmo arco, desde que a interseção das linhas seja delimitada pela presença de um nó.

O que é uma ilha?

• Tipo especial de polígono delimitado por um único arco, apenas um nó define o ponto inicial e final do polígono, uma vez que não há polígonos adjacentes.

O que é uma linha poligonal?

• Ou polígono aberto, é formado por um conjunto de pontos interligados por segmentos de reta que começam e terminam em um nó. Ao contrário de um arco uma linha poligonal não define uma área (polígono). Utilizada para modelar feições lineares como linhas que representam fraturas geológicas, rios, estradas, e outros elementos geográficos que possam ser observados como feições lineares.

• A linha poligonal é utilizada quando o ponto de interseção das linhas não deve ser modelada, e então não há necessidade de se introduzir um nó.

O que é isolinha?

• Uma linha poligonal em que é atribuído um único valor Z.

O que é topologia?

• Definida como a parte da matemática que estuda as propriedades geométricas que não variam mediante uma deformação, especificamente o relacionamento espacial entre os objetos, como por exemplo proximidade e vizinhança. Formas e coordenadas dos objetos são menos importantes que os elementos do modelo topológico como conectividade, contiguidade e continência. A definição da topologia explicita os relacionamentos espaciais entre os objetos através de um processo matemático.
• A definição da topologia para um dado de modelo temático ou cadastral, resulta na criação dos polígonos armazenando as informações das linhas, nós e identificadores que os compõem, as linhas que são compartilhadas por diferentes polígonos e as vizinhanças e circunscrividade entre eles.
• A topologia pode ser definida automaticamente durante a digitalização se, ao digitalizar uma linha, um nó é inserido automaticamente quando intercepta outra linha ou termina a própria. Uma vez definida a topologia, cada polígono poderá então ser associado a uma classe temática, ou a um objeto do mapa cadastral, ou ainda de um segmento de um rede.

Como é efetuada a edição de dados vetoriais?

• O processo de edição de vetores consiste inicialmente em digitalizar linhas, corrigir ou ajustar os nós, para então constitur polígonos.

O que é digitalização?

• A digitalização é um processo que permite converter dados espaciais do meio analógico para o digital permitindo a realização das operações típicas de análise espacial. A digitalização das linhas pode ser por passo, introduzindo ponto-a-ponto, ou em modo contínuo, seguindo a feição com freqüência de pontos a serem adquiridos definida através de um Fator de Digitalização.
• Fator de Digitalização corresponde ao intervalo entre os pontos da linha a ser digitada. O fator é dado normalmente em mm na escala do mapa que está sendo editado e deve ser considerado o fato de a precisão cartográfica de mapas é da ordem de 0.3mm da escala do mapa. Assim, um fator de digitalização menor que este valor estará fora do próprio limite de precisão do mapa.
• Caso a definição de topologia seja automática, cada vez que um arco intercepta outro, um nó é automaticamente definido, sendo ideal para digitalizar polígonos. Com topologia manual nós ou quebras de linha devem ser explicitados pelo operador, sendo indicado para digitalizar linhas que devem permanecer íntegros, mesma que outras a cruzem.
• A digitalização pode ser realizada através de diferentes instrumentos, como por exemplo mesa digitalizadora (o mais usual), dispositivos imageadores por varredura ou monitor de vídeo (tela).

Como se efetua a digitalização via mesa?

• A mesa digitalizadora é constituída basicamente de duas partes:
  • - uma superfície plana, sensível eletronicamente, onde se coloca o mapa ou o gráfico a ser digitalizado;
  • - um "mouse", que envia as coordenadas (x,y) de um ponto na superfície da mesa, para o computador.

• O mouse da mesa digitalizadora tem a função de adquirir as coordenadas xy, que serão relacionadas às coordenadas geográficas, através de botões, que desempenham funções específicas para cada objetivo. Em geral as seguintes operações estão disponíveis:
  • Adquirir pontos, ou seja, edita pontos e linhas com o botão "select" (botão 1) do mouse do cursor.
  • O botão "adjust" para término de uma linha.
  • Finalizar a digitalização manual dos dados.

Como se efetua a digitalização via tela?

• Linhas ou pontos do mapa podem ser digitalizados na própria tela, utilizando-se o mouse do cursor para a definição dos objetos geográficos, utilizando os botões do mouse do cursor:
  • O botão select do mouse do cursor seleciona e edita linhas ou seleciona, edita e move pontos.
  • O botão adjust do mouse do cursor marca o fim de uma linha, inserindo nós.

Quais erros estão associados à digitalização de vetores?

• Digitalização de número de pontos insuficientes: a representação do formato de curvas depende do número de vértices utilizados. Conseqüentemente, o erro relativo à digitalização de linhas retas é muito menor que o resultante da digitalização de curvas complexas.

• A definição coerente do Fator de Digitalização pode minimizar este erro, no entanto fatores muito pequenos produzem linhas com excesso de pontos.

• Alguns erros podem ser evitados e outros provocados a partir da escolha da topologia manual ou automática, podendo ser classificados quanto a estes procedimentos.

Quais erros ocorrem com uso de topologia manual ?

• Usuário não definiu um nó - em um polígono, toda linha que intercepta outra linha deve ter associado um nó notificando o ponto de interseção. Neste caso deve-se inserir um ponto na linha que interceptada e transformá-la em nó para que se possa as juntar linhas.

• .

• Usuário não fez a sobreposição dos nós: na digitalização o polígono fica aberto, ou uma linha não alcança ou ultrapassa o ponto de interseção. Pode ser necessária a edição manual destes nós, aproximando-os ou juntando as linhas.

Quais erros ocorrem com uso de topologia automática?

• Usuário ultrapassa o limite de interseção - como a linha será automaticamente quebrada, uma pequena linha após o cruzamento poderá ficar residente e deverá ser eliminada manualmente (opção eliminar linhas).
• Usuário não definiu corretamente limites entre polígonos: na digitalização, as linhas podem se sobrepor ou deixar uma lacuna entre elas.
• Sobreposição - como não há nós inseridos o erro será apenas detectado na geração de polígonos, devendo-se então corrigi-lo através da edição manual.
• Lacuna - este erro não tem como ser detectado estando relacionado com a acuidade do operador durante a digitalização.
• Usuário não fez a sobreposição dos nós: na digitalização o polígono fica aberto, ou uma linha não alcança (ou ultrapassa) o ponto de interseção.

• Usuário não definiu corretamente limites entre polígonos: na digitalização, as linhas podem se sobrepor ou deixar uma lacuna entre elas.

Como é a estrutura matricial?

• Define-se o formato matricial ou varredura (ou ainda "raster") como um conjunto de celas localizadas em coordenadas contíguas, implementadas como uma matriz 2D. Cada célula é referenciada por índices de linha e coluna e contém um número representando o tipo ou o valor do atributo mapeado. Os valores de cada "pixel" estão limitados num certo intervalo numérico, como por exemplo de 0 a 255 para imagens em 8 bits, ou números associados à classes no caso de uma imagem temática.

Quais são as vantagens e as desvantagens das estruturas vetorial e matricial?

• As representações matricial (ou varredura) e vetorial não são exatamente equivalentes para um mesmo dado havendo perda de precisão na transformação do formato vetorial para o formato de varredura, uma vez que bordas contínuas são discretizadas de acordo com a resolução da imagem de saída. Esta perda pode ser compensada pelo fato de que as operações de análise geográfica no domínio varredura serem mais eficientes.
• A representação vetorial é a mais adequada para identificar objetos, individualizáveis no terreno, onde se requer precisão. A representação varredura por sua vez é mais adequada para fenômenos e grandezas que variam continuamente no espaço.

Como se efetua a conversão do formato vetorial para o matricial?

• A conversão gera uma imagem em formato varredura (ou "raster") a partir de dados representados vetorialmente. Dois casos devem ser analisados: o elemento linear e o polígono.
  • A conversão para um elemento linear pode ser esquematizada sobrepondo-se este a uma matriz varredura. Essa conversão identifica os elementos da matriz que cruzam a linha e codifica-os com atributos ou valores de classe associados à linha.

• Para elementos poligonais define-se a área a ser convertida e o tamanho do pixel, definindo uma grade que é sobreposta ao mapa de polígono original. A cada pixel é associada uma classe, considerando o centro do pixel e verificando em qual polígono este se encontra, associando ao pixel, o valor de classe do polígono.

• A conversão da representação vetorial para a varredura introduz distorções na geometria original dos dados. Estas distorções aumentam com o tamanho do pixel e com a complexidade das fronteiras entre polígonos. Pixels localizados sobre uma fronteira (pixels mistos) serão mapeados para a classe do polígono mais próximo. Quanto menor o tamanho da célula ("pixel"), maior a fidelidade da imagem convertida.

Como se efetua a conversão do formato matricial para o vetorial?

• A conversão da representação varredura para a vetorial deve extrair os contornos dos objetos e as relações espaciais entre eles, tais como vizinhança e pertinência entre polígonos, e conectividade entre arcos.
• A partir da imagem original, o algoritmo gera uma imagem binária contendo apenas as fronteiras entre os objetos presentes.

• As fronteiras são construídas entre os pixels: se a imagem original tem tamanho nxn, onde n é o número de linhas e o número de colunas, a imagem binária terá tamanho (2n + 1) x (2n + 1). Durante a conversão da imagem para o formato binário, detectam-se também os nós e, a seguir, os contornos dos objetos são extraídos (vetorizados) da imagem binária e suavizados para amenizar o "efeito de escada", característico da representação por varredura.
• Finalmente, os polígonos e as relações espaciais (vizinhança e pertinência entre polígonos, e conectividade entre arcos) são construídos.