前言

了解更多常考高頻算法題可以關(guān)注
公眾號：一個搬磚的胖子
企業(yè)面試題庫:https://codetop.cc/
小程序：CodeTop

該題曾出現(xiàn)在字節(jié)跳動、騰訊、網(wǎng)易、美團(tuán)、小馬智行等公司的面試中。如果你面試的是游戲相關(guān)崗位，那就更得需要掌握了。

• 如何判斷一個點(diǎn)在三角形內(nèi)部，回答了用向量叉乘判斷。——2020.7 字節(jié)跳動-游戲
• 手撕：判斷一個點(diǎn)是否在三角形內(nèi)部——2020.9 美團(tuán)-買菜
• 如何判斷一個點(diǎn)在三角形內(nèi)還是外—— 2019.8 阿里巴巴-游戲
• 怎么判斷一個點(diǎn)在不在三角形內(nèi)——2020.03 騰訊-游戲

題目描述

給定三角形3個點(diǎn)的坐標(biāo)，在給定一個點(diǎn)(x,y)，判斷該點(diǎn)是否在三角形中。
ps:坐標(biāo)值均為double型

題目分析

方法一：面積比較

判斷△ABO+△BOC+△COA的面積與△ABC是否相等。若相等則O在內(nèi)部，反之則在外部。
點(diǎn)O分別在△ABC內(nèi)外的圖示
如何計算三角形的面積呢？通過坐標(biāo)，很容易計算三角形的邊長。再由海倫公式計算面積。

#include <iostream> #include <math.h> using namespace std;struct Point {double x;double y; };double getDist(Point p1,Point p2) {//兩點(diǎn)之間計算距離公式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類型計算時有精度問題，因此這種方法存在誤差，在牛客上無法通過全部測試用例。

方法二：向量叉乘

若點(diǎn)O在三角形內(nèi)部，則沿著三角形的邊逆時針走，點(diǎn)O一定保持在邊的左側(cè)。如圖示，點(diǎn)在逆時針行走時，在AB，BC，CA的左側(cè)。

如何判斷點(diǎn)在一個邊的左側(cè)呢？

可以借助向量叉乘來判斷O是否在向量AB的哪一側(cè)。若計算向量AO與向量AB的叉乘的值為正，則表示O在AB的左側(cè)，反之為右側(cè)。

（理解最好，理解不了也不要糾結(jié)，把叉乘公式記一下就ok）

本題的核心思路就是這樣。如果要讓手撕代碼，題目可能沒有說輸入的3個點(diǎn)是逆時針順序的。比如，上圖中如果依次輸入的是A,C,B的坐標(biāo)，那就不行了。

怎么解決呢？假設(shè)依次輸入的點(diǎn)分別是p1,p2,p3。

我們判斷若p3在的右側(cè)，則表示輸入的點(diǎn)的順序是順時針的，即A,C,B式的輸入，將p2,p3調(diào)換位置即可保證順序是逆時針。

#include <iostream> #include <math.h> using namespace std; struct Point {double x;double y; }; double product(Point p1,Point p2,Point p3) {//首先根據(jù)坐標(biāo)計算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"); }

個人建議：這個解法涉及數(shù)學(xué)，如果不太了解向量知識的可能會花費(fèi)很長時間。比如我，說多了都是淚…如果對你來說也很難，這道題可以先只掌握解法一，把準(zhǔn)備面試的寶貴時間花在其他高頻題上，性價比會更高。但如果你面的是游戲相關(guān)業(yè)務(wù)，又或者是美團(tuán)買菜部門，我還是建議你花點(diǎn)時間學(xué)學(xué)解法二。

參考鏈接

https://mp.weixin.qq.com/s/qnVUJq4lmnLsXJgyHCXngA

總結(jié)

以上是生活随笔為你收集整理的面试高频算法题补充系列：如何判断一个点是否在三角形内？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。