将一维编码的二维数组划分为扇区

Question

我有一个编码成一维颜色数组的图像（为简单起见，这里用字母表示）：

[A, B, C, D,
 E, F, G, H,
 I, J, K, L,
 M, N, O, P]

但是由于我使用的库的限制，每个图像都必须在maxElements项目下，并且是正方形的。所以我需要做的是从该图像中提取"扇区"，这样我就可以单独迭代它们。maxElements = 4示例：

[A, B, [C, D,
 E, F]  G, H]
[I, J, [K, L,
 M, N]  O, P]

如果有余数，则应将其存储在较小的数组中。side = 3 的示例，maxElements = 4：

[A, B, C,      [[A, B, [C,
 D, E, F,  ->    D, E]  F]
 G, H, I]       [G, H] [I]]

请注意，数组在第 3 列被切割，因为如果其尺寸超过 2x2，则会违反 maxElements .

但是，另一个挑战是我无法访问此图像直到为时已晚，但我确实拥有图像的一面（如正方形面）和每个扇区的最大元素计数。所以我要做的是为数组中的每个像素生成一个索引数组。

所以我有 1D 数组中每一行的长度和行数（两者都是边），我需要为该要获得的数组生成一个索引数组。side = 4 、 maxElements = 4 的示例输出：

[[1, 2, 5, 6], [3, 4, 7, 8], [9, 10, 13, 14], [11, 12, 15, 16]]

也许我只是太多时间没有睡觉，但我无法解决这个问题。

Answer 1

这是一个粗略的想法：

要访问二维数组的一维表示中的第 (x,y) 个元素：x + y*H 。假设我们要访问数组中的 x = 1 和 y = 2（W=4， H=4）： arr[1 + 2*4] == arr[9] = J .

由于我们知道如何通过坐标访问元素，因此我们可以使用循环：

for (int x = 0; x < W; x += 2) {
  for (int y = 0; y < H; y += 2)
    output[(x/2) + (y/2)*(H/2)] = new int[] { arr[x + y*H],     arr[(x+1) + y*H], 
                                          arr[x + (y+1)*H], arr[(x+1) + (y+1)*H] };
  }
}

这是粗略的草图。要处理side = 3 maxElements = 4情况，您需要边界检查，以检查是否(x+1)<W和(y+1)<H。这意味着，有四种情况：

bool xi = (x+1)<W, yi = (y+1)<H;
if (xi && yi) // both within range
  output[...] = new int[] { arr[...], arr[...], arr[...], arr[...] };
if (!xi && yi) // only y within range
  output[...] = new int[] { arr[...], arr[...] };
if (xi && !yi) // only x within range
  output[...] = new int[] { arr[...], arr[...] };
else // both out of range
  output[...] = new int[] { arr[...] };

Answer 2

回到这个问题后，我找到了解决方案：

public static List<List<int>> SectorizeMap<T>(IEnumerable<T> input, int width, int maxPerSector) {
    var sectorSide = (int)Math.Sqrt(maxPerSector);
    var widthSectors = (int)Math.Ceiling((float)width / sectorSide);
    var resultSectors = new List<List<int>>();
    for (var i = 0; i < input.Count(); i++) {
        var x = i % width;
        var y = i / width;
        var sectorX = x / sectorSide;
        var sectorY = y / sectorSide;
        var sectorIndex = sectorY * widthSectors + sectorX;
        if (resultSectors.Count <= sectorIndex) {
            resultSectors.Add (new List<int> ());
        }
        resultSectors[sectorIndex].Add(i);
    }
    return resultSectors;
}

使用以下示例：

var resultSectors = SectorizeMap(Enumerable.Range(0, 36), 6, 4);
Console.WriteLine(string.Join(", ", 
    resultSectors.Select(sec => string.Format("[{0}]", 
        string.Join(", ", sec)))));

工作原理

我们开始接收输入数组、其宽度（以 2D 表示时）和每个扇区的最大项目数量。

由于扇区
1. 是正方形的，因此取每个扇区最大项目数的根，并将其用作扇区两侧的维度。
2. 计算一行适合多少个扇区。
3. 迭代输入：
   1. 将元素的索引解码为 （x， y） 对。
   2. 为这些坐标指定扇区 （x， y） 对
   3. 将扇区坐标转换为索引
   4. 将当前元素的索引添加到我们计算位置的扇区，必要时创建它。
4. 返回扇区列表。