我有许多由GPS记录的轨道，在形式上可以用许多线串来形容。

现在，某些记录的轨迹可能是同一路线的记录，但是由于GPS系统的不精确性，这些记录是在不同的场合进行的，并且它们可能以不同的速度行进，所以不会完美匹配，但当人类在地图上查看时仍然看起来足够接近，以确定其实际上与所记录的路线相同。

我想找到一种计算两个线串之间相似度的算法。我想出了一些自行开发的方法来执行此操作，但想知道这是否已经有好的算法来解决。

假设相似的均值表示地图上的相同路径，我们将如何计算相似度？

编辑：对于那些不确定我在说什么的人，请查看此链接以获取什么是行字符串的定义：http://msdn.microsoft.com/zh-cn/library/bb895372.aspx不问字符串。

解决方案

回答

我会根据估计的可能错误在第一行周围添加一个缓冲区，然后确定第二行是否完全适合缓冲区。

回答

要确定"相同路线"，请创建最小化的归一化路径矢量集，计算总功率差，然后将总功率差与质量度量进行比较。

• 将GPS航路点归一化为总路径长度，
• 将路径的向量放在一起，根据每个航路点上的最短向量为每个路径创建一组新的路径向量，
• 计算归一化路径中向量长度加权的每个向量端点之间的总功率差，以及
• 与质量度量进行比较。

视觉上调整差异的功效(以平方差异开头)和质量度量(例如，占总功效差异的百分比)。该算法可对路径匹配以及二进制结果进行连续的质量度量(路径是否相同？)

Paul Tomblin said: I would add a buffer
  around the first line based on the
  estimated probable error, and then
  determine if the second line fits
  entirely within the buffer.

我们可以在比较归一化向量端点时修改算法。我们可以确定是否有任何端点差异超出某个大小(实施Paul的缓冲区思想)，或者，如果端点在"缓冲区"之外，则可以使用该事实忽略该端点差异，从而可以进行比较，而忽略了边沿行程。

回答

我实际上与那个人(亚伦·F)在一起，他说我们可能对Levenshtein距离问题感兴趣(并引用了这个观点)。在我看来，他的回答似乎是迄今为止最好的。

更具体地说，Levenshtein距离(也称为编辑距离)不严格测量每个字符的距离，但允许我们执行插入和删除操作。可以在二次时间内计算出最佳的距离测量算法(如果弦长，则算起来会很慢)，但是计算生物学家对此颇有启发，我们可能会对自己感兴趣。查看BLAST和FASTA。

在问题中，似乎我们正在处理数字字符串之间的差异，并且我们在乎数字。如果我们提供更多信息，我可能会根据需要将我们定向到BLAST / FASTA / etc的正确变体。无论如何，我们都可以考虑根据需要调整BLAST和FASTA。他们很简单。

1：http：//en.wikipedia.org/wiki/Levenshtein_distance，http：//www.nist.gov/dads/HTML/Levenshtein.html

回答

我们可以沿着线串A的每个点(Pa)行走，并测量从Pa到线串B的最近线段的距离，取每个这些距离的平均值。

这不是一个快速或者完美的方法，但是应该能够使用一个有用的数字并且实现起来非常迅速。

线串是在相似的点处开始还是结束，还是程度不同？

回答

计算每对轨道上的Frchet距离。距离可用于评估轨迹的相似性。

数学警报：Frchet是与问题相关的度量空间领域的先驱。

回答

如果我们将单个线串视为[x，y]点(或者[x，y，z]点)的序列，则可以使用Needleman-Wunsch算法计算每对线串之间的相似度。如参考的Wikipedia文章中所述，Needleman-Wunsch算法需要定义两个点之间距离的"相似度矩阵"。但是，使用函数而不是矩阵会很容易。在情况下，我们可以简单地使用2D欧式距离函数(如果点具有高程，则使用3D欧式函数)来提供每对点之间的距离。