function data_new=RDP_algorithm(data,epsilon)
% function: 曲線數(shù)據(jù)壓縮的Ramer-Douglas-Peucker (RDP) 算法
% input: 
%        data: 輸入的點(diǎn)序列（x,y）
%        epsilon: 限差,若d_max<epsilon,則刪除全部中間點(diǎn)；若大于則保留d_max對(duì)應(yīng)的點(diǎn)
% output:
%        data_new: 刪除冗余的點(diǎn)后剩下的點(diǎn)序列

num=size(data,1); % 總樣點(diǎn)數(shù)
first_data=[];
first_data=[first_data; data(1,:)];  % 第一個(gè)點(diǎn)的坐標(biāo)
last_data=[];
last_data=[last_data; data(num,:)];  % 最后一個(gè)點(diǎn)的坐標(biāo)
loop=0;
while loop<size(first_data,1)
    loop=loop+1;k=0;b=0;
    % 確定第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)連成的直線方程
    if first_data(loop,1)<last_data(loop,1)
        k=(first_data(loop,2)-last_data(loop,2))/(first_data(loop,1)-last_data(loop,1)); % 計(jì)算兩點(diǎn)連成的直線方程中的斜率
        b=first_data(loop,2)-k*first_data(loop,1);  % 計(jì)算兩點(diǎn)連成的直線方程中的截距b
    end
    
    % 計(jì)算中間點(diǎn)到直線的距離,找出最大距離和相應(yīng)的點(diǎn)坐標(biāo)
    d_max=0;  % 最大的距離,初始化為0
    data_max=first_data(loop,:);  % 最大距離對(duì)應(yīng)的點(diǎn)，初始化為第一個(gè)點(diǎn)
    low=find(data(:,1)'==first_data(loop,1))+1; 
    up=find(data(:,1)'==last_data(loop,1))-1;
    if low<=up
        for i=low:up
            x=data(i,1);
            y=data(i,2);
            d=abs(k*x-y+b)/sqrt(k^2+1);
            if d>d_max
                d_max=d;
                data_max=data(i,:);
            end
        end
        if d_max<epsilon  % 若d_max<epsilon,則刪除全部中間點(diǎn)
            data(low:up,:)=[]; % 后面的坐標(biāo)作相應(yīng)變化
            end_line=size(first_data,1);
            find_result=find(first_data(loop:end_line,1)'>low);
            point=loop+find_result-1;
            first_data(point,1)=first_data(point,1)-(up-low+1);
            find_result=find(last_data(loop:end_line,1)'>low);
            point=loop+find_result-1;
            last_data(point,1)=last_data(point,1)-(up-low+1);
        else
            first_data=[first_data; first_data(loop,:)];
            first_data=[first_data; data_max];
            last_data=[last_data; data_max];
            last_data=[last_data; last_data(loop,:)];
        end
    end
end

data_new=data;