Ray-Tracing e Modelli Ambientali Capitolo 3

Capitolo 3

Ray-Tracing e Modelli Ambientali

Come descritto nel capitolo 2 il contributo GTD al campo totale è calcolato come somma dei campi associati con i raggi che raggiungono il punto di osservazione. In ambienti complessi, come scenari 3D, la principale difficoltà dell’applicazione GTD è di risolvere il ray-tracing, che consuma la maggior parte del tempo di calcolo. Tuttavia, l’efficienza del tool che sfrutta la GTD dipende altamente dal simulatore ray-tracing. Questo capitolo descrive una tecnica di ray-tracing utilizzata per la creazione di un modello di propagazione deterministica basato sulla GTD. Prima è presentato un metodo adeguato per modellare tali ambienti: il modello a facce. Poi, è analizzato il modello che abbiamo creato e implementato in C++ per lo studio 2D di uno scenario. Questo modello è stato utilizzato nel tool di predizione della propagazione da noi sviluppato descritto nel capitolo 4. Successivamente si discuterà del problema della visibilità tra due punti, infine verrà mostrato un algoritmo rigoroso per ottenere il ray-tracing.

3.1 – Descrizione Geometrica e Morfologica di un Ambiente

1) descrizione geometrica della scena;

2) descrizione morfologica della scena, cioè proprietà dei materiali costituenti gli oggetti presenti in essa.

3.1.1 – Descrizione Geometrica

Da un punto di vista geometrico i tipici scenari di microcelle e picocelle sono abbastanza complessi poiché sono coinvolti un gran numero di oggetti differenti sia fermi come edifici, lampioni, cabine telefoniche, alberi, che in movimento come persone e autoveicoli. Ognuno di questi è coinvolto nel fenomeno della radio propagazione sebbene con una differente influenza. Come conseguenza, senza semplificazioni è impossibile simulare la radio propagazione in tali ambienti anche ricorrendo a metodi elettromagnetici approssimati. Quindi, solitamente i dati disponibili non contengono informazioni relative agli oggetti più piccoli.

Dunque, il livello di dettaglio nei modelli geometrici deve essere in relazione ai dati disponibili e all’approccio elettromagnetico usato.

In molti casi, le sole informazioni disponibili sugli edifici riguardano le loro pareti esterne (forma geometrica e posizione), a volte includono anche informazioni relative ai materiali interni alle pareti. Questo potrebbe essere sufficiente per una predizione della propagazione outdoor ma non per una predizione indoor, che richiede l’ausilio di informazioni sulla struttura interna all’edificio (muri, piani, porte, finestre). I dati riguardanti il terreno devono essere sempre tenuti in considerazione in modelli geometrici outdoor, specialmente in piccoli ambienti urbani e in aree collinari

dove il terreno non può essere assunto piatto. In altri casi, come in microcelle e picocelle il terreno può essere considerato piatto.

I dati su edifici e terreni possono essere ottenuti negli uffici comunali o nelle sedi di provincia e regione, da planimetrie disegnate o da files creati allo scopo.

3.1.2 – Modelli Morfologici

Le proprietà riflettenti di terreno e materiali costituenti superfici di edifici devono essere considerate in funzione dell’accuratezza delle predizioni. Esse possono essere ottenute da misure [18, 28] o possono essere calcolate [27, 29] da proprietà elettriche e rugosità dei materiali corrispondenti. Le proprietà elettriche sono:

• Permittività relativa, ; ε_r • Permeabilità relativa, ; µ_r • Conducibilità, ; σ

Tabelle di proprietà elettriche di materiali possono essere trovate in letteratura [18, 20, 30]. Esse variano con la frequenza. Come esempio, parametri elettrici tipici a 1.8 GHz per comuni superfici esterne di edifici sono [18]:

Calcestruzzo: ε = 6.5, µ = 0.95, σ = 0.01 S/m_{r r} , Mattone: ε = 4.26, µ = 1.03, σ = 0.01 S/m_{r r} ,

Pietra calcarea: ε = 0.21, µ = 0.006, σ = 0.03 S/m_{r r} .

Queste proprietà caratterizzano superfici lisce. Per tener conto della rugosità di certe superfici dovrebbe essere incluso nel modello un parametro di rugosità σ . Poiché l’inserimento di questa caratteristica complica di molto le espressioni utilizzate nel calcolo del campo elettrico (presentate nel capitolo 2) senza apportare un sostanziale aumento della precisione nella predizione della propagazione, noi consideriamo come lisce tutte le superfici coinvolte nell’ambiente in analisi.

3.2 – Modelli a facce

Per inserire informazioni geometriche e morfologiche in un tool di propagazione, è necessario presentare in una forma opportuna le informazioni ambientali costituite da dati relativi ad entità geometriche come linee e poligoni. Per far questo, deve essere sviluppato un database per immagazzinare e gestire i dati richiesti.

Nel database, terreni ed edifici sono immagazzinati usando un modello a facce, ovvero, le loro superfici sono modellate con facce piane poligonali. Di solito ogni parete di un edificio è rappresentata da un quadrilatero. I tetti sono modellati da facce con un numero arbitrario di lati. Il numero di facce usate per modellare il terreno dipende dalla grandezza della scena e dall’orografia dell’ambiente. In scenari piani una sola faccia può essere sufficiente per modellare il terreno. Quando le informazioni circa porte e finestre sono disponibili, esse possono essere adeguatamente modellate come facce con corrispondenti proprietà morfologiche.

Nel database i dati immagazzinati includono le seguenti quantità: • Numero di facce;

• Numero di vertici di ciascuna faccia;

• Coordinate cartesiane dei vertici di ciascuna faccia;

• Tipo di materiale; il tipo di materiale è assegnato a ciascuna faccia come un attributo.

X Y

Z

Come esempio, la figura 3.1 mostra una semplice scena outdoor con un edificio. Il modello contiene sei facce: quattro per le pareti laterali, una per il tetto, una per il terreno. La tabella 3.1 mostra come i dati sono sistemati nel database. I dati in questa tabella forniscono le informazioni base sul modello a facce.

Faccia No.Ver Materiale X-coords Y-coords Z-coords

1 4 Mattone 5.0 5.0 4.0 4.0 7.0 7.0 7.0 7.0 0.0 3.0 3.0 0.0 2 4 Mattone 5.0 5.0 5.0 5.0 7.0 8.0 8.0 7.0 0.0 0.0 2.0 3.0 3 4 Mattone 5.0 4.0 4.0 5.0 8.0 8.0 8.0 8.0 0.0 0.0 2.0 2.0 4 4 Mattone 4.0 4.0 4.0 4.0 8.0 7.0 7.0 8.0 0.0 0.0 3.0 2.0 5 4 Tegola 5.0 5.0 4.0 4.0 7.0 8.0 8.0 7.0 3.0 2.0 2.0 3.0 6 4 Asfalto 0.0 8.0 8.0 0.0 0.0 0.0 15.0 15.0 0.0 0.0 0.0 0.0

Tabella 3.1 – Dati relativi ai Materiali e Coordinate delle Facce di Figura 3.1

Tuttavia i database solitamente contengono altri tipi di dati molto utili per i modelli di propagazione:

• Numero di edifici;

• Numero di facce di ciascun edificio (pareti laterali e tetto); • Numero di facce da pavimento a soffitto;

• Tipo di faccia (questo indica se la faccia appartiene al terreno, a un muro, a un tetto etc.).

Spesso è vantaggioso aggiungere dei dati geometrici che saranno usati dal tool di propagazione con una certa frequenza. Queste informazioni possono essere ottenute dalla descrizione di ogni faccia e solitamente includono il vettore normale a ciascuna faccia e la topologia della faccia. L’informazione sulla topologia di una faccia consiste nel sapere quante e quali facce sono a lei connesse; questa informazione è ricavata

dallo spigolo a comune. Il numero di facce connesse ad una data faccia deve essere in accordo con il numero di vertci di quest’ultima.

La tabella 3.2 mostra come questi dati relativi al modello di figura 3.1 sono sistemati nel database.

Faccia _{Topologia Vettore Normale}

1 2,5,4,6 0.0, -1.0, 0.0 2 6,3,5,1 1.0, 0.0, 0.0 3 6,4,5,2 0.0, 1.0, 0.0 4 6,1,5,3 -1.0, 0.0, 0.0 5 2,3,4,1 0.0, 0.7071, 0.7071 6 0,0,0,0 0.0, 0.0, 1.0

Tabella 3.2 – Dati relativi a Topologia e Vettori Normali delle facce di Figura 3.1

Le informazioni menzionate fino a qui riguardano le facce, ma anche gli spigoli del modello possono giocare un importante ruolo nel fenomeno della propagazione (vedi cap.2). Gli spigoli del modello nascono dalla connessione di una coppia di facce. Uno spigolo è definito dai suoi estremi, dalla coppia di facce che lo genera e dall’angolo tra queste due facce.

La tabella 3.3 mostra come i dati degli spigoli di figura 3.1 sono immagazzinati nel database. Queste informazioni possono anche essere ottenute indirettamente dal modello a facce di base. Per far questo deve essere seguita una regola fondamentale: un confine di una faccia (uno spigolo) non può essere condiviso da più di due facce.

Come menzionato precedentemente, il database contiene informazioni tridimensionali (3D) dell’ambiente. Spesso sono messi a disposizione dalla sorgente di

informazione solo dati 2D (planimetrie, proiezioni ortogonali sul piano orizzontale), in questi casi, in modelli outdoor, il terreno è assunto piatto e può essere scelta un’altezza approssimata per tutte le costruzioni in gioco per ottenere un modello a facce.

Spigoli Facce Angolo X-coords Y-coords Z-coords

1 1, 2 90.0 5.0 5.0 7.0 7.0 0.0 3.0 2 2, 3 90.0 5.0 5.0 8.0 8.0 0.0 2.0 3 3, 4 90.0 4.0 4.0 8.0 8.0 0.0 2.0 4 4, 1 90.0 4.0 4.0 7.0 7.0 0.0 3.0 5 1, 5 45.0 5.0 4.0 7.0 7.0 3.0 3.0 6 2, 5 90.0 5.0 5.0 7.0 8.0 3.0 2.0 7 3, 5 135.0 5.0 4.0 8.0 8.0 2.0 2.0 8 4, 5 90.0 4.0 4.0 8.0 7.0 2.0 3.0

Tabella 3.3 – Dati relativi agli Spigoli della scena di Figura 3.1

Come altri autori [31] abbiamo deciso di lavorare direttamente su modelli 2D per facilitare l’applicazione del modello di radio propagazione.

3.3 – Creazione e Implementazione C++ di un modello per la

descrizione 2D di uno scenario

La scelta di utilizzare un modello per descrivere attraverso due sole dimensioni uno scenario non dipende solo dal fatto di poter utilizzare una mappa 2D come sorgente di informazione e magari la stessa mappa modificata per la presentazione dei risultati di predizione. Innanzitutto comporta:

• La rappresentazione di un ambiente visto dall’alto, cioè sul piano orizzontale. Questa è un’ottima scelta per studiare ambienti indoor costituiti da stanze appartenenti allo stesso piano di un edificio e una buona scelta per l’analisi di scene outdoor che possono contenere strutture con molti piani (palazzi, grattacieli, opere d’arte).

• Tutti i punti coinvolti si trovano alla stessa altezza. Anche un’antenna trasmittente e una ricevente (che identifica un punto su cui vogliamo calcolare la potenza ricevuta) si trovano alla stessa altezza che è quella dei punti costituenti la forma dello scenario.

• La descrizione di un qualsiasi punto attraverso due sole coordinate X e Y. Questo perché l’aggiunta di un’ulteriore componente uguale per tutti i punti sarebbe inutile.

• Una faccia 2D è modellata con un segmento, quindi ha una descrizione base costituita da due vertici di due coordinate ciascuno (anziché da quattro vertici di tre coordinate ciascuno come nel caso 3D).

• Gli spigoli considerati sono solo quelli verticali che sul piano orizzontale appaiono come semplici punti, quindi individuati solo da una coppia di coordinate.

Inoltre, per quanto riguarda i raggi che si originano, essi giacciono tutti sul piano orizzontale quindi alcuni effetti non possono essere implementati come:

• Diffrazioni dai tetti e da tutti gli spigoli non verticali. • Riflessioni da terreno e soffitti.

Da quanto detto fin’ora emerge che i database costruiti con modelli 2D sono più semplici, ovvero la descrizione di uno stesso ambiente contiene una minore mole di dati rispetto alla descrizione 3D.

Insieme a questo vantaggio, occorre però dire che rispetto ai tools che si basano su modelli ambientali 3D nasce una minore precisione nella nostra predizione. In realtà, come mostreremo nella sezione 4.3 i nostri risultati trovano un’efficace

validazione in quanto la perdita di precisione suddetta è trascurabile a fronte di un’elevata riduzione dei tempi di simulazione.

Il modello per la descrizione 2D di uno scenario così come l’algoritmo di ray-tracing sono stati implementati utilizzando il linguaggio di programmazione C++.

Per caratterizzare ogni faccia in 2D (quindi ogni segmento), abbiamo utilizzato una struttura chiamata segment formata da diversi campi. I più significativi affiancati da una breve descrizione sono i seguenti:

short nus; numero identificativo del segmento.

short nua; numero identificativo del segmento accoppiato a quello in esame.

short dif; dif=0,(1) lo spigolo di questo segmento non produce (produce) diffrazione. short rif; rif=0,(1) questo segmento non produce (produce) riflessione una o molteplici. double spessore; spessore formato da questo segmento con quello accoppiato.

double V1xy[2]; ascissa e ordinata del vertice1 del segmento (rispetto al sistema di assi xy). double V2xy[2]; ascissa e ordinata del vertice2 del segmento (rispetto al sistema di assi xy). struct can=fin retta generica, y=ax+b passante per V1-V2.

{coeffang can; can=inf retta||assey, a non è settato e b è l'ascissa dei punti

double a, b; } retxy; appartenentialla retta x=b.

short tplgy[2]; contiene gli nus dei segmenti a lui consecutivi precedente e seguente. double nv[2]; contiene il vettore normale al segmento.

struct

{short numater;

double epsilon_r, sigma; } material;

La struttura retxy dentro la struttura segment serve per identificare la retta che contiene il segmento, retta sul piano xy di equazione y=ax+b. La quantità can di tipo coeffang può valere fin o inf. Si tratta del coefficiente angolare della retta che può essere finito (per una retta generica) o infinito (per una retta parallela all’asse y). L’introduzione di can serve per evitare divisioni per zero.

La struttura material dentro segment serve per caratterizzare le proprietà morfologiche della faccia. In particolare numater è il numero identificativo del materiale. Nel nostro modello abbiamo scelto 14 materiali diversi che è possibile attribuire ad una faccia. Essi sono stati scelti tra quelli che possono comporre gli elementi presenti in ambienti indoor e outdoor. Per visionarli, qui di seguito è riportato uno switch del programma in cui ad ogni segmento sono assegnate proprietà elettriche (permittività relativa e conducibilità in [S/m]) al variare del numero identificativo (numater) che gli è stato precedentemente assegnato.

switch (cnf[i].material.numater)

{case 1: cnf[i].material.epsilon_r=15; //Acciaio cnf[i].material.sigma=1.1e6; break;

case 2: cnf[i].material.epsilon_r=1; //Alluminio cnf[i].material.sigma=3.94e7; break;

case 3: cnf[i].material.epsilon_r=4; //Calcare cnf[i].material.sigma=0.03; break;

case 4: cnf[i].material.epsilon_r=1.64; //Calcestruzzo_A cnf[i].material.sigma=0.01; break;

case 5: cnf[i].material.epsilon_r=6.05; //Calcestruzzo_B cnf[i].material.sigma=0.01; break;

case 6: cnf[i].material.epsilon_r=9; //Cemento cnf[i].material.sigma=0.01; break;

case 7: cnf[i].material.epsilon_r=17; //Ferro cnf[i].material.sigma=1.03e7; break; case 8: cnf[i].material.epsilon_r=2; //Legno cnf[i].material.sigma=1e-5; break;

case 9: cnf[i].material.epsilon_r=4; //Materiali plastici cnf[i].material.sigma=1e-5; break;

case 10: cnf[i].material.epsilon_r=2.25; //Mattoni_A cnf[i].material.sigma=0.0; break;

case 11: cnf[i].material.epsilon_r=4.26; //Mattoni_B cnf[i].material.sigma=0.01; break;

case 12: cnf[i].material.epsilon_r=7.6; //Vetro da finestre cnf[i].material.sigma=1e-12; break;

case 13: cnf[i].material.epsilon_r=76; //Acqua distillata cnf[i].material.sigma=2e-4; break;

case 14: cnf[i].material.epsilon_r=81; //Acqua del mare

cnf[i].material.sigma=4; break; default: cout<<"Errore!!! Il numero identificativo del materiale inserito non consentito\n";}

Da quanto scritto sopra si capisce che il programma C++ completo prevede uno step di pre-processing nel quale aprendo uno stream in ingresso vengono prelevati e memorizzati dati relativi alla geometria e alla morfologia di ogni segmento presente nello scenario d’interesse. Nel nostro caso, per rendere più snello questo database abbiamo raggruppato dei segmenti (in numero variabile) in blocchi così da leggere pochi numeri ma ricavare da essi molte più informazioni. Un esempio è rappresentato dalle finestre, che (modellate con un rettangolo) possono essere descritte anziché da -segmento1: X e Y di V1, X e Y di V2, materiale;

-segmento2: X e Y di V2, X e Y di V3, materiale; -segmento3: X e Y di V3, X e Y di V4, materiale; -segmento4: X e Y di V4, X e Y di V1, materiale; (vedi fig. 3.2), semplicemente da

-segmento1: X e Y di V1, X e Y di V2, materiale, lunghezza, spessore.

segmento1

nus=1

segmento2

nus=2

segmento3

nus=3

segmento4

nus=4

V1

V2

V3

V4

Fig. 3.2 – Modello semplificato di una finestra.

Dopo la lettura dei dati indispensabili il programma calcola altre quantità necessarie nelle successive elaborazioni come ad esempio il vettore normale ad ogni segmento. Nel database vengono sistemate anche ulteriori informazioni necessarie all’algoritmo di ray-tracing per ridurre i tempi di simulazione.

A partire dai soli numeri riguardanti i segmenti vengono calcolate poi tutte le quantità relative agli spigoli verticali; esse sono inserite nei campi di una struttura che

li caratterizza chiamata edge. I campi di tale struttura affiancati da una breve descrizione sono riportati qui di seguito (vedi anche fig. 3.3):

short nue; numero identificativo dello spigolo.

double Vxy[2]; ascissa e ordinata del punto che costituisce lo spigolo verticale.

short facet[2]; nus della faccia precedente e nus della faccia successiva.

double nvp[2]; vettore normale alla faccia precedente. double nvs[2]; vettore normale alla faccia seguente.

double binp[2]; binormale giacente sulla faccia precedente.

double bins[2]; binormale giacente sulla faccia seguente.

double angle; angolo interno allo spigolo.

Da notare che per uno spigolo il campo nus della faccia seguente è pari al campo nue.

spigolo2 nue=2 spigolo3 nue=3 spigolo4 nue=4 spigolo1 nue=1 1 2 3 4 spigolo2 faccia precedente fp faccia seguente fs binormali bins binp normale a fp normale a fs angle

Fig. 3.3 – Modello di un elemento rettangolare costituito da 4 segmenti e 4 spigoli.

Operando nella maniera sopra descritta si arriva ad aver memorizzato tutte le quantità necessarie all’algoritmo di ray-tracing per calcolare la copertura elettromagnetica dell’ambiente in studio.

Ovviamente nel file.txt utilizzato in lettura dal nostro programma C++ ci sono oltre ai dati relativi a geometria, morfologia e topologia dello scenario (environment

configuration) anche delle informazioni riguardanti la rete wireless che si vuole installare (wireless network configuration) e i parametri di simulazione (simulation parameters). Queste quantità saranno esaminate in dettaglio nel prossimo capitolo.

3.4 – Il problema della visibilità

Le tipiche scene urbane e indoor tendono ad essere ambienti complessi che richiedono un elevato numero di facce per essere modellati (vedi fig. 3.4). In tali ambienti la propagazione delle onde radio è un fenomeno estremamente complicato.

Fig. 3.4 – Tipico scenario urbano 3D.

In un problema di comunicazione mobile può essere richiesto il calcolo del campo in un elevato numero di punti posizionati lungo una linea all’interno di una strada (vedi fig. 3.5), in un corridoio indoor o nei nodi di una maglia (vedi fig. 3.6). Il numero di punti di osservazione può essere dell’ordine delle migliaia o più.

Fig. 3.5 – Vista dall’alto di una tipica scena urbana. Il campo è valutato su un set di punti su una linea.

Anche usando un modello semplificato della scena come il modello a facce e un approccio di propagazione a raggi come quello GTD/UTD, il compito della simulazione della propagazione di onde radio è complesso. La figura 3.4 mostra un modello a facce di una tipica scena urbana.

L’operazione necessaria per determinare se un punto di osservazione è visibile ad un punto sorgente è nota come “test di visibilità” (shadowing test). In altre parole il test di visibilità determina se un oggetto della scena copre un dato percorso di un raggio da un punto sorgente a un punto osservatore. I punti sorgente possono essere antenne trasmittenti, punti di riflessione, punti di diffrazione e punti di trasmissione. I punti osservatori possono essere punti di osservazione, punti di riflessione, punti di diffrazione o punti di trasmissione.

Nei modelli sfaccettati gli oggetti ambientali sono descritti con facce, così il test di visibilità si riduce all’applicazione ripetuta di test di intersezione raggio-faccia.

In ambienti complessi il tempo dovuto ai tests di intersezione raggio-faccia può occupare più del 90% del tempo di ray-tracing totale. Il rimanente 10% è impiegato nel calcolo di punti di riflessione e di trasmissione sulle facce, di punti di diffrazione e calcoli matematici dell’espressioni presentate nel capitolo 2.

3.5 – Algoritmo di intersezione raggio-faccia

Il cuore di ogni modello di ray-tracing è costituito dall’algoritmo di intersezione tra raggi e oggetti dell’ambiente. In un processo di ray-tracing generale l’analisi dell’intersezione raggio-oggetto è ripetuta molte volte. Nei modelli a facce i raggi si intersecano sulle facce così è necessario usare un algoritmo efficiente di intersezione raggio-faccia. L’efficienza del processo di ray-tracing dipende molto da questo algoritmo.

Nei modelli ray-tracing per la predizione della propagazione, i raggi hanno sempre un’origine (sorgente) e arrivano a un punto di osservazione (osservatore).

Quindi geometricamente, i raggi possono essere considerati come segmenti orientati, cioè segmenti con una data direzione e un certo verso. Le sorgenti possono essere antenne trasmittenti, punti di riflessione o punti di diffrazione. I punti di osservazione possono essere antenne riceventi, punti di riflessione o punti di diffrazione.

Poiché come già detto il nostro modello di descrizione caratterizza un ambiente 2D, tutti i raggi originati sono segmenti orientati che giacciono sullo stesso piano: il piano d’incidenza definito nel capitolo 2 (che è anche il piano cui appartengono tutti i punti coinvolti). Inoltre l’intersezione raggio-faccia si trasforma più semplicemente in un’intersezione raggio-segmento.

L’algoritmo di intersezione raggio-segmento può essere diviso in due passi: 1. Calcolo dell’intersezione raggio-retta. Prima viene determinata la retta che

contiene il segmento. Poi è calcolato il punto di intersezione raggio-retta. Se la retta e il raggio sono paralleli non c’è tra loro un’intersezione e quindi non esiste un punto di intersezione raggio-segmento. Altrimenti è calcolato il punto di intersezione raggio-retta.

2. Test per determinare se il punto è all’interno o all’esterno del segmento

appartenente alla retta. Conoscendo il punto di intersezione raggio-retta, si

può determinare se il punto è interno o esterno al segmento. Se il punto è interno al segmento esiste l’intersezione raggio-segmento (vedi fig. 3.7a) altrimenti non esiste tale intersezione (vedi fig. 3.7b).

Linea contenente il raggio

Raggio

Retta contenente il segmento

Segmento

Segmento

Retta contenente il segmento Linea contenente il raggio

Raggio

La figura 3.8 mostra un diagramma a blocchi della procedura appena descritta.

Segmento Raggio

Determinazione della retta che lo contiene

Raggio e retta sono paralleli?

L’intersezione si trova compresa tra gli estremi del

raggio? (t_i [0,1]?) Il raggio giace sulla retta?

Determinazione del punto di intersezione raggio-retta (3.7)

Il punto è interno al segmento? SI NO SI NO NO Intersezione NO SI NO Intersezione SI Intersezione NO NO Intersezione SI

Raggio e retta hanno almeno un punto in comune?

NO

NO Intersezione SI

Infiniti punti di intersezione

Fig. 3.8 – Algoritmo di intersezione raggio-segmento.

• Determinazione della retta contenente il segmento:

L’equazione della retta y=ax+b contiene due coefficienti a e b che possono essere determinati sfruttando le coordinate del vertice1 e del vertice2 del segmento che valgono rispettivamente (X , Y )_{v1 v1} e (X , Y )_{v2 v2} . v1 v2 v1 v2 Y Y X X a= −

− Questo si può sempre fare tranne nel caso in cui la retta è parallela all’asse y perché il denominatore di a diventa nullo. In questo

caso il nostro programma prevede che se

v2 v2

Y X

b= −a

v1 v2

X =X la retta ha un coefficiente angolare infinito, a non viene settato, b=X_v1=X_v2, e la retta ha equazione x=b.

• Intersezione raggio-retta

Consideriamo un raggio definito dalla sua origine rG₀ e dalla sua punta in modo che

i punti sul raggio siano definiti da (vedi fig. 3.9):

1 rG r tG( )= +rG₀ t r(G G₁−r₀) con 0≤ ≤t 1 (3.1)

X

Y

r

r(0.5)

r

Fig. 3.9 – Definizione di un raggio come segmento orientato.

Definiamo la retta in termini del suo versore normale ˆn=( , )n n_{x y}

2 2 1 1 1 x y a n a n a = + = − + (3.2)

Con questa scelta ogni retta sul piano cartesiano ha un versore normale che giace sul 3° o 4° quadrante incluso il semiasse positivo delle ascisse ed escluso il semiasse negativo delle ascisse (vedi fig. 3.10).

¾ Se il raggio è parallelo alla retta e non c’è intersezione eccetto quando il raggio giace sulla retta (infiniti punti di intersezione). Questo ultimo caso accade quando

1 0 ˆ

(rG G−r )⋅ =n 0

(3.3)

1 0 ˆ 0 ˆ

dove è la distanza tra retta e origine del sistema di coordinate. Quando l’origine del sistema di coordinate vale (0,0)

d 2 ₁ b d a = + (3.4)

Da notare che d può essere positivo negativo o nullo.

X

Y

Fig. 3.10 – Scelta dei versori normali alle rette.

¾ Se c’è un punto di intersezione tra la retta che contiene il segmento e la linea che contiene il raggio. La coordinata parametrica del raggio nel punto di intersezione vale 1 0 ˆ (rG G−r )⋅ ≠n 0 0 1 0 ˆ ˆ ( ) i r n d t r r n ⋅ + = − − ⋅ G G G (3.5)

A questo punto se 0≤ ≤ allora la linea definita dal raggio interseca la retta in un ti 1 punto compreso tra gli estremi del raggio e dunque esiste l’intersezione raggio-retta. In questo caso il punto di intersezione è dato da

0 (1

i i

rG = +rG t rG G−r₀) (3.6)

• Intersezione raggio-segmento

Dato un segmento con estremi rv₁ =( ,xv₁ yv₁) e rv₂ =(xv₂,yv2)

G G la sua equazione parametrica è (3.7) 1 2 1 ( ) ( ) 0 1 s s v s v v s r tG =rG +t rG −rG ≤ ≤t

Supponendo che il raggio abbia la sua origine e la sua punta rispettivamente pari a

0 ( , ) 0 0 1 ( , )1

rG = x y e rG = x y₁ l’intersezione raggio-segmento esiste se le seguenti

condizioni sono soddisfatte (vedi fig. 3.11 ): ¾ Raggio e segmento non sono paralleli.

¾ La linea definita dal raggio interseca la retta contenente il segmento in un punto compreso tra gli estremi del raggio.

¾ Tale punto è anche compreso tra gli estremi del segmento. Oppure se sono soddisfatte le seguenti:

¾ Raggio e segmento giacciono sulla medesima retta. ¾ Raggio e segmento hanno almeno un punto in comune.

NO intersezione

Segmento

Raggio

SI intersezione SI intersezione

a) b) c)

Fig. 3.11 – Intersezione raggio-segmento in tre casi diversi, nel caso a) non esiste, nei casi b) e c) ci sono infiniti punti di intersezione.

Analiticamente, trovato il punto di intersezione raggio-retta con la procedura vista poc’anzi, lo si confronta con l’equazione parametrica del segmento

( , ) i i i rG = x y 1 2 1 , da 1 2 1 ( ) ( ) x x x x s v s v v s y y y y s v s v v r r t r r r r r t r r ⎛ ⎞ ⎛ + − ⎞ =_{⎜ ⎟ ⎜}= _⎟ + − ⎝ ⎠ ⎝ ⎠ G 1 ( 2 x x i v s v v1) x x =r +t r −r si calcola 1 2 1 x i v s x x v v x r t r r − = −

Se 0≤ ≤ts 1 esiste l’intersezione raggio-segmento altrimenti non esiste. Nel calcolo di

s

t se capita che basta semplicemente agire con lo stesso criterio sulla

coordinata y. 2 1 0 x x v v r −r =