梁友棟-柏世奇算法

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

基本介紹

• 中文名：梁友棟-柏世奇算法
• 外文名：Liang–Barsky algorithm
• 分類：計算機圖形學
• 套用：線段裁剪算法

算法描述

考慮直線的參數方程：

點在裁剪窗內，若

且

其可用4個不等式表達：

其中，

計算最終線段：

1、與裁剪窗平行的直線在平行的邊界上有

2、若對於這樣的 ，則線段全部在裁剪窗的外面，可以被消除

3、當 時，線從裁剪窗外向內走；

4、對非零的

5、對每條線，計算 和 。對 檢查 的邊界（即從外向內）。令 為 ， 檢查 的邊界（即從內向外）。令 為

示例代碼

以下是梁友棟-柏世奇算法的代碼演示：

// Liang--Barsky line-clipping algorithm#include<iostream>#include<graphics.h>#include<math.h>using namespace std;// this function gives the maximumfloat 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 minimumfloat 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  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();}