3

我枚举了不到 32 个绝对矩形大小，我需要给定尺寸并在枚举中找到最佳近似值。

有没有比我用大量嵌套if的 's 和else's 制定的意大利面条代码更好（即更具可读性和可维护性）的方法？

目前我刚刚：

enum imgOptsScale {
    //Some relative scales
    w005h005 = 0x8,
    w010h010 = 0x9,
    w020h020 = 0xA,
    w040h040 = 0xB,
    w070h070 = 0xC,
    w100h100 = 0xD,
    w150h150 = 0xE,
    w200h200 = 0xF,
    w320h320 = 0x10,
    w450h450 = 0x11,
    w200h010 = 0x12,
    w200h020 = 0x13,
    w200h070 = 0x14,
    w010h200 = 0x15,
    w020h200 = 0x16,
    w070h200 = 0x17
};
imgOptsScale getClosestSizeTo(int width, int height);

我想在我深入编码之前寻求帮助。我应该强调远离过于复杂的库的偏见，尽管我对算法比容器更感兴趣，容器应该在资源受限的系统上运行。

4

3 回答 3

2

是的...将您的 32 种不同尺寸放在预先构建的二叉搜索树中，然后递归搜索树中的“最佳”尺寸。基本上，如果当前节点矩形的左子预建矩形小于您的输入矩形，并且当前节点的矩形大于输入矩形，您将停止搜索。然后，您将返回与两者之间的输入矩形“最接近”的预定义矩形。

递归搜索创建的干净代码的一个很好的补充是它在搜索时间上也是对数的而不是线性的。

顺便说一句，您将希望随机化将初始预定义矩形值插入二叉搜索树的顺序，否则您最终会得到一个看起来像链表的退化树，并且您不会得到对数搜索时间因为树的高度将是节点数，而不是节点数的对数。

因此，例如，如果您按矩形的面积对树进行了排序（假设没有两个具有相同面积的矩形），那么您可以执行以下操作：

//for brevity, find the rectangle that is the 
//greatest rectangle smaller than the input
const rec_bstree* find_best_fit(const rec_bstree* node, const rec& input_rec)
{
    if (node == NULL)
        return NULL;

    rec_bstree*  return_node;

    if (input_rec.area < node->area)
        return_node = find_best_fit(node->left_child, input_rec);
    else if (input_rec.area > node->area)
        return_node = find_best_fit(node->right_child, input_rec);

    if (return_node == NULL)
        return node;
}

顺便说一句，如果树太复杂，您也可以简单地做一个数组或std::vector矩形实例，使用某种类型的条件对它们进行排序std::sort，然后对数组进行二进制搜索。

于 2012-02-10T23:54:39.567 回答
2

我想我会用一些结构数组来解决这个问题，一个用于水平测量，一个用于垂直测量。

通读数组以找到下一个更大的大小，并返回相应的键。从这两个键构建最终的盒子度量。（由于 32 只允许 5 位，这可能不是很理想——你可能想要水平 2.5 位和垂直 2.5 位，但我这里的简单方法需要 6 位——水平 3 位，垂直 3 位.如果您对具有较少自由度的维度之一感到满意，则可以从列表之一中删除一半元素（也可以调整<< 3）。如果您希望更好地表示两个维度，这可能需要足够的重新工作，这种方法可能不适合。）

未经测试的伪代码：

struct dimen {
    int x;
    int key;
}

struct dimen horizontal[] = { { .x = 10, .key = 0 },
                              { .x = 20, .key = 1 },
                              { .x = 50, .key = 2 },
                              { .x = 90, .key = 3 },
                              { .x = 120, .key = 4 },
                              { .x = 200, .key = 5 },
                              { .x = 300, .key = 6 },
                              { .x = 10000, .key = 7 }};

struct dimen vertical[] = { { .x = 10, .key = 0 },
                           { .x = 20, .key = 1 },
                           { .x = 50, .key = 2 },
                           { .x = 90, .key = 3 },
                           { .x = 120, .key = 4 },
                           { .x = 200, .key = 5 },
                           { .x = 300, .key = 6 },
                           { .x = 10000, .key = 7 }};

/* returns 0-63 as written */
int getClosestSizeTo(int width, int height) {
    int horizontal_key = find_just_larger(horizontal, width);
    int vertical_key = find_just_larger(vertical, height);
    return (horizontal_kee << 3) & vertical_key;
}

int find_just_larger(struct dimen* d, size) {
    int ret = d.key;
    while(d.x < size) {
        d++;
        ret = d.key;
    }
    return ret;
}
于 2012-02-11T00:30:35.820 回答
1

这是我提出的解决方案，

enum imgOptsScale {
    notScaled = 0x0,
    //7 relative scales upto = 0x7
    w010h010, w010h025, w010h060, w010h120, w010h200, w010h310, w010h450,
    w025h010, w025h025, w025h060, w025h120, w025h200, w025h310, w025h450,
    w060h010, w060h025, w060h060, w060h120, w060h200, w060h310, w060h450,
    w120h010, w120h025, w120h060, w120h120, w120h200, w120h310, w120h450,
    w200h010, w200h025, w200h060, w200h120, w200h200, w200h310, w200h450,
    w310h010, w310h025, w310h060, w310h120, w310h200, w310h310, w310h450,
    w450h010, w450h025, w450h060, w450h120, w450h200, w450h310, w450h450,
    w730h010, w730h025, w730h060, w730h120, w730h200, w730h310, w730h450
};
//Only call if width and height are actually specified. else 0=>10px 
imgOptsScale getClosestSizeTo(int width, int height) {
    static const int possSizes[] = {10, 25, 60, 120, 200, 310, 450, 730};
    static const int sizesHalfways[] = {17, 42, 90, 160, 255, 380, 590};
    int widthI = 6;
    while (sizesHalfways[widthI - 1] > width && --widthI>0);
    int heightI = 6;
    while (sizesHalfways[heightI - 1] > height && --heightI>0);
    return (imgOptsScale)(8 + 7 * widthI + heightI);
}
于 2012-02-11T01:31:09.373 回答