在進行圖形求交時，常常需要判定兩個圖形間是否有包含關系。如點是否包含在線段、平面區域、三維形體中，線段是否包含在平面區域、三維形體中，等等。許多包含判定問題可轉化為點的包含判定問題，如判斷線段是否在平面上可以轉化為判斷其兩端點是否在平面上。因此下面主要討論關于點的包含判定算法。
判斷點與線段的包含關系，也就是判斷點與線的最短距離是否位于容差范圍內。造型中常用的線段有三種：
（1）直線段，（2）圓錐曲線段（主要是圓?。?）參數曲線（主要是Bezier，B樣條與NURBS曲線）。點與面的包含判定也類似地分為三種情況。下面分別討論。
1、點與直線段的包含判定
假設點坐標為P(x, y, z)，直線段端點為P1(x1, y1, z1)，P2(x2,y2,z2)，則點P到線段P1P2的距離的平方為
d2=(x-x1)2+(y-y1)2+(z-z1)2-[(x2-x1)(x-x1)+(y2-y1)(y-y1)+(z2-z1)(z-z1)]2/[(x2-x1)2+(y2-y1)2+(z2-z1)2]
當d2<a2時，認為點在線段（或其延長線）上，這時還需進一步判斷點是否落在直線段的有效區間內。只要對坐標分量進行比較，假設線段兩端點的x分量不等（否則所有分量均相等，那么線段兩端點重合，線段退化為一點），那么當x-x1與x-x2反號時，點P在線段的有效區間內。
2、點與圓錐曲線段的包含判定
以圓弧為例，假設點的坐標為(x, y, z)，圓弧的中心為（x0, y0, z0），半徑為r，起始角a1，終止角a2。這些角度都是相對于局部坐標系x軸而言。圓弧所在平面為
ax+by+cz+d=0
先判斷點是否在該平面上，若不在，則點不可能被包含。若在，則通過坐標變換，把問題轉換到二維的問題。
給定中心為（x0, y0），半徑為r，起始角a1，終止角a2的圓弧，對平面上一點P（x, y），判斷P是否在圓弧上，可分二步進行。第一步判斷P是否在圓心為（x0, y0），半徑為r的圓的圓周上，即下式是否成立：
第二步判斷P是否在有效的圓弧段內。
3、點與參數曲線的包含判定
設點坐標為P(x, y, z)，參數曲線為Q(t)=(x(t), y(t), z(t))。點也參數曲線的求交計算包括三個步驟：
（1）計算參數t值，使P到Q(t)的距離最?。?/font>
（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)|2最小
根據微積分知識，在該處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）叉積判斷法
假設判斷點為P0。多邊形頂點按順序排列為P1P2…Pn。如圖2.5.2所示。令Vi=Pi-P0, i=1, 2, …, n, Vn+1=V1。
那么，P0在多邊形內的充要條件是叉積ViXVi+1(i=1, 2, …, n)的符號相同。叉積判斷法僅適用于凸多邊形。當多邊形為凹時，盡管點在多邊形內也不能保證上述叉積符號都相同。這時可采用后面介紹的兩種方法。
圖2.5.2 叉積判斷法
（2）夾角之和檢驗法
假設某平面上有點P0和多邊形P1P2P3P4P5，如圖2.5.3所示。將點P0分別與Pi相連，構成向量Vi=P-P0。假設角 PiP0Pi+1=ai。如果
=0，則點P0在多邊形之外，如圖2.5.3(a)所示。如果
=2π，則點P0在多邊形之內，如圖2.5.3(b)所示。ai可通過下列公式計算：令Si=Vi? Vi+1, Ci=Vi·Vi+1，則tg(ai)=Si/Ci，所以ai=arctg(Si/Ci)且
ai的符號即代表角度的方向。
圖2.5.3 夾角之和檢驗法
在多邊形邊數不太多（<44）的情況下，可以采用下列近似公式計算ai。
當 |Si|≤|Ci|
當 |Si|>|Ci|
其中d=0.0355573為常數。當Σαi≥π
時，可判P0在多邊形內。當Σαi＜π 時，可判P0在多邊形外。證明略。
（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(x0, y0, z0)，二次曲面方程為Q(x, y, z)=0，則當|Q(x0, y0, z0)|<? 時，認為點在該二次曲面上，在造型系統中，通常使用裁剪的二次曲面。在這種情況下，還要判斷點是否在有效范圍內。裁剪的二次曲面通常用有理Bezier或有理B樣條的參數空間上的閉合曲線來定義曲面的有效范圍，故要把點所對應的參數空間的參數坐標計算出來，再判斷該參數坐標是否在參數空間有效區域上。
6、點與三維形體的包含判定
判斷點是否被三維形體所包含，可先用前面的方法判斷點是否在三維形體的表面上，然后判斷點是否在形體內部，其方法因形體不同而異。下面以凸多面體為例說明。
設凸多面體某個面的平面方程為ax+by+cz+d=0，調整方程系數的符號，使當ax+by+cz+d<0時，點(x,y,z)位于該平面兩側中包含該凸多面體的一側。于是要檢驗一個點是否在凸多面體內部，只要檢驗是否它對凸多面體的每一個面均滿足以上的不等式即可。
posted on 2007-12-09 20:26
李陽 閱讀(4338)
評論(0) 編輯 收藏 引用 所屬分類:
算法