学习｜判断一个点是否在三角形内

数学基础向量点乘（Dot Product）

点乘比较简单一号三角点，是相应元素的乘积的和：

V1( x1, y1)+ V2(x2, y2) = x1*x2 + y1*y2

注意结果不是一个向量，而是一个标量（Scalar）。点乘有什么用呢，我们有：

A·B= |A||B|Cos(θ)。

θ是向量A和向量B见的夹角。这里|A|我们称为向量A的模(norm)，也就是A的长度， 在二维空间中就是|A| = sqrt(

)。这样我们就和容易计算两条线的夹角：Cos(θ) = A·B / (|A||B|)

这可以告诉我们如果点乘的结果，简称点积，为0的话就表示这两个向量垂直。当两向量平行时，点积有最大值.另外，点乘运算不仅限于2维空间，他可以推广到任意维空间.

叉乘（cross product）

相对于点乘，叉乘可能更有用吧。2维空间中的叉乘是：V1(x1, y1) X V2(x2, y2) = x1y2 -y1x2

看起来像个标量，事实上叉乘的结果是个向量，方向在z轴上。上述结果是它的模。在二维空间里，让我们暂时忽略它的方向，将结果看成一个向量，那么这个结果类似于上述的点积，我们有：A x B = |A||B|Sin(θ)

然而角度 θ和上面点乘的角度有一点点不同，他是有正负的，是指从A到B的角度。另外还有一个有用的特征那就是叉积的绝对值就是A和B为两边说形成的平行四边形的面积。也就是AB所包围三角形面积的两倍。这个还是很显然的啦。在计算面积时，我们要经常用到叉积。

一次牛客的比赛中遇到了这个题，当时是用下面的方法一来实现的，之后看了些博客，发现还有好几种更好的方法，当时实现起来代码还显得特别不好看2333，太菜了。

判断点在三角形内面积法：

利用面积，如图中

,求三角形面积的方法就可以用上面提到的利用叉积就行了，注意记得加上绝对值，因为叉积可能为负。还有种简单的方法是利用内角和为

但效率低下，就不管了。

同侧法：

首先看一下这个问题，如何判断某两个点在某条直线的同一侧

根据向量的叉乘以及右手螺旋定则，AB^AM （^表示叉乘，这里向量省略了字母上面的箭头符号）的方向为向外指出屏幕，AB^AN也是向外指出屏幕，但AB^AO的方向是向内指向屏幕，因此M,N在直线AB的同侧，M ,O在直线AB的两侧。实际计算时，只需要考虑叉积的数值正负假设以上各点坐标为A(0,0), B(4,0), M(1,2), N(3,4), O(3,-4)， 则：

AB^AM = (4,0)^(1,2) = 4*2 - 0*1 = 8

AB^AN = (4，0)^(3，4) = 4*4 – 0*3 = 16

AB^AO = (4,0)^(3,-4) = 4*-4 – 0*3 = –16

由上面的数值可知，可以根据数值的正负判断叉乘后向量的方向。即，如果叉积AB^AM 和 AB^AN的结果同号，那么M,N两点就在直线的同侧，否则不在同一侧。特殊地，如果点M在直线AB上，则AB^AM的值为0。（如果是在三维坐标系中一号三角点，求出的叉积是一个向量，可以根据两个向量的点积结果正负来判断两个向量的是否指向同一侧）。

以上的问题解决了，就很容易的用来判断某个点是否在三角形内，如果P在三角形ABC内部，则满足以下三个条件：P,A在BC的同侧、P,B在AC的同侧、PC在AB的同侧。某一个不满足则表示P不在三角形内部。

一个不知道怎么命名的方法

该方法也用到了向量。对于三角形ABC和一点P，可以有如下的向量表示：

p点在三角形内部的充分必要条件是：1 >= u >= 0, 1 >= v >= 0, u+v = u >= 0, 1 >= v >= 0, u+v