多边形全等算法

Question

有人知道一种算法可以检查两组多边形之间的全等吗？更具体地说，请参见下图。 我正在寻找一种方法来检查给定的彩色三角形集是否与另一个集相同，即给定的集合（例如蓝色三角形）通过多次平移、旋转或翻转是否可以重叠在另一个集合（例如红色三角形）上。在上面的例子中，所有3组三角形（蓝色、红色和绿色）都是全等的。

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

我已经搜索了谷歌并找到了这篇论文，但它涉及到三维多边形，不直接适用（在我看来）。

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

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

此外，我只需要一个算法来确定一个三角形集合是否与另一个集合相似，但是这个三角形比上面的三角形大得多，而且有更多的集合。想象一下边长为N且总共由N^2个小三角形组成的三角形，分成N个不同颜色的N个三角形集合。

- Jens

---

@user3386109 我已经知道每个集合的多边形面积都相同，因为每个集合都有相同数量的（相同的）三角形。您能详细说明一下“检查角度顺序”是什么意思吗？ - Jens

@user3386109 不理解。你明白为什么图中的三组是全等的，以及如果我交换一个彩色三角形的位置与另一个不同颜色的三角形的位置，它们为什么不会是全等的吗？ - Jens

@ Jens 这就是需要添加到问题中的澄清。您还需要澄清是否将问题范围限制在三角形上。 - user3386109

@user3386109 已经明白，我现在会添加澄清。抱歉没有表达清楚。 - Jens

Answer 1

一组旋转和反射可以表示为一个旋转和至多一个反射，因此如果您用原始图形和反射图形分别运行旋转算法两次，则可以忽略反射。

三角形的重心（或者更容易的是，仅在三角形顶点处具有质量的图形的重心）不受旋转影响，因此我会先计算每个图形的重心。现在，通过给出每个点与其重心之间的方向和距离的列表来表示该图形。

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

- mcdowella