CODEWITHSUNDEEP
algorithmmath
JustAMartin
JustAMartin

Reputation: 13723

How to find the rectangle that leaves the most free space on both sides of a smaller rectangle?

I'm trying to figure out an appropriate algorithm for my software but I can't find any relevant "textbook solution". I reduced the task to the following core problem.

Given choices of rectangular areas, I need to find the area that leaves the most space on all sides simultaneously of a smaller rectangle that is known to fit all of the areas.

Given: Rectangle: length=100, width=200

Areas (will be always preselected to be larger than the rectangle):

  1. length=100, width=200
  2. length=101, width=500
  3. length=101, width=201
  4. length=300, width=300 <- this is the best fit because it has the most of free space in both dimensions simultaneously, despite the fact that there are other options that have even more space, but in a single direction only
  5. length=200, width=1000
  6. length=1000, width=200

What should be the algorithm to find the 4) choice as the best fit?

Will be grateful for pseudocode or code in any C-like language or Python, or a pointer to some well-known algorithm.

The numbers were picked just for this test example. In real life, all the numbers could be any, as entered by users.

Upvotes: 0

Views: 109

Answers (1)

user12069894
user12069894

Reputation:

If I understood your problem correctly this would be a solution (c++), didn't test it though:

struct Rectangle
{
    size_t x, y;
};

//returns first index which fits your condition
int alg(Rectangle a, Rectangle *others, size_t othersLen)
{
    unsigned int biggestIndex = 0;
    size_t biggest = 0;
    for (int i = 0; i < othersLen; i++)
    {
        size_t diffX = others[i].x - a.x;
        size_t diffY = others[i].y - a.y;
        size_t size = diffX > diffY ? diffY : diffX;
        if (size > biggest)
        {
            biggest = size;
            biggestIndex = i;
        }
    }
    return biggestIndex;
}

Edit: Only works if the other rectangles are bigger than the given rectangle, because it doesn't do negative differences.

Upvotes: 1

Related Questions