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

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

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

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

и

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

куда

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

  1. Линия, параллельная краю окна отсечения, имеет для этой границы.
  2. Если для этого , , то линия полностью выходит за пределы и может быть устранена.
  3. Когда , линия идет наружу внутрь окна клипа, а когда , линия идет изнутри наружу.
  4. Для ненулевого , дает точку пересечения.
  5. Для каждой строки рассчитайте и . За , посмотрите границы, для которых (т.е. снаружи внутрь). Брать быть самым большим среди . За , посмотрите границы, для которых (т.е. изнутри наружу). Брать быть минимумом . Если , линия находится снаружи и поэтому отклонена.
// Алгоритм обрезки линий Лян - Барского#включают<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);  получить();  закрыть();}

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

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

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

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