矩形近似算法

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