矩形近似アルゴリズム

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

私は構造体のいくつかの配列を使ってこれにアプローチしたいと思います。水平型のものと垂直のものの配列です。

次の大きなサイズを見つけるために配列を読み取って、対応するキーを返します。 2つのキーから最後のボックスメジャーを作成します。 （32ビットは5ビットしか使えないので、これはおそらくあまり理想的ではないでしょう。水平方向には2.5ビット、垂直方向には2.5ビットが必要ですが、私の単純なアプローチでは水平方向に3、垂直方向に3あなたが自由度の低い方のディメンションでうまくいけば、リストの1つから要素の半分を削除することができます（<< 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; 
} 

：あなたは長方形の面積でツリーをソートしてきたのであれば、たとえば

は、その後、あなたは、次のような何かを行うことができます（同じ面積とは2つの四角形がない提供しました）ところで、ツリーが複雑すぎる場合は、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); 
}