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

У меня есть перечисление чуть менее 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);

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

3 3
c++ algorithm approximation

3 ответа:

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

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

2

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

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