点、线、面之间的关系

1. 点到直线的距离

第一种: 本文默认情况下，直线的方程为 $l:Ax+By+C=0$，$A$, $B$ 均不为 0，斜率为 $k_l$，点的坐标为 P (x0, y0)，点 $P$ 到 $l$ 的距离为 $d$ 。

则距离为:

$$d=\frac{|Ax_0+By_0+C|}{\sqrt{A^2+B^2}}$$

推导过程如下: https://zhuanlan.zhihu.com/p/26307123

第二种: 直线的方程为 $l: y = ax + b$，$a$, $b$ 均不为 0，斜率为 $a$，点的坐标为 P (x0, y0)，点 $P$ 到直线 $l$ 的距离为 $d$ 。

$$d=\frac{|ax_{0} - y_{0} + b|}{\sqrt{a^2+b^2}}$$

2. 如何判断两点在直线的两侧

判断点在直线的一侧:

方法一:

已知 $P(0,0)$, $Q(3,2)$ 两点，试判断 $P$ , $Q$ 是否在直线 $2x+3y=4$ 的同一侧。

解：直线 2x+3y=4, 即直线 2x+3y-4=0, 把 P、Q 代入 2x+3y-4 得到:

$$2 \times 0 + 3 \times 0-4=-4<0$$

$$2 {\times} 3+3 {\times} 2 - 4 = 8 > 0$$

所以，在两侧。

方法 2:

怎么判断坐标为 (xp,yp) 的点 P 是在直线的哪一侧呢？

设直线是由其上两点 $(x_1,y_1)$，$(x_2,y_2)$ 确定的，直线方向是由 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的方向。

假设直线方程为：$Ax+By+C=0$，则有:

$A=y2-y1$; $B=x1-x2$; $C=x2y1-x1y2$;

$$\left\{\begin{aligned} A&=y_2-y_1\\ B&=x_1-x_2\\ C&=x_2y_1-x_1y_2 \end{aligned}\right.$$

这时可以通过计算 D, 来判断点 P 是在直线的哪一侧:

$$D=Ax_p+By_p+C$$

若 D<0, 则点 P 在直线的左侧； 若 D>0, 则点 P 在直线的右侧； 若 D=0, 则点 P 在直线上。

注：这里的直线是有方向性的！

方法 3：

利用矢量计算快速判定一点在直线的哪一侧！

例如矢量 A× 矢量 B = 矢量 C

设想矢量 A 沿小于 180 度的角度转向矢量 B

将右手的四指指向矢量 A 的方向，右手的四指弯曲代表上述旋转方向，则伸直的拇指指向它们的叉乘得到的矢量 C

如果矢量 C 的方向相同，则在同侧；否则在两侧。

注：叉乘计算公式！

若将向量用坐标表示（三维向量），向量 $a=(x_1,y_1,z_1)$，向量 $b=(x_2,y_2,z_2)$，则：

点乘，也叫向量的内积、数量积。

$$向量 a・向量 b = |a||b|cos\theta$$ $$向量 a・向量 b = x_1 * x_2 + y_1 * y_2 + z_1 * z_2$$

叉乘，也叫向量的外积、向量积。

$$| 向量 c| = | 向量 a× 向量 b| = |a||b|sin \theta$$

向量 c 的方向与 a,b 所在的平面垂直，且方向要用 “右手法则” 判断（用右手的四指先表示向量 a 的方向，然后手指朝着手心的方向 < 180 摆动到向量 b 的方向，大拇指所指的方向就是向量 c 的方向）；

$$a\times b=\begin{vmatrix}\mathrm{i}&\mathrm{j}&\mathrm{k}\\x_{1}&y_{1}&z_{1}\\x_{2}&y_{2}&z_{2}\end{vmatrix}=(y_{1}z_{2}-y_{2}z_{1})i-(x_{1}z_{2}-x_{2}z_{1})j+(x_{1}y_{2}-x_{2}y_{1})k$$

（i、j、k 分别为空间中相互垂直的三条坐标轴的单位向量） ref:
[1]. Cross Product 叉乘速查手册
[2]. 叉乘几何意义
[3].https://blog.csdn.net/wzyaiwl/article/details/106310705

3. 判断点是否在矩形、多边形中

方法一:

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。

例如：判断一个点是否在两条线段之间夹着就转化成，判断一个点是否在某条线段的一边上，就可以利用叉乘的方向性，来判断夹角是否超过了 180 度

如下图:

BP Network

只要判断 $(AB \times AE ) * (CD \times CE) >= 0$ 就说明 E 在 AD 和 BC 中间夹着，同理 $(DA \times DE ) * (BC \times BE) >= 0$ 计算另两边 AB,CD 就可以了。(备注可进一步学习：向量点乘，叉乘的意义和几何意义)

最后就是只需要判断

$$(AB \times AE) * (CD \times CE) >= 0 \text {且} (DA \times DE ) * (BC \times BE) >= 0$$ 。

参考代码:

1
2
3
4
5
6
7
8
9

// 计算 |p1 p2| X |p1 p|
function GetCross(p1: Point, p2: Point, p: Point) {
    return (p2.x - p1.x) * (p.y - p1.y) - (p.x - p1.x) * (p2.y - p1.y);
}
//判断点p是否在p1p2p3p4的正方形内
function IsPointInMatrix(p1: Point, p2: Point, p3: Point, p4: Point, p: Point) {
    let isPointIn = GetCross(p1, p2, p) * GetCross(p3, p4, p) >= 0 && GetCross(p2, p3, p) * GetCross(p4, p1, p) >= 0;
    return isPointIn;
}

举例: https://www.cnblogs.com/fangsmile/p/9306510.html

方法 2：

采用点是否包含在多边形中判断

以该点为顶点，做一条射线，使得矩形四个顶点中任意一点都不在射线上。

若该射线与矩形有且仅有一个交点，则在矩形内；若有零个或两个焦点，则在矩形外。

至于射线，可以通过选择肯定在矩形外的一点和已知点练成线段来构成。

References: [1] 二维计算几何基础

4. 判断一个点是否在三角形的内部

方法一：面积比较

判断△ABO+△BOC+△COA 的面积与△ABC 是否相等。若相等则 O 在内部，反之则在外部。

BP Network

如何计算三角形的面积呢？通过坐标，很容易计算三角形的边长。

再由海伦公式计算面积。 $$S=\sqrt{p(p-a)(p-b)(p-c)}$$

其中，a,b,c 为三边长度，$p=\frac{a+b+c}{2}$

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <iostream>
#include <math.h>
using namespace std;

struct Point {
    double x;
    double y;
};

double getDist(Point p1,Point p2) {
    //两点之间计算距离公式
    return sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
}
double getArea(Point p1,Point p2,Point p3) {
    double a = getDist(p1, p2);
    double b = getDist(p2, p3);
    double c = getDist(p1, p3);
    double p = (a + b + c) / 2;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}
bool isInTriangle(Point p1,Point p2,Point p3,Point o) {
    double s1 = getArea(p1,p2,o);
    double s2 = getArea(p2,p3,o);
    double s3 = getArea(p3,p1,o);
    double s = getArea(p1,p2,p3);
    return s1+s2+s3 == s; //此处没有用fabs(a-b)<eps比较，是方便大家理解思路
}
int main() {
    Point p1,p2,p3,o;
    cin >> p1.x >> p1.y;
    cin >> p2.x >> p2.y;
    cin >> p3.x >> p3.y;
    cin >> o.x >> o.y;
    bool flag = isInTriangle(p1,p2,p3,o);
    if(flag) puts("Yes");
    else puts("No");
}

方法二：向量叉乘

若点 O 在三角形内部，则沿着三角形的边逆时针走，点 O 一定保持在边的左侧。如图示，点在逆时针行走时，在 AB，BC，CA 的左侧。

BP Network

如何判断点在一个边的左侧呢？

可以借助向量叉乘来判断 O 是否在向量 AB 的哪一侧。通过计算向量 AO 与向量 AB 的叉乘的值为正，则表示 O 在 AB 的左侧，反之为右侧。

(理解最好，理解不了也不要纠结，把叉乘公式记一下就 ok)

向量 $\overrightarrow{a}$ 是 $(m,n)$ , $\vec{b}$ 是 $(p,q)$

$$\vec{a} \times \vec{b} = mq-np$$

本题的核心思路就是这样。如果要让手撕代码，题目可能没有说输入的 3 个点是逆时针顺序的。比如，上图中如果依次输入的是 A,C,B 的坐标，那就不行了。

怎么解决呢？假设依次输入的点分别是 p1,p2,p3。

我们判断若 p3 在 $\vec{p1} \vec{p2}$的右侧！则表示输入的点的顺序是顺时针的，即 A,C,B 式的输入，将 p2,p3 调换位置即可保证顺序是逆时针。

BP Network

参考代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <math.h>
using namespace std;
struct Point {
    double x;
    double y;
};
double crossproduct(Point p1,Point p2,Point p3) {
    //首先根据坐标计算p1p2和p1p3的向量，然后再计算叉乘
    //p1p2 向量表示为 (p2.x-p1.x,p2.y-p1.y)
    //p1p3 向量表示为 (p3.x-p1.x,p3.y-p1.y)
    return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}
bool isInTriangle(Point p1,Point p2,Point p3,Point o) {
    //保证p1，p2，p3是逆时针顺序
    if(crossproduct(p1, p2, p3)<0) return isInTriangle(p1,p3,p2,o);
    if(crossproduct(p1, p2, o)>0 && crossproduct(p2, p3, o)>0 && crossproduct(p3, p1, o)>0)
        return true;
    return false;
}
int main() {
    Point p1,p2,p3,o;
    cin >> p1.x >> p1.y;
    cin >> p2.x >> p2.y;
    cin >> p3.x >> p3.y;
    cin >> o.x >> o.y;
    bool flag = isInTriangle(p1,p2,p3,o);
    if(flag) puts("Yes");
    else puts("No");
}

https://leetcode.cn/circle/discuss/7OldE4/