Rectangle approximation algorithm

Question

I have an enumeration of just under 32 absolute rectangle sizes and I need to given dimensions and find the best approximation among my enumeration.

Is there any better (ie more readable and maintainable) way than the spaghetti code I am formulating out of lots of nested if's and else's?

At the moment I have just:

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

and I thought I'd ask for help before I got too much further into coding up. I should emphasise a bias away from too elaborate libraries though I am more interested in algorithms than containers this is supposed to run on a resource constrained system.

Answer 1

Here is my proposed solution,

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

Answer 2

I think I'd approach this with a few arrays of structs, one for horizontal measures and one for vertical measures.

Read through the arrays to find the next larger size, and return the corresponding key. Build the final box measure from the two keys. (Since 32 only allows 5 bits, this is probably not very ideal -- you'd probably want 2.5 bits for the horizontal and 2.5 bits for the vertical, but my simple approach here requires 6 bits -- 3 for horizontal and 3 for vertical. You can remove half the elements from one of the lists (and maybe adjust the << 3 as well) if you're fine with one of the dimensions having fewer degrees of freedom. If you want both dimensions to be better represented, this will probably require enough re-working that this approach might not be suitable.)

Untested pseudo-code:

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 3

Yes ... place your 32 different sizes in a pre-built binary search tree, and then recursively search through the tree for the "best" size. Basically you would stop your search if the left child pre-built rectangle of the current node's rectangle is smaller than your input rectangle, and the current node's rectangle is larger than the input rectangle. You would then return the pre-defined rectangle that is "closest" to your input rectangle between the two.

One nice addition to the clean code the recursive search creates is that it would also be logarithmic rather than linear in search time.

BTW, you will want to randomize the order that you insert the initial pre-defined rectangle values into the binary search tree, otherwise you will end up with a degenerate tree that looks like a linked list, and you won't get logarithmic search time since the height of the tree will be the number of nodes, rather than logarithmic to the number of nodes.

So for instance, if you've sorted the tree by the area of your rectangles (provided there are no two rectangles with the same area), then you could do something like the following:

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

BTW, if a tree is too complex, you could also simply do an array or std::vector of instances of your rectangles, sort them using some type of criteria using std::sort, and then do binary searched on the array.