我正在尝试提出一种算法,该算法将确定x / y坐标轨迹中的转折点。下图说明了我的意思:绿色表示 轨迹的起点,红色表示轨迹的终点(整个轨迹由〜1500点组成):
在下图中,我手动添加了算法可能返回的可能的(全局)转折点
显然,真正的转折点总是有争议的,并且将取决于 人们指定的转折点之间的角度。此外, 可以在全局范围内定义转折点(我尝试对黑 圈进行操作),但也可以在高分辨率局部范围内定义转折点。我 对全球(总体)方向变化很感兴趣,但是我很乐意看到 关于将用来挑逗 全球解决方案与本地解决方案的不同方法的讨论。
到目前为止,我已经尝试过:
编辑以下是原始数据(以防有人要玩):
垫文件 文本文件 (x坐标在第一行,y坐标在第二行)
您可以使用Ramer-Douglas-Peucker(RDP) 算法来简化路径。然后,您可以计算沿简化路径的每个线段的方向变化。与方向最大变化相对应的点可以称为转折点:
可以在github上找到RDP算法的Python实现。
import matplotlib.pyplot as plt import numpy as np import os import rdp def angle(dir): """ Returns the angles between vectors. Parameters: dir is a 2D-array of shape (N,M) representing N vectors in M-dimensional space. The return value is a 1D-array of values of shape (N-1,), with each value between 0 and pi. 0 implies the vectors point in the same direction pi/2 implies the vectors are orthogonal pi implies the vectors point in opposite directions """ dir2 = dir[1:] dir1 = dir[:-1] return np.arccos((dir1*dir2).sum(axis=1)/( np.sqrt((dir1**2).sum(axis=1)*(dir2**2).sum(axis=1)))) tolerance = 70 min_angle = np.pi*0.22 filename = os.path.expanduser('~/tmp/bla.data') points = np.genfromtxt(filename).T print(len(points)) x, y = points.T # Use the Ramer-Douglas-Peucker algorithm to simplify the path # http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm # Python implementation: https://github.com/sebleier/RDP/ simplified = np.array(rdp.rdp(points.tolist(), tolerance)) print(len(simplified)) sx, sy = simplified.T # compute the direction vectors on the simplified curve directions = np.diff(simplified, axis=0) theta = angle(directions) # Select the index of the points with the greatest theta # Large theta is associated with greatest change in direction. idx = np.where(theta>min_angle)[0]+1 fig = plt.figure() ax =fig.add_subplot(111) ax.plot(x, y, 'b-', label='original path') ax.plot(sx, sy, 'g--', label='simplified path') ax.plot(sx[idx], sy[idx], 'ro', markersize = 10, label='turning points') ax.invert_yaxis() plt.legend(loc='best') plt.show()
上面使用了两个参数:
RDP算法采用一个参数,tolerance它代表简化路径可以偏离原始路径的最大距离。越大tolerance,简化路径越粗糙。另一个参数是,min_angle它定义了什么是转折点。(我将转折点设为原始路径上的任意点,其简化路径上的进入和离开向量之间的角度大于min_angle)。