矩形近似算法

我有一个只有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);

，我想我会寻求帮助之前，我有太多的进一步进入编码了。我应该强调偏离精心设计的图书馆，尽管我比容器更感兴趣算法，它应该在资源受限的系统上运行。

来源

2012-02-10 John

你是怎么定义“最好”的？这与[欧几里德距离]（http：// en。wikipedia.org/wiki/Euclidian_distance）在矩形的_area_上？或双方总和的欧几里德距离？还是双方单独？ 6x9矩形是否与9x6矩形相同？ – sarnold 2012-02-11 00:06:38

6x9不会与9x6相同。我呈现的图像和缩放将看起来可怕颠倒。最好的，我还不知道，对于相对缩放，我大多数都是将高度从几个四分之一屏幕和一半屏幕正方形分开。 – John 2012-02-11 00:10:08

我想我需要分别枚举枚举的每个维度，并确保它们在我的枚举中都是组合的。然后我可以简单地近似每个维度。现在烫发和组合的公式在哪里？ – John 2012-02-11 00:13:30

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

通读数组以找到下一个较大的大小，并返回相应的键。从两个键构建最终的盒子尺寸。（由于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-11 00:30:35 sarnold

我很高兴你同意我需要63枚32枚枚举。我仍然保留了8位，并且事情正在抬头。 – John 2012-02-11 00:42:53

64或16会比32更“容易”; 32这个机制绝对是可行的，但也许是次级结果。我敢肯定，对于奇数幂级别的机制，有一个更聪明的机制，但在此期间这可能“足够好”。 – sarnold 2012-02-11 01:09:55

只需返回'对'。并执行二进制搜索而不是线性扫描。并忘记关键 - 使用一个简单的'int'数组并返回实际尺寸而不是尺寸的关键。 – tom 2012-02-11 01:28:04

是的......将您的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::sort使用某种类型的条件对它们进行排序，然后在数组上进行二进制搜索。

来源

2012-02-10 23:54:39 Jason

我熟悉二进制排序的优点，但我仍然没有看到如何通过查看“矩形是否比我的输入矩形小”来应用它，当然这更适合而不是最接近逼近？找到最近的将需要测量每个维度，而不是比较矩形。即使只有24个矩形来比较意大利面条if-elses运行到100行代码！ – John 2012-02-11 00:01:43

可以排序的方法很多......为了简洁起见，我已经发布了一个非常简单的版本，但是如果您愿意，可以进行词汇排序，或者根据面积与长度的权重值进行排序。宽度等有很多的可能性... – Jason 2012-02-11 00:14:45

这是我提出的解决方案，

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-11 01:31:09 John

矩形近似算法

回答

相关问题