[计算机图形学经典算法] Liang-Barsky（梁友栋-Barsky）算法（附Matlab代码）_梁友栋浙江大学-程序员宅基地

刚学习了计算机图形学这门课程，为奠定根基的算法所倾倒，特此记录一二。

Liang-Barsky（梁友栋-Barsky）

梁友栋,福建福州人，1956-1960年,复旦大学,师从苏步青先生，80年代初,提出了Liang-Barskey裁剪算法，1984-1990年任浙江大学数学系主任。1991年，梁友栋先生获国家自然科学三等奖，学生谭建荣、汪国昭、王国瑾、鲍虎军、马利庄第二届“中国几何设计与计算贡献奖”。

问题

Liang-Barsky 算法是 Cyrus-Beck 算法的特例，为此先介绍Cyrus-Beck 算法。

考虑一凸多边形区域 R 和线段 P1P2，要求计算线段落在区域 R 中的部分。假定 A 是区域 R 边界上一点。N 是区域边界在 A 点的内法向量。线段 P1P2 用参数方程表示：

这里写图片描述

Cyrus-Beck 算法－判断

这里写图片描述

Cyrus-Beck 算法－推导

这里写图片描述

Cyrus-Beck 算法－极值

这里写图片描述

Cyrus-Beck 算法－算法构造

这里写图片描述

Cyrus-Beck 算法－特殊情况

这里写图片描述

Liang-Barsky 算法的情形

当凸多边形恰为矩形，且矩形的边平行于坐标轴时，每个边的法向量仅有一个非零分量，所以法向量与任意矢量的内积，等于该向量的相应 x 或 y 分量。
其余具体步骤则与 Cyrus-Beck 算法相同，具体为：
- (1) 对每条边，计算交点并根据的符号判断其为上限组还是下限组；(若为特殊情况，则区别对待)
- (2) 在下限组及 0 中选取最大者 tl ，在上限组及 1 中选取最小者 tu ，若 tl ≤ tu 则其为参数 t 的最小最大范围；否则舍弃。

Liang-Barsky 算法－简化之后

这里写图片描述

Liang-Barsky 算法－书上推导

这里写图片描述

Liang-Barsky 算法－算法步骤

这里写图片描述

Liang-Barsky 算法－示例

这里写图片描述

Matlab 代码

clear;
lines=random_lines(100,[-10,10],[-10,10]);
hold on;
top=3;
bottom=-3;
left=-4;
right=4;
axis([-10,10 -10 10]);
plot([-4 4 4 -4 -4],[-3 -3 3 3 -3],'r-','LineWidth',2);
for k=1:100
x1=lines(k,1);
y1=lines(k,2);
x2=lines(k,3); 
y2=lines(k,4);
p1=x1-x2;
p2=x2-x1;
p3=y1-y2;
p4=y2-y1;
p=[p1,p2,p3,p4];
q1=x1-left;
q2=right-x1;
q3=y1-bottom;
q4=top-y1;
q=[q1,q2,q3,q4];
u=[q1/p1 q2/p2 q3/p3 q4/p4];
for i=1:4
    for j=(i+1):4
        if(u(j)>u(i))
            temp=u(i);
            u(i)=u(j);
            u(j)=temp;
            temp1=p(i);
            p(i)=p(j);
            p(j)=temp1;
            temp2=q(i);
            q(i)=q(j);
            q(j)=temp2;
        end
    end
end
u1=0;        
u2=1;
for m=1:4
    if(u(5-m)>0&&p(5-m)<0)
        u1=u(5-m);
    end
    if(u(m)<1&&p(m)>0)
        u2=u(m);       
    end
end
x=[x1,x2];
y=[y1,y2];
plot(x,y,'y');
if(p1==0||p2==0||p3==0||p4==0&&u1<u2)
        if((q1<0||q2<0||q3<0||q4<0))
        else
            x_1=x1+u1*(x2-x1);
            y_1=y1+u1*(y2-y1);
            x_2=x1+u2*(x2-x1);
            y_2=y1+u2*(y2-y1);
            x=[x_1,x_2];
            y=[y_1,y_2];
            plot(x,y,'b');
        end
elseif(u1<=u2)
    x_1=x1+u1*(x2-x1);
    y_1=y1+u1*(y2-y1);
    x_2=x1+u2*(x2-x1);
    y_2=y1+u2*(y2-y1);
    x=[x_1,x_2];
    y=[y_1,y_2];
    plot(x,y,'g');
end
end
hold off;

这里写图片描述

本文链接：https://blog.csdn.net/soulmeetliang/article/details/79185603

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

已解决（selenium操作火狐浏览器报错）TypeError: init() got an unexpected keyword argument ‘firefox_options‘-程序员宅基地

文章浏览阅读1.6w次，点赞8次，收藏18次。已解决（selenium操作火狐浏览器报错）TypeError: __init__() got an unexpected keyword argument ‘firefox_options‘_typeerror: __init__() got an unexpected keyword argument 'chrome_options

python方差_Python编程：方差、标准差、均方差、均方根值、均方误差、均方根误差...-程序员宅基地

文章浏览阅读315次。python实现代码# -*- coding: utf-8 -*-import mathdef get_average(records):"""平均值"""return sum(records) / len(records)def get_variance(records):"""方差反映一个数据集的离散程度"""average = get_average(records)return sum(..._pycharm方差计算代码

jmeter接口测试实例（五）对cookies的自动管理，实现登录后修改用户信息_jmeter中post请求如何更改每次的用户名-程序员宅基地

文章浏览阅读902次。一、前提：cookie是保存在本地，用来记录用户信息，最典型的作用是判断用户是否已经登录。如果一个接口，需要用户登录后，才能进行操作，如下，修改用户信息那么这时候，就需要用到cookie去识别这个登录的用户，因为要修改的是这个登录的用户的信息。二、使用1、jmeter.properties 中将CookieManager.save.cookies 设置为true。完成后重启jmet..._jmeter中post请求如何更改每次的用户名

python新建项目没有venv_pycharm配置venv虚拟环境-程序员宅基地

文章浏览阅读7.5k次，点赞2次，收藏2次。虚拟环境的好处：搭建独立的python运行环境，不与其他产生冲突虚拟环境有助于包的管理和防止版本冲突3.删除卸载方便虚拟环境的搭建：1.进入python的Scripts下，执行：pip3 install virtualenv2.选择建立虚拟环境的文件夹，我这边是直接在D盘software下面创建了一个virtualenv，如图：image.png3.创建虚拟环境：virtualenv --no-s..._pycharm没有venv怎么办

M1芯片的Mac在开发iOS项目时遇到的问题汇总（模拟器无法运行，Cocoapods错误等）_oc cocospods 安装依赖库之后不能使用模拟器了-程序员宅基地

文章浏览阅读2.3k次。--pod install时报错，且错误提示中有“ffi”字眼，提示错误：/Library/Ruby/Gems/2.6.0/gems/ffi-1.15.3/lib/ffi/library.rb:275: [BUG] Bus Error at 0x00000001042fc000 ruby 2.6.3p62 (2019-04-16 revision 67580) [universal.arm64e-darwin20]解决方案：juejin.cn/post/698064…--pod repo upd_oc cocospods 安装依赖库之后不能使用模拟器了

编辑器VSCode使用心得-程序员宅基地

文章浏览阅读540次。工欲善其事必先利其器，趁手的工具会使我们开发事半功倍。市面上的编辑器我用过许多，编辑器使用经历Notepad++，（开源）这个应该是最轻量级的吧，查看代码还好，编辑代码就算了官网地址：https://notepad-plus-plus.org/Brackets，（开源）这个也不错，github-star：30k了，上次发布版本是6月..._vscode nextick

随便推点

西部数码mysql怎么用织梦_[原创]织梦程序(DeDeCms)常见问题集锦-程序员宅基地

文章浏览阅读95次。前言：织梦程序是最知名的cms程序，使用广泛,但很多朋友对织梦还不太熟悉,通过工单分析得知,经常容易出现本文中的问题,本次统一整理出来,希望对新手朋友有帮助,本文写的非常详细,请仔细阅读,一、描述：“dedecms错误警告：连接数据库失败，可能数据库密码不对或数据库服务器出错”如图：分析：用织梦程序制作的站点做迁移服务器后容易出现这个问题,原因是程序中设置的数据库连接信息有误连接不到数据库,解决方..._西部数码支不支持织梦的程序

免安装mysql启动3534错误处理_mysql 免安装版本启动时 3534出错_mysql-程序员宅基地

文章浏览阅读295次。上午在win7下安装MYSQL,只到“net start mysql”这一步报错:3534的错误：于是在百度中搜索关键字“mysql服务无法启动3534”。参考以下两个链接中的方法，解决了3534启动失败的问题：mysql服务无法启动3534错误。http://jingyan.baidu.com/article/219f4bf7e978fcde442d38a9.htmlhttp://blog.cs..._免安装mysql启动失败

评测了10款画流程图软件，这4款最好用！（完全免费）_好用的流程图软件免费-程序员宅基地

文章浏览阅读5.1w次，点赞58次，收藏295次。最近在做项目和复习的时候，用了不少流程图软件给我帮了大忙，所以今天就来分享分享你在网上搜索一下流程图软件，能找到很多很多：但这些软件多数并不是专门绘制流程图的软件，它可能是一些思维导图软件、或者说一些产品交互原型图软件，使用时或多或少有些麻烦。而且，普遍这些软件缺点也很多，比如：只有在线版：ProcessOn（https://www.processon.com）导出功能收费：迅捷流程图软件体积庞大：VISIO就没有一款简单易用、绿色免费的流程图软件吗？阿虚花了不少时间，挨着_好用的流程图软件免费

在CentOS6.9安装Azkaban3.50.0_centos6.9 azkaban-程序员宅基地

文章浏览阅读1.4k次。cd /data/install_pkgwget https://github.com/azkaban/azkaban/archive/3.50.0.tar.gztar -zxvf 3.50.0.tar.gzvi /data/install_pkg/azkaban-3.50.0/azkaban-common/src/main/java/azkaban/utils/EmailMessage..._centos6.9 azkaban

Java项目基于ssm+vue.js的学生宿舍维修服务平台附带文章和源代码设计说明文档ppt-程序员宅基地

文章浏览阅读586次，点赞23次，收藏30次。博主介绍：CSDN特邀作者、985计算机专业毕业、某互联网大厂高级全栈开发程序员、码云/掘金/华为云/阿里云/InfoQ/StackOverflow/github等平台优质作者、专注于Java、小程序、前端、python等技术领域和毕业项目实战，以及程序定制化开发、全栈讲解、就业辅导、面试辅导、简历修改。精彩专栏推荐订阅2023-2024年最值得选的微信小程序毕业设计选题大全：100个热门选题推荐2023-2024年最值得选的Java毕业设计选题大全：500个热门选题推荐。

ultralytics的YOLOv8改为自用版本_from ultralytics.utils.plotting import annotator, -程序员宅基地

文章浏览阅读944次。由于需要用pyqt给yolov8做一个界面，而ultralytics一层嵌一层，不是很好用，所以对它的这个源码进行精简，具体代码我放到了这里，ultralytics使用的版本是8.0.54。具体代码如下，需要根据自己的情况来修改data的配置文件以及权值文件，在代码的49和50行。_from ultralytics.utils.plotting import annotator, colors, save_one_box modul

[计算机图形学经典算法] Liang-Barsky（梁友栋-Barsky）算法（附Matlab代码）_梁友栋浙江大学-程序员宅基地

Liang-Barsky（梁友栋-Barsky）