Poligon simplu - Simple polygon
În geometrie , un poligon simplu / p ɒ l ɪ ɡ ɒ n / este un poligon care nu se intersectează în sine și nu are găuri. Adică, este o formă plană formată din segmente de linie drepte, care nu se intersectează sau „laturi” care sunt unite în perechi pentru a forma o singură cale închisă . Dacă laturile se intersectează, poligonul nu este simplu. Calificativul „simplu” este omis frecvent, definiția de mai sus fiind apoi înțeleasă pentru a defini un poligon în general.
Definiția dată mai sus asigură următoarele proprietăți:
- Un poligon cuprinde o regiune (numită interiorul său) care are întotdeauna o zonă măsurabilă .
- Segmentele de linie care alcătuiesc un poligon (numite laturi sau margini) se întâlnesc doar la punctele lor finale, numite vârfuri (singular: vârf) sau mai puțin formal „colțuri”.
- Exact două margini se întâlnesc la fiecare vârf.
- Numărul de muchii este întotdeauna egal cu numărul de vârfuri.
Două margini întâlnite la un colț sunt de obicei necesare pentru a forma un unghi care nu este drept (180 °); în caz contrar, segmentele de linie coliniară vor fi considerate părți ale unei singure laturi.
Matematicienii folosesc de obicei „poligon” pentru a se referi doar la forma alcătuită din segmentele de linie, nu regiunea închisă, totuși unii pot folosi „poligon” pentru a se referi la o figură plană care este delimitată de o cale închisă, compusă dintr-o secvență finită a segmentelor de linie dreaptă (adică, printr-un lanț poligonal închis ). Conform definiției utilizate, această limită poate sau nu să facă parte din poligon în sine.
Poligoanele simple se mai numesc și poligoane Jordan , deoarece teorema curbei Jordan poate fi utilizată pentru a demonstra că un astfel de poligon împarte planul în două regiuni, regiunea din interiorul său și regiunea din afara acestuia. Un poligon în plan este simplu dacă și numai dacă este echivalent topologic cu un cerc . Interiorul său este echivalent topologic cu un disc .
Poligon slab simplu
Dacă o colecție de segmente de linie care nu se încrucișează formează granița unei regiuni a planului echivalentă topologic cu un disc, atunci această graniță se numește un poligon slab simplu . În imaginea din stânga, ABCDEFGHJKLM este un poligon slab simplu conform acestei definiții, cu culoarea albastră care marchează regiunea pentru care este granița. Acest tip de poligon slab simplu poate apărea în grafica computerizată și CAD ca reprezentare computerizată a regiunilor poligonale cu găuri: pentru fiecare gaură este creată o "tăietură" pentru a-l conecta la o graniță externă. Referindu-ne la imaginea de mai sus, ABCM este o limită externă a unei regiuni plane cu o gaură FGHJ. ED tăiat conectează orificiul cu exteriorul și este traversat de două ori în reprezentarea poligonală slab simplă rezultată.
Într-o definiție alternativă și mai generală a poligoanelor slab simple, acestea sunt limitele secvențelor de poligoane simple de același tip combinator, cu convergența sub distanța Fréchet . Acest lucru oficializează noțiunea că un astfel de poligon permite segmentelor să atingă, dar să nu treacă. Cu toate acestea, acest tip de poligon slab simplu nu trebuie să formeze granița unei regiuni, deoarece "interiorul" său poate fi gol. De exemplu, referindu-ne la imaginea de mai sus, lanțul poligonal ABCBA este un poligon slab simplu conform acestei definiții: poate fi privit ca limita de „stoarcere” a poligonului ABCFGHA.
Probleme de calcul
În geometria de calcul , mai multe sarcini de calcul importante implică intrări sub forma unui poligon simplu; în fiecare dintre aceste probleme, distincția dintre interior și exterior este crucială în definirea problemei.
- Punct în poligon de testare implică determinarea, pentru un poligon simplu P și un punct de interogare q , dacă q minciuni interior la P .
- Formulele simple sunt cunoscute pentru calculul ariei poligonului ; adică zona interiorului poligonului.
-
Partiția poligonului este un set de unități primitive (de exemplu pătrate), care nu se suprapun și a căror unire este egală cu poligonul. O problemă de partiție poligon este o problemă a găsirii unei partiții care este minimă într-un anumit sens, de exemplu: o partiție cu un număr mic de unități sau cu unități cu cea mai mică lungime laterală totală.
- Un caz special al partiției poligonului este Triangularea poligonului : împărțirea unui poligon simplu în triunghiuri. Deși poligoanele convexe sunt ușor de triangulat, triangularea unui poligon simplu general este mai dificilă, deoarece trebuie să evităm adăugarea muchiilor care se încrucișează în afara poligonului. Cu toate acestea, Bernard Chazelle a arătat în 1991 că orice poligon simplu cu n vârfuri poate fi triangulat în timp Θ ( n ), ceea ce este optim. Același algoritm poate fi folosit și pentru a determina dacă un lanț poligonal închis formează un poligon simplu.
- Un alt caz special este problema galeriei de artă , care poate fi reformulată în mod echivalent ca o partiție într-un număr minim de poligoane în formă de stea .
- Operații booleene pe poligoane : Diverse operații booleene pe seturile de puncte definite de regiuni poligonale.
- Convexă a unui poligon simplu se poate calcula mai eficient decât coca convexe a altor tipuri de intrări, cum ar fi corpul navei convexe a unui set punct.
- Diagrama Voronoi a unui poligon simplu
- Medial axa / topologică schelet / schelet drept un simplu poligon
- Curba de decalaj a unui poligon simplu
- Suma Minkowski pentru poligoane simple