Алгоритм Лианга-Барски

FastClip алгоритм (быстрого отсечения)

Алгоритм разбиения средней точкой

Является модификацией алгоритма Сазерленда-Коэна: точки пересечения находятся не непосредственным вычислением, а методом бинарного поиска. Первый и второй случаи обрабатываются аналогично, а в третьем случае отрезок делится пополам, и каждая из частей обрабатывается отдельно. В конце все видимые части склеиваются в один отрезок, который и будет результатом.

Достоинства:

● Используется только целочисленная арифметика (деление на два реализуется как сдвиг вправо на один бит).

Недостатки:

● Большое количество итераций.

Является оптимизацией алгоритма Сазерленда-Коэна.

Все возможные варианты расположения концов отрезка кодируются восьмибитным кодом (по четыре бита для каждого конца), который интерпретируется одним большим switch с 72 вариантами (всего 9²=81, из них девять симметричных). Для каждой ситуации реализуется свой, наиболее оптимальный алгоритм нахождения ответа.

Тогда задача заключается в нахождении t₀ и t₁, которые будут соответствовать началу и концу видимой части отрезка. Поставим условие видимости:

x_Л ≤ x(t) ≤ x_П

y_Н ≤ y(t) ≤ y_В

или

x_Л ≤ (x₀ + tΔx) ≤ x_П

y_Н ≤ (y₀ + tΔy) ≤ y_В

что равносильно системе из четырёх неравенств:

-tΔx ≤ x₀ - x_Л

tΔx ≤ x_П - x₀

-tΔy ≤ y₀ - y_Н

tΔy ≤ y_В - y₀

Общий вид этих неравенств:

P_it ≤ Q_i i=1..4

где

P = {-Δx; Δx; -Δy; Δy}

Q = {x₀ - x_Л; x_П - x₀; y₀ - y_Н; y_В - y₀}

Каждое из них соответствует одной из сторон отсекающего окна. Инициализируем t₀=0 и t₁=1 (что означает, что отрезок полностью виден) и последовательно проверяем все условия:

● Если P_i > 0, то t ≤ Q_i / P_i ⇒ t₁ ≤ Q_i / P_i ⇒ t₁ := min(t₁, Q_i/P_i)

● Если P_i < 0, то t ≥ Q_i / P_i ⇒ t₀ ≥ Q_i / P_i ⇒ t₀ := max(t₀, Q_i/P_i)

● Если P_i = 0, то прямая параллельна стороне отсекающего окна. В этом случае:

○ если Q_i ≥ 0, то переходим к следующему неравенству,

○ если Q_i < 0, то отрезок полностью не виден. break.