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

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

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

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

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

我同意Andreas Brinck的观点，重心坐标对于这项任务来说非常方便。注意，不需要每次都求解一个方程组:只需计算解析解。使用Andreas的符号，解是:

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

其中Area是三角形的(带符号的)面积:

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

只计算st和1-s-t。点p在三角形内当且仅当它们都是正的。

编辑:请注意，上面的区域表达式假设三角形节点编号是逆时针方向的。如果编号是顺时针的，这个表达式将返回一个负的面积(但大小正确)。然而，测试本身(s>0 && t>0 && 1-s-t>0)并不依赖于编号的方向，因为如果三角形节点的方向改变，上面乘以1/(2*Area)的表达式也会改变符号。

编辑2:为了获得更好的计算效率，请参阅下面的coproc注释(其中指出，如果三角形节点的方向(顺时针或逆时针)事先已知，则可以避免在s和t的表达式中除以2*Area)。在Andreas Brinck的回答下面的评论中也可以看到Perro Azul的jsfiddle-code。

2013-01-17 15:42:17

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

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

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

推荐文章

最新文章

标签