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

Из Википедије, слободне енциклопедије

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

Увод[уреди]

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

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

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

Уколико се тражи пресек праве са свим страницама посматране области. Да би се нашао пресек P(t) праве са неком страницом, потребно је прво израчунати вектор нормале N на страницу и уочити неку произвољну тачку на правој, Pe (то може да буде једно од темена). Вектор P(t)-Pe је нормалан у односу на вектор 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*(P1-P0)<0), а потенцијално излазна уколико је овај угао мањи од 90° (N*(P1-P0)>0).

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

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

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

Спољашње везе[уреди]

Литература[уреди]