[math]判断线段是否相交及夹角
文章目录
- 向量
- 点乘
- 叉乘
- 线段相交
- 快速排斥
- 跨立实验
- 线间夹角
通过向量间的叉乘与点乘,可判断线段间的关系。
向量
向量(也称为矢量),指具有大小和方向的量。它可以形象化地表示为带箭头的线段。
- 箭头所指:代表向量的方向;
- 线段长度:代表向量的大小。
点乘
点 a ( x 1 , y 1 ) , b ( x 2 , y 2 ) a(x_1,y_1),b(x_2,y_2) a(x1,y1),b(x2,y2)的点乘为: a ⋅ b = x 1 ∗ x 2 + y 1 ∗ y 2 a\cdot b=x_1*x_2 + y_1*y_2 a⋅b=x1∗x2+y1∗y2
其几何意义: a ⋅ b = ∣ a ∣ ⋅ ∣ b ∣ ⋅ c o s θ a\cdot{b}=|a|\cdot |b|\cdot cos\theta a⋅b=∣a∣⋅∣b∣⋅cosθ
向量的点乘可以用来计算两个向量之间的夹角,进一步判断这两个向量是否正交(垂直)等方向关系:
- a ⋅ b > 0 a\cdot b>0 a⋅b>0:方向基本相同,夹角在0~90度之间
- a ⋅ b = 0 a\cdot b=0 a⋅b=0:正交,互相垂直
- a ⋅ b < 0 a\cdot b<0 a⋅b<0:方向基本相反,夹角在90~180度之间
同时,还可以用来计算一个向量在另一个向量方向上的投影长度。
叉乘
点
a
(
x
1
,
y
1
)
,
b
(
x
2
,
y
2
)
a(x_1,y_1),b(x_2,y_2)
a(x1,y1),b(x2,y2)的叉乘为:
a
×
b
=
∣
x
1
,
y
1
x
2
,
y
2
∣
=
x
1
∗
y
2
−
x
2
∗
y
1
a×b=\left| \begin{matrix} x_1, & y_1 \\ x_2, & y_2 \end{matrix} \right| =x_1*y_2 - x_2*y_1
a×b=∣
∣x1,x2,y1y2∣
∣=x1∗y2−x2∗y1
设 p ( 0 , 0 ) p(0,0) p(0,0)为原点,则:
- a × b > 0 a×b>0 a×b>0,表示 p b ⃗ \vec{pb} pb在 p a ⃗ \vec{pa} pa的逆时针方向;
- a × b = 0 a×b=0 a×b=0,表示 p b ⃗ \vec{pb} pb与 p a ⃗ \vec{pa} pa共线;
- a × b < 0 a×b<0 a×b<0,表示 p b ⃗ \vec{pb} pb在 p a ⃗ \vec{pa} pa的顺时针方向;
- ∣ a × b ∣ |a×b| ∣a×b∣,是以 p a ⃗ \vec{pa} pa与 p b ⃗ \vec{pb} pb为临边的平行四边形的面积
线段相交
判断两条线段是否相交:
- 快速排斥;
- 跨立实验;
快速排斥
通过快速排斥实验,可初步判断两条线段是否有相交的可能性,从而减少计算量:以两条线段作为对角线画矩形,判断矩形是否重合;若不重合,肯定不相交。
为此需要检验他们的最大坐标与最小坐标间的关系(任一项为真,则一定不相交):
max(C.x, D.x)<min(A.x, B.x)
或max(C.y, D.y)<min(A.y, B.y)
max(A.x, B.x)<min(C.x, D.x)
或max(A.y, B.y)<min(C.y, D.y)
跨立实验
两条线段AB、CD相交,则:
- 线段AB与CD所在的直线相交:即A、B两点分别在直线CD的两侧;
- 线段CD与AB所在的直线相交:即C、D两点分别在直线AB的两侧;
以C、D在AB两侧为例,连接AC、AD得到两个向量:
- 向量AC在AB的逆时针方向:即
AB×AC>0
- 向量AC在AB的顺时针方向:即
AB×AD<0
- 两个叉乘结果为异号:即
(AB×AC)*(AB×AD)<0
若叉乘结果为同号,则说明在同一边,肯定不相交。
同理判断A、B是否在CD的两侧;若A、B两点分别在直线CD的两侧,且C、D两点分别在直线AB的两侧,则线段AB与CD一定相交(在完成排斥实验的基础上)
func lineIsIntersect(AB [2]Point, CD [2]Point) bool {
ACx := CD[0].X - AB[0].X
ACy := CD[0].Y - AB[0].Y
ADx := CD[1].X - AB[0].X
ADy := CD[1].Y - AB[0].Y
ABx := AB[1].X - AB[0].X
ABy := AB[1].Y - AB[0].Y
AC_AB = ACx*ABy-ABx*ACy
AD_AB = ADx*ABy-ABx*ADy
return ()*() <= 0
}
线间夹角
通过点乘,可求出两条线间的夹角;通过计算夹角的cos值,可知向量间方向关系。
func dot(AB [2]image.Point, CD [2]image.Point) int {
ABx := AB[1].X - AB[0].X
ABy := AB[1].Y - AB[0].Y
CDx := CD[1].X - CD[0].X
CDy := CD[1].Y - CD[0].Y
return ABx*CDx + ABy*CDy
}
func dist(line [2]image.Point) float64 {
distX := line[1].X - line[0].X
distY := line[1].Y - line[0].Y
return math.Sqrt(float64(distX*distX + distY*distY))
}
func calcCos(AB [2]image.Point, CD [2]image.Point) float64 {
return float64(dot(AB, CD)) / (dist(AB) * dist(CD))
}