INTRODUÇÃO

 

 O processo de optimização da decomposição de um polígono em sub-polígonos convexos resulta de um príncipio bastante simples: a eliminação das “fronteiras” desnecessárias entre sub-polígonos, isto é, da sua eliminação resulta um sub-polígono igualmente convexo. Para isto é condição necessária e suficiente que os pontos que definem o segmento “fronteira” entre dois sub-polígonos não sejam nós.

Esta optimização é implementada através de um procedimento retmargem que é acedido no programa após a decomposição de cada um dos polígonos do ficheiro de entrada. Iremos descrever este procedimento e cada uma das sub-rotinas a ele inerentes.

 

  

TIPOS DE DADOS

 

v   DEFINIÇÃO DE NOVAS VARIÁVEIS GLOBAIS

 

poli – ficheiro temporário onde serão colocados os sub-polígonos resultantes da decomposição de cada um dos polígonos do ficheiro de entrada e sobre o qual é feita a optimização. Cada registo deste ficheiro corresponde a um sub-polígono.

poli_out – ficheiro onde será colocado o contéudo do ficheiro poli para cada polígono tratado. É associado ao ficheiro físico o nome R seguido do nome lido para nomefich. Cada registo deste ficheiro corresponde a um sub-polígono.

  

 

v  DEFINIÇÃO DAS VARIÁVEIS DO PROCEDIMENTO RETMARGEM

           

vs – tipo vertice onde é colocado um ponto da margem a testar – último ponto do sub-polígono. 

            vs_inc – tipo vertice onde é colocado o ponto que se segue a vs no sub-polígono  a testar a possível concatenação. 

            vs_dec – tipo vertice onde é colocado o ponto do sub-poligono que antecede vs. 

            • vh – tipo vertice onde é colocado o outro ponto da margem a testar – primeiro ponto do sub-polígono. 

vh_inc – tipo vertice onde é colocado o ponto do sub-polígono que se segue a vh.

vh_dec – tipo vertice onde é colocado o ponto que antecede vh no sub- -polígono a testar a possível concatenação.  

polig1 – registo com os dados relativos ao sub-polígono que contém a margem a eliminar.

pol – registo com os dados relativos ao sub-polígono a testar a possível concatenação.

pt_com – registo do tipo ptcom onde é colocado o elemento da lista pt a testar – a margem a testar.

 

 Nota: Os  tipos de dados usados são os já definidos no anterior relatório, tendo sido efectuadas as seguintes alterações:

 

          nomes string com capacidade para dez caracteres.

         peca registo que contém os seguintes campos:

nome      tipo nomes

texto       string com  “NUMERO DE VERTICES”

num        inteiro com o número de vértices do polígono

vert          string com  “VERTICES (X, Y, tangente/2)”

pontos  matriz 3053 de valores reais em que a uma linha i corresponde um  ponto com: abcissa pontos[i,1], ordenada pontos[i,2] – , e tang/2 pontos[i,3]

 

 

 

PROCEDIMENTO RETMARGEM

 

 Este procedimento actua sobre os dados relativos à decomposição do polígono através do algoritmo já descrito que se encontram no ficheiro temporário poli. Esta decomposição é optimizada de forma a serem eliminadas as margens desnecessárias, ou seja, realiza a “reunião” de sub-polígonos quando o resultado desta ainda for um sub-polígono convexo e coloca a decomposição resultante no mesmo ficheiro poli.

 

rpeca4.gif (18440 bytes)

rpeca_4 antes do procedimento retmargem                                     rpeca_4 após procedimento retmargem

 

Este procedimento faz uso de sub-rotinas pertencentes ao programa  principal, assim como de sub-rotinas próprias cujo princípio de funcionamento será mais tarde referido.

 A lista pt é totalmente percorrida sendo realizado para cada elemento  (par de vértices que definem uma margem) o algoritmo que se descreve em seguida.  À variável pt_com é atribuído o primeiro elemento desta lista.

 

1 -  São atribuídos às variáveis vh e vs os vértices que definem a margem em questão (campos p1 e p2 do registo pt_com, respectivamente)  

 2 – Caso se verifiquem as seguintes condições:

      –   encontra1 (vs_dec,vh_inc) = true

   encontra2 (vs_inc,vh_dec) = true

   angulo (vs_dec,vs,vs_inc) <= 180º

   angulo (vh_dec,vh,vh_inc) <= 180º

fig1.gif (7396 bytes)

2.1 – Concatenação dos sub-poligonos polig1 e pol  através do procedimento junta.

2.2 – Actualização do ficheiro temporário poliactualiza.

2.3 – Eliminação na lista pt do elemento que contém a margem – retpt.

3 – Atribuição à variável pt_com da nova margem da lista pt a testar.

 

 Finalmente são copiados para o ficheiro de saída poli_out os dados do ficheiro poli – a decomposição optimizada do polígono.

 

  

SUB-ROTINAS

  

encontra1 é uma função do tipo booleano sendo-lhe atribuído o valor true se o ponto em vs e vh forem dois pontos consecutivos de algum dos sub-polígonos do ficheiro poli (o sub-polígono é colocado no registo polig1). Para além disso retorna através da passagem de parâmetros por variável o ponto que antecede vs e o ponto que se segue a vh em polig1 (vs_dec e vh_inc, respectivamente). 

encontra2 é uma função semelhante à função encontra1, só que verifica a existência de algum sub-polígono no ficheiro poli, nas condições  necessárias, apenas a partir da posição que se segue ao polig1 (o sub-polígono encontra-se no registo pol). Neste caso são retornados o ponto que antecede vh e o ponto que se segue a vs em pol (vh_dec e vs_inc, respectivamente).                 

junta –   procedimento que concatena os sub-polígonos que se encontram em polig1 e pol. Esta concatenação é feita da seguinte forma:

   pontos de polig de vh até vs inclusivé

   pontos de pol de vs até vh inclusivé

 Coloca nas variaveis vs, vs_dec, vh e vh_inc os pontos inerentes à margem que corresponde aos sub-polígonos concatenados.

 altnome – procedimento que actualiza o nome do sub-polígono, retorna o novo nome através do parâmetro do tipo nomes – s.

actualiza – procedimento que coloca o resultado da concatenação na posição i do ficheiro poli e simultaneamente elimina o registo que contém os dados relativos ao sub-polígono pol. Para isso utiliza um ficheiro temporário f_temp para onde copia todos os registos de poli excepto o registo que corresponde a pol.O ficheiro poli é apagado, muda-se o nome externo do ficheiro f_temp para "fx_temp" e associa-se o ficheiro poli a "fx_temp".

retpt – percorre-se a lista pt com dois apontadores à procura da “margem” a eliminar (pt_com). Detectado esse registo, é retirado da lista garantindo-se que não há perda de qualquer outra informação.