Tesi di laurea: ingegneria elettrica

P̃ P̃

1 2 n 1 2 n ′

del disco unitario utilizzando i due insiemi di prevertici. Allora e sono simili, cioè

P̃ P̃

coincidono a meno di una traslazione, una rotazione ed un cambiamento di scala.

Siamo ora pronti ad illustrare l’algoritmo CRDT nei suoi passi fondamentali.

Indichiamo ancora con il

1. Aggiunta di vertici e suddivisione del poligono. P

poligono ottenuto dopo tale operazione; sia n il numero complessivo dei vertici z .

k

Possiamo quindi ordinare le diagonali ed i quadri-

2. Triangolazione di Delaunay di P.

lateri della triangolazione; definiamo

c = ln(|ρ(z , z , z , z )|) i = 1, ..., n − 3 (3.7)

i k(i,1) k(i,2) k(i,3) k(i,4)

In generale tali rapporti in croce sono dei numeri complessi, quindi il segno di valore

assoluto indica la loro ampiezza. n−3 n−3

= La funzione : R → R è

3. Risoluzione del sistema non lineare F(σ) 0. F

definita nel modo seguente: indicate con ζ le immagini di una disposizione di prevertici,

k

con le notazioni della (3.6) scriviamo:

F (σ , ..., σ ) = ln(|ρ(ζ , ζ , ζ , ζ )|) − c i = 1, ..., n − 3

i 1 n−3 i

k(i,1) k(i,2) k(i,3) k(i,4)

Fissate le σ , come visto, è individuato a meno di una similitudine. Per ogni i dob-

P

i

biamo dunque trovare i quattro vertici ζ , ..., ζ : per questo costruiamo un’op-

k(i,1) k(i,4)

portuna disposizione D di prevertici. Dal teorema 3.2 sappiamo che dato σ possiamo

i

disporre a piacere tre prevertici t , t , t , e lo facciamo in modo tale che,

k(i,1) k(i,2) k(i,3)

una volta trovato t , questi quattro punti siano disposti su un rettangolo centrato

k(i,4)

nell’origine e con opportuno rapporto in croce. Allora, utilizzando il teorema 3.1, di-

sponiamo i prevertici rimanenti per completare D . Questa disposizione definisce una

i

trasformazione f , cioè la (3.1) con a = 0 e c = 1, che utilizziamo per calcolare i vertici

i

immagine ζ , ..., ζ . Nel punto ove = si ha:

F(σ) 0

k(i,1) k(i,4)

|ρ(ζ , ζ , ζ , ζ )| = |ρ(z , z , z , z )|, i = 1, ..., n − 3

k(i,1) k(i,2) k(i,3) k(i,4) k(i,1) k(i,2) k(i,3) k(i,4)

Questo poligono è proprio quello cercato:

Sia un poligono limitato e triangolato di n vertici. Allora è

Teorema 3.3 P P

determinato in modo univoco, a meno di una similitudine:

dalla sequenza degli angoli interni ai vertici e

1. dagli n − 3 valori assoluti dei rapporti in croce relativi ai quadrilateri determinati

2. dalla triangolazione di P.

La risoluzione di = è il punto cruciale dell’ algoritmo. Utilizzando il metodo di

F(σ) 0

Newton si ha: (0)

 σ = c



 (k) ′ (k)

= 0 ≃ ) + ∆σ

F(σ) F(σ F −1

(k+1) (k) (k) (k) ′ (k)

 σ = σ + ∆σ = σ − (F ) )

F(σ

 39

Capitolo 3 - La trasformazione numerica

ove è il vettore dei c sopra definito. Esperimenti mostrano come in realtà basti una

c i

semplice iterazione lineare: (k+1) (k) (k)

σ = σ − ) (3.8)

F(σ

cioè la Jacobiana sembra essere sempre prossimo alla matrice identità. Sembra inoltre

(k+1) (k+1)

che le iterazioni soddisfino sempre la relazione ||F(σ )|| ≤ α||F(σ )|| , ove α

2 2

dipende dal problema, ma è sempre α < 1. La convergenza ”pulita” della (3.8) lascia

supporre che sia fortemente monotona: ci si aspetta quindi che ||F|| non abbia

F 2

minimi locali e che sia iniettiva. La convergenza della (3.8) è però in pratica troppo

F

lenta: viene quindi utilizzato per la risoluzione il pacchetto NESOLVE già descritto in

questo capitolo. Quando = sappiamo

4. Calcolo delle costanti della trasformazione affine. F(σ) 0,

che la trasformazione f applicata ai prevertici del quadrilatero Q nella disposizione D

i i i

′

produce un quadrilatero Q simile a Q . Due punti di ciascun quadrilatero definiscono

i

i

la trasformazione fra essi, cosı̀ ora è possibile risolvere un sistema lineare o un problema

di minimi quadrati per trovare le costanti a e c che compaiono nella (3.1). Questo

i i

completa la trasformazione da D a P.

i

Osserviamo che il CRDT essenzialmente calcola simultaneamente n−3 trasformazioni dal di-

sco verso vediamo ora come ciascuna trasformazione sia localmente accurata in una parte

P;

del poligono. Se contiene parti strette ed allungate, allora per ogni possibile posiziona-

P

mento dei prevertici alcuni di essi saranno estremamente addensati, ma un posizionamento

D per il calcolo di f assicura che non lo saranno certi t , ..., t , nè fra di loro nè

i i k(i,1) k(i,4)

rispetto agli altri prevertici; pertanto il crowding non ha alcuna influenza sull’accuratezza

della quadratura per questi prevertici, in quanto il cammino d’integrazione non passa vicino

ai prevertici addensati. Sfruttando questo fatto è possibile aggirare globalmente il crowding.

In figura 3.8 è mostrato un poligono triangolato con due quadrilateri distinti le cui diago-

Figura 3.8: due distinte disposizioni dei prevertici

nali sono indicate con linee tratteggiate; nessuna disposizione dei prevertici è non affetta da

crowding: al centro ne vediamo una dove i prevertici del primo quadrilatero (segnati con cer-

chietti) sono ben distanziati, mentre quelli dell’altra (segnati con triangoli) sono fortemente

addensati attorno ad un punto, troppo vicini per essere distinti; sulla destra la situazione è

rovesciata.

Vediamo per finire come utilizzare insieme le disposizioni D per trasformare i punti

i

dal disco. Ricordiamo che ogni trasformazione conforme dal disco unitario in se stesso è

frazionaria del tipo: z − r

(iθ)

g(z) = e 1 − rz 40

Capitolo 3 - La trasformazione numerica

ove r è un numero complesso con |r| < 1 e θ ∈ [0, 2π). Come conseguenza, esiste un’unica

trasformazione di questo tipo che trasforma tre punti distinti sulla circonferenza unitaria in

altri tre punti conservandone l’ordinamento.

Diciamo che due quadrilateri Q e Q della triangolazione di sono adia-

Definizione 3.4 P

i j

centi quando hanno tre vertici in comune. Se D e D sono le disposizioni relative a tali

i j

quadrilateri, anch’esse si dicono adiacenti.

Come si vede, quadrilateri adiacenti sono parzialmente sovrapposti. La disposizione D for-

i

nisce una trasformazione corretta in Q ; se Q è adiacente a Q allora questi hanno in comune

i i j

tre vertici e quindi tre prevertici, consentendo di calcolare la trasformazione frazionaria g fra

D e D . Ancora, poichè i prevertici di un quadrilatero sono ben distanziati nella propria

i j

disposizione, la g può esser calcolata con grande accuratezza.

Il primo passo è quello di scegliere una particolare disposizione di riferimento del disco in

cui specificare i punti: per questo si fissa t = 1 ed il centro della trasformazione z = f (0);

n 0

ciò in sostanza equivale a fissare i tre gradi di libertà e, implicitamente, a scegliere una

disposizione per i prevertici. Sia ora Q un quadrilatero che contiene z : possiamo invertire

k 0

numericamente la trasformazione affine f definita da a e b per trovare la controimmagine

k k k

t di z in D . Poichè D è associato ad una trasformazione localmente accurata per Q , ci

0 0 k k k

aspettiamo che t non sia troppo vicino al bordo del disco; ora, assegnato un punto t nella

0

disposizione di riferimento, è possibile calcolare la sua immagine nella disposizione D e da

k

qui le sue immagini in tutte le disposizioni adiacenti a D . Il procedimento è continuato

k

in modo iterativo finchè gli equivalenti di t sono noti in tutte le disposizioni. A questo

punto ogni D può essere in linea di principio utilizzato per calcolare l’immagine di t, ma dal

i

momento che, presumibilmente, ogni trasformazione locale è più accurata vicino all’origine,

si sceglie la disposizione in cui l’equivalente di t è minore in ampiezza.

La trasformazione inversa è analoga: dato z ∈ si inverte z numericamente in una

P

disposizione corrispondente ad un quadrilatero contenente z; quindi si trasforma questa

controimmagine attraverso disposizioni adiacenti a D , e da qui a quella di riferimento.

k

Mappe rettificate

Per molte applicazioni con regioni allungate, il disco unitario non è il dominio fondamentale

ideale, anche se si è in grado di calcolare la trasformazione con precisione: ad esempio, se

si vuole generare un reticolo ortogonale utilizzando il disco si devono trasformare punti che

si avvicinano esponenzialmente al suo bordo per ottenere le linee di campo dentro le parti

allungate.

In alternativa, supponiamo di conoscere una disposizione dei prevertici per il poligono: se

manteniamo tali prevertici e cambiamo gli angoli della trasformazione, ne risulterà un nuovo

poligono conformalmente equivalente a quello originario, essendo ad esso correlato da una

trasformazione inversa e da una diretta. Una scelta conveniente è scegliere questi nuovi angoli

interni α multipli interi di π/2: il poligono rettificato risultante, a meno di una rotazione,

k

avrà ogni lato parallelo ad uno degli assi, e si parla in questo caso di una mappa di Schwarz-

Christoffel rettificata. In un tale poligono è banale trovare un reticolo ortogonale. Da notare

che, una volta specificati gli angoli, si perde il controllo sulla lunghezza dei lati, a meno di

un cambiamento di scala (nel caso importante in cui quattro a sono π/2 e tutti gli altri π

k

il poligono rettificato è un rettangolo); le lunghezze dei lati del poligono rettificato vengono

determinate durante la ricerca delle trasformazioni affini per i raggruppamenti dell’algoritmo 41

Capitolo 3 - La trasformazione numerica

CRDT. Essendo possibile scegliere in più modi diversi gli angoli del poligono rettificato, il

procedimento non è stato automatizzato e vanno quindi forniti dall’utente; l’unico vincolo

per essi rimane α = −2π.

P j

In figura 3.9 è mostrato un quadrilatero che presenta numerose frastagliature (segmenti

blu) al suo interno, e le immagini in esso di alcune linee di campo da un rettangolo di lati

1 e 8,65 circa (il poligono rettificato). Le linee piene (in verde) sono le immagini di linee di

campo ben distanziate dai lati lunghi del rettangolo, e si mantengono lontane dalle ”anse”

del quadrilatero; le linee tratteggiate (in rosso) hanno invece controimmagini estremamente

−2 −4 −6

vicine ai lati lunghi del rettangolo (10 , 10 e 10 , sebbene sia possibile andare molto

oltre) e seguono da vicino i bordi del ”labirinto”. Attualmente, nessun altro algoritmo riesce

a calcolare tali curve con una simile precisione.

2

1.5

1