判断点是否在形状内

发表于 2023-08-28 更新于 2024-05-02 分类于编程

判断点是否在形状之内的算法很有用。我们可以用它实现鼠标与图形的交互功能，或是直接使用着色器绘制图形。

为了解释方便，我规定点$P$就是我们需要判断的那个点。

圆和椭圆

如何判断点圆关系是小学二年级的内容，这里不讲了。

根据椭圆的定义（$|PF_1|+|PF_2|=2a$），我们可以算出椭圆的焦点$F_1$、$F_2$，进而求出$|PF_1|+|PF_2|$，若小于$2a$，那么可以得出$P$点在椭圆内部。

如果想用和判断点圆关系一样的思路，先求得椭圆中心和点$P$之间的距离，再计算那个“半径”吗？椭圆的参数方程$(a\cos\theta, b\sin\theta)$里面的$\theta$怎么求呢？可以用atan2吗？

答案是不行，那个$\theta$表示的并不是绕原点旋转的角度，会有偏差。

既然椭圆是圆“压扁”变成的，那我们就可以把椭圆重新变成圆。

设椭圆的长轴（与$x$轴平行）长为$a$，短轴（与$y$轴平行）长为$b$，$P$点的坐标为$(x,y)$。

把$x$轴的单位长度变为原来的$\frac{b}{a}$，那么椭圆的长轴和短轴都为$b$，成为了圆，点的坐标则变为$(\frac{b}{a}x,y)$。如此，我们就可以用我们熟悉的方法来计算了。

扇形是圆的一部分，我用以下特征来描述一个扇形：圆心、半径、起始角度$\alpha$和圆心角$\beta$。

首先计算圆心与点$P$的距离，如果大于半径返回假。

接着使用atan2计算圆心与点$P$的连线与$x$轴的夹角（在$[0, 2\pi)$内），若在$(\alpha,\alpha+\beta)$的范围内返回真。

这个超级简单，算法如下：

# (x, y) 是矩形左下角的坐标，width 和 height 是矩形的长和宽。
# (px, py) 是任意一点 P
# 若以下表达式为 True 则说明点P在矩形内
(x < px < x + width) and (y < py < y + height)

这里的线段指的是有宽度的线段，它虽然可以作为一个旋转过的矩形来处理，但是会用到一堆三角函数，很烦！这里介绍的是一种只涉及到加减乘除和乘方的算法。

为了描述简便，线段只加粗而不伸长。

一张简单的示意图

首先，我们需要确定点$P$是否在两条红虚线的内侧，即线段向着其法向量的方向平移扫过的区域。

向量点乘可以做到这一点，若以下表达式为真，则点$P$符合要求：

$$\overrightarrow{AB}\cdot\overrightarrow{AP}\times\overrightarrow{BA}\cdot\overrightarrow{BP}\ge0$$

接下来就很简单了，使用三角形等面积法，算出$S_{PAB}$中$AB$边对应的高再和线段的宽度比较即可。

这里点$A(x_1,y_1)$、点$B(x_2,y_2)$和点$P(x_3,y_3)$的坐标都是已知的，在学到行列式的时候一定讲到一个公式可以求$S_{PAB}$的面积：

$$
S=\frac{1}{2}
\begin{Vmatrix}
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
x_3 & y_3 & 1 \\
\end{Vmatrix}
$$

这很显然比任何已知的方法都要快。

胶囊体与线段类似，若点$P$在红虚线的外侧（需要确定为哪一侧），则计算它与端点的距离。

据我所知，判断点是否在多边形里面的算法有两个。

首先是只适用于凸多边形的分离轴定理（SAT），它通常用来判断两个凸多边形是否相交，如果其中的一个多边形变成了单独的一个点，此算法依然是正确的。

另一种算法，简而言之：从$P$点向任意方向画一条射线，若该射线与多边形的边的相交次数为奇数次，该点位于多边形内部；否则该点在多边形外。您可以从该网站获取这个算法的Python代码。

将三角形从多边形里面拎出来是有原因的：我想到了一个更简单的方法（但不一定快）。

现在回忆一下奔驰定理：点$P$为$\triangle ABC$内任意一点，那么以下等式成立：

$$S_{\triangle PBC}\overrightarrow{AP}+S_{\triangle PAC}\overrightarrow{BP}+S_{\triangle PAB}\overrightarrow{CP}=\overrightarrow{0}$$

据此，我们可以很快地编写算法判断点是否在三角形内。

计算面积时请用刚刚提到的行列式来计算，这样更快。

在实现上述功能的时候，代码应该尽量简洁。例如，为了画出倾斜$45^{\circ}$的图形，形状一般会有一个rotation属性。但是我们在做上述的检测时，将旋转施加到形状上就麻烦了，我们应该让那个点绕着形状的中心反向旋转，而保持形状不变。这样的话运算更快，代码也会简洁。