C语言实现梁友栋-Barsky算法

2023-12-05 07:28

本文主要是介绍C语言实现梁友栋-Barsky算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

(引用梁友栋-Barsky裁剪算法_梁友栋 barsky算法-CSDN博客)

Cyrus和Beck用参数化方法提出了比Cohen-Sutherland更有效的算法。后来梁友栋和Barsky独立地提出了更快的参数化线段裁剪算法,也称为Liany-Barsky(LB)算法。

     一、梁友栋-Barsky裁剪算法思想:

  我们知道,一条两端点为P1(x1,y1)、P2(x2,y2)的线段可以用参数方程形式表示:

x= x1+ u·(x2-x1)= x1+ u·Δx
y= y1+ u·(y2-y1)= y1+ u·Δy
0≤u≤1(3-9)

  式中,Δx=x2-x1,Δy=y2-y1,参数u在0~1之间取值,P(x,y)代表了该线段上的一个点,其值由参数u确定,由公式可知,当u=0时,该点为P1(x1,y1),当u=1时,该点为P2(x2,y2)。如果点P(x,y)位于由坐标(xwmin,ywmin)和(xwmax,ywmax)所确定的窗口内,那么下式成立:

xwmin≤x1+ u·Δx≤xwmax
ywmin≤y1+ u·Δy≤ywmax
(3-10)

  这四个不等式可以表示为:

u·pk ≤qk , k=1,2,3,4(3-11)

  其中,p、q定义为:

p1=-Δx, q1=x1-xwmin
p2=Δx, q2=xwmax-x1
p3=-Δy, q3=y1-ywmin
p4=Δy, q4=ywmax-y1
(3-12)

  从(3-12)式可以知道:任何平行于窗口某边界的直线,其pk=0(但并不是所有的Pk均为0,是存在pk=0的意思。平行于窗口某边界的图片,会出现 (p1&&p2)||(p3&&p4)=0的情况),k值对应于相应的边界(k=1,2,3,4对应于左、右、下、上边界)。如果还满足qk<0(默认x1为最左点?默认斜率大于0小于1?),则线段完全在边界外,应舍弃该线段。如果pk=0并且qk≥0,则线段平行于窗口某边界并在窗口内,见图中所示。公式(3-12)式还告诉我们:

  1、当pk<0时,线段从裁剪边界延长线的外部延伸到内部;

  2、当pk>0时,线段从裁剪边界延长线的内部延伸到外部;

  例如,当Δx≥0时,对于左边界p1<0(p1=-Δx),线段从左边界的外部到内部;

           对于右边界p2>0(p2=Δx),线段从右边界的内部到外部。

     当Δy<0时,对于下边界p3>0(p3=-Δy),线段从下边界的内部到外部;

          对于上边界p4<0(p4=Δy),线段从上边界的外部到内部。

     当pK≠0时,可以计算出参数u的值,它对应于无限延伸的直线与延伸的窗口边界k的交点,即:

 

  对于每条直线,可以计算出参数u1和u2,该值定义了位于窗口内的线段部分:

  1、u1的值由线段从外到内遇到的矩形边界所决定(pk<0),对这些边界计算rk=qk/pk,u1取0和各个r值之中的最大值。

  2、u2的值由线段从内到外遇到的矩形边界所决定(pk>0),对这些边界计算rk=qk/pk,u2取0和各个r值之中的最小值。

  3、如果u1>u2,则线段完全落在裁剪窗口之外,应当被舍弃;否则,被裁剪线段的端点可以由u1和u2计算出来。

代码实现:

#include<stdio.h>
double xl, xr, yt, yb;//事先给出的已知窗体位置
int cansee(double q, double d, double t0, double t1) //判断直线是否可见
{double r;if (q < 0)//计算初始边的交点参数{r = d / q;if (r > t1){return 0;}else if(r>t0){t0 = r;}}else if(q>0){//计算终边的交点参数r = d / q;if (r < t0) {return 0;}else if (r < t1)t1 = r;}else if (d<0){return 1;}
}void L_Barsky(double x0,double y0,double x1,double y1)//double xl, xr, yt, yb已知
{double t0 = 0.0, t1 = 0.0,delatx=0.0,delaty=0.0;delatx = x1 - x0;if (!cansee(-delatx, x0 - x1, t0, t1))return;if (!candee(delatx, xr - x0, t0, t1))return;delatx = x1 - x0;if (!cansee(-delaty, y0 - yb, t0, t1))return;if (!cansee(delaty, yt - y0, t0, t1))return;x1 = x0 + t1 * delatx;y1 = y0 + t1 * delaty;x0 = x0 + t0 * delatx;y0 = y0 + t0 * delaty;showline(x0, y0, x1, y1);//显示可见线段
}

注意:显示线的方法作者未实现,在WFC可直接调用

这篇关于C语言实现梁友栋-Barsky算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/456679

相关文章

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

PyQt6/PySide6中QTableView类的实现

《PyQt6/PySide6中QTableView类的实现》本文主要介绍了PyQt6/PySide6中QTableView类的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学... 目录1. 基本概念2. 创建 QTableView 实例3. QTableView 的常用属性和方法

PyQt6/PySide6中QTreeView类的实现

《PyQt6/PySide6中QTreeView类的实现》QTreeView是PyQt6或PySide6库中用于显示分层数据的控件,本文主要介绍了PyQt6/PySide6中QTreeView类的实现... 目录1. 基本概念2. 创建 QTreeView 实例3. QTreeView 的常用属性和方法属性

Android使用ImageView.ScaleType实现图片的缩放与裁剪功能

《Android使用ImageView.ScaleType实现图片的缩放与裁剪功能》ImageView是最常用的控件之一,它用于展示各种类型的图片,为了能够根据需求调整图片的显示效果,Android提... 目录什么是 ImageView.ScaleType?FIT_XYFIT_STARTFIT_CENTE

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

C语言中位操作的实际应用举例

《C语言中位操作的实际应用举例》:本文主要介绍C语言中位操作的实际应用,总结了位操作的使用场景,并指出了需要注意的问题,如可读性、平台依赖性和溢出风险,文中通过代码介绍的非常详细,需要的朋友可以参... 目录1. 嵌入式系统与硬件寄存器操作2. 网络协议解析3. 图像处理与颜色编码4. 高效处理布尔标志集合