Triangularea Delaunay constrânsă

În geometria algoritmică^⁠(d) 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ă, $e$ , 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 $e$ , astfel încât vizibilitatea oricărui vârf interior al cercului să fie blocată față de cel puțin un capăt al $e$ 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 $O(n\log n)$ .^[1]^[3] Triangularea Delaunay constrânsă a unui poligon simplu poate fi construită în timp liniar.^[4]

Aplicații

Triangulare a unei suprafețe formate dintr-un cilindru și suprafața

x 4 + y 4 + z 4 = 1

. Dacă suprafețele ar fi date prin puncte, nu prin ecuații, într-o triangulare Delaunay linia lor de intersecție ar trebui impusă.

Î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 rafinare Delaunay^⁠(d) la generarea unei rețele^⁠(d), ca o modalitate de a forța rețeaua să se conformeze frontierelor domeniului rafinat pe măsură ce este rafinată.

Note

^ ^a ^b ^c en Chew, L. Paul (1989), „Constrained Delaunay triangulations”, Algorithmica, 4 (1): 97–108, doi:10.1007/BF01553881, MR 0983658
^ ^a ^b en Shewchuk, Jonathan Richard (2008), „General-dimensional constrained Delaunay and constrained regular triangulations. I. Combinatorial properties”, Discrete & Computational Geometry, 39 (1–3): 580–637, doi:10.1007/s00454-008-9060-3  , MR 2383774
^ en Wang, Cao An; Schubert, Lenhart K. (1987), „An optimal algorithm for constructing the Delaunay triangulation of a set of line segments”, În Soule, D., Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, ACM, pp. 223–232, doi:10.1145/41958.41982
^ en Chin, Francis; Wang, Cao An (1999), „Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time”, SIAM Journal on Computing, 28 (2): 471–486, doi:10.1137/S0097539795285916, hdl:10722/47094  , MR 1634357

Legături externe

Portal Matematică

en CDT Open Source implementation.

[chew-1] Chew, L. Paul (1989), „Constrained Delaunay triangulations”, Algorithmica, 4 (1): 97–108, doi:10.1007/BF01553881, MR 0983658

[shewchuk-2] Shewchuk, Jonathan Richard (2008), „General-dimensional constrained Delaunay and constrained regular triangulations. I. Combinatorial properties”, Discrete & Computational Geometry, 39 (1–3): 580–637, doi:10.1007/s00454-008-9060-3  , MR 2383774

[3] Wang, Cao An; Schubert, Lenhart K. (1987), „An optimal algorithm for constructing the Delaunay triangulation of a set of line segments”, În Soule, D., Proceedings of the Third Annual Symposium on Computational Geometry, Waterloo, Ontario, Canada, June 8-10, 1987, ACM, pp. 223–232, doi:10.1145/41958.41982

[4] Chin, Francis; Wang, Cao An (1999), „Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear time”, SIAM Journal on Computing, 28 (2): 471–486, doi:10.1137/S0097539795285916, hdl:10722/47094  , MR 1634357

[1]

[2]

[3]

[4]