计算几何之判断两直线是否相交并求两直线交点代码模板与证明

港控/mmm° 2022-11-05 10:59 216阅读 0赞

## 判断两直线是否相交 并 求两直线交点 ##

首先判断两直线的向量 v ⃗ \\vec v v与 w ⃗ \\vec w w的**叉积是否为0**，若为0说明两向量作为邻边构成的平行四边形面积为0，说明两向量平行或重合，则两直线无交点。

否则就相交，然后根据下面的函数模板求交点。

### 代码模板 ###

double cross(Point a,Point b)
    { 
     return a.x * b.y - b.x * a.y;
    }
    
    Point intersection(Point p,Vector v,Point q,Vector w)
    { 
    	Vector u = p - q;
    	double t = cross(w,u) / cross(v,w);
    	return { p.first+t*v.first , p.second+t*v.second};	//p + t*v
    }

### 判断方法与证明 ###

直线用**点向式**表示，即 p = p 0 + t v ⃗ p = p\_0 + t \\vec v p=p0\+tv，p0是直线上的一定点，v是直线的一个向量，我们的每一个t都对应直线上的一个点。在计算几何中，直线最常用的就是点向式表示法。

那么我们问题就是如何求出这个t，从而求出交点呢？我们知道cross是求两向量叉积的，叉积的几何意义就是以这两个向量为邻边的三角形的面积的两倍。因为 a ⃗ × b ⃗ = ∣ a ⃗ ∣ ⋅ ∣ b ⃗ ∣ ⋅ s i n θ \\vec a \\times \\vec b = |\\vec a| \\cdot |\\vec b| \\cdot sin\\theta a×b=∣a∣⋅∣b∣⋅sinθ  
![s][]  
如何我们来看这个求交点的求法，如下图：  
![eg][]

如图，将 v ⃗ \\vec v v平移到同起点q处，有  u ⃗ = p − q \\vec u = p-q u=p−q，直线交点是F，然后cross（w，u）就是三角形PQB面积的两倍，cross（v，w）是三角形ABQ面积的两倍，然后他们的比值 t就是两三角形面积的比值，并且两三角形同底，共同BQ底边，所以这个比值就是两高之比 h 1 h\_1 h1比 h 2 h\_2 h2。

然后再看三角形FPC和三角形QAD，他们有一组内错角相等，还有一直角相等，所以两三角形相似，因此两三角形的高之比就是两斜边之比，即PD比AQ也是t，因此那段距离PD和 v ⃗ \\vec v v的比就是t，所以p加上 t v ⃗ t \\vec v tv就是交点F。

[s]: /images/20221023/46a9dc3b85934f80b5c8a9be488d771a.png
[eg]: /images/20221023/bbcb4f6a41714e06b0b7cc21363ed23a.png