判断某点是否在三角形内

时间: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=uAB+vAC
其中u、v为常量系数,从图中我们即可得知,当u>0且v>0时,P的位置才有可能正确,那是不是u、v可以无限大呢?当然不是,当u+v>1时,P就会超出三角形的范围,而当u+v=1时,点P刚好位于BC上,这里稍微证明一下。
当点P在BC上时,也就是 BPPC 同向,将前面 AP 的表示方式代入,那么这两个向量可以分别表示为:
BP=APAB=(u1)AB+vAC PC=ACAP=(1v)ACuAB
由于两者同向,那么就存在一个 λ ( λ>0 ),使得 BP=λPC ,代入上面两式,整理一下,就得到了下面的式子:
(u1+λu)AB=(λλvv)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

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