Triangularea Delaunay constrânsă
În Format:Ill-wd triangularea Delaunay constrânsă este o variantă a triangulării Delaunay, care forțează drept laturi anumite segmente necesare la triangulare,[1][2] spre deosebire de triangularea Delaunay în sine, care se bazează exclusiv pe poziția unei mulțimi de vârfuri date, indiferent de modul în care acestea ar trebui conectate prin laturi. Poate fi calculată eficient și are aplicații în sistemele de informații geografice și în generarea de rețele.
Definiție
La o triangulare Delaunay constrânsă datele de intrare formează un graf planar cu muchii drepte, o mulțime de puncte și segmente care nu se intersectează în plan. Triangularea Delaunay constrânsă a acestei intrări este o triangulare a înfășurătoarei sale convexe, utilizând toate segmentele din intrare ca laturi (muchii) și folosind doar vârfurile din intrare. Pentru fiecare latură suplimentară, Format:Mvar, adăugată la această intrare pentru a o transforma într-o triangulare, ar trebui să existe un cerc care trece prin punctele de la capetele lui Format:Mvar, astfel încât vizibilitatea oricărui vârf interior al cercului să fie blocată față de cel puțin un capăt al Format:Mvar de un segment din intrare. Acest lucru generalizează proprietatea definitorie a triangulărilor Delaunay bidimensionale de puncte, că fiecare latură are un cerc care trece prin cele două capete ale sale fără a trece prin alte vârfuri. Întotdeauna există o triangulare care satisface aceste proprietăți.[1]
Jonathan Shewchuk a generalizat această definiție la triangulări Delaunay constrânse în cazul intrărilor tridimensionale, sisteme de puncte și segmente neintersectate și triunghiuri în spațiul tridimensional. Totuși, nu orice intrare de acest tip are o triangulare Delaunay constrânsă conform definiției sale generalizate.[2]
Algoritmi
Se cunosc mai mulți algoritmi pentru calcularea triangulărilor Delaunay constrânse ale grafurilor planare cu muchii drepte în timp .[1][3] Triangularea Delaunay constrânsă a unui poligon simplu poate fi construită în timp liniar.[4]
Aplicații
În ridicările topografice se construiește o triangulare din punctele trasate pe teren. Dacă o latură a triangulării traversează un râu, suprafața rezultată nu modelează cu precizie traseul râului. Pentru a remedia acest lucru se desenează linii de rupere de-a lungul râurilor, marginilor drumurilor, crestelor munților și a altor asemenea elemente. Aceste linii de rupere sunt folosite drept constrângeri la construirea triangulării.
Triangularea Delaunay constrânsă poate fi folosită și în metodele de Format:Ill-wd la Format:Ill-wd, ca o modalitate de a forța rețeaua să se conformeze frontierelor domeniului rafinat pe măsură ce este rafinată.
Note
Legături externe
- Format:En icon CDT Open Source implementation.