一尘不染

计算轨迹(路径)中的转折点/枢轴点

algorithm

我正在尝试提出一种算法,该算法将确定x / y坐标轨迹中的转折点。下图说明了我的意思:绿色表示
轨迹的起点,红色表示轨迹的终点(整个轨迹由〜1500点组成):

在下图中,我手动添加了算法可能返回的可能的(全局)转折点

显然,真正的转折点总是有争议的,并且将取决于
人们指定的转折点之间的角度。此外,
可以在全局范围内定义转折点(我尝试对黑
圈进行操作),但也可以在高分辨率局部范围内定义转折点。我
对全球(总体)方向变化很感兴趣,但是我很乐意看到
关于将用来挑逗
全球解决方案与本地解决方案的不同方法的讨论。

到目前为止,我已经尝试过:

  • 计算后续点之间的距离
  • 计算后续点之间的角度
  • 看看后续点之间的距离/角度如何变化
    不幸的是,这并没有给我任何可靠的结果。我可能也已经
    计算了多个点的曲率,但这只是一个想法。我
    真的很感激任何可能对我有帮助的算法/想法。该代码可以
    使用任何编程语言,最好是matlab或python。

编辑以下是原始数据(以防有人要玩):

垫文件
文本文件 (x坐标在第一行,y坐标在第二行)


阅读 924

收藏
2020-07-28

共1个答案

一尘不染

您可以使用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)。

2020-07-28