计算几何摸黑(2)-点和直线

相等判断函数

有的时候我们会用到判断一个数是否大于0，小于0或等于0。大于小于还好办，等于的话可能会出现例如0.00000000001≠0的现象，但是实际计算的时候这两个数是应该按照相等来算的。所以，我们可以自己定义一个函数dcmp()，来判断是否和0极其近似相等。

int dcmp(const double x)
{
    const double eps = 1e-10;
    if (std::fabs(x) < eps)
        return 0;
    else
        return x < 0 ? -1 : 1;
}

直线的参数表示

参数式：

\[P = P_0 + tv\]

这个式子的意思就是直线上的所有点的坐标都可以表示成\(P_0+tv\)的格式，其中\(v\)叫做直线的方向向量，\(P_0\)可以用来表示这条直线的起点，\(t\)叫做参数。

直线的交点

如果可以确保直线\(P+tv\)和\(Q+tw\)有唯一交点，且\(\vec v \cdot \vec w\)非零时，如果用\(t_1\)表示该点与\(P\)的距离，用\(t_2\)表示该点与\(Q\)的距离，易证

\[t_1=\frac{\vec w\times \vec u}{\vec v\times \vec w}, t_2=\frac{\vec v\times \vec u}{\vec v\times \vec w}\]

实现如下：

// 这里是用了上述的t1的思路，用交点和P的交点距离求交点
Point getLineInter(Point P, Vector v, Point Q, Vector w) // P + tv和Q + tw的……两点式……
{
    Vector u = P - Q;
    double t = mulCross(w, u) / mulCross(v, w);
    return P + v * t;
}

点到直线的距离

点到直线的距离，很简单，就是叉乘乘出来的那个平行四边形的面积除以它的底。

double getDisPointToLine(Point p, Point a, Point b)
{
    Vector v1 = b - a, v2 = p - a;
    return std::fabs(mulCross(v1, v2) / v1.getNorm()); // 如果不加std::fabs，得到的将是有向长度
}

点到线段的距离

点到线段的距离一共有三种情况，设投影点为\(Q\)，则有\(Q\)在线段\(AB\)上①，\(Q\)在线段\(AB\)的延长线上②，\(Q\)在线段\(AB\)的反向延长线上③。

对于①：所求的就是点 \(P\)到直线\(AB\)的距离。

对于②：所求的就是向量 \(\vec {PB}\)的模。

对于③：所求的就是向量 \(\vec {PA}\)的模。

至于\(Q\)的位置在哪里，可以用向量的点乘判断。

double getDisPointToSeg(Point P, Point a, Point b)
{
    if (a == b)
        return (P - a).getNorm();
    Vector v1 = b - a, v2 = p - a, v3 = p - b;
    if (dcmp(mulDot(v1, v2)) < 0)
        return v2.getNorm();
    else if (dcmp(mulDot(v1, v3)) > 0)
        return v3.getNorm();
    else
        return std::fabs(mulCross(v1, v2) / v1.getNorm());
}

点与线段的位置关系

一个点和一条线段无非就是两种关系，要么相交，要么相离。如果相交的话就相当于线段的两端点与该点所组成向量共线，且互相组成的两条向量方向相反。所以根据这两个性质，很容易想到需满足的性质为：点乘 < 0，且叉乘 == 0。为了避免精度错误，我这里用dcmp()来判断是否为0。

bool onSeg(Point P, Point hajimari, Point owari)
{
    return 
        dcmp( mulCross(hajimari - P, owari - P) ) == 0 &&
        dcmp( mulDot(hajimari - P, owari - P ) ) < 0;
}

线段相交判定

这里的线段相交，是指“规范相交”，即不算在端点处相交的情况。两线段相交的条件很好理解：每条线段的两个端点都在另一条线段的两侧。也就是说，一条线段两侧的端点所组成的向量分别和另一条线段自己构成的向量的叉乘符号相反。

bool isSegInter(Point a1, Point a2, Point b1, Point b2)
{
    double c1 = mulCross(a2 - a1, b1 - a1),
    c2 = mulCross(a2 - a1, b2 - a1),
    c3 = mulCross(b2 - b1, a1 - b1),
    c4 = mulCross(b2 - b1, a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

点在直线上的投影

既然是点在直线上的投影，那么我们可以把直线\(AB\)通过参数式表示成\(A + tv\)的形式，如果设\(P\)的投影点在\(AB\)上为\(Q\)，并且设\(Q\)的坐标为\(A + t_0v\)，那么根据\(PQ\perp AB\)，不难推出两个向量点乘 == 0。因此，\(\vec v \cdot [P - (A + t_0\vec v)]=0\)，根据分配率，可以推出：\(\vec v \cdot (P - A) - t_0 \times (\vec v^2)=0\)，这样就可以解出\(t_0\)，从而得到\(Q\)。

Point getLineProj(Point P, Point a, Point b)
{
    Vector v = B - A;
    return A + v * (mulDot(v, P - a) / mulDot(v, v));
}