乡下人产国偷v产偷v自拍,国产午夜片在线观看,婷婷成人亚洲综合国产麻豆,久久综合给合久久狠狠狠9

    • <output id="e9wm2"></output>
    <s id="e9wm2"><nobr id="e9wm2"><ins id="e9wm2"></ins></nobr></s> 
    

    • 
    
    
      



    
      
        
      
            
        
      
        
      
    
      
    
      
        
      
        
      
            
            
      
                
      
                    
                
      
                搜索
            
      

            分享
                
            

            
            
            
            
            
            
            
            

            
        
      
    
      
    
      

    
      

    
      
        
      
        
      
        
      
        
      
            
      
                
      
                    
      一種改進(jìn)的道格拉斯
      
                    
                    
                    
                    
      
                         mediatv
                        
                        
                        2021-12-11
                        
                            
                        
                    
      
                    
      
                        
                        
      
                    
      
                    
                    
      
                        
      
                            
                        
      
                        
      
                            
                                
      
                                    
                                        
      

                                        
                                        

                                        
      Douglas一Peukcer算法由D.Douglas和T.Peueker于1973年提出，簡(jiǎn)稱D一P算法，是目前公認(rèn)的線狀要素化簡(jiǎn)經(jīng)典算法?，F(xiàn)有的線化簡(jiǎn)算法中，有相當(dāng)一部分都是在該算法基礎(chǔ)上進(jìn)行改進(jìn)產(chǎn)生的。它的優(yōu)點(diǎn)是具有平移和旋轉(zhuǎn)不變性，給定曲線與閡值后，抽樣結(jié)果一定。本章線化簡(jiǎn)重點(diǎn)講解該算法。
       
 
      算法的基本思路是:對(duì)每一條曲線的首末點(diǎn)虛連一條直線,求所有點(diǎn)與直線的距離,并找出最大距離值dmax ,用dmax與限差D相比:若dmax < D ,這條曲線上的中間點(diǎn)全部舍去;若dmax ≥D ,保留dmax 對(duì)應(yīng)的坐標(biāo)點(diǎn),并以該點(diǎn)為界,把曲線分為兩部分,對(duì)這兩部分重復(fù)使用該方法。
       
 
      算法的詳細(xì)步驟如下:
       
 
      (1) 在曲線首尾兩點(diǎn)間虛連一條直線,求出其余各點(diǎn)到該直線的距離，如圖3（1）。
       
 
      (2) 選其最大者與閾值相比較,若大于閾值,則離該直線距離最大的點(diǎn)保留,否則將直線兩端點(diǎn)間各點(diǎn)全部舍去，如圖3（2），第4點(diǎn)保留。
       
 
      (3) 依據(jù)所保留的點(diǎn),將已知曲線分成兩部分處理,重復(fù)第1、2步操作，迭代操作，即仍選距離最大者與閾值比較,依次取舍,直到無點(diǎn)可舍去，最后得到滿足給定精度限差的曲線點(diǎn)坐標(biāo)，如圖3（3）、（4）依次保留第6點(diǎn)、第7點(diǎn)，舍去其他點(diǎn),即完成線的化簡(jiǎn)。
       
 
       
  
  
  
  
  
 
       
  分類： GIS底層開發(fā)
  2013-10-05 16:46 
  124人閱讀 
  評(píng)論(0) 
  收藏 
  舉報(bào)
 
       
 
       
  
               既然今天有時(shí)間，就多寫幾篇博文算了，也為了明天出去玩好好放松一下。
       
  
              GIS領(lǐng)域的同志都知道，傳統(tǒng)的道格拉斯-普克算法都是遞歸實(shí)現(xiàn)。然而有時(shí)候遞歸的層次太深的話會(huì)出現(xiàn)棧溢出的情況。在此，介紹一種非遞歸的算法。
       
  
              要將遞歸算法改為非遞歸算法，一般情況下分為兩種場(chǎng)景。第一種是問題定義是遞歸的，如階乘、斐波那契數(shù)列等，對(duì)于這類問題，改為遞歸算法很簡(jiǎn)單，直接用迭代來做。另外一種是過程是遞歸的，如本文的道格拉斯-普克算法，對(duì)于這類問題呢，一般是用棧（stack）來記錄中間結(jié)果，最后得到結(jié)果。
       
  
               為了保證極值點(diǎn)的不被舍去，將曲線在彎曲極值點(diǎn)分為兩段處理，彎曲極值點(diǎn)通過中間點(diǎn)與相鄰兩個(gè)頂點(diǎn)的角度度量。然而傳統(tǒng)的Douglas-Peucker算法一般在計(jì)算過程中沒有考慮到記錄中間最大的距離的節(jié)點(diǎn)，造成循環(huán)時(shí)間長(zhǎng)、遞歸嵌套層次太深，從而影響了程序的運(yùn)行效率。本文提出一種結(jié)合棧數(shù)據(jù)結(jié)構(gòu)的分段Douglas-Peucker算法，它從曲線的一端出發(fā)，首先將第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)作為改進(jìn)的Douglas-Peucker算法的工作區(qū)間，然后判斷最遠(yuǎn)點(diǎn)的距離是否大于閾值，這樣完成線要素的綜合化簡(jiǎn)。改進(jìn)D-P算法的具體步驟如下：
       
  
       (1)尋找曲線曲率最大的點(diǎn)，將曲線以此點(diǎn)為界一分為二分成兩部分，對(duì)于每一部分都有點(diǎn)列 。然后分別處理這兩段曲線。
       
  
       (2)對(duì)于第一段曲線，有矢量的離散點(diǎn)序列 ,設(shè) 并且 ，連接 組成一條線段。生成一個(gè)棧 ，將 點(diǎn)入棧 。
       
  
       (3)在 之間的點(diǎn)中尋找與 線段距離最大的點(diǎn)，記為 。
       
  
       (4)判斷 點(diǎn)到 的距離是否小于閾值，若否，則設(shè) ，并將 加入到特征點(diǎn)序列，將 壓入棧 ，用線段連接 ，回到(3)。若是，執(zhí)行第(5)步。
       
  
       (5)判斷 是否等于 的棧頂元素，若否，則設(shè) 、 ， 表示棧頂，用線段連接 ，回到(3)。若是，執(zhí)行(6)。
       
  
       (6)判斷 是否等于 ，若否，則設(shè) 、 ( 表示 的棧頂?shù)南乱稽c(diǎn))，用線段連接 ，棧頂元素出棧，回到(3)。
       
  
       (7)當(dāng)棧為空時(shí)，第一段曲線計(jì)算結(jié)束。處理第二段曲線，重復(fù)(1)～(7)。
       
  
       改進(jìn)算法的程序流程圖如下圖所示。
       
  
                                                                                                                
       
   
  
       圖 改進(jìn)Douglas-Peucker流程圖
       
  
        
       
  
       本文提出的改進(jìn)算法雖然在編程上面比較復(fù)雜，但是能夠減少中間重復(fù)循環(huán)的次數(shù)。有了上面的流程圖之后，那么代碼就相對(duì)簡(jiǎn)單了。
       
  
       
   
       
    
       
     [cpp] 
     view plain
     copy 
      
    
       
   
       
   
      1.  void DouglasPeucker(LineVertex *V,int &i,int &j,double e)  
      2.  {  
      3.      double dist = 9999;  
      4.      int f = 0;          //最大距離的點(diǎn)的序號(hào)  
      5.      stack<int> tempVertex;            //STL實(shí)現(xiàn)的棧  
      6.      tempVertex.push(j);  
      7.    
      8.      do   
      9.      {  
      10.          //循環(huán)i和j之間距離直線ij最大的點(diǎn)  
      11.          FindSplit(*V,i,j,&f,&dist);  
      12.    
      13.          if (dist > e)      //大于閾值  
      14.          {  
      15.              (*V)[f].flag = true;  
      16.    
      17.              j = f;  //更新B值  
      18.    
      19.              tempVertex.push(f);                 //記錄最大距離點(diǎn)，放入棧中存儲(chǔ)  
      20.              continue;  
      21.          }  
      22.    
      23.          else              
      24.          {  
      25.              if (!tempVertex.empty() && j != tempVertex.top())   //判斷后一點(diǎn)是否和當(dāng)前棧頂相等  
      26.              {  
      27.                  i = f;  
      28.                  j = tempVertex.top();  
      29.                  continue;  
      30.              }  
      31.              else  
      32.              {  
      33.                  if (j != V->size())      //判斷最后一個(gè)點(diǎn)是否和當(dāng)前線段的B點(diǎn)重合  
      34.                  {  
      35.                      i = j;  
      36.                      if (!tempVertex.empty())  
      37.                      {  
      38.                          deque<int> cont = tempVertex._Get_container();  
      39.                          if (cont.size() > 1) //棧中至少還有兩個(gè)點(diǎn)  
      40.                          {  
      41.                              j = cont[cont.size()-2];  
      42.                          }  
      43.                          else if (cont.size() == 1)  //棧中只有一個(gè)點(diǎn)  
      44.                          {  
      45.                              j = cont[cont.size()-1];  
      46.                          }  
      47.                          tempVertex.pop();  
      48.                          continue;  
      49.                      }  
      50.                  }  
      51.              }  
      52.          }  
      53.      } while (!tempVertex.empty());  
      54.    
      55.  }  
       
  
       
  
        
       
  
       代碼不是完整的，其中有調(diào)用到了另外一個(gè)函數(shù)，就是找曲線中離曲線兩端點(diǎn)的直線的距離的最大值點(diǎn)，這個(gè)過程很簡(jiǎn)單，就不講了，還有自己定義的一些數(shù)據(jù)結(jié)構(gòu)，本文只是講解這一種算法的思想，其中算法描述部分由公式，原文是在word中編輯的，如果看不懂就直接看流程圖還清晰點(diǎn)。
       
 
       
 
      
                                          		
                                
      
                                  
                        
      
                    
      



                
      
                
      
                    
                    
                        
      
                            
                                
        
                                    		
                        
        
                            
                
        
                
        
                
                
                
        
                
        


                

                
        本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。
        
                
                

                
        
                    轉(zhuǎn)藏
                    
                    
                    
                    
                    
                    
                        分享
                        
                        
                    
                    獻(xiàn)花（0）
                            
                
        
                
                
                
        
                    
        
                        
                        
                    
        
                
        

            
        

            
        

            
        
                
                
                
        
                
        
                    
        
                        
        0條評(píng)論
        
                        
                        
                        
        
                            
                            
        
                                發(fā)表
                            
        
                        
        
                        
                    
        
                    
                    
        請(qǐng)遵守用戶 評(píng)論公約
        
                    
                    
          
                    
        
                    
        
                    
        
                    
                
        
               
                
        
                    
        
                        類似文章
                        更多