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

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

题目

在二维坐标系中，所有的值都是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外部，则不满足这个关系。如下图所示。