有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
一个简单的方法是:
找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。
两个解释替代方案的好网站是:
黑卒和沃尔夫勒姆
其他回答
由andreasdr和Perro Azul发布的重心方法的c#版本。我添加了一个检查,当s和t有相反的符号(而且都不为零)时,放弃面积计算,因为潜在地避免三分之一的乘法成本似乎是合理的。
public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
var s = (p0.X - p2.X) * (p.Y - p2.Y) - (p0.Y - p2.Y) * (p.X - p2.X);
var t = (p1.X - p0.X) * (p.Y - p0.Y) - (p1.Y - p0.Y) * (p.X - p0.X);
if ((s < 0) != (t < 0) && s != 0 && t != 0)
return false;
var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);
return d == 0 || (d < 0) == (s + t <= 0);
}
2021年更新:这个版本正确处理任意一个缠绕方向(顺时针和逆时针)指定的三角形。请注意,对于恰好位于三角形边缘上的点,本页上的一些其他答案会给出不一致的结果,这取决于三角形三个点的排列顺序。这些点被认为是“在”三角形中,这段代码正确地返回true,而不管缠绕方向如何。
我要做的是预先计算三个面法线,
在三维中通过边向量和面法向量的叉乘得到。 通过简单地交换分量和负一个,
对于任意一条边的内/外都是边法线和点到点向量的点积,改变符号。重复其他两(或更多)面。
好处:
在同一个三角形上进行多点测试,很多都是预先计算好的。 早期拒签的常见情况是外分多内分。(如果点分布偏向一侧,可以先测试这一侧。)
bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
/* inputs: e=point.x, f=point.y
a=triangle.Ax, b=triangle.Bx, c=triangle.Cx
g=triangle.Ay, h=triangle.By, i=triangle.Cy */
v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
else return false;//is outside
return 0;
}
从质心转换而来的几乎完美的笛卡尔坐标 在*v (x)和*w (y)双精度内导出。 在每种情况下,两个导出双精度对象前面都应该有一个*字符,可能是*v和*w 代码也可以用于四边形的另一个三角形。 特此签名只写三角形abc从顺时针abcd的四边形。
A---B
|..\\.o|
|....\\.|
D---C
o点在ABC三角形内 对于带有第二个三角形的测试,将此函数称为CDA方向,*v=1-*v后的结果应正确;* w = 1 - * w;为了四合院
最简单的方法,适用于所有类型的三角形,就是确定P点A点B点C点的角。如果任何一个角大于180.0度,那么它在外面,如果是180.0度,那么它在圆周上,如果acos欺骗了你,小于180.0度,那么它在里面。看一看理解http://math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html
我同意Andreas Brinck的观点,重心坐标对于这项任务来说非常方便。注意,不需要每次都求解一个方程组:只需计算解析解。使用Andreas的符号,解是:
s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);
其中Area是三角形的(带符号的)面积:
Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);
只计算st和1-s-t。点p在三角形内当且仅当它们都是正的。
编辑:请注意,上面的区域表达式假设三角形节点编号是逆时针方向的。如果编号是顺时针的,这个表达式将返回一个负的面积(但大小正确)。然而,测试本身(s>0 && t>0 && 1-s-t>0)并不依赖于编号的方向,因为如果三角形节点的方向改变,上面乘以1/(2*Area)的表达式也会改变符号。
编辑2:为了获得更好的计算效率,请参阅下面的coproc注释(其中指出,如果三角形节点的方向(顺时针或逆时针)事先已知,则可以避免在s和t的表达式中除以2*Area)。在Andreas Brinck的回答下面的评论中也可以看到Perro Azul的jsfiddle-code。