Inviare il tuo buon lavoro nella knowledge base è semplice. Usa il modulo sottostante

Gli studenti, i dottorandi, i giovani scienziati che utilizzano la base di conoscenze nei loro studi e nel loro lavoro ti saranno molto grati.

Ospitato su http://www.allbest.ru/

PROGETTO DEL CORSO

COSTRUZIONEtriangolazioneRitardare

Su disciplina "struttureealgoritmiin lavorazionedati"

Contenuto

• introduzione
• 2.1 Algoritmo avido
• 2.4 Algoritmo con indicizzazione dei centri del triangoloK- D- albero
• 3.4 Algoritmo della ventola
• 4. Parte software
• Conclusione

introduzione

Oggi, all'inizio del 21° secolo, l'umanità sta entrando in una nuova civiltà, una civiltà associata alla penetrazione dei computer in tutte le sfere della vita umana. Questa civiltà si chiama informazione, virtuale, computer.

teoricoInformatica- una disciplina matematica che utilizza i metodi della matematica per costruire e studiare modelli per l'elaborazione, la trasmissione e l'utilizzo dell'informazione. Si basa sulla logica matematica e comprende sezioni come la teoria degli algoritmi e degli automi, la teoria dell'informazione e della codifica, la teoria dei linguaggi formali e delle grammatiche, la ricerca operativa e altri.

Una delle aree dell'informatica teorica è la geometria computazionale , che sviluppa metodi per risolvere problemi geometrici su computer utilizzando algoritmi e programmi.

Informaticageometriaè una branca dell'informatica che studia algoritmi per la risoluzione di problemi geometrici. Tali compiti si trovano nella computer grafica, nella progettazione di circuiti integrati, dispositivi tecnici, ecc. I dati iniziali per tali compiti possono essere un insieme di punti su un piano, un insieme di segmenti, un poligono, ecc. I problemi geometrici in informatica sono abbastanza comuni, poiché un computer è uno strumento molto comodo e veloce per risolverli, poiché il conteggio manuale è assolutamente inapplicabile qui.

Obbiettivooperaecompiti: per studiare uno degli algoritmi iterativi per la costruzione della triangolazione di Delaunay.

1) Studiare le definizioni ei teoremi di base del problema della triangolazione di Delaunay;

2) Considerare le principali tipologie di algoritmi iterativi per la costruzione della triangolazione;

3) Implementare l'algoritmo "Delete and build" per costruire la triangolazione di Delaunay.

1. Descrizione generale della triangolazione di Delaunay

Il compito di costruire una triangolazione.

Delaunay è una delle basi della geometria computazionale. Molti altri compiti sono ridotti ad esso, è ampiamente utilizzato nella computer grafica e nei sistemi di geoinformazione per modellare superfici e risolvere problemi spaziali. Il problema della costruzione di una triangolazione di Delaunay fu posto per la prima volta nel 1934 nel lavoro del matematico sovietico Boris Nikolaevich Delaunay.

triangolazioneRitardare per un insieme di punti S nel piano, si dice una triangolazione DT (S) tale che nessun punto A di S sia contenuto all'interno di una circonferenza circoscritta attorno a qualsiasi triangolo di DT (S) tale che nessuno dei suoi vertici sia un punto A.

1.1 Analisi della letteratura sull'argomento

SkvortsovMA.A.TriangolazioneRitardareesuoapplicazione. /SkvortsovMA.A. -Tomsk: Casa editriceVolume. un-ta,2002 . - 128s. Questo tutorial è il principale per questo progetto di corso. Descrive in dettaglio le informazioni teoriche relative alla triangolazione di Delaunay, fornisce varie definizioni e teoremi.

Ci sono anche sezioni che descrivono in dettaglio gli algoritmi per costruire triangolazioni, danno le loro caratteristiche comparative e la complessità degli algoritmi.

Che cosa preso in prestito: materiale di base, informazioni teoriche, definizioni, disegni.

PopovDA.MA.Informaticametodieprogrammazione. /PopovDA.MA. -Mosca: Casa editriceUniversità statale di Mosca2008, - 24s. Questo manuale è una fonte ausiliaria di letteratura. Alcuni algoritmi sono descritti da un punto di vista matematico, vengono calcolate formule di costruzione e c'è anche una descrizione della triangolazione nello spazio euclideo

Che cosa preso in prestito: descrizione matematica della triangolazione di Delaunay, costruzione sullo spazio euclideo

MedvedevH.N.MetodoVoronoi - Ritardareinricercastrutturenon cristallinosistemi/ RAS,Novosibirskrsk: Casa editriceCOSÌRAS,2000, - 214 Insieme a. Un libro dedicato alla descrizione dei metodi di Voronoi e Delaunay nei sistemi non cristallini.

Che cosa preso in prestito: proprietà delle triangolazioni di Delaunay, definizione delle triangolazioni di Delaunay.

1.2 Definizioni e proprietà di base

triangolazioneè un grafo planare le cui regioni interne sono tutte triangoli.

Proprietà:

· La triangolazione di Delaunay corrisponde uno a uno al diagramma di Voronoi per lo stesso insieme di punti.

· Di conseguenza: se non ci sono quattro punti sullo stesso cerchio, la triangolazione di Delaunay è unica.

· La triangolazione Delaunay massimizza l'angolo minimo tra tutti gli angoli di tutti i triangoli costruiti, evitando così i triangoli "sottili".

· La triangolazione di Delaunay massimizza la somma dei raggi delle sfere incise.

· La triangolazione Delaunay riduce al minimo il funzionale Dirichlet discreto.

· La triangolazione Delaunay riduce al minimo il raggio massimo della sfera minima che lo racchiude.

· La triangolazione di Delaunay su un piano ha la somma minima di raggi di cerchi circoscritti a triangoli tra tutte le possibili triangolazioni.

Fig 1. Triangolazione.

convesso triangolazione Una triangolazione è chiamata tale che il poligono minimo che racchiude tutti i triangoli sia convesso. Si chiama triangolazione non convessa non convesso.

compito costruzione triangolazione Su dato impostare bidimensionale puntiè chiamato il problema di collegare punti dati da segmenti non intersecanti in modo da formare una triangolazione.

Si dice che la triangolazione soddisfi condizione Ritardare , se nessuno dei punti di triangolazione indicati rientra nel cerchio descritto attorno a un triangolo costruito.

Triangolazionechiamatotriangolazione Ritardare , se è convesso e soddisfa la condizione di Delaunay.

Fig 2. Triangolazione di Delaunay.

1.3 Metodo a palla vuota di Delaunay. Costruzione nel caso generale

Utilizziamo una palla vuota, che sposteremo, modificandone le dimensioni in modo che possa toccare i punti del sistema (A), ma rimane sempre vuota.

Quindi, mettiamo una palla Delaunay vuota nel sistema di punti (A). Questo è sempre possibile se la pallina viene scelta abbastanza piccola. Iniziamo ad aumentare il suo raggio, lasciando in posizione il centro della palla. Ad un certo punto, la superficie della palla incontrerà un punto i del sistema (A). Questo accadrà sicuramente, perché non ci sono vuoti infinitamente grandi nel nostro sistema. Continueremo ad aumentare il raggio della palla vuota in modo che il punto i rimanga sulla sua superficie. Per fare ciò, dovrai spostare il centro della palla dal punto i. Prima o poi la palla raggiungerà con la sua superficie un altro punto del sistema (A).

Fig.3 - Partizione Delaunay di un sistema bidimensionale di punti

I semplici Delaunay riempiono lo spazio senza lacune e sovrapposizioni.

La sfera descritta di qualsiasi simplesso non contiene altri punti del sistema all'interno.

Sia questo il punto j. Continuiamo ad aumentare il raggio della nostra palla, mantenendo entrambi i punti sulla sua superficie. Aumentando, la palla raggiungerà un terzo punto del sistema, il punto k. Nel caso bidimensionale, il nostro "cerchio vuoto" sarà fissato in questo momento, cioè diventa impossibile aumentarne ulteriormente il raggio mantenendo vuoto il cerchio. Allo stesso tempo, riveliamo una configurazione bidimensionale elementare di tre punti (i, j, k), che definisce un certo triangolo, la cui particolarità è che non ci sono altri punti del sistema (A) all'interno del suo circoscritto cerchio. In tre dimensioni, una palla non è definita da tre punti. Continuiamo ad aumentare il suo raggio, mantenendo tutti e tre i punti trovati sulla sua superficie. Ciò sarà possibile finché la superficie della palla non incontra il quarto punto l del sistema. Dopodiché, il movimento e la crescita di una palla vuota diventeranno impossibili. I quattro punti trovati (i, j, k, l) determinano i vertici del tetraedro, che è caratterizzato dal fatto che non ci sono altri punti del sistema (A) all'interno della sua sfera circoscritta. Tale tetraedro è chiamato Delaunay simplex.

Un simplesso in matematica è chiamato la figura più semplice in uno spazio di una data dimensione: un tetraedro - nello spazio tridimensionale; triangolo - in due dimensioni. Una tripla (quadrupla) arbitraria di punti del sistema che non giacciono sullo stesso piano definisce sempre un certo simplesso. Tuttavia, è un Delaunay simplex solo se la sua sfera circoscritta è vuota. In altre parole, i simplice di Delaunay sono determinati da una scelta speciale di triple (quadruple) di punti nel sistema (A).

Abbiamo costruito un Delaunay simplex, tuttavia, posizionando la palla vuota in punti diversi e ripetendo la stessa procedura, se ne possono definire altri. Si afferma che l'insieme di tutti i semplici Delaunay del sistema (A) riempie lo spazio senza sovrapposizioni e lacune, cioè implementa la partizione dello spazio, ma questa volta in tetraedri. Questa divisione si chiama scissioneRitardare(Fig. 3).

1.4 Applicazione della triangolazione di Delaunay

Spesso le triangolazioni di Delaunay vengono applicate nello spazio euclideo. È garantito che lo spanning tree euclideo minimo si trovi su una triangolazione di Delaunay, quindi alcuni algoritmi usano la triangolazione. Inoltre, attraverso la triangolazione di Delaunay, il problema del commesso viaggiatore euclideo è approssimativamente risolto.

Nell'interpolazione 2D, la triangolazione di Delaunay divide l'aereo nei triangoli più spessi possibili, evitando angoli troppo acuti o troppo ottusi. Questi triangoli possono essere utilizzati per costruire, ad esempio, l'interpolazione bilineare.

Un altro problema che spesso si pone in geoinformatica è la costruzione di esposizioni di versanti. Qui è necessario determinare le direzioni dominanti dei pendii per punti cardinali e suddividere la superficie in regioni in cui domina una certa direzione. Poiché la definizione di esposizione non ha senso per le sezioni orizzontali della superficie, le aree orizzontali o con una leggera pendenza, ad esempio, sono assegnate a una regione separata.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Fig.4. Un esempio di calcolo dell'esposizione ai pendii utilizzando un modello di rilievo

Il compito di calcolare l'esposizione ai pendii è comunemente usato per analizzare l'illuminazione della Terra. A questo proposito, è spesso necessario tenere in considerazione anche l'attuale posizione del Sole, cioè l'esposizione è calcolata come la direzione tra la normale al triangolo e la direzione del Sole.

Pertanto, ogni triangolo di triangolazione può essere classificato secondo il principio di appartenenza a una determinata regione. Dopodiché, devi solo chiamare l'algoritmo di selezione della regione.

2. Descrizione degli algoritmi di costruzione

In generale, tutti gli algoritmi si basano su un'idea molto semplice di aggiungere in sequenza punti a una triangolazione Delaunay parzialmente costruita. Formalmente, sembra così.

Dato molti da N punti.

1. Sui primi tre punti di partenza, costruiamo un triangolo.

2. Nel ciclo per n per tutti gli altri punti, eseguire i passaggi 3-5.

3. Il successivo n-esimo punto viene aggiunto alla struttura di triangolazione già costruita come segue. Innanzitutto, il punto è localizzato, ad es. c'è un triangolo (costruito in precedenza), in cui cade il punto successivo. Oppure, se il punto non cade all'interno della triangolazione, c'è un triangolo sul bordo della triangolazione più vicino al punto successivo.

4. Se il punto colpisce un nodo di triangolazione inserito in precedenza, tale punto viene solitamente scartato, altrimenti il ​​punto viene inserito nella triangolazione come nuovo nodo. Inoltre, se il punto colpisce uno spigolo, viene diviso in due nuovi ed entrambi i triangoli adiacenti allo spigolo vengono anche divisi in due più piccoli. Se il punto è rigorosamente all'interno di qualsiasi triangolo, viene diviso in tre nuovi. Se il punto è al di fuori della triangolazione, vengono costruiti uno o più triangoli.

5. Vengono effettuati i controlli locali dei triangoli appena ottenuti per il rispetto della condizione di Delaunay e vengono eseguiti i necessari riarrangiamenti.

Fine algoritmo.

Sotto viene data dettagliato descrizione parecchi algoritmi.

2.1 Algoritmo avido

Uno dei primi ha proposto il seguente algoritmo per costruire la triangolazione.

Avidometodo Questo è un metodo che non annulla mai ciò che è già stato fatto prima. I passaggi seguenti vengono eseguiti in sequenza nell'algoritmo.

1. Le estremità di tutti i segmenti strutturali sono poste nell'insieme dei punti iniziali.

2. Vengono generati segmenti che collegano tutte le coppie di punti, i segmenti sono ordinati per lunghezza.

3. Tutti i segmenti della linea di discontinuità vengono inseriti nella triangolazione.

4. I segmenti vengono selezionati in sequenza per la triangolazione da un insieme di segmenti ordinati per lunghezza (dal più corto al più lungo). Se il segmento si interseca con uno qualsiasi di quelli già inseriti, viene scartato, altrimenti viene inserito nella triangolazione.

Il passaggio 4 viene ripetuto fino all'esaurimento dei segmenti.

Si noti che se tutti i segmenti possibili hanno lunghezze diverse, il risultato di questo algoritmo non è ambiguo, altrimenti dipende dall'ordine di inserimento dei segmenti della stessa lunghezza.

Si chiama triangolazione avido se è costruito da un algoritmo avido.

2.2 Algoritmo "Elimina e costruisci"

" Elimina e sistema " non vengono eseguite ricostruzioni. Invece, ad ogni inserimento di un nuovo nodo (a), vengono immediatamente cancellati tutti i triangoli, in cui un nuovo nodo (b) cade all'interno dei cerchi descritti. In questo caso, tutti i triangoli remoti formano implicitamente un certo poligono. Successivamente, al posto dei triangoli eliminati, viene costruita una triangolazione di riempimento collegando un nuovo nodo a questo poligono (Fig. c).

Riso. 4. Algoritmo "Elimina e costruisci"

Questo algoritmo costruisce tutti i triangoli necessari contemporaneamente, in contrasto con il solito algoritmo iterativo, dove quando si inserisce un nodo, sono possibili ricostruzioni multiple dello stesso triangolo. Tuttavia, qui emerge la procedura per estrarre il contorno di un poligono remoto, la velocità complessiva dell'algoritmo dipende dalla sua efficienza. In generale, a seconda della struttura dei dati utilizzata, questo algoritmo potrebbe richiedere meno tempo rispetto all'algoritmo con ricostruzioni e viceversa.

2.3 Algoritmo "Costruisci rompendo"

L'algoritmo per l'inserimento di segmenti strutturali "Build by breaking" è il più semplice nell'implementazione e stabile nel funzionamento.

In esso è necessario, passando in sequenza per triangoli lungo il segmento inserito, trovare i punti della sua intersezione con i bordi della triangolazione. In questi punti di intersezione, è necessario inserire nuovi nodi di triangolazione, suddividendo in parti i bordi e i triangoli esistenti. Successivamente, tutti i triangoli di nuova costruzione devono essere controllati per la condizione di Delaunay e, se necessario, ricostruiti senza intaccare i bordi fissi.

Riso. 5. Algoritmo "Costruisci rompendo"

In alcuni casi, lo svantaggio di questo algoritmo di inserimento può essere la creazione di un gran numero di nodi e spigoli di triangolazione aggiuntivi. Allo stesso tempo, in altri casi, questo inconveniente diventa un vantaggio, impedendo la formazione di triangoli lunghi e stretti, cosa particolarmente apprezzata nella modellazione del terreno.

Un altro vantaggio di questo algoritmo di inserimento rispetto a quelli successivi si ha quando si cerca di inserire un segmento strutturale in una triangolazione in cui ci sono spigoli fissi tra gli spigoli che interseca. Tali bordi, come tutti gli altri, sono semplicemente divisi in due parti.

2.4 Algoritmo con indicizzazione k-D-tree dei centri di triangoli

A algoritmo triangolazione Insieme a indicizzazione centri triangoli K-D- albero solo i centri dei triangoli sono posti nell'albero k-D (per k = 2). Quando si eliminano i vecchi triangoli, è necessario rimuovere i loro centri dall'albero k-D e, durante la costruzione di nuovi triangoli, è necessario inserirli.

Per cercare un triangolo che contenga il punto corrente inserito nella triangolazione, è necessario eseguire una query di punti non standard sull'albero k-D. La ricerca in un albero deve partire dalla radice e scendere fino alle foglie. Se i discendenti del nodo corrente dell'albero k-D (il rettangolo che racchiude i discendenti) non coprono il punto corrente, è necessario scegliere il discendente più vicino al punto di ricerca per un'ulteriore discesa lungo l'albero.

Di conseguenza, si troverà un triangolo, il cui centro sarà vicino al punto dato. Se il punto dato non cade nel triangolo trovato, è inoltre necessario utilizzare il solito algoritmo di ricerca del triangolo da un semplice algoritmo iterativo per costruire la triangolazione di Delaunay.

3. Valutazione dell'efficienza degli algoritmi

La complessità computazionale di un algoritmo è una funzione che determina la dipendenza della quantità di lavoro svolto da un algoritmo dalla dimensione dei dati di input. La quantità di lavoro viene solitamente misurata in termini astratti di tempo e spazio chiamati risorse di calcolo. Il tempo è determinato dal numero di passaggi elementari necessari per risolvere un problema, mentre lo spazio è determinato dalla quantità di memoria o spazio sul supporto di memorizzazione.

3.1 Algoritmo iterativo semplice

In un semplice algoritmo iterativo, la ricerca del triangolo successivo viene implementata come segue. Viene preso qualsiasi triangolo che già appartiene alla triangolazione (ad esempio, viene scelto in modo casuale) e il triangolo richiesto viene cercato mediante transizioni successive lungo i triangoli collegati.

In questo caso, nel peggiore dei casi, tutti i triangoli di triangolazione devono essere incrociati, quindi la complessità di tale ricerca è O (N). Tuttavia, in media, solo le operazioni di salto O() devono essere eseguite per distribuire uniformemente al quadrato. Pertanto, la complessità dell'algoritmo iterativo più semplice è nel peggiore dei casi e in media -

3.2 Algoritmo iterativo con indicizzazione a triangolo

La complessità di trovare un triangolo in un albero R è O(N) nel caso peggiore e O(log N) in media. In questo caso si trovano da 1 a N triangoli, che devono poi essere verificati. Inoltre, ci sono costi di tempo aggiuntivi per il mantenimento della struttura ad albero - O (log N) con ogni costruzione e rimozione di triangoli. Da ciò otteniamo che la complessità dell'algoritmo di triangolazione con indicizzazione di triangoli nel peggiore dei casi è, e in media - O (N log N).

3.3 Algoritmo iterativo con indicizzazione dell'albero K-D dei centri del triangolo

La complessità di trovare un punto in un albero k-D è O(N) nel caso peggiore e O(logN) nel caso medio. Inoltre, può essere coinvolta la procedura di transizione attraverso triangoli, che può avere una laboriosità nel caso peggiore di O N (). Ci sono anche costi di tempo aggiuntivi per il mantenimento della struttura ad albero - O N (log) con ogni costruzione e rimozione di triangoli.

Da ciò otteniamo che la complessità dell'algoritmo di triangolazione con indicizzazione dei centri dei triangoli nel peggiore dei casi è, e in media - O (N log N).

3.4 Algoritmo della ventola

Nell'algoritmo di triangolazione della ventola (algoritmo per lo spazzamento radiale del piano), inizialmente, dai punti iniziali, viene selezionato quello che è il più vicino possibile al baricentro di tutti i punti. Inoltre, per i punti rimanenti, viene calcolato l'angolo polare relativo al punto centrale selezionato e tutti i punti vengono ordinati in base a questo angolo. Quindi tutti i punti sono collegati da spigoli con il punto centrale e i punti adiacenti nell'elenco ordinato. Quindi la triangolazione viene completata in una convessa. Infine, la triangolazione è completamente ricostruita per soddisfare la condizione di Delaunay.

La complessità di un tale algoritmo è in media O N (). L'algoritmo funziona approssimativamente alla stessa velocità dell'algoritmo precedente.

4. Parte software

Il programma è stato sviluppato nell'ambiente di sviluppo Microsoft Visual Studio 2012. L'applicazione è una finestra in cui l'utente può aggiungere arbitrariamente punti che sono immediatamente collegati alla triangolazione di Delaunay. L'elenco delle coordinate di tutti i punti aggiunti viene visualizzato sulla destra.

principale. cpp - funzioni della finestra, funzioni dell'interfaccia utente

delone. cpp - algoritmo e funzioni necessarie per lavorarci

Descrizione delle funzioni del programma:

void DrawPoint (int x, int y) - funzione per disegnare un punto nella finestra dell'applicazione

void Triangulation() - funzione per eseguire la triangolazione

void TriangulationIn () - una funzione per eseguire azioni con punti che si trovano all'interno di un triangolo

void TriangulationOut () - una funzione per eseguire azioni con punti esterni al triangolo.

Per lavorare con l'applicazione, l'utente deve fare clic nell'area desiderata, dopodiché viene eseguita la costruzione della triangolazione di Delaunay.

Algoritmo software di triangolazione Delaunay

Riso. 6. Interfaccia del programma

Conclusione

In questo lavoro è stato sviluppato un programma sulla base del quale viene eseguita la costruzione della triangolazione di Delaunay.

Inoltre, tutti gli scopi e gli obiettivi sono stati raggiunti, vale a dire, è stato studiato uno degli algoritmi iterativi per la costruzione della triangolazione di Delaunay; vengono studiate definizioni e teoremi di base del problema della triangolazione di Delaunay; si considerano le principali tipologie di algoritmi iterativi per la costruzione della triangolazione; È stato implementato un algoritmo per la costruzione della triangolazione di Delaunay.

Elenco della letteratura usata

1. Skvortsov AV Triangolazione di Delaunay e sua applicazione. / Skvortsov AV - Tomsk: casa editrice vol. Univ., 2012. - 128s.

2. Popov SA Metodi computazionali e programmazione. /Popov SA - Mosca: casa editrice dell'Università statale di Mosca, 2008, - 24 p.

3. Medvedev N.N. Il metodo Voronoi-Delaunay nello studio della struttura dei sistemi non cristallini / RAS, Novosibirsk: casa editrice della filiale siberiana dell'Accademia delle scienze russa, 2009, - 214p.

Ospitato su Allbest.ru

Documenti simili

Metodo Delaunay a palla vuota. Partizione semplice (triangolazione). Peculiarità della disposizione reciproca dei semplici di Delaunay. Algoritmo per la costruzione del cerchio di Delaunay. Funzionalità di programmazione con la tecnologia Microsoft Windows Presentation Foundation.

tesina, aggiunta il 14/05/2011


Esplorazione delle possibilità del programma "Superficie": considerazione di metodi per la costruzione di isolinee, diagrammi di Voronoi, profili, grafici interpolati, visualizzazione tridimensionale, superfici utilizzando il metodo della triangolazione Delaunay e calcolo delle zone di visuale.

sommario, aggiunto il 02/11/2010


Studio teorico del problema e applicazione pratica. Informazioni generali sui grafici. L'algoritmo di Dijkstra. Caratteristiche del lavoro nell'ambiente. Implementazione software. Descrizione dell'algoritmo e della struttura del programma. Descrizione del software. Testo del programma.

tesina, aggiunta il 27/11/2007


Costruzione di diagrammi a blocchi - rappresentazioni grafiche di algoritmi di filtraggio digitale. Possibili opzioni per la sintesi di strutture sull'esempio dei filtri ricorsivi. Costruzione di un'equazione differenziale per tali filtri con la funzione di sistema scritta in forma generale.

presentazione, aggiunta il 19/08/2013


Descrizione della soluzione progettuale del sistema strategico, fasi di analisi e progettazione orientata agli oggetti. Descrizione dei collegamenti tra oggetti. Implementazione del software, costruzione di un modello di stati degli oggetti. Manuale utente e descrizione del programma.

tesina, aggiunta il 17/11/2011


Principali caratteristiche degli algoritmi evolutivi. Descrizione degli algoritmi di selezione, mutazione, incrocio utilizzati per implementare algoritmi genetici. Calcolo della funzione fitness. Implementazione software. Test e manuale utente.

tesina, aggiunta il 03/11/2014


Fasi di sviluppo della computer grafica. Concetto generale di grafica tridimensionale. Organizzazione del processo di costruzione della proiezione. Modello a filo, rifilatura off-face, rotazione. Implementazione software di costruzione di immagini. Costruire modelli complessi.

tesina, aggiunta il 06/11/2012


Le reti semantiche come modelli di rappresentazione della conoscenza. Metodi di base per determinare la somiglianza dei modelli grafici dei sistemi. Un metodo per risolvere i problemi di determinazione della somiglianza delle reti semantiche in base alla loro complessità. Sviluppo di algoritmi e loro implementazione software.

tesi, aggiunta il 17/12/2011


Descrizione del processo di scansione in forma semplificata. Descrizione delle componenti del metamodello e dei loro possibili stati. Iniziatori e risultanti, classi di equivalenza. Operazioni sui processi: riposizionamento, riduzione, composizione. Costruzione di una rete di Petri e sue proprietà.

tesina, aggiunta il 13/06/2011


Costruzione di un modello concettuale e metodo di modellazione simulata. Determinazione di equazioni variabili di un modello matematico e costruzione di un algoritmo di modellizzazione. Descrizione di possibili miglioramenti al sistema e versione finale del modello con i risultati.

Triangolazione spaziale di Delaunay

Il problema della costruzione di una rete di triangoli non sovrapposti è uno dei fondamentali della geometria computazionale ed è ampiamente utilizzato nella computer grafica e nei sistemi di geoinformazione per la modellazione di superfici e la risoluzione di problemi spaziali.

Per la prima volta il problema della costruzione di una rete di triangoli non sovrapposti fu posto nel 1934 nell'opera del matematico sovietico B. N. Delone, che formulò anche le condizioni corrispondenti.

In matematica, il problema della costruzione di una triangolazione per punti dati è chiamato problema della loro connessione a coppie per segmenti non intersecanti in modo da formare una rete di triangoli. I suoi elementi principali sono (Figura 5.3): nodi (vertici del triangolo), spigoli (lati) e facce (triangoli veri e propri). La triangolazione costruita può essere convessa (se questo è il poligono minimo che copre l'area di simulazione), non convessa (se la triangolazione non è convessa) e ottimale (se la somma delle lunghezze di tutti i bordi è minima).

Una rete di tali triangoli è chiamata triangolazione di Delaunay se soddisfa determinate condizioni:

Nessuno dei punti di partenza cade all'interno del cerchio descritto attorno a un triangolo (Fig. 5.3);

La triangolazione è convessa e soddisfa la condizione di Delaunay sopra formulata;

La somma degli angoli minimi di tutti i triangoli è il massimo di tutte le possibili triangolazioni;

La somma dei raggi dei cerchi circoscritti ai triangoli è la più piccola tra tutte le triangolazioni possibili.

Il primo dei criteri di cui sopra per costruire una triangolazione di Delaunay, detto circolare, è uno dei principali e viene verificato per ogni coppia di triangoli con facce comuni. L'interpretazione matematica del criterio segue dalla fig. 5.3:

(5.2)

Esistono molti modi per costruire la triangolazione di Delaunay, che è uno dei metodi più popolari per costruire una mesh di triangolazione negli ultimi tempi. Viene utilizzato in molti sistemi GIS per la costruzione di modelli del terreno.

Quando applicato allo spazio bidimensionale, è formulato come segue: un sistema di triangoli interconnessi non sovrapposti ha il perimetro più piccolo se nessuno dei vertici cade all'interno di nessuno dei cerchi descritti attorno ai triangoli formati (Fig. 5.4).

Riso. 5.4. Triangolazione delaunay

Ciò significa che i triangoli formati in una tale triangolazione sono il più vicino possibile all'equilatero e ciascuno dei lati dei triangoli formati dal vertice opposto è visibile all'angolo massimo da tutti i possibili punti del semipiano corrispondente. Questa è esattamente la triangolazione ottimale, lungo i cui bordi viene solitamente eseguita l'interpolazione lineare per costruire isolinee.

Molti algoritmi per costruire una triangolazione di Delaunay utilizzano il seguente teorema.

Teorema 1. La triangolazione di Delaunay può essere ottenuta da qualsiasi altra triangolazione sullo stesso sistema di punti ricostruendo in sequenza coppie di triangoli vicini ABC e BCD che non soddisfano la condizione di Delaunay in coppie di triangoli ABD e ACD (Fig. 5.5).

Riso. 5.5 Ricostruzione di triangoli che non soddisfano la condizione di Delaunay

Questa operazione di ricostruzione è spesso chiamata capovolgimento. Questo teorema permette di costruire una triangolazione di Delaunay in modo sequenziale, costruendo prima una triangolazione e poi migliorandola successivamente nel senso della condizione di Delaunay. Quando si controlla la condizione di Delaunay per coppie di triangoli vicini, è possibile utilizzare direttamente la definizione, ma a volte vengono utilizzati altri metodi in base alle condizioni sopra elencate.

In queste condizioni appare la caratteristica totale dell'intera triangolazione (somma degli angoli minimi o somma dei raggi), ottimizzando quale si può ottenere la triangolazione di Delaunay.

Come accennato in precedenza, una delle operazioni più importanti eseguite durante la costruzione di una triangolazione è controllare la condizione di Delaunay per date coppie di triangoli. Sulla base della definizione della triangolazione di Delaunay e delle condizioni corrispondenti, nella pratica vengono solitamente utilizzati diversi metodi di verifica:

- verifica mediante l'equazione del cerchio circoscritto;

– verificare con un cerchio circoscritto precalcolato;

– verifica della somma degli angoli opposti;

è un controllo modificato della somma degli angoli opposti.

Molti sistemi testano con un cerchio circoscritto precalcolato. L'idea principale dell'algoritmo per il controllo tramite cerchi precalcolati è di precalcolare per ogni triangolo costruito il centro e il raggio del cerchio circoscritto attorno ad esso, dopodiché la verifica della condizione di Delaunay sarà ridotta al calcolo della distanza al centro di questo cerchio e confrontando il risultato con il raggio. Il centro e il raggio r di un cerchio descritto intorno possono essere trovati come , , , r 2 = (b 2 + c 2 - 4ad)/4a 2 , dove i valori a, b, c, d definito dalle formule (5.3)

(5.3)

Un altro modo per scrivere l'equazione per questo cerchio è:

(5.5.)

(5.6)

Allora la condizione di Delaunay per sarà soddisfatta solo quando per ogni altro punto di triangolazione sarà:

(x 0 - x C) 2 + (y 0 - y C) 2 ≥ r 2 . (5.7)

Attualmente, ci sono molti algoritmi per costruire la triangolazione di Delaunay. Molti dei noti algoritmi utilizzano la definizione di triangolazione di Delaunay come caratteristica secondaria della triangolazione. Pertanto, tali algoritmi presentano i seguenti punti deboli:

- gli algoritmi utilizzano funzioni trigonometriche costantemente calcolate, che rallentano drasticamente il processo;

- quando si studia la relazione tra i punti e il segmento di base, sorgono angoli molto piccoli e quando si utilizzano funzioni trigonometriche c'è un pericolo costante di scomparsa dell'ordine e divisione per 0 a causa della limitata precisione delle rappresentazioni dei dati in un computer, questa situazione richiede un'elaborazione aggiuntiva costante.

I prodotti software più famosi costruiscono la triangolazione di Delaunay utilizzando il teorema della palla vuota come principio principale e primario per la costruzione dei triangoli. L'algoritmo si presenta così:

– l'intero insieme di punti è diviso in triangoli, cioè vengono create combinazioni di tre punti;

– per ogni combinazione si trovano il cerchio circoscritto e le coordinate del suo centro;

- se non c'è un solo punto tra quelli rimanenti all'interno del cerchio della combinazione corrente, allora questa combinazione è un triangolo - parte della triangolazione di Delaunay.

I vantaggi di questo algoritmo includono:

– nessun utilizzo di funzioni trigonometriche, che non rallenti il ​​processo costruttivo;

– realizzazione diretta della triangolazione Delaunay, senza costruzioni preliminari;

– semplicità di tutti i calcoli e trasformazioni;

- di conseguenza, la mesh di triangolazione è rappresentata da molti triangoli, non da singole linee.

La triangolazione così costruita è la base geometrica per la costruzione delle isolinee.

Gli algoritmi per la costruzione della triangolazione di Delaunay possono essere suddivisi in un certo numero di gruppi che differiscono per la struttura dei dati di input utilizzati, la quantità di operazioni di calcolo, le ipotesi iniziali, ecc. Consideriamone alcuni.

Gli algoritmi di fusione implicano la divisione di un insieme di punti iniziali in sottoinsiemi, la costruzione di una triangolazione su ciascuno di essi e quindi la loro combinazione in un'unica rete. L'essenza di uno di questi algoritmi è la seguente.

L'insieme dei punti iniziali è diviso da linee verticali in due o più parti, dopo di che ciascuna di esse è divisa da linee orizzontali e verticali in parti approssimativamente uguali. Di conseguenza, l'intera area dei punti iniziali è divisa in primitive di tre o quattro punti (Fig. 2.4), su cui sono costruiti uno o due triangoli.

L'unione di questi triangoli in un'unica rete viene eseguita costruendo due linee di base (P 0 P 1 e P 2 P 3, Riso. 5.7.a), disegnando cerchi di raggio variabile centrati sulla mediana perpendicolare alla linea di base (Fig. 5.7, b), cercando un nodo cadente sul cerchio (punto UN, Riso. 5.7. c) e la costruzione di un nuovo triangolo (P 0 P 1 A). In questo caso, potrebbe essere necessario eliminare un triangolo già esistente (ad esempio, P0AB).

Gli algoritmi iterativi si basano sull'idea di aggiungere in sequenza punti a una triangolazione parzialmente costruita con il suo simultaneo miglioramento e ricostruzione secondo i criteri di Delaunay. In generale, includono diversi passaggi e si riducono alla costruzione di un triangolo sui primi tre punti di partenza e all'esplorazione di diverse opzioni per posizionare il punto successivo. In particolare, vengono considerate le opzioni per portarlo oltre il confine dell'area di modellazione, su un nodo o bordo esistente, all'interno di un triangolo costruito, ecc. Ognuna di queste opzioni implica l'esecuzione di una determinata operazione: dividere uno spigolo in due, una faccia in tre, ecc.; dopodiché i triangoli risultanti vengono controllati per verificare la conformità con la condizione di Delaunay e i necessari riarrangiamenti.

Gli algoritmi a due passaggi forniscono prima la costruzione di una triangolazione, ignorando le condizioni di Delaunay e quindi ricostruendola in base a queste condizioni. Un esempio dell'applicazione dell'algoritmo è mostrato in fig. 5.8.

Per approssimare il modello in rilievo creato a quello reale, in esso vengono introdotti elementi aggiuntivi che garantiscono la contabilizzazione e la visualizzazione dei suoi elementi strutturali lineari e areali. Tali elementi aggiuntivi sono le linee strutturali ampiamente utilizzate in topografia che definiscono lo "scheletro di rilievo": bacini idrografici, thalweg, costoni, scogliere, cenge, laghi, anfratti, coste, confini di strutture artificiali, ecc., la cui totalità crea, come era, il quadro della triangolazione di Delaunay. Queste linee di discontinuità vengono introdotte nella triangolazione come bordi di triangoli, ed è così che si ottiene la modellazione di elementi in rilievo reali sullo sfondo della rugosità generale della superficie terrestre. Tali bordi sono chiamati strutturali (fissi, non ricostruibili), non intersecano i bordi di altri triangoli e non cambiano successivamente.

Il compito di costruire un modello di superficie che tenga conto delle linee di discontinuità è chiamato triangolazione di Delaunay con restrizioni se le condizioni di Delaunay sono soddisfatte per qualsiasi coppia di triangoli adiacenti che non sono separati da linee di discontinuità. I ricercatori ritengono che tale triangolazione sia costruita in modo più efficace utilizzando algoritmi iterativi.

Un frammento della triangolazione di Delaunay con elementi aggiuntivi inclusi in essa è mostrato in Fig. 5.9, dove a destra sono mostrati nodi, bordi, facce e linee di discontinuità, mentre a sinistra sono mostrate le linee di discontinuità del terreno (linee costiere, bordi di burroni, ecc.) e punti con segni noti.

Gli algoritmi per la costruzione della triangolazione di Delaunay sono implementati con una rappresentazione reale o intera delle coordinate dei nodi, che può aumentare notevolmente la velocità e la precisione dell'elaborazione, ma dà origine a problemi nel trovare ed eliminare i nodi corrispondenti.

Il modello TIN è facilmente modificabile spostando i nodi, inserendone di nuovi, eliminando quelli esistenti, modificando la posizione di uno o più bordi, introducendo nuove linee di discontinuità, ecc. Tali modifiche interessano sempre un piccolo gruppo di triangoli adiacenti, non richiedono la ricostruzione dell'intero rete e si svolgono in modalità on-line, puntando il cursore sull'elemento corrispondente.

Informazioni sulla precisione:

Quando si posizionano picchetti su elementi caratteristici in rilievo (ad esempio, bacini idrografici e thalweg), ignoriamo gli elementi più piccoli nel mezzo. Quando si costruiscono linee di contorno1 lungo tali bordi di triangoli, si verifica un errore, che dipende dall'entità dell'irregolarità del rilievo e dall'angolo di inclinazione del terreno. Ad esempio, l'errore medio del rilievo rilievo non deve superare 1/3 della sezione rilievo ad angoli di inclinazione della superficie da 2 a 10 gradi. Si può calcolare che con una sezione trasversale del rilievo di 0,5 m, il valore limite della mancata irregolarità (cioè lo scostamento della superficie terrestre da una retta passante per picchetti vicini) non deve superare (0,5/3)*cos10 °=0,16 m.

Per l'accuratezza della determinazione del volume del terreno spostato, è importante anche l'area occupata dal dettaglio del rilievo che non viene presa in considerazione. Supponiamo che in un quadrato di 20x20 m tra due coppie di picchetti ci sia un rigonfiamento cilindrico con un'altezza massima di 0,15 m È facile calcolare che ignorarlo quando si rappresenta questa superficie con solo due triangoli comporterà un errore di circa 40 m3. Non tanto, ma per un appezzamento di 1 ha, situato su una collina o nella parte superiore (solitamente convessa) del pendio, otterrai già 40 * 25 = 1000 m3 di terreno in eccesso. Se i picchetti vengono presi due volte più spesso (cioè ogni 10 m), l'errore si quadruplica e ammonta a 250 m3 per ettaro. Questo fattore può essere preso in considerazione in anticipo, poiché le forme positive del rilievo piatto hanno solitamente una forma convessa e le forme negative sono concave. Se l'area da rilevare ha dati approssimativi sul rilievo, allora il raggio di curvatura della superficie e la densità richiesta dei picchetti possono essere facilmente calcolati dai valori delle curve di livello o dei singoli prospetti.

Struttura della lezione Definizioni Definizioni Applicazioni Applicazioni Proprietà della triangolazione Delaunay Proprietà della triangolazione Delaunay Metodi di costruzione della triangolazione Delaunay Metodi di costruzione della triangolazione di Delaunay Metodi di input a gradini Metodi di input a gradini Metodi di campionamento a gradini Metodi di campionamento a gradini Metodi di decomposizione Metodi di decomposizione Metodi di scansione Metodi di scansione Metodi a due passaggi Metodi a due passaggi

Triangolazione La triangolazione è un grafo planare le cui regioni interne sono tutte triangoli. Una triangolazione è un grafo planare le cui regioni interne sono tutti triangoli. Il termine "Triangolazione" è il termine "Triangolazione" è un grafico; grafico; processo di costruzione del grafico. processo di costruzione del grafico. Il compito di triangolare un insieme di punti S è il compito di collegare tutti i punti dell'insieme S con segmenti non intersecanti per ottenere un grafico di triangolazione. Il compito di triangolare un insieme di punti S è il compito di collegare tutti i punti dell'insieme S con segmenti non intersecanti per ottenere un grafico di triangolazione. Definizione di triangolazione Insieme di punti S

La triangolazione ottimale è una triangolazione con la somma minima delle lunghezze di tutti i bordi del grafico. La triangolazione ottimale è una triangolazione con la somma minima delle lunghezze di tutti i bordi del grafico. ! Compito richiesto, ma molto dispendioso in termini di tempo O(2 n) ! In pratica si utilizzano approssimazioni (approssimazioni alla) triangolazione ottimale: Triangolazione “Greedy” O(N 2 *logN) Triangolazione “Greedy” O(N 2 *logN) Triangolazione Delaunay O(N*logN) Triangolazione Delaunay O(N*logN ) Definizione triangolazione ottimale

La triangolazione di Delaunay (DT(S)) è una triangolazione convessa che soddisfa la condizione di Delaunay: La triangolazione di Delaunay (DT(S)) è una triangolazione convessa che soddisfa la condizione di Delaunay: nessuno dei vertici del grafo deve cadere all'interno di un cerchio circoscritto attorno uno qualsiasi dei suoi triangoli. nessuno dei vertici del grafico dovrebbe cadere all'interno di un cerchio circoscritto attorno a uno qualsiasi dei suoi triangoli. Definizione di triangolazione di Delaunay La condizione di Delaunay è soddisfatta La condizione di Delaunay non è soddisfatta B.N. Ritardo ()

Applicazione della triangolazione di Delaunay In altri problemi VG In altri problemi VG Intervallo minimo di un insieme di punti Intervallo minimo di un insieme di punti Costruire zone cuscinetto Costruire zone cuscinetto Costruire un diagramma di Voronoi (zone di prossimità) Costruire un diagramma di Voronoi (zone di prossimità) Trovare il cerchio vuoto massimo Trovare il cerchio vuoto massimo, ecc. ecc. Nelle applicazioni in CG, GIS, GM in CAD Nelle applicazioni in CG, GIS, GM in CAD Modelli di superficie poligonale Modelli di superficie poligonale Rilievi in ​​GIS, sculture, modelli industriali, modelli in giochi, Rilievi in ​​GIS, sculture, modelli industriali, modelli in giochi, Analisi numerica di modelli Analisi numerica di modelli Isoline, Isoclines, FEM. Isoline, Isocline, FEM.

Proprietà di qualsiasi triangolazione convessa 1. Per un insieme di n punti di cui m sono interni Numero di triangoli di triangolazione = n + m – 2 Numero di triangoli di triangolazione = n + m – 2 Numero di spigoli di triangolazione 3n – 6 Numero di spigoli di triangolazione 3n – 6 Esempio: Punti (n) – 13 Punti (n) – 13 Interno (m) – 4 Interno (m) – 4 Triangoli – 15 = Triangoli – 15 = Bordi – 26 3*13-6 = 33 Bordi – 26 3 *13-6 = 33

Proprietà della triangolazione di Delaunay 2. La triangolazione di Delaunay ha la somma massima degli angoli minimi di tutti i triangoli tra tutte le possibili triangolazioni. 3. La triangolazione di Delaunay ha la somma minima dei raggi dei cerchi circoscritti ai triangoli tra tutte le possibili triangolazioni. Triangolazione Delaunay NON Triangolazione Delaunay

Metodi di costruzione della triangolazione Delaunay Metodi di input passo-passo Metodi di input passo-passo Algoritmi iterativi () Algoritmi iterativi () Metodi di campionamento passo-passo Metodi di campionamento passo-passo Algoritmi di costruzione diretta (passo-passo) (3) Algoritmi di costruzione diretta (passo-passo) (3) Metodi di scomposizione Metodi di scomposizione Algoritmi di fusione (2) ) Algoritmi di fusione (2) Metodi di scansione Metodi di scansione Algoritmi iterativi con un ordine modificato di punti (1.4) Algoritmi iterativi con un ordine modificato di somma dei punti (1.4) Algoritmi a due passaggi (4) Algoritmi a due passaggi (4)

Metodi di input passo-passo Algoritmi iterativi () Schema generale degli algoritmi iterativi per la costruzione della triangolazione di Delaunay 1. Nei primi tre punti, costruire un triangolo 2. Eseguire un ciclo su tutti i punti rimanenti p i dell'insieme S 3. Trovare il triangolo t j dell'insieme S triangolazione corrente più vicina al punto p i 4. Se il punto p i è esterno al triangolo t j, costruire triangoli fino al bordo più vicino. 5. Se il punto p i è all'interno del triangolo t j, dividere il triangolo in tre. 6. Se il punto p i è su uno spigolo, dividere i triangoli adiacenti in coppie. 7. Se la condizione di Delaunay per i vicini viene violata, ricostruire i triangoli vicini. Opzioni di accelerazione della ricerca del triangolo: Indicizzazione del triangolo (alberi) – O(log n) Indicizzazione del triangolo (alberi) – O(log n) Memorizzazione nella cache del triangolo (mesh) – O(s) Memorizzazione nella cache del triangolo (grid) – O(s)

Metodi di campionamento passo-passo Algoritmi di costruzione diretta (passo-passo) (3) Costruire i triangoli necessari in una volta, senza riordinare ciò che è già stato costruito. Schema generale degli algoritmi per la costruzione diretta della triangolazione di Delaunay È conveniente utilizzare una pila di archi che non sono stati ancora elaborati. 1. Trova un qualsiasi bordo q dello scafo convesso dell'insieme di punti S. 2. Spingi il bordo q sulla pila di bordi grezzi. 3. Ripeti finché la pila di bordi grezzi non è vuota. 4. Estrarre il bordo v dalla pila. 5. Per il bordo v, trovare un punto p che soddisfi la condizione di Delaunay (il vicino di Delaunay) 6. Se si trova il vicino di Delaunay p, allora 7. Costruire un triangolo dal bordo v al punto p. 8. Spingere i nuovi bordi del nuovo triangolo sulla pila di bordi grezzi. Opzioni per velocizzare la ricerca di un vicino di Delaunay: Indicizzazione di punti per k-D-tree - O(log n) Indicizzazione di punti per k-D-tree - O(log n) Indicizzazione di punti cellulari - O(c) Indicizzazione di punti cellulari - O(c )

Il flusso di lavoro dell'avido algoritmo di triangolazione Delaunay

Metodi di scomposizione Algoritmi di unione (2) Suddivisione in sottoinsiemi, elaborazione indipendente, unione di risultati. Lo schema generale degli algoritmi di unione 0. Se non ci sono più di 3 punti nell'insieme S, costruisci direttamente altrimenti 1. Dividi l'insieme di punti S in sottoinsiemi approssimativamente uguali. 1. Dividere l'insieme dei punti S in sottoinsiemi approssimativamente uguali. 2. Costruzione di triangolazioni per sottoinsiemi. 2. Costruzione di triangolazioni per sottoinsiemi. 3. Unire le triangolazioni risultanti in una. 3. Unire le triangolazioni risultanti in una. Metodi di divisione in sottoinsiemi Linee ortogonali Linee ortogonali Per il diametro dello scafo convesso Per il diametro dello scafo convesso Strisce Strisce

Algoritmi di fusione (2) Metodi per unire le triangolazioni "Elimina e costruisci" (controlla prima della costruzione) "Elimina e costruisci" (controlla prima della costruzione) "Costruisci e ricostruisci" (controlla dopo la costruzione) "Costruisci e ricostruisci" (controlla dopo la costruzione) " Build Build by Rebuilding" (controlla in fase di build) "Build by Rebuild" (controlla in fase di build)

Lo schema generale dei metodi iterativi con un ordine modificato di somma dei punti 1. Ordina punti (costruisci un elenco di punti evento) 2. Scansiona il ciclo su tutti i punti evento 3. Per ogni punto p costruisci triangoli al triangolo precedente. 4. Se la condizione di Delaunay per i vicini viene violata, ricostruire i triangoli vicini. Metodi di scansione Algoritmi iterativi con un ordine modificato di somma dei punti (1.4)

Metodi di scansione Metodi per ordinare i punti evento Rettilineo Rettilineo Polare (circolare, a forma di ventaglio) Polare (circolare, a forma di ventaglio) Stripe Stripe Square Square Curva di Hilbert Curva di Hilbert Z-code Z-code Obiettivi: Costruire immediatamente tanti triangoli validi Costruire immediatamente quanti molti triangoli buoni Ridurre al minimo il numero di ricostruzioni Ridurre al minimo il numero di ricostruzioni

Caratteristiche riassuntive dei metodi di triangolazione Delaunay Metodo di triangolazione Tempo medio Tempo peggiore Tempo sec / t Facilità di attuazione Metodi di input incrementali Metodi di input incrementali Algoritmi iterativi () Algoritmi iterativi ()O(n)- O(n 3/2) O(n 2) 1.5-9.2 2-5 Metodi di campionamento incrementale Metodi di campionamento incrementale Metodo di costruzione diretta (3) Diretto metodo di costruzione (3) O(n)- O(n 2) O(n 2) -2 Metodi di decomposizione Metodi di decomposizione Metodi di fusione (2) Metodi di fusione (2) O(n)- O(nlogn) O (nlogn)- O(n 2) 2.5-4.52-3 Metodi di scansione Metodi di scansione Iterativo con l'ordine di aggiunta dei punti modificato (1.4) Iterativo con l'ordine di aggiunta dei punti modificato (1.4)O(n) O(n 2) 1 ,9-5 ,34-5 Metodi a due passaggi (4) Metodi a due passaggi (4) O(n)- O(n 2) O(nlogn)- O(n 2) 2,2-15,41-5 Skvortsov raccomanda: algoritmo iterativo con cache dinamica

E oggi? Informazioni sulla triangolazione di Delaunay! Definizione Definizione Applicazioni Applicazioni Proprietà della triangolazione di Delaunay Proprietà della triangolazione di Delaunay Metodi di costruzione della triangolazione di Delaunay Metodi di costruzione della triangolazione di Delaunay Metodi di input incrementali Metodi di input incrementali Metodi di campionamento incrementale Metodi di campionamento incrementale Metodi di decomposizione Metodi di decomposizione Metodi di scansione Metodi di scansione Metodi a due passaggi Metodi a due passaggi

Definizioni e proprietà di base

Una triangolazione è un grafo planare le cui regioni interne sono tutte triangoli.

Proprietà:

· La triangolazione di Delaunay corrisponde uno a uno al diagramma di Voronoi per lo stesso insieme di punti.

· Di conseguenza: se non ci sono quattro punti sullo stesso cerchio, la triangolazione di Delaunay è unica.

· La triangolazione Delaunay massimizza l'angolo minimo tra tutti gli angoli di tutti i triangoli costruiti, evitando così i triangoli "sottili".

· La triangolazione di Delaunay massimizza la somma dei raggi delle sfere incise.

· La triangolazione Delaunay riduce al minimo il funzionale Dirichlet discreto.

· La triangolazione Delaunay riduce al minimo il raggio massimo della sfera minima che lo racchiude.

· La triangolazione di Delaunay su un piano ha la somma minima di raggi di cerchi circoscritti a triangoli tra tutte le possibili triangolazioni.

Fig 1. Triangolazione.

Una triangolazione convessa è una tale triangolazione per la quale il poligono minimo che racchiude tutti i triangoli è convesso. Una triangolazione che non è convessa si dice non convessa.

Il compito di costruire una triangolazione da un dato insieme di punti bidimensionali è il problema di collegare punti dati con segmenti non intersecanti in modo da formare una triangolazione.

Si dice che una triangolazione soddisfi la condizione di Delaunay se nessuno dei punti di triangolazione dati cade all'interno del cerchio circoscritto attorno a un triangolo costruito.

Una triangolazione è chiamata triangolazione di Delaunay se è convessa e soddisfa la condizione di Delaunay.

Fig 2. Triangolazione di Delaunay.

Metodo Delaunay a palla vuota. Costruzione nel caso generale

Utilizziamo una palla vuota, che sposteremo, modificandone le dimensioni in modo che possa toccare i punti del sistema (A), ma rimane sempre vuota.

Quindi, mettiamo una palla Delaunay vuota nel sistema di punti (A). Questo è sempre possibile se la pallina viene scelta abbastanza piccola. Iniziamo ad aumentare il suo raggio, lasciando in posizione il centro della palla. Ad un certo punto, la superficie della palla incontrerà un punto i del sistema (A). Questo accadrà sicuramente, perché non ci sono vuoti infinitamente grandi nel nostro sistema. Continueremo ad aumentare il raggio della palla vuota in modo che il punto i rimanga sulla sua superficie. Per fare ciò, dovrai spostare il centro della palla dal punto i. Prima o poi la palla raggiungerà con la sua superficie un altro punto del sistema (A).

Fig.3

I semplici Delaunay riempiono lo spazio senza lacune e sovrapposizioni.

La sfera descritta di qualsiasi simplesso non contiene altri punti del sistema all'interno.

Sia questo il punto j. Continuiamo ad aumentare il raggio della nostra palla, mantenendo entrambi i punti sulla sua superficie. Aumentando, la palla raggiungerà un terzo punto del sistema, il punto k. Nel caso bidimensionale, il nostro "cerchio vuoto" sarà fissato in questo momento, cioè diventa impossibile aumentarne ulteriormente il raggio mantenendo vuoto il cerchio. Allo stesso tempo, riveliamo una configurazione bidimensionale elementare di tre punti (i, j, k), che definisce un certo triangolo, la cui particolarità è che non ci sono altri punti del sistema (A) all'interno del suo circoscritto cerchio. In tre dimensioni, una palla non è definita da tre punti. Continuiamo ad aumentare il suo raggio, mantenendo tutti e tre i punti trovati sulla sua superficie. Ciò sarà possibile finché la superficie della palla non incontra il quarto punto l del sistema. Dopodiché, il movimento e la crescita di una palla vuota diventeranno impossibili. I quattro punti trovati (i, j, k, l) determinano i vertici del tetraedro, che è caratterizzato dal fatto che non ci sono altri punti del sistema (A) all'interno della sua sfera circoscritta. Tale tetraedro è chiamato Delaunay simplex.

Un simplesso in matematica è chiamato la figura più semplice in uno spazio di una data dimensione: un tetraedro - nello spazio tridimensionale; triangolo - in due dimensioni. Una tripla (quadrupla) arbitraria di punti del sistema che non giacciono sullo stesso piano definisce sempre un certo simplesso. Tuttavia, è un Delaunay simplex solo se la sua sfera circoscritta è vuota. In altre parole, i simplice di Delaunay sono determinati da una scelta speciale di triple (quadruple) di punti nel sistema (A).

Abbiamo costruito un Delaunay simplex, tuttavia, posizionando la palla vuota in punti diversi e ripetendo la stessa procedura, se ne possono definire altri. Si afferma che l'insieme di tutti i semplici Delaunay del sistema (A) riempie lo spazio senza sovrapposizioni e lacune, cioè implementa la partizione dello spazio, ma questa volta in tetraedri. Questa divisione si chiama Partizione di ritardo(Fig. 3).

Applicazione della triangolazione di Delaunay

Spesso le triangolazioni di Delaunay vengono applicate nello spazio euclideo. È garantito che lo spanning tree euclideo minimo si trovi su una triangolazione di Delaunay, quindi alcuni algoritmi usano la triangolazione. Inoltre, attraverso la triangolazione di Delaunay, il problema del commesso viaggiatore euclideo è approssimativamente risolto.

Nell'interpolazione 2D, la triangolazione di Delaunay divide l'aereo nei triangoli più spessi possibili, evitando angoli troppo acuti o troppo ottusi. Questi triangoli possono essere utilizzati per costruire, ad esempio, l'interpolazione bilineare.

Un altro problema che spesso si pone in geoinformatica è la costruzione di esposizioni di versanti. Qui è necessario determinare le direzioni dominanti dei pendii per punti cardinali e suddividere la superficie in regioni in cui domina una certa direzione. Poiché la definizione di esposizione non ha senso per le sezioni orizzontali della superficie, le aree orizzontali o con una leggera pendenza, ad esempio, sono assegnate a una regione separata.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Fig.4.

Il compito di calcolare l'esposizione ai pendii è comunemente usato per analizzare l'illuminazione della Terra. A questo proposito, è spesso necessario tenere in considerazione anche l'attuale posizione del Sole, cioè l'esposizione è calcolata come la direzione tra la normale al triangolo e la direzione del Sole.

Pertanto, ogni triangolo di triangolazione può essere classificato secondo il principio di appartenenza a una determinata regione. Dopodiché, devi solo chiamare l'algoritmo di selezione della regione.

In generale, tutti gli algoritmi si basano su un'idea molto semplice di aggiungere in sequenza punti a una triangolazione Delaunay parzialmente costruita. Formalmente, sembra così.

Dato un insieme di N punti.

1. Sui primi tre punti di partenza, costruiamo un triangolo.

2. Nel ciclo per n per tutti gli altri punti, eseguire i passaggi 3-5.

3. Il successivo n-esimo punto viene aggiunto alla struttura di triangolazione già costruita come segue. Innanzitutto, il punto è localizzato, ad es. c'è un triangolo (costruito in precedenza), in cui cade il punto successivo. Oppure, se il punto non cade all'interno della triangolazione, c'è un triangolo sul bordo della triangolazione più vicino al punto successivo.

4. Se il punto colpisce un nodo di triangolazione inserito in precedenza, tale punto viene solitamente scartato, altrimenti il ​​punto viene inserito nella triangolazione come nuovo nodo. Inoltre, se il punto colpisce uno spigolo, viene diviso in due nuovi ed entrambi i triangoli adiacenti allo spigolo vengono anche divisi in due più piccoli. Se il punto è rigorosamente all'interno di qualsiasi triangolo, viene diviso in tre nuovi. Se il punto è al di fuori della triangolazione, vengono costruiti uno o più triangoli.

5. Vengono effettuati i controlli locali dei triangoli appena ottenuti per il rispetto della condizione di Delaunay e vengono eseguiti i necessari riarrangiamenti.

Fine dell'algoritmo.

Di seguito è riportata una descrizione dettagliata di diversi algoritmi.

Algoritmo goloso

Uno dei primi ha proposto il seguente algoritmo per costruire la triangolazione.

Metodo goloso Questo è un metodo che non annulla mai ciò che è già stato fatto prima. I passaggi seguenti vengono eseguiti in sequenza nell'algoritmo.

1. Le estremità di tutti i segmenti strutturali sono poste nell'insieme dei punti iniziali.

2. Vengono generati segmenti che collegano tutte le coppie di punti, i segmenti sono ordinati per lunghezza.

3. Tutti i segmenti della linea di discontinuità vengono inseriti nella triangolazione.

4. I segmenti vengono selezionati in sequenza per la triangolazione da un insieme di segmenti ordinati per lunghezza (dal più corto al più lungo). Se il segmento si interseca con uno qualsiasi di quelli già inseriti, viene scartato, altrimenti viene inserito nella triangolazione.

Il passaggio 4 viene ripetuto fino all'esaurimento dei segmenti.

Si noti che se tutti i segmenti possibili hanno lunghezze diverse, il risultato di questo algoritmo non è ambiguo, altrimenti dipende dall'ordine di inserimento dei segmenti della stessa lunghezza.

Una triangolazione è chiamata greedy se è costruita da un algoritmo greedy.

Algoritmo "Elimina e costruisci"

Elimina e crea non esegue alcuna ricostruzione. Invece, ad ogni inserimento di un nuovo nodo (a), vengono immediatamente cancellati tutti i triangoli, in cui un nuovo nodo (b) cade all'interno dei cerchi descritti. In questo caso, tutti i triangoli remoti formano implicitamente un certo poligono. Successivamente, al posto dei triangoli eliminati, viene costruita una triangolazione di riempimento collegando un nuovo nodo a questo poligono (Fig. c).

Riso. 4. Algoritmo "Elimina e costruisci"

Questo algoritmo costruisce tutti i triangoli necessari contemporaneamente, in contrasto con il solito algoritmo iterativo, dove quando si inserisce un nodo, sono possibili ricostruzioni multiple dello stesso triangolo. Tuttavia, qui emerge la procedura per estrarre il contorno di un poligono remoto, la velocità complessiva dell'algoritmo dipende dalla sua efficienza. In generale, a seconda della struttura dei dati utilizzata, questo algoritmo potrebbe richiedere meno tempo rispetto all'algoritmo con ricostruzioni e viceversa.

Algoritmo "Costruisci rompendo"

L'algoritmo per l'inserimento di segmenti strutturali "Build by breaking" è il più semplice nell'implementazione e stabile nel funzionamento.

In esso è necessario, passando in sequenza per triangoli lungo il segmento inserito, trovare i punti della sua intersezione con i bordi della triangolazione. In questi punti di intersezione, è necessario inserire nuovi nodi di triangolazione, suddividendo in parti i bordi e i triangoli esistenti. Successivamente, tutti i triangoli di nuova costruzione devono essere controllati per la condizione di Delaunay e, se necessario, ricostruiti senza intaccare i bordi fissi.

Riso. 5. Algoritmo "Costruisci rompendo"

In alcuni casi, lo svantaggio di questo algoritmo di inserimento può essere la creazione di un gran numero di nodi e spigoli di triangolazione aggiuntivi. Allo stesso tempo, in altri casi, questo inconveniente diventa un vantaggio, impedendo la formazione di triangoli lunghi e stretti, cosa particolarmente apprezzata nella modellazione del terreno.

Un altro vantaggio di questo algoritmo di inserimento rispetto a quelli successivi si ha quando si cerca di inserire un segmento strutturale in una triangolazione in cui ci sono spigoli fissi tra gli spigoli che interseca. Tali bordi, come tutti gli altri, sono semplicemente divisi in due parti.

Algoritmo con indicizzazione dei centri del triangolo k-D - albero

Nell'algoritmo di triangolazione con indicizzazione k-D-tree dei centri del triangolo, solo i centri del triangolo sono inseriti nell'albero k-D (per k = 2). Quando si eliminano i vecchi triangoli, è necessario rimuovere i loro centri dall'albero k-D e, durante la costruzione di nuovi triangoli, è necessario inserirli.

Per cercare un triangolo che contenga il punto corrente inserito nella triangolazione, è necessario eseguire una query di punti non standard sull'albero k-D. La ricerca in un albero deve partire dalla radice e scendere fino alle foglie. Se i discendenti del nodo corrente dell'albero k-D (il rettangolo che racchiude i discendenti) non coprono il punto corrente, è necessario scegliere il discendente più vicino al punto di ricerca per un'ulteriore discesa lungo l'albero.

Di conseguenza, si troverà un triangolo, il cui centro sarà vicino al punto dato. Se il punto dato non cade nel triangolo trovato, è inoltre necessario utilizzare il solito algoritmo di ricerca del triangolo da un semplice algoritmo iterativo per costruire la triangolazione di Delaunay.