空间或平面判断两线段相交(求交点)
目录
1. 概述
研究了一些空间计算几何的相关算法，现在对《计算几何》这门科学有了更多的认识。以前，解决空间几何问题都是通过解析几何的角度来解决问题的(高中数学知识)，虽然解决思路比较直观，但是很多时候都要付出昂贵的代价，比如精度、效率，以及繁复的判断。而计算几何是通过向量来解决空间几何问题的，可以规避这些问题，使得精度和效率更高。
2. 详论
2.1. 解析几何算法
比如说，在平面中判断两线段相交，我们可以很容易通过解析几何来求解，联立两直线的代数方程：
(y−y2)/(y1−y2)=(x−x2)/(x1−x2)(y−y2)/(y1−y2)=(x−x2)/(x1−x2)
然后对这个二元二次方程进行求解。很容易得到相应算法的代码：
//判断两线段相交 bool IsIntersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4, double py4) { bool flag = false; double d = (px2 - px1) * (py4 - py3) - (py2 - py1) * (px4 - px3); if (d != 0) { double r = ((py1 - py3) * (px4 - px3) - (px1 - px3) * (py4 - py3)) / d; double s = ((py1 - py3) * (px2 - px1) - (px1 - px3) * (py2 - py1)) / d; if ((r >= 0) && (r <= 1) && (s >= 0) && (s <= 1)) { flag = true; } } return flag; }
可以看出这个算法其实并不严密，其实缺少了对一些极端条件的判断，比如与坐标轴平行的情况，两直线平行的情况，还需要做额外的判断。同时用了很多乘法和除法，算法效率并不高。
2.2. 同侧法
这种算法的思想是：如果两条线段相交，那么一条线段的两端点必然位于另一条线段的两端点的异侧。那么问题就可以转换成点是否在一条线段的同侧。同侧判断可以通过向量叉乘的方法来实现，即判断最后叉乘的方向是否相同。
这个算法与平面中判断点在三角形内算法这篇文章介绍的同侧/异侧判断是一样的，我认为算是比较优秀快速的算法了。不过这个算法可以判断定性判断，无法定量判断准确的交点。而且实际使用过程中，似乎精度不太准确（个人实验结论，尤其是位于三角形边上的点）。
2.3. 向量方程法
2.3.1. 原理
已知空间中线段的起点O和终点E，那么显然方向向量D为：
D=E−OD=E−O
这时，可以确定线段上某一点P为：
P=O+tDP=O+tD
其中，t为范围满足0<=t<=10<=t<=1的标量。
这个方程就是线段上某一点的向量方程。如果要求两线段的交点，很显然可以将两个线段进行联立：
{P=O1+t1D1P=O2+t2D2{P=O1+t1D1P=O2+t2D2
上式-下式,有：
t1D1−t2D2=O2−O1=O12(1)(1)t1D1−t2D2=O2−O1=O12
在平面上展开，也就是使用X和Y分量：
[D1.x−D2.xD1.y−D2.y][t1t2]=[O12.xO12.y][D1.x−D2.xD1.y−D2.y][t1t2]=[O12.xO12.y]
那么这个问题就转换成了求解2行2列的线性方程组，如果有解，说明存在交点并直接求出。2行2列线性方程组直接使用克莱姆法则求解即可。
2.3.2. 实现
具体的C++实现代码如下：
//空间直线 template <class T> class LineSegment { public: Vec3<T> startPoint; Vec3<T> endPoint; Vec3<T> direction; Vec3<T> min; Vec3<T> max; LineSegment() { } LineSegment(Vec3<T> start, Vec3<T> end) { startPoint = start; endPoint = end; direction = end - start; CalMinMax(); } inline void Set(Vec3<T> start, Vec3<T> end) { startPoint = start; endPoint = end; direction = end - start; CalMinMax(); } inline void CalMinMax() { min.x() = std::min<T>(startPoint.x(), endPoint.x()); min.y() = std::min<T>(startPoint.y(), endPoint.y()); min.z() = std::min<T>(startPoint.z(), endPoint.z()); max.x() = std::max<T>(startPoint.x(), endPoint.x()); max.y() = std::max<T>(startPoint.y(), endPoint.y()); max.z() = std::max<T>(startPoint.z(), endPoint.z()); } //两条线段相交 inline static bool Intersection2D(LineSegment & line1, LineSegment & line2, Vec3<T>& insPoint) { double D = -line1.direction.x() * line2.direction.y() + line1.direction.y() * line2.direction.x(); if(D == 0.0) { return false; } auto O12 = line2.startPoint - line1.startPoint; T D1 = -O12.x() * line2.direction.y() + O12.y() * line2.direction.x(); T D2 = line1.direction.x() * O12.y() - line1.direction.y() * O12.x(); T t1 = D1 / D; if(t1<0 || t1 > 1) { return false; } T t2 = D2 / D; if(t2<0 || t2 > 1) { return false; } insPoint = line1.startPoint + line1.direction * t1; //这样计算得到的Z值是不准确的 return true; } };
2.3.3. 三维展开
这个算法还有一个好处是也很适合三维空间展开，因为线段上点的向量方程是二三维通用的。当使用X，Y，Z三个分量带入式(1)，这时得到的就是一个3行2列的超定方程组。可以继续求解原来的2行2列的线性方程组，只有当得到的t1，t2也能满足Z方向上的式子成立，才能说明存在交点。
3. 参考
分类: 计算几何
