[科普中国]-梁友栋-柏世奇算法

在计算机图形学中，梁友栋—柏世奇算法（以梁友栋和柏世奇的名字命名）是一个线段裁剪算法。梁友栋—柏世奇算法使用直线的参数方程和不等式组来描述线段和裁剪窗口的交集。求解出的交集将被用于获知线的哪些部分是应当绘制在屏幕上的1。这一算法比Cohen-Sutherland算法要更加高效，梁友栋—柏世奇算法的基本思想是：在计算线段与裁剪窗交集之前做尽可能多的判断。2

算法描述考虑直线的参数方程：

点在裁剪窗内，若

且

其可用4个不等式表达：

其中，

计算最终线段：

1、与裁剪窗平行的直线在平行的边界上有

2、若对于这样的 ，则线段全部在裁剪窗的外面，可以被消除

3、当 时，线从裁剪窗外向内走；

4、对非零的

5、对每条线，计算 和 。对 检查 的边界（即从外向内）。令 为 ， 检查 的边界（即从内向外）。令 为

示例代码以下是梁友栋-柏世奇算法的代码演示3：

// Liang--Barsky line-clipping algorithm#include#include#includeusing namespace std;// this function gives the maximumfloat maxi(float arr[],int n) { float m = 0; for (int i = 0; i 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();}本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学