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