Алгоритм приближения прямоугольника

Я думаю, что подошёл бы к этому с несколькими массивами структур, один для горизонтальных мер и один для вертикальных мер.

Прочитайте массивы, чтобы найти следующий больший размер, и верните соответствующий ключ. Постройте окончательную меру коробки из двух ключей. (Поскольку 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;
}

Да... поместите свои 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, а затем выполнить двоичный поиск в массиве.

Вот мое предлагаемое решение,

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