Сецкање линија
У области рачунарска графика, сецекање линија је процес који елиминише линије или делове линија које се не налазе у области интереса. Тако да било која линија или део ње који се не налази у тој области бива одстрањен.
Постоје два класична алгоритма за сецкање линија: Коен-Садерленд алгоритам и Лианг-Барски алгоритам.
Метода сецкања линија се састоји из различитих делова. Прво можемо да тестирамо одређен сегмент линије да бисмо отркили да ли лежи потпуно ван области интереса. Мора се гледати постојање раскрсница тј пресека линија.[1]
Линија се процесуира унутар области као и споља тако што се гледају где се линије завршавају. Линија чија се оба завршетка налазе унутар области се чува, а линија којој се један или оба крају завршавају ван области интереса мора да се дање процесуира јер није могућа моментална процена њене тачне локације због могућности постојања неколико раскрсница.
Коен–Садерланд уреди
Ово је један од алгоритама за сецакње линија. Алгоритам дели дводимензиони простор на 9 мањих регија, од којих је само средњи део, тачка погледа, видљив.
1967. симулација авионског лета Денија Коена је довела до развоја Коен–Садерландовог алгоритма који ради дводимензионим и тродимензионим алгоритмима које је креирао Иван Садерланд.
Лианг–Барски уреди
Овај алгоритам користи параметричну једначину линије и неједнакости која описује распон прозора за сецкање да би се дефинисала раскрсница између линије и прозора за сецкање. Помоћу ових раскрсница алгоритам зна који део линије треба да се нацрта. Овај алгоритам је ефикаснији од Коен-Садерланд-овог алгоритма. Идеја Лианд – Барски алгоритма је да се ради што више тесирања пре рачунања раскрсница.
Сајрус–Бек уреди
Овај алгоритам је врло сличан претходном (Лианг–Барски). Разлика је у томе што је Лианг–Барски поједностављена варијација Сајрус–Бек- овог алгоритма који врши оптимизацију за правоугаони прозор за сецкање.
Сајрус – Бек има сложеност O(N), и примарно је намењен за сецкање линије у параметричном облику која се налази на конвексном многоуглу у две димензије или полиедра у три димензије.[2]
Нишол–Ли–Нишол уреди
Овај алгоритам је брз алгоритам за цескање линија који смањује шансе сецкања сегмената исте линије из неколико пута, као што може да се деси у Коен – Садерладовом алгоритму. Прозор за сецкање се дели на неколико различитих области, у зависности од позиције почетне тачке линије која треба да се сецка.
Брзо сецкање уреди
Овај алгоритам има сличности са Коен–Садерландовим алгоритмом. Почетне и крајње позиције се класификују по томе који део од 9 области оне заузимају. Велика switch наредба скаче на спрецијализовани хендлер за сваки могући случај. У контрасту, Коен–Садерланд ће итеративно да прође неколико пута да би решио тај проблем.
O(lg N) алгоритам уреди
Овај алгоритам класификује чворове против задате линије у имплицитном облику: p: ax + by + c = 0. Како се претпоставља да је многоугао конвексан и да су чворови поређани супротно од казаљке на сату можемо закључити да се време потребно да се изврши овај алгоритам O(lg N) сложености.
Скала уреди
Овај алгоритам је заснован на хомогеним координатама и дуалности. Може да се користи за сецкање линија или њихових сегмената уз употребу правоугаоног прозора или конвексног многоугла. Алгоритам се заснива на класификацији чворова помоћу полу-простора који задаје линија : p: ax + by + c = 0. Резултат ове класификација одређује ивице које се пресечене линијом p. Алгоритам је врло једноставан, једноставан за имплементацију и могуће га је унапредити да ради и са конвексним прозором. Линија или њен сегмент p може да се израчуна од тачака x1, x2 које су задате помоћу хомогених координата директно користећи међупроизвод као p = x1 x x2 = [x1,y1,w1] x [x2,y2,w2] or as p = x1 x x2 = [x1,y1,1] x [x2,y2,1]
Види још уреди
Референце уреди
- ^ Renka, R. J. (2014-10-19). „Line Clipping” (PDF). Department of Computer Science & Engineering, University of North Texas. Приступљено 2016-01-12.
- ^ Cyrus, M., Beck, J.: Generalized Two and Three Dimensional Clipping, Computers&Graphics, Vol.3, No.1, pp.23-28, 1978