矩阵/坐标转换顺序

Question

矩阵/坐标转换顺序

3

我有两个点数组：

Point [] original; 和 Point [] transformed;

这个被转换的数组是原数组应用变换后的副本。例如：

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

原始点是已知的。
转换值是已知的。
应用变换的顺序是不确定的。

如何计算/推断变换的顺序？

编辑

只有一个转换回合。
一回合最多包含三个变换，如下所示。
唯一应用的变换是旋转、缩放和平移的任意组合。

为了给它一些现实世界的背景，考虑拥有一个已知兴趣点的图像。你打印图像、扫描它并试图再次读取它。图像包含方向标记，允许我在扫描过程中计算应用的变换。

现在，一种暴力的方法是：

读取扫描的图像。
计算扫描图像上的旋转。
在扫描的图像上应用旋转。
在旋转后的图像上计算比例。
在缩放后的图像上应用比例。
在缩放后的图像上计算翻译。
在缩放后的图像上应用翻译。

现在，你可以使用原始点从处理过的图像中读取感兴趣的点，就好像没有进行任何变换一样。当然，这种方法是昂贵的。一个500MB的图像需要同时存在于内存中至少两个副本，并且必须使用图形对象进行转换。

这个问题的前提是只读取一次图像，计算所有变换并将它们应用于坐标而不是图像本身。然后使用转换后的坐标来读取感兴趣的点。这就是“变换的顺序”的问题所在。下面有一些非常有用的答案，我希望这澄清了背景。

- Raheel Khan

1

你有多少个变换？我认为，除非它们非常多，否则暴力方法将是最简单和最好的方法。如果你有很多变换，我认为你可能仍然需要一种暴力方法，而不是对事物进行复杂的分析...此外，你不能保证找到唯一的解决方案（例如，连续两次翻译可能会被颠倒）。 - Chris

1

@Musefan：这并不适用于翻译。想象一下，你的第一个点是0,1，你的两个变换是沿着0,-1平移和绕原点旋转180度。显然，在旋转之前进行平移非常重要。同样的论点也适用于缩放。 - Chris

@Chris：你说得对，我曾经假设原点相对于物体（比如说中心点）……鉴于上下文，我承认这可能不是最好的假设。;) - musefan

@Chris：只会有一轮变换，可能包括旋转、缩放和平移。原始点已知，变换后的点也已知，甚至变换值也已知！即使是暴力方法也不应该很昂贵。我只是因为不熟悉而感到困难。 - Raheel Khan

@Nocturn：不是代码，但我已经编辑了问题，以便您可以获得确切的上下文。那应该能澄清问题。此外，请查看我对Chris答案的最后评论。 - Raheel Khan

显示剩余4条评论

2个回答

0

在计算机图形学中，保持一个矩阵栈是非常常见的。也就是说，每次对矩阵执行操作（如变换、旋转或缩放）时，将新的矩阵放入堆栈中。这样，您就可以回溯到原始状态。

- Shai

当然，边记录边进行是了解顺序的好方法，但我假设在这种情况下这不是一个选项，因为这会使问题变得琐碎。虽然当然，他为什么拥有他所拥有的信息而不知道顺序是另一回事。 :) - Chris

那当然是另一回事 :). 你可以在这里查看参考资料：http://stackoverflow.com/questions/8815223/matrix-coordinate-transformation-in-c-sharp。我不想混淆问题并使它们变得复杂。我无法控制它们被应用的顺序。 - Raheel Khan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chris · Accepted Answer

对于你所寻找的变换次数，暴力破解可能是最简单的方法，而不是尝试对事物进行任何数学分析（我不确定是否可能，但这将非常困难）。

对于三个不同的变换（A、B、C），你有六种不同的应用方式。它们是：

ABC
ACB
BAC
BCA
CAB
CBA

因此，对于每个变换，按照该顺序将其应用于输入，并检查最终产品是否与输出匹配。

如果你没有其中一个特定的变换，则只剩下两个顺序选项。这可能最好通过使用上述六个选项并在缺少变换的位置应用恒等矩阵（或无操作）来处理。当然，你还需要检查以防止重复相同的变换顺序。

为了获得最佳性能，您不一定需要检查数组中的所有点 - 如果第一个点不匹配，则无需再检查。当然，您肯定希望检查数组中的所有点以查找任何匹配项，以确保第一个点转换有效并非仅仅是偶然。此外，您可以检查微不足道的变换（例如按比例缩放1倍），并将它们视为不存在，因为它们可能出现在任何位置，所以您可以假设它们位于开头（或结尾或中间 - 个人喜好）。

最后，仍然存在歧义的可能性。虽然这不太可能，并且即使只有少量输入点，也变得非常不可能。但这是您需要注意的一点。另请参见下面关于特殊情况的讨论，其中歧义变得更加可能。

我希望这足以让您朝着正确的方向前进。我无法编写完整的代码，因为我不知道您的转换数据是如何存储的等等。

在讨论某些翻译是否可交换（例如，先做A再做B和先做B再做A是否相同）后，我认为它们不是可交换的。特殊情况下，如果X和Y的缩放相等，则缩放和旋转是可交换的，但此处使用的语法表明缩放具有两个因素，我假设它们是X和Y的比例因子。这意味着在这种情况下，缩放和旋转是不可交换的。翻译从来都不是可交换的（想象一下平凡的情况，其中翻译将点移动到原点，你会发现这很重要）。

Nocturn在评论中提到的可交换性确实适用于X和Y轴上的比例相同的情况。这意味着如果您拥有这样的比例并且它紧挨着旋转，则将获得两个可能的有效变换顺序。没有办法区分这两者。