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

29.05.2021

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

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

Описание алгоритма

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

x = x 0 + t ( x 1 − x 0 ) = x 0 + t Δ x ,   t ∈ [ 0 , 1 ] , {displaystyle {x=x_{0}+t(x_{1}-x_{0})=x_{0}+tDelta x, tin left[0,1 ight],}} y = y 0 + t ( y 1 − y 0 ) = y 0 + t Δ y ,   t ∈ [ 0 , 1 ] . {displaystyle {y=y_{0}+t(y_{1}-y_{0})=y_{0}+tDelta y, tin left[0,1 ight].}}

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

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

x min ⩽ x 0 + t Δ x ⩽ x max , {displaystyle {x_{ ext{min}}leqslant x_{0}+tDelta xleqslant x_{ ext{max}},}} y min ⩽ y 0 + t Δ y ⩽ y max . {displaystyle {y_{ ext{min}}leqslant y_{0}+tDelta yleqslant y_{ ext{max}}.}}

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

t p i ⩽ q i , i = 1 , 2 , 3 , 4 , , {displaystyle {tp_{i}leqslant q_{i},quad i=1,2,3,4,},}

где

p 1 = − Δ x , q 1 = x 0 − x min , {displaystyle {egin{aligned}p_{1}&=-Delta x,&q_{1}&=x_{0}-x_{ ext{min}},end{aligned}}} (левая граница окна) p 2 = Δ x , q 2 = x max − x 0 , {displaystyle {egin{aligned}p_{2}&=Delta x,&q_{2}&=x_{ ext{max}}-x_{0},end{aligned}}} (правая граница окна) p 3 = − Δ y , q 3 = y 0 − y min , {displaystyle {egin{aligned}p_{3}&=-Delta y,&q_{3}&=y_{0}-y_{ ext{min}},end{aligned}}} (верхняя граница окна) p 4 = Δ y , q 4 = y max − y 0 . {displaystyle {egin{aligned}p_{4}&=Delta y,&q_{4}&=y_{ ext{max}}-y_{0}.end{aligned}}} (нижняя граница окна)

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

  • Для линии, параллельной границе окна, p i = 0 {displaystyle {p_{i}=0}} для неравенства этой границы.
  • Если для данного i {displaystyle {i}} , q i < 0 {displaystyle {q_{i}<0}} , то линия находится вне рассматриваемой области и не должна быть изображена.
  • Если p i < 0 {displaystyle {p_{i}<0}} , то линия ориентирована с невидимой части области на видимую, и, если p i > 0 {displaystyle {p_{i}>0}} , то линия ориентирована с видимой части области в невидимую.
  • Для ненулевого p i {displaystyle {p_{i}}} , u = q i p i {displaystyle {u={frac {q_{i}}{p_{i}}}}} даёт точку пересечения границы и искомой линии.
  • Для каждой границы вычисляем u 1 {displaystyle {u_{1}}} и u 2 {displaystyle {u_{2}}} .
  • Для u 1 {displaystyle {u_{1}}} , отбираем те границы, в которых p i < 0 {displaystyle {p_{i}<0}} (то есть ориентирована с невидимой части области на видимую). Выбираем u 1 {displaystyle {u_{1}}} как наибольшее из { 0 , q i p i } {displaystyle {{0,{frac {q_{i}}{p_{i}}}}}} .
  • Для u 2 {displaystyle {u_{2}}} , отбираем те границы, в которых p i > 0 {displaystyle {p_{i}>0}} (то есть линия ориентирована с видимой части области в невидимую). Выбираем u 2 {displaystyle {u_{2}}} как наименьшее из { 1 , q i p i } {displaystyle {{1,{frac {q_{i}}{p_{i}}}}}} .
  • Если 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 << " Liang-Barsky line clipping"; cout << " The system window outlay is: (0,0) at bottom left and (631, 467) at top right"; cout << " Enter the co-ordinates of the window(wxmin, wxmax, wymin, wymax):"; float xmin, xmax, ymin, ymax; cin >> xmin >> ymin >> xmax >> ymax; cout << " Enter 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(); }

    Другие алгоритмы отсечения отрезков

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


    Имя:*
    E-Mail:
    Комментарий:
    Информационный некоммерческий ресурс fccland.ru © 2020
    При цитировании и использовании любых материалов ссылка на сайт обязательна