Universidade
Federal de Viçosa
Tratamento de Erros de
Arredondamento na Biblioteca
TerraLib
Jaudete Daltio1
Marcus Vinícius Alvim Andrade1
Gilberto Ribeiro de Queiroz2
1
UFV - Universidade Federal de Viçosa - Departamento de Informática, Viçosa, MG, Brasil
2 INPE - Instituto Nacional de Pesquisas Espaciais, São José dos Campos, SP, Brasil
Introdução
TerraLib: Biblioteca de Componentes de
SIG
Desenvolvida pela parceria
• INPE (Instituto Nacional de Pesquisas Espaciais)
• Tecgraf/PUC-Rio (Grupo de Computação Gráfica da
Universidade Católica do Rio de Janeiro)
• FUNCATE (Fundação de Ciência, Aplicações e Tecnologia
Espaciais)
Visa a implementação de aplicativos
geográficos customizados – Small GIS
www.terralib.org
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Erros de Arredondamento
Metodologias
Computação Exata
Aritmética Intervalar
Aritmética Afim
Solução aplicada a TerraLib
Tolerâncias

TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Distorções Topológicas
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Erros de Arredondamento
Variações de Valor
Variação numérica do resultado
Controlada: inerentes ao processo
Variações de Decisão
Decisões erradas baseadas em valores de
processamento numérico
Resultados imprevisíveis
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Objetivos
Incorporar tratamento de erros de
arredondamento na TerraLib
Analisar onde os erros levam a situações
críticas
Minimizar este efeito em predicados
sensíveis às variações de decisão
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Arquitetura Modular da
TerraLib
Algoritmos
Algoritmos
Visualização
Conversor de
Dados
Estrutura de
Estrutura de
Dados
Dados Espaciais
Espaciais
Gerenciador
de Dados
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Representação de Dados
Espaciais
Pontos
Coordenadas Homogêneas Inteiras
Coordenadas
Homogêneas
Coordenadas
Cartesianas
x, y, z, w   x , y , z    3
w w w


TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Representação de Dados
Espaciais
Retas
Coeficientes Homogêneos da Reta
Coordenadas Inteiras
P0  x0 , y0 , w0 
P1  x1 , y1 , w1 

 x0
x
 1
 x
y0
y1
y
w0 
w1 
w 
x, y, w  y0 w1  y1w0 , x1w0  x0 w1, x0 y1  x1 y0
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Vantagens
P =1
2
 ,   1,2,3
3 3
P=
1,2,0
Simplificação das operações básicas
Interseção entre segmentos
Reta passando por 2 pontos
Orientação de 3 pontos
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Resultados
A Orientação de três pontos
Baseado no trabalho de Jonathan Richard
Shewchuk - “Adaptive Precision Floating-Point
Arithmetic and Fast Robust Geometric
Predicates”
É possível retornar respostas corretas sem
prosseguir os cálculos da Computação
Exata
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Orientação de três pontos
A: resultado ponto flutuante, obtido através
da avaliação convencional
B e C: expansão dos números em diferentes
pontos da equação e realização do cálculo
exato das operações
D: o determinante exato
A maioria das execuções termina com a
aproximação A
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Interseções de segmentos Plane Sweeper
S1
R
S2
S3
(a)
(b) (c)
(a) evento esquerdo (b) evento direito (c) interseção
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Interseções de segmentos
Tratamento de Overflows:
Sobrecarga das operações básicas
Translação dos pontos para o menor valor
de X e Y dentre as coordenadas
Bisseção dos segmentos: descartar o
trecho de cada segmento que não contém
o ponto interseção
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib
Próximos Passos
Determinação de envoltório convexo
Orientação de polígonos
Relacionamentos topológicos
Operadores união, interseção e
diferença - sobreposição
Comparação do comportamento da
implementação original em situações
críticas com os resultados obtidos
TerraUFV - Tratamento de Erros de Arredondamento na Biblioteca TerraLib