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

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

当前回答

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

其他回答

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

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

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

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

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

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

2016-12-03 17:59:01

下面是一个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")

制作以下图表:

2018-07-23 12:57:41

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

我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解，它会更容易理解。

区域A定义为s * v02 + t * v01给出的任意向量，条件s >= 0, t >= 0。如果三角形v0 v1 v2内的任意一点，它一定在区域A内。

如果进一步限制s, t属于[0,1]。得到包含s * v02 + t * v01的所有向量的区域B，条件s, t属于[0,1]。值得注意的是，区域B的下部是三角形v0, v1, v2的镜像。问题来了，我们是否可以给定一定的s和t条件，来进一步排除区域B的低部分。

假设我们给出一个值s, t在[0,1]内变化。在下图中，点p位于v1v2的边缘。s * v02 + t * v01的所有向量沿着虚线通过简单向量和得到。在v1v2和虚线交点p处，我们有:

（1-S）|V0v2|/ |v0v2|= tp|v0v1|/ |v0v1|

得到1 - s = tp，然后1 = s + tp。如果任意t > tp，即1 < s + t where在双虚线上，则该向量在三角形外，任意t <= tp，即1 >= s + t where在单虚线上，则该向量在三角形内。

如果我们给出[0,1]中的任意s，对应的t必须满足1 >= s + t，对于三角形内的向量。

最后我们得到v = s * v02 +t * v01, v在三角形内，条件s, t, s+t属于[0,1]。然后翻译到点，我们有

P - p0 = s * (p1 - p0) + t * (p2 - p0)， and s, t, s + t in [0,1]

和Andreas解方程组的解是一样的 P = p0 + s * (p1 - p0) + t * (p2 - p0)，带s, t, s + t属于[0,1]。

2016-07-14 19:33:55

求解如下方程组:

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

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

推荐文章

最新文章

标签