根据步行速度在 2 个 GPS 位置之间进行插值

Question

问题：

给定两个位置：

L₁ = (纬度₁,经度₁,时间戳₁), L₂ = (纬度₂ , 经度₂, 时间戳₂),

和一个可配置但恒定的移动速度：

v = 1.39 米每秒（例如）。

我们如何在这两个位置之间进行插值以估计用户从 L₁ 到 的位置L₂?

我一直在寻找这个问题的解决方案，到目前为止我发现，对于小距离（远离极点）可以使用线性插值。所以，我在维基百科上查找 linear interpolation 并发现：

// Imprecise method which does not guarantee v = v1 when t = 1,
// due to floating-point arithmetic error.
float lerp(float v0, float v1, float t) {
    return v0 + t*(v1-v0);
}

所以我正在考虑使用这个 lerp 函数在 L₁ 和 L[ 之间插入纬度和经度₂。那是容易的部分。如何计算 t？我猜我必须计算一些时间增量，但我如何考虑移动速度？

编辑：

我正在测试各种收集 GPS 位置的方法。为此，我在整个步行过程中记录路标位置。我需要使用移动速度在这些 waypoints 之间进行插值，以估计我在步行过程中的位置。然后我可以将我的结果与估计值进行比较，看看它们的表现如何。

示例：

Answer 1

仔细看看Calculate distance, bearing and more between Latitude/Longitude points

它包含几个公式和 Java可能对您有所帮助的脚本示例。我知道它不是 Java，但它应该足够简单以移植代码。特别给出公式的详细说明

编辑：

虽然对于较短的距离使用线性插值似乎没问题，但实际上可能会很不合适，尤其是当您靠近两极时。从您在汉堡的示例来看，这已经产生了在几百米之外很明显的效果。请参阅 this answer 以获得很好的解释。

问题：经度 1 度之间的距离因纬度而异。

这是因为地球不是平坦的，而是一个球体——实际上是一个椭球体。因此，二维地图上的直线不是地球上的直线 - 反之亦然。

要解决此问题，可以使用以下方法：

获取起点坐标(L1)到终点坐标(L2)的方位
给定计算出的方位和指定距离，从起始坐标 (L1) 沿大圆路径计算新坐标
重复这个过程，但使用新计算的坐标作为起始坐标

我们可以创建一些简单的函数来解决问题：

double radius = 6371; // earth's mean radius in km

// Helper function to convert degrees to radians
double DegToRad(double deg) {
    return (deg * Math.PI / 180);
}

// Helper function to convert radians to degrees
double RadToDeg(double rad) {
    return (rad * 180 / Math.PI);
}

// Calculate the (initial) bearing between two points, in degrees
double CalculateBearing(Location startPoint, Location endPoint) {
    double lat1 = DegToRad(startPoint.latitude);
    double lat2 = DegToRad(endPoint.latitude);
    double deltaLon = DegToRad(endPoint.longitude - startPoint.longitude);

    double y = Math.sin(deltaLon) * Math.cos(lat2);
    double x = Math.cos(lat1) * Math.sin(lat2) - Math.sin(lat1) * Math.cos(lat2) * Math.cos(deltaLon);
    double bearing = Math.atan2(y, x);

    // since atan2 returns a value between -180 and +180, we need to convert it to 0 - 360 degrees
    return (RadToDeg(bearing) + 360) % 360;
}

// Calculate the destination point from given point having travelled the given distance (in km), on the given initial bearing (bearing may vary before destination is reached)
Location CalculateDestinationLocation(Location point, double bearing, double distance) {

    distance = distance / radius; // convert to angular distance in radians
    bearing = DegToRad(bearing); // convert bearing in degrees to radians

    double lat1 = DegToRad(point.latitude);
    double lon1 = DegToRad(point.longitude);

    double lat2 = Math.asin(Math.sin(lat1) * Math.cos(distance) + Math.cos(lat1) * Math.sin(distance) * Math.cos(bearing));
    double lon2 = lon1 + Math.atan2(Math.sin(bearing) * Math.sin(distance) * Math.cos(lat1), Math.cos(distance) - Math.sin(lat1) * Math.sin(lat2));
    lon2 = (lon2 + 3 * Math.PI) % (2 * Math.PI) - Math.PI; // normalize to -180 - + 180 degrees

    return new Location(RadToDeg(lat2), RadToDeg(lon2));
}

// Calculate the distance between two points in km
double CalculateDistanceBetweenLocations(Location startPoint, Location endPoint) {

    double lat1 = DegToRad(startPoint.latitude);
    double lon1 = DegToRad(startPoint.longitude);

    double lat2 = DegToRad(endPoint.latitude);
    double lon2 = DegToRad(endPoint.longitude);

    double deltaLat = lat2 - lat1;
    double deltaLon = lon2 - lon1;

    double a = Math.sin(deltaLat / 2) * Math.sin(deltaLat / 2) + Math.cos(lat1) * Math.cos(lat2) * Math.sin(deltaLon / 2) * Math.sin(deltaLon / 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

    return (radius * c);
}

这里使用的平均地球半径为 6371 公里。有关此数字及其准确性的解释，请参阅 Wikipedia。

现在可以计算出两点之间的新中间位置，给定行进距离（以公里为单位）：

double bearing = CalculateBearing(startLocation, endLocation);

Location intermediaryLocation = CalculateDestinationLocation(startLocation, bearing, distanceTravelled);

假设速度为每秒 v（例如 1.39）米，现在可以使用简单的 for 循环来获取相隔 1 秒的点：

List<Location> locations = new ArrayList<Location>();

// assuming duration in full seconds
for (int i = 0; i < duration; i++){
    double bearing = CalculateBearing(startLocation, endLocation);
    double distanceInKm = v / 1000;
    Location intermediaryLocation = CalculateDestinationLocation(startLocation, bearing, distanceInKm);

    // add intermediary location to list
    locations.add(intermediaryLocation);

    // set intermediary location as new starting location
    startLocation = intermediaryLocation;
}

作为额外的奖励，您甚至可以确定在任意两点之间旅行所需的时间：

double distanceBetweenPoints = CalculateDistanceBetweenLocations(startPoint, endPoint) * 1000; // multiply by 1000 to get meters instead of km

double timeRequired = distanceBetweenPoints / v;

与仅使用坐标增量的简单线性插值相比，这将在任何距离上产生更高的精度。虽然这种方法并不完美，但一般会有0.3%或更小的误差，这是可以接受的。如果您需要更好的解决方案，您可能需要研究 Vincenty 公式。

Answer 2

是的。线性插值。

L1 = (1, 2, 3)
L2 = (4, 5, 6)
desired_number_of_interpolation_points = 9
interpolation_points = []

lat_step = (L2[0] - L1[0]) / (desired_number_of_interpolation_points + 1)
lon_step = (L2[1] - L1[1]) / (desired_number_of_interpolation_points + 1)
time_step = (L2[2] - L1[2]) / (desired_number_of_interpolation_points + 1) 

for i in range(1, desired_number_of_interpolation_points + 1)
    interpolation_points.append((lat_step * i, lon_step * i, time_step * i))

Answer 3

I'm guessing I have to calculate some time deltas, but how do I factor in the movement speed?

在线性插值中，在您的案例中，您使用迭代变量 t 在两个时间点之间迭代，迭代变量 t 从开始时间 t1 运行到结束时间 t2，具有预定义的步长。假设 step = 1 秒，这对您的应用程序非常有用。

long t1 = location1.getTimeStamp(); // in milliseconds;
long t2 = location2.getTimeStamp();
double deltaLat = location2.latitude - location1.latitude;
doule deltaLon =  location2.longitude- location1.longtude;
// remove this line if you don't have measured speed:
double deltaSpeed =  location2.speed - location1.speed;

long step = 1 * 1000; // 1 second in millis 
for (long t = t1; t1 < t2; t+= step) {

   // t0_1 shall run from 0.0 to (nearly) 1.0 in that loop
  double t0_1 = (t - t1) / (t2 - t1);
  double latInter = lat1 + deltaLat  * t0_1;
  double lonInter = lon1 + deltaLon  * t0_1;
  // remove the line below if you dont have speed
  double speedInter = speed1 + deltaSpeed  * t0_1;
  Location interPolLocation = new Location(latInter, lonInter, speedInter);
  // add interPolLocation to list or plot.
}

Answer 4

还有一些其他插值策略比线性插值性能更好，包括运动学插值，它将锚点的初始和最终速度作为输入。例如，请参阅最近一篇论文（Long JA (2015) Kinematic interpolation of movement data. Int J Geogr Inf Sci 8816:1–15.doi: 10.1080/13658816.2015.1081909）中的比较：

运动学插值有 R and Python 种实现。写一个Java版本应该很容易。

Answer 5

如果您先将 lat/longs 转换为 n 向量 (https://en.wikipedia.org/wiki/N-vector)，这样的计算实际上非常简单。转换后你可以使用标准插值，你也将避免任何长距离、极点或日期变更线的问题。

如果在维基百科页面上查看"External links"，有一个页面（http://www.navlab.net/nvector/）解决了十个问题，并且该页面上的问题6（插值位置）应该与你的问题。如您所见，该解决方案适用于任何距离，也适用于任何地球位置，例如两极。

根据步行速度在 2 个 GPS 位置之间进行插值

Interpolate between 2 GPS locations based on walking speed

java

algorithm

gps

android

interpolation

问题：

编辑：