基本介紹
- 中文名：梁友棟-柏世奇算法
- 外文名：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();}