文章目录
判断一个点是否在三角形内部
题目
在二维坐标系中，所有的值都是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外部，则不满足这个关系。如下图所示。
使用向量积（叉积）判断相对方位（内外侧）。
注意:保持三个点相对位置为逆时针方向。
需先对AB和CA叉积运算，判断其相对位置，若结果大于0，则交换B，C点位置。
相应代码
# 解法2：叉积法
def crossProduct(x1, y1, x2, y2):
return x1 * y2 - x2 * y1
def isInTri2(x1, y1, x2, y2, x3, y3, x, y):
# 保证三个点相对位置为逆时针方向：1 -> 2 -> 3
if crossProduct(x2 - x1, y2 - y1, x3 - x1, y3 - y1) >= 0:
x2, x3 = x3, x2
y2, y3 = y3, y2
if crossProduct(x2 - x1, y2 - y1, x - x1, y - y1) <= 0:
return False
if crossProduct(x3 - x2, y3 - y2, x - x2, y - y2) <= 0:
return False
if crossProduct(x1 - x3, y1 - y3, x - x3, y - y3) <= 0:
return False
return True
有任何疑问和建议，欢迎在评论区留言和指正！
感谢您所花费的时间与精力！