20 august 2012 la 22:41

Optimizarea algoritmului de verificare a condiției Delaunay prin ecuația cercului circumscris și aplicarea acestuia

• Procesarea imaginii ,
• Programare

Vă voi spune secretul cum să verificați rapid starea Delaunay pentru două triunghiuri.
De fapt, optimizarea în sine este descrisă puțin mai jos (vezi „Optimizarea algoritmului de verificare a condiției Delaunay prin ecuația cercului circumscris”), dar vă voi spune despre totul în ordine.

În cazul meu, triangulația este folosită în trasarea imaginii pentru a împărți planul în sectoare primitive (triunghiuri). După cum știți, este, de asemenea, împărțit în mai multe etape: ajustare, detectarea limitelor, ocolirea granițelor, măturarea contururilor. Acest lucru este în modul cel mai general. Aș vrea să mă opresc, cred, la cea mai grea etapă: măturarea avionului.

La intrare

După detectarea și ocolirea limitelor la ieșire, am obținut o mulțime de contururi externe. Fiecare contur atingere are o culoare diferită. Fiecare astfel de contur conține, de asemenea, un număr cunoscut de contururi interne.
Astfel, din punctul de vedere al „măturării planului”, dacă luăm în considerare separat contururile exterioare, avem un set de puncte, fiecare având câte un vecin în dreapta și în stânga. Acestea. toate punctele sunt închise în lanț, nu există un singur punct de „atârnare” și fiecare dintre lanțuri conține cel puțin 3 puncte (Figura 1).

Poza 1

Ce trebuie să faci

Este necesar să măturați figura cu triunghiuri.

Căutare

După ce am citit cartea, nu am găsit o singură (cel puțin una) modalitate de a construi o triangulație Delaunay care să fie cel puțin oarecum potrivită pentru cazul meu. Nu am căutat alte cărți. Da, și asta a fost suficient, mi-a pus în ordine gândurile capului. Drept urmare, și-a inventat propria „bicicletă”.

Algoritm

1) Să presupunem, pentru început, că există o singură secvență în figura luată în considerare. Apoi totul se reduce la luarea secvențială a triunghiurilor. Luăm orice punct și încercăm să construim un triunghi cu puncte învecinate. Dacă nu a fost posibil să se construiască un triunghi (linia care leagă aceste două puncte se intersectează cu cele deja construite sau linia trece în zona de excludere (Figura 2), trecem la punctul vecin, să spunem la dreapta. Când următorul se găsește triunghi, îl adăugăm în listă (Figura 3), iar punctul din care a fost construit este șters (Figura 4).

Figura 2

Figura 3

Figura 4

Încă un lucru: atunci când salvați următorul triunghi, este necesar să înregistrați vârfurile într-o ocolire în sensul acelor de ceasornic (în sistemul de coordonate corect). Acest lucru va fi util în viitor pentru a reduce resursele de calcul.

2) Repetați pasul 1 până când măturăm întregul avion.

3) Dacă există mai multe secvențe, de ex. unul, iar în interiorul acestuia se află unul sau mai multe contururi interne (Figura 1). Aici este necesar să se ia în considerare fiecare secvență separat. Să luăm un alt contur interior. Dintr-unul extern și unul intern vom realiza două contururi unice. Pentru a face acest lucru, trebuie să găsiți două „porturi” de la un circuit la altul. Condiția pentru „porturile”: nu trebuie să se intersecteze între ele (nu trebuie să atingă nici măcar capetele), nu trebuie să se intersecteze cu liniile de contur (Figura 5).

Figura 5

Figura 6
4) În continuare, ar trebui să introduceți pe rând toate secvențele interne în secvențele deja formate, separate unele de altele (punctul 3). Trebuie să fuzionați cu cel care îl conține pe cel nou. Prin definiție, nicio secvență internă nu atinge sau se intersectează cu altele (fie una externă, fie toate elementele interne posibile), așa că totul va decurge fără probleme.
După ce au găsit porturile (Figura 6), este ușor să construiți secvențe noi și să le ocoliți cu punctele 1 și 2 ale algoritmului curent (Figura 7).

Figura 7

5) După etapa a 4-a, avem o listă de triunghiuri (Figura 8). De parcă ne-am descurcat deja sarcinii, dar rămâne să facem imaginea frumoasă: verificați îndeplinirea condiției Delaunay (Figura 9).

Figura 8

Figura 9

6) Privind în viitor, vă voi spune despre al șaselea punct. Constă într-o parcurgere secvențială prin lista triunghiurilor primite de la punctul nr. 5. În primul rând, marchem toate triunghiurile ca „murdar”. În fiecare ciclu, verificăm condiția Delaunay pentru fiecare triunghi. Dacă condiția nu este îndeplinită, atunci reconstruim și marcăm vecinii și triunghiul curent ca „murdar”. Dacă condiția este îndeplinită, marcați-o curată. În implementarea mea a algoritmului, fiecare triunghi are o legătură cu vecinii săi. În acest caz, al 6-lea punct funcționează cel mai repede.

Mai multe despre etapa a cincea

Acum, din câte știu, există două modalități posibile de a determina dacă triunghiurile îndeplinesc sau nu condiția Delaunay: 1) Verificați suma unghiurilor opuse. Trebuie să fie mai mic de 180. 2) Calculați centrul cercului circumscris și calculați distanța până la al 4-lea punct. Toată lumea știe că condiția Delaunay este îndeplinită dacă punctul se află în afara cercului circumscris.

Puterea de calcul #1: 10 operații de înmulțire/împărțire și 13 operații de adunare/scădere.
Puterea de calcul #2: 29 de înmulțiri/diviziuni și 24 de adunări/scăderi.

Din punct de vedere al puterii de calcul, care este calculată, de exemplu, în carte, opțiunea numărul 1 este mai profitabilă. Și și-a dat seama, dacă nu pentru... (Figura 10). După cum s-a dovedit, după introducerea acestei metode pe „conveior”, a existat incertitudine. Aceasta este o opțiune când unghiul A în sine este mai mare de 180 de grade. Este tratată în carte ca una dintre metodele private separate. Și odată cu aceasta, toată eleganța, transparența și performanța ei dispar. Și, de asemenea, mai târziu s-a dovedit că metoda nr. 2 poate fi optimizată foarte semnificativ.

Figura 10

Optimizarea algoritmului de verificare a condiției Delaunay prin ecuația cercului circumscris

Ceea ce urmează este matematică pură.

Deci avem:
Verificarea condiției pentru punctul M(X, Y) prin ecuația unui cerc care trece prin punctele A(x1, y1), B(x2, y2), C(x3, y3) poate fi scrisă astfel:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ semn a ≥ 0

Detalii pot fi găsite în cartea excelentă. (Nu, nu sunt autorul)
Deci, semnul a este semnul direcției de traversare, de la bun început am construit triunghiuri în sensul acelor de ceasornic, astfel încât să poată fi omis (este egal cu unu).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D >= 0

Figura 11

Doar nu-i așa?

Conform cărții, din nou,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Avem: 15 operații de înmulțire/împărțire și 14 operații de adunare/scădere.

Vă mulțumim pentru atenție. Astept critici.

Bibliografie

1. Skvortsov A.V. Triangulația Delaunay și aplicarea acesteia. - Tomsk: Editura Vol. un-ta, 2002. - 128 p. ISBN 5-7511-1501-5 20 august 2012 la 22:41

Optimizarea algoritmului de verificare a condiției Delaunay prin ecuația cercului circumscris și aplicarea acestuia

Vă voi spune secretul cum să verificați rapid starea Delaunay pentru două triunghiuri.
De fapt, optimizarea în sine este descrisă puțin mai jos (vezi „Optimizarea algoritmului de verificare a condiției Delaunay prin ecuația cercului circumscris”), dar vă voi spune despre totul în ordine.

În cazul meu, triangulația este folosită în trasarea imaginii pentru a împărți planul în sectoare primitive (triunghiuri). După cum știți, este, de asemenea, împărțit în mai multe etape: ajustare, detectarea limitelor, ocolirea granițelor, măturarea contururilor. Acest lucru este în modul cel mai general. Aș vrea să mă opresc, cred, la cea mai grea etapă: măturarea avionului.

La intrare

După detectarea și ocolirea limitelor la ieșire, am obținut o mulțime de contururi externe. Fiecare contur atingere are o culoare diferită. Fiecare astfel de contur conține, de asemenea, un număr cunoscut de contururi interne.
Astfel, din punctul de vedere al „măturării planului”, dacă luăm în considerare separat contururile exterioare, avem un set de puncte, fiecare având câte un vecin în dreapta și în stânga. Acestea. toate punctele sunt închise în lanț, nu există un singur punct de „atârnare” și fiecare dintre lanțuri conține cel puțin 3 puncte (Figura 1).

Poza 1

Ce trebuie să faci

Este necesar să măturați figura cu triunghiuri.

Căutare

După ce am citit cartea, nu am găsit o singură (cel puțin una) modalitate de a construi o triangulație Delaunay care să fie cel puțin oarecum potrivită pentru cazul meu. Nu am căutat alte cărți. Da, și asta a fost suficient, mi-a pus în ordine gândurile capului. Drept urmare, și-a inventat propria „bicicletă”.

Algoritm

1) Să presupunem, pentru început, că există o singură secvență în figura luată în considerare. Apoi totul se reduce la luarea secvențială a triunghiurilor. Luăm orice punct și încercăm să construim un triunghi cu puncte învecinate. Dacă nu a fost posibil să se construiască un triunghi (linia care leagă aceste două puncte se intersectează cu cele deja construite sau linia trece în zona de excludere (Figura 2), trecem la punctul vecin, să spunem la dreapta. Când următorul se găsește triunghi, îl adăugăm în listă (Figura 3), iar punctul din care a fost construit este șters (Figura 4).

Figura 2

Figura 3

Figura 4

Încă un lucru: atunci când salvați următorul triunghi, este necesar să înregistrați vârfurile într-o ocolire în sensul acelor de ceasornic (în sistemul de coordonate corect). Acest lucru va fi util în viitor pentru a reduce resursele de calcul.

2) Repetați pasul 1 până când măturăm întregul avion.

3) Dacă există mai multe secvențe, de ex. unul, iar în interiorul acestuia se află unul sau mai multe contururi interne (Figura 1). Aici este necesar să se ia în considerare fiecare secvență separat. Să luăm un alt contur interior. Dintr-unul extern și unul intern vom realiza două contururi unice. Pentru a face acest lucru, trebuie să găsiți două „porturi” de la un circuit la altul. Condiția pentru „porturile”: nu trebuie să se intersecteze între ele (nu trebuie să atingă nici măcar capetele), nu trebuie să se intersecteze cu liniile de contur (Figura 5).

Figura 5

Figura 6
4) În continuare, ar trebui să introduceți pe rând toate secvențele interne în secvențele deja formate, separate unele de altele (punctul 3). Trebuie să fuzionați cu cel care îl conține pe cel nou. Prin definiție, nicio secvență internă nu atinge sau se intersectează cu altele (fie una externă, fie toate elementele interne posibile), așa că totul va decurge fără probleme.
După ce au găsit porturile (Figura 6), este ușor să construiți secvențe noi și să le ocoliți cu punctele 1 și 2 ale algoritmului curent (Figura 7).

Figura 7

5) După etapa a 4-a, avem o listă de triunghiuri (Figura 8). De parcă ne-am descurcat deja sarcinii, dar rămâne să facem imaginea frumoasă: verificați îndeplinirea condiției Delaunay (Figura 9).

Figura 8

Figura 9

6) Privind în viitor, vă voi spune despre al șaselea punct. Constă într-o parcurgere secvențială prin lista triunghiurilor primite de la punctul nr. 5. În primul rând, marchem toate triunghiurile ca „murdar”. În fiecare ciclu, verificăm condiția Delaunay pentru fiecare triunghi. Dacă condiția nu este îndeplinită, atunci reconstruim și marcăm vecinii și triunghiul curent ca „murdar”. Dacă condiția este îndeplinită, marcați-o curată. În implementarea mea a algoritmului, fiecare triunghi are o legătură cu vecinii săi. În acest caz, al 6-lea punct funcționează cel mai repede.

Mai multe despre etapa a cincea

Acum, din câte știu, există două modalități posibile de a determina dacă triunghiurile îndeplinesc sau nu condiția Delaunay: 1) Verificați suma unghiurilor opuse. Trebuie să fie mai mic de 180. 2) Calculați centrul cercului circumscris și calculați distanța până la al 4-lea punct. Toată lumea știe că condiția Delaunay este îndeplinită dacă punctul se află în afara cercului circumscris.

Puterea de calcul #1: 10 operații de înmulțire/împărțire și 13 operații de adunare/scădere.
Puterea de calcul #2: 29 de înmulțiri/diviziuni și 24 de adunări/scăderi.

Din punct de vedere al puterii de calcul, care este calculată, de exemplu, în carte, opțiunea numărul 1 este mai profitabilă. Și și-a dat seama, dacă nu pentru... (Figura 10). După cum s-a dovedit, după introducerea acestei metode pe „conveior”, a existat incertitudine. Aceasta este o opțiune când unghiul A în sine este mai mare de 180 de grade. Este tratată în carte ca una dintre metodele private separate. Și odată cu aceasta, toată eleganța, transparența și performanța ei dispar. Și, de asemenea, mai târziu s-a dovedit că metoda nr. 2 poate fi optimizată foarte semnificativ.

Figura 10

Optimizarea algoritmului de verificare a condiției Delaunay prin ecuația cercului circumscris

Ceea ce urmează este matematică pură.

Deci avem:
Verificarea condiției pentru punctul M(X, Y) prin ecuația unui cerc care trece prin punctele A(x1, y1), B(x2, y2), C(x3, y3) poate fi scrisă astfel:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ semn a ≥ 0

Detalii pot fi găsite în cartea excelentă. (Nu, nu sunt autorul)
Deci, semnul a este semnul direcției de traversare, de la bun început am construit triunghiuri în sensul acelor de ceasornic, astfel încât să poată fi omis (este egal cu unu).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D >= 0

Figura 11

Doar nu-i așa?

Conform cărții, din nou,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Avem: 15 operații de înmulțire/împărțire și 14 operații de adunare/scădere.

Vă mulțumim pentru atenție. Astept critici.

Bibliografie

1. Skvortsov A.V. Triangulația Delaunay și aplicarea acesteia. - Tomsk: Editura Vol. un-ta, 2002. - 128 p. ISBN 5-7511-1501-5

Pentru a cuantifica calitatea triangulației construite, definim două tipuri de criterii, topologic și geometric.

Criteriul topologic se bazează pe cei mai apropiati vecini ai unui punct dintr-o mulțime. În mod ideal, un punct are 6 vecini pentru o regiune 2D și 12 vecini pentru o regiune 3D. Obținem o estimare topologică folosind formula (1), unde este numărul total de puncte din regiune, este gradul sau numărul de puncte învecinate conectate cu un punct intern.

Criteriul geometric se bazează pe diferența dintre cercurile înscrise și circumscrise în jurul elementului triunghiular calculat. Obținem o estimare geometrică folosind formula (2), unde este numărul de triunghiuri, este raza cercului înscris, este raza cercului circumscris.

Algoritmi pentru construirea triangulației

Există un număr mare de algoritmi pentru construirea triangulației. Ele diferă unele de altele prin laboriozitate, complexitate a implementării pe un computer și abordări ale construcției. Puteți afla mai multe despre algoritmi în cartea lui A.V. Skvortsova. Să luăm în considerare câțiva algoritmi.

Una dintre primele propuse algoritm lacom construirea unei triunghiuri. O triangulație Delaunay se numește greedy dacă este construită folosind un algoritm greedy. Complexitatea algoritmului lacom cu unele dintre îmbunătățirile sale este de . Datorită unei complexități atât de mari în practică, nu este aproape niciodată folosit. Luați în considerare algoritmul pas cu pas:

Pasul 1. O listă cu toate segmentele de linie posibile care conectează perechile de puncte sursă este generată și sortată după lungimea segmentelor.

Pasul 2 Pornind de la cel mai scurt, segmentele sunt introduse secvenţial în triangulaţie. Dacă segmentul nu se intersectează cu alte segmente inserate anterior, atunci este inserat, în caz contrar este aruncat.

Rețineți că, dacă toate segmentele posibile au lungimi diferite, atunci rezultatul acestui algoritm este lipsit de ambiguitate, altfel depinde de ordinea de inserare a segmentelor de aceeași lungime.

Algoritm iterativ se bazează pe o idee foarte simplă de a adăuga succesiv puncte la o triangulație Delaunay parțial construită. Complexitatea acestui algoritm constă în complexitatea găsirii unui triunghi, la care se adaugă un punct la pasul următor, complexitatea construirii de noi triunghiuri, precum și complexitatea reconstrucției corespunzătoare a structurii de triunghi ca urmare a nesatisfăcătoarei verificări ale perechilor de triunghiuri învecinate ale triangulației rezultate pentru condiția Delaunay. Luați în considerare algoritmul pas cu pas:

Pasul 1. Pe primele trei puncte de plecare construim un triunghi.

Pasul 2În bucla pentru toate celelalte puncte, efectuați pașii 3-5.

Pasul 3 Următorul --lea punct este adăugat structurii de triangulație deja construită după cum urmează. În primul rând, punctul este localizat, adică. există un triunghi (construit mai devreme), în care se încadrează următorul punct. Sau, dacă punctul nu se încadrează în interiorul triangulației, există un triunghi pe marginea triunghiului care este cel mai aproape de punctul următor.

Pasul 4 Dacă un punct lovește un nod de triangulație inserat anterior, atunci un astfel de punct este de obicei eliminat, altfel punctul este inserat în triangulație ca un nou nod. Mai mult, dacă punctul atinge o margine, atunci este împărțit în două noi, iar ambele triunghiuri adiacente marginii sunt, de asemenea, împărțite în două mai mici. Dacă punctul se află strict în interiorul oricărui triunghi, acesta este împărțit în trei noi. Dacă punctul se află în afara triangulației, atunci se construiesc unul sau mai multe triunghiuri.

Pasul 5 Se efectuează verificări locale ale triunghiurilor nou obținute pentru conformitatea cu condiția Delaunay și se efectuează rearanjamentele necesare.

Când se construiesc noi triunghiuri, sunt posibile două situații când punctul adăugat se află fie în interiorul triunghiului, fie în afara acesteia. În primul caz, se construiesc noi triunghiuri și se fixează numărul de acțiuni efectuate de algoritm. În cel de-al doilea, este necesar să se construiască triunghiuri suplimentare exterioare triangulației curente, iar numărul lor poate fi egal în cel mai rău caz? 3. Cu toate acestea, nu se vor adăuga mai mult de triunghiuri pentru toți pașii algoritmului, unde este numărul total de puncte inițiale. Prin urmare, în ambele cazuri, timpul total petrecut pentru construirea triunghiurilor este.

Algoritm de lanț unul dintre primii algoritmi eficienți de construcție a triangulației se bazează pe o procedură de regularizare a unui graf plan și pe triangularea poligonului monoton. Complexitatea acestui algoritm este, unde este numărul de segmente inițiale. Luați în considerare algoritmul pas cu pas:

Pasul 1. Din mulțimea segmentelor structurale inițiale, formăm un grafic planar conex (Figura 4, a).

Pasul 2 Graficul este regularizat, i.e. se adaugă muchii noi care nu se intersectează pe altele, astfel încât fiecare vârf al graficului devine adiacent cu cel puțin un vârf deasupra lui și unul sub acesta. Regularizarea se face în două treceri folosind o măturare plată verticală. În prima trecere de jos în sus, găsim secvenţial toate vârfurile din care nu există muchii care să conducă în sus. De exemplu, pe (Figura 4, b) acesta este vârful B. Trasând o linie orizontală, găsim cele mai apropiate muchii ale graficelor AD și EF traversate de acesta în stânga și în dreapta. Apoi găsim cel mai de jos vârf din patrulaterul DEHG și tragem în el o margine din B. În mod similar, a doua trecere este efectuată de sus în jos (Figura 4, c). Ca urmare a acestui pas, fiecare zonă a graficului plan devine un poligon monoton.

Pasul 3 Fiecare zonă a graficului trebuie împărțită în triunghiuri. Pentru a face acest lucru, puteți utiliza algoritmul de îmbinare neconvexă a două triangulații (Figura 4, d).

Figura 4. Schema de funcționare a algoritmului lanțului de triangulație: a) - segmente inițiale; b - trecerea de jos în sus a regularizării graficului; c) - trecere de sus în jos; d) - triangularea poligoanelor monotone

Pentru a implementa algoritmul în lanț, cel mai bine este să folosiți structuri de date în care marginile sunt reprezentate explicit, cum ar fi „Muchii duble” sau „Noduri, margini și triunghiuri”.

Dezavantajul algoritmului în lanț este că nu se poate spune nimic în avans despre forma triangulației rezultate. Aceasta nu este o triangulare optimă, nu una lacomă și nu o triangulare Delaunay constrânsă. Algoritmul lanțului poate produce triunghiuri alungite foarte lungi.

Pentru a îmbunătăți calitatea triangulației rezultate, toate perechile de triunghiuri adiacente neseparate de o muchie structurală pot fi verificate pentru îndeplinirea condiției Delaunay și, dacă este necesar, reconstruite. Ca urmare, se va obține o triangulație Delaunay cu restricții.

Modelele GRID sunt modele de celule obișnuite.

Lasă sistemul de coordonate
și și
. Seturi de utilizatori
și etapele de eșantionare
.

,

- coordonatele fizice ale punctului.

calculati
și
,
- grilă de biți.

- valori cuantificate. Real:

- parametrul algoritm - numărul de puncte, - greutatea. Cu cât punctul este mai aproape, cu atât greutatea este mai mare.

- gradul de distanta (1 sau 2).

Factorul de normalizare:

Cum mai aproape de 1, cu atât punctele mai ponderate sunt luate în considerare.

Aceasta este metoda IDW - lungă, pentru fiecare t este necesar să găsiți vecini. Un set de vecini poate fi găsit eficient - cel mai apropiat. Fiecare dintre puncte produce o „cuieță” de o anumită înălțime. Depinde mult de neregularitatea stabilirii punctului, pentru asta iau
sau
acestea. împărțiți în sectoare și construiți în vecinătatea punctului.

Avantaj– simplitate

Defect:

------Biletul 14. Tin-model. Algoritmi de triangulare Delaunay ------

1) Triunghiulare (staniu).

Triangulaţie– construcția unei funcții sub forma unui set de funcții liniare pe bucăți

Triangulaţie– interpolare în interiorul regiunii convexe.

Triangulaţie este un grafic plan, ale cărui muchii interioare sunt triunghiuri; un mod de a reprezenta spațiul sub formă de triunghiuri alăturate între ele fără a se suprapune. Triangulația este construită pe un set de puncte în mai multe moduri.

Avem nevoie de un algoritm pentru a construi o triangulație optimă.

Un avion care trece prin 3 puncte.

1) Găsiți un triunghi care
;

2)
- construim ecuația planului.

Pentru a verifica dacă punctele sunt sau nu în interiorul triunghiului, trebuie să înlocuiți valoarea în ecuația liniilor - marginile triunghiului. Dacă toate cele 3 ecuații > 0, atunci în interior.

Vedeți structura:

Fiecare triunghiulare conține același număr de triunghiuri.

, Unde este numărul de puncte interne,
- suma de puncte.

Triangulație lacomă.

Conectăm toate punctele cu margini, selectăm minimul, adăugăm la triangulație. În continuare, luăm următorul minim care nu se intersectează cu precedentele și așa mai departe. Rezultatul este o triangulare lacomă.

Triangulația Delaunay.

Punctele altor triunghiuri nu se încadrează în interiorul unui cerc circumscris oricărui triunghi. Construit într-un singur fel.

Un flip este un flip de margini. Vă permite să treceți de la triangulația convențională la triangulația Delaunay. Pentru a verifica dacă un punct aparține unui cerc: înlocuiți dacă< R, то внутри.

starea Delaunay.

Ecuația unui cerc care trece prin trei puncte:

Dacă este mai mic decât zero, atunci extern, în caz contrar - intern.

este condiția Delaunay.

Algoritmul pentru construirea triangulației Delaunay:

1) În curs de investigare adăugând puncte este un algoritm iterativ simplu:

Există un set
adăugați la triunghi, construcția este efectuată
împărțirea unui triunghi
reconstruind. În stadiul zero, adăugăm 3-4 puncte fictive care ne acoperă evident plicul, toate punctele sunt înăuntru. După ce aruncăm un punct, ne uităm la ce triunghi a lovit, îl împărțim în 3, pentru fiecare triunghi verificăm starea Delaunay și răsturnăm marginile. Numărul mediu de reconstrucții este de trei.

Complexitatea teoretică

2) Metode de accelerare. Pe baza punctelor dependente statistic. Triunghiul sămânță este triunghiul în care a căzut punctul anterior. Apoi conectăm două puncte - cel anterior și cel nou.

Trecem de la primul punct la altul.

(Dezvoltarea și implementarea algoritmilor pentru triangulații cu volum constrâns: algoritmi iterativi
Preprint, Inst. Aplic. Math., Academia Rusă de Științe)

Galanin M.P., Shcheglov I.A.
(M.P.Galanin, I.A.Sheglov)

IPM-i. M.V. Keldysh RAS

Moscova, 2006
Această lucrare a fost susținută de Fundația Rusă pentru Cercetare de bază (Proiectul nr. 06-01-00421)

adnotare

Sunt luate în considerare metode iterative de discretizare tridimensională a domeniilor spațiale (construcția rețelelor tetraedrice): metode de corecție a limitelor, metode bazate pe criteriul Delaunay și metode de epuizare. Sunt date variante de algoritmi pentru fiecare dintre aceste metode. Sunt discutate caracteristicile construcției de grile în domenii complexe.

Abstract

Sunt descrise trei familii principale de algoritmi iterativi pentru triangularea simplă a volumului liberă și constrânsă: corecția limitei (inclusiv algoritmul „octree”), metodele bazate pe Delaunay și abordarea frontală avansată. Pentru fiecare tip de metodă este dat un exemplu de algoritm.

1. Introducere 3

2. Metode de corectare a limitelor4

2.1 Construcția rețelei primare4

2.2 Corectarea grilei primare6

3. Metode bazate pe criteriul Delaunay9

3.1 Construirea unei triangulații Delaunay pe un set dat de puncte 12

3.2. Triangularea Delaunay cu restricții17

3.3 Caracteristici ale implementării tehnice a algoritmilor bazați pe
criteriul Delaunay 22

4. Metode de epuizare23

4.1 Exemplu de algoritm de epuizare26

Referințe 3 0

1. Introducere

Dintre cele două clase de metode de triangulare - directă și iterativă - acestea din urmă au suficientă universalitate și, prin urmare, spre deosebire de cele directe, pot fi folosite pentru a triangula regiuni de o formă destul de arbitrară. Această versatilitate vine cu prețul unui consum semnificativ mai mare de resurse și al unei implementări mai intensive a metodei într-un anumit algoritm.

În prezent, un număr mare de pachete software au fost dezvoltate pe baza uneia sau alteia metode iterative care implementează construcția de grile (parțial sau complet) în mod automat. Practic, aceste pachete sunt comerciale, ceea ce este destul de justificat având în vedere efortul depus pentru crearea lor, deoarece spațiul tridimensional are o serie de caracteristici neplăcute care complică semnificativ viața dezvoltatorului.

Ochiurile construite prin metode iterative sunt de obicei nestructurate și neomogene. Nestructurarea se datorează faptului că topologia rețelei se formează în procesul de construcție și, prin urmare, poate varia în mod natural chiar și în cadrul aceluiași subdomeniu. Din același motiv, omogenitatea, dacă poate apărea, este doar întâmplător.

Deoarece nu se poate spune nimic despre structura sa viitoare înainte de construirea plasei, nici calitatea acesteia nu poate fi garantată. Adesea, rețeaua construită poate fi îmbunătățită semnificativ folosind una dintre numeroasele tehnici de optimizare. Această posibilitate nu este de obicei neglijată, deoarece timpul alocat optimizării, de regulă, este semnificativ mai mic decât timpul alocat construirii.

Scopul acestei lucrări este de a revizui și clasifica metodele existente de construire a rețelelor tetraedrice în domenii tridimensionale. Având în vedere cantitatea considerabilă de informații, mai jos sunt luate în considerare doar așa-numitele „metode iterative”. Metodele directe sunt descrise în .

Această lucrare a fost susținută parțial de Fundația Rusă pentru Cercetare de bază (Proiectul nr. 06-01-00421).

Orez. 11. Triangularea unui domeniu reprezentând unirea unui dodecaedru și a unui icosaedru (triangulație Delaunay cu restricții)

Calitatea ochiurilor construite prin această metodă este la un nivel mediu (tetraedrele din apropierea granițelor pot avea o formă foarte slabă), așa că de obicei se recurge suplimentar la una dintre metodele de optimizare.

În lucrările lui B. Joe, sunt propuse și alte variante ale algoritmului care nu folosesc puncte suplimentare și se bazează complet pe transformări locale similare cu „comerț”.

4) volumul tetraedrului nu este mai mare decât maximul admis ().

Dintre toate tetraedrele () se selectează tetraedrul de cea mai bună calitate și se face trecerea la pasul 5; dacă nu există tetraedre care să îndeplinească condițiile indicate, atunci se realizează trecerea la pasul 4.

4. Există un astfel de punct în interiorul regiunii încă inepuizabile încât:

1) tetraedrul () îndeplinește toate condițiile alin. 3;

2) într-o minge nu există niciun punct îndepărtatF(acest lucru împiedică plasarea noduluip prea aproape de feţele şi vârfurile tetraedrelor existente).

O variantă a algoritmului de căutare a nodurilorpdiscutat mai jos.

5. Eliminați toate vârfurileF, căzând în interiorul (și pe granițele) tetraedrului format. Apoi frontul se actualizează după următoarea schemă: se consideră fiecare față a tetraedrului format și

1) dacă fața este o față frontală, atunci este îndepărtată din față;

2) dacă fața NU este o față frontală, se adaugă față.

6. Dacă mai sunt puncte neșterseFsau (ceea ce este echivalent) frontul nu este gol (adică regiunea nu a fost încă complet epuizată), se realizează trecerea la pasul 1, altfel procesul s-a încheiat.

Deci matriceaFeste folosit în mai multe scopuri simultan: pentru a estima valoarea unghiului solid, pentru a controla corectitudinea construcției și pentru a controla plasarea noilor noduri. De asemenea, o matriceFutil pentru indicarea progresului. Raportul dintre numărul de puncte eliminate în timpul funcționării algoritmuluiFla numărul inițial de puncte existenteFarată de fapt cât de mult din zonă este deja epuizată.

Să revenim la întrebarea de a găsi coordonatele unui nou nod pentru construirea unui tetraedru (articolul 4 al algoritmului descris). Să fie date trei noduri.

1. La prima etapă, găsim - centrul de masă al triunghiului (ca medie aritmetică a coordonatelor nodurilor sale) și unitatea normală la planul feței (prin produsul vectorial normalizat).

2. În continuare, se determină prima aproximare pentru distanța de la punctul doritp (H), pe baza volumului maxim al tetraedrului: . Rețineți că zona fețeiSgăsit efectiv la pasul anterior (rezultatul produsului încrucișat a două margini este egal cu de două ori suprafața feței), iar volumul maxim este determinat de valoarea funcției de control.

3. Punctul este verificat. Dacă tetraedrul () îndeplinește toate cerințele, mergeți la pasul 6, în caz contrar treceți la pasul 4.

4. Punctul este verificat. Dacă tetraedrul () îndeplinește toate cerințele, mergeți la pasul 6, în caz contrar treceți la pasul 5.

5. Crede și treceți la pasul 3.

6. Se găsește nodul dorit.

Rețineți că în 99% din cazuri punctul dorit este situat la 1 sau 2 iterații ale acestui algoritm.

În algoritmul de epuizare descris mai sus, un tetraedru este îndepărtat din regiune la fiecare pas. Angajatul NASA Sh. Pirzade ( Shahyar Pirzadeh ) a propus o altă versiune a algoritmului, în care un întreg strat de tetraedre este îndepărtat dintr-o dată din regiune (adică, la fiecare iterație, tetraedre sunt construite imediat pentru toate fețele frontului curent) . Contrar așteptărilor, această variantă nu accelerează semnificativ procesul de construcție (deoarece toate tetraedrele noi mai trebuie verificate pentru corectitudine), dar elimină nevoia de a căuta cea mai potrivită față pentru construirea unui tetraedru. Acesta este însă mai degrabă un minus decât un plus, deoarece datorită acestei caracteristici, varianta Pirzade este mai puțin fiabilă și poate eșua în zonele complexe din punct de vedere geometric. În același timp, arată rezultate bune în zone relativ simple.

Ochiurile construite prin metode de epuizare, de regulă, au o calitate bună, iar optimizarea ulterioară a poziției nodurilor oferă o creștere suplimentară a calității. Rezumând, observăm că metodele de epuizare sunt cele mai eficiente dacă triangularea limitei zonei este stabilită inițial. Aceasta este principala lor diferență față de metodele bazate pe criteriul Delaunay, pentru care situația este direct opusă.

Bibliografie

1. Shaydurov V.V. Metode cu elemente finite multigrid. - M., Nauka, 1989. - 288s.

2. Skvortsov A.V. Prezentare generală a algoritmilor pentru construirea triangulației Delaunay // , 2002, №3, c. 14-39.

3. Skvortsov A.V. Algoritmi pentru construirea unei triangulații cu restricții // Metode de calcul și programare, 2002, №3, c. 82-92.

4. I.Babushka, W.C. Rheinboldt. Estimări de eroare a posteriori pentru metoda elementului finit // Int. J. Numer. Meth. ing., Vol. 12, p.p. 1597-1615, 1978.

5. T.J. Brutar. Generarea automată a rețelelor pentru regiuni tridimensionale complexe folosind o triangulație Delaunay constrânsă // Inginerie cu calculatoare, Springer-Verlag, nr. 5, p.p. 161-175, 1989.

6. M. Berna, D. Eppstein. Generarea rețelei și triangularea optimă // Calcul în geometrie euclidiană, World Scientific Publishing Co., p.p. 23-90, 1995.

7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Reprezentări compacte ale rețelelor simple în două și trei dimensiuni // Proceedings of the 12th International Meshing Roundtable, Laboratoarele Naționale Sandia, p.p.135-146, sept. 2003.

8. H. Borouchaki, S.H. Iată. Triangulație rapidă Delaunay în trei dimensiuni // Metode computerizate în mecanică și inginerie aplicată, Elsevier, voi. 128, p.p. 153-167, 1995.

9. E.K. Buratynski. Un generator de plase nestructurat tridimensional pentru limite interne arbitrare // Generarea de grile numerice în mecanica fluidelor computaționale, Pineridge Press, p.p. 621-631, 1988.

10. RELATII CU PUBLICUL. Cavalcanti, U.T. Mello. Triangulația Delaunay constrânsă tridimensională: o abordare minimalistă // Proceedings of the 8th International Meshing Round Table, p.p. 119-129, 1999.

11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Triangulații Delaunay în trei dimensiuni cu aritmetică de precizie finită // Proiectare geometrică asistată de calculator, Olanda de Nord, nr. 9, p.p. 457-470, 1992.

12. H.N. Djidjev. Metode direcționate prin forță pentru netezirea rețelelor triunghiulare și tetraedrice nestructurate // Proceedings of the 9th International Meshing Roundtable, Laboratoarele Naționale Sandia, p.p. 395-406, octombrie 2000.

13. L. Durbeck. Evaporarea: O tehnică pentru vizualizarea calității rețelei // Proceedings of the 8th International Meshing Roundtable, South Lake Tahoe, CA, S.U.A., p.p. 259-265, octombrie 1999.

14. D.A. camp. Netezirea Laplaciană și Triangulațiile Delaunay // , vol. 4, p.p. 709-712, 1988.

15. PIJAMALE. Frey, H. Borouchaki, P.-L. George. Tetraedralizarea Delaunay folosind o abordare frontală // Proceedings of the 5th International Meshing Roundtable, Laboratoarele Naționale Sandia, p.p. 31-46, octombrie 1996.

16. LA. Freitag, C. Ollivier-Gooch. O comparație a tehnicilor de îmbunătățire a rețelei tetraedrice // Proceedings of the 5th International Meshing Roundtable, Laboratoarele Naționale Sandia, p.p. 87-106, octombrie 1996.

17. LA. Freitag, C. Ollivier-Gooch. Îmbunătățirea rețelei tetraedrice prin schimbarea și netezirea // , vol. 40, p.p. 3979-4002, 1995.

18. LA. Freitag, C. Ollivier-Gooch. Efectul calității rețelei asupra eficienței soluției // Proceedings of the 6th International Meshing Roundtable, Laboratoarele Naționale Sandia, p.p.249, octombrie 1997.

19. P.L. George. TET MESHING: Construcție, Optimizare și Adaptare // Procesul din 8Masa rotundă internațională Mesh, p.p.133-141, 1999.

20. N / A. Golias, T.D. Tsiboukis. O abordare a rafinarii rețelelor tetraedrice tridimensionale pe baza transformărilor Delaunay // , John Wiley, nr. 37, p.p.793-812, 1994.

21. C. Hazlewood. Aproximarea tetraedralizărilor constrânse // Proiectare geometrică asistată de calculator, vol. 10, p.p. 67–87, 1993.

22. B. Joe. Ochiuri triunghiulare Delaunay în poligoane convexe, SIAM J Sci. stat. Calculator., Vol. 7, p.p. 514-539, 1986.

23. B. Joe. Construirea triunghiurilor tridimensionale Delaunay folosind transformări locale // Proiectare geometrică asistată de calculator, Vol. 8, p.p. 123-142, 1991.

24. B. Joe. Construirea de triangulații tridimensionale de calitate îmbunătățită folosind transformări locale // Siam J. Sc. Calculator., vol. 16, p.p. 1292-1307, 1995.

25. R.W. Lewis, Yao Zheng, D.T. Gethin. Generarea de rețele nestructurate tridimensionale: partea 3. Rețele de volum // Metode computerizate în mecanică și inginerie aplicată, Elsevier, Vol 134, p.p. 285-310, 1996.

26. A. Liu, B. Joe. Despre forma tetraedrelor din bisectie // Matematica calculului, vol. 63, nr. 207, 141–154, 1994.

27. SH. Iată. Discretizarea volumului în tetraedre-I. Verificarea și orientarea suprafețelor limită // Calculatoare și Structuri, Pergamon Press, voi. 39, nr.5, p.p. 493-500, 1991.

28. SH. Iată. Discretizarea volumului în tetraedre - II. Triangulare 3D prin avansarea abordării frontale // Calculatoare și Structuri, Pergamon, voi. 39, nr.5, p.p. 501-511, 1991.

29. R. Lohner. Generarea de grile tridimensionale nestructurate prin metoda frontului de avansare // Proceedings of the 26th AIAA Aerospace Sciences Meeting, Reno, Nevada, 1988.

30. S.J. Owen. Un studiu asupra tehnologiei de generare a plaselor nestructurate // Proceedings of the 7th International Meshing Roundtable, p.p. 239-269, Dearborn, MI, 1998.

31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. O comparație a măsurilor de calitate a tetraedrului // Elemente finite în analiză și proiectare, Elsevier, nu. 15, p.p. 255-261, 1993.

32. S. Pirzadeh. Generarea rețelei vâscoase nestructurate prin metoda straturilor în avans // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.

33. V.T. Rajan. Optimitatea triangulației Delaunay în // Proc. Al 7-lea ACM Symp. Comp. geometrie, p.p. 357-363, 1991.

34. A. Rassineux. Generarea și optimizarea rețelelor tetraedrice prin avansarea tehnicii frontale // Jurnalul Internațional pentru Metode Numerice în Inginerie, Wiley, Vol. 41, p.p. 651-674, 1998.

35. S. Rebay. Generare eficientă a rețelei nestructurate prin triangularea Delaunay și algoritmul Bowyer-Watson // Jurnalul de fizică computațională, vol. 106, p.p. 125-138, 1993.

36. M.-C. Rivara. Algoritmi selectivi de rafinare/definire pentru secvențe de triangulații imbricate // Jurnalul Internațional pentru Metode Numerice în Inginerie, nr. 28, p.p. 2889-2906, 1998.

37. M.-C. Rivara, C. Levin. Un algoritm de rafinare 3D potrivit pentru tehnici adaptive și multigrid // Comunicări în metode numerice aplicate, nr. 8, p.p. 281-290, 1998.

38. J. Ruppert. Un algoritm de rafinare Delaunay pentru generarea de ochiuri bidimensionale de calitate // Jurnalul de algoritmi, nr. 18, p.p. 548-585, 1995.

39. DOMNIȘOARĂ. Ciobanesc, M.K. Georges. Generarea de plase tridimensionale prin tehnica Finite Octree // Jurnalul Internațional pentru Metode Numerice în Inginerie, vol. 32, p.p. 709-749, 1991.

40. DOMNIȘOARĂ. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Generare de rețea octree finită pentru analiza fluxului 3D adaptivă automată // Generarea de grile numerice în mecanica fluidelor computaționale Miami, 1988

41. K. Shimada, D.C. Gossard. Bubble Mesh: Îmbinare triunghiulară automată a geometriei fără colectoare prin sferă de ambalare // Proceduri ale Al 3-lea simpozion de modelare solidă și aplicații , p.p. 409-419, 1995.

42. K. Shimada, A. Yamada, T. Itoh. Îmbinarea triunghiulară anizotropă a suprafețelor parametrice prin ambalarea strânsă a bulelor elipsoidale // Proceedings of the 6th International Meshing Roundtable, p.p. 375-390, 1997.

43. D.F. Watson. Calcularea teselării Delaunay cu aplicare la politopii Voronoi // Jurnalul Calculatoarelor, Vol. 24(2), p.p. 167-172, 1981.

44. M.A. Yerry, M.S. Păstor. Generarea de plase tridimensionale prin tehnica Octree modificată // Jurnalul Internațional pentru Metode Numerice în Inginerie, Vol. 20, p.p. 1965-1990, 1984.

45. Galanin M.P., Shcheglov I.A. Dezvoltarea și implementarea algoritmilor pentru triangularea tridimensională a regiunilor spațiale complexe: metode directe. IPM preprint im. M.V. Keldysh RAN, 2006, în presă. puncte, adică Noduri Steiner - noduri suplimentare care nu au fost incluse în setul original

Poate părea că condiția 2 rezultă din condiția 3, dar de fapt nu este. De exemplu, un tetraedru existent poate fi în întregime interiortetraedru testat.