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

Алгоритм Ляна — Барского — алгоритм, используемый в компьютерной графике для отсечения отрезков в некоторой прямоугольной области. Разработан Лян Юдуном и Брайаном Барским в 1984 году^[1] и усовершенствован в 1992 году^[2].

Использует параметрическое представление линии и неравенства для определения того, какая часть отрезка попадает в заданную прямоугольную область. Для отрезка в параметрической форме (${\displaystyle t\in \left[0,1\right]}$):

${\displaystyle x=x_{0}+t(x_{1}-x_{0})=x_{0}+t\Delta x}$,

${\displaystyle y=y_{0}+t(y_{1}-y_{0})=y_{0}+t\Delta y}$

удлиняя диапазон ${\displaystyle t}$ до ${\displaystyle \left(-\infty ,+\infty \right)}$, можно получить прямую, содержащую искомый отрезок.

Точка линии находится в окне, если:

${\displaystyle x_{\min }\leqslant x_{0}+t\Delta x\leqslant x_{\max }}$,

${\displaystyle y_{\min }\leqslant y_{0}+t\Delta y\leqslant y_{\max }}$.

Разбивая каждое из неравенств на два, получаются неравенства для четырёх сторон окна:

${\displaystyle tp_{i}\leqslant q_{i}}$ (${\displaystyle i=1,2,3,4}$),

где:

${\displaystyle p_{1}=-\Delta x,q_{1}=x_{0}-x_{\min }}$ (левая граница окна),

${\displaystyle p_{2}=\Delta x,q_{2}=x_{\max }-x_{0}}$ (правая граница окна),

${\displaystyle p_{3}=-\Delta y,q_{3}=y_{0}-y_{\min }}$ (верхняя граница окна),

${\displaystyle p_{4}=\Delta y,q_{4}=y_{\max }-y_{0}}$ (нижняя граница окна).

Правила для вычисления отсечённого отрезка:

• для линии, параллельной границе окна, ${\displaystyle p_{i}=0}$ для неравенства этой границы;
• если для данного ${\displaystyle i}$ имеет место ${\displaystyle {q_{i}<0}}$, то линия находится вне рассматриваемой области и не должна быть изображена;
• если ${\displaystyle p_{i}<0}$, то линия ориентирована с невидимой части области на видимую, и, если ${\displaystyle p_{i}>0}$, то линия ориентирована с видимой части области в невидимую;
• для ненулевого ${\displaystyle p_{i}}$ точка ${\displaystyle u={\frac {q_{i}}{p_{i}}}}$ — пересечение границы и искомой линии;
• для каждой границы вычисляется ${\displaystyle u_{1}}$ и ${\displaystyle u_{2}}$:
  • для ${\displaystyle u_{1}}$ отбираются те границы, в которых ${\displaystyle p_{i}<0}$ (то есть ориентирована с невидимой части области на видимую); выбирается ${\displaystyle u_{1}}$ как наибольшее из ${\displaystyle \{0,{\frac {q_{i}}{p_{i}}}\}}$;
  • для ${\displaystyle u_{2}}$ отбираются те границы, в которых ${\displaystyle p_{i}>0}$ (то есть линия ориентирована с видимой части области в невидимую); выбирается ${\displaystyle u_{2}}$ как наименьшее из ${\displaystyle \{1,{\frac {q_{i}}{p_{i}}}\}}$;
  • если ${\displaystyle u_{1}>u_{2}}$, то линия находится вне рассматриваемой области и не должна быть изображена.

• Боресков А. В. Программирование компьютерной графики. Современный OpenGL. — М.: ДМК Пресс, 2019. — С. 50—52. — 372 с.