logo标签列表

设计一个算法来匹配轨迹？

algorithmgeometrycomputational-geometry
3

我有一个数据集，格式为（时间戳、纬度、经度）。我将得到n个条目，每个条目的格式为（时间戳、纬度、经度），这是针对一个用户的。

User1:(timestamp1,latitude1,longitude1)....(timestamp_n,latitude_n,longitude_n)

现在假设我们有100个用户，每个用户都有一组点（时间戳，纬度，经度）。
我想知道哪些用户可能有匹配的轨迹。匹配的轨迹应该是相同的路线，因此在给定的时间戳集中，纬度和经度应该是相同或足够接近，时间戳应该相同或足够接近，时间戳可以接受30秒左右，而空间距离可以接受200米左右。我可以通过蛮力方法来解决这个问题，但我正在寻求更好的解决方案。
你能具体说明一下什么是“匹配轨迹”吗？你是指给定用户最后两个时间点确定的方向吗？还是一些更长期的时间平均值？ - lurker
在这种情况下，时间戳也必须匹配吗？ - SirGuy
问题太模糊了，请更具体一些。 - Timothy Shields
2个回答
1
这与算法是否仍然是暴力算法无关。
我想在这里介绍的是如何测量两条路径之间的差异。我认为精确定义如何量化这种差异将非常重要。如果您想要更快的东西，那么您可能可以稍后近似计算这个量。
好的，我认为两条路径之间的差异是：
The average distance between 2 users over time.

你应该能够在给定的两个数据点之间进行插值，以找出用户在任何给定时间的位置。只使用线性插值可能就足够了。
当我说随时间平均时，我们会将时间离散化，以便更容易计算。假设：
The average distance between 2 users every 10 seconds period.

编辑：上述建议假设您关心“时间”。 因为您提到了时间戳等。 如果您不关心它，您在问题中就不应该放入它。

无论如何，我有点想象您可能只想查看路径本身。 在这种情况下，您仍然可以使用上述路径差异的定义 只需忽略实际时间戳，并想象用户在路径开头同时开始。 旅行速度可以以各种方式设置...例如使两个用户在相同时间内完成路径，无论一条路径是否比另一条路径更长，或者只让两者以相同速度行驶。

总之，这归结为定义您要如何测量路径差异。 您需要在问题中提供更多详细信息。

1
你可以使用 k-dtree 或 范围树 来索引你的数据。这将使你能够高效地对数据的所有三个维度执行范围查询。
你的意思是分别为时间戳、纬度和经度各有一个3kd树？ - gizgok
@gizgok 没错。也许有一种方法可以只用一棵树来完成这个任务，但我现在想不出来。 - Zim-Zam O'Pootertoot
@gizgok 我忘了你可以实现多维kd树或范围树；请看我的修订答案。 - Zim-Zam O'Pootertoot
O'Pootertot，你知道有没有实现多维部分的kd树吗？ - gizgok
@gizgok 对不起，我把kd-tree和区间树弄混了。一个kd-tree已经考虑到你有高维度的数据（在这种情况下是三维数据），所以你应该能够直接使用任何kd-tree实现。 - Zim-Zam O'Pootertoot
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接