计算几何学.pptx

计算几何学.pptx计算几何学
朱成名
2014/4/18
大纲
2
计算几何的基本工具
计算几何的常见问题
总结
线段方面的问题
凸包方面的问题
最远/近点对问题
叉积
点积
3
计算几何的基本工具
叉积(向量积)
已知有向线段
op1
=(x1,y1),
op2
=(x2,y2).
op1
op2
和
的叉积为:
op1 ×
op2
几何意义:是以和为边的平行四边形的有向面积。
op1
op2
O(0,0)
p2(x2,y2)
p1(x1,y1)
另一种定义:
op1 ×
op2
=det
x1,x2
y1,y2
p(x1+x2,y1+y2)
= x1y2 – x2y1
op2 ×
op1
= -
= -det
x2,x1
y2,y1
= op1 × op2 ×sin(α)。
α
4
右手法则可快速判断两个平面向量叉积的方向,继而判断两个向量的相对位置关系。
O(0,0)
p2(x2,y2)
p1(x1,y1)
op1×op2 >0,表示op1到op2成逆时针,即op2在op1的左边。
op2×op1 < 0
若op1×op2 = 0,则表示op1和op2共线(同向或反向)。
O(0,0)
p1(x1,y1)
p2(x2,y2)
共向
O(0,0)
p1(x1,y1)
p2(x2,y2)
反向
5
计算几何的基本工具
点积(数量积)
已知有向线段
op1
=(x1,y1),
op2
=(x2,y2)。
op1
op2
和
的点积为:
op1 ·
op2
几何意义:是在上的投影与长度的乘积。
op1
op2
= op1 ×cos(α)× op2 。
op2
O(0,0)
p1(x1,y1)
p2(x2,y2)
α
另一种定义:
op1 ·
op2
= x1x2 + y1y2
= op2·
op1
cos(2 Π- α) = cos(- α)= cos(α)
6
大纲
计算几何的基本工具
计算几何的常见问题
总结
线段方面的问题
凸包方面的问题
最远/近点对问题
叉积
点积
7
计算几何的常见问题
线段方面的问题
?
O(0,0)
p1(x1,y1)
p2(x2,y2)
计算叉积op1×op2。
右
左
若>0,即op2在op1的左边,因此在p1点向左转。
若<0,即op2在op1的右边,因此在p1点向右转。
若=0,即op2与op1共线。
8
?
a(x1,y1)
d(x4,y4)
c(x3,y3)
b(x2,y2)
A
B
方法:检查每条线段是否跨越了包含另一条线段的直线。
即点c、d分别在线段A所在直线的两侧,同时点a、b分别在B所在直线的两侧,则可以确定A与B相交.
若ab×ad和ab×ac结果异号,
ab×ad>0,即ad在ab的左边; ab×ac<0,即ac在ab的右边。
ab×ad<0,即ad在ab的右边; ab×ac>0,即ac在ab的左边。
ac和ad分别在A所在直线的左右两侧。
即点c、d分别在线段A所在直线的两侧
线段ab和线段cd相交
ab×ac与ab×ad的结果为异号
cd×ca与cd×cb的结果为异号
9
特殊情况:
a(x1,y1)
d(x4,y4)
c(x3,y3)
b(x2,y2)
此时ab ×ad=0,但只有(一)是相交的。
a(x1,y1)
d(x4,y4)
c(x3,y3)
b(x2,y2)
(一)
(二)
即知道某条线段端点在另一线段所在直线上时,需要判断该点是否在另一线段上。
方法一:Xa<=Xd<=Xb  and  Ya <=Yd<=Yb;
方法二: ad · db>0 ( db (ad)指向ad (db)的前方)
ad · db >0
ad · db <0
10
判断两条线段是否相交?
a
b
d
c
ab ×ad与ab ×ac结果异号;
&& cd ×ca与cd ×cb结果异号
return true
真
有同号
假
无同号,有0
return false
交点是否在线段上
是
否
return true
return false
是否还存在0
是
否