梁友栋-柏世奇算法

✍ dations ◷ 2025-10-22 16:30:20 #计算机图形学,算法

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

考虑直线的参数方程:

点在裁剪窗内,若

其可用4个不等式表达:

其中

计算最终线段:

// 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)      m = arr;  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)      m = arr;  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, negarr;  int posind = 1, negind = 1;  posarr = 1;  negarr = 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 = r1; // for negative p1, add it to negative array      posarr = r2; // and add p2 to positive array    } else {      negarr = r2;      posarr = r1;    }  }  if (p3 != 0) {    float r3 = q3 / p3;    float r4 = q4 / p4;    if (p3 < 0) {      negarr = r3;      posarr = r4;    } else {      negarr = r4;      posarr = 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();}

参见

其他裁剪算法:

相关

  • 被子植物门传统分类方式:Anthophyta Magnoliophyta Cronquist, Takht. & W.Zimm., 1966被子植物(学名:Angiosperms),又名开花植物或有花植物。(以前的生物学分类称“被子植物门”,而现今被归
  • 莱尼蕨门莱尼蕨(学名:Rhynia),又名雷尼蕨、赖尼蕨,是一属已灭绝的原始陆生维管植物,是在约四亿年前的泥盆纪地层中所发现的一种化石蕨类。科学家认为它们是原始的蕨类,只有茎,而没有根与叶,高
  • 726年前9世纪 | 前8世纪 | 前7世纪前740年代 前730年代 | 前720年代 | 前710年代 前700年代前731年 前730年 前729年 前728年 前727年 | 前726年 | 前725年 前724年 前723年 前7
  • 学海书院坐标:25°02′10.55″N 121°29′43.39″E / 25.0362639°N 121.4953861°E / 25.0362639; 121.4953861学海书院(闽南语:.mw-parser-output .sans-serif{font-family:-apple-sy
  • 中国报中国报(Chinapress Sdn. Bhd.)是马来西亚中文报章之一,总部位于吉隆坡孟沙。公司成立于1946年2月1日,由李孝式(后来成为马来亚第一任财政部长)为首的筹组委员会发起创刊。
  • 保罗·埃伦费斯特保罗·埃伦费斯特(德语:Paul Ehrenfest,1880年1月18日-1933年9月25日),奥地利数学家、物理学家,1922年取得荷兰国籍。他的主要贡献是在统计力学的领域及对其与量子力学的关系的研究
  • 皇家阿尔弗雷德亲王医院皇家阿尔弗雷德亲王医院(英语:,简称:RPAH、RPA或PA医院)是一座澳大利亚医院。位于澳大利亚新南威尔士州首府悉尼内西区(英语:Inner West)的坎伯当,1882年成立,是悉尼重要的公立教学医
  • 基什哈齐·贝娅特丽克丝基什哈齐·贝娅特丽克丝(匈牙利语:Kisházi Beatrix,1946年10月13日-),出生于布达佩斯,匈牙利前女子乒乓球运动员。她曾获得3枚欧洲乒乓球锦标赛女子团体金牌。
  • 巴古尔巴古尔(Bhagur),是印度马哈拉施特拉邦Nashik县的一个城镇。总人口12454(2001年)。该地2001年总人口12454人,其中男性6374人,女性6080人;0—6岁人口1638人,其中男860人,女778人;识字率75
  • 关心羚关心羚(英语:Kuanh Sin Ling,1982年6月4日-),出生于台北市,兽医师,时代力量党籍,现为左岸动物医院兽医师,毕业于国立台湾大学兽医学系。2019年11月12日,关名列时代力量不分区立委候选人