Poligon simplu
Un poligon simplu este o figură constând din segmente neintersectate („laturi”) conectate în perechi pentru a forma o cale închisă. Dacă laturile se intersectează, poligonul nu este simplu. Adesea, cuvântul „simplu” este omis din definiția de mai sus.
Definiția de mai sus oferă următoarele proprietăți ale formei:
- Poligonul înconjoară o regiune (numită interior) care are întotdeauna o zonă măsurabilă.
- Segmentele de linie care formează un poligon (numite laturi, mai rar muchii) se intersectează doar la punctele lor de capăt, care sunt numite vârfuri (sau, mai puțin formal, „colțuri”).
- Exact două laturi se întâlnesc la fiecare vârf.
- Numărul de laturi este întotdeauna egal cu numărul de vârfuri.
De obicei, este necesar ca două laturi care se întâlnesc la un vârf să nu formeze un unghi drept (180°). În caz contrar, laturile situate pe aceeași linie dreaptă sunt considerate parte a aceleiași laturi.
Matematicienii folosesc în general termenul „poligon” numai pentru figurile formate din segmente de linie, fără a include interiorul. Cu toate acestea, unii folosesc termenul „poligon” pentru a se referi la o figură plată delimitată de o cale închisă constând dintr-o succesiune finită de segmente (adică o polilinie închisă ). În funcție de definiția utilizată, o chenar poate fi sau nu parte dintr-un poligon [1] .
Poligoanele simple sunt numite și poligoane Jordan , deoarece teorema lui Jordan poate fi folosită pentru a demonstra că astfel de poligoane împart planul în două regiuni, în interior și în exterior. Un poligon în plan este simplu dacă și numai dacă este echivalent topologic cu un cerc . Interiorul său este echivalent topologic cu un cerc .
Poligon slab simplu
Dacă o mulțime de segmente care nu se intersectează formează granița unui domeniu în plan, echivalent topologic cu un cerc, atunci această limită se numește poligon slab simplu [2] . În figura din stânga, ABCDEFGHJKLM este un poligon slab simplu prin definiție. Albastrul reprezintă regiunea pentru care un poligon slab simplu este granița. Acest tip de poligoane slab simple pot apărea în grafica computerizată și sistemele CAD ca o reprezentare computerizată a zonelor poligonale cu cavități - pentru fiecare cavitate este creată o „tăietură” pentru a se conecta la limita exterioară. Conform figurii, ABCM este limita exterioară a regiunii plate cu cavitatea FGHJ. ED tăiat conectează cavitatea la conturul exterior și este traversat de două ori într-o reprezentare slab simplă a poligonului.
O definiție alternativă și mai generală a poligoanelor simple slabe este limita unei secvențe de poligoane simple de același tip combinatoric care converg în distanța Fréchet [3] . Aceasta formalizează ideea că elementele unui poligon au voie să se atingă, dar nu să se traverseze. Cu toate acestea, acest tip de poligon slab simplu nu formează neapărat granița unei regiuni, deoarece „interiorul” poate fi gol. De exemplu, în figura lanțului, ABCBA este un poligon slab simplu - poate fi considerat limita de „strângere” a poligonului ABCFGHA.
Probleme de calcul
În geometria computațională, unele probleme de calcul importante folosesc o intrare simplă de poligon. În fiecare dintre aceste sarcini, distincția dintre interior și exterior este cheia [4]
- Problema dacă un punct aparține unui poligon necesită determinarea dacă punctul q se află în interiorul poligonului P .
- Sunt cunoscute formule simple pentru calcularea ariei unui poligon , adică a zonei interioare.
- O partiție a unui poligon este un set de unități elementare (de exemplu, pătrate) care nu se intersectează și a căror unire formează un poligon. Sarcina de a partiționa un poligon este de a găsi o partiție care este minimă într-un anumit sens. De exemplu, o partiție cu un număr minim de unități sau cu o lungime totală minimă a laturilor.
- Un caz special de împărțire a unui poligon este problema triangulației poligonului, care este împărțirea unui poligon simplu în triunghiuri. Deși poligoanele convexe sunt ușor de triangulat, triangularea poligoanelor generale simple este mai dificilă, deoarece trebuie să evitați adăugarea marginilor care se intersectează în afara poligonului. Cu toate acestea, Bernhard Chazelle în 1991 a arătat că orice poligon simplu cu n vârfuri poate fi triangulat în timp optim Θ ( n ). Același algoritm poate fi folosit pentru a determina dacă o linie întreruptă închisă formează un poligon simplu.
- Operații booleene pe poligoane — diverse operații booleene pe setul de puncte definit de zonele interioare ale poligoanelor.
- Corpul convex al unui poligon simplu poate fi calculat mai eficient decât corpul convex pentru alte tipuri de intrare, cum ar fi un set de puncte.
- Diagrama Voronoi a unui poligon simplu
- Axa mediană / schelet topologic / schelet rectiliniu al unui poligon simplu
- Curba paralelă a unui poligon simplu
- Suma Minkowski pentru poligoane simple
Vezi și
Note
- ↑ Grünbaum, 2003 .
- ↑ Dumitrescu, Toth, 2007 , p. 177.
- ↑ Chang, Erickson, Xu, 2015 , p. 1655–1670
- ↑ comp.graphics.algorithms Întrebări frecvente Arhivat 13 februarie 2011 la Wayback Machine cu o listă de soluții la probleme de matematică cu poligoane 2D și 3D.
Literatură
- Branko Grünbaum . Politopuri convexe / Volker Kaibel, Victor Klee, Günter M. Ziegler. — al 2-lea. - New York, Londra: Springer-Verlag , 2003. - ISBN 0-387-00424-6 .
- Adrian Dumitrescu, Csaba D. Toth. STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germania, 22-24 februarie 2007, Proceedings / Wolfgang Thomas, Pascal Weil. — ilustrat. - Springer, 2007. - ISBN 3540709177 .
- Hsien-Chih Chang, Jeff Erickson, Chao Xu. Actele celui de-al douăzeci și șaselea Simpozion anual ACM-SIAM despre algoritmi discreti (SODA'15). — 2015.
Link -uri