Posted on 2021-04-17 16:45
eryar 閱讀(2100)
評論(0) 編輯 收藏 引用 所屬分類:
2.OpenCASCADE
OpenCASCADE Point Classifier
eryar@163.com
在解決幾何問題時常會遇到這樣的問題：給定平面上一個有N條邊的簡單多邊形P和一點z，在問點z是在P的內(nèi)部還是外部，或者是在多邊形的邊上。在OpenCASCADE中也有對點的位置判斷的功能，叫分類器Classifier，其主要功能就是用于點的定位。點定位功能主要用于模型的網(wǎng)格化Mesh，布爾運算（BO）中面的重構等。
點定位的狀態(tài)由TopAbs_State來表示，總共有以下幾種狀態(tài)：
引入UNKNOWN是因為這個枚舉也經(jīng)常用于表示計算失敗的狀態(tài)。當不能確定點在外部或內(nèi)部時，就用UNKNOWN來表示。
點定位相關的類名都是帶有Classifier或其縮寫，如：
l CSLib_Class2d：最底層的多邊形點定位類，用于二維空間點與多邊形的定位；
l BRepClass_FaceClassifier：判斷參數(shù)點是否在面Face的參數(shù)空間和模型點是否在面上；
l BRepClass3d_SolidClassifier：判斷點是否在體Solid內(nèi)部；
l IntTools_FClass2d：判斷參數(shù)點是否在面Face的參數(shù)空間；
判斷一個點是否在多邊形內(nèi)部常見算法有：
（1）面積和判別法：判斷目標點與多邊形的每條邊組成的三角形面積和是否等于該多邊形，相等則在多邊形內(nèi)部。
（2）夾角和判別法：判斷目標點與所有邊的夾角和是否為360度，為360度則在多邊形內(nèi)部。
（3）引射線法：從目標點出發(fā)引一條射線，看這條射線和多邊形所有邊的交點數(shù)目。如果有奇數(shù)個交點，則說明在內(nèi)部，如果有偶數(shù)個交點，則說明在外部。時間復雜度：O（n） 適用范圍：任意多邊形。是非常不錯的算法（不需考慮精度誤差和多邊形點給出的順序），可以作為第一選擇。算法思想：以被測點Q為端點，向任意方向作射線（一般水平向右作射線），統(tǒng)計該射線與多邊形的交點數(shù)。如果為奇數(shù)，Q在多邊形內(nèi)；如果為偶數(shù)，Q在多邊形外。
OpenCASCADE中判斷點在多邊形內(nèi)部也是采用了射線法，相關代碼如下：
其中變量nbc即是交點的個數(shù)。
x, y是需判定點與多邊形中一條線段起點的差值，SH是表示點與起點的狀態(tài)，起點在判定點下方時為-1，否則為1；
nx, ny是需判定點與多邊形中一條線段終點的差值，NH是表示點與終點的狀態(tài)，終點在判定點下方時為-1，否則為1；
當多邊形中一條線段起點和終點與指定點狀態(tài)不一致時，即判定點在線段的Y之間才會有相交。
返回值使用了一個位運算來判斷交點個數(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
為了方便大家在移動端也能看到我的博文和討論交流，現(xiàn)已注冊微信公眾號，歡迎大家掃描下方二維碼關注。
