c++ - 可扩展的邻居循环

Question

众所周知，如果想要布置实数的方格(又名矩阵)，他可以使用具有行优先顺序的array。让我们画出某个元素 i 的邻域:

...................................
...|i-width-1|i-width|i-width+1|...
...|   i-1   |   i   |   i+1   |...
...|i+width-1|i+width|i+width+1|...
...................................

为了简单起见，让我们假设我在方形网格中间的某个地方，所以没有边界问题。(我们可以添加 %(width*height) 并在边界网格上连接)。因此，如果想对第 i 个元素附近的每个元素做某事，应该这样做:

//function which does something with element at idx
void DoSomethinWithElement(size_t idx);

//left neighbour
DoSomethinWithElement(i-1);
//right neighbour
DoSomethinWithElement(i+1);
//top neighbour
DoSomethinWithElement(i-width);
//bottom neighbour
DoSomethinWithElement(i+width);

我想将此算法推广到任何类型的正多边形网格(即三角形、正方形、五边形、六边形等)。正则意味着它仅由一种多边形构成(即仅由三角形)。

如何概括任何类型的多边形网格: 1.数组中其他网格的布局？ 2. 这N(for square mesh four)语句在一个循环中？

问题“如何在多边形网格中找到一个瓦片的所有邻居？”使用图表快速解决。但我想使用数组，这样我就可以使用 CUDA 将它们复制到显卡。

网格示例:

1. 
2. 
3. 

Answer 1

I want to generalize this algorithm for any type of regular polygon grid (i.e. triangle, square, pentagonal, hexagonal etc.)

您对正多边形网格的定义很不寻常。通常，您可能不会旋转或镜像网格(平铺)的面，因为它被认为是规则的。只有 3 种规则拼贴(三角形、正方形、六边形)。所有五边形拼贴都需要镜像或旋转或两者兼而有之。

让我们将您的问题简化为:“如何在多边形网格中找到一张脸的所有邻居？”一旦你弄明白了这一点，在每个邻居上调用一个函数就很简单了。

网格是具有一定局限性的图形。可以通过用通用图表示网格来概括对邻居的搜索。图的顶点代表面，它们有到邻居的边。网格图是 planar graph .当网格由图表示时，问题就变成了:“给定图中的一个顶点，我如何找到所有相邻的顶点？”

请注意，图的顶点和边与网格的顶点和边不是一回事。例如，六边形网格的网格顶点有 3 条相连的边，而面有 6 个相邻的面，因此每个图顶点有 6 条边。

表示图形的一种方法是 adjacency list .在此表示中，您只需查找顶点的邻接表即可找到它的所有邻居。

But I want to use arrays

因为每个邻接表的大小是恒定的，所以它们可以像 decltype_auto 的回答中那样用数组来实现。或者，您可以使用邻接矩阵表示图形。

但是，如果您想要一个通用算法来处理网格的任何 表格表示，那么我认为您已经将自己逼入绝境。每种表示形式都不同，您需要针对每种表示形式使用不同的算法。