Enkel polygon
En enkel polygon är en figur som består av icke-korsande segment ("sidor") kopplade i par för att bilda en sluten bana. Om sidorna skär varandra är polygonen inte enkel. Ofta utelämnas ordet "enkelt" från definitionen ovan.
Ovanstående definition ger följande egenskaper hos formen:
- Polygonen omger ett område (kallat inre) som alltid har en mätbar area.
- Linjesegmenten som bildar en polygon (kallas sidor, mer sällan kanter) skär varandra endast vid sina ändpunkter, som kallas hörn (eller, mindre formellt, "hörn").
- Exakt två sidor möts vid varje vertex.
- Antalet sidor är alltid lika med antalet hörn.
Det krävs vanligtvis att två sidor som möts i en vertex inte bildar en rak (180°) vinkel. Annars anses sidorna som ligger på samma räta linje vara en del av samma sida.
Matematiker använder i allmänhet termen "polygon" endast för figurer som bildas av linjesegment, inklusive interiören. Vissa använder emellertid termen "polygon" för att hänvisa till en platt figur som begränsas av en sluten bana som består av en ändlig sekvens av segment (det vill säga en sluten polylinje ). Beroende på vilken definition som används kan en gräns vara en del av en polygon eller inte [1] .
Enkla polygoner kallas också Jordans polygoner , eftersom Jordans sats kan användas för att bevisa att sådana polygoner delar upp planet i två regioner, inuti och utanför. En polygon i planet är enkel om och bara om den är topologiskt ekvivalent med en cirkel . Dess inre är topologiskt likvärdigt med en cirkel .
Svagt enkel polygon
Om en uppsättning icke-korsande segment bildar gränsen för en domän i planet, topologiskt ekvivalent med en cirkel, så kallas denna gräns för en svagt enkel polygon [2] . I figuren till vänster är ABCDEFGHJKLM en svagt enkel polygon per definition. Blått representerar det område för vilket en svagt enkel polygon är gränsen. Den här typen av svagt enkla polygoner kan förekomma i datorgrafik och CAD -system som en datorrepresentation av polygonområden med kaviteter – för varje kavitet skapas ett "snitt" för att ansluta till den yttre gränsen. Enligt figuren är ABCM den yttre gränsen för den platta regionen med FGHJ-kaviteten. Den skurna ED förbinder kaviteten med den yttre konturen och korsas två gånger i en svagt enkel polygonrepresentation.
En alternativ och mer allmän definition av svaga enkla polygoner är gränsen för en sekvens av enkla polygoner av samma kombinatoriska typ som konvergerar i Fréchet-avståndet [3] . Detta formaliserar tanken att elementen i en polygon tillåts röra, men inte korsa. Den här typen av svagt enkla polygoner utgör dock inte nödvändigtvis gränsen för en region, eftersom "insidan" kan vara tom. Till exempel, i kedjefiguren är ABCBA en svagt enkel polygon - den kan betraktas som "utpressningsgränsen" för polygonen ABCFGHA.
Datorproblem
I beräkningsgeometri använder några viktiga beräkningsproblem en enkel polygoningång. I var och en av dessa uppgifter är skillnaden mellan inne och ute nyckeln [4]
- Problemet med huruvida en punkt tillhör en polygon kräver att man avgör om punkten q är i det inre av polygonen P .
- Enkla formler är kända för att beräkna arean av en polygon , det vill säga det inre området.
- En partition av en polygon är en uppsättning elementära enheter (till exempel kvadrater) som inte skär varandra och vars förening bildar en polygon. Uppgiften med att partitionera en polygon är att hitta en partition som är minimal i någon mening. Till exempel en partition med ett minsta antal enheter eller med en minsta total längd på sidorna.
- Ett specialfall för att dela en polygon är polygontrianguleringsproblemet, som är uppdelningen av en enkel polygon i trianglar. Även om konvexa polygoner är lätta att triangulera, är triangulering av allmänna enkla polygoner svårare eftersom du måste undvika att lägga till kanter som skär utanför polygonen. Bernhard Chazelle 1991 visade dock att vilken enkel polygon som helst med n hörn kan trianguleras på optimal tid Θ ( n ). Samma algoritm kan användas för att avgöra om en sluten streckad linje bildar en enkel polygon.
- Booleska operationer på polygoner – olika booleska operationer på den uppsättning punkter som definieras av polygonernas inre områden.
- Det konvexa skrovet för en enkel polygon kan beräknas mer effektivt än det konvexa skrovet för andra typer av indata, såsom en uppsättning punkter.
- Voronoi diagram av en enkel polygon
- Medianaxel / topologiskt skelett / rätlinjigt skelett av en enkel polygon
- Parallell kurva för en enkel polygon
- Minkowski summa för enkla polygoner
Se även
Anteckningar
- ↑ Grünbaum, 2003 .
- ↑ Dumitrescu, Toth, 2007 , sid. 177.
- ↑ Chang, Erickson, Xu, 2015 , sid. 1655–1670
- ↑ comp.graphics.algorithms FAQ Arkiverad 13 februari 2011 på Wayback Machine med en lista över lösningar på matematiska problem med 2D- och 3D-polygoner.
Litteratur
- Branko Grünbaum . Konvexa polytoper / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2:a. - New York, London: 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, Tyskland, 22-24 februari 2007, Proceedings / Wolfgang Thomas, Pascal Weil. — illustrerad. - Springer, 2007. - ISBN 3540709177 .
- Hsien-Chih Chang, Jeff Erickson, Chao Xu. Handlingar från det tjugosjätte årliga ACM-SIAM-symposiet om diskreta algoritmer (SODA'15). — 2015.
Länkar