06-数学相关/06-计算几何

欧几里得距离

- [math]\displaystyle{ (x_1,y_1) }[/math] 与 [math]\displaystyle{ (x_2,y_2) }[/math] 的距离为 [math]\displaystyle{ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} }[/math] - [math]\displaystyle{ (x_1,y_1,z_1) }[/math] 与 [math]\displaystyle{ (x_2,y_2,z_2) }[/math] 的距离为 [math]\displaystyle{ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} }[/math]

海伦公式

三角形三边长分别为 [math]\displaystyle{ a,b,c }[/math]，定义半周长 [math]\displaystyle{ p=\frac{a+b+c}{2} }[/math]，则三角形面积为：

[math]\displaystyle{ S=\sqrt{p(p-a)(p-b)(p-c)} }[/math]

向量叉乘

[math]\displaystyle{ \vec{a}=(a_x,a_y),\ \vec{b}=(b_x,b_y) \quad\Rightarrow\quad \vec{a} \times \vec{b} = a_x b_y - a_y b_x }[/math]

意义：

- 结果的绝对值恰好为两向量为邻边的平行四边形面积，可以用来计算三角形面积 - 可以利用正负值判断两个向量的位置关系

// 传入两个点，返回对应向量（第一个点指向第二个点）
pair<double, double> getV(pair<double, double> a, pair<double, double> b)
{
    return {b.first - a.first, b.second - a.second};
}

// 传入两个向量，返回叉乘结果
// 如果结果为正，第二个向量偏左，否则偏右
double getMul(pair<double, double> a, pair<double, double> b)
{
    return a.first * b.second - a.second * b.first;
}

三角形面积

三角形 [math]\displaystyle{ ABC }[/math] 的面积：

[math]\displaystyle{ S=\frac{1}{2}|\vec{AB}\times \vec{AC}| }[/math]

线段相交判断

对于四个点 [math]\displaystyle{ A,B,C,D }[/math]，判断线段 [math]\displaystyle{ AB }[/math] 与线段 [math]\displaystyle{ CD }[/math] 是否相交。

通过计算 [math]\displaystyle{ \vec{AB}\times \vec{AC} }[/math] 与 [math]\displaystyle{ \vec{AB}\times \vec{AD} }[/math]，如果结果一正一负，则 [math]\displaystyle{ C,D }[/math] 两点处于直线 [math]\displaystyle{ AB }[/math] 的两边。同理判断 [math]\displaystyle{ A,B }[/math] 是否在直线 [math]\displaystyle{ CD }[/math] 的两边。如果两个条件都满足，则两线段相交。

bool checkX(pair<double, double> a, pair<double, double> b,
            pair<double, double> c, pair<double, double> d)
{
    double x, y;
    // c,d 是否在直线 ab 的两边
    auto AB = getV(a, b);
    auto AC = getV(a, c);
    auto AD = getV(a, d);
    x = getMul(AB, AC);
    y = getMul(AB, AD);
    if (x > 0 && y > 0 || x < 0 && y < 0) // c,d 在 ab 同一侧
        return false;
    // a,b 是否在直线 cd 的两边
    auto CD = getV(c, d);
    auto CA = getV(c, a);
    auto CB = getV(c, b);
    x = getMul(CD, CA);
    y = getMul(CD, CB);
    if (x * y > 0)
        return false;
    return true;
}

常用几何模板速记

功能	公式/方法
两点距离	[math]\displaystyle{ \sqrt{(x_1-x_2)^2+(y_1-y_2)^2} }[/math]
叉乘	[math]\displaystyle{ a_x b_y - a_y b_x }[/math]
点积	[math]\displaystyle{ a_x b_x + a_y b_y }[/math]
三角形面积	[math]\displaystyle{ \frac{1}{2} | \vec{AB}\times \vec{AC} | }[/math]
向量夹角余弦	[math]\displaystyle{ \frac{\vec{u}\cdot\vec{v}}{ | \vec{u} | | \vec{v} | } }[/math]