【题目】
在二维坐标系中,所有的值都是double型,那么一个三角形可以由三个点来代表,给定三个点代表的三角形,再给定一个点(x, y),判断(x, y)是否在三角形中。
【基本思路】
方法一。
等面积法。如果一个点在三角形内部,那么以该点为顶的三个小三角形的面积和应该等于大三角形的面积。如果这个点在三角形的外部,那么三个小三角形的面积和要大于大三角形的面积。知道三个点,如何求该三个点为顶点的三角形的面积?使用海伦公式:
虽然该方法的逻辑是正确的,但是并不推荐使用该方法。因为double类型的值在计算时会出现一定程度的偏差。所以经常会出现一个点明明在三角形内部,面积却对不准的情况,最终导致判断出错。方法二则没有此顾虑。
方法二。
如果一个点O在三角形的内部,那么从三角形的一个点出发,逆时针走过所有边的过程中,点O始终在走过边的左边。如果点O在外侧,则不满足这一条件。
如果要逆时针走过一遍三角形,那么三个点的位置是重要的,假设输入的三个点依次是a,b,c,如果b在边ac的左边,按照a -> b -> c的顺序遍历是顺时针遍历,如果b在边ac的右边,按照a -> b -> c的顺序遍历就是逆时针遍历。如果出现前者情况,我们需要先调整一下三个点输入的顺序。
接下来的重点就是判断一个点是在一条边的左侧还是右侧。该问题可以使用几何上的向量积(叉积)解决。
设线段端点为从A(x1, y1)到B(x2, y2),线外一点p(x, y)。
一个简单的确定满足“右手定则”的结果向量的方向的方法是这样的:若坐标系是满足右手定则的,当右手的四指从a以不超过180度的转角转向b时,竖起的大拇指指向是c的方向。
实现代码参见isInside2。
【代码实现】
#python3.5
def isInside1(x1, y1, x2, y2, x3, y3, x, y):
def getSideLength(x1, y1, x2, y2):
a = abs(x2 - x1)
b = abs(y2 - y1)
return math.sqrt(a*a + b*b)
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 math.sqrt(p * (p-a) * (p-b) * (p-c))
area1 = getArea(x1, y1, x2, y2, x, y)
print(area1)
area2 = getArea(x1, y1, x3, y3, x, y)
print(area2)
area3 = getArea(x2, y2, x3, y3, x, y)
print(area3)
allArea = getArea(x1, y1, x2, y2, x3, y3)
print(allArea)
return (area1 + area2 + area3) <= allArea
def isInside2(x1, y1, x2, y2, x3, y3, x, y):
def crossProduct(x1, y1, x2, y2):
return x1 * y2 - x2 * y1
if crossProduct(x3-x1, y3-y1, x2-x1, y2-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