比较两条路径的相似性

Question

我有路径集 A 和路径集 B。我试图找到一种算法来比较两个路径集的相似性。

路径特性：

1. 路径集是一条或多条线，每条线有两个或多个点。不必连接线路。
2. 路径集可能会自身重叠（即 X）。
3. 路径集可能包含不同数量的顶点（即一条路径可能看起来与另一条相似，但其中包含更多点）。
4. 不能保证点对于两个路径集都是有序的。

应该考虑比例，即一个小的 X 应该匹配一个大的 X。对于任何路径都不需要考虑平移，因为任何路径的最底部点的 y 将为 0，任何路径的最左边点将x 为 0。

是否有最佳实践或众所周知的算法（我在 Google 搜索中几乎没有发现）来比较这些类型的路径集的相似性？

Answer 1

从算法上来说，我想我会尝试这样的事情：

1. 对于每条路径，将构成该路径的连续点对转换为向量列表，其中向量定义为大小（长度）和方向（相对于 X 轴的角度）的配对。您可以像这样计算这些值 (C#)：

   double dx = endPoint.X - startPoint.X;
   double dy = endPoint.Y - startPoint.Y;
   double magnitude = Math.Sqrt((dx * dx) + (dy * dy));
   double direction = Math.Atan2(dy, dx) * (180 / Math.PI);
   

2. 接下来，通过组合具有相同方向的连续向量来“标准化”每个向量序列。换句话说，用具有相同方向及其幅值总和的新向量替换它们。这将处理路径上任意位置的同一条线上有两个以上点的情况。在此步骤之后，每个序列中应该具有相同数量的向量。（如果不是，则路径不相似。）

3. 计算出比例因子。取第一个序列中第一个向量的大小，并将其除以第二个序列中第一个向量的大小。

4. 现在，您可以通过串联迭代两个序列来比较序列的相似性。对于每个序列中的每个对应向量，检查它们的方向是否相等*以及它们的大小之比是否等于缩放因子。如果不是，则路径不相似。

*在检查两个双精度值是否“相等”时，必须记住，并非每个实数都可以用双精度值准确表示，因此您不能直接比较两个双精度值并期望得到准确的结果。相反，您应该决定适合您情况的误差容限，并确定您正在比较的值之间的差异是否在该容差范围内。请参阅浮点数和双精度比较最有效的方法是什么？用于对主题进行广泛的治疗。