有没有一种简单的方法来确定一个点是否在三角形内?是2D的,不是3D的。
当前回答
python中的其他函数,比Developer的方法更快(至少对我来说),并受到Cédric Dufour解决方案的启发:
def ptInTriang(p_test, p0, p1, p2):
dX = p_test[0] - p0[0]
dY = p_test[1] - p0[1]
dX20 = p2[0] - p0[0]
dY20 = p2[1] - p0[1]
dX10 = p1[0] - p0[0]
dY10 = p1[1] - p0[1]
s_p = (dY20*dX) - (dX20*dY)
t_p = (dX10*dY) - (dY10*dX)
D = (dX10*dY20) - (dY10*dX20)
if D > 0:
return ( (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D )
else:
return ( (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D )
你可以用:
X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8])
p1 = np.array([12 , 55])
p2 = np.array([7 , 19])
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
p_test[0] = points_unif[0][i]
p_test[1] = points_unif[1][i]
if ptInTriang(p_test, p0, p1, p2):
plt.plot(p_test[0], p_test[1], '.g')
else:
plt.plot(p_test[0], p_test[1], '.r')
绘制网格需要花费很多时间,但是该网格在0.0195319652557秒内测试,而开发人员代码为0.0844349861145秒。
最后是代码注释:
# Using barycentric coordintes, any point inside can be described as:
# X = p0.x * r + p1.x * s + p2.x * t
# Y = p0.y * r + p1.y * s + p2.y * t
# with:
# r + s + t = 1 and 0 < r,s,t < 1
# then: r = 1 - s - t
# and then:
# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t
# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t
#
# X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# we have to solve:
#
# [ X - p0.x ] = [(p1.x-p0.x) (p2.x-p0.x)] * [ s ]
# [ Y - p0.Y ] [(p1.y-p0.y) (p2.y-p0.y)] [ t ]
#
# ---> b = A*x ; ---> x = A^-1 * b
#
# [ s ] = A^-1 * [ X - p0.x ]
# [ t ] [ Y - p0.Y ]
#
# A^-1 = 1/D * adj(A)
#
# The adjugate of A:
#
# adj(A) = [(p2.y-p0.y) -(p2.x-p0.x)]
# [-(p1.y-p0.y) (p1.x-p0.x)]
#
# The determinant of A:
#
# D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)
#
# Then:
#
# s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }
# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }
#
# s = s_p / D
# t = t_p / D
#
# Recovering r:
#
# r = 1 - (s_p + t_p)/D
#
# Since we only want to know if it is insidem not the barycentric coordinate:
#
# 0 < 1 - (s_p + t_p)/D < 1
# 0 < (s_p + t_p)/D < 1
# 0 < (s_p + t_p) < D
#
# The condition is:
# if D > 0:
# s_p > 0 and t_p > 0 and (s_p + t_p) < D
# else:
# s_p < 0 and t_p < 0 and (s_p + t_p) > D
#
# s_p = { dY20*dX - dX20*dY }
# t_p = { dX10*dY - dY10*dX }
# D = dX10*dY20 - dY10*dX20
其他回答
由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,而不管缠绕方向如何。
我要做的是预先计算三个面法线,
在三维中通过边向量和面法向量的叉乘得到。 通过简单地交换分量和负一个,
对于任意一条边的内/外都是边法线和点到点向量的点积,改变符号。重复其他两(或更多)面。
好处:
在同一个三角形上进行多点测试,很多都是预先计算好的。 早期拒签的常见情况是外分多内分。(如果点分布偏向一侧,可以先测试这一侧。)
我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解,它会更容易理解。
区域A定义为s * v02 + t * v01给出的任意向量,条件s >= 0, t >= 0。如果三角形v0 v1 v2内的任意一点,它一定在区域A内。
如果进一步限制s, t属于[0,1]。得到包含s * v02 + t * v01的所有向量的区域B,条件s, t属于[0,1]。值得注意的是,区域B的下部是三角形v0, v1, v2的镜像。问题来了,我们是否可以给定一定的s和t条件,来进一步排除区域B的低部分。
假设我们给出一个值s, t在[0,1]内变化。在下图中,点p位于v1v2的边缘。s * v02 + t * v01的所有向量沿着虚线通过简单向量和得到。在v1v2和虚线交点p处,我们有:
(1-S)|V0v2|/ |v0v2|= tp|v0v1|/ |v0v1|
得到1 - s = tp,然后1 = s + tp。如果任意t > tp,即1 < s + t where在双虚线上,则该向量在三角形外,任意t <= tp,即1 >= s + t where在单虚线上,则该向量在三角形内。
如果我们给出[0,1]中的任意s,对应的t必须满足1 >= s + t,对于三角形内的向量。
最后我们得到v = s * v02 +t * v01, v在三角形内,条件s, t, s+t属于[0,1]。然后翻译到点,我们有
P - p0 = s * (p1 - p0) + t * (p2 - p0), and s, t, s + t in [0,1]
和Andreas解方程组的解是一样的 P = p0 + s * (p1 - p0) + t * (p2 - p0),带s, t, s + t属于[0,1]。
我同意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。
老实说,这就像Simon P Steven的回答一样简单,但是用这种方法,你无法控制你是否想要包含三角形边缘上的点。
我的方法有点不同,但非常基本。考虑下面的三角形;
为了在三角形中有这个点我们必须满足三个条件
ACE角(绿色)应小于ACB角(红色) ECB角(蓝色)应小于ACB角(红色) 当点E和点C的x和y值应用于|AB|直线方程时,点E和点C的符号应该相同。
在此方法中,您可以完全控制单独包含或排除边缘上的点。所以你可以检查一个点是否在三角形中,例如,只包括|AC|边。
所以我的JavaScript解决方案是这样的;
function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (a.y - b.y) / (a.x - b.x); // calculate the slope return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(c.x-a.x, c.y-a.y), // ca edge length cb = Math.hypot(c.x-b.x, c.y-b.y), // cb edge length ab = Math.hypot(a.x-b.x, a.y-b.y); // ab edge length return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle } var pas = t.slice(1) .map(tp => findAngle(p,tp,t[0])), // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0]) ta = findAngle(t[1],t[2],t[0]); return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p); } var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}], point1 = {x:3, y:9}, point2 = {x:7, y:9}; console.log(isInTriangle(triangle,point1)); console.log(isInTriangle(triangle,point2));