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

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

当前回答

通过使用重心坐标的解析解(由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

其他回答

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

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

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

重心法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

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

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

推荐文章

最新文章

标签