仅使用点邻居将环形展开到2D空间中

我正在尝试想出一种算法，可以将圆环展开为2D阵列，这样我就可以使用X、Y坐标来寻址各个点，并以一致的方式在网格上漫游。

我的问题是我没有很多信息可以处理。我有一个组成环面的唯一标识点的列表，但整数标识符是随机的和非连续的。我有一个与每个点相关的邻居列表，但这个列表是一个无序的集合。

不知怎的，我需要选择一个起点（可能是标识符整数最低的点），然后在整个网格上迭代，这样我就可以得到一个2D数组，当每个点在环面上排列时，该数组描述了它们的标识符。

我该如何最好地解决这样的问题？

如果你有2D环面，并且你想把它放入带有"邻居"数据的2D阵列中，你可以通过这种方法来做到这一点。

托罗德是对称的，所以你们可以先取任意一点，然后把他放到数组的任意位置。我会把它放在阵列的中间，但你们甚至可以从角落开始，这并不重要。

对于5 x 5圆环，您可以创建5 x 5阵列

X - X - X - X - X
X - X - X - X - X
X - X - X - X - X
X - X - X - X - X
X - X - X - X - X

你从你的名单上取一个，把他放在中间的

X - X - X - X - X
X - X - X - X - X
X - X - O - X - X
X - X - X - X - X
X - X - X - X - X

现在你想找到这些邻居N，由邻居F的邻居识别。这很容易：

满足条件的第一对：

X - X - X - X - X
X - X - N - F - X
X - X - O - N - X
X - X - X - X - X
X - X - X - X - X

你可以得到4对（在每个方向），但由于对称结构，你可以只取一对放在阵列中

X - X - X - X - X
X - X - O - O - X
X - X - O - O - X
X - X - X - X - X
X - X - X - X - X

现在，您终于将环面定位到某个东西上，并且可以开始用值填充它。

看看这些"N"个节点

X - X - X - X - X
X - X - O - O - X
X - X - O - O - X
X - X - N - N - X
X - X - X - X - X

只有两个确切的节点满足这些条件。数组中已经有"O"个节点，因此您知道它们的位置。如果我把重要的（在这个步骤中）标记为1和2，它看起来像这个

X - X - X - X - X
X - X - O - O - X
X - X - 1 - 2 - X
X - X - N - N - X
X - X - X - X - X

只有两个未公开的节点实现了这一点："N1连接到1；N2连接到2；N1和N2连接"。因此，您可以找到它们并将其放入。

X - X - X - X - X
X - X - O - O - X
X - X - O - O - X
X - X - O - O - X
X - X - X - X - X

你可以用这种方法完成全线

X - X - O - O - X
X - X - O - O - X
X - X - O - O - X
X - X - O - O - X
X - X - O - O - X

现在你可以对另一个方向做同样的

X - X - O - O - X
O - O - O - O - O
O - O - O - O - O
X - X - O - O - X
X - X - O - O - X

然后是另一个

X - X - O - O - X
O - O - O - O - O
O - O - O - O - O
O - O - O - O - O
O - O - O - O - O

最后一次

O - O - O - O - O
O - O - O - O - O
O - O - O - O - O
O - O - O - O - O
O - O - O - O - O

相关内容