矩形近似算法

Question

我有一个略低于 32 个绝对矩形尺寸的枚举，我需要给定尺寸并在我的枚举中找到最佳近似值。

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

目前我只有：

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);

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

Answer 1

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

读取数组以找到下一个更大的大小，并返回相应的键。从两个键构建最终的盒子尺寸。 （由于 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;
}

Answer 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 使用某种类型的标准对它们进行排序，然后在大批。

Answer 3

这是我提出的解决方案，

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);
}