Алгоритм Лян-Барского - 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 {align} p_ {1} & = - Delta x, & q_ {1} & = x_ {0} -x _ { text {min}}, && { text {(слева)}} 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 {(снизу)}} p_ {4} & = Delta y, & q_ {4 } & = y _ { text {max}} - y_ {0}. && { text {(вверху)}} end {выровнено}}}$

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

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: вкратце об алгоритме обрезки линий Лян-Барски!