动态查找矩形的边缘

Question

我有2个2D点,​​它们被塞在一起成阵列:int square[4].这四个数字被解释为矩形的定义,其中水平线平行于X轴,垂直线平行于Y轴.然后,数组的元素分别定义:

1. 左边的X坐标
2. 底边的Y坐标
3. 右边缘的X坐标
4. 上边缘的Y坐标

我在这里定义了一个绕线顺序enum:

enum WindingOrder {
    BOTTOM = 0,
    RIGHT,
    TOP,
    LEFT
};

我的代码的最小,完整,可验证的例子是,我得到一个输出第二个数组:int output[4]和一个输入WindingOrder edge.我需要填写output如下:

switch(edge) {
case BOTTOM:
    output[0] = square[0]; output[1] = square[1]; output[2] = square[2]; output[3] = square[1];
    break;
case RIGHT:
    output[0] = square[2]; output[1] = square[1]; output[2] = square[2]; output[3] = square[3];
    break;
case TOP:
    output[0] = square[2]; output[1] = square[3]; output[2] = square[0]; output[3] = square[3];
    break;
case LEFT:
    output[0] = square[0]; output[1] = square[3]; output[2] = square[0]; output[3] = square[1];
    break;
}

我没有嫁给一个特定的WindingOrder安排,也不关心分数的顺序ouptut,所以如果改变那些使得这个可以解决,我就失望了.我想知道的是我可以构建square索引以output在for循环中分配,而不使用if/ case/三元语句(换句话说使用逐位操作)？

所以我想要,给予int i = 0并对WindingOrder edge它们进行逐位操作以找到:

do {
    output[i] = array[???];
} while(++i <= LEFT);

编辑:

我收到了很多静态数组的答案(我相信这是解决这个问题的最佳方法,所以我给了+1).但作为一个逻辑问题,我很奇怪为什么很少有位操作可以动态地找到给定边的元素.因此,例如,如何把这个函数体被writen给出一个任意edge和i:int getIndex(int i, int edge)

Answer 1

这是一个不同的解决方案.它是静态数组方法的变体,但没有实际数组:索引矩阵内联为计算为常量表达式的32位无符号整数.通过edge单个移位选择参数列,最后,通过简单的位移和屏蔽选择每个数组元素的各个索引.

该解决方案具有以下优点:

• 它很容易理解
• 它不使用测试
• 它不使用静态数组,也不使用任何其他内存位置
• 它独立于缠绕顺序,可以轻松定制任何阵列组件顺序
• 它不使用C99特定语法,这可能在C++中不可用.

这就像我可以得到一个按位解决方案一样接近.

#include <iostream>

enum WindingOrder { BOTTOM = 0, RIGHT, TOP, LEFT };

void BitwiseWind(int const *input, int *output, enum WindingOrder edge)
{
    unsigned bits = ((0x00010201 << BOTTOM * 2) |
                     (0x02010203 << RIGHT  * 2) |
                     (0x02030003 << TOP    * 2) |
                     (0x00030001 << LEFT   * 2))
                    >> (edge * 2);

    output[0] = input[(bits >> 24) & 3];
    output[1] = input[(bits >> 16) & 3];
    output[2] = input[(bits >>  8) & 3];
    output[3] = input[(bits >>  0) & 3];
}

int main() {
    enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT };
    int rect[4] = { 1, 3, 4, 5 };
    int output[4];

    for (int i = 0; i < 4; i++) {
        BitwiseWind(rect, output, edges[i]);
        std::cout << output[0] << output[1] << output[2] << output[3] << std::endl;
    }
    return 0;
}

编译BitwiseWindfor x86-64with clang -O3生成21条指令,比静态数组版本多6条,但没有任何内存引用.这有点令人失望,但我希望它可以为ARM目标生成更少的指令,利用位域提取操作码.顺便说一句,内联版本使用output[i] = array[(i+(i==winding)*2)&3];产生25条指令而没有任何跳转,并且gcc -O3更糟糕的是:它通过4次测试和跳转生成了更多的代码.

下面的通用getIndex函数只编译为6 x86条指令:

int getIndex(int i, int edge) {
    return (((0x00010201 << BOTTOM * 2) |
             (0x02010203 << RIGHT  * 2) |
             (0x02030003 << TOP    * 2) |
             (0x00030001 << LEFT   * 2))
            >> (edge * 2 + 24 - i * 8)) & 3;
}

Answer 2

是否可以重新定义 WindingOrder 的值集？如果可能的话，这是我的解决方案，它尝试在 WindingOrder 的值集中编码选择索引，然后input[]在output[]索引迭代时通过移位和屏蔽简单地解码出选择索引。

[感谢chqrlie提供代码库]：

    #include <iostream>

enum WindingOrder {
    // the RIGHT most 4-bits indicate the selection index from input[] to output[0]
    // the LEFT most 4-bits indicate the selection index from input[] to output[3]
    BOTTOM = 0x1210,
    RIGHT = 0x3212,
    TOP = 0x3230,
    LEFT = 0x3010
};

void BitwiseWind(int const *input, int *output, unsigned short edge)
{
    for (size_t i = 0; i < 4; i++)
        output[i] = input[(edge >> (i*4)) & 0x000F];    // decode
}

int main() {
    enum WindingOrder edges[4] = { BOTTOM, RIGHT, TOP, LEFT };
    int rect[4] = { 1, 3, 4, 5 };
    int output[4];

    for (int i = 0; i < 4; i++) {
        BitwiseWind(rect, output, edges[i]);
        std::cout << output[0] << output[1] << output[2] << output[3] << std::endl;
    }
    return 0;
}

通用 getIndex(int i,enum WindingOrder edge) 为：

int getIndex(int i,enum WindingOrder edge)
{
   return ((edge >> (i*4)) & 0x000F);
}

我没有计算它使用了多少指令，但我相信它会很少。并且很容易想象它是如何工作的。:)