SGI-algoritmus
Az SGI-algoritmus háromszögek halmazából hivatott háromszögsávokat előállítani. C nyelven publikálta K. Akeley, P. Haeberli és D. Burns az IEEE Visualization ’96 Proceedings című kiadványának 319–326. oldalán 1996-ban. Programjuk neve "tomesh.c" volt, és Silicon Graphics IRIS GL API-t használt.[1]
Az algoritmus háromszögek egy halmazán dolgozik, mely halmaz elemei még nem szerepelnek egy háromszögsávban sem; kezdetben ez a teljes bemeneti halmazt jelenti. A háromszögeket mohó módon adja hozzá háromszögsávokhoz mindaddig, míg már nem talál olyan háromszöget, melyet az aktuális sávhoz fűzhetne. Ez esetben új sávot kezd. Kezdéskor, illetve egy más meglévő sáv folytatásánál a következő háromszög kiválasztása a háromszög fokszáma (azaz a vele szomszédos háromszögek száma) alapján történik; az algoritmus a kisebb fokszámú háromszöget részesíti előnyben.
Amennyiben az új sávok indításakor a kezdő háromszög kiválasztását prioritási sor segíti, az algoritmus lineáris időben fut.[1]
Jegyzetek
szerkesztésFordítás
szerkesztésEz a szócikk részben vagy egészben a SGI algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
