吉林大学：《计算机图形学》课程电子教案（PPT课件）第五章 图形运算 第二节 多边形表面的交线计算

两线段AB和CD交点的算法 1.〔计算行列式〕△←(x。-×)(y。y)-(x。 xa(y。y 若△=0，则两线段重合或平行，可算做无交 点，算法结束； 2.〔计算交点参数〕人←(x。×)y。y) (x。-xy。ya)/△ 若入1，则无交点，算法结束； u←(x。-×)(y。ya)-(x。-x)(y。ya)/△ 若K0或4>1，则无交点，算法结束；

两线段AB和CD交点的算法 1.〔计算行列式〕 ←(xb -xa )(yc -yd )-(xc - xd )(yb -ya) 若 =0,则两线段重合或平行,可算做无交 点,算法结束; 2.〔计算交点参数〕 ←((xc -xa )(yc -yd )- (xc -xd )(yc -ya ))/ 若 1,则无交点,算法结束; ←((xb -xa )(yc -ya )-(xc -xa )(yb -ya ))/ 若 1,则无交点,算法结束;   λ λ λ     

3.〔计算交点〕x←x+入(x。×),y←y+入y。 ya),输出交点(x,y)后算法结束； 多条线段求交 寻找这样的算法，其计算工作量要大体 上与交点个数成正比，即只对有可能相交 的两线段计算交点，对不可能相交的线段 不计算交点，使算法有更好的效率

3.〔计算交点〕x←xa + (xb -xa ),y←ya + (yb - ya ),输出交点(x,y)后算法结束; λ λ 多条线段求交 寻找这样的算法,其计算工作量要大体 上与交点个数成正比,即只对有可能相交 的两线段计算交点,对不可能相交的线段 不计算交点,使算法有更好的效率

我们称平面内两条线段在横 坐标x处是可比较的，如果存在一 条通过x的垂直线，此线与两条线 段都相交。我们规定一个在x处的 "上面"关系为：在x处，线段S在 S,的上面，记为S>S2,如果在x处 可比较，且S与垂直线的交点位于 S,与垂直线的交点的上面

我们称平面内两条线段在横 坐标x处是可比较的,如果存在一 条通过x的垂直线,此线与两条线 段都相交。我们规定一个在x处的 "上面"关系为：在x处,线段S1在 S2的上面,记为S1 >x S2 ,如果在x处 可比较,且S1与垂直线的交点位于 S2与垂直线的交点的上面

1 S2 S3 S4 u 其中，S2>uS4S1>vS2,S22,S4,S1>vS4

u  其中，S2 >μS4 ,S1 >νS2 ,S2 >νS4 ,S1 >νS4

规定的次序关系对垂直的线段不适合 两线段相交的必要条件，即若两线段相交， 则必然存在某个x,使它们在规定的次序关系 >x下是相邻的。 算法从左向右扫描，在扫描过程维持正确 的线段间上述次序关系。这种次序关系只能 有三种可能的变化方式： 1.遇见某条线段$的左端点，此时$应加入次序 关系。 2.遇见某线段$的右端点，此时$应从次序关系 中删除。 3.遇到某两条线段$和S,的交点，这时在次 序关系中S和S,交换位置

规定的次序关系对垂直的线段不适合 两线段相交的必要条件,即若两线段相交, 则必然存在某个x,使它们在规定的次序关系 >x下是相邻的。 算法从左向右扫描,在扫描过程维持正确 的线段间上述次序关系。这种次序关系只能 有三种可能的变化方式: 1．遇见某条线段S的左端点,此时S应加入次序 关系。 2．遇见某线段S的右端点,此时S应从次序关系 中删除。 3．遇到某两条线段S1和S2 的交点,这时在次 序关系中S1和S2交换位置

算法实施需要两个基本的数据结构： 扫描线状态表和事件点进度表 扫描线状态表L中存放按所规定次序关系>× 排序的线段的序列。此表初始应为空，在平面 扫描过程中当关系>改变时变化。 事件点指扫描进行中可能使所规定次序关 系>发生变化的点，存放于事件点进度表E中， 该表初始时应是排序的要求交点的各线段端点 的坐标。在平面扫描过程中求出的交点，应及 时地插入到事件点进度表中

算法实施需要两个基本的数据结构: 扫描线状态表和事件点进度表 扫描线状态表L中存放按所规定次序关系>x 排序的线段的序列。此表初始应为空,在平面 扫描过程中当关系>x改变时变化。 事件点指扫描进行中可能使所规定次序关 系>x发生变化的点,存放于事件点进度表E中, 该表初始时应是排序的要求交点的各线段端点 的坐标。在平面扫描过程中求出的交点,应及 时地插入到事件点进度表中

扫描线状态表应能支持以下四个操作： (1) INSERT(S,L),把线段S插入到扫描 线状态表L中，注意应插入到适当位置 以保持正确的次序关系。 (2) DELETE(S,L),从L中删除线段S。 (3) ABOVE(S,L),返回次序关系中S上面 紧接着的线段的编号。 (4) BELOW(S,L),返回次序关系中S下 面紧接着的线段的编号

扫描线状态表应能支持以下四个操作: (1) INSERT(S,L),把线段S插入到扫描 线状态表L中,注意应插入到适当位置 以保持正确的次序关系。 (2) DELETE(S,L),从L中删除线段S。 (3) ABOVE(S,L),返回次序关系中S上面 紧接着的线段的编号。 (4) BELOW(S,L),返回次序关系中S下 面紧接着的线段的编号

事件点进度表E应能支持以下三个操 作： (1) MIN(E),取出表E中的最小元素。 (2) INSERT(x,E),把横坐标为x的一个 点插入到表E中，插入要使E中事件点存 放保持递增次序。 (3)MEMBER(x,E),判定横坐标为x的 点是否在事件点进度表E中

事件点进度表E应能支持以下三个操 作: (1) MIN(E),取出表E中的最小元素。 (2) INSERT(x,E),把横坐标为x的一个 点插入到表E中,插入要使E中事件点存 放保持递增次序。 (3 ) MEMBER(x,E),判定横坐标为x的 点是否在事件点进度表E中

算法： 1.〔事件点进度表E初始化)将输入待求交点的 n条线段的2n个端点按x,y字典式排序后存放 于表E中； 2.(准备收集交点)A-⑩；{A是一集合，初为 空，准备存入找到的交点 3.〔平面扫描)若表E不为空，则进行(1)(3)循 环。直到表E为空时算法结束。 3.1(取出当前事件点)P←-MNE); 3.2(当前事件点处理)考查当前事件点P,分三 种情况： (1)若P是边S的左端点，则做：INSERT(S,L;

算法: 1.〔事件点进度表E初始化〕将输入待求交点的 n条线段的2n个端点按x,y字典式排序后存放 于表E中; 2.〔准备收集交点〕A← ;{A是一集合,初为 空,准备存入找到的交点;} 3.〔平面扫描〕若表E不为空,则进行(1)~(3)循 环。直到表E为空时算法结束。 3.1〔取出当前事件点〕P←MIN(E)； 3.2〔当前事件点处理〕考查当前事件点P,分三 种情况: (1) 若P是边S的左端点,则做：INSERT(S,L); 

S=ABOVE(S,L); S2=BELOW(S,L); 若S和S相交，则求出的交点送入集和A中； 若S和S,相交，则求出的交点送入集和A中； (2)若P是边S的右端点，则做： S=ABOVE(S,L); S,=BELOW(S,L); 若S和S2相交于点P的右边，则求出的交点送 入集和A中； DELETE(S,L); (3)若P是边S,和S,的交点，且在P的左边 S=ABOVE(S2),则做

S1=ABOVE(S,L); S2=BELOW(S,L); 若S和S1相交,则求出的交点送入集和A中; 若S和S2相交,则求出的交点送入集和A中; (2) 若P是边S的右端点,则做： S1=ABOVE(S,L); S2=BELOW(S,L); 若S1和S2相交于点P的右边,则求出的交点送 入集和A中； DELETE(S,L)； (3) 若P是边S1和S2的交点,且在P的左边 S1=ABOVE(S2 ),则做