梁友栋-柏世奇算法

✍ dations ◷ 2025-06-08 13:42:03 #计算机图形学,算法

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

参见

其他裁剪算法:

相关

  • NOsub2/subF硝酰氟(化学式:NO2F)是最常见的硝酰盐之一。它首先由莫瓦桑于1905年制得。硝酰氟与硝酸根离子是等电子体,也为平面结构。通常状态下为无色气体,共价性较强,熔点-166°C,沸点-72.5°
  • 台北府台北府为清廷于光绪元年12月20日(公元1876年1月16日),沈葆祯奏请在台湾岛北部设置之官署及行政区划。于官署方面,台北府设置台北府知府等官员,衙门地点则位于台北城内,与台湾巡抚
  • 马来酸马来酸(maleic acid),即顺丁烯二酸,化学式为 HO2CCHCHCO2H,是一种二羧酸,即一个含有两个羧酸官能基的有机化合物。马来酸和富马酸(反丁烯二酸)互为顺反异构物。马来酸常用来制备富马
  • 癸二酸癸二酸,结构式HOOC(CH2)8COOH。白色片状结晶。微溶于水,溶于乙醇、乙醚。可燃。基本无毒,但生产原料甲酚有毒。存放时避免与液酸和碱接触,于阴凉通风处贮存,防火防潮。蓖麻油在碱
  • 河鼓二河鼓二,即著名的“牛郎星”,“天鹰座α”(α Aql/Altair),又叫“牵牛星”或“大将军”,在日文中称作“彦星”。排名全天第十二的明亮恒星,白色。在星空观测中,是夏季大三角中的一角
  • 劳拉·卡芙特劳拉·克罗夫特(英语:Lara Croft,港台译作“萝拉·卡芙特”,中国大陆又译作“劳拉·克劳馥”)是Eidos Interactive(现史克威尔艾尼克斯)的动作冒险游戏《古墓丽影》的主角。由托比
  • 禅 (消歧义)禅在中文原意是“帝王的祭天地之礼”或“禅让王位”;佛教传入后,作为梵语“dhyāna”的音译。
  • 矢量字体矢量字体是与点阵字体相对应的一种字体。矢量字体的每个字形都是通过数学方程来描述的,一个字形上分割出若干个关键点,相邻关键点之间由一条光滑曲线连接,这条曲线可以由有限个
  • 地心历险记2:神秘岛《地心历险记2:神秘岛》(英语:)是一部2012年2月上映的美国奇幻冒险三维电影,由加拿大导演布拉德·佩顿执导,为2008年的电影《地心历险记》的续集。根据法国作家儒勒·凡尔纳的科幻
  • Suho金俊勉(朝鲜语:김준면,英语:Kim Jun-myeon, 1991年05月22日-),艺名Suho(朝鲜语:수호;中文:守护),韩国男艺人,为韩国男子团体EXO及韩国分队EXO-K的队长,在队中担任总队长,虚构超能力为“水”。