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

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

当前回答

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

其他回答

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

这是确定一个点是在三角形的内、外还是在三角形的臂上的最简单的概念。

用行列式确定三角形内的点:

最简单的工作代码:

#-*- coding: utf-8 -*-

import numpy as np

tri_points = [(1,1),(2,3),(3,1)]

def pisinTri(point,tri_points):
    Dx , Dy = point

    A,B,C = tri_points
    Ax, Ay = A
    Bx, By = B
    Cx, Cy = C

    M1 = np.array([ [Dx - Bx, Dy - By, 0],
                    [Ax - Bx, Ay - By, 0],
                    [1      , 1      , 1]
                  ])

    M2 = np.array([ [Dx - Ax, Dy - Ay, 0],
                    [Cx - Ax, Cy - Ay, 0],
                    [1      , 1      , 1]
                  ])

    M3 = np.array([ [Dx - Cx, Dy - Cy, 0],
                    [Bx - Cx, By - Cy, 0],
                    [1      , 1      , 1]
                  ])

    M1 = np.linalg.det(M1)
    M2 = np.linalg.det(M2)
    M3 = np.linalg.det(M3)
    print(M1,M2,M3)

    if(M1 == 0 or M2 == 0 or M3 ==0):
            print("Point: ",point," lies on the arms of Triangle")
    elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
            #if products is non 0 check if all of their sign is same
            print("Point: ",point," lies inside the Triangle")
    else:
            print("Point: ",point," lies outside the Triangle")

print("Vertices of Triangle: ",tri_points)
points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]
for c in points:
    pisinTri(c,tri_points)

2018-08-08 14:10:14

有一些恼人的边条件，即一个点恰好在两个相邻三角形的公共边上。这个点不可能在两个三角形中，也不可能不在两个三角形中。你需要一种任意但一致的方式来分配点。例如，画一条横线穿过这个点。如果这条直线与三角形的另一边在右侧相交，则该点被视为在三角形内。如果交点在左边，则该点在外面。

如果该点所在的直线是水平的，则使用above/below。

如果该点位于多个三角形的公共顶点上，则使用该点与中心点形成的角最小的三角形。

更有趣的是:三个点可以在一条直线上(零度)，例如(0,0)-(0,10)-(0,5)。在三角剖分算法中，“耳朵”(0,10)必须被切掉，生成的“三角形”是直线的退化情况。

2015-11-30 23:45:09

老实说，这就像Simon P Steven的回答一样简单，但是用这种方法，你无法控制你是否想要包含三角形边缘上的点。

我的方法有点不同，但非常基本。考虑下面的三角形;

为了在三角形中有这个点我们必须满足三个条件

ACE角(绿色)应小于ACB角(红色) ECB角(蓝色)应小于ACB角(红色) 当点E和点C的x和y值应用于|AB|直线方程时，点E和点C的符号应该相同。

在此方法中，您可以完全控制单独包含或排除边缘上的点。所以你可以检查一个点是否在三角形中，例如，只包括|AC|边。

所以我的JavaScript解决方案是这样的;

2016-12-03 17:59:01

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;为了四合院

2018-02-12 13:00:15

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

推荐文章

最新文章

标签