OpenCASCADE Point Classifier

eryar@163.com

在解決幾何問(wèn)題時(shí)常會(huì)遇到這樣的問(wèn)題：給定平面上一個(gè)有N條邊的簡(jiǎn)單多邊形P和一點(diǎn)z，在問(wèn)點(diǎn)z是在P的內(nèi)部還是外部，或者是在多邊形的邊上。在OpenCASCADE中也有對(duì)點(diǎn)的位置判斷的功能，叫分類器Classifier，其主要功能就是用于點(diǎn)的定位。點(diǎn)定位功能主要用于模型的網(wǎng)格化Mesh，布爾運(yùn)算（BO）中面的重構(gòu)等。

點(diǎn)定位的狀態(tài)由TopAbs_State來(lái)表示，總共有以下幾種狀態(tài)：

引入U(xiǎn)NKNOWN是因?yàn)檫@個(gè)枚舉也經(jīng)常用于表示計(jì)算失敗的狀態(tài)。當(dāng)不能確定點(diǎn)在外部或內(nèi)部時(shí)，就用UNKNOWN來(lái)表示。

       點(diǎn)定位相關(guān)的類名都是帶有Classifier或其縮寫(xiě)，如：

l  CSLib_Class2d：最底層的多邊形點(diǎn)定位類，用于二維空間點(diǎn)與多邊形的定位；

l  BRepClass_FaceClassifier：判斷參數(shù)點(diǎn)是否在面Face的參數(shù)空間和模型點(diǎn)是否在面上；

l  BRepClass3d_SolidClassifier：判斷點(diǎn)是否在體Solid內(nèi)部；

l  IntTools_FClass2d：判斷參數(shù)點(diǎn)是否在面Face的參數(shù)空間；

判斷一個(gè)點(diǎn)是否在多邊形內(nèi)部常見(jiàn)算法有：

（1）面積和判別法：判斷目標(biāo)點(diǎn)與多邊形的每條邊組成的三角形面積和是否等于該多邊形，相等則在多邊形內(nèi)部。

（2）夾角和判別法：判斷目標(biāo)點(diǎn)與所有邊的夾角和是否為360度，為360度則在多邊形內(nèi)部。

（3）引射線法：從目標(biāo)點(diǎn)出發(fā)引一條射線，看這條射線和多邊形所有邊的交點(diǎn)數(shù)目。如果有奇數(shù)個(gè)交點(diǎn)，則說(shuō)明在內(nèi)部，如果有偶數(shù)個(gè)交點(diǎn)，則說(shuō)明在外部。時(shí)間復(fù)雜度：O（n） 適用范圍：任意多邊形。是非常不錯(cuò)的算法（不需考慮精度誤差和多邊形點(diǎn)給出的順序），可以作為第一選擇。算法思想：以被測(cè)點(diǎn)Q為端點(diǎn)，向任意方向作射線（一般水平向右作射線），統(tǒng)計(jì)該射線與多邊形的交點(diǎn)數(shù)。如果為奇數(shù)，Q在多邊形內(nèi)；如果為偶數(shù)，Q在多邊形外。

OpenCASCADE中判斷點(diǎn)在多邊形內(nèi)部也是采用了射線法，相關(guān)代碼如下：

其中變量nbc即是交點(diǎn)的個(gè)數(shù)。

x, y是需判定點(diǎn)與多邊形中一條線段起點(diǎn)的差值，SH是表示點(diǎn)與起點(diǎn)的狀態(tài)，起點(diǎn)在判定點(diǎn)下方時(shí)為-1，否則為1；

nx, ny是需判定點(diǎn)與多邊形中一條線段終點(diǎn)的差值，NH是表示點(diǎn)與終點(diǎn)的狀態(tài)，終點(diǎn)在判定點(diǎn)下方時(shí)為-1，否則為1；

當(dāng)多邊形中一條線段起點(diǎn)和終點(diǎn)與指定點(diǎn)狀態(tài)不一致時(shí)，即判定點(diǎn)在線段的Y之間才會(huì)有相交。

返回值使用了一個(gè)位運(yùn)算來(lái)判斷交點(diǎn)個(gè)數(shù)是否為偶數(shù)。

參考資料：

1 https://blog.csdn.net/WilliamSun0122/article/details/77994526

2 https://blog.csdn.net/zsjzliziyang/article/details/108813349

3 https://www.jianshu.com/p/0e974c27af09

為了方便大家在移動(dòng)端也能看到我的博文和討論交流，現(xiàn)已注冊(cè)微信公眾號(hào)，歡迎大家掃描下方二維碼關(guān)注。