Алгоритм Ляна — Барського
У комп'ютерній графіці, алгоритм Ляна — Барського це алгоритм відсікання відрізків. Цей алгоритм використовує параметричне рівняння прямої і нерівності, що описують вікно відсікання для визначення перетинів між відрізком і вікном відсікання. За цими перетинами визначається, яку частину відрізка потрібно малювати. Алгоритм можна узагальнити до тривимірного випадку. Цей алгоритм значно ефективніший від алгоритму Коена — Сазерленда.
Розробили Лян Юдун[en] і Браян Барський[en] 1984 року[1] і вдосконалили 1992 року[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();
}
- ↑ Liang, Y. D., and Barsky, B., «A New Concept and Method for Line Clipping», ACM Transactions on Graphics, 3(1):1-22, January 1984
- ↑ 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.] (англ.)