梁友栋-柏世奇算法

✍ dations ◷ 2025-09-18 20:22:56 #计算机图形学,算法

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

参见

其他裁剪算法:

相关

  • 林达尔托马斯·罗伯特·林达尔(瑞典语:Tomas Robert Lindahl,1938年1月28日-),瑞典-英国医学家,专门从事癌症研究。他是挪威科学和文学研究院的成员。2010年,他因对DNA修复的研究被授予英
  • 驻台湾外交机构/大使/代表驻台湾外交机构列表是列出所有驻台湾的外交代表机构,包括官方及非官方的机构。大部分国家在台北市设置具有大使馆功能的代表处,部分同时于高雄市、台中市设立具备领事馆功能之
  • 脱衣游戏脱衣游戏是一种派对游戏,在游戏中输了的人要脱去身上部分的衣服或是饰物。许多图版游戏、卡片游戏及运动都可以修改为输了的人要脱衣的版本,例如脱衣扑克(英语:Strip poker)、脱
  • 苏福克县萨福克县(Suffolk County, New York)是美国纽约州的一个县,位于长岛东部,北向长岛海湾,南面大西洋,西接拿骚縣 ,是纽约州与纽约大都会区最东边的县。面积6,146平方公里。根据美国2
  • 卡宾达共和国卡宾达共和国(宾达语:Kilansi kia Kabinda、法语:République du Kabinda)是目前未被承认的卡宾达省(目前是安哥拉一部分)分离政府采用的名称。卡宾达是位于中部非洲西部的地区,面
  • 十九锗化十一铬十九锗化十一铬是一种无机化合物,化学式为Cr11Ge19,它具有非中心对称的结构。十九锗化十一铬可由铬和锗的单质在碘的存在下按45:55(mol%)于高温通过化学气相传输反应得到:它也可
  • TE缓冲液TE缓冲液(英语:TE buffer)是分子生物学中常用的缓冲溶液,尤其是涉及到DNA、cDNA或RNA的步骤中。“TE”这个单词得名于其组分:Tris(常用的 pH缓冲液)及EDTA(用于螯合如Mg2+等阳离子的
  • 锺明善锺明善(1939年-),男,汉族,陕西咸阳人,中国书法家,中国书法家协会原副主席、顾问。曾先后师从书法家高乐三、程克刚、陈少默。1960年毕业于陕西师范大学中文系。书法作品1987年获“全
  • 麟庆麟庆(满语:ᠯᡳᠨᡴᡳᠩ,转写:,1791年-1846年),完颜氏,字伯余,又字振祥,号见亭、佛寮,室名凝香室、蓉湖草堂、琅环妙境、永保尊彝之室、退思斋、拜石轩、云荫堂、近光楼、知止轩、水木清
  • 姚爵姚爵(?-?),字汝修,陕西平凉府静宁州(今甘肃省静宁县)人,明朝政治人物。正德六年(1511年)辛未科进士。初授刑部广东清吏司主事,转浙江司,进任郎中。正德十三年,明武宗南巡之争时,反对武宗巡游