Egyszerű sokszög
Geometriában egyszerű sokszögnek nevezzük az olyan sokszögeket, melyek oldalai nem keresztezik egymást. Egy egyszerű sokszög tehát egy zárt töröttvonal (vonallánc), melynek szakaszai nem metszik egymást. Az egyszerű sokszög kifejezésből az „egyszerű” gyakran kimarad, és gyakran az előbbi definíciót tekintik sokszögnek.
Az egyszerű sokszögek néhány tulajdonsága:
- A sokszög magába zárja a síknak egy részét (ezt nevezik a sokszög belsejének), aminek minden esetben mérhető a területe.
- A sokszöget alkotó töröttvonalak (oldalak vagy élek) kizárólag a végpontokban találkoznak, ezek a sokszög csúcsai vagy sarkai.
- Minden csúcsban pontosan két él találkozik.
- Az élek száma mindig megegyezik a csúcsok számával.
Az egyszerű sokszögeket gyakran hívják Jordan-sokszögeknek is, mivel a Jordan-féle görbetétel szerint egy ilyen sokszög a síkot két részre osztja, a belső és a külsőre. Egy egyszerű sokszög a síkban topologikusan izomorf egy körrel, míg a belseje egy körlappal.
A nem egyszerű sokszögeket a geometriában önmetsző sokszögeknek, a grafikusok pedig komplex poligonoknak nevezik. Az ilyen poligonoknak nem feltétlenül van egyértelmű belső és külső része.
Felhasználások a számítógépes geometria területén
[szerkesztés]A számítógépes geometriában sok fontos feladat közt szerepel egy poligon mint input megadása; az ilyen feladatoknál a poligon belső és külső területei közti különbségtétel elengedhetetlen.
- Egy P egyszerű poligon és egy q pont esetén eldöntendő, hogy q P belsejében van-e vagy sem.
- Egyszerű képletek ismertek a poligonok területének meghatározására, azaz a belső területének kiszámolására.
- Poligon felosztás: egy egyszerű poligon háromszögekre osztása. Ez komplex poligonok esetében egyszerűbb feladat, ugyanis az egyszerű poligonoknál vigyáznunk kell, hogy ne adjunk hozzá extra éleket, vagyis hogy a háromszögek élei rendre a poligon belsejében fussanak. Bernard Chazelle 1991-ben megmutatta, hogy bármely n csúcsú egyszerű poligon felosztható háromszögekre Θ(n) időben, ami optimális. Ugyanezen algoritmus segítségével az is eldönthető hogy egy zárt vonallánc egyszerű poligont határoz-e meg.
- Poligon unió: egy vagy több egyszerű poligon keresése, mely(ek) belső területe megegyezik két másik (melyek metszők is lehetnek) egyszerű poligon területével.
- Poligon metszet: egy vagy több egyszerű poligon keresése, mely(ek) területe megegyezik két másik egyszerű poligon metszetének területével.
Kapcsolódó szócikkek
[szerkesztés]Software
[szerkesztés]- GPC General Polygon Clipper Library, egy C++ könyvtár, mely poligonok közti műveletek (különbség, metszet, unió) kiszámolására alkalmas. Használható C, C#, Delphi, Java, Perl, Python, Haskell, Lua, VB.Net programokkal.
További információk
[szerkesztés]- comp.graphics.algorithms FAQ, mely 2 és 3 dimenziós poligonokkal kapcsolatos problémákra sorol fel megoldásokat.