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

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

Алгоритм использует параметрическую форму прямой:

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

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

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

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

и

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

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

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

где

{\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}}

Чтобы вычислить окончательный сегмент линии:

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

// Liang—Barsky line-clipping algorithm
#include<iostream>
#include<graphics.h>
#include<math.h>

using namespace std;

// this function gives the maximum
float maxi(float arr[],int n) {
  float m = 0;
  for (int i = 0; i < n; ++i)
    if (m < arr[i])
      m = arr[i];
  return m;
}

// this function gives the minimum
float mini(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) {
  // defining variables
  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(xmin, ymin, xmax, ymax); // drawing the clipping window

  if ((p1 == 0 && q1 < 0) || (p2 == 0 && q2 < 0) || (p3 == 0 && q3 < 0) || (p4 == 0 && q4 < 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; // for negative p1, add it to negative array
      posarr[posind++] = r2; // and add p2 to positive array
    } 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); // maximum of negative array
  rn2 = mini(posarr, posind); // minimum of positive array

  if (rn1 > rn2)  { // reject
    outtextxy(80, 80, "Line is outside the clipping window!");
    return;
  }

  xn1 = x1 + p2 * rn1;
  yn1 = y1 + p4 * rn1; // computing new points

  xn2 = x1 + p2 * rn2;
  yn2 = y1 + p4 * rn2;

  setcolor(CYAN);

  line(xn1, yn1, xn2, yn2); // the drawing the new line

  setlinestyle(1, 1, 0);

  line(x1, y1, xn1, yn1);
  line(x2, y2, xn2, 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, wymin, wxmax, wymax):";
  float xmin, ymin, xmax, 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;

  // using the winbgim library for C++, initializing the graphics mode
  initgraph(&gd, &gm, "");
  liang_barsky_clipper(xmin, ymin, xmax, ymax, x1, y1, x2, y2);
  getch();
  closegraph();
}

См. также

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

Ссылки

Лян Ю.Д. и Барски Б., « Новая концепция и метод обрезки строк », Транзакции ACM в графике , 3 (1): 1–22, январь 1984 г.
Лян, Ю.Д., Б.А., Барски и М. Слейтер, Некоторые улучшения алгоритма параметрического отсечения линий ^{[ мертвая ссылка ]}, CSD-92-688, Отдел компьютерных наук, Калифорнийский университет, Беркли, 1992.
Джеймс Д. Фоли. Компьютерная графика: принципы и практика . Аддисон-Уэсли Профессионал, 1996. с. 117.

Внешние ссылки