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

Эту страницу предлагается переименовать в «Алгоритм Ляна — Барски». Пояснение причин и обсуждение — на странице Википедия:К переименованию/16 марта 2021. Пожалуйста, основывайте свои аргументы на правилах именования статей. Не удаляйте шаблон до подведения итога обсуждения. Переименовать в предложенное название, снять этот шаблон.

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

Данный алгоритм использует параметрическое представление линии и неравенства для определения того, какая часть отрезка попадает в заданную прямоугольную область.

Рассмотрим обычную параметрическую форму отрезка:

${\displaystyle {x=x_{0}+t(x_{1}-x_{0})=x_{0}+t\Delta x,\ t\in \left[0,1\right],}}$

${\displaystyle {y=y_{0}+t(y_{1}-y_{0})=y_{0}+t\Delta y,\ t\in \left[0,1\right].}}$

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

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

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

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

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

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

где

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

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

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

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

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

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

Ниже представлена реализация алгоритма на языке C++ с использованием библиотеки winbgim:

// Алгоритм Лианга-Барски отсечения отрезка #include<iostream> #include<math.h> #include<graphics.h>  using namespace std;  // Функция, возвращающая максимум в массиве float maxi(const 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(const 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;     posarr[0] = 1;     negarr[0] = 0;      rectangle(int(round(xmin)), int(round(467 - ymin)), int(round(xmax)),               int(round(467 - ymax))); // Рисование отсекающего окна      if ((p1 == 0 && q1 < 0) || (p3 == 0 && q3 < 0)) {         outtextxy(80, 80, "Line is parallel to clipping window!");         return;     }     if (p1 != 0) {         float r1 = q1 / p1;         float r2 = q2 / p2;         if (p1 < 0) {             negarr[negind++] = r1; // При отрицательном p1, добавляем r1 к отрицательному массиву             posarr[posind++] = r2; // и добавляем r2 к положительному массиву         } else {             negarr[negind++] = r2;             posarr[posind++] = r1;         }     }     if (p3 != 0) {         float r3 = q3 / p3;         float r4 = q4 / p4;         if (p3 < 0) {             negarr[negind++] = r3;             posarr[posind++] = r4;         } else {             negarr[negind++] = r4;             posarr[posind++] = r3;         }     }      float xn1, yn1, xn2, yn2;     float rn1, rn2;     rn1 = maxi(negarr, negind); // Максимум отрицательного массива     rn2 = mini(posarr, posind); // Минимум положительного массива      if (rn1 > rn2) { // Отклоняем         outtextxy(80, 80, "Line is outside the clipping window!");         return;     }      xn1 = x1 + p2 * rn1;     yn1 = y1 + p4 * rn1; // Вычисляем новые точки      xn2 = x1 + p2 * rn2;     yn2 = y1 + p4 * rn2;      setcolor(CYAN);      line(int(round(xn1)), int(round(467 - yn1)), int(round(xn2)), int(round(467 - yn2))); // Рисование новой линии      setlinestyle(1, 1, 0);      line(int(round(x1)), int(round(467 - y1)), int(round(xn1)), int(round(467 - yn1)));     line(int(round(x2)), int(round(467 - y2)), int(round(xn2)), int(round(467 - yn2))); }  int main() {     cout << "\nLiang-Barsky line clipping";     cout << "\nThe system window outlay is: (0,0) at bottom left and (631, 467) at top right";     cout << "\nEnter the co-ordinates of the window(wxmin, wxmax, wymin, wymax):";     float xmin, xmax, ymin, ymax;     cin >> xmin >> ymin >> xmax >> ymax;     cout << "\nEnter the end points of the line (x1, y1) and (x2, y2):";     float x1, y1, x2, y2;     cin >> x1 >> y1 >> x2 >> y2;      int gd = DETECT, gm;      // Инициализация графического режима     initgraph(&gd, &gm, "");     liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);     getch();     closegraph(); } 

• Алгоритм Кируса — Бека
• Алгоритм Коэна — Сазерленда
• Быстрое отсечение^[англ.]
• Алгоритм Николл — Ли — Николла^[англ.]

• The Liang-Barsky line clipping algorithm in a nutshell! (англ.)
• Двумерный алгоритм Лианга-Барски