II – ELEMENTI DI MATEMATICA Capitolo 2° ELEMENTI DI ... · • 2.4 – Introduzione alla...

Architettura dei Database Territoriali Pr. R. Laurini

Cap 2°: Elementi di Matematica 1

Capitolo 2°

ELEMENTI DI MATEMATICA

II – ELEMENTI DI MATEMATICA

• 2.1 – Euclide, Cartesio, Eulero, Peano, Mandelbrot

• 2.2 – Tessellazioni regolari e irregolari

• 2.3 – Geometria computazionale

• 2.4 – Introduzione alla geometria frattale

• 2.5 – Conclusioni

2.1 – Euclide, Cartesio, Eulero, Peano, Mandelbrot

• Visioni matematiche dello spazio

• Definizione: modo di vedere la struttura e l’organizzazione degli oggetti nello spazio

• Geometria (etimologicamente): misura dellaterra

Visione euclidea

• Oggetti nel piano o nello spazio• Oggetti perfetti (cerchi, quadrati, ecc.)• Poligoni conosciuti attraverso i loro vertici• Particelle = poligoni• Unità di lunghezza e di superficie• Perimetro, superficie• Studio degli oggetti isolati



Oggetti euclidei Visione cartesiana

• Assi 2D et 3D (mosca volante)

• Coordinate (x, y, z)

• Posizione relativa degli oggetti nello spazio

• Necessità di un sistema di riferimento

Y

X

X

Y

Z

2D

3D

O

O

Visione peaniana

• Giuseppe Peano

• Definizione di un punto, di una linea, ecc.

• Esistono punti a 2D, a 3D

• Curve che empiono lo spazio

• Pixel = quadratino, o punto ?



Oggeti peaniani Visione frattale

• Creata da Benoît Mandelbrot

• Il modello euclideo è insufficiente per glioggetti naturali (fiume, colline, isole, ecc.)

• Oggetti limitati da piccolissimi segmenti

• Visione ricorsiva e stocastica

Il fiocco di Koch2.2 – Tassellazioni regolari e

irregolari

• Pavimenti, nidi d’ape

• Ripetizioni iterative

• Grammatica di forme iterative



Tassellazioni regulari 2.3 – Geometria computazionale

• Operazioni su punti, linee e segmenti

• Appartenenze

• Operazioni sui poligoni

Operazioni su punti, linee e segmenti

• Intersezione di linee e di segmenti

• Generalizzazione di linee

Rappresentazione

• Punto : x, y oppurex, y, z, spesso, x, y, z, t

• Segmenti : insieme di punti localizzati suuna linea limitata da due estremità==> rappresentazione in intensione

equazione parametrica :

x = xa +u× (xb-xa)

y = ya +u× (yb-ya)Con o ≥ u ≥ 1



Rappresentazione dei segmenti

x

y

x

y

A

B

u=0

u=1

t>1

u<0

0<u<1

Origine Origine

Rappresentazioneparametrica

Rappresentazionecon le estremità

B(xb,yb)

A(xa,ya)

Generalizzazione di una polilinea

Linea originale Linea generalizzata

Punti di cui distanza è inferiorea una soglia

Appartenenza

• R : y=3x+2• Esatta :

– (x=0, y=2)

• Approssimativa– (x=0, y=1.9999999999999999)

• Problemi dei pixels: si clica nel centro del pixel, ma la retta non passa esattamente nelcentro del pixel

X

Y

Cerchio :Se (x-x0)2 + (y-y0)2 - R2 = 0 allora sul cerchio(impossibile informaticamente)

Se (x-x0)2 + (y-y0)2 - R2 > 0 allora esternoSe (x-x0)2 + (y-y0)2 - R2 < 0 allora interno

0 x0

y0R

Appartenenza di un punto a un cerchio



Appartenenza di un puntoa un rettangolo

X

Y

xmin xmax

ymin

ymax

Rettangolo :Se (xmin<x<xmax) and (ymin<y<ymax) allora interno

Se (x<xmin) or (x>xmax) or (y<ymin) or (y>ymax) allora esterno

Appartenenza di un punto a un poligono qualsiasi

• Caso semplice– Rettangoli con i lati paralleli agli assi

• Caso comune– Poligono connesso

• Caso generale– Poligono con buchi ed isole– soluzione : teorema della semi-retta di Jordan

Appartenenza di un punto a un poligono: teorema di Jordan

punto candidato

1

21

1 2 3 4 5

1 2

0

1

3

4

2 3 41

semi-retta

numero delle intersezionicon i lati

Un punto è interno se il numero delle intersezioni è dispariUn punto è esterno se il numero delle intersezioni è pari

Operazioni sui poligoni

• Rettangolo minimo (MBR)

• Unione, intersezione, differenza

• Calcolo della superficie

• Rubber-sheeting



Rettangolo minimo

ymin

ymax

xminxmax

Rettangolo minimodi un poligono

Poligono

X

Y

Unione ed intersezione didue poligoni

Poligono A

Due poligoni A et B Unione di A e B Intersezione di A e B

Poligono B

Taglio di due poligoni in fette parallele

Poligono A

Poligono B

Metodo delle fette per determinarel'unione e l'intersezione di due poligoni

INTER-SEZIONE

UNIONEPOLIGONI FETTATI



Calcolo della superficie diun triangolo

• Superficie di ogni triangolo con il prodottovettoriale

V2

V1

V3 = V1 ∧ V2

O

)]()()()[(2

101020201 yyxxyyxxST −×−+−×−=

Calcolo della superficie di un poligono qualsiasi

• Taglio in triangoli

S x y x y x y x yi i i i n n

i

i n

= − + −+ +

=

= −

∑12 1 1 1 1

1

2

( ( )) ( )

�

Rubber-sheeting

Mappainiziale

Nuovamappa

Puntidi controlloda muovere

Puntifissi

2.4 – Introduzione alla geometriafrattale

• Presentazione di alcuni oggetti frattali

• Benoît Mandelbrot

• Forme ricorsive (autosimilarità)

• Frattali stocastici



Esempio

• Ripetizioni ricorsive

• Iniziatore

• Ripetitore

Curva di Koch : tappe iniziali

Il fiocco di Koch Generatore d’isole

Iniziatore Ripetitore

Punto di partenza Prima tappa Seconda tappa



Polvere di Cantor e oggetti derivati

Pettine di Cantor

Collana di Cantor Città di Cantor

Polvere di Cantor

Altri oggetti frattaliCurva di Levy Dragone di Heighway

Tappetto di SierpinskiPolvere di Cantor

Frattali stocastici

• Variazioni aleatorie

• Terreni

• Piante

• ecc.

Spostamento aleatoriodel medio di un segmento

Segmentodi partenza

1a tappa

2a tappa

3a tappa



Metodo d'interpolazionestocastica dei terreni

A B

C D

E F

G

I

H

Procedura

Prima tappa Seconda tappa

Parecchie fasi

Dan Connellyhttp://www.flash.net/~djconnel/Vue/ Curve di Peano

• Definizione e proprietà elementari

• Curve che empiono lo spazio

• Curve che passano ad ogni punto dellospazio

• Curva di Hilbert, e in N di Peano

• Codifica delle chiavi sulle curve



Fasi inizialidella curva di Hilbert

Fasi inizialidella curva in N di Peano

Ottenimento delle chiave diPeano con bit alternati

0 0 1 1 0 0 1 0

0 0 0 0 1 1 1 0

X = Y =

P =

(x = 3) e (y = 2) => p = 14

Cifre dopo la virgola

(x = 1,5) e (y = 1,0) => p = 3,5

0 0 1 1 0 0 1 0

0 0 0 0 1 1 1 0

X = Y =

P =



Ordine in N di Peano

0

1

2

3

4

5 7 13 15

6 12 14

119

8 10

0

1

2

3

4

0 1 2 3 4

16

Ordine di Hilbert

0

1

2

3

4

0 1 2 3 4

0 1

23

4

5 6

7 8

9 10

11

1213

14 15

2.5 – Conclusioni

• Importanza delle geometrie euclidea, peanianae frattale

• Uso per gli algoritmi

• Uso per la modellistica dei dati spaziali

• Uso per l'indicizzazione spaziale (ORACLE)

II – ELEMENTI DI MATEMATICA Capitolo 2° ELEMENTI DI ... · • 2.4 – Introduzione alla...

Documents

Transcript of II – ELEMENTI DI MATEMATICA Capitolo 2° ELEMENTI DI ... · • 2.4 – Introduzione alla...