Идентификация измененных путей в документе svg

Question

У меня есть фиксированный набор (вокруг хрустали) форм svg, каждый из которых содержит один <path>. Представьте, что любое количество этих фигур помещается где угодно в новый документ. то я применить любой из следующих операций на каждой форме столько раз, сколько я хочу:

• Поворот
• Зеркало (вертикальное/горизонтальное)
• Scale (X/Y)

Эти операции затем выводятся на новый путь (ни одна из операций svg не используется, как атрибут преобразования). В основном, это результат иллюстратора adobe save-as-svg.

Учитывая произвольный такой документ, я хотел бы найти алгоритм для обратной инженерии это в список форм и операций, таких как

1. Форма лодка: позиция (4,5), вращение 20deg, масштабируются й 50% у 100%, не зеркальный v = Да, Н = нет
2. формы автомобиля: и т.д ...

можно было бы ввести, что формы в документе названы после того, как их соответствующий " оригинальной "формы с использованием идентификатора слоя, но я хотел бы избежать этого, насколько это возможно.

Моя первая мысль заключалась в том, чтобы сделать какой-то хэш для фигур для их идентификации (может быть х хешей, по одному для каждой операции с зеркалом), а затем использовать две опорные точки в форме для поиска вращения. Вариантом этого может быть измерение абсолютного значения всех расстояний между точками в форме и разделение каждого расстояния между точками с этим, чтобы получить уникальный хеш. Хотя потребность в шкале x/y, по-видимому, сильно испортила эту идею. К сожалению, я не могу отказаться от этого требования.

Answer 1

Что вы делаете с фигурами, называется affine transformation, и ваша проблема заключается в том, чтобы найти формы, которые могут быть сопоставлены друг с другом аффинным преобразованием. Предполагая, что порядок точек остается фиксированным, это не слишком сложно.
Аффинное преобразование можно записать в виде линейной карты: (1) P'_k = A P_k+b. P_k - исходная точка, записанная как 2-вектор, содержащий x- и y-компоненты: 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 достаточно трех точек в общем положении (т. Е. Не на прямой). Когда у вас есть эти значения, вы можете проверить, соответствуют ли остальные точки этой карте (1), и если это так, формы соответствуют друг другу.
Более прочный способ - написать (1) для всех точек в форме, в результате получится over-determined linear equation system. Я не буду подробно разбираться в этом, но вам в основном нужно найти least-square solution и проверить точность этого решения.Если остатки достаточно низки, формы соответствуют друг другу. Это более устойчиво, потому что вы относитесь ко всем точкам одинаково, вместо того, чтобы выбирать три очка.