Sistemas de Informações
Geográficas
Unidade 3.2: Estrutura de Dados
Espaciais
Prof. Cláudio Baptista
2003.1
3.2 Estrutura de Dados Espaciais
 Necessidade de indexação dos dados
espaciais de modo a reduzir o tempo de
acesso aos mesmos
 Métodos de indexação tradicionais não são
indicados para dados espaciais


Hash: não atende a consultas de faixa (range
queries)
B-Tree: trata apenas uma dimensão
3.2 Estrutura de Dados Espaciais
 Operação comum com dados espaciais é a
pesquisa de objetos que estão numa
determinada área

Ex.: Encontre todos os hospitais que estão a no
máximo 20Km deste ponto
3.2 Estrutura de Dados Espaciais
 Algumas estruturas de dados propostas:




Grid
quad-trees
k-d-tree
r-tree
3.2.1 Quad trees
 Acelera o acesso a dados num plano 2d
 Técnica bastante simples
 O espaço de busca é recursivamente
decomposto em quadrantes até que o
número de retângulos sobrepondo cada
quadrante é menor do que a capacidade da
página.
 Os quadrantes são nomeados: Noroeste,
Nordeste, Sudeste e Sudoeste
3.2.1 Quad trees
 O índice é representado como uma árvore
quaternária (cada nó interno tem 4 filhos,
um por quadrante)
 Cada folha é associada a uma página de
disco
 Cada retângulo aparece em todos os
quadrantes folhas que o sobrepõem
3.2.1 Quad trees
x
1
2
y
5
a
14
8
6 t
z
11
R
12
a
13
3
c
7
4
b
9
10
b
[8,11,12,13]
c
d
[3,4,7] d [9,10,13]
d
x
y
z
t
[1,2,5,6] [5,6,14] [2,3,6] [6]
3.2.1 Quad tree
 Consulta de ponto (point query) é simples
em quad tree.
 Um único path (caminho) é percorrido da
raiz até a folha
 Em cada nível, é escolhido um dos
quadrantes que contém o ponto da consulta
3.2.1 Quad trees
Exemplo de Consulta Ponto P
x
y
a
b
11
1
5
14
2
8
6
z
t
12
P
13
3
c
9
d
7
4
10
R
a
b
[8,11,12,13]
x
y
z
c
d
[3,4,7] d [9,10,13]
t
[1,2,5,6] [5,6,14] [2,3,6] [6]
3.2.1 Quad trees
 Inserção em quadtrees




um retângulo será inserido em cada quadrante
folha que o sobrepõe
então todos os caminhos para as folhas que
sobrepõem o retângulo a ser inserido são
percorridos
a página P associada com cada folha é lida
Se P não está cheio, então insere o novo
retângulo
3.2.1 Quad trees
 Inserção em quadtrees (cont)



Se P estiver cheio, O quadrante deve ser
dividido em quatro quadrantes e 3 novas
páginas são alocadas
As entradas da página antiga mais a página
nova são divididas nas quatro páginas
Uma entrada E é adicionada a toda página cujo
quadrante intercepta E.MBR (Minimum
Bounding Rectangle)
3.2.1 Quad trees
Inserção em Quadtree
x
1
2
y
5
am
14
p 8
6 t
z
3
n
11
b
15
12 q
13
16
c
7
9
d
10
4
Como ficará a árvore após as inserções de 15 e 16?
3.2.2 k-d tree
 Usada para representar pontos
 árvore kd particiona o espaço em
células
 é uma árvore de busca binária,
 reside em memória principal, de forma que
os nós interiores em cada nível contêm
valores referentes a um único eixo, X ou Y,
alternadamente
 as folhas apontam para páginas físicas
 várias folhas podem apontar para a mesma
3.2.2 k-d tree
 o valor armazenado na raiz divide o espaço
em dois subespaços através de uma reta
perpendicular ao eixo dos X, digamos;
 o valor armazenado no filho à esquerda (ou
direita) por sua vez divide o subespaço à
esquerda (ou direita) em dois subespaços
através de uma reta perpendicular ao eixo
dos Y ; e assim por diante, alternando as
dimensões.
3.2.2 K-D-Tree
3.2.2 K-D-Tree
Árvore para figura anterior
A
B
D
C
3.2.2 K-d Tree
 Outro Exemplo
 Sejam as cidades com coordenadas
Cidade
Mossoró
Natal
Campina Grande
João Pessoa
Monteiro
(X,Y)
(19,45)
(40,50)
(38,38)
(54,40)
(4,4)
3.2.2 K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
3.2.2 K-d Tree
 Inserção de Mossoró
Mossoró (19,45)
 Inserção de Natal
Mossoró (19,45)
Natal (40,50)
3.2.2 K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
3.2.2 K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
3.2.2 K-d Tree
 Inserção de Campina
Mossoró (19,45)
Natal (40,50)
Campina (38,38)
3.2.2 K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
3.2.2 K-d Tree
 Inserção de João Pessoa:
Mossoró (19,45)
Natal (40,50)
Campina(38,38)
JP(54,40)
3.2.2 K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
3.2.2 K-d Tree
 Inserção de Monteiro:
Mossoró (19,45)
Monteiro(4,4)
Natal (40,50)
Campina(38,38)
JP(54,40)
3.2.2 K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
3.2.3 R-Tree
 É uma árvore similar a uma B+-tree, com
índices para dados nas folhas
 Nós correspondem à páginas de disco
 A estrutura é projetada de forma que uma
pesquisa espacial requer visitar um número
pequeno de nós
 Um BD espacial consiste de tuplas
representando objetos espaciais, onde cada
tupla possui um identificador
3.2.3 R-Tree
 Nós folhas contêm entradas da forma:




(R, TId)
Onde: R contém o retângulo que encobre a área
da tupla identificada por TId.
Este retângulo é conhecido por Minimum
Bounding Box ou Minimum Bounding
Rectangle
Ex.
3.2.3 R-Tree
 Nós não-folhas contêm entradas da forma:


(R, Filho)
Onde R é o retângulo que envolve todos os
retângulos dos descendentes deste nó e Filho é
o endereço do nó filho
3.2.3 R-Tree
 Definição: Sejam M e m o número máximo
e mínimo de entradas de um nó
respectivamente, tal que m <= M/2



Uma R-tree satisfaz às seguintes propriedades:
P1. Cada nó contém entre M e m entradas,
exceto a raiz
P2. Para cada nó folha (R, TId), R é o menor
retângulo que espacialmente contém os objetos
espaciais n-dimensionais representados pela
tupla TId
3.2.3 R-Tree
 Definição (cont)



P3. Para cada entrada (R, filho) num nó não
folha, T é o menor retângulo que espacialmente
contém os retângulos descendentes
P4. O nó raiz tem pelo menos dois filhos a
menos que seja um nó folha
P5. Todas as folhas aparecem num mesmo nível
3.2.3 R-Tree
3.2.3 R-Tree
PointQuery (consulta ponto)
R
T
P
o
i
n
t
Q
u
e
r
y
(
p
:P
o
i
n
t
)
:s
e
t(
o
i
d
)
b
e
g
i
n
r
e
s
u
l
t=
{
}
;
/
/P
a
s
s
o
1
:A
t
r
a
v
e
s
s
a
r
a
á
r
v
o
r
e
d
a
r
a
i
z
,e
c
o
m
p
u
t
a
r
/
/S
L
,o
c
o
n
j
u
n
t
o
d
e
f
o
l
h
a
s
c
u
j
o
T
I
d
c
o
n
t
é
m
P
S
L
=
R
T
T
r
a
v
e
r
s
a
l
(
r
o
o
t
,P
)
;
/
/P
a
s
s
o
2
:p
e
r
c
o
r
r
a
a
s
f
o
l
h
a
s
e
a
c
r
e
s
c
e
n
t
e
a
o
/
/r
e
s
u
l
t
a
d
o
à
q
u
e
l
a
s
q
u
e
c
o
n
t
i
v
e
r
e
m
P
f
o
r
e
a
c
h
L
i
n
S
L
d
o
/
/P
e
r
c
o
r
r
a
a
s
e
n
t
r
a
d
a
s
d
a
f
o
l
h
a
L
f
o
r
e
a
c
h
e
i
n
L
d
o
i
f
(
e
.
m
b
b
c
o
n
t
é
m
P
)
t
h
e
n
r
e
s
u
l
t+
=
e
.
o
i
d
;
r
e
t
u
r
n
r
e
s
u
l
t
;
e
n
d
PointQuery (consulta ponto)
R
T
T
r
a
v
e
r
s
a
l
(
o
i
d
:
N
o
d
e
,P
:
p
o
i
n
t
)
:
s
e
t
o
f
f
o
l
h
a
s
b
e
g
i
n
r
e
s
u
l
t
=
{
}
;
/
/
O
b
t
é
m
a
p
á
g
i
n
a
N
=
r
e
a
d
P
a
g
e
(
o
i
d
)
;
i
f
(
e
h
F
o
l
h
a
(
N
)
)
r
e
t
u
r
n
N
;
/
/
S
c
a
n
a
s
e
n
t
r
a
d
a
s
d
e
N
e
v
i
s
i
t
a
r
à
q
u
e
l
a
s
q
u
e
c
o
n
t
é
m
P
f
o
r
e
a
c
h
e
i
n
N
d
o
i
f
(
e
.
m
b
b
c
o
n
t
é
m
P
)
t
h
e
n
r
e
s
u
l
t
+
=
R
T
T
r
a
v
e
r
s
a
l
(
e
.
o
i
d
,P
)
;
r
e
t
u
r
n
r
e
s
u
l
t
;
e
n
d
Inserção



A árvore é percorrida top-down, a partir da raiz.
Em cada nível, verifica-se qual mbb contém o
mbb do objeto a ser inserido e desce naquela
sub-árvore
Caso não exista nenhum nó não folha que
contenha o objeto a ser inserido, então um nó é
escolhido para ter seu mbb estendido de forma
a conter o objeto a ser inserido. O nó escolhido
será aquele que precisa crescer menos seu mbb.
O processo é repetido até se encontrar um nó
folha.
Inserção


Se o nó folha não estiver cheio, uma nova
entrada [mbb, oid] é adicionada à página
associada com a folha. Observação: se houver
crescimento no mbb da folha, este deve se
progagar para cima na árvore.
Se o nó folha f estiver cheio, uma divisão de nó
ocorrerá: uma nova folha f’ é criada, e M+1
entradas são distribuidas entre f e f’.
Inserção
I
n
s
e
r
i
r
(
e
:N
o
d
o
)
b
e
g
i
n
/
/I
n
i
c
i
a
l
i
z
a
a
b
u
s
c
a
p
e
l
a
r
a
i
z
n
o
d
o
=
r
a
i
z
;
/
/E
s
c
o
l
h
a
u
m
c
a
m
i
n
h
o
d
e
s
c
e
n
d
o
p
a
r
a
f
o
l
h
a
w
h
i
l
e
(
n
ã
o
E
h
F
o
l
h
a
(
n
o
d
o
)
)
d
o
n
o
d
o
=
E
s
c
o
l
h
e
r
S
u
b
Á
r
v
o
r
e
(
n
o
d
o
,e
)
;
/
/
I
n
s
i
r
a
n
a
f
o
l
h
a
I
n
s
e
r
i
r
E
m
F
o
l
h
a
(
n
o
d
o
,e
)
;
/
/D
i
v
i
d
e
e
a
j
u
s
t
a
a
á
r
v
o
r
e
s
e
a
f
o
l
h
a
e
s
t
i
v
e
r
c
h
e
i
a
,
/
/s
e
n
ã
o
a
j
u
s
t
a
o
c
a
m
i
n
h
o
i
f
(
e
h
C
h
e
i
o
(
n
o
d
o
)
)
t
h
e
n
D
i
v
i
d
i
r
E
A
j
u
s
t
a
r
(
n
o
d
o
)
;
e
l
s
e
A
j
u
s
t
a
r
C
a
m
i
n
h
o
(
n
o
d
o
)
;
e
n
d
Inserção

A função EscolherSubÁrvore(node, e) pega a
entrada do node cujo node.mbb contém e.mbb
ou precisa de menor crescimento

A função AjustarCaminho(node) propaga o
crecimento do mbb para cima na árvore. Este
processo pára quando não precisar mais fazer
crescimento ou se alcançar a raiz. Esta função
está descrita a seguir.
Inserção
A
j
u
s
t
a
r
C
a
m
i
n
h
o
(
n
o
d
o
:
N
o
d
e
)
b
e
g
i
n
i
f
(
e
h
R
a
i
z
(
n
o
d
o
)
)
r
e
t
u
r
n
;
/
/
E
n
c
o
n
t
r
a
r
o
p
a
i
d
o
n
o
d
o
p
a
i
=
g
e
t
P
a
i
(
n
o
d
o
)
;
/
/
A
j
u
s
t
e
a
e
n
t
r
a
d
a
d
o
n
o
d
o
n
o
p
a
i
i
f
(
A
j
u
s
t
a
r
E
n
t
r
a
d
a
(
p
a
i
,
n
o
d
o
)
)
t
h
e
n
/
/
E
n
t
r
a
d
a
f
o
i
m
o
d
i
f
i
c
a
d
a
,
a
j
u
s
t
e
o
c
a
m
i
n
h
o
/
/
p
a
r
a
o
p
a
i
A
j
u
s
t
a
r
C
a
m
i
n
h
o
(
p
a
i
)
;
e
n
d
Inserção
D
i
v
i
d
i
r
E
A
j
u
s
t
a
r(
n
o
d
o
:N
o
d
e
)
b
e
g
i
n
/
/
C
r
i
a
u
m
n
o
v
o
n
o
d
o
e
d
i
s
t
r
i
b
u
ia
se
n
t
r
a
d
a
s
n
o
v
o
N
o
d
o
=
D
i
v
i
d
i
r
(
n
o
d
o
)
;
i
f(
e
h
R
a
i
z
(
n
o
d
o
)
)t
h
e
n
C
r
i
a
r
N
o
v
a
R
a
i
z
(
n
o
d
o
,n
o
v
o
N
o
d
o
)
;
e
l
s
e
/
/O
b
t
e
rp
a
id
o
n
ó
p
a
i=
g
e
t
P
a
i
(
n
o
d
o
)
;
/
/
A
j
u
s
t
a
re
n
t
r
a
d
a
d
o
n
o
d
o
e
s
e
u
sp
a
i
s
A
j
u
s
t
a
r
E
n
t
r
a
d
a
(
p
a
i
,n
o
d
o
)
/
/I
n
s
e
r
i
rn
o
v
o
n
o
d
o
n
o
p
a
i
I
n
s
e
r
i
r
N
o
d
o
(
p
a
i
,n
o
v
o
N
o
d
o
)
;
i
f(
e
h
C
h
e
i
o
(
p
a
i
)
)t
h
e
n
D
i
v
i
d
i
r
E
A
j
u
s
t
a
r
(
p
a
i
)
;
e
l
s
e
A
j
u
s
t
e
C
a
m
i
n
h
o
(
p
a
i
)
;
e
n
d
Inserção
 A função AjustarEntrada(pai, filho)
compara pai.mbb e filho.mbb. Se for
preciso o pai.mbb é estendido e a função
retorna TRUE, caso contrário retorna
FALSE
3.2.3 R-Tree
 Divisão de Nó



Para adicionar uma nova entrada a um nó cheio
é necessário dividir as entradas em dois nós
A divisão deve ser feita de modo que seja
improvável que ambos nós sejam examinados
em pesquisas subsequentes
Uma vez que a decisão de visitar um nó
depende se seu retângulo sobrepõe a área sendo
pesquisada, a área total dos dois retângulos
deve ser minimizada
3.2.3 R-Tree
Veja que a área do Bad Split é muito maior
do que a área de Good Split
Remoção
 A remoção é feita em 3 passos:




Encontrar o nodo folha F que contém a entrada
e
Remover e de F
Reorganizar a árvore se houver underflow.
Obs.: Uma abordagem simples na
reorganização é remover o nodo inteiro e reinserir as m-1 entradas restantes.
Remoção
R
e
m
o
ç
ã
o
(
e
:
O
b
j
e
t
o
)
b
e
g
i
n
/
/
E
n
c
o
n
t
r
a
r
a
f
o
l
h
a
c
o
n
t
e
n
d
o
e
F
=
E
n
c
o
n
t
r
a
r
F
o
l
h
a
(
e
)
;
/
/
R
e
m
o
v
e
r
e
n
t
r
a
d
a
s
e
r
e
o
r
g
a
n
i
z
a
r
á
r
v
o
r
e
/
/
o
r
e
s
u
l
t
a
d
o
é
u
m
c
o
n
j
u
n
t
o
d
e
n
o
d
o
s
Q
Q
=
R
e
o
r
g
a
n
i
z
a
r
(
F
,
e
)
;
/
/
R
e
i
n
s
e
r
i
r
a
s
e
n
t
r
a
d
a
s
d
o
s
n
o
d
o
s
d
e
Q
R
e
i
n
s
e
r
i
r
(
Q
)
;
e
n
d
Remoção
R
e
o
r
g
a
n
i
z
a
r
(
N
:n
o
d
o
,e
:o
b
j
e
t
o
)
:{
o
b
j
e
t
o
s
d
e
n
o
d
o
}
b
e
g
i
n
Q
=
{
}
;/
/c
o
n
j
u
n
t
o
d
e
n
o
d
o
s
/
/
R
e
m
o
v
e
r
e
d
e
N
N
=
N
-e
;
i
f
(
n
o
te
h
R
a
i
z
(
N
)
)
t
h
e
n
i
f
(
N
.
n
u
m
N
o
d
o
s
<
m
)
t
h
e
n
Q
=
Q
U
N
;
/
/O
b
t
é
m
o
p
a
ie
r
e
o
r
g
a
n
i
z
a
o
F
=
g
e
t
P
a
i
(
N
)
;
Q
=
Q
U
R
e
o
r
g
a
n
i
z
a
r
(
F
,e
n
t
r
a
d
a
d
e
N
e
m
F
)
e
l
s
e
/
/N
f
o
im
o
d
i
f
i
c
a
d
o
:a
j
u
s
t
e
o
c
a
m
i
n
h
o
A
j
u
s
t
a
r
C
a
m
i
n
h
o
(
N
)
;
e
n
d