计算机算法基础 第2版 习题及答案 第12章 .docx

PAGE22

第12章 计算几何基础

给定以下X-Y平面上两个向量，求它们的点积和叉积：

p1=(4,-6)，p2=(-2,7)

p1=(0,8)，p2=(5,-2)

解：(a) p1·p2=4-6·-27=-

p1′p2=4-2-67=28

(b) p1·p2=08·5-2=

p1′p2=058-2

假设平面上四个点p1，p2，p3，p4的坐标如下，用叉积判断线段p1p2和

p1=(3,5)，p2=(-4,6)，p3=(-2,-1)和p4=(1,-5)

p1=(-1,8)，p2=(5,-1)，p3=(1,6)和p4=(-4,-7)

解：(a) p1=(3,5)，p2=(-4,6)，p3=(-2,-1)和p4=(1,-5)

d1=(p2–p1)?(p3–p1)=x2-x1x

d2=(p2–p1)?(p4–p1)=x2-x1x4

因为d1?0，显然不共线。又因为d1?d20所以两线段不相交。

p

p3

p4

p2

p1

O

(b) p1=(-1,8)，p2=(5,-1)，p3=(1,6)和p4=(-4,-7)

d1=(p2–p1)?(p3–p1)=x2-x1x3-x

d2=(p2–p1)?(p4–p1)=x2-x1x4-x1y2

d3=(p4–p3)?(p1–p3)=x4-x3x1-

d4=(p4–p3)?(p2–p3)=x4-x3x

因为d1?0，显然不共线。又因为d1?d20和d3?d40，所以两线段相交。

p

p3

p4

p2

p1

O

线段p1p2和p3p4相交但不共线有三种情况，即交点不与任何端点重合，交点与其中一个线段的一个端点重合，和交点与两个线段各有一个端点重合。书中算法Segment-Intersect不给予分类。请修改书上算法使得每种相交类型得以确定，并指明交点与哪一个端点或哪两个端点重合

解： 修改后算法如下，正确性显然。

Modified-Segment-Intersect(p1,p2,p3,p4) //p1p2和

d1?(p2–p1)?(p3–p1)

d2?(p2–p1)?(p4–p1)

d3?(p4–p3)?(p1–p3)

d4?(p4–p3)?(p2–p3)

ifd1=d2=0 //p1p2和p3p4共一直线，此时必有d3

then ifx1=x2

then ifmax{y1,y2}min{y3,y4}ormax{y3,y4}min{y1,y2}

thenreturnfalse //不相交

elsereturntrue //相交

endif

else ifmax{x1,x2}min{x3,x4}ormax{x3,x4}min{x1,x2}

thenreturnfalse //不相交

elsereturntrue //相交

endif

endif

else if(d1?d20)or(d3?d40)

thenreturnfalse //不相交

elsecase //相交

(1)(d1?d20)and(d3?d40)

return(true,交点不与任何端点重合)

(2)(d1?d20)and(d3=0)and(d4?0)

return(true,交点只与p1重合)

(3)(d1?d20)and(d4=0)and(d3?0)

return(true,交点只与p2重合)

(4)(d3?d40)and(d1=0)and(d2?0)

return(true,交点只与p3重合)

(5)(d3?d40)and(d2=0)and(d1?0)

return(true,交点只与p4重合)

(6)(d1=0)and(d3