在進(jìn)行圖形求交時，常常需要判定兩個圖形間是否有包含關(guān)系。如點是否包含在線段、平面區(qū)域、三維形體中，線段是否包含在平面區(qū)域、三維形體中，等等。許多包含判定問題可轉(zhuǎn)化為點的包含判定問題，如判斷線段是否在平面上可以轉(zhuǎn)化為判斷其兩端點是否在平面上。因此下面主要討論關(guān)于點的包含判定算法。

判斷點與線段的包含關(guān)系，也就是判斷點與線的最短距離是否位于容差范圍內(nèi)。造型中常用的線段有三種：

（1）直線段，（2）圓錐曲線段（主要是圓弧），（3）參數(shù)曲線（主要是Bezier，B樣條與NURBS曲線）。點與面的包含判定也類似地分為三種情況。下面分別討論。

1、點與直線段的包含判定

假設(shè)點坐標(biāo)為P(x, y, z)，直線段端點為P₁(x₁, y₁, z₁)，P₂(x₂,y₂,z₂)，則點P到線段P₁P₂的距離的平方為

d²=(x-x₁)²+(y-y₁)²+(z-z₁)²-[(x₂-x₁)(x-x₁)+(y₂-y₁)(y-y₁)+(z₂-z₁)(z-z₁)]²/[(x₂-x₁)²+(y₂-y₁)²+(z₂-z₁)²]

當(dāng)d²<a²時，認(rèn)為點在線段（或其延長線）上，這時還需進(jìn)一步判斷點是否落在直線段的有效區(qū)間內(nèi)。只要對坐標(biāo)分量進(jìn)行比較，假設(shè)線段兩端點的x分量不等（否則所有分量均相等，那么線段兩端點重合，線段退化為一點），那么當(dāng)x-x₁與x-x₂反號時，點P在線段的有效區(qū)間內(nèi)。

2、點與圓錐曲線段的包含判定

以圓弧為例，假設(shè)點的坐標(biāo)為(x, y, z)，圓弧的中心為（x₀, y₀, z₀），半徑為r，起始角a₁，終止角a₂。這些角度都是相對于局部坐標(biāo)系x軸而言。圓弧所在平面為

　　　　ax+by+cz+d=0

先判斷點是否在該平面上，若不在，則點不可能被包含。若在，則通過坐標(biāo)變換，把問題轉(zhuǎn)換到二維的問題。

給定中心為（x₀, y₀），半徑為r，起始角a₁，終止角a₂的圓弧，對平面上一點P（x, y），判斷P是否在圓弧上，可分二步進(jìn)行。第一步判斷P是否在圓心為（x₀, y₀），半徑為r的圓的圓周上，即下式是否成立：

第二步判斷P是否在有效的圓弧段內(nèi)。

3、點與參數(shù)曲線的包含判定

設(shè)點坐標(biāo)為P(x, y, z)，參數(shù)曲線為Q(t)=(x(t), y(t), z(t))。點也參數(shù)曲線的求交計算包括三個步驟：

（1）計算參數(shù)t值，使P到Q(t)的距離最小；

（2）判斷t是否在有效參數(shù)區(qū)間內(nèi)（通常為[0，1]）；

（3）判斷Q(t)與P的距離是否小于a 。若（2），（3）步的判斷均為“是”，則點在曲線上；否則點不在曲線上。

第一步應(yīng)計算t，使得|P-Q(t)|最小，

即 R(t)=(P-Q(t))(P-Q(t))=|P-Q(t)|²最小

根據(jù)微積分知識，在該處R'(t)=0即

Q'(t)[P-Q(t)]=0

用數(shù)值方法解出t值，再代入曲線參數(shù)方程可求出曲線上對應(yīng)點的坐標(biāo)。第（2）、（3）步的處理比較簡單，不再詳述。

4、點與平面區(qū)域的包含判定

設(shè)點坐標(biāo)為P(x, y, z)，平面方程為ax+by+cz+d=0。則點到平面的距離為

　　　　d=

若d<a ，則認(rèn)為點在平面上，否則認(rèn)為點不在平面上。在造型系統(tǒng)中，通常使用平面上的有界區(qū)域作為形體的表面。在這種情況下，對落在平面上的點還應(yīng)進(jìn)一步判別它是否落在有效區(qū)域內(nèi)。若點落在該區(qū)域內(nèi)，則認(rèn)為點與該面相交，否則不相交。下面以平面區(qū)域多邊形為例，介紹有關(guān)算法。

判斷平面上一個點是否包含在同平面的一個多邊形內(nèi)，有許多種算法，這里僅介紹常用的三種：叉積判斷法、夾角之和檢驗法以及交點計數(shù)檢驗法。

（1）叉積判斷法

假設(shè)判斷點為P₀。多邊形頂點按順序排列為P₁P₂…P_n。如圖2.5.2所示。令V_i=P_i-P₀, i=1, 2, …, n, V_n+1=V₁。

那么，P₀在多邊形內(nèi)的充要條件是叉積V_iXV_i+1(i=1, 2, …, n)的符號相同。叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為凹時，盡管點在多邊形內(nèi)也不能保證上述叉積符號都相同。這時可采用后面介紹的兩種方法。

圖2.5.2 叉積判斷法

（2）夾角之和檢驗法

假設(shè)某平面上有點P₀和多邊形P₁P₂P₃P₄P₅，如圖2.5.3所示。將點P₀分別與P_i相連，構(gòu)成向量V_i=P-P₀。假設(shè)角 P_iP₀P_i+1=a_i。如果=0，則點P₀在多邊形之外，如圖2.5.3(a)所示。如果=2π，則點P₀在多邊形之內(nèi)，如圖2.5.3(b)所示。a_i可通過下列公式計算：令S_i=V_i? V_i+1, C_i=V_i·V_i+1，則tg(a_i)=S_i/C_i，所以a_i=arctg(S_i/C_i)且

a_i的符號即代表角度的方向。

圖2.5.3 夾角之和檢驗法

在多邊形邊數(shù)不太多（<44）的情況下，可以采用下列近似公式計算a_i。

　　　　當(dāng) |S_i|≤|C_i|

　　當(dāng) |S_i|>|C_i|

其中d=0.0355573為常數(shù)。當(dāng)_Σαi≥π

時，可判P₀在多邊形內(nèi)。當(dāng)_Σαi＜π 時，可判P₀在多邊形外。證明略。

（3）交點計數(shù)檢驗法

當(dāng)多邊形是凹多邊形，甚至還帶孔時，可采用交點計數(shù)法判斷點是否在多邊形內(nèi)。具體做法是，從判斷點作一射線至無窮遠(yuǎn)：

求射線與多邊形邊的交點個數(shù)。若個數(shù)為奇數(shù)，則點在多邊形內(nèi)，否則，點在多邊形外。

如圖2.5.4所示，射線a, c分別與多邊形交于二點和四點，為偶數(shù)，故判斷點A，C在多邊形外。而射線b, d與多邊形交三點和一點，為奇數(shù)，所以B，D在多邊形內(nèi)。

當(dāng)射線穿過多邊形頂點時，必須特殊對待。如圖2.5.4所示，射線f過頂點，若將交點計數(shù)為2，則會錯誤地判斷F在多邊形外。但是，若規(guī)定射線過頂點時，計數(shù)為1，則又會錯誤地判斷點E在多邊形內(nèi)。正確的方法是，若共享頂點的兩邊在射線的同一側(cè)，則交點計數(shù)加2，否則加1。按這種方法，E點計為2，所以在多邊形外；F點計數(shù)為１，所以在多邊形內(nèi)。讀者可以自己另取一些點來驗證。

圖2.5.4 交點計數(shù)法

5、點與二次曲面/參數(shù)曲面的包含判定

假設(shè)點坐標(biāo)為P(x₀, y₀, z₀)，二次曲面方程為Q(x, y, z)=0，則當(dāng)|Q(x₀, y₀, z₀)|<? 時，認(rèn)為點在該二次曲面上，在造型系統(tǒng)中，通常使用裁剪的二次曲面。在這種情況下，還要判斷點是否在有效范圍內(nèi)。裁剪的二次曲面通常用有理Bezier或有理B樣條的參數(shù)空間上的閉合曲線來定義曲面的有效范圍，故要把點所對應(yīng)的參數(shù)空間的參數(shù)坐標(biāo)計算出來，再判斷該參數(shù)坐標(biāo)是否在參數(shù)空間有效區(qū)域上。

6、點與三維形體的包含判定

判斷點是否被三維形體所包含，可先用前面的方法判斷點是否在三維形體的表面上，然后判斷點是否在形體內(nèi)部，其方法因形體不同而異。下面以凸多面體為例說明。

設(shè)凸多面體某個面的平面方程為ax+by+cz+d=0，調(diào)整方程系數(shù)的符號，使當(dāng)ax+by+cz+d<0時，點(x,y,z)位于該平面兩側(cè)中包含該凸多面體的一側(cè)。于是要檢驗一個點是否在凸多面體內(nèi)部，只要檢驗是否它對凸多面體的每一個面均滿足以上的不等式即可。