如何在保留原始图形形态的前提下精简坐标点至指定数量？

问题背景 #

我有一个包含250个坐标点的文件，希望将坐标点精简至100个，同时不改变原始数据图形的形状。示例坐标如下：

3.69014,-0.0527779
3.70677,-0.0481951
3.72343,-0.043741
3.74013,-0.0391163
3.75687,-0.0341463
3.77366,-0.0290773
3.7905,-0.0240456
3.80741,-0.0186694
3.82439,-0.0129752
3.84145,-0.00727358
3.8586,-0.00148542
3.87584,0.0047693
3.89318,0.0113316
3.91062,0.0178894
3.92818,0.0246717
3.92818,0.0246717
3.94587,0.0319402
3.96368,0.0395285
3.98164,0.0472058
3.99974,0.0551477
4.018,0.0636555
4.03642,0.0725895
4.05502,0.0814367
4.07381,0.0897025
4.0928,0.0963327
4.112,0.103078
4.13143,0.990615

我用了一段脚本做坐标精简，但它会错误地选择删除点。脚本核心逻辑是计算连续坐标间的斜率，再算斜率差，每次删除斜率差最小对应的点。部分代码如下：

del_points_index = []
data_new = data.copy()
for i in range(data.shape[0]-POINTS_NUMBER):
    del_point = slope_dif_df[0].idxmin()+1
    del_points_index.append(del_point)
    slope_dif_df.drop(del_point-1, inplace=True)
    data_new.drop(index=del_point, inplace=True)

原始图形存在点簇密集的圆角区域，删除100个点时效果还行，但删除130个点时，脚本没有从点簇区删点，反而删掉了稀疏区域的点，导致图形变形。完整脚本如下：

import pandas as pd
import os
import matplotlib.pyplot as plt
POINTS_NUMBER = 100 #how many coordinates to keep
def calculate_slope(x1, y1, x2, y2):
    slope = (y2 - y1) / (x2 - x1)
    return slope
folder = r"defining the path"
files = os.listdir(folder)
plots_folder = os.path.join(folder, "Plots")
os.makedirs(plots_folder, exist_ok=True)

for file in files:
    if file.endswith('.dat'):
        file_path = os.path.join(folder, file)
        data = pd.read_csv(file_path, header=None)
        data = data.apply(pd.to_numeric, errors='coerce')
        slopes = []
        x_values = data.iloc[:, 0]
        y_values = data.iloc[:, 1]
        for i in range(len(x_values)-1):
            x1, y1 = x_values.iloc[i], y_values.iloc[i]
            x2, y2 = x_values.iloc[i + 1], y_values.iloc[i + 1]
            slope = calculate_slope(x1, y1, x2, y2)
            slopes.append(slope)
        differences = [abs(((slopes[i + 1] - slopes[i]) / slopes[i])*100) 
for i in range(len(slopes) - 1)]
        slope_dif_df = pd.DataFrame(differences)
        del_points_index = []
        data_new = data.copy()
        for i in range(data.shape[0]-POINTS_NUMBER):
            del_point = slope_dif_df[0].idxmin()+1
            del_points_index.append(del_point)
            slope_dif_df.drop(del_point-1, inplace=True)
            data_new.drop(index=del_point, inplace=True)
        file_basename = os.path.splitext(file)[0]
        plt.plot(data.iloc[:,0], data.iloc[:,1])
        plt.scatter(data.iloc[:, 0], data.iloc[:, 1], c='b', label='b = original data')
        plt.plot(data_new.iloc[:,0], data_new.iloc[:,1])
        plt.scatter(data_new.iloc[:, 0], data_new.iloc[:, 1], c='r', label='r = reduced data')
        plt.xlabel()
        plt.ylabel()
        plt.legend()
        plot_path = os.path.join(plots_folder, f"{file_basename}_plot.png")
        plt.savefig(plot_path)
        plt.clf()       

现有脚本问题分析 #

当前基于斜率差的贪心删点策略存在两个核心问题：

• 斜率差的相对变化计算（(slopes[i+1]-slopes[i])/slopes[i]）在斜率接近0时会出现数值异常，导致判断逻辑失真；
• 仅考虑局部斜率变化的最小值，没有从整体几何形状的角度判断点的重要性，容易误删稀疏区域的关键转折点，同时保留密集区域的冗余点。

替代方案：道格拉斯-普克算法 #

道格拉斯-普克算法是曲线抽稀的经典算法，核心通过点到直线的垂直距离判断点对图形形状的贡献度，优先保留关键转折点，删除冗余点。

算法核心逻辑 #

1. 连接曲线首尾两点形成直线；
2. 计算所有中间点到该直线的垂直距离；
3. 找出距离最大的点，若该距离超过阈值，则将曲线拆分为该点左右两段，递归处理每一段；
4. 若所有点的距离都小于阈值，则只保留首尾两点。

如果需要固定保留的点数，可以通过二分查找调整阈值，找到刚好保留目标点数的阈值参数。

修改后的完整脚本 #

import pandas as pd
import os
import matplotlib.pyplot as plt
import numpy as np

POINTS_NUMBER = 100  # 要保留的坐标点数量

def perpendicular_distance(point, line_start, line_end):
    """计算点到直线的垂直距离"""
    x0, y0 = point
    x1, y1 = line_start
    x2, y2 = line_end
    numerator = abs((y2 - y1)*x0 - (x2 - x1)*y0 + x2*y1 - y2*x1)
    denominator = np.sqrt((y2 - y1)**2 + (x2 - x1)**2)
    return numerator / denominator

def douglas_peucker(points, epsilon):
    """道格拉斯-普克算法实现"""
    if len(points) <= 2:
        return points
    
    max_dist = 0
    index = 0
    line_start = points[0]
    line_end = points[-1]
    
    for i in range(1, len(points)-1):
        dist = perpendicular_distance(points[i], line_start, line_end)
        if dist > max_dist:
            max_dist = dist
            index = i
    
    if max_dist > epsilon:
        left = douglas_peucker(points[:index+1], epsilon)
        right = douglas_peucker(points[index:], epsilon)
        return left[:-1] + right
    else:
        return [line_start, line_end]

def find_epsilon_for_target_points(points, target_count):
    """二分查找找到刚好保留目标点数的epsilon"""
    left_epsilon = 0
    right_epsilon = np.max(points) - np.min(points)
    
    best_epsilon = right_epsilon
    
    # 迭代50次足够找到精确的阈值
    for _ in range(50):
        mid_epsilon = (left_epsilon + right_epsilon) / 2
        simplified = douglas_peucker(points, mid_epsilon)
        current_count = len(simplified)
        
        if current_count == target_count:
            return mid_epsilon
        elif current_count > target_count:
            left_epsilon = mid_epsilon
        else:
            right_epsilon = mid_epsilon
    
    return mid_epsilon

folder = r"defining the path"
files = os.listdir(folder)
plots_folder = os.path.join(folder, "Plots")
os.makedirs(plots_folder, exist_ok=True)

for file in files:
    if file.endswith('.dat'):
        file_path = os.path.join(folder, file)
        data = pd.read_csv(file_path, header=None)
        data = data.apply(pd.to_numeric, errors='coerce').dropna()
        points = data.values.tolist()
        
        # 获取匹配目标点数的阈值
        epsilon = find_epsilon_for_target_points(points, POINTS_NUMBER)
        simplified_points = douglas_peucker(points, epsilon)
        data_new = pd.DataFrame(simplified_points)
        
        # 绘图
        file_basename = os.path.splitext(file)[0]
        plt.plot(data.iloc[:,0], data.iloc[:,1], label='原始数据')
        plt.scatter(data.iloc[:, 0], data.iloc[:, 1], c='b')
        plt.plot(data_new.iloc[:,0], data_new.iloc[:,1], label='精简后数据')
        plt.scatter(data_new.iloc[:, 0], data_new.iloc[:, 1], c='r')
        plt.xlabel('X坐标')
        plt.ylabel('Y坐标')
        plt.legend()
        plot_path = os.path.join(plots_folder, f"{file_basename}_plot.png")
        plt.savefig(plot_path)
        plt.clf()

方案优势 #

• 基于几何距离判断点的重要性，精准保留图形的关键转折点，避免误删稀疏区域的核心点；
• 通过二分查找可精确控制最终保留的点数；
• 算法逻辑稳定，适配不同密度的点分布，最大程度还原原始图形形状。

内容的提问来源于stack exchange，提问作者krishna vamshi 9573