Egyszerű sokszög
Az egyszerű sokszög olyan alakzat, amely nem metsző szakaszokból ("oldalakból") áll, amelyek páronként zárt pályát alkotnak. Ha az oldalak metszik egymást, a sokszög nem egyszerű. Az "egyszerű" szót gyakran kihagyják a fenti definícióból.
A fenti definíció az ábra következő tulajdonságait biztosítja:
- A sokszög egy olyan régiót (az úgynevezett belsőt) vesz körül, amelynek mindig van mérhető területe.
- A sokszöget alkotó szakaszok (úgynevezett oldalak, ritkábban élek) csak a végpontjaikban metszik egymást, amelyeket csúcsoknak (vagy kevésbé formálisan "saroknak") neveznek.
- Minden csúcsban pontosan két oldal találkozik.
- Az oldalak száma mindig megegyezik a csúcsok számával.
Általában előírják, hogy két, egy csúcsban találkozó oldal ne alkosson egyenes (180°-os) szöget. Ellenkező esetben az ugyanazon az egyenesen fekvő oldalak ugyanazon oldal részének tekintendők.
A matematikusok általában csak a vonalszakaszok által alkotott ábrákra használják a "sokszög" kifejezést, nem számítva a belsőt. Néhányan azonban a "sokszög" kifejezést olyan lapos alakzatra használják, amelyet egy véges szakaszok sorozatából álló zárt út határol ( vagyis egy zárt vonallánc ). A használt definíciótól függően egy szegély lehet egy sokszög része vagy nem [1] .
Az egyszerű sokszögeket Jordan poligonoknak is nevezik , mivel Jordan tétele felhasználható annak bizonyítására, hogy az ilyen sokszögek két részre osztják a síkot, belül és kívül. Egy sokszög a síkban akkor és csak akkor egyszerű, ha topológiailag ekvivalens egy körrel . Belseje topológiailag egy körnek felel meg .
Gyengén egyszerű sokszög
Ha nem metsző szakaszok halmaza alkotja egy tartomány határát a síkban, topológiailag egy körrel ekvivalens, akkor ezt a határt gyengén egyszerű sokszögnek nevezzük [2] . A bal oldali ábrán az ABCDEFGHJKLM definíció szerint gyengén egyszerű sokszög. A kék azt a régiót jelöli, amelynek egy gyengén egyszerű sokszög a határa. Az ilyen típusú gyengén egyszerű sokszögek előfordulhatnak számítógépes grafikában és CAD -rendszerekben üreges sokszögű területek számítógépes ábrázolásaként - minden üreghez egy "vágás" jön létre, amely a külső határhoz kapcsolódik. Az ábra szerint az ABCM a lapos régió külső határa az FGHJ üreggel. A vágott ED összeköti az üreget a külső kontúrral, és kétszer áthalad egy gyengén egyszerű sokszög ábrázolásban.
A gyenge egyszerű sokszögek alternatív és általánosabb definíciója az azonos kombinatorikus típusú egyszerű sokszögek sorozatának határa, amelyek a Fréchet távolságban konvergálnak [3] . Ez formalizálja azt az elképzelést, hogy egy sokszög elemei érintkezhetnek, de nem keresztezhetik egymást. Ez a fajta gyengén egyszerű sokszög azonban nem feltétlenül képezi egy régió határát, mivel a „belső” üres lehet. Például a láncábrán az ABCBA egy gyengén egyszerű sokszög - az ABCFGHA sokszög „kiszorítási” határának tekinthető.
Számítástechnikai problémák
A számítási geometriában néhány fontos számítási probléma egyszerű sokszög bemenetet használ. Ezen feladatok mindegyikében kulcsfontosságú a belső és a külső különbségtétel [4]
- Annak a problémának, hogy egy pont egy sokszöghez tartozik-e, meg kell határozni, hogy a q pont a P sokszög belsejében van-e .
- Egyszerű képletek ismertek egy sokszög területének , azaz a belső területének kiszámítására.
- A sokszög partíciója olyan elemi egységek (például négyzetek) halmaza, amelyek nem metszik egymást, és amelyek uniója sokszöget alkot. A sokszög particionálásának feladata egy bizonyos értelemben minimális partíció megtalálása. Például egy partíció minimális számú egységgel vagy minimális teljes oldalhosszúsággal.
- A sokszög felosztásának speciális esete a sokszög háromszögelési probléma, amely egy egyszerű sokszög háromszögekre történő felosztása. Bár a konvex sokszögeket könnyű háromszögelni, az általános egyszerű sokszögek háromszögelése nehezebb, mert kerülni kell a sokszögön kívül metsző élek hozzáadását. Bernhard Chazelle 1991-ben azonban kimutatta, hogy bármely egyszerű, n csúcsú sokszög háromszögezhető optimális Θ ( n ) idő alatt. Ugyanez az algoritmus használható annak meghatározására, hogy egy zárt szaggatott vonal egyszerű sokszöget alkot-e.
- Boole-műveletek sokszögeken – különféle logikai műveletek a sokszögek belső területei által meghatározott ponthalmazokon.
- Egy egyszerű sokszög konvex héja hatékonyabban számítható ki, mint a konvex burok más típusú bemenetek, például egy pontkészlet esetén.
- Voronoi diagram egy egyszerű sokszögről
- Középtengely / topológiai váz / egyszerű sokszög egyenes vonalú váza
- Egy egyszerű sokszög párhuzamos görbéje
- Minkowski összeg egyszerű sokszögekre
Lásd még
Jegyzetek
- ↑ Grünbaum, 2003 .
- ↑ Dumitrescu, Tóth, 2007 , p. 177.
- ↑ Chang, Erickson, Xu, 2015 , p. 1655–1670
- ↑ comp.graphics.algorithms GYIK Archiválva : 2011. február 13. a Wayback Machine -nél a 2D-s és 3D-s poligonokkal kapcsolatos matematikai feladatok megoldásainak listájával.
Irodalom
- Branko Grünbaum . Konvex politópok / Volker Kaibel, Victor Klee, Günter M. Ziegler. — 2. - New York, London: Springer-Verlag , 2003. - ISBN 0-387-00424-6 .
- Adrian Dumitrescu, D. Tóth Csaba. STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Németország, 2007. február 22-24., Proceedings / Wolfgang Thomas, Pascal Weil. — illusztrálva. - Springer, 2007. - ISBN 3540709177 .
- Hsien-Chih Chang, Jeff Erickson, Chao Xu. A huszonhatodik éves ACM-SIAM szimpózium a diszkrét algoritmusokról (SODA'15) anyaga. — 2015.
Linkek