Identifying modified paths in svg document

Question

I have a fixed set (around a hundered) of svg shapes, each containing a single <path>. Imagine that any number of these shapes are placed anywhere into a new document. I then apply any of the following operations on each shape as many times as I want:

• Rotate
• Mirror (vertical/horizontal)
• Scale (X/Y)

These operations are then rendered to a new path (none of the svg operations are used, like the transform attribute). Basically, it's the output of an adobe illustrator save-as-svg.

Given an arbitrary such document, I would like to find an algorithm for reverse-engineering this into a list of Shapes and operations, like

1. Shape Boat: Position (4,5), Rotation 20deg, scaled x 50% y 100%, mirrored v=yes,h=no
2. Shape Car: etc...

It would be possible to impose that the shapes in the document are named after their respective "original" shape using layer id's, but I would like to avoid that as far as it's possible.

My first thought was to make some kind of a hash for shapes to identify them (could be x hashes, one for each mirror operation) and then use two reference points in the shape to find the rotation. An version of this could be to measure the absolute value of all distances between points in the shape and divide each distance between points with this, to get a unique hash. Though the Scale x/y requirement seems to mess this idea up pretty badly. Unfortunately I cannot drop this requirement.

Answer 1

What you are doing to the shapes is called affine transformation, and your problem is to find shapes that can be mapped to each other by an affine transformation. Assuming the order of the points remains fixed this is not too hard.
An affine transformation can be written as a linear map: (1) P'_k = A P_k+b. P_k is the original point, written as 2-vector containing the x- and y- components: P_k = (x, y). P'_k is the mapped point. A is an unknown 2x2 Matrix. b is a 2x1 vector. Two shapes correspond to each other if and only if there exist A and b so that the points from one shape can be mapped to the points of the other shape using (1). A has 2x2=4 values, b has 2 values, so together they have 6 values. Those values can be determined by writing the above equation for at least 3 Points: P'1 = A P1+b; P'2 = A P2+b; P'3 = A P3+b; Each is a two-dimensional vector equation, so those 3 vector equations can be written as 6 scalar equation. Those 6 scalar equations form a linear equation system that can be solved for the coefficients of A and b. So three points in general position (i.e. not on a straight line) are sufficient to determine the elements of A and b. When you have those values, you can check if the remaining points fit that map (1) as well, and if this is the case, the shapes correspond to each other.
A more robust way is to write (1) for all points in the shape, resulting in an over-determined linear equation system. I won't get into the details of that, but you basically have to find the least-square solution to that and check the accuracy of that solution. If the residuals are sufficiently low, the shapes correspond to each other. This is more robust because you treat all points equally, instead of picking three points.