Алгоритм Лян-Барского - Liang–Barsky algorithm - Wikipedia

В компьютерная графика, то Алгоритм Лян-Барского (названный в честь Ю-Донг Лян и Брайан А. Барски ) это обрезка линии алгоритм. Алгоритм Лянга – Барского использует параметрическое уравнение линии и неравенства, описывающие диапазон окна отсечения, чтобы определить пересечения между линией и окно клипа. С помощью этих пересечений он знает, какую часть линии следует провести. Этот алгоритм значительно эффективнее, чем Коэн – Сазерленд. Идея алгоритма отсечения Лянга – Барски состоит в том, чтобы провести как можно больше тестов перед вычислением пересечений линий.

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

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

${\displaystyle y=y_{0}+t(y_{1}-y_{0})=y_{0}+t\Delta y.}$

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

${\displaystyle x_{\text{min}}\leq x_{0}+t\Delta x\leq x_{\text{max}}}$

и

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

которое можно выразить в виде 4 неравенств

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

куда

${\displaystyle {\begin{aligned}p_{1}&=-\Delta x,&q_{1}&=x_{0}-x_{\text{min}},&&{\text{(left)}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{(right)}}\\p_{3}&=-\Delta y,&q_{3}&=y_{0}-y_{\text{min}},&&{\text{(bottom)}}\\p_{4}&=\Delta y,&q_{4}&=y_{\text{max}}-y_{0}.&&{\text{(top)}}\end{aligned}}}$

Чтобы вычислить последний отрезок линии:

1. Линия, параллельная краю окна отсечения, имеет ${\displaystyle p_{i}=0}$ для этой границы.
2. Если для этого ${\displaystyle i}$, ${\displaystyle q_{i}<0}$, то линия полностью выходит за пределы и может быть устранена.
3. Когда ${\displaystyle p_{i}<0}$, линия идет наружу внутрь окна клипа, а когда ${\displaystyle p_{i}>0}$, линия идет изнутри наружу.
4. Для ненулевого ${\displaystyle p_{i}}$, ${\displaystyle u=q_{i}/p_{i}}$ дает точку пересечения.
5. Для каждой строки рассчитайте ${\displaystyle u_{1}}$ и ${\displaystyle u_{2}}$. За ${\displaystyle u_{1}}$, посмотрите границы, для которых ${\displaystyle p_{i}<0}$ (т.е. снаружи внутрь). Брать ${\displaystyle u_{1}}$ быть самым большим среди ${\displaystyle \{0,q_{i}/p_{i}\}}$. За ${\displaystyle u_{2}}$, посмотрите границы, для которых ${\displaystyle p_{i}>0}$ (т.е. изнутри наружу). Брать ${\displaystyle u_{2}}$ быть минимумом ${\displaystyle \{1,q_{i}/p_{i}\}}$. Если ${\displaystyle u_{1}>u_{2}}$, линия находится снаружи и поэтому отклонена.

// Алгоритм обрезки линий Лян - Барского#включают<iostream>#включают<graphics.h>#включают<math.h>с помощью пространство имен стандартное;// эта функция дает максимумплавать макси(плавать обр[],int п) {  плавать м = 0;  за (int я = 0; я < п; ++я)    если (м < обр[я])      м = обр[я];  возвращаться м;}// эта функция дает минимумплавать мини(плавать обр[], int п) {  плавать м = 1;  за (int я = 0; я < п; ++я)    если (м > обр[я])      м = обр[я];  возвращаться м;}пустота liang_barsky_clipper(плавать xmin, плавать ymin, плавать xmax, плавать ymax,                          плавать x1, плавать y1, плавать x2, плавать y2) {  // определение переменных  плавать p1 = -(x2 - x1);  плавать p2 = -p1;  плавать p3 = -(y2 - y1);  плавать p4 = -p3;  плавать q1 = x1 - xmin;  плавать q2 = xmax - x1;  плавать q3 = y1 - ymin;  плавать q4 = ymax - y1;  плавать Posarr[5], негарр[5];  int Posind = 1, негр = 1;  Posarr[0] = 1;  негарр[0] = 0;  прямоугольник(xmin, ymin, xmax, ymax); // отрисовываем окно отсечения  если ((p1 == 0 && q1 < 0) || (p2 == 0 && q2 < 0) || (p3 == 0 && q3 < 0) || (p4 == 0 && q4 < 0)) {      Outtextxy(80, 80, "Линия параллельна окну отсечения!");      возвращаться;  }  если (p1 != 0) {    плавать r1 = q1 / p1;    плавать r2 = q2 / p2;    если (p1 < 0) {      негарр[негр++] = r1; // для отрицательного p1 добавить его в отрицательный массив      Posarr[Posind++] = r2; // и добавляем p2 в положительный массив    } еще {      негарр[негр++] = r2;      Posarr[Posind++] = r1;    }  }  если (p3 != 0) {    плавать r3 = q3 / p3;    плавать r4 = q4 / p4;    если (p3 < 0) {      негарр[негр++] = r3;      Posarr[Posind++] = r4;    } еще {      негарр[негр++] = r4;      Posarr[Posind++] = r3;    }  }  плавать xn1, yn1, xn2, yn2;  плавать rn1, rn2;  rn1 = макси(негарр, негр); // максимум отрицательного массива  rn2 = мини(Posarr, Posind); // минимум положительного массива  если (rn1 > rn2)  { // отклонять    Outtextxy(80, 80, "Линия за окном вырезки!");    возвращаться;  }  xn1 = x1 + p2 * rn1;  yn1 = y1 + p4 * rn1; // вычисление новых точек  xn2 = x1 + p2 * rn2;  yn2 = y1 + p4 * rn2;  установить цвет(CYAN);  линия(xn1, yn1, xn2, yn2); // рисование новой линии  набор(1, 1, 0);  линия(x1, y1, xn1, yn1);  линия(x2, y2, xn2, yn2);}int главный() {  cout << " пЛян-барская линия отсечения ";  cout << " пСтруктура окна системы: (0,0) внизу слева и (631, 467) вверху справа ";  cout << " пВведите координаты окна (wxmin, wxmax, wymin, wymax): ";  плавать xmin, xmax, ymin, ymax;  cin >> xmin >> ymin >> xmax >> ymax;  cout << " пВведите конечные точки линии (x1, y1) и (x2, y2): ";  плавать x1, y1, x2, y2;  cin >> x1 >> y1 >> x2 >> y2;  int б-г = ОБНАРУЖИТЬ, гм;  // используя библиотеку winbgim для C ++, инициализируем графический режим  initgraph(&б-г, &гм, "");  liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);  получить();  закрыть();}

Смотрите также

Алгоритмы, используемые с той же целью:

• Алгоритм Сайруса – Бека
• Алгоритм Николла – Ли – Николла
• Быстрая обрезка

Рекомендации

• Лян Ю. Д. и Барски Б. "Новая концепция и метод обрезки линий ", Транзакции ACM на графике, 3 (1): 1-22, январь 1984.
• Лян, Ю. Д., Б. А., Барски, М. Слейтер, Некоторые улучшения в алгоритме параметрической обрезки линии, CSD-92-688, Отдел компьютерных наук, Калифорнийский университет, Беркли, 1992.
• Джеймс Д. Фоули. Компьютерная графика: принципы и практика. Addison-Wesley Professional, 1996. стр. 117.

внешняя ссылка

• http://hinjang.com/articles/04.html#eight
• Skytopia: вкратце об алгоритме обрезки линий Лян-Барски!