Representação de Objetos...
Intensão X Extensão
• Extensão - todos os dados pertencentes ao objeto são
armazenados
• Intensão - i) armazenamento de alguns elementos de dados
privilegiados do objeto;
ii) especificação de uma regra para gerar todos os possíveis
elementos do objeto;
iii) Definição de uma regra para testar se um elemento é
membro do objeto.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
1
Representação de Objetos...
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
2
Representação Intensional...
P (x, y)
(y-y2)/(y-y1) = (x-x2)/(x-x1)
equação da reta
P1 (x1, y1)
P2 (x2, y2)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
3
Representação Intensional
(x-x0)2 + (y-y0)2 = R2
P (x, y)
P0 (x0, y0)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
4
Trajetórias (caminhos) no espaço...
• Existem procedimentos para representar localizações
relativas em um espaço bidimensional (ou tridimensional
ou n-dimensional) em um sistema uni-dimensional.
• Há diferentes tipos de ordenamento.
• Propriedades desejáveis de um bom ordenamento
sequencial:
– A trajetória deve percorrer apenas uma vez cada célula do espaço
bidimensional (n-dimensional);
– células vizinhas no espaço bidimensional (n-dimensional) devem
ser vizinhas na trajetória;
– A trajetória deve ser factível, ainda que exista uma mistura de
células de diferentes tamanhos.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
5
Trajetórias (caminhos) no espaço...
I) Row Order
II) Row Prime Order
12
13
14
15
15
14
13
12
8
9
10
11
8
9
10
11
4
5
6
7
7
6
5
4
0
1
2
3
0
1
2
3
III) Cantor-Diagonal Order
UERJ - Março 2001
IV) Spiral Order
9
10
14
15
9
8
7
6
3
8
11
13
10
15
14
5
2
4
7
12
11
12
13
4
0
1
5
6
0
1
2
3
© Oscar Luiz Monteiro de Farias
6
Trajetórias (caminhos) no espaço
• Uma comparação de diferentes trajetórias (para um dado
nível de resolução) pode considerar:
– comprimento total da trajetória;
– variabilidade nas unidades de medidas, aonde a unidade de medida é
a distância de um ponto na trajetória para o próximo na seqüência;
– distância média de uma célula para os quatro vizinhos no espaço
(bidimensional);
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
7
Space-filling Curves...
• Trata-se de curvas fractais especiais que têm por
característica cobrir completamente uma área ou volume.
dx
0
dy
0
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
8
Space-filling Curves...
• Pode-se pensar em trajetórias como space-filling curves,
linhas que passam por todos os pontos no espaço (cada
ponto entendido aqui como um retângulo de dimensões
dx 0 , dy 0);
Propriedades das space-filling curves:
 A curva deve passar apenas uma vez em cada ponto do
espaço multi-dimensional;
 Dois pontos que sejam vizinhos no espaço devem ser
vizinhos na curva;
 Dois pontos que sejam vizinhos na curva devem ser vizinhos
no espaço;
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
9
Space-filling Curves...
Propriedades das space-filling curves:
 A recuperação dos vizinhos de um ponto deve ser fácil;
 A curva corresponde a um mapeamento bijetivo de um
espaço multi-dimensional para um espaço unidimensional;
 A curva deve ser passível de utilização com resolução
espacial variável, isto é, uma mistura de pontos de
diferentes tamanhos;
 A curva deve ser estável, ainda quando o espaço torna-se
muito grande ou infinito.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
10
A Curva de Peano
• Em 1890, o matemático italiano Giuseppe Peano
apresentou a primeira space-filling curve.
• Uma variedade, conhecida como a curva de Peano ou
N-Ordering facilita a recuperação de ontos vizinhos
• É possível tratar-se diferentes resoluções
• A curva é estável
• Na prática a codificação das space-filling curves usa uma
coordenada, chamada de chave (Peano key)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
11
Passos Iniciais da Curva de Peano (N)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
12
Passos Iniciais da Curva de Hilbert
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
13
A Chave de Peano
Y= 0 0 1 0
X= 0 0 1 1
P= 0 0 0 0 1 1 1 0
03
02
01
00
00
00
UERJ - Março 2001
01
01
02
10
03
11
© Oscar Luiz Monteiro de Farias
decimal
binary
14
A Chave de Hilbert
Vide algoritmo à página 165 do Laurini
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
15
Space-filling Curves
• Normalmente as space-filling curves são auto-similares,
isto é, qualquer parte da mesma, quando ampliada, não se
distingüe do objeto como um todo.
• As space-filling curves têm duas utilizações principais em
sistemas de informação espaciais:
– eficiência em operações de varredura (em hardware ou em
operações de pesquisa em arquivos)
– são usadas como índices espaciais, simplificando o endereçamento
bidimensional em um endereçamento uni-dimensional.
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
16
Quadtrees...
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
17
Quadtrees...
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
18
Quadtrees...
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
19
Quadtrees...
0
0
16
32
32
0
4
8
40
44
12
32
UERJ - Março 2001
36
48
33
34
35
© Oscar Luiz Monteiro de Farias
44
45
46
47
20
Quadtree Objects X Peano Keys
QUAD (Object_Id, Peano_Key, Side_Length)
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
21
Quadtree Space X Peano Keys
UERJ - Março 2001
© Oscar Luiz Monteiro de Farias
22