去除冗余GPS点的压缩算法
Compression algorithm to remove redundant GPS points
我有一组longitude/latitude数据，每秒记录一次，想要一个可以去除多余坐标点的算法
因此，例如，如果 driver 沿直线行驶，则无需每秒跟踪一次坐标，但可能仅每半分钟一次。或者如果 driver 正在转弯，而不是在转弯中有 10 个坐标，如果我可以有 5 个坐标并且仍然精确地显示转弯。
如果您只收集纬度和经度（即没有时间或速度信息）and/or您不太关心准确性（即您可以接受实际路线的一些近似值）然后确定'redundant'分应该不是问题。
一种简单的方法是简单地遍历路线的点（按照 driver 通过它们的顺序）并为每个点 Xi 计算 [=10= 之间的距离] 和段 [Xi-1, Xi+1] 检查此距离是否小于阈值 T，其中 T 取决于您的近似值的准确度。如果距离足够小，您可以得出结论 Xi 是多余的，然后将其删除（或将其标记为删除）。
上述方法有很多变体。一个明显的方法是根据线段的长度 [Xi-1, Xi+1] and/or 点 Xi 在该线段上的投影位置来改变 T。您可能希望消除 Xi 仅当它位于以线段 [Xi-1, Xi+1] 为长对角线的细长菱形中时。
您可能不必删除积分。按原样发送第一个点，然后将每个后续点作为与前一个点的 差异 发送。为数据设置精度，使纬度和经度为整数。使用对小增量占用更少位的编码方案。根据您的精度，很多时候差异可能是 (0,0)。那么当变化不大的时候，用很少的比特来表示。较大的更改将需要更多位。您需要一些示例数据来获取编码方案的统计信息。
我正在使用一种算法，其中对于路线的（几乎）直线只存储线的起点和终点，而对于曲线每个点都存储。
诀窍是跟踪与直线的小偏差，并用新点替换直线的当前端点，只要直线保持足够直，并尽快开始一条新直线因为前面的点之一会偏离直线太多。
因此我的算法如下：
开始时，前两点被视为直线的起点。所以我存储了线的起点和终点，我正在计算这条线左右两侧的角度，这将导致一条线，其中当前端点的允许距离为 2 米。
这意味着如果下一个点位于由这两个角度定义的圆锥内，我可以用新点替换前一个端点，因为前一个点将偏离直线最多 2 米。
此外，新线再次定义了一个圆锥体，它必须与先前的圆锥体相交，因此它越来越窄。只要有一个新点在这个圆锥体内部，我确信之前的所有点的最大偏差为 2 米。
一旦一个位于圆锥体之外的点进入，前一个点 "closes" 线和一条由前一个点和新点组成的新线开始。
优点是，该算法在录制过程中以增量方式工作。您不需要先存储这些点，然后再平滑它们。您需要保留的唯一附加信息是锥体的当前张角。
我有一组longitude/latitude数据，每秒记录一次，想要一个可以去除多余坐标点的算法
因此，例如，如果 driver 沿直线行驶，则无需每秒跟踪一次坐标，但可能仅每半分钟一次。或者如果 driver 正在转弯，而不是在转弯中有 10 个坐标，如果我可以有 5 个坐标并且仍然精确地显示转弯。
如果您只收集纬度和经度（即没有时间或速度信息）and/or您不太关心准确性（即您可以接受实际路线的一些近似值）然后确定'redundant'分应该不是问题。
一种简单的方法是简单地遍历路线的点（按照 driver 通过它们的顺序）并为每个点 Xi 计算 [=10= 之间的距离] 和段 [Xi-1, Xi+1] 检查此距离是否小于阈值 T，其中 T 取决于您的近似值的准确度。如果距离足够小，您可以得出结论 Xi 是多余的，然后将其删除（或将其标记为删除）。
上述方法有很多变体。一个明显的方法是根据线段的长度 [Xi-1, Xi+1] and/or 点 Xi 在该线段上的投影位置来改变 T。您可能希望消除 Xi 仅当它位于以线段 [Xi-1, Xi+1] 为长对角线的细长菱形中时。
您可能不必删除积分。按原样发送第一个点，然后将每个后续点作为与前一个点的 差异 发送。为数据设置精度，使纬度和经度为整数。使用对小增量占用更少位的编码方案。根据您的精度，很多时候差异可能是 (0,0)。那么当变化不大的时候，用很少的比特来表示。较大的更改将需要更多位。您需要一些示例数据来获取编码方案的统计信息。
我正在使用一种算法，其中对于路线的（几乎）直线只存储线的起点和终点，而对于曲线每个点都存储。
诀窍是跟踪与直线的小偏差，并用新点替换直线的当前端点，只要直线保持足够直，并尽快开始一条新直线因为前面的点之一会偏离直线太多。
因此我的算法如下：
开始时，前两点被视为直线的起点。所以我存储了线的起点和终点，我正在计算这条线左右两侧的角度，这将导致一条线，其中当前端点的允许距离为 2 米。 这意味着如果下一个点位于由这两个角度定义的圆锥内，我可以用新点替换前一个端点，因为前一个点将偏离直线最多 2 米。 此外，新线再次定义了一个圆锥体，它必须与先前的圆锥体相交，因此它越来越窄。只要有一个新点在这个圆锥体内部，我确信之前的所有点的最大偏差为 2 米。 一旦一个位于圆锥体之外的点进入，前一个点 "closes" 线和一条由前一个点和新点组成的新线开始。
优点是，该算法在录制过程中以增量方式工作。您不需要先存储这些点，然后再平滑它们。您需要保留的唯一附加信息是锥体的当前张角。