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

В компьютерной графике алгоритм Лянга–Барского (названный в честь Ю-Донг Ляна и Брайана А. Барского ) — это алгоритм отсечения линий . Алгоритм Лянга–Барского использует параметрическое уравнение линии и неравенства, описывающие диапазон окна отсечения, для определения пересечений между линией и окном отсечения . С помощью этих пересечений он знает, какую часть линии следует нарисовать. Таким образом, этот алгоритм значительно эффективнее, чем алгоритм Коэна–Сазерленда . Идея алгоритма отсечения Лянга–Барского заключается в том, чтобы провести как можно больше испытаний перед вычислением пересечений линий.

Алгоритм использует параметрическую форму прямой линии:

${\displaystyle x=x_{0}+t(x_{1}-x_{0})=x_{0}+t\Дельта x,}$

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

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

${\displaystyle x_{\text{мин}}\leq x_{0}+t\Delta x\leq x_{\text{макс}}}$

и

${\displaystyle y_{\text{мин}}\leq y_{0}+t\Дельта y\leq y_{\text{макс}},}$

что можно выразить как 4 неравенства

${\displaystyle tp_{i}\leq q_{i},\quad i=1,2,3,4,}$

где

${\displaystyle {\begin{align}p_{1}&=-\Delta x,&q_{1}&=x_{0}-x_{\text{min}},&&{\text{(слева)}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{(справа)}}\\p_{3}&=-\Delta y,&q_{3}&=y_{0}-y_{\text{min}},&&{\text{(внизу)}}\\p_{4}&=\Delta y,&q_{4}&=y_{\text{max}}-y_{0}.&&{\text{(сверху)}}\end{align}}}$

Чтобы вычислить конечный отрезок линии:

1. Линия, параллельная краю окна отсечения, имеет для этой границы.${\displaystyle p_{i}=0}$
2. Если для этого , , то линия полностью находится снаружи и ее можно исключить.${\displaystyle я}$${\displaystyle q_{i}<0}$
3. Когда , линия продолжается снаружи внутрь окна обрезки, а когда , линия продолжается изнутри наружу.${\displaystyle p_{i}<0}$${\displaystyle p_{i}>0}$
4. Для ненулевого значения дает точку пересечения линии и края окна (возможно, спроецированную).${\displaystyle p_{i}}$${\displaystyle u=q_{i}/p_{i}}$${\displaystyle т}$
5. Два фактических пересечения линии с краями окна, если они существуют, описываются и , вычисляются следующим образом. Для , рассмотрим границы, для которых (т. е. снаружи внутрь). Возьмем в качестве наибольшего среди . Для , рассмотрим границы, для которых (т. е. изнутри наружу). Возьмем в качестве минимума из .${\displaystyle u_{1}}$${\displaystyle u_{2}}$${\displaystyle u_{1}}$${\displaystyle p_{i}<0}$${\displaystyle u_{1}}$${\displaystyle \{0,q_{i}/p_{i}\}}$${\displaystyle u_{2}}$${\displaystyle p_{i}>0}$${\displaystyle u_{2}}$${\displaystyle \{1,q_{i}/p_{i}\}}$
6. Если , то линия полностью находится за пределами окна обрезки. Если она полностью находится внутри него.${\displaystyle u_{1}>u_{2}}$${\displaystyle u_{1}<0<1<u_{2}}$

// Алгоритм отсечения линий Лян-Барски #include <iostream> #include <graphics.h> #include <math.h>с использованием пространства имен std ;  // эта функция возвращает максимальное значение float maxi ( float arr [], int n ) { float m = 0 ; for ( int i = 0 ; i < n ; ++ i ) if ( m < arr [ i ]) m = arr [ i ]; return m ; }                          // эта функция возвращает минимальное значение float mini ( float arr [], int n ) { float m = 1 ; for ( int i = 0 ; i < n ; ++ i ) if ( m > arr [ i ]) m = arr [ i ]; return m ; }                           void liang_barsky_clipper ( float xmin , float ymin , float xmax , float ymax , float x1 , float y1 , float x2 , float y2 ) { // определение переменных float p1 = - ( x2 - x1 ); float p2 = - p1 ; float p3 = - ( y2 - y1 ); float p4 = - p3 ;                                       float q1 = x1 - xmin ; float q2 = xmax - x1 ; float q3 = y1 - ymin ; float q4 = ymax - y1 ;                        float posarr [ 5 ], negarr [ 5 ]; int posind = 1 , negind = 1 ; посарр [ 0 ] знак равно 1 ; негарр [ 0 ] знак равно 0 ;                прямоугольник ( xmin , ymin , xmax , ymax ); // рисуем окно отсечения     if (( p1 == 0 && q1 < 0 ) || ( p2 == 0 && q2 < 0 ) || ( p3 == 0 && q3 < 0 ) || ( p4 == 0 && q4 < 0 )) { outtextxy ( 80 , 80 , "Линия параллельна окну отсечения!" ); return ; } if ( p1 != 0 ) { float r1 = q1 / p1 ; float r2 = q2 / p2 ; if ( p1 < 0 ) { negarr [ negind ++ ] = r1 ; // для отрицательного p1, добавляем его в отрицательный массив posarr [ posind ++ ] = r2 ; // и добавляем p2 в положительный массив } else { negarr [ negind ++ ] = r2 ; posarr [ положить ++ ] = r1 ; } } if ( p3 != 0 ) { float r3 = q3 / p3 ; float r4 = q4 / p4 ; if ( p3 < 0 ) { negarr [ отрицать ++ ] = r3 ; posarr [ положить ++ ] = r4 ; } else { negarr [ отрицать ++ ] = r4 ; posarr [ положить ++ ] = r3 ; } }                                                                                                                      float xn1 , yn1 , xn2 , yn2 ; float rn1 , rn2 ; rn1 = maxi ( negarr , negind ); // максимум отрицательного массива rn2 = mini ( posarr , posind ); // минимум положительного массива                  if ( rn1 > rn2 ) { // отклонить outtextxy ( 80 , 80 , "Строка находится за пределами окна отсечения!" ); return ; }           xn1 = x1 + p2 * rn1 ; yn1 = y1 + p4 * rn1 ; // вычисление новых точек               xn2 = x1 + p2 * rn2 ; yn2 = y1 + p4 * rn2 ;              установить цвет ( CYAN ); line ( xn1 , yn1 , xn2 , yn2 ); // рисование новой линии     setlinestyle ( 1 , 1 , 0 );   линия ( x1 , y1 , xn1 , yn1 ); линия ( x2 , y2 , xn2 , yn2 ); }       int main () { cout << " \n Отсечение линии Лян-Барского" ; cout << " \n Расположение системного окна: (0,0) внизу слева и (631, 467) вверху справа" ; cout << " \n Введите координаты окна (wxmin, wymin, wxmax, wymax):" ; float xmin , ymin , xmax , ymax ; cin >> xmin >> ymin >> xmax >> ymax ; cout << " \n Введите конечные точки линии (x1, y1) и (x2, y2):" ; float x1 , y1 , x2 , y2 ; cin >> x1 >> y1 >> x2 >> y2 ;                                           int gd = ОБНАРУЖЕНИЕ , gm ;     // используем библиотеку winbgim для C++, инициализируем графический режим initgraph ( & gd , & gm , "" ); liang_barsky_clipper ( xmin , ymin , xmax , ymax , x1 , y1 , x2 , y2 ); getch (); closegraph (); }             

Алгоритмы, используемые для той же цели:

• Алгоритм Сайруса–Бека
• Алгоритм Николла–Ли–Николла
• Быстрая обрезка

• Лян, Ю.Д. и Барски, Б., «Новая концепция и метод обрезки линий», ACM Transactions on Graphics , 3(1):1–22, январь 1984 г.
• Лян, Я.Д., Б.А., Барски и М. Слейтер, Некоторые улучшения параметрического алгоритма отсечения линий , CSD-92-688, Отделение компьютерных наук, Калифорнийский университет, Беркли, 1992.
• Джеймс Д. Фоли. Компьютерная графика: принципы и практика . Addison-Wesley Professional, 1996. С. 117.

• http://hinjang.com/articles/04.html#eight
• Skytopia: алгоритм отсечения линий Лянга-Барского в двух словах!