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

有没有一种简单的方法来确定一个点是否在三角形内?是2D的，不是3D的。

当前回答

由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，而不管缠绕方向如何。

2013-12-31 17:34:51

其他回答

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

我在最后一次尝试谷歌和找到这个页面之前写了这段代码，所以我想我应该分享它。它基本上是Kisielewicz答案的优化版本。我也研究了重心法，但从维基百科的文章来看，我很难看出它是如何更有效的(我猜有一些更深层次的等价性)。不管怎样，这个算法的优点是不用除法;一个潜在的问题是边缘检测的行为取决于方向。

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x - a.x;
    int as_y = s.y - a.y;

    bool s_ab = (b.x - a.x) * as_y - (b.y - a.y) * as_x > 0;

    if ((c.x - a.x) * as_y - (c.y - a.y) * as_x > 0 == s_ab) 
        return false;
    if ((c.x - b.x) * (s.y - b.y) - (c.y - b.y)*(s.x - b.x) > 0 != s_ab) 
        return false;
    return true;
}

换句话说，思想是这样的:点s是在直线AB和直线AC的左边还是右边?如果是真的，它就不可能在里面。如果为假，则至少在“锥”内满足条件。现在，因为我们知道三角形(三角形)内的一个点必须与BC(以及CA)在AB的同一侧，我们检查它们是否不同。如果有，s就不可能在里面，否则s一定在里面。

计算中的一些关键字是线半平面和行列式(2x2叉乘)。也许一个更有教学意义的方法是将它看作是一个在AB、BC和CA的同一侧(左或右)的点。然而，上面的方法似乎更适合进行一些优化。

2012-03-18 01:22:31

因为没有JS的答案，顺时针和逆时针解决方案:

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) >= 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) >= 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) >= 0    

}

编辑:修正了两个拼写错误(关于符号和比较)。

https://jsfiddle.net/jniac/rctb3gfL/

我在这里使用与上面描述的相同的方法:如果一个点分别位于AB, BC, CA的“同”边，则它在ABC内。

2017-12-08 23:11:28

If you know the co-ordinates of the three vertices and the co-ordinates of the specific point, then you can get the area of the complete triangle. Afterwards, calculate the area of the three triangle segments (one point being the point given and the other two being any two vertices of the triangle). Thus, you will get the area of the three triangle segments. If the sum of these areas are equal to the total area (that you got previously), then, the point should be inside the triangle. Otherwise, the point is not inside the triangle. This should work. If there are any issues, let me know. Thank you.

2014-08-03 18:56:04

通过使用重心坐标的解析解(由Andreas Brinck指出)和:

不是把乘法分布在括号里的项上通过存储相同的项来避免多次计算还原比较(如coproc和Thomas Eding所指出的)

可以最小化“昂贵”操作的数量:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

代码可以粘贴在Perro Azul jsfiddle中，或者通过点击下面的“运行代码片段”来尝试

导致:

变量“召回”:30 可变存储:7 补充:4 减法:8 乘法:6 部门:没有比较:4

这与Kornel Kisielewicz解决方案(25次召回，1次存储，15次减法，6次乘法，5次比较)相比非常好，如果需要顺时针/逆时针检测(它本身需要6次召回，1次加法，2次减法，2次乘法和1次比较，使用解析解行列式，如rhgb所指出的)，可能会更好。

2015-12-04 17:08:58

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

推荐文章

最新文章

标签