获取形状的唯一哈希值，而与形状的旋转、镜像或位置无关

Question

>上下文

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

总结层次结构：映射<-节点列表<-定位节点

问题

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

>>> 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.opens(( et map7.joinable_on(( 并不难，因为当节点的位置归一化时，我可以进行一对一的比较。

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

我尝试了什么

在搜索想法时，我找到了配对函数(此函数将两个 int 链接到一个唯一的 int，因此每个坐标 x-y 都变成了一个唯一的 int(。有了它，我可以通过在 (x，y( 坐标上递归应用此函数来唯一地识别形状。第一个问题，唯一的 int 确实是唯一的，所以即使旋转 90°，int 也会发生变化，所以我不能以这种方式比较两个形状。

问题

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

Answer 1

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

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

Answer 2

似乎您应该拥有没有平移、旋转或镜像的形状列表。然后，要创建地图，请为形状编制索引并提供转换矩阵。因此，您的输入文件将如下所示：

Shapes
    shape1
    shape2
    shape3
    etc.

这些形状都是在原点构建的，没有翻译。

然后，您的地图将变为：

Map
    0 (index to shape1), transformation matrix (scaling, rotation, translation, mirroring)
    2 (index to shape3), transformation matrix
    0 (index to shape1), different transformation matrix

然后，要确定地图中的两个形状是否相同，您所要做的就是比较它们的索引。