Сајрус-Беков алгоритам

Сајрус-Беков алгоритам (енгл. Cyrus-Beck) је геометријски алгоритам за сецкање линије. Сецкање линије представља одстрањивање дела дужи (или праве), која је изван неке посматране области. Потребно је да буде испуњен услов да је област конвексан полигон.

Увод[уреди | уреди извор]

У овом алгоритму се користи параметарска једначина праве. Права је задата преко две различите тачке, P₀ и P₁, тако да њена параметарска једначина гласи $P(t)=P_{0}+t*(P_{1}-P_{0})$ . Параметарска једначина праве користи једну тачку праве и вектор правца. Вектор правца се добија тако што се одузму координате две дате тачке (P₁-P₀). Параметар t физички посматрано представља време, а геометријски посматрано у правцу вектора правца. Овом једначином су описане све једначине на правој. (У случају дужи, параметар t узима вредности између 0 и 1)

Алгоритам[уреди | уреди извор]

Уколико се тражи пресек праве са свим страницама посматране области. Да би се нашао пресек P(t) праве са неком страницом, потребно је прво израчунати вектор нормале N на страницу и уочити неку произвољну тачку на правој, P_e (то може да буде једно од темена). Вектор P(t)-P_e је нормалан у односу на вектор N, па је њихов производ једнак нули. Значи потребно је наћи такво t, које задовољава $N*(P_{0}+t*(P_{1}-P_{0})-P_{e})=0$ . Када се једначина реши по t, добије се $t={\frac {N*(P_{0}-P_{e})}{-N*(P_{1}-P_{0})}}$ . Овде је потребно покрити и специјални случај када су права и страница паралелне (тада ова формула не важи).

На овај начин су пронађене пресечне тачке са свим страницама области. Затим се све ове тачке класификују на потенцијално улазне и потенцијално излазне. Тачка је потенцијално улазна уколико вектор правца са вектором нормале странице заклапа угао већи од 90° (N*(P₁-P₀)<0), а потенцијално излазна уколико је овај угао мањи од 90° (N*(P₁-P₀)>0).

Затим се све пресечне тачке сортирају (по параметру t), и уочимо највећу од потенцијално улазних тачака, MAX P_u и најмању од потенцијално излазних тачака, MIN P_i. Уколико уочена улазна тачка долази пре излазне, део праве који је унутар области је између тачака MAX P_u и MIN P_i. У супротном права нема пресек са облашћу.

Сложеност[уреди | уреди извор]

Уколико се претпостави да полигон има n страница. Пресек праве са сваком од страница се налази у константном времену, па се сви пресеци налазе у линеарном времену, ${\mathcal {O}}(n)$ (види: нотација великог О). Пресечне тачке је потребно сортирати, а сложеност сортирања је ${\mathcal {O}}(n\log n)$ . Проналажење највеће улазне и најмање излазне тачке се спроводи проласком кроз сортирани низ (сложеност ${\mathcal {O}}(n)$ ), тако да је свеукупна сложеност алгоритма ${\mathcal {O}}(n\log n)$ .