计算轨迹（路径）中的转折点/枢轴点

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在尝试提出一种算法，该算法将确定x / y坐标轨迹中的转折点。下图说明了我的意思：绿色表示

轨迹的起点，红色表示轨迹的终点（整个轨迹由〜1500点组成）：

在下图中，我手动添加了算法可能返回的可能的（全局）转折点

显然，真正的转折点总是有争议的，并且将取决于

人们指定的转折点之间的角度。此外，

可以在全局范围内定义转折点（我尝试对黑

圈进行操作），但也可以在高分辨率局部范围内定义转折点。我

对全球（总体）方向变化很感兴趣，但是我很乐意看到

关于将用来挑逗

全球解决方案与本地解决方案的不同方法的讨论。

到目前为止，我已经尝试过：

  • 计算后续点之间的距离

  • 计算后续点之间的角度

  • 看看后续点之间的距离/角度如何变化

    不幸的是，这并没有给我任何可靠的结果。我可能也已经

    计算了多个点的曲率，但这只是一个想法。我

    真的很感激任何可能对我有帮助的算法/想法。该代码可以

    使用任何编程语言，最好是matlab或python。

编辑以下是原始数据（以防有人要玩）：

垫文件

文本文件 （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）。

以上是 计算轨迹（路径）中的转折点/枢轴点 的全部内容， 来源链接： utcz.com/qa/429975.html

回到顶部