Konvex burok meghatározása

A feladat

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. 

Szokásos mese a konvex burokhoz: A pontok egy asztallapba vert szögek, ekkor a konvex burkot meghatározza a szögekre szoruló befőttes gumi.

Például:
A konvex burok meghatározására több hatékony algoritmus létezik, az egyiket Graham-pásztázásnak szokás nevezni. 

Graham-pásztázás

Az algoritmus vázlata

  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. Ha kettőnél több pont esik egy egyenesre, akkor a legalsó (előbb kiválasztott) ponttól mért távolság szerint rendezzük őket, tehát előbb jön az, aki közelebb van  "piros" ponthoz.

  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. Ezt a lépést ismételni kell mindaddig, amíg az aktuálisan megmaradt utolsó három pont megfelelő nem lesz. A rendezés miatt biztosan bekövetkezik ez az állapot, ha van legalább három pont a halmazban.

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