从GPS坐标记录中计算圈数

Question

我有一个包含大量点（按时间排序的经度和纬度）的GPX文件，如何计算其中包含多少圈？

这个GPS记录了赛车会话期间的数据。

圈数是指车辆通过赛道起点/终点的次数。

- Daniil Harik

---

有很多GPX解析库可供选择。我推荐使用Haskell库，名为“GPX”。 - Thomas M. DuBuisson

你能描述一下你所拥有的数据吗？它是按时间排序的一组点吗？你如何定义一个圈？ - moinudin

感谢您的快速回复，我已经在我的问题中添加了信息 :) - Daniil Harik

Answer 1

假设赛道足够小，我们可以假定所有点都在一个平面内，例如，我们可以忽略地球的曲率。在这种情况下，您可以将所有点转换为平面上的点，例如P(i) = (x(i), y(i))，没有z坐标。

考虑以下算法：找到一个点C = (Cx, Cy)，它位于赛道中间的某个位置，例如，所有点的重心。确切的位置并不重要。然后想象一个观察者站在点C处，始终面向车辆旋转。您需要计算当车辆行驶时观察者旋转了多少次。

为了做到这一点，您需要能够找到观察者在点列表中相邻的两个点P(i)和P(i+1)之间旋转的有符号角度。这与找到向量P(i) - C和P(i+1) - C之间的有符号角度相同，可以使用叉积来完成。由于我们有二维点，因此这特别容易。我们有

P = (x(i) - Cx) * (y(i+1) - Cy) + (x(i+1) - Cx) * (y(i) - Cy)

如果P为正，则观察者逆时针旋转，如果为负则顺时针旋转。观察者旋转的角度为

theta(i, i+1) = arcsin(P / (length(x(i) - C) * length(x(i+1) - C)))

这里我们假设相邻的点彼此靠近，因此观察者在相邻点之间仅旋转了小于pi/2的小角度。

要找到观察者旋转的总量，只需将所有theta从路径开始到结束相加，确保保留theta的符号以防车辆出现倒退情况。假设theta以弧度为单位，则总圈数就是theta之和除以2 * pi。

对于真正的极客来说，这只是使用定义计算车辆绕C路径的绕组数。

- David Norman

---

我正确地得出结论，这个算法假定课程没有在任何地方重复返回吗？ - Chris Cleeland

双倍返回是什么意思？只要航线绕着中心点，它应该是有效的，即使有时theta为负数，因为车辆有时会朝相反的方向行驶。 - David Norman

通过“double-back”，考虑一条沿着“U”形周长的课程。 - Chris Cleeland

这要看情况。你能选一个点在U内部，使得即使存在噪声，内部周长和外部周长始终与该点分离吗？ - David Norman

我打算更仔细地研究你在答案中提供的“绕数”链接，看看是否能够先回答自己的问题。 - Chris Cleeland

Answer 2

这个问题需要一些试错来找到可行的解决方案，因为它很大程度上取决于数据的质量和数据点的数量。

如果数据点以高频率采集，使用线-线相交测试可能已经足够好了。如果由相邻两个数据点形成的直线与赛道终点线相交，则可以将其视为一圈。但是，当数据点之间距离过远时，这种方法可能会失败。除非你的解决方案非常谨慎，否则车辆在终点线外离开赛道也可能导致失败。

更一般的解决方案是将赛道分成两个多边形：每个多边形代表赛道的一半。让它们的覆盖范围包括赛道外。然后使用点在多边形内测试来确定哪些数据点位于赛道的哪一半。然后遍历这些点，并注意当车从一半转移到另一半时。每次第二次转换应该表示一圈。但是，如果车失控旋转并在两半之间振荡而没有完成整个圈数，这种方法也会失败。

您可以通过强制要求在转换之间具有最小数据点来解决此问题。另一个想法是将赛道分成三个多边形，并确保汽车始终向前移动。

- moinudin