c++ - 对角展平矩阵的邻域索引计算

Question

我有一个二维矩阵存储在沿对角线的 FlatBuffers 中。例如，一个 4x4 矩阵的索引会像这样分散:

 0   2   5   9
 1   4   8  12
 3   7  11  14
 6  10  13  15

使用这种表示，在给定原始索引和 X/Y 偏移量的情况下，计算相邻元素索引的最有效方法是什么？例如:

// return the index of a neighbor given an offset
int getNGonalNeighbor(const size_t index,
                      const int x_offset,
                      const int y_offset){
    //...
}

// for the array above:
getNGonalNeighbor(15,-1,-1); // should return 11
getNGonalNeighbor(15, 0,-1); // should return 14
getNGonalNeighbor(15,-1, 0); // should return 13
getNGonalNeighbor(11,-2,-1); // should return 1

我们在这里假设永远不会发生溢出并且没有回绕。

我有一个涉及很多 triangular number 的解决方案和三角根计算。它还包含很多分支，如果可能的话，我更愿意用代数代替它们(这将在发散控制流成本高昂的 GPU 上运行)。我的解决方案有效但非常冗长。我觉得必须有一种更简单、计算强度更低的方法来做到这一点。

如果有人可以为这个特定问题/表示命名，也许会对我有所帮助。

如果有人感兴趣，我可以发布我的完整解决方案，但正如我所说，对于这样一个简单的任务来说，它非常长且相对复杂。简而言之，我的解决方案可以:

• 将原始索引转换为更大的三角矩阵以避免处理 2 个三角形(例如 13 将变为 17)

对于 4x4 矩阵，这将是:

0   2   5   9   14  20  27
1   4   8   13  19  26  
3   7   12  18  25  
6   11  17  24  
10  16  23
15  22  
21  

• 使用偏移量的曼哈顿距离和索引的三角根计算此表示中邻居对角线的索引。
• 使用偏移计算这条对角线上邻居的位置
• 通过删除填充转换回原始表示。

出于某种原因，这是我能想到的最简单的解决方案。

编辑:

有循环来累积偏移量:

我意识到，鉴于三角形数的属性，将矩阵拆分为两个三角形会更容易(我们称 0 到 9 为“上三角”，10 到 15 为“下三角”)并有一个循环内部测试通过在上三角中加一个 while 并在下三角中减去一个(如果有意义的话)来累积偏移量。但对于我的解决方案，必须不惜一切代价避免循环，尤其是行程计数不平衡的循环(同样，非常对 GPU 不利)。

所以我更多地寻找代数解决方案而不是算法解决方案。

构建查找表:

同样，由于 GPU，最好避免构建查找表并在其中进行随机访问(非常昂贵)。最好使用代数解。

矩阵的属性:

• 矩阵的大小已知。
• 目前我只考虑方阵，但也可以解决矩形矩阵问题。
• 正如我示例中的函数名称所暗示的那样，将解决方案扩展到 N 维体积(因此 N 边形扁平化)也将是一个很大的优势。

Answer 1

表格查找

#include <stdio.h>

#define SIZE 16
#define SIDE  4  //sqrt(SIZE)

int table[SIZE];
int rtable[100];// {x,y| x<=99, y<=99 }

void setup(){
    int i, x, y, xy, index;//xy = x + y

    x=y=xy=0;
    for(i=0;i<SIZE;++i){
        table[i]= index= x*10 + y;
        rtable[x*10+y]=i;
        x = x + 1; y = y - 1;//right up
        if(y < 0 || x >= SIDE){
            ++xy;
            x = 0;
            y = xy;;
            while(y>=SIDE){
                ++x;
                --y;
            }
        }
    }
}
int getNGonalNeighbor(int index, int offsetX, int offsetY){
    int x,y;
    x=table[index] / 10 + offsetX;
    y=table[index] % 10 + offsetY;
    if(x < 0 || x >= SIDE || y < 0 || y >= SIDE) return -1; //ERROR
    return rtable[ x*10+y ];
}

int main() {
    int i;
    setup();
    printf("%d\n", getNGonalNeighbor(15,-1,-1));
    printf("%d\n", getNGonalNeighbor(15, 0,-1));
    printf("%d\n", getNGonalNeighbor(15,-1, 0));
    printf("%d\n", getNGonalNeighbor(11,-2,-1));
    printf("%d\n", getNGonalNeighbor(0, -1,-1));

    return 0;
}

不要使用表格版本。

#include <stdio.h>

#define SIZE 16
#define SIDE  4

void num2xy(int index, int *offsetX, int *offsetY){
    int i, x, y, xy;//xy = x + y

    x=y=xy=0;
    for(i=0;i<SIZE;++i){
        if(i == index){
            *offsetX = x;
            *offsetY = y;
            return;
        }
        x = x + 1; y = y - 1;//right up
        if(y < 0 || x >= SIDE){
            ++xy;
            x = 0;
            y = xy;;
            while(y>=SIDE){
                ++x;
                --y;
            }
        }
    }
}
int xy2num(int offsetX, int offsetY){
    int i, x, y, xy, index;//xy = x + y

    x=y=xy=0;
    for(i=0;i<SIZE;++i){
        if(offsetX == x && offsetY == y) return i;
        x = x + 1; y = y - 1;//right up
        if(y < 0 || x >= SIDE){
            ++xy;
            x = 0;
            y = xy;;
            while(y>=SIDE){
                ++x;
                --y;
            }
        }
    }
    return -1;
}
int getNGonalNeighbor(int index, int offsetX, int offsetY){
    int x,y;

    num2xy(index, &x, &y);

    return xy2num(x + offsetX, y + offsetY);
}

int main() {
    printf("%d\n", getNGonalNeighbor(15,-1,-1));
    printf("%d\n", getNGonalNeighbor(15, 0,-1));
    printf("%d\n", getNGonalNeighbor(15,-1, 0));
    printf("%d\n", getNGonalNeighbor(11,-2,-1));
    printf("%d\n", getNGonalNeighbor(0, -1,-1));

    return 0;
}