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

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

当前回答

我要做的是预先计算三个面法线，

在三维中通过边向量和面法向量的叉乘得到。通过简单地交换分量和负一个，

对于任意一条边的内/外都是边法线和点到点向量的点积，改变符号。重复其他两(或更多)面。

好处:

在同一个三角形上进行多点测试，很多都是预先计算好的。早期拒签的常见情况是外分多内分。(如果点分布偏向一侧，可以先测试这一侧。)

2012-10-29 23:28:23

其他回答

我在最后一次尝试谷歌和找到这个页面之前写了这段代码，所以我想我应该分享它。它基本上是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

由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

求解如下方程组:

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

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

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

2010-01-12 14:41:40

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