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 algoritmusAdott 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
Forgásirány függvényGeometriai 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 |