algorithm - 独立于旋转、镜像或位置获取形状的唯一哈希值

Question

上下文

我正在创建一个基于“房间”的迷宫生成器(实际上，更像是一个 map 生成器)想要相互连接。我从文本文件中读取这些，然后转换为由 LocatedNodes 组成的内部格式，它基本上是一个节点类型和 x-y 坐标。我将它们重新组合在 NodeList 中，我将所有函数放在其中以旋转/镜像/规范化这些节点。 Map 是腔室的集合，因此它有一个包含这些腔室的 NodeList。

总结层次结构:Map <- NodeList <- LocatedNodes

问题

为了连接房间，我比较了第一张 map 的开口形状和第二张 map 开口周围区域的形状。让我们从一个例子开始:

>>> print map6.nodes # nodes of the entire map
              1 1
    0    5    0 2
   o⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
 0 |#############
   |#...........#
   |#...........#
   |#...........#
   |#............
 5 |#............
   |#........    
   |#........    
   |#........    
   |#........    
10 |#########    

>>> print map6.openings() # just the nodes placed on the opening
       1
   8   2
  o⎯⎯⎯⎯⎯
4 |    .
  |.....
  |.    
  |.    
  |.    
9 |. 

>>> print map7.nodes # map we want to connect with the other
             1   1
   0    5    0   4
  o⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
0 |    ###########
  |    ..........#
  |    ..........#
  |..............#
  |..............#
5 |..............#
  |..............#
7 |###############

>>> print map7.joinable_on() # area around the map7.openings()
   -
   1   3
  o⎯⎯⎯⎯⎯
1 |    .
  |.....
  |.    
  |.    
  |.    
6 |. 

>>> map7.joinable_on().normalized(x=0,y=0) == map6.openings().normalized(x=0, y=0)
True

比较 map6.openings() 和 map7.joinable_on() 并不难，因为当节点的位置归一化时，我可以进行一对一的比较。

但是，现在困难的部分来了: 我希望能够独立于它们的位置、旋转或镜像来比较这些形状。

我尝试过的

在搜索想法时，我找到了 pairing function (此函数将两个 int 链接到一个唯一的 int，因此每个坐标 x-y 都变成一个唯一的 int)。这样我就可以通过在 (x,y) 坐标上递归地应用这个函数来唯一地识别一个形状。第一个问题，unique int 确实是独一无二的，所以即使旋转 90° int 也会改变，所以我不能这样比较两个形状。

问题

您是否有想法或解决方案来帮助我获得形状的唯一 ID，该形状在镜像、平移或旋转时不会改变？

Answer 1

有一个通用方案用于创建在镜像、平移或旋转形状时不会改变的 ID。从一个关心镜像、平移和旋转的 id 开始。当你得到一个形状时，考虑每一种可能的镜像、旋转和平移，并为每种情况计算一个 id。这会为您提供大量 ID，因此只需选择数值最小的一个即可。

对于平移的情况，另一个想法可能更实用 - 在完成所有这些之前(和/或之后)，平移形状，使其重心位于原点，或尽可能靠近原点做到这一点。