Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

26. óra

Síkbeli ponthalmazok konvex burkának meghatározásával foglalkozunk. Az ismert algoritmusok közül Graham pásztázását beszéljük meg.

Konvex burok algoritmus

Adott N pont a síkon és keressük azt a legkisebb konvex sokszöget, ami mindegyik pontot tartalmazza. A legkisebb jelző a területre vonatkozik, de bizonyíthatóan azt is jelenti, hogy az összes - a ponthalmazt magában foglaló - konvex sokszög részhalmazként a konvex burkot is tartalmazza. 

Például:
Graham algoritmusa a következő lépésekből áll
  1. Kiinduló csúcs megkeresése
    A legalsó csúcsból fogunk indulni. Ha több legalsó van, akkor a "legbaloldalibbat" választjuk.


  2. Rendezés forgásirány szerint
    A kiválasztott kiinduló csúcsból "nézve" rendezzük a többi pontot forgásirány szerint.

  3. Pásztázás a rendezés szerint
    A kiinduló csúcsból indulva és a rendezés szerint sorba véve a többi csúcsot egyesével döntünk a pontokról. Egyszerre mindig három pontot vizsgálunk, és az "új" pontról eldöntjük, hogy ha bevennénk a konvex burokba, akkor a benne végződő él "balra" vagy "jobbra" fordulna az előző élhez képest.
    3.a
    Bal kanyarnál felvesszük az új pontot a konvex burokba.
    3.b
    Jobb kanyar esetén a három vizsgált pont közül a középső nem tartozik a konvex burokhoz.
     

Forgásirány függvény

Geometriai algoritmusokban gyakran kell eldöntenünk, hogy az ABC háromszög körüljárása negatív vagy pozitív, vagyis azt, hogy a BC vektor az AB vektorhoz képest jobbra vagy balra kanyarodik. Ezt legegyszerűbben a vektoriális szorzás segítségével számolhatjuk ki.

Egy lehetséges megfogalmazás: A forgásirány függvény ( fi(P,Q,R) ) értéke 1, ha a P pont a Q-R szakasztól balra esik; 0, ha vele egy egyenesre esik; illetve -1, ha tőle jobbra esik.

Függvény fi(P,Q,R)

cr:=(R.x-Q.x)*(P.y-Q.Y)-(P.x-Q.x)*(R.y-Q.y)
Ha cr < 0 
    akkor fi := -1
    különben 
        Ha cr>0 
                akkor fi := 1 
                különben fi := 0
        Elágazás vége
Elágazás vége

Függvény vége

Feladat