梁友栋-柏世奇算法

✍ dations ◷ 2024-09-20 13:53:08 #计算机图形学,算法

梁友栋—柏世奇算法(以梁友栋和柏世奇(英语: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();}

参见

其他裁剪算法:

相关

  • 电负性电负性(英语:electronegativity,简写EN),也译作离子性、负电性及阴电性,是综合考虑了电离能和电子亲合能,首先由莱纳斯·鲍林于1932年提出。它以一组数值的相对大小表示元素原子在
  • 风疹疫苗风疹疫苗(英文:Rubella vaccine),是一种用于预防风疹的疫苗。其效力始于单一剂量后的两周,而且大约95%的人会得到免疫力。 有高免疫接种率的国家不再有风疹及先天性风疹综合征的
  • 大统集团大统集团是一间主要以台湾南部高雄市为营运重心的百货和量贩业者,于1950年代由纺织品贸易商吴耀庭所创立,其旗下的大统百货是台湾南部第一间大型百货公司。除了经营自有品牌的
  • 自由贸易园区自由贸易园区(英语:Free-trade zone)亦称自由贸易港区或自由经济区,经济特区的一种,是指在主权国家或者地区的关境以外,划出特定的区域,准许外国商品豁免关税自由进出。实质上是采
  • 桐城派桐城派,中国清朝散文流派。创始人方苞,继承者众,流传甚广,刘大櫆和姚鼐为集大成者,三人有“桐城三祖”之称,后继者有方东树。主张义理、考据、辞章三者并重,树立了桐城派古文的风范
  • 阿居兰阿居兰苏丹国(索马里语:Dawladdii Ajuuraan, 阿拉伯语:الدولة الأجورانيون‎),简称阿居兰,是索马里人建立的 穆斯林苏丹国。中世纪统治非洲之角的大部分。通过强
  • 炸酱面 (짜장면)韩式炸酱面(韩语:짜장면),是一种韩式中华料理(英语:Korean Chinese cuisine),在面条淋上由春酱(一种咸黑豆酱)、猪肉粒和蔬菜粒、有时还有海鲜制成的浓酱。这种酱称为炸酱。
  • 七甸街道七甸街道是中国云南省昆明市呈贡区下辖的一个街道,位于呈贡区东北部,距呈贡区主城22公里,距昆明市18公里。东临宜良县,南接澄江县,北依昆明市官渡区。辖区面积126平方千米,2008年
  • 翁德鲁祖区翁德鲁祖区(马达加斯加语:Vondrozo),是马达加斯加的行政区,位于该国东南部,由阿齐莫-阿齐那那那区负责管辖,首府设于翁德鲁祖,面积2,953平方公里,2011年人口121,274,人口密度每平方公
  • 侯赛因 (波斯)侯赛因(波斯语:شاه سلطان حسین‎,1668年-1726年),全名为素丹侯赛因。伊朗萨非王朝的第九任沙阿(1694年—1722年在位)。侯赛因为苏莱曼一世的长子。在他统治时期,萨非王朝