判断某点是否在三角形内

时间：2022-04-30 10:25:58

判断某点是否在三角形内

这个问题碰到过好几次了，不仅是笔试的时候，还有在工作上，所以这里做个小总结。

1、通过第三方库函数

首先介绍最简单的方法，直接调用已有的函数。采用python的matplotlib库，里面的Path.contains_points,
该函数十分强大，可以根据任意几个点所组成的多边形，计算新输入的点是否在该多边形内，当然三角形就是其中的一种情况了。

该函数使用示例如下：

>>>from matplotlib import path
>>>p = path.Path([(0, 0), (1, 0), (1, 1)])
>>>p.contains_points([(0.1, 0.1)])
array([ True], dtype=bool)

其中我们用(0, 0)、(0, 1)、(1, 1)构建了一个三角形，当新输入一点(0.1, 0.1)的时候，返回值为True，说明该点位于三角形内。该函数还支持输入多个点进行判决，得到一个bool型的array数组。

看到array自然就能联想到，它也支持以numpy.array格式输入的点，但是一定要注意，以此种格式输入时，一定要加上reshape(n, 2)，即输入必须为一个n行2列的数组。

2、内角和等于360°

这种方法最好理解，即对于△ABC内的某一点P，连接PA、PB、PC得到三条线段，当且仅当三条线段组成的三个夹角和为360°的时候，该点才位于三角形内部。但此种方法的计算涉及到平方根、反正（余）弦，效率十分低下。

类似的还有，P与ABC三个顶点组成的三个三角形，面积之和等于△ABC的面积，同样可以证明点P位于三角形内部，但效率也很低。

3、Same Side Technique

这种方法是我从别处看来的，觉得很新颖，想看英文原版的可以直接点这里。下面我解释一下该方法的思想，首先看下图：
判断某点是否在三角形内
如果某点位于△ABC内部，那么该点一定位于AB的下边，AC的右边，BC的左边。要用数学的方法来表示，可以采用向量积，向量积有个很重要的右手定则，忘记了的自行复习一下。下面接着看下一张图：
判断某点是否在三角形内
对于任意的一点P, AB→×AP→ ，其结果根据右手定则，应为指向屏幕外，而 AB→×AP′→ 的结果则是指向屏幕里。根据这一特性，我们只要找到某一点P，满足 AB→×AP→ 与 AB→×AC→ 具有同一方向、 AC→×AP→ 与 AC→×AB→ 具有同一方向、 BC→×BP→ 与 BC→×BA→ 具有同一方向，则点P位于△ABC内。

这种方法涉及到的计算是向量运算，没有平方根、反余弦这些，效率比第2种方法高，代码部分可以参考原文，下面着重介绍最后一种方法。

4、Barycentric Coordinates

最后一种方法的效率最高，但是理解起来需要的步骤多一点，我们先看下面这张图
判断某点是否在三角形内
AP→ 可表示为：
AP→=u∗AB→+v∗AC→
其中u、v为常量系数，从图中我们即可得知，当u>0且v>0时，P的位置才有可能正确，那是不是u、v可以无限大呢？当然不是，当u+v>1时，P就会超出三角形的范围，而当u+v=1时，点P刚好位于BC上，这里稍微证明一下。
当点P在BC上时，也就是 BP→、PC→ 同向，将前面 AP→ 的表示方式代入，那么这两个向量可以分别表示为：
BP→=AP→−AB→=(u−1)∗AB→+v∗AC→ PC→=AC→−AP→=(1−v)∗AC→−u∗AB→
由于两者同向，那么就存在一个 λ ( λ>0 )，使得 BP→=λPC→ ，代入上面两式，整理一下，就得到了下面的式子：
(u−1+λu)∗AB→=(λ−λv−v)∗AC→
上式要成立，当且仅当左右两边的系数都为0。由此得到两个方程，消去 λ 就可以得到u+v=1了。有了这一点，为什么三角形内部点的u、v之和小于1，外部点的大于1，请读者自行理解，这里不再展开了。

根据模型，得到公式

由此我们的模型就得到了：对于任意给定的一点P，判断其是否位于△ABC的内部，就是要计算其相对于△ABC的u、v值，只要这两个值满足u>0、 v>0、 u+v<1，那么可以确定点P位于三角形内。这样只要得到u、v的表达式，在代码里面就能直接使用了。该表达式的推导还是有点麻烦的，我看原文（最底下）中，作者是用软件算出来的，想挑战一下的朋友也可以自行推导，这里我直接给出最终的代码（参考的是*上面的第三个回答）：

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

u = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
v = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

其中p0、p1、p2分别是三角形的三个顶点，p表示待判断的点，后面跟着x、y表示顶点的横、纵坐标。只要满足u>0、v>0、u+v<1，就说明p位于p0、p1、p2组成的三角形内部，这几个公式的计算量对计算机而言是相当小了。

PS

第一次写技术类博客，竟然是两个月以后了，拖延症晚期啊。而且刚开始写，也不知道侧重点在哪，因为有的时候看下解决方案就好，有的时候可能还想了解一下原理，还是慢慢摸索吧。最后，这篇文章还是费了不少时间的，由此我想到了网上那些大神的博客，衷心为他们点赞！
标签：

相关文章