Enkel polygon - Simple polygon
I geometri , en enkel polygon / p ɒ l ɪ ɡ ɒ n / er en mangekant som ikke skjærer seg selv og ikke har noen hull. Det vil si at det er en flat form som består av rette, ikke kryssende linjesegmenter eller "sider" som sammenføyes parvis for å danne en enkelt lukket bane. Hvis sidene krysser hverandre, er polygonen ikke enkel. Kvalifikatoren "enkel" blir ofte utelatt, med definisjonen ovenfor forstås å definere en polygon generelt.
Definisjonen gitt ovenfor sikrer følgende egenskaper:
- En polygon omslutter en region (kalt dens indre) som alltid har et målbart område .
- Linjesegmentene som utgjør en polygon (kalt sider eller kanter) møtes bare ved endepunktene, kalt hjørner (entall: toppunkt) eller mindre formelt "hjørner".
- Nøyaktig to kanter møtes ved hvert toppunkt.
- Antall kanter er alltid lik antall hjørner.
To kanter som møtes ved et hjørne kreves vanligvis for å danne en vinkel som ikke er rett (180 °); Ellers vil de linjære linjesegmentene betraktes som deler av en enkelt side.
Matematikere bruker vanligvis "polygon" for å referere bare til formen som består av linjesegmentene, ikke det lukkede området, men noen kan bruke "polygon" for å referere til en plan figur som er avgrenset av en lukket bane, sammensatt av en endelig sekvens av rette linjesegmenter (dvs. ved en lukket mangekantet kjede ). I henhold til definisjonen i bruk, kan denne grensen utgjøre en del av selve polygonen.
Enkle polygoner kalles også Jordan-polygoner , fordi Jordan-kurvesetningen kan brukes til å bevise at en slik polygon deler planet i to regioner, regionen i den og regionen utenfor den. En polygon i planet er enkel hvis og bare hvis den tilsvarer topologisk en sirkel . Interiøret tilsvarer topologisk en disk .
Svakt enkel polygon
Hvis en samling av ikke-kryssende linjesegmenter danner grensen til et område av planet som er topologisk ekvivalent med en disk, så kalles denne grensen en svakt enkel polygon . På bildet til venstre er ABCDEFGHJKLM en svakt enkel polygon i henhold til denne definisjonen, med fargen blå som markerer regionen det er grensen for. Denne typen svakt enkel polygon kan oppstå i datagrafikk og CAD som en datamaskinrepresentasjon av polygonale regioner med hull: for hvert hull opprettes et "kutt" for å koble det til en ytre grense. Med henvisning til bildet ovenfor er ABCM en ytre grense for en plan region med et hull FGHJ. Den kuttede ED forbinder hullet med utsiden og krysses to ganger i den resulterende svakt enkle polygonale representasjonen.
I en alternativ og mer generell definisjon av svakt enkle polygoner, er de grensene for sekvenser av enkle polygoner av samme kombinatoriske type, med konvergens under Fréchet-avstanden . Dette formaliserer forestillingen om at en slik polygon tillater segmenter å berøre, men ikke krysse. Imidlertid trenger denne typen svakt enkel polygon ikke å danne grensen til en region, da dens "indre" kan være tom. For eksempel, med henvisning til bildet ovenfor, er den polygonale kjeden ABCBA en svakt enkel polygon i henhold til denne definisjonen: den kan sees på som grensen for "klemming" av polygonen ABCFGHA.
Beregningsproblemer
I beregningsgeometri involverer flere viktige beregningsoppgaver innganger i form av en enkel polygon; i hvert av disse problemene er skillet mellom interiør og eksteriør avgjørende i problemdefinisjonen.
- Punkt i polygon -testing involverer å bestemme, for en enkel polygon P og en spørring punkt q , enten q ligger innvendig til P .
- Enkle formler er kjent for å beregne polygonområdet ; det vil si området av polygonets indre.
-
Polygonpartisjon er et sett med primitive enheter (f.eks. Firkanter), som ikke overlapper hverandre og hvis forening er lik polygonet. Et polygonpartisjonsproblem er et problem med å finne en partisjon som er minimal i noen forstand, for eksempel: en partisjon med det minste antall enheter eller med enheter med den minste totale sidelengden.
- Et spesielt tilfelle av polygonpartisjon er Polygon-triangulering : deling av en enkel polygon i trekanter. Selv om konvekse polygoner er enkle å triangulere, er det vanskeligere å triangulere en generell enkel polygon fordi vi må unngå å legge til kanter som krysser utenfor polygonen. Likevel viste Bernard Chazelle i 1991 at ethvert enkelt polygon med n hjørner kan trianguleres på Θ ( n ) tid, noe som er optimalt. Den samme algoritmen kan også brukes for å bestemme om en lukket polygonal kjede danner en enkel polygon.
- Et annet spesielt tilfelle er kunstgalleriproblemet , som kan omformuleres tilsvarende som en partisjon til et minimum antall stjerneformede polygoner .
- Boolske operasjoner på polygoner : Ulike boolske operasjoner på settene med punkter definert av polygonale regioner.
- Det konvekse skroget til en enkel polygon kan beregnes mer effektivt enn det konvekse skroget til andre typer innganger, for eksempel det konvekse skroget til et punktsett.
- Voronoi-diagram over en enkel polygon
- Medial akse / topologisk skjelett / rett skjelett av en enkel polygon
- Offset kurve av en enkel polygon
- Minkowski sum for enkle polygoner
