Egyszerű poligon

A Wikipédiából, a szabad enciklopédiából
Egy egyszerű konkáv hexagon
Egy nem-egyszerű (komplex) pentagon.

Geometriában egyszerű poligonnak nevezzük az olyan poligonokat, melyek oldalai nem keresztezik egymást. Egy egyszerű poligon tehát egy zárt poligonháló melynek szakaszai nem metszik egymást. Az egyszerű poligon kifejezéssel gyakran utalnak csak az alakzat körvonalára.

Az egyszerű poligonokat gyakran hívják Jordan-poligonoknak is, mivel a Jordan-féle görbetétel szerint egy ilyen poligon a síkot két részre osztja, a belső és a külsőre. Egy egyszerű poligon a síkban topologikusan izomorf egy körrel, míg a belseje egy körlappal.

A nem-egyszerű poligonokat a geometristák önmetsző poligonoknak, 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 | forrásszöveg szerkesztése]

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. Ugyanazen algoritmus segítségével az is eldönthető hogy egy zárt poligonlá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.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Software[szerkesztés | forrásszöveg szerkesztése]

  • 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.

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Software[szerkesztés | forrásszöveg szerkesztése]