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

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.

CodePudding user response：

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.