c++ - 动态查找矩形的边

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 中点的顺序，所以如果改变这些可以解决这个问题我'我下来。我想知道的是，我能否在 for 循环中构造 square 索引以分配给 output，没有 if/case/三元语句(换句话说，使用按位运算)？

所以我想，给定 int i = 0 和 WindingOrder edge 对它们进行按位运算以找到:

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

编辑:

我收到了很多静态数组答案(我认为这是解决这个问题的最佳方法，所以我给了 +1)。但作为一个逻辑问题，我很好奇可以采用多少位运算来动态查找给定边的元素。因此，例如，在给定任意 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;
}

使用clang -O3 为x86-64 编译BitwiseWind 生成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;
}