UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 1

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 2

Representação de Objetos...

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 3

Representação Intensional...

P1 (x1, y1)

P2 (x2, y2)

P (x, y)(y-y2)/(y-y1) = (x-x2)/(x-x1) equação da reta

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 4

Representação Intensional

P (x, y)

P0 (x0, y0)

(x-x0)2 + (y-y0)2 = R2

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 5

• 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.

Trajetórias (caminhos) no espaço...

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 6

Trajetórias (caminhos) no espaço...

1212

77665544

332200 11

1313 1414 1515

88 99 1010 1111

1515

44556677

332200 11

1414 1313 1212

88 99 1010 1111

99

1212774422

665500 11

1010 1414 1515

33 88 1111 1313

99

44131312121111

332200 11

88 77 66

1010 1515 1414 55

I) Row Order II) Row Prime Order

III) Cantor-Diagonal Order IV) Spiral Order

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 7

• 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);

Trajetórias (caminhos) no espaço

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 8

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 9

• 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;

Space-filling Curves...

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 10

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 uni-dimensional;

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.

Space-filling Curves...

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 11

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 12

Passos Iniciais da Curva de Peano (N)

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 13

Passos Iniciais da Curva de Hilbert

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 14

A Chave de Peano

00 01 02 0300 01 10 11

decimal binary

00

01

02

03

X = 0 0 1 1 Y = 0 0 1 0

P = 0 0 0 0 1 1 1 0

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 15

Vide algoritmo à página 165 do Laurini

A Chave de Hilbert

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 16

• 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.

Space-filling Curves

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...

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 20

0

0 16

4

32 48

0 8 12

32 36 40 44

32 33 34 35 44 45 46 47

Quadtrees...

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 21

Quadtree Objects X Peano Keys

QUAD (Object_Id, QUAD (Object_Id, Peano_Key, Side_LengthPeano_Key, Side_Length))

UERJ - Março 2001 © Oscar Luiz Monteiro de Farias 22

Quadtree Space X Peano Keys