How do I check if a rectangle can fit into a bounding area?

Question

I wrote a function that generates a lot of things like this:

[
        (0, 619.5312394955338, 337.573529597446, 1080),
        (619.5312394955338, 1544.7619727875272, 0, 310.3079296654736),
        (619.5312394955338, 1544.7619727875272, 310.3079296654736, 337.573529597446),
        (1544.7619727875272, 1920, 0, 310.3079296654736),
        (619.5312394955338, 1088.2418093689296, 708.2009619111413, 1080),
        (1088.2418093689296, 1920, 337.573529597446, 708.2009619111413),
        (1088.2418093689296, 1920, 708.2009619111413, 1080),
        (0, 173.32617646340788, 288.56747000927186, 337.573529597446),
        (173.32617646340788, 619.5312394955338, 0, 288.56747000927186),
        (173.32617646340788, 619.5312394955338, 288.56747000927186, 337.573529597446),
        (0, 25.117144604340456, 177.08675820480235, 288.56747000927186),
        (25.117144604340456, 173.32617646340788, 0, 177.08675820480235),
        (25.117144604340456, 173.32617646340788, 177.08675820480235, 288.56747000927186),
        (0, 22.953859822450067, 0, 96.22494617847441),
        (0, 22.953859822450067, 96.22494617847441, 177.08675820480235),
        (22.953859822450067, 25.117144604340456, 0, 96.22494617847441),
        (22.953859822450067, 25.117144604340456, 96.22494617847441, 177.08675820480235),
        (619.5312394955338, 1061.0668595171933, 337.573529597446, 487.04072151109654),
        (619.5312394955338, 1061.0668595171933, 487.04072151109654, 708.2009619111413),
        (1061.0668595171933, 1088.2418093689296, 337.573529597446, 487.04072151109654),
        (1061.0668595171933, 1088.2418093689296, 487.04072151109654, 708.2009619111413),
        (1544.7619727875272, 1797.260895403902, 310.3079296654736, 324.5737372982961),
        (1544.7619727875272, 1797.260895403902, 324.5737372982961, 337.573529597446),
        (1797.260895403902, 1920, 310.3079296654736, 324.5737372982961),
        (1797.260895403902, 1920, 324.5737372982961, 337.573529597446)
]

The first number is always smaller than the second number, and the third number is always smaller than the fourth number, the first two numbers represent x coordinates, the last two numbers represent y coordinates.

The above list represents this:

[
        [(0, 337.573529597446), (619.5312394955338, 337.573529597446), (619.5312394955338, 1080), (0, 1080)],
        [(619.5312394955338, 0), (1544.7619727875272, 0), (1544.7619727875272, 310.3079296654736), (619.5312394955338, 310.3079296654736)],
        [(619.5312394955338, 310.3079296654736), (1544.7619727875272, 310.3079296654736), (1544.7619727875272, 337.573529597446), (619.5312394955338, 337.573529597446)],
        [(1544.7619727875272, 0), (1920, 0), (1920, 310.3079296654736), (1544.7619727875272, 310.3079296654736)],
        [(619.5312394955338, 708.2009619111413), (1088.2418093689296, 708.2009619111413), (1088.2418093689296, 1080), (619.5312394955338, 1080)],
        [(1088.2418093689296, 337.573529597446), (1920, 337.573529597446), (1920, 708.2009619111413), (1088.2418093689296, 708.2009619111413)],
        [(1088.2418093689296, 708.2009619111413), (1920, 708.2009619111413), (1920, 1080), (1088.2418093689296, 1080)],
        [(0, 288.56747000927186), (173.32617646340788, 288.56747000927186), (173.32617646340788, 337.573529597446), (0, 337.573529597446)],
        [(173.32617646340788, 0), (619.5312394955338, 0), (619.5312394955338, 288.56747000927186), (173.32617646340788, 288.56747000927186)],
        [(173.32617646340788, 288.56747000927186), (619.5312394955338, 288.56747000927186), (619.5312394955338, 337.573529597446), (173.32617646340788, 337.573529597446)],
        [(0, 177.08675820480235), (25.117144604340456, 177.08675820480235), (25.117144604340456, 288.56747000927186), (0, 288.56747000927186)],
        [(25.117144604340456, 0), (173.32617646340788, 0), (173.32617646340788, 177.08675820480235), (25.117144604340456, 177.08675820480235)],
        [(25.117144604340456, 177.08675820480235), (173.32617646340788, 177.08675820480235), (173.32617646340788, 288.56747000927186), (25.117144604340456, 288.56747000927186)],
        [(0, 0), (22.953859822450067, 0), (22.953859822450067, 96.22494617847441), (0, 96.22494617847441)],
        [(0, 96.22494617847441), (22.953859822450067, 96.22494617847441), (22.953859822450067, 177.08675820480235), (0, 177.08675820480235)],
        [(22.953859822450067, 0), (25.117144604340456, 0), (25.117144604340456, 96.22494617847441), (22.953859822450067, 96.22494617847441)],
        [(22.953859822450067, 96.22494617847441), (25.117144604340456, 96.22494617847441), (25.117144604340456, 177.08675820480235), (22.953859822450067, 177.08675820480235)],
        [(619.5312394955338, 337.573529597446), (1061.0668595171933, 337.573529597446), (1061.0668595171933, 487.04072151109654), (619.5312394955338, 487.04072151109654)],
        [(619.5312394955338, 487.04072151109654), (1061.0668595171933, 487.04072151109654), (1061.0668595171933, 708.2009619111413), (619.5312394955338, 708.2009619111413)],
        [(1061.0668595171933, 337.573529597446), (1088.2418093689296, 337.573529597446), (1088.2418093689296, 487.04072151109654), (1061.0668595171933, 487.04072151109654)],
        [(1061.0668595171933, 487.04072151109654), (1088.2418093689296, 487.04072151109654), (1088.2418093689296, 708.2009619111413), (1061.0668595171933, 708.2009619111413)],
        [(1544.7619727875272, 310.3079296654736), (1797.260895403902, 310.3079296654736), (1797.260895403902, 324.5737372982961), (1544.7619727875272, 324.5737372982961)],
        [(1544.7619727875272, 324.5737372982961), (1797.260895403902, 324.5737372982961), (1797.260895403902, 337.573529597446), (1544.7619727875272, 337.573529597446)],
        [(1797.260895403902, 310.3079296654736), (1920, 310.3079296654736), (1920, 324.5737372982961), (1797.260895403902, 324.5737372982961)],
        [(1797.260895403902, 324.5737372982961), (1920, 324.5737372982961), (1920, 337.573529597446), (1797.260895403902, 337.573529597446)]
]

A list of coordinates of vertices non-overlapping rectangles:

I want to know, given a rectangle with width w and height h, how do I efficiently find all bounding boxes the rectangle can fit into?

I only know how to do this using list comprehension:

[(x1, x2, y1, y2) for x1, x2, y1, y2 in limits if x2 - x1 >= w and y2 - y1 >= h]

---

Rotation is not allowed. And position is disregarded. Only size matters.

Answer 1

This problem can be solved by different heuristics. There is a python repo that provides ready solution, and has good descriptions. It looks solid:

https://github.com/secnot/rectpack

the repository was mentioned in this article:

https://gorillasun.de/blog/rectangle-packing-an-incredibly-difficult-problem

Answer 2

If you have a lot of rectangles and a lot of tests to do, then you can solve this problem with a partially persistent red-black tree or similar. Partial persistence means that all previous versions of the data structure remain accessible after you change it.

This solution will require O(N log N) time and space to set up the data structure, but then only O(log N + output_size) to find all the boxes big enough for any particular rectangle.

Given this data structure, which is admittedly somewhat complicated, solving the problem is easy.

BUILD:

1. Start with an empty tree. We will put rectangles into this tree, ordered by height.
2. Sort rectangles by width, and process them in order of decreasing width.
3. For each rectangle, add it to the tree. For each width, remember the last tree you created.

QUERY:

1. In the list created in (3) above, binary search to find the smallest width >= the query width, and retrieve its tree version. This tree will contain all rectangles that are wide enough, sorted by height.

2. Traverse the tree starting at the maximum height, until you get to a height that is too small. Output every rectangle you find.

You can find implementations of partially persistent red-black trees on the net. They are popular in functional languages, and they are used in a fair number of computational geometry problems. I don't know of a pre-existing implementation in python, though.

Answer 3

IMHO, this is an instance of the bin packing problem, resp. the sub-type of rectangle packing. Simplified, this means, in general, there is not better/faster solution than really trying every possible combination to find the matches.

Wikipedia links two different possible approaches with a little improved runtime ([1], [2]). The first one aims at always finding the optimal solution, the second one could also come up with "good, but not perfect" solutions. They're both quite complex, so I won't go into details here. You can have a look at them, they're well-explained, if that's interesting for you.

My personal, not so elaborated, approach would be a little more heuristic and still find the optimal solution. A heuristic approach means, that some of the combinations can be eliminated beforehand or very early during the process, so there are less operations to perform overall.

• For every given rectangle, compute its area by multiplying width and height.
• Store these values together with the rectangle definition in a data structure that supports sorting by this area value (like a tree map).
• For every rectangle coming in for comparison, you can disregard all given rectangles with an area less than its own one. Thus, you just cut off some of the source rectangles for comparing.
• Anyway, for each of the remaining source rectangles, you will still have to do the fill comparison of width and height.

I did not calculate the performance gain of my solution in terms of (less) operations needed and of course, like every heuristic, it's highly dependent on the concrete rectangle instances you have to deal with. But in general, despite having a bigger initial overhead (for calculating all the areas), you should come out a little quicker because - on average - you have less comparisons to make for every single rectangle.