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


当前回答

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

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

其他回答

下面是一个高效的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))

和一个示例输出:

bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

从质心转换而来的几乎完美的笛卡尔坐标 在*v (x)和*w (y)双精度内导出。 在每种情况下,两个导出双精度对象前面都应该有一个*字符,可能是*v和*w 代码也可以用于四边形的另一个三角形。 特此签名只写三角形abc从顺时针abcd的四边形。

A---B
|..\\.o|  
|....\\.| 
D---C 

o点在ABC三角形内 对于带有第二个三角形的测试,将此函数称为CDA方向,*v=1-*v后的结果应正确;* w = 1 - * w;为了四合院

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

以下是关于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);
}

一个简单的方法是:

找出连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是 在三角形里面。

两个解释替代方案的好网站是:

黑卒和沃尔夫勒姆

求解如下方程组:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

当0 <= s <= 1和0 <= t <= 1以及s + t <= 1时,点p在三角形内。

S,t和1 - S - t称为点p的重心坐标。