Блог

У меня есть таблица занятости, хранящаяся в виде вектора в виде строки-мажорной формы. Допустим, на ячейки ссылаются по их номерам

 v = [1, 2, 3, ...... , width * height ]
  

где ширина и высота — это размеры сетки занятости, вот так

 0  1  2  3  4  5
6  7  8  9  10 11
12 13 14 15 16 17
18 19 20 21 22 23
24 25 26 27 28 29
30 31 32 33 34 35
  

если у нас есть сетка занятости 6 x 6.

Что я хотел бы сейчас сделать, так это уменьшить размер сетки занятости 6 x 6 до размера сетки занятости 2 x 2 (или 3 x 3). Способ сделать это — проверить следующие группы ячеек по отдельности:

 0  1  2 
6  7  8 
12 13 14 

3  4  5
9  10 11
15 16 17

18  19  20
24  25  26
30  31  32

21  22  23
27  28  29
33  34  35
  

и если какая-либо ячейка в одной группе занята, то
новая ячейка в таблице с уменьшенной выборкой также будет занята. Таким образом, я получаю следующую сетку занятости, где заполняемость ячеек 1,2,3,4 определяется четырьмя группами ячеек выше

 1  2
3  4
  

Как я могу написать цикл for на C , чтобы выполнить вышеуказанное для сеток произвольного размера? Единственный шаблон, который мне удалось выяснить, заключается в том, что индекс первого элемента в каждой строке равен i * width, где i — номер строки

Важной вещью здесь, вероятно, является сопоставление 2D с 1D:

 idx = x   width * y
  

После этого мы можем перейти к уменьшению выборки:

 input:
    originalOccupancy[]
    originalWidth, originalHeight
    newWidth, newHeight

int downsampleFactorX = originalWidth / newWidth;
int downsampleFactorY = originalHeight / newHeight;

for(int y = 0; y < newHeight;   y)
{
    for(int x = 0; x < newWidth;   x)
    {
        int bool occupied = false;
        //now check all the relevant original cells
        for(int oy = 0; oy < downsampleFactorY;   oy)
        {
            int originalRowStartIdx = (y * downsampleFactorY   oy) * originalWidth   x * downsampleFactorX;
            for(int ox = 0; ox < downsampleFactorX;   ox)                
                occupied = occupied || originalOccupancy[originalRowStartIdx   ox];
        }
        newOccupancy[x   y * newWidth] = occupied;
    }
}