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


当前回答

我同意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。

其他回答

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

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

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

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

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

好处:

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

老实说,这就像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));

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

下面是一个python解决方案,它是高效的,文档化的,包含三个单元测试。它具有专业级的质量,并且可以以模块的形式放入您的项目中。

import unittest

###############################################################################
def point_in_triangle(point, triangle):
    """Returns True if the point is inside the triangle
    and returns False if it falls outside.
    - The argument *point* is a tuple with two elements
    containing the X,Y coordinates respectively.
    - The argument *triangle* is a tuple with three elements each
    element consisting of a tuple of X,Y coordinates.

    It works like this:
    Walk clockwise or counterclockwise around the triangle
    and project the point onto the segment we are crossing
    by using the dot product.
    Finally, check that the vector created is on the same side
    for each of the triangle's segments.
    """
    # Unpack arguments
    x, y = point
    ax, ay = triangle[0]
    bx, by = triangle[1]
    cx, cy = triangle[2]
    # Segment A to B
    side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
    # Segment B to C
    side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
    # Segment C to A
    side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
    # All the signs must be positive or all negative
    return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)

###############################################################################
class TestPointInTriangle(unittest.TestCase):

    triangle = ((22 , 8),
                (12 , 55),
                (7 , 19))

    def test_inside(self):
        point = (15, 20)
        self.assertTrue(point_in_triangle(point, self.triangle))

    def test_outside(self):
        point = (1, 7)
        self.assertFalse(point_in_triangle(point, self.triangle))

    def test_border_case(self):
        """If the point is exactly on one of the triangle's edges,
        we consider it is inside."""
        point = (7, 19)
        self.assertTrue(point_in_triangle(point, self.triangle))

###############################################################################
if __name__ == "__main__":
    suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
    unittest.TextTestRunner().run(suite)

上面的算法有一个额外的可选图形测试,以确认其有效性:

import random
from matplotlib import pyplot
from triangle_test import point_in_triangle

###############################################################################
# The area #
size_x = 64
size_y = 64

# The triangle #
triangle = ((22 , 8),
            (12 , 55),
            (7 , 19))

# Number of random points #
count_points = 10000

# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)

# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))

# Plot the points #
for i in range(count_points):
    x = random.uniform(0, size_x)
    y = random.uniform(0, size_y)
    if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
    else:                                  pyplot.plot(x, y, '.b')

# Save it #
figure.savefig("point_in_triangle.pdf")

制作以下图表: