前言

这里是补充题系列文章，旨在为大家补充一些Leetcode上没有但又常考的高频题。

今天为大家分享的是判断一个点是否在三角形内部。

该题曾出现在字节跳动、腾讯、网易、美团、小马智行等公司的面试中。如果你面试的是游戏相关岗位，那就更得需要掌握了。

如何判断一个点在三角形内部，回答了用向量叉乘判断。——2020.7 字节跳动-游戏

手撕：判断一个点是否在三角形内部——2020.9 美团-移动端开发

如何判断一个点在三角形内还是外—— 2019.8 阿里巴巴-游戏

判断点在三角形内——2020.10 小马智行

来一起学习一下吧~

题目描述

给定三角形3个点的坐标，在给定一个点(x,y)，判断该点是否在三角形中。

ps:坐标值均为double型

题目分析

方法一：面积比较

判断△ABO+△BOC+△COA的面积与△ABC是否相等。若相等则O在内部，反之则在外部。

如何计算三角形的面积呢？通过坐标，很容易计算三角形的边长。

再由海伦公式计算面积。
$S = p (p - a) (p - b) (p - c)$
$其中， a, b, c 为三边长度， p = \frac{a + b + c}{2}$

#include <iostream>
#include <math.h>
using namespace std;

struct Point {
    double x;
    double y;
};

double getDist(Point p1,Point p2) {
    //两点之间计算距离公式
    return sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
}
double getArea(Point p1,Point p2,Point p3) {
    double a = getDist(p1, p2);
    double b = getDist(p2, p3);
    double c = getDist(p1, p3);
    double p = (a + b + c) / 2;
    return sqrt(p * (p - a) * (p - b) * (p - c));
}
bool isInTriangle(Point p1,Point p2,Point p3,Point o) {
    double s1 = getArea(p1,p2,o);
    double s2 = getArea(p2,p3,o);
    double s3 = getArea(p3,p1,o);
    double s = getArea(p1,p2,p3);
    return s1+s2+s3 == s; //此处没有用fabs(a-b)<eps比较，是方便大家理解思路
}
int main() {
    Point p1,p2,p3,o;
    cin >> p1.x >> p1.y;
    cin >> p2.x >> p2.y;
    cin >> p3.x >> p3.y;
    cin >> o.x >> o.y;
    bool flag = isInTriangle(p1,p2,p3,o);
    if(flag) puts("Yes");
    else puts("No");
}

由于double类型计算时有精度问题，因此这种方法存在误差，在牛客上无法通过全部测试用例。

方法二：向量叉乘

若点O在三角形内部，则沿着三角形的边逆时针走，点O一定保持在边的左侧。如图示，点在逆时针行走时，在AB，BC，CA的左侧。

如何判断点在一个边的左侧呢？

可以借助向量叉乘来判断O是否在向量AB的哪一侧。通过计算向量AO与向量AB的叉乘的值为正，则表示O在AB的左侧，反之为右侧。

（理解最好，理解不了也不要纠结，把叉乘公式记一下就ok）

向量 $a 是（ m, n$ ）， $b 是（ p, q ）$

$a * b = （ m * q - n * p ）$

本题的核心思路就是这样。如果要让手撕代码，题目可能没有说输入的3个点是逆时针顺序的。比如，上图中如果依次输入的是A,C,B的坐标，那就不行了。

怎么解决呢？假设依次输入的点分别是p1,p2,p3。

我们判断若p3在 $p 1 p 2$ 的右侧！则表示输入的点的顺序是顺时针的，即A,C,B式的输入，将p2,p3调换位置即可保证顺序是逆时针。

详情可以看代码。

参考代码

#include <iostream>
#include <math.h>
using namespace std;
struct Point {
    double x;
    double y;
};
double product(Point p1,Point p2,Point p3) {
    //首先根据坐标计算p1p2和p1p3的向量，然后再计算叉乘
    //p1p2 向量表示为 (p2.x-p1.x,p2.y-p1.y)
    //p1p3 向量表示为 (p3.x-p1.x,p3.y-p1.y)
    return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}
bool isInTriangle(Point p1,Point p2,Point p3,Point o) {
    //保证p1，p2，p3是逆时针顺序
    if(product(p1, p2, p3)<0) return isInTriangle(p1,p3,p2,o);
    if(product(p1, p2, o)>0 && product(p2, p3, o)>0 && product(p3, p1, o)>0)
        return true;
    return false;
}
int main() {
    Point p1,p2,p3,o;
    cin >> p1.x >> p1.y;
    cin >> p2.x >> p2.y;
    cin >> p3.x >> p3.y;
    cin >> o.x >> o.y;
    bool flag = isInTriangle(p1,p2,p3,o);
    if(flag) puts("Yes");
    else puts("No");
}

参考链接

[1] 编程之美——微软技术面试心得
[2] 程序员代码面试指南