問題說明

實際操作中，發現有的多邊形存在“尾巴”或者很細的部分。“尾巴”細長，明顯不是有效建筑物區域，特點就是區域面積小，看起來細長，附著于大面積多邊形外測或者連接兩個多邊形。

需要去除尾巴或者分割多邊形，為后面擬合多邊形做準備。

算法思想

去除“尾巴”（凸出部分）和分割多邊形的算法思想：

1.求平均距離。

針對環，遍歷每個點，求到下一個點之間的距離，計算該環兩點間的平均距離L，為之后設定閾值做準備。 ??

具體做法：每個polyline（環）添加計算平均距離的函數calAvgDis，添加平均距離成員變量avgDis,在構造函數中調用calAvgDis函數初始化avgDis。

2.設定判斷兩點的距離閾值和下標閾值。

即存在兩個點下標差超過閾值，距離差小于閾值，若兩點與其之間的點構成的環面積小于閾值，則說明“尾巴”存在；若大于閾值，則說明多邊形應該分割。

此處下標閾值設定為10，距離閾值設定為3個avgDis,面積閾值設定為固定值，具體效果和參數的改變要根據實際效果改變。

3.遍歷環上的沒點，找到最符合條件的兩點。

計算每點到其他點的距離，針對每個點來說，遍歷的起點是本點閾值+下標閾值。

當出現距離小于閾值時，記錄下標號，得到（本點下標，距離小于閾值點的下標）的下標對。

每個點可能有不同的下標對，每個環可能有不同的疑似點及其下標對。

如何找到最合理的兩點，遍歷這些下標對：1）首先找下標號差距最大；2）相同的情況下距離最小的；

4.找到兩點后：1）針對“尾巴”（面積小于閾值），消除兩個點之間的點，得到除去尾巴的多邊形。2）針對面積大于閾值的，分割多邊形。

5.循環操作，直至某一次操作前后環的點個數一致。

?

實際操作

1.設置 距離閾值 和 下標差閾值，實際數值根據要求進行設置

int firstNum = circles[i]->pts.size(); //操作前點數 int lastNum = 0; //操作后點數 初始為0 int t = circles[i]->pointDisThreshold; //下標差閾值 double length = circles[i]->calAvgDis(circles[i]->pts); //距離閾值

2.針對環的每一個點，求與之距離超出閾值，下標差超過閾值且差值最大的點，形成一個點與另一個點的關系對（J和K），遍歷所有的關系對，找到最合適的一個關系對（因為每次只刪除一個尾巴）

while( count<1 && firstNum!=lastNum ){firstNum = circles[i]->pts.size();int num = circles[i]->pts.size()-1; //環的點數(去除尾點)int finalJ = 0, finalK = 0, FinalDis = 0, finalType = 0; //最后J,K,類型if(num > t) { //環的總點數大于點數差閾值時//找到所有環中下標差最大的兩點for(int j = 0 ; j < (num - t); j++){ //遍歷環的每個點，int tempDis = 0, tempk = 0, temptype = 0;for(int k = (j + t) ; k<num && (j+num-k)>=t ; k++) { //針對每一個點，計算該點與符合要求的點的距離，找到下標差最大的另一個點,int dis = (j+num-k)>=(k-j)?(k-j):(j+num-k); //取小的int type = (j+num-k)>=(k-j)?1:2; // 1代表順序，2代表非順序if( (calDis(circles[i]->pts[j],circles[i]->pts[k])<(length*3)) && (tempDis<dis) ){ //尋找下標差最大tempDis = dis;tempk = k;temptype = type;}}if( FinalDis<=tempDis ){FinalDis = tempDis;finalJ = j;finalK = tempk;finalType = temptype;}} }

3.刪除尾巴或者分割多邊形

實驗效果

? ? ? ? ? ??

總結

由于本算法自己原創，實際問題又非常復雜，所以效果并沒有很理想，后期還有優化。實際操作中，部分尾巴去不掉，算法也耗時，這表明這種方法并不是一個很成熟的算法。而且由于數據的復雜性，考慮的問題很多。比如有的最理想的點對中，一個在環首附近的位置，另一個在環尾附近位置，需要考慮不同的取舍辦法，等等。

該算法以后需要進一步考慮和優化。

?

轉載于:https://www.cnblogs.com/fan-0802-WHU/p/9748689.html

總結

以上是生活随笔為你收集整理的（四）建筑物多边形化简系统——“去尾巴”和分割复杂多边形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。