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

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

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

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

假設點坐標為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²<a²時，認為點在線段（或其延長線）上，這時還需進一步判斷點是否落在直線段的有效區間內。只要對坐標分量進行比較，假設線段兩端點的x分量不等（否則所有分量均相等，那么線段兩端點重合，線段退化為一點），那么當x-x₁與x-x₂反號時，點P在線段的有效區間內。

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

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

　　　　ax+by+cz+d=0

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

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

第二步判斷P是否在有效的圓弧段內。

3、點與參數曲線的包含判定

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

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

（2）判斷t是否在有效參數區間內（通常為[0，1]）；

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

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

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

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

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

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

4、點與平面區域的包含判定

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

　　　　d=

若d<a ，則認為點在平面上，否則認為點不在平面上。在造型系統中，通常使用平面上的有界區域作為形體的表面。在這種情況下，對落在平面上的點還應進一步判別它是否落在有效區域內。若點落在該區域內，則認為點與該面相交，否則不相交。下面以平面區域多邊形為例，介紹有關算法。

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

（1）叉積判斷法

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

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

圖2.5.2 叉積判斷法

（2）夾角之和檢驗法

假設某平面上有點P₀和多邊形P₁P₂P₃P₄P₅，如圖2.5.3所示。將點P₀分別與P_i相連，構成向量V_i=P-P₀。假設角 P_iP₀P_i+1=a_i。如果=0，則點P₀在多邊形之外，如圖2.5.3(a)所示。如果=2π，則點P₀在多邊形之內，如圖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 夾角之和檢驗法

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

　　　　當 |S_i|≤|C_i|

　　當 |S_i|>|C_i|

其中d=0.0355573為常數。當_Σαi≥π

時，可判P₀在多邊形內。當_Σαi＜π 時，可判P₀在多邊形外。證明略。

（3）交點計數檢驗法

當多邊形是凹多邊形，甚至還帶孔時，可采用交點計數法判斷點是否在多邊形內。具體做法是，從判斷點作一射線至無窮遠：

求射線與多邊形邊的交點個數。若個數為奇數，則點在多邊形內，否則，點在多邊形外。

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

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

圖2.5.4 交點計數法

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

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

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

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

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