5. 矩形

浏览量:24

参考

      Mike Cyrus, and Jay Beck. "Generalized two-and three-dimensional clipping."Computers & Graphics, vol.3, no.1, pp.23-28, 1978.       You-Dong Liang, and Brian A. Barsky. "A new concept and method for line clipping." ACM Transactions on Graphics (TOG), vol.3, no.1, pp.1-22, 1984.

spacer
浏览量:42

5.3. 对线性对象的裁剪

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 5.3. 对线性对象的裁剪 5.3.1. 裁剪算法综述 问题描述:求矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)对线段\({{P}_{0}}{{P}_{1}}\)的裁剪。 图5.5 线段的端点坐标沿着矩形的两条轴的投影 Cyrus-Beck算法解决了凸多边形或者凸多面体对象对线性对象的裁剪,矩形也是一个凸多边形,同样适用。在图形学中,有一个经典的问题,就是矩形窗口对线段的裁剪,即二维平面上轴对齐的矩形对线段的裁剪问题。对于非轴对齐的矩形的裁剪,可以把线段坐标按矩形的两条互相垂直的轴作投影,把矩形转化为轴对齐的情况。如图5.5所示,把线段的两个端点\({{P}_{0}}\)和\({{P}_{1}}\)投影到\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\)上,得到新的坐标P0'和P1',投影等式为\( {{P}_{0}}'=\left( ({{P}_{0}}-C)\cdot {{{\vec{e}}}_{0}},({{P}_{0}}-C)\cdot {{{\vec{e}}}_{1}} \right),{{P}_{1}}'=\left( ({{P}_{1}}-C)\cdot {{{\vec{e}}}_{0}},({{P}_{1}}-C)\cdot {{{\vec{e}}}_{1}} \right)\),问题就转化为求轴对齐的矩形对线段P0'P1'的裁剪问题。求出裁剪后的线段Q0'Q1'后,再变换成原矩形的坐标,设\({{Q}_{0}}'=({{x}_{0}},{{y}_{0}}),{{Q}_{1}}'=({{x}_{1}},{{y}_{1}})\),则变换等式是\({{Q}_{0}}={{x}_{0}}{{\vec{e}}_{0}}+{{y}_{0}}{{\vec{e}}_{1}}+C,{{Q}_{1}}={{x}_{1}}{{\vec{e}}_{0}}+{{y}_{1}}{{\vec{e}}_{1}}+C\)。下面将重点讨论轴对齐的矩形对线段的裁剪算法。 大致有五种算法,可以解决轴对齐的矩形对线段的裁剪算法。最早由Danny Cohen&Ivan Sutherland提出的一种算法,称为Cohen-Sutherlad裁剪算法(简称CS算法),该算法把平面分成9个区域,根据点的位置确定与矩形的相交边。后来,Cyrus&Beck(1978)提出了Cyrus-Beck裁剪算法(简称CB算法),线段用参数方程来表示,计算与矩形的每条边所在的直线的交点,但是该算法的效率相对较低。Liang&Barsky(1984)尝试对CS算法进行改进,提出了该算法的一种变种,称为Liang-Barsky裁剪算法(简称为LB算法),Liang和Barsky(1992)进一步对LB算法进行了改进。Sobkow&Pospisil&Yang(1987)描述了另外一种线段的裁剪算法,称为快速裁剪算法(简称为SPY算法)。Nicholl,Lee&Nicholl对前面四种线段裁剪算法进行了较为深入地分析和比较,并且描述了一种更加高效的算法,称为Nicholl-Lee-Nicholl算法(简称为NLN算法)。对比五种算法的性能,它们并不是在数量级上的差别,只是算法中运算个数的差别,比如NLN算法拥有最少的除法次数。CS、LB和SPY在不同机器、不同的数据集上,会显示出不同的算法性能。在算法实现上,NLN和SPY算法较为复杂,CS和LB相对简单。如果不会特别苛求算法的性能,建议选择CS或者LB算法,接下来将详细地描述这两种算法。 5.3.2. Cohen-Sutherland裁剪算法 设矩形的左侧边为\(x={{x}_{\min }}\),右侧边为\(x={{x}_{\max }}\),下侧边为\(y={{y}_{\min }}\),上侧边为\(y={{y}_{\max }}\)。矩形的四条边所在的直线,把平面分成9个区域,可以用4位的编码来指定点所在的区域,我们可以作如下所规定: 0000       点在矩形区域内; 0001       点在左侧边的左侧; 0010      

spacer
浏览量:24

5.2. 点与矩形

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 5.2. 点与矩形 5.2.1. 点到矩形的矩离 问题描述:在二维空间上,计算点P到矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}},-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}},-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)的距离。 图5.2 矩形把平面划分的9个区域 令\(\Delta =P-C\),有\({{s}_{0}}=\Delta \cdot {{\vec{e}}_{0}}\)和\({{s}_{1}}=\Delta \cdot {{\vec{e}}_{1}}\),矩形上与P最接近的点取决于参数平面\( ({{t}_{0}},{{t}_{1}})\)上9个区域中的哪一个包含\(({{s}_{0}},{{s}_{1}})\),平面上9个区域的划分如图5.2所示。若\(({{s}_{0}},{{s}_{1}})\)落在区域0中,说明点P在矩形内部,它到矩形的距离是0;若\(({{s}_{0}},{{s}_{1}})\)落在区域1、3、5、7上,则\(({{s}_{0}},{{s}_{1}})\)到矩形对应的顶点上的距离最近;若\(({{s}_{0}},{{s}_{1}})\)落在区域2、6上,则最近距离是点P到边\({{\vec{e}}_{1}}\)的投影;若\(({{s}_{0}},{{s}_{1}})\)落在区域4、8上,则最近距离是点P到边\({{\vec{e}}_{0}}\)的投影。 在算法的具体实现中,不需要将参数平面划分成9个区域,然后分成不同的区域来处理,采用每次处理一维,点与矩形距离的伪码如下所示: 求点P到矩形对象\(R:X({{t}_{0}},{{t}_{1}})=C+{{t}_{0}}\cdot {{\vec{e}}_{0}}+{{t}_{1}}\cdot {{\vec{e}}_{1}}\)的距离的平方 1.    计算\(\Delta =P-C\); 2.    计算\({{s}_{0}}=\Delta \cdot {{\vec{e}}_{0}}\)和\({{s}_{1}}=\Delta \cdot {{\vec{e}}_{1}}\); 3.    distSquare = 0; 4.   

spacer
浏览量:22

5.1. 矩形对象简介

本篇文章禁止用于任何商业目的,版权申明、版本说明等见《前言》。 PDF文档和源码下载地址:https://github.com/twinklingstar20/Programmers_Computational_Geometry 5.1. 矩形对象简介 二维的矩形对象,在图形学上起到重要的作用,比如碰撞检测。一个矩形形对象如图5.1所示,可以用等式(5.1)表示,其中C表示矩形的中心,\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\)都是单位长度,表示矩形上互相垂直的两个方向,\({{u}_{0}}\)和\({{u}_{1}}\)分别是矩形在两个方向上的半长度,则有\(-{{u}_{0}}\le {{t}_{0}}\le {{u}_{0}}\)和\(-{{u}_{1}}\le {{t}_{1}}\le {{u}_{1}}\)。 \ 图5.1 矩形对象 实现矩形对象时,可以采用保存等式(5.1)中的矩形中心C,单位长度的两个方向向量\({{\vec{e}}_{0}}\)和\({{\vec{e}}_{1}}\),以及在两个方向上的边的半长\({{u}_{0}}\)和\({{u}_{1}}\)。采用这种表示形式,在计算矩形面积、周长,求点与矩形的距离等问题,都特别的方便。例如计算矩区的面积为\(4\cdot {{u}_{0}}\cdot {{u}_{1}}\),矩形的周长为\(2\cdot ({{u}_{0}}+{{u}_{1}})\)。

spacer