如何确定一个点是否在二维三角形中?

有没有一种简单的方法来确定一个点是否在三角形内?是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

2017-09-25 16:13:20

其他回答

一般来说，最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。

以下是关于GameDev的一些高质量信息，包括性能问题。

这里有一些代码让你开始:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

2010-01-12 14:27:02

下面是一个高效的Python实现:

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

和一个示例输出:

2014-01-06 11:32:43

其中一个最简单的方法来检查是否由三角形的顶点组成的面积 (x1,y1) (x2,y2) (x3,y3)是否为正。

面积可由公式计算:

1/2 [x1（y2–y3） + x2（y3–y1） + x3（y1–y2）]

或者python代码可以写成:

def triangleornot(p1,p2,p3):
    return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]

2019-02-03 05:41:39

如果你正在寻找速度，这里有一个方法可能会帮助你。

对三角形顶点的纵坐标进行排序。这最多需要三次比较。设Y0 Y1 Y2是三个排好序的值。通过画三条水平线，你可以把这个平面分成两个半平面和两块平板。设Y为查询点的纵坐标。

if Y < Y1
    if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done
    else Y > Y0 -> the point lies in the upper slab
else
    if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done
    else Y < Y2 -> the point lies in the lower slab

又花费了两次比较。如你所见，在“边界板”之外的点可以快速拒绝。

可选地，您可以在横坐标上提供一个测试，以便在左侧和右侧快速拒绝(X <= X0'或X >= X2')。这将同时实现一个快速的包围框测试，但您还需要在横坐标上排序。

最终，你需要计算给定点的符号，相对于三角形的两边，划定相关的板(上或下)。该测试形式为:

((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))

关于i, j, k组合的完整讨论(根据排序的结果，有六种组合)超出了这个答案的范围，“留给读者练习”;为了提高效率，它们应该被硬编码。

如果您认为这个解决方案很复杂，请注意，它主要涉及简单的比较(其中一些可以预先计算)，加上6个减法和4个乘法，以防边界盒测试失败。后者的代价是难以克服的，因为在最坏的情况下，你无法避免将测试点与两边进行比较(在其他答案中，没有哪种方法的代价更低，有些方法的代价更低，比如15个减法和6个乘法，有时是除法)。

更新: 用剪切变换更快

如上所述，您可以使用两次比较快速定位由三个顶点纵坐标分隔的四个水平带之一内的点。

您可以选择执行一个或两个额外的X测试来检查边界框(虚线)的内部性。

然后考虑X'= X - m Y, Y' = Y给出的“剪切”变换，其中m是最高边的斜率DX/DY。这个变换会使三角形的这条边是垂直的。因为你知道你在中间水平线的哪一边，所以只用三角形的一条边来测试符号就足够了。

假设你预先计算了斜率m，以及剪切三角形顶点的X'和边方程的系数X = m Y + p，你将需要在最坏的情况下

纵向分类的两个纵坐标比较; 可选的一个或两个横坐标比较用于边界框拒绝; 计算X' = X - m Y; 与剪切三角形的横坐标作一两次比较; 一个符号测试X >< m' Y + p'对剪切三角形的相关边。

2014-02-02 11:27:31