Порядок преобразования матрицы / координат

Question

У меня есть два массива точек:

Point [] original; И Point [] transformed;

Этот преобразованный массив является просто копией оригинала с примененными преобразованиями.Пример:

matrix.Rotate(5f);  
matrix.Scale(.8f, 1.1f);  
matrix.Translate(30f, 18f);  
matrix.TransformPoints(transformed);

• Исходные точки ARE известны.
• Значения преобразования ARE известны.
• Порядок, в котором были применены преобразования, известен как NOT .

Как вычислить / вывести порядок преобразований?

EDIT

• Существует только ОДИН раунд преобразования.
• Раунд может содержать не более трех преобразований, как показано ниже.
• Единственными применяемыми преобразованиями являются любые комбинации при повороте., масштабируйте и переводите.

Чтобы придать ему реальный контекст, подумайте о том, чтобы иметь изображение с известными интересными объектами.Вы распечатываете изображение, сканируете его и пытаетесь прочитать снова.Изображение содержит маркеры ориентации, которые позволяют мне вычислять преобразования, примененные во время процесса сканирования.

Теперь подход с использованием грубой силы будет следующим:

1. Чтение отсканированного изображения.
2. Расчет поворота на отсканированном изображении.
3. Применение поворота на отсканированном изображении.
4. Расчет масштаба на повернутом изображении.
5. Применение масштаба на повернутом изображении.
6. Рассчитать перевод на масштабированном изображении.
7. Применить перевод на масштабированном изображении.

Теперь вы можете прочитать интересующие точки из обработанного изображения, используя исходные точки какесли бы не было никакого преобразования.Конечно, этот метод дорогой.Изображение объемом 500 МБ должно иметь как минимум две копии в памяти за раз и должно быть преобразовано с использованием графического объекта.

Суть этого вопроса состояла в том, чтобы прочитать изображение только один раз, рассчитать все преобразования ипримените их к координатам, а не к самому изображению.Используйте преобразованные координаты, чтобы прочитать достопримечательности.Вот здесь и возникает проблема «порядка преобразований». Ниже приведены некоторые очень полезные ответы, и я надеюсь, что это проясняет контекст.

Answer 1

Для числа преобразований, которые вы смотрите на грубую силу, это, вероятно, самый простой подход, а не пытаться делать какой-либо математический анализ вещей (я не уверен на 100%, если это вообще возможно, но это будет очень сложно).

Для трех различных преобразований (A, B, C) у вас есть шесть различных способов их применения.Это:

• ABC
• ACB
• BAC
• BCA
• CAB
• CBA

Таким образом, для каждого из них примените их в указанном порядке к вашему входу и проверьте, соответствует ли конечный продукт вашему выходу.

Если у вас нет одного из конкретных преобразований, тогда у вас останется только два варианта заказа.Это может быть лучше всего решено, просто используя вышеупомянутые шесть вариантов и применяя матрицу тождества (или не-опцию), где отсутствует пропущенное преобразование.Конечно, вам также нужны проверки, чтобы предотвратить дублирование одного и того же порядка преобразования.

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

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

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

После небольшого обсуждения того, является ли определенный перевод коммутативным или нет (например, выполняет ли A, а затем B то же, что иделаю б то а) я считаю что их нет.В особом случае, когда масштабирование X и Y равно, тогда масштабирование и вращение являются коммутативными, но используемый здесь синтаксис предполагает, что масштабирование имеет два фактора, которые, как я полагаю, являются масштабными коэффициентами X и Y.Это означает, что в этом случае масштабирование и вращение не являются коммутативными.Переводы никогда не бывают коммутативными (представьте себе тривиальный случай, когда перевод переместит точку в начало координат, и вы увидите, что это имеет значение).

Точка Ноктурна (в комментариях) о коммутативности действительно применима, хотя, если масштабто же самое по осям X и Y.Это означает, что если у вас есть такой масштаб, и он находится рядом с вращением, то вы получите два возможных заказа трансформации, которые действительны.Не будет никакой возможности различить эти два.

Answer 2

в CG довольно часто держать матрицу Stack, т.е. каждый раз, когда вы выполняете операцию над матрицей (преобразование, поворот или масштабирование), вы помещаете новую матрицу в стек.Таким образом, вы можете вернуться к исходному состоянию.