一種三角形內外點的快速判定方法

摘 要：提出一種不需進行乘除運算，僅通過比較就可以判定點與三角形的位置關系的新方法。對于三角形內外點的判定，在分析點與三角形位置關系的基礎上，提出通過確定點與給定三角形的相鄰頂點構成新三角形的方向與原三角形的方向是否相同進而確定該點的內外性。利用該方法，同時實現對邊界點內外性的判斷。試驗表明，該算法高效、穩定。

關鍵詞：計算機應用；計算機圖形學；三角形內外點；方向判別

中圖分類號：TP391.4

文獻標識碼：B

文章編號：1004—373X(2008)04—110—03

簡單多邊形的方向及內外點的判定，是計算機圖形學中的一個基本問題，在計算機圖形處理、模式識別、CAD及科學計算、可視化中有著廣泛的應用。判定點在多邊形內外的方法主要有定向角度法、射線法和面積符號判別法等。角度法要使用復雜的三角運算，計算量大。而定向射線法雖然方法簡單、可靠，卻要進行大量的求交運算，并且難以處理對邊界點及邊界與射線共線等特殊情況。雖然，有些文獻對射線法的執行效率以及上述情況進行了一系列改進，但射線法穩定性差的缺點依然沒有得到很好的解決。文獻雖然采用矢量與射線法結合的方法，解決了射線法具有的奇異性，但在判斷中卻用了叉積等運算，不利于效率的提高。FEITO等采用有向三角形面積之和的符號來確定點是否在多邊形內，在判定前采用的確定多邊形方向的方法，卻需要較大計算量，使判定效率受到影響，并且難以處理自相交多邊形的情況。而三角形是一種最簡單的多邊形，也是最基本的多邊形，在實踐中有廣泛的應用。因此，本文以三角形為例，先利用外接矩形判定部分位于三角形外的點，然后結合一種新的有關點在三角形內外的判定方法對剩下點的進行判定，該方法無需進行乘除運算，只需簡單的比較即可判定點的內外性。

1 相關定義

1.1 三角形

他是由不在同一直線上的3條線段首尾順次連結所組成的封閉圖形。三個頂點分別為P₁，P₂，p₃。

1.2 三角形的方向

沿著頂點的排列順序在三角形邊上行進，若三角形始終位于觀測者的左手側，則三角形的方向為逆時針方向；否則，如果三角形始終位于觀測者的右手側，則三角形的方向為順時針方向。

2 三角形方向的確定

本文利用參考文獻的方法僅通過簡單的分析比較即可快速判定三角形的方向。

先從三角形的3個頂點P₁，P₂，p₃中找出最左、最右、最下和最上4個極點，分別用a，b，c，d表示各極點在點列中的序號，其中有一對極點是重合的，如圖1所示，判別規則見表1。

3 點與三角形的位置關系

點與三角形的位置關系有以下幾種情況，如圖2所示。

4 算法原理

4.1點在三角形外的判定

若該點M(x，y)滿足下列不等式之一，則點在矩形邊界同側，點為三角形外點，判斷結束，如圖3中點M₁，點M₂。

角形內點，如圖4(b)中點M₂；否則，包括一些邊界點(圖4(b)中點M₃，M₄)和非邊界點(圖4(b)中點M₁)，全部是三角形的外點。

5 算法實現

任意給定一個三角形P₁P₂P₃和一點M，具體的算法步驟如下：

Step 1：若點M在矩形區域外，則M在三角形外，是三角形的外點，轉Step 6；

Step 2：確定三角形P₁P₂P₃的4個極點a，b，c，d，判定原三角形的方向；

Step 3：點M與三角形前后相鄰的2個頂點構成3個不同的新三角形，判斷新三角形的4個極點，若有1對極點重合，轉Step4；若有2對極點重合，轉Step 5；

Step 4：根據4．2(a)判斷新三角形的方向是否與原三角形方向相同，若相同，點M為內點，否則為外點；

Step 5：根據4．2(b)中內外性判斷的方法，判斷M的內外性，結束后，轉Step 6；

Step 6：判斷結束。

6 結 語

文中根據一個簡單的三角形方向判斷的算法，提出一個不用進行乘除運算，僅通過比較就可以快速判斷點與三角形的位置關系的新方法，該方法比已有方法的計算量小。對于邊界上特殊點的處理，也比較簡單、方便。通過測試，算法快速、穩定。若將此算法推廣到點在任意多邊形內外的判斷上，也是可行的。