判斷某點是否在三角形內

這個問題碰到過好幾次了，不僅是筆試的時候，還有在工作上，所以這里做個小總結。

1、通過第三方庫函數

首先介紹最簡單的方法，直接調用已有的函數。采用python的matplotlib庫，里面的Path.contains_points,
該函數十分強大，可以根據任意幾個點所組成的多邊形，計算新輸入的點是否在該多邊形內，當然三角形就是其中的一種情況了。

該函數使用示例如下：

>>>from matplotlib import path >>>p = path.Path([(0, 0), (1, 0), (1, 1)]) >>>p.contains_points([(0.1, 0.1)]) array([ True], dtype=bool)

其中我們用(0, 0)、(0, 1)、(1, 1)構建了一個三角形，當新輸入一點(0.1, 0.1)的時候，返回值為True，說明該點位于三角形內。該函數還支持輸入多個點進行判決，得到一個bool型的array數組。

看到array自然就能聯想到，它也支持以numpy.array格式輸入的點，但是一定要注意，以此種格式輸入時，一定要加上reshape(n, 2)，即輸入必須為一個n行2列的數組。

2、內角和等于360°

這種方法最好理解，即對于△ABC內的某一點P，連接PA、PB、PC得到三條線段，當且僅當三條線段組成的三個夾角和為360°的時候，該點才位于三角形內部。但此種方法的計算涉及到平方根、反正（余）弦，效率十分低下。

類似的還有，P與ABC三個頂點組成的三個三角形，面積之和等于△ABC的面積，同樣可以證明點P位于三角形內部，但效率也很低。

3、Same Side Technique

這種方法是我從別處看來的，覺得很新穎，想看英文原版的可以直接點這里。下面我解釋一下該方法的思想，首先看下圖：

如果某點位于△ABC內部，那么該點一定位于AB的下邊，AC的右邊，BC的左邊。要用數學的方法來表示，可以采用向量積，向量積有個很重要的右手定則，忘記了的自行復習一下。下面接著看下一張圖：

對于任意的一點P, AB→×AP→，其結果根據右手定則，應為指向屏幕外，而AB→×AP′→的結果則是指向屏幕里。根據這一特性，我們只要找到某一點P，滿足AB→×AP→與AB→×AC→具有同一方向、AC→×AP→與AC→×AB→具有同一方向、BC→×BP→與BC→×BA→具有同一方向，則點P位于△ABC內。

這種方法涉及到的計算是向量運算，沒有平方根、反余弦這些，效率比第2種方法高，代碼部分可以參考原文，下面著重介紹最后一種方法。

4、Barycentric Coordinates

最后一種方法的效率最高，但是理解起來需要的步驟多一點，我們先看下面這張圖

AP→可表示為：

AP→=u?AB→+v?AC→
其中u、v為常量系數，從圖中我們即可得知，當u>0且v>0時，P的位置才有可能正確，那是不是u、v可以無限大呢？當然不是，當u+v>1時，P就會超出三角形的范圍，而當u+v=1時，點P剛好位于BC上，這里稍微證明一下。
當點P在BC上時，也就是 BP→、PC→同向，將前面 AP→的表示方式代入，那么這兩個向量可以分別表示為：
BP→=AP→?AB→=(u?1)?AB→+v?AC→ PC→=AC→?AP→=(1?v)?AC→?u?AB→
由于兩者同向，那么就存在一個 λ( λ>0)，使得 BP→=λPC→，代入上面兩式，整理一下，就得到了下面的式子：
(u?1+λu)?AB→=(λ?λv?v)?AC→
上式要成立，當且僅當左右兩邊的系數都為0。由此得到兩個方程，消去 λ就可以得到u+v=1了。有了這一點，為什么三角形內部點的u、v之和小于1，外部點的大于1，請讀者自行理解，這里不再展開了。

根據模型，得到公式

由此我們的模型就得到了：對于任意給定的一點P，判斷其是否位于△ABC的內部，就是要計算其相對于△ABC的u、v值，只要這兩個值滿足u>0、 v>0、 u+v<1，那么可以確定點P位于三角形內。這樣只要得到u、v的表達式，在代碼里面就能直接使用了。該表達式的推導還是有點麻煩的，我看原文（最底下）中，作者是用軟件算出來的，想挑戰一下的朋友也可以自行推導，這里我直接給出最終的代碼（參考的是stackoverflow上面的第三個回答）：

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);u = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py); v = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

其中p0、p1、p2分別是三角形的三個頂點，p表示待判斷的點，后面跟著x、y表示頂點的橫、縱坐標。只要滿足u>0、v>0、u+v<1，就說明p位于p0、p1、p2組成的三角形內部，這幾個公式的計算量對計算機而言是相當小了。

PS

第一次寫技術類博客，竟然是兩個月以后了，拖延癥晚期啊。而且剛開始寫，也不知道側重點在哪，因為有的時候看下解決方案就好，有的時候可能還想了解一下原理，還是慢慢摸索吧。最后，這篇文章還是費了不少時間的，由此我想到了網上那些大神的博客，衷心為他們點贊！

---

總結

以上是生活随笔為你收集整理的判断某点是否在三角形内的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。