algorithm - 识别 svg 文档中的修改路径

Question

我有一组固定的(大约一百个)svg 形状，每个包含一个 <path> .想象一下，将任意数量的这些形状放置在新文档的任意位置。然后，我根据需要多次对每个形状应用以下任何操作:

• 旋转
• 镜子(垂直/水平)
• 比例(X/Y)

然后将这些操作呈现到新路径(不使用任何 svg 操作，如 transform 属性)。基本上，它是 adobe illustrator save-as-svg 的输出。

给定一个任意的这样的文件，我想找到一个算法来将它逆向工程成一个形状和操作的列表，比如

1. 造船:位置 (4,5)，旋转 20 度，缩放 x 50% y 100%，镜像 v=yes,h=no
2. 汽车造型:等...

可以使用层 ID 强制文档中的形状以它们各自的“原始”形状命名，但我想尽可能避免这种情况。

我的第一个想法是为形状制作某种散列来识别它们(可以是 x 个散列，每个镜像操作一个)，然后使用形状中的两个引用点来找到旋转。这个的一个版本可以是测量形状中所有点之间距离的绝对值，并将点之间的每个距离除以这个值，以获得唯一的哈希值。虽然 Scale x/y 要求似乎把这个想法搞得一团糟。很遗憾，我不能放弃这个要求。

Answer 1

您对形状所做的操作称为 affine transformation ，你的问题是找到可以通过仿射变换相互映射的形状。假设点的顺序保持不变，这并不难。
仿射变换可以写成线性映射: (1) P'_k = A P_k+b。 P_k 是原始点，写成包含 x 和 y 分量的 2 向量:P_k = (x, y)。 P'_k 是映射点。 A 是一个未知的 2x2 矩阵。 b 是一个 2x1 向量。当且仅当存在 A 和 b 时，两个形状相互对应，这样来自一个形状的点可以使用 (1) 映射到另一个形状的点. A 有 2x2=4 个值，b 有 2 个值，所以它们加在一起有 6 个值。这些值可以通过为至少 3 个点编写上述等式来确定:P'1 = A P1+b； P'2 = A P2+b; P'3 = A P3+b;每一个都是一个二维向量方程，所以这3个向量方程可以写成6个标量方程。这 6 个标量方程构成一个线性方程组，可以求解 A 和 b 的系数。所以一般位置的三个点(即不在一条直线上)就足以确定A和b的元素。当您拥有这些值时，您可以检查其余点是否也适合该 map (1)，如果是这种情况，则形状相互对应。
一种更稳健的方法是为形状中的所有点编写 (1)，结果是 over-determined linear equation system .我不会详细介绍，但你基本上必须找到 least-square solution并检查该解决方案的准确性。如果残差足够低，则形状相互对应。这更稳健，因为您平等对待所有点，而不是选择三个点。