Алгоритм Ляна — Барского — алгоритм, используемый в компьютерной графике для отсечения отрезков в некоторой прямоугольной области. Разработан и в 1984 году и усовершенствован в 1992 году.
Использует параметрическое представление линии и неравенства для определения того, какая часть отрезка попадает в заданную прямоугольную область. Для отрезка в параметрической форме (): ,
удлиняя диапазон до , можно получить прямую, содержащую искомый отрезок.
Точка линии находится в окне, если: , . Разбивая каждое из неравенств на два, получаются неравенства для четырёх сторон окна: (), где: (левая граница окна), (правая граница окна), (верхняя граница окна), (нижняя граница окна).
Правила для вычисления отсечённого отрезка: для линии, параллельной границе окна, для неравенства этой границы; если для данного имеет место , то линия находится вне рассматриваемой области и не должна быть изображена; если , то линия ориентирована с невидимой части области на видимую, и, если , то линия ориентирована с видимой части области в невидимую; для ненулевого точка — пересечение границы и искомой линии; для каждой границы вычисляется и : для отбираются те границы, в которых (то есть ориентирована с невидимой части области на видимую); выбирается как наибольшее из ; для отбираются те границы, в которых (то есть линия ориентирована с видимой части области в невидимую); выбирается как наименьшее из ; если , то линия находится вне рассматриваемой области и не должна быть изображена.
Примечания
Литература
Категория:Геометрические алгоритмы Категория:Компьютерная графика