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


当前回答

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

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

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

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

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

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

function isInTriangle(t,p){ function isInBorder(a,b,c,p){ var m = (a.y - b.y) / (a.x - b.x); // calculate the slope return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y); } function findAngle(a,b,c){ // calculate the C angle from 3 points. var ca = Math.hypot(c.x-a.x, c.y-a.y), // ca edge length cb = Math.hypot(c.x-b.x, c.y-b.y), // cb edge length ab = Math.hypot(a.x-b.x, a.y-b.y); // ab edge length return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle } var pas = t.slice(1) .map(tp => findAngle(p,tp,t[0])), // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0]) ta = findAngle(t[1],t[2],t[0]); return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p); } var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}], point1 = {x:3, y:9}, point2 = {x:7, y:9}; console.log(isInTriangle(triangle,point1)); console.log(isInTriangle(triangle,point2));

其他回答

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

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

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

好处:

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

我在最后一次尝试谷歌和找到这个页面之前写了这段代码,所以我想我应该分享它。它基本上是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的同一侧(左或右)的点。然而,上面的方法似乎更适合进行一些优化。

重心法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的边缘半平面版本一致,因为浮点舍入误差。

图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。

其中一个最简单的方法来检查是否由三角形的顶点组成的面积 (x1,y1) (x2,y2) (x3,y3)是否为正。

面积可由公式计算:

1/2 [x1(y2–y3) + x2(y3–y1) + x3(y1–y2)]

或者python代码可以写成:

def triangleornot(p1,p2,p3):
    return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]
bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
  float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), 
    l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), 
    l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
  return (l1>0 && l2>0  && l3>0) || (l1<0 && l2<0 && l3<0);
}

没有比这更有效率的了!三角形的每边都可以有独立的位置和方向,因此需要进行l1、l2和l3三个计算,每个计算需要进行2次乘法。一旦l1, l2和l3是已知的,结果只是一些基本的比较和布尔运算。