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

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

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

1、點(diǎn)與直線段的包含判定

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

2、點(diǎn)與圓錐曲線段的包含判定

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

　　　　ax+by+cz+d=0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　　　d=

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

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

（1）叉積判斷法

假設(shè)判斷點(diǎn)為P₀。多邊形頂點(diǎn)按順序排列為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)的符號(hào)相同。叉積判斷法僅適用于凸多邊形。當(dāng)多邊形為凹時(shí)，盡管點(diǎn)在多邊形內(nèi)也不能保證上述叉積符號(hào)都相同。這時(shí)可采用后面介紹的兩種方法。

圖2.5.2 叉積判斷法

（2）夾角之和檢驗(yàn)法

假設(shè)某平面上有點(diǎn)P₀和多邊形P₁P₂P₃P₄P₅，如圖2.5.3所示。將點(diǎn)P₀分別與P_i相連，構(gòu)成向量V_i=P-P₀。假設(shè)角 P_iP₀P_i+1=a_i。如果=0，則點(diǎn)P₀在多邊形之外，如圖2.5.3(a)所示。如果=2π，則點(diǎn)P₀在多邊形之內(nèi)，如圖2.5.3(b)所示。a_i可通過下列公式計(jì)算：令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的符號(hào)即代表角度的方向。

圖2.5.3 夾角之和檢驗(yàn)法

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

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

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

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

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

（3）交點(diǎn)計(jì)數(shù)檢驗(yàn)法

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

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

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

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

圖2.5.4 交點(diǎn)計(jì)數(shù)法

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

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

6、點(diǎn)與三維形體的包含判定

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

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