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

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

当前回答

重心法Java版:

class Triangle {
    Triangle(double x1, double y1, double x2, double y2, double x3,
            double y3) {
        this.x3 = x3;
        this.y3 = y3;
        y23 = y2 - y3;
        x32 = x3 - x2;
        y31 = y3 - y1;
        x13 = x1 - x3;
        det = y23 * x13 - x32 * y31;
        minD = Math.min(det, 0);
        maxD = Math.max(det, 0);
    }

    boolean contains(double x, double y) {
        double dx = x - x3;
        double dy = y - y3;
        double a = y23 * dx + x32 * dy;
        if (a < minD || a > maxD)
            return false;
        double b = y31 * dx + x13 * dy;
        if (b < minD || b > maxD)
            return false;
        double c = det - a - b;
        if (c < minD || c > maxD)
            return false;
        return true;
    }

    private final double x3, y3;
    private final double y23, x32, y31, x13;
    private final double det, minD, maxD;
}

上面的代码可以准确地处理整数，假设没有溢出。它也适用于顺时针和逆时针三角形。它不适用于共线三角形(但您可以通过测试det==0来检查)。

如果你要用同一个三角形测试不同的点，以重心为中心的版本是最快的。

重心版本在3个三角形点上是不对称的，所以它可能不如Kornel Kisielewicz的边缘半平面版本一致，因为浮点舍入误差。

图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。

2014-08-17 06:22:25

其他回答

由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

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

以下是关于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中的其他函数，比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

我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解，它会更容易理解。

区域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]。

2016-07-14 19:33:55

因为没有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

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

推荐文章

最新文章

标签