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

Розробили і 1984 рокуLiang, Y. D., and Barsky, B., «A New Concept and Method for Line Clipping», ACM Transactions on Graphics, 3(1):1-22, January 1984 і вдосконалили 1992 року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..

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

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

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

 — ліворуч  — праворуч  — знизу  — згори

Якщо  — відрізок паралельний до однієї з площин відсікання  — зовні, відкинути  — всередині Якщо  — ззовні всередину Перетин у: Якщо  — зсередини назовні Перетин у:

Для  — точка ззовні всередину

Для  — точка зсередини назовні

Якщо повністю зовні, відкинути Інакше, опрацьовуваний відрізок пролягає у межах

Реалізація мовою 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, negarr; int posind = 1, negind = 1; posarr = 1; negarr = 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(); }

Примітки

Посилання Графіка і Мультимедіа: Обтинання Опис алгоритму із кодом на C++ The Liang-Barsky algorithm for line-rectangle collisions