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 ,...,vn1 n pontos no plano.
Exemplo:
1.2 Linha poligonal
 Sejam v0 , v1 , v2 ,...,vn1 n pontos no plano.

Sejam
s0  v0v1, s1  v1v2 ,...,sn2  vn2vn1
, 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  vn1 , 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  vn1 ).
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 123   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 n1
A( P)    ( xi  xi 1 )  ( yi 1  yi )
2 i 0
Exemplo:
1 i n1
A( P)    ( xi  xi 1 )  ( yi 1  yi )
2 i 0
p1  ( x0 , y0 )  (4,1)
Exemplo:
1 i n1
A( P)    ( xi  xi 1 )  ( yi 1  yi )
2 i 0
p1  ( x0 , y0 )  (4,1)
p2  ( x1 , y1 )  (1,1)
Exemplo:
1 i n1
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 n1
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 n1
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 n1
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 n1
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 n1
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 n1
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 n1
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.