rdp_algorithm.m

曲线数据压缩是计算机图形学、计算机自动制图和地理信息系统( GIS) 等学科理论与方法研究的一个重要问题,其实质是一个信息压缩问题.RDP 算法是应用最为广泛的一种,由于容易编程实现且压缩结果较好,

function data_new=RDP_algorithm(data,epsilon)
% function: 曲线数据压缩的Ramer-Douglas-Peucker (RDP) 算法
% input: 
%        data: 输入的点序列（x,y）
%        epsilon: 限差,若d_max<epsilon,则删除全部中间点；若大于则保留d_max对应的点
% output:
%        data_new: 删除冗余的点后剩下的点序列

num=size(data,1); % 总样点数
first_data=[];
first_data=[first_data; data(1,:)];  % 第一个点的坐标
last_data=[];
last_data=[last_data; data(num,:)];  % 最后一个点的坐标
loop=0;
while loop<size(first_data,1)
    loop=loop+1;k=0;b=0;
    % 确定第一个点和最后一个点连成的直线方程
    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)); % 计算两点连成的直线方程中的斜率
        b=first_data(loop,2)-k*first_data(loop,1);  % 计算两点连成的直线方程中的截距b
    end
    
    % 计算中间点到直线的距离,找出最大距离和相应的点坐标
    d_max=0;  % 最大的距离,初始化为0
    data_max=first_data(loop,:);  % 最大距离对应的点，初始化为第一个点
    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,则删除全部中间点
            data(low:up,:)=[]; % 后面的坐标作相应变化
            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;