GPS抽稀之道格拉斯-普克（Douglas-Peuker)算法

道格拉斯-普克算法是我們常用的一種軌跡點的抽稀算法，抽稀出來的點可以盡可能的維持原先軌跡點的大體輪廓，剔除一些非必要的點。

?

道格拉斯-普克原理

假設在平面坐標系上有一條由N個坐標點組成的曲線，已設定一個閾值epsilon。

（1）首先，將起始點與結束點用直線連接， 再找出到該直線的距離最大，同時又大于閾值epsilon的點并記錄下該點的位置（這里暫且稱其為最大閾值點），如圖所示：

（2）接著，以該點為分界點，將整條曲線分割成兩段(這里暫且稱之為左曲線和右曲線)，將這兩段曲線想象成獨立的曲線然后重復操作（1），找出兩邊的最大閾值點，如圖所示：

（3）最后，重復操作（2）（1）直至再也找不到最大閾值點為止，然后將所有最大閾值點按順序連接起來便可以得到一條更簡化的，更平滑的，與原曲線十分近似的曲線，如圖所示：

?

具體思路

? ? ? ? 對每一條曲線的首末點虛連一條直線，求所有點與直線的距離，并找出最大距離值dmax，用dmax與限差D相比；若dmax < D，這條曲線上的中間點所有舍去；若dmax ≥D，保留dmax 相應的坐標點，并以該點為界，把曲線分為兩部分，對這兩部分反復使用該方法。控制限差值的大小可以控制抽稀的粒度。

?

Matlab代碼實現:

%% 主函數入口（在該函數界面下點擊運行實驗） clc;clear;close all; points(:,1) = 5:5:300; %x值為1到60 points(:,2) = 10 + 3 * rand(60,1); %y為10加一個0到1的隨機數 points(25:35,2) = 5 + 3 * rand(11,1); %其中第25到第35個點低一點 % ========================================================================= [r,c] = size(points); A(1,1) = points(1,1); A(1,2) = points(1,2); A(2,1) = points(r,1); A(2,2) = points(r,2); Threshold = 3; %給定閾值 [A] = ARecursionFun(points,A,Threshold); % 遞歸 A = sortrows(A,1); figure(1); %創建圖層 plot(points(:,1),points(:,2),'-k'); %繪制原始折線 hold on; %保留當前圖層的要素 plot(A(:,1),A(:,2),'*-r'); %在原圖基礎上繪制特征點 title(['閾值為：',num2str(Threshold)]); % 輸入兩個相鄰特征點之間的掃描線pointsTab，特征點表A(A是折線首尾兩個端點) % 輸出補充新發現的特征點后的特征點表A % 函數名稱為ARecursionFun（一個遞歸函數） function [A] = ARecursionFun(pointsTab,A,Threshold) [r,~] = size(pointsTab); % 獲取掃描線片段上點的個數 if r > 2 % 如果這條掃描線片段上點數大于2則執行操作Q1 = [pointsTab(1,1);pointsTab(1,2)]; % 起點坐標對的列向量表示（為了便于點到直線距離計算的表示方法）Q2 = [pointsTab(r,1);pointsTab(r,2)]; % 終點坐標對的列向量表示（作用同上）% 遍歷這個掃描線，依次計算每個點到掃描線起點終點連線的距離==================for i = 1:1:rP = [pointsTab(i,1);pointsTab(i,2)]; % 當前點坐標的列向量表示d(i,1) = abs(det([Q2-Q1,P-Q1]))/norm(Q2-Q1); % 計算點到直線的距離end% 計算完畢，每個點到直線的距離存入列向量d中================================if max(d) > Threshold % 如果距離列向量中最大值大于閾值則進行下述操作ind = find(all(repmat(max(d),size(d,1),1)==d,2)); % 獲取列向量中最大值對應的點的序號[rA,~] = size(A); % 獲取當前特征點表A已存點的個數A(rA+1,1) = pointsTab(ind,1); % 將這個點作為特征點存儲起來（x坐標）A(rA+1,2) = pointsTab(ind,2); % 將這個點作為特征點存儲起來（y坐標）pointsTabb = pointsTab(1:ind,:); % 以剛才存儲的特征點為界限，起點到該點建立新的片段掃描線A = ARecursionFun(pointsTabb,A,Threshold); % 函數自身調用進行遞歸，進一步獲取片段內的特征點pointsTabe = pointsTab(ind:r,:); % 以剛才存儲的特征點為界限，該點到終點建立新的片段掃描線A = ARecursionFun(pointsTabe,A,Threshold); % 函數自身調用進行遞歸，進一步獲取片段內的特征點end end

?

總結

以上是生活随笔為你收集整理的2021-03-20 GPS抽稀之道格拉斯-普克（Douglas-Peuker)算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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