其他题目---判断一个点是否在三角形内部

时间:2023-01-09 10:23:31

【题目】

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

【基本思路】

  方法一。
  等面积法。如果一个点在三角形内部,那么以该点为顶的三个小三角形的面积和应该等于大三角形的面积。如果这个点在三角形的外部,那么三个小三角形的面积和要大于大三角形的面积。知道三个点,如何求该三个点为顶点的三角形的面积?使用海伦公式 S=p(pa)(pb)(pc) ,其中,a,b,c表示三个边长,p表示半周长,即 p=a+b+c2 。实现代码参见isInside1。

  虽然该方法的逻辑是正确的,但是并不推荐使用该方法。因为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⃗ =(x2x1,y2y1)
   b⃗ =(xx1,yy1)
   a⃗ ×b⃗ =|a⃗ ||b⃗ |sinθ
   a⃗ ×b⃗  决定p的位置,如果 a⃗ ×b⃗  大于0,p在线段左侧;小于0,在右侧;等于0,共线。所以有如下结论:
       xaybxbya>0   p在左侧
       xaybxbya<0   p在右侧
       xaybxbya=0   共线
  一个简单的确定满足“右手定则”的结果向量的方向的方法是这样的:若坐标系是满足右手定则的,当右手的四指从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