2024-12-05 如何從一串列曲線數值找到最少的控制點的演算法

要從一串曲線數值中找到最少的控制點，可以使用以下演算法來進行擬合和簡化。以下是一般步驟和方法：

這是一個常見的簡化曲線的演算法，以下是 Python 的實現示例：

import numpy as np

def perpendicular_distance(point, start, end):
    """計算點到線段的垂直距離"""
    if np.array_equal(start, end):
        return np.linalg.norm(point - start)
    
    # 計算線段的向量
    line_vec = end - start
    line_len = np.linalg.norm(line_vec)
    line_unit_vec = line_vec / line_len
    
    # 計算點到起點的向量
    point_vec = point - start
    projection_length = np.dot(point_vec, line_unit_vec)
    
    if projection_length < 0:
        closest_point = start
    elif projection_length > line_len:
        closest_point = end
    else:
        closest_point = start + projection_length * line_unit_vec
    
    return np.linalg.norm(point - closest_point)

def ramer_douglas_peucker(points, epsilon):
    """Ramer-Douglas-Peucker 演算法"""
    # 找到最遠的點
    start, end = points[0], points[-1]
    dmax = 0.0
    index = -1
    
    for i in range(1, len(points) - 1):
        d = perpendicular_distance(points[i], start, end)
        if d > dmax:
            index = i
            dmax = d
    
    # 如果最大距離大於 epsilon，則遞歸
    if dmax > epsilon:
        # 遞歸
        left = ramer_douglas_peucker(points[:index+1], epsilon)
        right = ramer_douglas_peucker(points[index:], epsilon)
        
        return np.concatenate((left[:-1], right))  # 去除重複的點
    else:
        return np.array([start, end])

# 示例數據
y_values = [你的曲線數值]  # 替換為你的數據
x_values = np.arange(len(y_values))
points = np.column_stack((x_values, y_values))

# 設定 epsilon 值
epsilon = 0.1  # 調整此值以控制簡化程度

# 簡化曲線
simplified_points = ramer_douglas_peucker(points, epsilon)

# 顯示結果
import matplotlib.pyplot as plt

plt.plot(x_values, y_values, label='原始曲線')
plt.plot(simplified_points[:, 0], simplified_points[:, 1], 'r-', label='簡化曲線')
plt.legend()
plt.show()

perpendicular_distance：計算一個點到線段的垂直距離。

ramer_douglas_peucker：實現 Ramer-Douglas-Peucker 演算法，返回簡化後的控制點。

通過這種方法，你可以有效地從一串曲線數值中提取出最少的控制點。根據你的需求，可以調整 epsilon 參數來控制簡化的程度。

https://zh.wikipedia.org/wiki/%E9%81%93%E6%A0%BC%E6%8B%89%E6%96%AF-%E6%99%AE%E5%85%8B%E7%AE%97%E6%B3%95

拉默-道格拉斯-普克演算法（英語：Ramer–Douglas–Peucker algorithm），又稱道格拉斯-普克演算法（英語：Douglas–Peucker algorithm）和迭代端點擬合算法（英語：iterative end-point fit algorithm），是一種將線段組成的曲線降採樣為點數較少的類似曲線的算法。它是最早成功地用於製圖綜合（英語：cartographic generalization）的算法之一。

起始曲線是一組有序的點或線，距離維度 ε > 0。

該算法遞迴劃分線。最初，它被賦予了第一點和最後一點之間的所有點。它自動標記要保留的第一點和最後一點。然後它找到離以第一點和最後一點為終點的線段最遠的點；這個點顯然是曲線上離終點之間的近似線段最遠的點。如果這個點離線段的距離比 ε 更近，那麼在簡化曲線不比 ε 差的情況下，可以捨棄任何當前沒有標記保留的點。

如果離線段最遠的點大於近似值 ε，那麼該點必須保留。該算法以第一點和最遠點遞迴調用自身，然後以最遠點和最後一點調用自身，其中包括最遠點被標記為保留。

當遞迴完成後，可以生成一條新的輸出曲線，該曲線由所有且僅由那些被標記為保留的點組成。

用道格拉斯-普克算法簡化一條分段線性曲線。

6 person(s) visited this page until now.

Back