梁友棟-柏世奇算法

梁友棟—柏世奇算法（以梁友棟和柏世奇的名字命名）是計算機圖形學中的一個線段裁剪算法。梁友棟—柏世奇算法使用直線的參數方程和不等式組來描述線段和裁剪窗口的交集。求解出的交集將被用於獲知線的哪些部分是應當繪製在屏幕上的。這一算法比科恩－蘇澤蘭算法（Cohen-Sutherland algorithm）要更加高效，梁友棟—柏世奇算法的基本思想是：在計算線段與裁剪窗交集之前做儘可能多的判斷。

算法描述

考慮直線的參數方程：

$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}},$

其可用4個不等式表達：

$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{( 左 )}}\\p_{2}&=\Delta x,&q_{2}&=x_{\text{max}}-x_{0},&&{\text{( 右 )}}\\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{aligned}}$

計算最終線段：

1. 與裁剪窗平行的直線在平行的邊界上有 $p_{i}=0$
2. 若對於這樣的 $i$$q_{i}<0$，則線段全部在裁剪窗的外面，可以被消除
3. 當 $p_{i}<0$時，線從裁剪窗外向內走；$p_{i}>0$
4. 對非零的 $p_{k}$, $u=q_{i}/p_{i}$
5. 對每條線，計算 $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}$

示例代碼

// 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, 467 - ymin, xmax, 467 - ymax); // drawing the clipping window
  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; // 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, 467 - yn1, xn2, 467 - yn2); // the drawing the new line
  setlinestyle(1, 1, 0);
  line(x1, 467 - y1, xn1, 467 - yn1);
  line(x2, 467 - y2, xn2, 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;
  // 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();
}

參見

其他裁剪算法：

• 科恩－蘇澤蘭算法
• Cyrus–Beck算法
• Nicholl–Lee–Nicholl算法
• 快速裁剪

參考文獻

• Liang, Y. D., and Barsky, B., "A New Concept and Method for Line Clipping", ACM Transactions on Graphics, 3(1):1–22, January 1984.
• Liang, Y. D., B. A., Barsky, and M. Slater, Some Improvements to a Parametric Line Clipping Algorithm, CSD-92-688, Computer Science Division, University of California, Berkeley, 1992.
• James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. p. 117.

外部連結

• http://hinjang.com/articles/04.html#eight （頁面存檔備份，存於網際網路檔案館）
• Skytopia: The Liang-Barsky line clipping algorithm in a nutshell! （頁面存檔備份，存於網際網路檔案館）