多边形同余算法

Question

有谁知道检查两组多边形之间的同余的算法吗？更具体一些，请看下图。

我正在寻找一种方法来检查一组给定的彩色三角形是否全等另一组，即通过大量的平移，旋转或反射给定一组（例如蓝色三角形）是否能叠加在另一组（例如红色三角形）上。在上面的例子中，所有3组三角形（蓝色，红色和绿色）是全等的。

我正在处理的实际三角形比这个大，并且有更多的集合。

我一派，发现this paper，但它涉及3 d多边形，而不是直接（在我看来）实现的。

任何建设性的想法或链接将受到欢迎。

编辑

只是为了澄清，每个组三角形必须被视为一个整体连接的图中，即，在组中的每个三角形被固定在它的相对于所述集合中的其他的三角形的位置。

另外，我只需要一种算法可能确定一组三角形是否是全等到另一组，但具有比上面并与许多更多组的一个大得多的三角形。设想一个边长为N和总数为N^2个较小三角形的三角形，将其分成N个不同颜色的N个三角形集合。

Answer 1

旋转和反射的组合可以用一个旋转和最多一个反射来表示，所以如果你只用一个旋转算法运行一次旋转算法两次，一次使用原始数字，一次使用反射数字，则可以忽略反射。

三角形的重心（或更容易地，只有在三角形的顶点处有质量的图形的重心）不受旋转的影响，所以我将首先计算重心的每个数字。现在用一个列表来表示图形，从列表中给出图形中每个点从其重心的方向和距离。

如果设置的距离是不同的数字不能被对方的旋转，我想大多数非全等将在这一阶段被发现。对于总成本N^2，您可以考虑将一个图中的顶点旋转到另一个图的每个可能的顶点，然后将此计算的旋转应用于所有其他顶点并查看它们是否匹配。可能有些版本的https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation可以用来加速这个。将它们按顺序排列后，通过顶点方向之间的角度来表示方向可能会有所帮助。