老铁们，大家好，相信还有很多朋友对于三维空间中判断一点是否位于三角形内部的方法和的相关问题不太懂，没关系，今天就由我来为大家分享分享三维空间中判断一点是否位于三角形内部的方法以及的问题，文章篇幅可能偏长，希望可以帮助到大家，下面一起来看看吧！
注明：我只是为了自己学习照搬
概述：给定三角形ABC和一点P(x,y,z)，判断点P是否在ABC内。这是游戏设计中一个常见的问题。需要注意的是，这里假定点和三角形位于同一个平面内。
本文从浅到深介绍了三种不同的方法。
一内角和法
连接点P 和三角形的三个顶点，得到三条线段PA、PB 和PC。求这三个线段与三角形每条边之间的角度。如果所有角度之和为180 度，则点P 在三角形内。否则它不存在。这种方法直观但效率低下。
image.png
二同向法
假设P点位于三角形内，就会有这样的规则。当我们沿着ABCA方向走在三边上时，你会发现P点总是在AB、BC、CA边的右侧。我们会利用这一点，但是如何确定一个点是在线段的左侧还是右侧呢？我们可以从另一个角度来思考。当选择线段AB时，C点位于AB的右侧。同样，当选择BC时，A点位于BC的右侧。最后，当选择CA时，B点位于CA的右侧。在右侧，所以在选择一条边时，我们只需要验证点P与该边相对的点在同一侧即可。问题又来了，如何判断两点是否在某条线段的同一侧呢？可以通过叉积来实现，连接PA，PA和AB叉积，然后CA和AB叉积。如果两个叉积的结果方向相同，则这两个点属于同一测量。判断两个向量是否同向可以通过点积来实现。如果点积大于0，则两个向量之间的夹角为锐角，否则为钝角。
图片.png
代码如下。为了实现程序功能，增加了一个Vector3类，它表示三维空间中的向量。
//3D向量
类Vector3
{
公共：
Vector3（浮点fx，浮点fy，浮点fz）
:x(fx)、y(fy)、z(fz)
{
}
//减法
Vector3 运算符- (const Vector3 v) const
{
返回Vector3(x - v.x, y - v.y, z - v.z);
}
//点积
浮点点(const Vector3 v) const
{
返回x * v.x + y * v.y + z * v.z；
}
//叉积
Vector3 Cross(const Vector3 v) const
{
返回向量3(
y * v.z - z * v.y，
z * v.x - x * v.z,
x * v.y - y * v.x );
}
公共：
浮动x、y、z；
};
//判断两个向量v1和v2是否指向同一个方向
//v1=交叉(AB, AC)
//v2=交叉(AB, AP)
bool SameSide(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
{
向量3 AB=B - A ;
Vector3 AC=C - A ;
Vector3 AP=P - A ;
Vector3 v1=AB.Cross(AC);
Vector3 v2=AB.Cross(AP);
//v1 和v2 应该指向同一方向
返回v1.Dot(v2)=0;
}
//同边方法
//判断点P是否在三角形ABC中
bool PointinTriangle1(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
{
返回SameSide(A, B, C, P)
同边（B、C、A、P）
SameSide(C, A, B, P);
}
//类定义：二维向量2D向量
Laya ts写法
//判断两个向量v1和v2是否指向同一个方向
公共SameSide(A: Laya.Vector3, B: Laya.Vector3, C: Laya.Vector3, P: Laya.Vector3) {
让AB: Laya.Vector3=new Laya.Vector3();
让AC: Laya.Vector3=new Laya.Vector3();
让AP: Laya.Vector3=new Laya.Vector3();
Laya.Vector3.subtract(B, A, AB);
Laya.Vector3.subtract(C, A, AC);
Laya.Vector3.subtract(P, A, AP);
让v1: Laya.Vector3=new Laya.Vector3();
让v2: Laya.Vector3=new Laya.Vector3();
Laya.Vector3.cross(AB, AC, v1);
Laya.Vector3.cross(AB, AP, v2);
//判断v1和v2是否指向同一方向
让num=Laya.Vector3.dot(v1, v2)
返回数字=0；
}
//确定三角形ABC三点中的点P
公共PointinTriangle1（A: Laya.Vector3，B: Laya.Vector3，C: Laya.Vector3，P: Laya.Vector3）{
返回this.SameSide(A, B, C, P) this.SameSide(B, C, A, P) this.SameSide(C, A, B, P);
}
三 重心法
上述方法简单易懂，速度快。下面的方法更快，但需要更多的数学知识。
三角形的三点在同一平面上。如果选择其中一个点，则其他两点只是相对于该点的位移。例如选择A点作为起点，那么B点就相当于沿AB方向移动了一定的距离。 C点相当于沿AC方向移动一定距离得到
图片.png
因此，对于平面上的任意点，可以用以下方程表示
P=A + u * (C A) + v * (B A) //公式1
如果系数u或v为负值，则相当于向相反方向移动，即BA或CA方向。那么如果想让P在三角形ABC内部，u和v必须满足什么条件呢？有以下三个条件
u=0
v=0
u+v=1
几种边界情况，当u=0、v=0时为A点，当u=0、v=1时为B点，当u=1、v=0时为C点
整理方程1 得到P A=u(C A) + v(B A)
令v0=C A，v1=B A，v2=P A，则v2=u * v0 + v * v1，现在这是一个有两个未知数的方程，u和v无法求解，将两边将方程点乘v0 和v1 分别得到两个方程
(v2) • v0=(u * v0 + v * v1) • v0
(v2) • v1=(u * v0 + v * v1) • v1
注意，这里u和v是数字，v0、v1和v2是向量，因此可以将点积展开得到下面的公式。
v2 • v0=u * (v0 • v0) + v * (v1 • v0) //方程1
v2 • v1=u * (v0 • v1) + v * (v1• v1) //方程2
求解这个方程给出
u=((v1•v1)(v2•v0)-(v1•v0)(v2•v1))/((v0•v0)(v1•v1) - (v0•v1)(v1•v0))
v=((v0•v0)(v2•v1)-(v0•v1)(v2•v0))/((v0•v0)(v1•v1) - (v0•v1)(v1•v0))
是时候添加代码了。此代码还使用了上面的Vector3 类。
//判断点P是否在三角形ABC中
bool PointinTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
{
Vector3 v0=C - A ;
Vector3 v1=B - A ;
Vector3 v2=P - A ;
浮动点00=v0.Dot(v0);
浮动点01=v0.Dot(v1);
浮动点02=v0.Dot(v2);
浮动点11=v1.Dot(v1);
浮动点12=v1.Dot(v2);
浮点数inverDeno=1/(dot00 * dot11 - dot01 * dot01) ;
浮点数u=(dot11 * dot02 - dot01 * dot12) * inverDeno;
if (u 0 || u 1) //如果u超出范围，直接返回
{
返回假；
}
浮点数v=(dot00 * dot12 - dot01 * dot02) * inverDeno;
if (v 0 || v 1) //如果v 超出范围，直接返回
{
返回假；
}
返回u+v=1；
Laya ts写法
//确定三角形ABC三点中的点P
公共PointinTriangle2（A: Laya.Vector3，B: Laya.Vector3，C: Laya.Vector3，P: Laya.Vector3）{
让v0: Laya.Vector3=new Laya.Vector3();
让v1: Laya.Vector3=new Laya.Vector3();
让v2: Laya.Vector3=new Laya.Vector3();
Laya.Vector3.subtract(C, A, v0);
Laya.Vector3.subtract(B, A, v1);
Laya.Vector3.subtract(P, A, v2);
让dot00=Laya.Vector3.dot(v0, v0);
让dot01=Laya.Vector3.dot(v0, v1);
让dot02=Laya.Vector3.dot(v0, v2);
让dot11=Laya.Vector3.dot(v1, v1);
让dot12=Laya.Vector3.dot(v1, v2);
让inverDeno=1/(dot00 * dot11 - dot01 * dot01);
让u=(dot11 * dot02 - dot01 * dot12) * inverDeno;
if (u 0 || u 1) //如果u超出范围，直接返回
{
返回假；
}
让v=(dot00 * dot12 - dot01 * dot02) * inverDeno;
if (v 0 || v 1) //如果v超出范围，直接返回
{
返回假；
}
返回u + v=1
}
-----------------------------------------2D---------------------------------------
文章转载：http://www.cnblogs.com/TenosDoIt/p/4024413.html
原作者：tenos
注明：我只是为了自己学习照搬
二维平面上判断点是否在三角形内
给定三角形三个顶点的坐标，本文提供了三种方法来判断一个点是否在三角形内（在三角形的边上，我们也认为它在三角形内）。
image.png
算法1
面积法，如上图所示，如果点P在三角形ABC内部，则三个小三角形PAB、PBC、PAC的面积之和=ABC的面积，否则为不相等。要计算三角形的三个顶点坐标的面积，可以使用向量的叉积，参考链接地址
该算法详见后面代码中的函数：IsPointInTriangle1算法2我们先来看这个问题：如何判断两点在直线的同一边（代码中函数：IsPointAtSameSideOfLine）
图像
根据向量叉积和右手螺旋法则，AB^AM（代表叉积，其中向量省略字母上方的箭头符号）的方向指向屏幕外，ABAN也指向外屏幕上，但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)=42 - 01=8
AB^AN=(4,0)^(3,4)=44 03=16
AB^AO=(4,0)^(3,-4)=4-4 03=16
从上面的值可以看出，可以根据正负值来判断叉积后向量的方向。即如果叉积AB^AM和ABAN的结果符号相同，则两点M和N在直线的同一侧，否则不在同一侧。具体来说，如果点M在直线AB上，则ABAM的值为0。（如果是在三维坐标系中，叉积是一个向量，可以根据判断两个向量是否指向同一条边）两个向量的正或负点积结果）
解决了上面的问题之后，就可以很方便的用来判断某个点是否在三角形内了。如果P在三角形ABC内部，则满足以下三个条件：P和A在BC的同一边，并且P和B在AC的同一边。同侧，PC 与AB 在同一侧。如果其中之一不满足，则说明P不在三角形内。
该算法详见后面代码中的函数：IsPointInTriangle2算法3此方法也使用向量。对于三角形ABC和点P，我们可以有以下向量表示：
imagep点在三角形内部的充分必要条件是：1=u=0, 1=v=0, u+v=1。
给定A、B、C、P四个点的坐标，将上述公式分别与向量AC和向量AB点乘即可得到u和v。
对图像解方程可得：
图像解完u和v后，只需看它们是否满足“1=u=0, 1=v=0, u+v=1”。如果它们满足，则p 在三角形内。
（当u=0时，p在AB上，当v=0时，p在AC上，当两者都为0时，p和A重合）
该算法详见后面代码中的函数：IsPointInTriangle3算法4该算法与算法2类似，可以看作是算法2的简化，同样使用了向量的叉积。假设三角形的三点按顺时针（或逆时针）顺序依次为A、B、C。对于某个点P，求出三个向量PA、PB、PC，然后计算以下三个叉积（^表示叉积符号）：
t1=PA^PB，
t2=PB^PC,
t3=PC^PA,
如果t1、t2 和t3 具有相同的符号（相同的正值或相同的负值），则P 在三角形内部，否则在三角形外部。
该算法详见后面代码中的函数：IsPointInTriangle4
原代码是C语言写的我转换成了TS
//经测试，算法4最快，其次是算法3，其次是算法2，算法1最慢。直观上，从计算量来看，算法4的计算量也是最少的。
//下面是代码，定义了两个类：二维向量类和三角形类
//类定义：二维向量
V2 类{
构造函数（x: 数字，y: 数字）{
这个.x_=x;
这个.y_=y;
}
私人x_:号码=0；
私人y_: 号码=0;
//二维向量叉积。叉积的结果实际上是一个向量。该方向垂直于两个向量组成的平面。这里我们只需要它的大小和方向。
CrossProduct(vec: V2): 数字{
返回this.x_ * vec.y_ - this.y_ * vec.x_;
}
//二维向量点积
点积(vec: V2): 数字{
返回this.x_ * vec.x_ + this.y_ * vec.y_;
}
//二维向量减法
减(vec: V2): V2 {
返回新的V2(this.x_ - vec.x_, this.y_ - vec.y_);
}
//判断M点和N点是否在直线AB的同一侧
静态IsPointAtSameSideOfLine(pointM: V2, pointN: V2, pointA: V2, pointB: V2): 布尔{
让AB=pointB.Minus(pointA);
让AM=pointM.Minus(pointA);
让AN=pointN.Minus(pointA);
//等于0时，表示某点在直线上
返回AB.CrossProduct(AM) * AB.CrossProduct(AN)=0;
}
}
//三角形类
三角形类{
私人点A_: V2；
私人点B_: V2；
私人点C_: V2；
构造函数（point1: V2，point2: V2，point3: V2）{
this.pointA_=point1;
this.pointB_=point2;
this.pointC_=point3;
}
//计算三角形的面积
计算三角形区域() {
//根据两个向量的叉积计算，请参考http://blog.csdn.net/zxj1988/article/details/6260576
让AB: V2=this.pointB_.Minus(this.pointA_);
让BC: V2=this.pointC_.Minus(this.pointB_);
//原文：fabs(AB.CrossProduct(BC)/2.0);
return Math.abs(AB.CrossProduct(BC)/2.0);
}
//算法1
IsPointInTriangle1(pointP: V2) {
让area_ABC=this.ComputeTriangleArea();
让area_PAB=new Triangle(pointP, this.pointA_, this.pointB_).ComputeTriangleArea();
让area_PAC=new Triangle(pointP, this.pointA_, this.pointC_).ComputeTriangleArea();
让area_PBC=new Triangle(pointP, this.pointB_, this.pointC_).ComputeTriangleArea();
//原文： if (fabs(area_PAB +area_PBC +area_PAC -area_ABC) 0.000001)
if (Math.abs(区域_PAB + 区域_PBC + 区域_PAC - 区域_ABC) 0.000001)
返回真；
否则返回false；
}
//算法2
IsPointInTriangle2(pointP: V2) {
返回V2.IsPointAtSameSideOfLine(pointP, this.pointA_, this.pointB_, this.pointC_)
V2.IsPointAtSameSideOfLine(pointP, this.pointB_, this.pointA_, this.pointC_)
V2.IsPointAtSameSideOfLine(pointP, this.pointC_, this.pointA_, this.pointB_);
}
//算法3
IsPointInTriangle3(pointP: V2) {
让AB=this.pointB_.Minus(this.pointA_);
让AC=this.pointC_.Minus(this.pointA_);
让AP=pointP.Minus(this.pointA_);
让dot_ac_ac=AC.DotProduct(AC);
让dot_ac_ab=AC.DotProduct(AB);
让dot_ac_ap=AC.DotProduct(AP);
让dot_ab_ab=AB.DotProduct(AB);
让dot_ab_ap=AB.DotProduct(AP);
让tmp=1.0/(dot_ac_ac * dot_ab_ab - dot_ac_ab * dot_ac_ab);
让u=(dot_ab_ab * dot_ac_ap - dot_ac_ab * dot_ab_ap) * tmp;
如果（u 0 || u 1）
返回假；
让v=(dot_ac_ac * dot_ab_ap - dot_ac_ab * dot_ac_ap) * tmp;
如果（v 0 || v 1）
返回假；
返回u+v=1；
}
//算法4
IsPointInTriangle4(pointP: V2) {
让PA=this.pointA_.Minus(pointP);
让PB=this.pointB_.Minus(pointP);
让PC=this.pointC_.Minus(pointP);
让t1=PA.CrossProduct(PB);
让t2=PB.CrossProduct(PC);
让t3=PC.CrossProduct(PA);
//返回t1 * t2=0 t1 * t3=0;
返回t1 * t2=0 t1 * t3=0 t2 * t3=0;
}
【三维空间中判断一点是否位于三角形内部的方法】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
这个题目听起来有点抽象啊，感觉需要有点几何学的知识才能理解。
有10位网友表示赞同！
我想知道这种方法能不能应用到其他多面体上？
有16位网友表示赞同！
3D空间的判断好像比2D复杂多了，怎么才能更方便地理解呢？
有10位网友表示赞同！
我以前学过一些三角形的性质，不知道能不能用到这里...
有16位网友表示赞同！
这题应该需要编程吧？可以用哪些语言来实现呢？
有7位网友表示赞同！
感觉这种判断问题还是挺有用的，比如在游戏设计中就可以用上。
有5位网友表示赞同！
我试着想想，如果点离三角形所有边的距离都比较远的话，应该是不会在里面的吧？
有19位网友表示赞同！
3D空间的坐标怎么处理呢？这比2D复杂很多。
有6位网友表示赞同！
这个方法应该适用于任意大小的三角形吗？
有13位网友表示赞同！
感觉要理解这个问题需要画图才行啊！你能给我画个例子嘛？
有13位网友表示赞同！
如果点在三角形的边上，该怎么判断呢？
有19位网友表示赞同！
我想知道这个算法的时间复杂度是多少？是不是效率很高？
有11位网友表示赞同！
能不能用更直观的语言描述一下这个原理？
有9位网友表示赞同！
学习这种方法应该对做图形设计很有帮助吧？
有6位网友表示赞同！
我平时学一些计算机视觉，这听起来好像也会用到。
有13位网友表示赞同！
有没有一些现成的工具可以用来判断点是否在三角形内？
有17位网友表示赞同！
如果这个算法能应用到更高维的空间就好了...
有11位网友表示赞同！
我觉得3D空间的几何问题比2D更有趣！
有6位网友表示赞同！
我对这种求解方法很感兴趣，希望能学到更多！
有13位网友表示赞同！
看来我还需要多学习一些数学知识才能理解这个问题
有18位网友表示赞同！