判断二维平面一个点是否在三角形内

判断二维平面一个点是否在三角形内有三种流行的方法，本文记录相关内容。

问题描述

给定二维平面三个点 A(x_1, y_1), B(x_2, y_2), C(x_3, y_3) 组成一个三角形，给定该平面内一点 P(x,y) ，如何快速判断 P 在 \Delta ABC 内部、边上、还是外部？

常用的有三种方法，分别是：

1. 面积法
2. 同向法
3. 重心法

面积法

如果一个点在三角形内，其与三角形的三个点构成的三个子三角形的面积等于大三角形的面积。否则，大于大三角形的面积。

所以，这个问题就转化成如何在知道三角形的三个点的情况下，求这个三角形的面积的问题了。

因为所有点的坐标已知，我们有几种方式计算面积：

海伦公式

首先可以计算出每条边的长度及周长，我们就可以利用海伦公式计算面积，然后进行比较。

如果一个三角形的三边长分别是a、b和c，半周长（半周长是三边和的半数）记为s，那么这个三角形的面积A可以通过下面的公式计算：

向量法

先求出这个三角形的对应的平行四边形的面积。然后这个面积的1/2就是三角形的面积。

先随意选择两个点，如B、C通过其坐标相减得向量（B，C）。记得谁减另一个就是指向谁。然后求出其中一个点和剩下一个点的向量。这两个向量的叉乘的便是平行四边形的面积。除以2就是三角形的面积。（注意这里是叉乘 (cross product)，而非点乘（dot product））。

同向法

假设点P位于三角形内，会有这样一个规律，当我们沿着ABCA的方向在三条边上行走时，你会发现点P始终位于边AB，BC和CA的右侧或左侧。

我们就利用这一点，但是如何判断一个点在线段的左侧还是右侧呢？我们可以从另一个角度来思考，以下图为例：

当选定线段AB时，点C位于AB的左侧，同理选定BC时，点A位于BC的左侧，最后选定CA时，点B位于CA的左侧，所以当选择某一条边时，我们只需验证点P与该边所对的点在同一侧即可。

问题又来了，如何判断两个点在某条线段的同一侧呢？可以通过叉积来实现，连接PA，将PA和AB做叉积，再将CA和AB做叉积，如果两个叉积的结果方向一致，那么两个点在同一测。

或者查看 AB-AP 、 BC-BP、CA-CP 三组叉乘结果的符号，如果三个符号相同（同为正或同为负）则 P 在三角形内部，如果不同则在外部，如果存在 0 则在边上。

重心法

三角形的三个点在同一个平面上，如果选中其中一个点，其他两个点不过是相对该点的位移而已，比如选择点A作为起点，那么点B相当于在AB方向移动一段距离得到，而点C相当于在AC方向移动一段距离得到。

所以对于平面内任意一点，都可以由如下方程来表示。

如果系数u或v为负值，那么相当于朝相反的方向移动，即BA或CA方向。那么如果想让P位于三角形ABC内部，u和v必须满足什么条件呢？有如下三个条件：

几个边界情况：

整理方程1得到：

令 ，则

现在是一个方程，两个未知数，无法解出 \begin{array}{c} v_2⋅v_0=(uv_0+vv_1)⋅v_0\ v_2⋅v_1=(uv_0+vv_1)⋅v_1 \end{array}

\begin{array}{c} v_2⋅v_0=u(v_0⋅v_0)+v(v_1⋅v_0)\

v_2⋅v_1=u(v_0⋅v_1)+v(v_1⋅v_1) \end{array}

u=((v_1⋅v_1)(v_2⋅v_0)−(v_1⋅v_0)(v_2⋅v_1))/((v_0⋅v_0)(v_1⋅v_1)−(v_0⋅v_1)(v_1⋅v_0))\

v=((v_0⋅v_0)(v_2⋅v_1)−(v_0⋅v_1)(v_2⋅v_0))/((v_0⋅v_0)(v_1⋅v_1)−(v_0⋅v_1)(v_1⋅v_0))

$$

参考资料

• https://blog.csdn.net/u011489043/article/details/78213650
• https://blog.csdn.net/roadtohacker/article/details/120498776
• https://blog.csdn.net/weixin_44120025/article/details/123830197

文章链接： https://cloud.tencent.com/developer/article/2436904