有谁知道检查两组多边形之间是否一致的算法?更具体的,请看下图。
我正在寻找一种方法来检查一组给定的彩色三角形是否与另一组一致,即是否可以通过多次平移、旋转或反射将给定的一组(例如蓝色三角形)叠加到另一组上设置(例如红色三角形)。在上面的示例中,所有 3 组三角形(蓝色、红色和绿色)都是全等的。
我正在研究的实际三角形比这个大,而且有更多的集合。
我用谷歌搜索并找到了 this paper ,但它涉及 3-D 多边形并且不能直接(在我看来)实现。
欢迎任何建设性的想法或链接。
编辑
澄清一下,每组三角形都必须被视为一个完整的连接图形,即该组中的每个三角形相对于组中其他三角形的位置是固定的。
此外,我只需要一种算法来确定一组三角形是否与另一组三角形一致,但三角形比上面的三角形大得多并且有更多的组。想象一个边长为 N 的三角形和总共 N^2 个较小的三角形,分成 N 个不同颜色的 N 个三角形组。
最佳答案
旋转和反射的组合可以用旋转和最多一次反射来表示,因此如果您运行仅旋转算法两次,则可以忽略反射,一次使用原始图形,一次使用反射图形。
三角形的重心(或者更简单地说,只在三角形顶点有质量的图形的重心)不受旋转的影响,所以我将从计算重心开始每个数字。现在用一个列表表示图形,给出图形中每个点与其重心的方向和距离。
如果一组距离不同,图形就不能相互旋转,我想大多数不一致会在这个阶段被发现。对于总成本 N^2,您可以考虑将一个图中的顶点旋转到另一个图中的每个可能的顶点,然后将计算出的旋转应用到所有其他顶点并查看它们是否匹配。可能是 https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation 的某个版本可以用来加快速度。在对顶点排序后,它可能有助于通过顶点方向之间的角度来表示方向。
关于algorithm - 多边形同余算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38085102/