0

众所周知，如果一个人想要布局实数的方形网格（又名矩阵），他可以使用array行优先顺序。让我们画一些元素 i 的邻域：

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

为简单起见，我们假设 i 在方形网格的中间某处，因此没有边界问题。（我们可以%(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 4) 语句？

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

网格示例：

  1. 三角形
  2. 五角形
  3. 六角形
4

2 回答 2

4

我想将此算法推广到任何类型的正多边形网格（即三角形、正方形、五边形、六边形等）

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

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

网格是具有某些限制的图表。可以通过用一般图表示网格来概括搜索邻居。图的顶点代表面，它们与邻居有边。网格图是平面图。当网格用图来表示时，问题就变成了：“给定图中的一个顶点，如何找到所有相邻的顶点？”

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

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

但我想使用数组

好吧，由于每个邻接列表的大小是恒定的，因此可以使用 decltype_auto 的答案中的数组来实现它们。或者，您可以使用邻接矩阵来表示图形。

但是，如果您想要一个用于网格的任何表格表示的通用算法，那么我认为您已经将自己画到了满足该要求的角落。每种表示形式都不同，您需要为每种表示形式使用不同的算法。

于 2015-11-05T14:36:06.973 回答
1

您可以通过长度为 N*K 的一维向量 v 或二维 NxK 矩阵 M 来表示多边形计数 N 的 K 多边形网格的邻接关系。使用std::size_t -1、nullptr 或任何适合您存储在 v 或 M 中的参考类型以指示在边界失踪的邻居。

给定这样一个 NxK 矩阵 M：

对于多边形 n 的邻居，您从 M[n][0] 迭代到 M[n][K-1]，通过您存储在 M 中的任何引用获取邻居，并在它们上应用您想要的任何函数。

于 2015-11-05T15:48:20.923 回答