Алгоритм аппроксимации прямоугольника

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