点和直线

直线的参数表示:直线可以用直线上一点$P_0$和方向向量v表示(虽然这个向量的大小没什么用处)。直线上所有点P满足$P=P_0+tv$,其中t称为参数。如果已知直线上的两个不同点A和B,则方向向量为$B-A$,所以参数方程为$A+(B-A)t$。
参数方程最方便的地方在于直线、射线和线段的方程形式是一样的,区别仅仅在于参数。直线的t没有范围限制,射线的t>0,线段的t在0—1之间。这样,很多对于直线适用的公式可以很方便地用在射线和线段上。
直线交点:下面介绍参数方程下的直线交点公式。设直线分别为$P+tv$和$Q+tv$,设向量$u=P-Q$,交点在第一条直线的参数为$t_1$,第二条直线上的参数为$t_2$,则x和y坐标可以列出一个方程,解得(过程略):
$t1=\frac{cross(w,u)}{cross(v,w)},t2=\frac{cross(v,u)}{cross(v,w)}$
代码如下:

1
2
3
4
5
6
7
//调用前请确保两条直线P+tv和Q+tw有唯一交点。当且仅当cross(v,w)非0
point GetLineIntersection(point P,vector v,point Q,vector w)
{
vector u=P-Q;
double t=cross(w,u)/cross(v,w);
return P+v*t;
}

要注意的是,从上数公式可以看到,如果P,v,Q,w的各个分量均为有理数,则交点坐标也是有理数。在精度要求极高的情况下,可以考虑自定义分数类。
点到直线的距离:点到直线的距离是一个常用的函数,可以用叉积算出,即可用叉积算出,即用平行四边形的面积除以底,代码如下:

1
2
3
4
5
double DistanceToLine(point P,point A,point B)
{
vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2))/Lenth(v1);//如果不取绝对值,得到的是有向距离
}

点到线段的距离:点到线段的距离有两种可能,如图
这里写图片描述

简单地说,设投影点为Q,如果Q在线段AB上,则所求距离就是P点直线AB的距离(左图);如果Q在射线BA上,则所求距离为PA距离;否则为PB距离。判断Q的位置可以用点积进行。

1
2
3
4
5
6
7
8
double DistanceToSegment(point P,point A,point B)
{
if(A==B) return Length(P-A);
vector v1=B-A,v2=P-A,v3=P-B;
if(dcmp(Dot(v1,v2))<0) return Length(v2);
else if(dcmp(Dot(v1,v3))>0) return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}

还有其他方法可以求出上述距离,但不仅速度慢,而且也更容易产生精度误差。
点在直线上的投影。虽然上面的运算避免了求出P在直线AB上的投影点Q,但有时候还是需要把它求出来的。为此,我们把直线AB写成参数式A+vt(v为向量AB),并且设Q的参数为$t_0$,那么Q=A+$t_0$v。根据PQ垂直于AB,两个向量的点积应该为0,因此Dot(v,P-A)-$t_0$*Dot(v,v)=0,这样就可以解出$t_0$,从而等到Q点。

1
2
3
4
5
point GetLineProjection(point P,point A,point B)
{
vector v=B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}

线段相交判定:最后介绍线段相交判定,即给定两条线段,判断是否相交。我们定义“规范相交”为两个线段恰好有一个公共点,且不在任何一条线段的端点。线段规范相交的必要条件是:每条线段的两个端点都在另一条线段的两侧(这里的“两侧”是指叉积的符号不同)。代码如下:

1
2
3
4
5
6
bool SegmentProperIntersection(point a1,point a2,point b1,point b2)
{
double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),
c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}

如果允许在端点处相交,情况就比较复杂了:如果c1和c2都是0,表示两线段共线。这时可能会有部分重叠的情况;如果c1和c2不都是0,则只有一种相交方法,即某个端点在另外一条线段上。为了判断上述情况是否发生,还需要如下一段判断一个点是否在一条线段上(不包含端点)的代码:

1
2
3
4
bool OnSegment(point p,point a1,point a2)
{
return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p))<0;
}