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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

Ссылки

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