多邊形同餘算法

Question

有誰知道檢查兩組多邊形之間的同餘的算法嗎？更具體一些，請看下圖。

我正在尋找一種方法來檢查一組給定的彩色三角形是否全等另一組，即通過大量的平移，旋轉或反射給定一組（例如藍色三角形）是否能疊加在另一組（例如紅色三角形）上。在上面的例子中，所有3組三角形（藍色，紅色和綠色）是全等的。

我正在處理的實際三角形比這個大，並且有更多的集合。

我一派，發現this paper，但它涉及3 d多邊形，而不是直接（在我看來）實現的。

任何建設性的想法或鏈接將受到歡迎。

編輯

只是爲了澄清，每個組三角形必須被視爲一個整體連接的圖中，即，在組中的每個三角形被固定在它的相對於所述集合中的其他的三角形的位置。

另外，我只需要一種算法可能確定一組三角形是否是全等到另一組，但具有比上面並與許多更多組的一個大得多的三角形。設想一個邊長爲N和總數爲N^2個較小三角形的三角形，將其分成N個不同顏色的N個三角形集合。

Answer 1

旋轉和反射的組合可以用一個旋轉和最多一個反射來表示，所以如果你只用一個旋轉算法運行一次旋轉算法兩次，一次使用原始數字，一次使用反射數字，則可以忽略反射。

三角形的重心（或更容易地，只有在三角形的頂點處有質量的圖形的重心）不受旋轉的影響，所以我將首先計算重心的每個數字。現在用一個列表來表示圖形，從列表中給出圖形中每個點從其重心的方向和距離。

如果設置的距離是不同的數字不能被對方的旋轉，我想大多數非全等將在這一階段被發現。對於總成本N^2，您可以考慮將一個圖中的頂點旋轉到另一個圖的每個可能的頂點，然後將此計算的旋轉應用於所有其他頂點並查看它們是否匹配。可能有些版本的https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation可以用來加速這個。將它們按順序排列後，通過頂點方向之間的角度來表示方向可能會有所幫助。