Алгоритм Ліангу–Барського

У комп'ютерній графіці, алгоритм Ляна — Барського це алгоритм відсікання відрізків. Цей алгоритм використовує параметричне рівняння прямої і нерівності, що описують вікно відсікання для визначення перетинів між відрізком і вікном відсікання. За цими перетинами визначається, яку частину відрізка потрібно малювати. Алгоритм можна узагальнити до тривимірного випадку. Цей алгоритм значно ефективніший від алгоритму Коена — Сазерленда.

Розробили ^[en] і ^[en] 1984 року і вдосконалили 1992 року.

Опис

Ідеєю відсікання Ляна — Барського є якомога повніша перевірка перед обчисленням перетину відрізків. Спочатку розглянемо звичайне параметричне рівняння відрізка:

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

${\displaystyle y=y_{0}+u(y_{1}-y_{0})=y_{0}+u\Delta y\,\!}$

${\displaystyle u\in [0,1]}$

Точка перебуває у вікні відсікання, якщо

${\displaystyle x_{\text{min}}\leq x_{0}+u\Delta x\leq x_{\text{max}}\,\!}$

і

${\displaystyle y_{\text{min}}\leq y_{0}+u\Delta y\leq y_{\text{max}}\,\!}$,

що можна виразити чотирма нерівностями

${\displaystyle up_{k}\leq q_{k},\quad k=1,2,3,4\,\!}$,

де

${\displaystyle p_{1}=-\Delta x,q_{1}=x_{0}-x_{\text{min}}\,\!}$ — ліворуч

${\displaystyle p_{2}=\Delta x,q_{2}=x_{\text{max}}-x_{0}\,\!}$ — праворуч

${\displaystyle p_{3}=-\Delta y,q_{3}=y_{0}-y_{\text{min}}\,\!}$ — знизу

${\displaystyle p_{4}=\Delta y,q_{4}=y_{\text{max}}-y_{0}\,\!}$ — згори

• Якщо ${\displaystyle p_{k}=0}$ — відрізок паралельний до однієї з площин відсікання
  • ${\displaystyle q_{k}<0}$ — зовні, відкинути
  • ${\displaystyle q_{k}\geq 0}$ — всередині
• Якщо ${\displaystyle p_{k}<0}$ — ззовні всередину
  • Перетин у: ${\displaystyle u=q_{k}/p_{k}}$
• Якщо ${\displaystyle p_{k}>0}$ — зсередини назовні
  • Перетин у: ${\displaystyle u=q_{k}/p_{k}}$

• Для ${\displaystyle p_{k}<0}$ — точка ззовні всередину
  • ${\displaystyle r_{k}=q_{k}/p_{k}}$
  • ${\displaystyle u_{1}=max(r_{k},0)}$
• Для ${\displaystyle p_{k}>0}$ — точка зсередини назовні
  • ${\displaystyle r_{k}=q_{k}/p_{k}}$
  • ${\displaystyle u_{2}=min(r_{k},1)}$
• Якщо ${\displaystyle u_{1}>u_{2},}$ повністю зовні, відкинути
• Інакше, опрацьовуваний відрізок пролягає у межах ${\displaystyle u_{1},u_{2}}$

Реалізація мовою C++

Нижче наведено реалізацію алгоритму мовою 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(); } 

Примітки

1. Liang, Y. D., and Barsky, B., «A New Concept and Method for Line Clipping», ACM Transactions on Graphics, 3(1):1-22, January 1984
2. Liang, YD, BA, Barsky, and M. Slater, Some Improvements to a Parametric Line Clipping Algorithm, CSD-92-688, Computer Science Division, University of California, Berkeley, 1992.

Посилання

• Графіка і Мультимедіа: Обтинання [ 22 листопада 2015 у Wayback Machine.]
• Опис алгоритму із кодом на C++ [ 21 листопада 2016 у Wayback Machine.] (англ.)
• The Liang-Barsky algorithm for line-rectangle collisions [ 12 березня 2017 у Wayback Machine.] (англ.)