您的当前位置:首页正文

判断一个点是否在三角形内部

2024-11-08 来源:个人技术集锦



判断一个点是否在三角形内部

题目

在二维坐标系中,所有的值都是double类型,那么一个三角形可以由3个点来代表,
给定3个点代表的三角形,再给定一个点(x,y),判断(x,y)是否在三角形中。

解法1:面积法

算法思路

如果点O在三角形ABC内部,如图9-1所示,那么,有面积ABC=面积ABO+面积BCO+面积CAO;
如果点O在三角形ABC外部,如图9-2所示,那么,有面积ABC<面积ABO+面积BCO+面积CAO。

根据海伦公式,使用三角形边长求出其面积


相应代码
# 解法1:面积法
def getSideLength(x1, y1, x2, y2):
    return ((x1 - x2)**2 + (y1 - y2)**2)**0.5

def getArea(x1, y1, x2, y2, x3, y3):
    # 海伦公式:三角形边长求面积
    a = getSideLength(x1, y1, x2, y2)
    b = getSideLength(x1, y1, x3, y3)
    c = getSideLength(x2, y2, x3, y3)
    p = (a + b + c) / 2
    return (p * (p - a) * (p - b) * (p - c))  ** 0.5

def isInTri1(x1, y1, x2, y2, x3, y3, x, y):
    s = getArea(x1, y1, x2, y2, x3, y3)
    s1 = getArea(x1, y1, x2, y2, x, y)
    s2 = getArea(x1, y1, x3, y3, x, y)
    s3 = getArea(x2, y2, x3, y3, x, y)
    eps = 1e-6  # eps抵消浮点数计算过程的误差
    # 面积相等,有可能在三角形边上,因此需要排除
    if s1 < eps and s2 < eps and s3 < eps and s1 + s2 + s3 - s < eps:
        return True
    else:
        return False

缺陷

开方等浮点数运算,导致结果精度存在偏差。
需要指定eps e.g. 1e-6缓解面积对准情形。


解法2:向量法

算法思路

如果点O在三角形ABC中,那么如果从三角形的一点出发,逆时针走过所有边的过程中,点O始终都在走过边的左侧。如果点O在三角形ABC外部,则不满足这个关系。如下图所示。

Top