计算机编程之直行,射线与线段相交理论
在二维空间中,两条直线(射线与线段是一种特例)有如下几种关系:
a) 相交(有且只有一个交点)
b) 平行(无交点)
c) 重叠
假想在直线L1上有一个运动的点 M; 那么M的方程使用参数可以表示为M=A+(B-A)t, 其中t 为参数,可以理解为直线 L1上有一个运动的点M.
a) 当 t<0时在 A 外运动,
b) 当 t=0时, M就是 A点;
c) 当 t>0且 t<1时, M 就在 AB 之间运动;
d) 当 t=1时,M就是B;
e) t>1时, M就在 B外运动
如果设 在 L2上有一个动点 N;同样 L2的方程为: N=C+(D-C)s,其中 s 为参数
因为求交点,所以 M=N;则有:
A+(B-A)t = C+(D-C)s;
此处引入向量的叉乘:a=[x0,y0],b=[x1,y1],cross(a,b)=x0*y1-x1*y0;关键的来了,自己与自己叉乘为0;
先求 t;
(B-A)t = (C-A)+(D-C)s;
等式两边叉乘(D-C),则有:
cross((B-A),(D-C))t = cross((C-A), (D-C));
同理求 s 得方程如下:
cross((D-C), (B-A))s = cross((A-C), (B-A));
a) 两个方程的系数不为0,则有相交且有一个交点;
b) 如果系数为0,如果等式右边有个为0,则两条线重合;
c) 如果系数为0,如果等式右边都不为0,则两条线平行;
如若有交点:
t= cross((C-A), (D-C))/ cross((B-A),(D-C));
s= cross((A-C), (B-A))/ cross((D-C), (B-A))
t 与 s 参数的值域如下:
t∈[0,1]且 s∈[0,1],相交线段线段 AB 与线段 CD 相交.
t∈[0,1]且 s∈[0,+∞],相交线段线段 AB 与射线 CD 相交.
t ∈ [0,1]且 s ∈ [0,-∞],相交线段线段 AB 与射线 DC 相交.
…(没有完,其他情况自己想)
C++实现方式
#include <stdio.h> //
#include <math.h> /* fabs */
#include <float.h> //FLT_EPSILON
class Vec2 {
public:
double x;
double y;
public:
Vec2(double x=0, double y=0) {
this->x = x;
this->y = y;
}
const Vec2 operator+(const Vec2 &b) const {
Vec2 r;
r.x = this->x+b.x;
r.y = this->y+b.y;
return r;
}
const Vec2 operator*(const double s) const {
Vec2 r;
r.x = this->x*s;
r.y = this->y*s;
return r;
}
const Vec2 operator-(const Vec2 &b) const {
Vec2 r;
r.x = this->x-b.x;
r.y = this->y-b.y;
return r;
}
const double cross(const Vec2 &b) const {
return this->x * b.y - b.x*this->y;
}
};
class SegmentLine;
class Line {
public:
Vec2 start;
Vec2 end;
public:
Line(Vec2 &start, Vec2 &end) {
this->start=start;
this->end=end;
}
Line(double x0, double y0, double x1, double y1) {
this->start = Vec2(x0, y0);
this->end= Vec2(x1, y1);
}
virtual bool intersection(const Line& b, double &t, double &s) {
Vec2 d0 = b.end-b.start;
Vec2 d1 = this->end-this->start;
double dd0 = (this->end-this->start).cross(d0);
double dd1 = (b.end-b.start).cross(d1);
if(fabs(dd0) < FLT_EPSILON || fabs(dd1) < FLT_EPSILON ) {
return false;
}
t = (b.start - this->start).cross(d0)/dd0;
s = (this->start-b.start).cross(d1)/dd1;
return true;
}
virtual bool intersection(const Line& b, Vec2 &point) {
double t = 0;
double s = 0;
bool r = intersection(b, t ,s);
if(r) {
//通过判断 t与 s 的范围来决定线的类型;
//小于0,
//等于0
//大于0且小于1,
//等于1
//大于1
Vec2 xx = this->end - this->start;
point = this->start + xx * t;
}
return r;
}
// bool intersection(const SegmentLine& b, Vec2 &point) {
// return b.intersection(this, point);
// }
};
int main(void) {
Vec2 A(-1, 0);
Vec2 B(1, 0);
Vec2 C(0.5, 1);
Vec2 D(0.5, 0.1);
Line l0(A, B);
Line l1(C, D);
Vec2 point;
bool r = l0.intersection(l1, point);
printf("%d, %f,%f\n", r, point.x, point.y);
return 0;
}