Algoritmos Geométricos Prof. Herondino 1. Principais técnicas e algoritmos As principais técnicas e algoritmos utilizados na implementação das diversas funções de um sistema de gerência de bancos de dados espaciais (SGDBE), em especial as operações sobre representações vetoriais (pontos, linhas e polígonos). Imagem Digital Processo de digitalização ( Gonzales e Woods, 2002) 1.1Ponto Um ponto é um par ordenado (x, y) de coordenadas espaciais Representação matemática do pixel digital ( Gonzales e Woods, 2002) Representação da Imagem Digital Fonte: Gonzales e Woods, 2002 1.2 Linha poligonal Sejam v0 , v1 , v2 ,...,vn1 n pontos no plano. Exemplo: 1.2 Linha poligonal Sejam v0 , v1 , v2 ,...,vn1 n pontos no plano. Sejam s0 v0v1, s1 v1v2 ,...,sn2 vn2vn1 , uma sequencia de n – 1 segmentos, conectando estes pontos. Exemplo: 1.2 Linha poligonal Estes segmentos formam uma poligonal L se, e somente se, (1) a interseção de segmentos consecutivos é apenas o ponto extremo compartilhado por eles (i.e. , si si 1 vi 1 ), (2) segmentos não consecutivos não se interceptam (i.e., si s j Ø para todo i e j tais que j i 1 ) , e (3) v0 vn1 , ou seja, a poligonal não é fechada. 1.3 Polígono Um polígono é a região do plano limitada por uma linha poligonal fechada A definição acima implica que, apenas invertendo a condição (3) da definição de linha poligonal, temos um polígono (i. e., v0 vn1 ). 1.4 Tipos abstratos de dados Estas três entidades geométricas básicas podem ser definidas em uma linguagem de programação usando tipos abstratos de dados. 1.5 Algoritmos Básicos 1.5.1 Área do Triângulo 1.5.2 Coordenadas Baricêntricas Para determinar se um determinado ponto pertence ou não a um triângulo, utiliza-se um método baseado em coordenadas baricêntricas Sinais das Coordenadas Baricêntricas indica a região p do plano 1.5.2 Coordenadas Baricêntricas Cada ponto p do plano pode ser escrito na forma: p 1 p1 2 p2 3 p3 Em que 123 e 1 2 3 1 Os valores 1 , 2 e 3 são obtidos usando a regra de Cramer, expressos em áreas de triângulos de vértices p, p1 , p2 e p3 . A análise do sinal das coordenadas baricêntricas indica a região do plano em que se encontra p, em relação ao triângulo p1 p2 p3 . 1.5.3 Interseção de Retângulos O uso do retângulo envolvente mínimo (REM) é uma estratégias que procura evitar, o uso de procedimentos computacionalmente caros. O REM é o menor retângulo com lados paralelos aos eixos coordenados que contém a geometria do objeto Interseção de REMs REMs Disjuntos 1.5.3 Interseção de Retângulos Interseção de retângulos envolventes mínimos 1.5.4 Interseção de dois segmentos de reta A solução consiste em testar se os pontos p1 e p2 estão de lados opostos do segmento formado por p3 p4 e também se p3 e p4 estão de lados opostos do segmento formado por p1 p2 . 1.5.4 Interseção de dois segmentos de reta A solução consiste em avaliar o sinal da área dos triângulos formados por p1 p2 p3 e p1 p2 p4 Se os sinais forem contrários, significa que os pontos estão de lados opostos. Exemplo 1 O ponto de interseção Dados dois segmentos formados pelos pontos p1 p2 e p3 p4 , respectivamente, e com p1 ( x1, y1 ), p2 ( x2 , y2 ), p3 ( x3 , y3 ) e p4 ( x4 , y4 ) o ponto de interseção entre eles é dado por: p1 u( p2 p1 ) p3 v( p4 p3 ) Esta igualdade dá origem a um sistema com duas equações e duas incógnitas (u e v): xint e sec x1 u ( x2 x1 ) xint e sec x3 v( x4 x3 ) ou yint e sec y1 u ( y2 y1 ) yint e sec y3 v( y4 y3 ) O ponto de interseção Desenvolvendo o sistema, temos: ( x4 x3 )( y1 y3 ) ( y4 y3 )(x1 x3 ) u ( y4 y3 )(x2 x1 ) ( x4 x3 )( y2 y1 ) ( x2 x1 )( y1 y3 ) ( y2 y1 )(x1 x3 ) v ( y4 y3 )(x2 x1 ) ( x4 x3 )( y2 y1 ) Calculados os parâmetros u e v, podemos determinar o ponto de interseção Exemplo: Calculando pelo u u ( x4 x3 )( y1 y3 ) ( y4 y3 )(x1 x3 ) ( y4 y3 )(x2 x1 ) ( x4 x3 )( y2 y1 ) Exemplo: Substituindo o u xint e sec x1 u ( x2 x1 ) yint e sec y1 u ( y2 y1 ) Exemplo 2 Mostre que os pontos p1 p2 estão de lados opostos e encontre o ponto de interseção. Análise do parâmetro u e v Se o denominador for zero, as duas linhas são paralelas. Análise do parâmetro u e v Se além do denominador os numeradores de ambos os parâmetros também forem zero, então as duas linhas são coincidentes. 1.5.5 Área de polígonos A área de um polígono pode ser calculada em tempo linear com relação ao número de vértices, usando um somatório simples, baseado na soma de áreas de triângulos formados entre cada par de vértices consecutivos e a origem do sistema de coordenadas (O'Rourke, 1998): 1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) p4 ( x3 , y3 ) ( x0 , y0 ) (4,1) Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) p4 ( x3 , y3 ) ( x0 , y0 ) (4,1) 1 A( P) ( x0 x1 ) ( y1 y0 ) .... .... 2 Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) p4 ( x3 , y3 ) ( x0 , y0 ) (4,1) 1 A( P) ( x0 x1 ) ( y1 y0 ) ( x1 x2 ) ( y2 y1 ) ... 2 Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) p4 ( x3 , y3 ) ( x0 , y0 ) (4,1) 1 A( P) ( x0 x1 ) ( y1 y0 ) ( x1 x2 ) ( y2 y1 ) ( x2 x3 ) ( y3 y2 ) 2 Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) p4 ( x3 , y3 ) ( x0 , y0 ) (4,1) 1 A( P) ( x0 x1 ) ( y1 y0 ) ( x1 x2 ) ( y2 y1 ) ( x2 x3 ) ( y3 y2 ) 2 1 A( P) (4 1) (1 1) (1 1) (5 1) (1 4) (1 5) 2 Exemplo: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 p1 ( x0 , y0 ) (4,1) p2 ( x1 , y1 ) (1,1) p3 ( x2 , y2 ) (1,5) p4 ( x3 , y3 ) ( x0 , y0 ) (4,1) 1 A( P) ( x0 x1 ) ( y1 y0 ) ( x1 x2 ) ( y2 y1 ) ( x2 x3 ) ( y3 y2 ) 2 1 A( P) (4 1) (1 1) (1 1) (5 1) (1 4) (1 5) 2 1 A( P ) (4 0 2 4 5 (4) 2 Exemplo 2: 1 i n1 A( P) ( xi xi 1 ) ( yi 1 yi ) 2 i 0 Referência Bibliográfica M. Casanova, G. Câmara, C. Davis, L. Vinhas, G. Ribeiro (org), “Bancos de Dados Geográficos”. São José dos Campos, MundoGEO, 2005. Gonzalez, R. C.; Woods, R. E. Processamento de imagens digitais. São Paulo: Edgard Blücher Ltda, 2003.
Download
