Algorithm for finding "free space" between objects on a surface

JonB

This is a "WiP", as I think it's going to be difficult! I need an algorithm/approach for discovering the following:

I have a (large) rectangular surface.
There are any number of existing (small) rectangles placed non-overlapping on the surface. Note that they may be placed anywhere, there is no "columns/rows" layout/restriction.
I want to place a new (small) rectangle on the surface, not overlapping any existing ones.
I need to identify existing area(s) which are "free" and "big enough" to accept the new rectangle. Perhaps a list of all "free rectangular areas" on the surface.

For a human it's easy. Imagine a kitchen table on which there are a bunch of objects randomly placed. To place a new object I look with my eyes and easily identify a (number of) unoccupied areas to place my next object. Simplez.

I am bad (in fact terrible!) at any drawing, so here is a fixed-font text representation:

------------------------------------
|                                  |
|    XXX           XXXX            |
|                         XXXX     |
|       XXXX XXX        XXX        |
|                                  |
|          XXXX   XXX              |
|                                  |
|    XXX  XXXX          XXX        |
------------------------------------

I want to place some new YYY or YYYYYY. You should get the gist. Please remember that in reality the rectangles are not placed in fixed rows/columns like the text is.

Everything is actually QGraphicsRectItems placed on a QGraphicsScene. As I said, in the setPos(x, y) the x & y can take any values, not limited to set "rows" or "columns".

I imagine I am not the first person who wants an algorithm/approach for this. There must be other applications where one needs to identify "unoccupied space" for a new object.

I am sort of thinking that you need to discover/partition the scene into a list of rectangular areas of maximal size which are quite empty and do not overlap any existing object. But if you think about there are many ways to discover such empty areas (quite different sets/sizes for them) with the corresponding results being more or less suitable for placement of a new object....

Thoughts? Approaches? References?

P.S.
Anybody who says I need an "AI/neural network/pattern recognition" or similar for this may be quite correct but will not be awarded a gold star! I need an implementable C++ algorithm/approach.

J.Hilk

@JonB I could ask the generative AI ? :D

class Rectangle:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height

def get_maximal_free_rectangles(surface_width, surface_height, existing_rectangles):
    # Generate vertical and horizontal sweep lines
    vertical_lines = {0, surface_width}
    horizontal_lines = {0, surface_height}
    
    for rect in existing_rectangles:
        vertical_lines.add(rect.x)
        vertical_lines.add(rect.x + rect.width)
        horizontal_lines.add(rect.y)
        horizontal_lines.add(rect.y + rect.height)
    
    vertical_lines = sorted(vertical_lines)
    horizontal_lines = sorted(horizontal_lines)
    
    # Identify maximal free rectangles
    free_rectangles = []
    for i in range(len(horizontal_lines) - 1):
        for j in range(len(vertical_lines) - 1):
            x1, x2 = vertical_lines[j], vertical_lines[j+1]
            y1, y2 = horizontal_lines[i], horizontal_lines[i+1]
            candidate_rect = Rectangle(x1, y1, x2-x1, y2-y1)
            
            if not any(intersects(candidate_rect, rect) for rect in existing_rectangles):
                free_rectangles.append(candidate_rect)
    
    return free_rectangles

def intersects(rect1, rect2):
    return not (rect1.x >= rect2.x + rect2.width or
                rect1.x + rect1.width <= rect2.x or
                rect1.y >= rect2.y + rect2.height or
                rect1.y + rect1.height <= rect2.y)

def place_new_rectangle(surface_width, surface_height, existing_rectangles, new_rect_width, new_rect_height):
    free_rectangles = get_maximal_free_rectangles(surface_width, surface_height, existing_rectangles)
    
    for free_rect in free_rectangles:
        if free_rect.width >= new_rect_width and free_rect.height >= new_rect_height:
            return Rectangle(free_rect.x, free_rect.y, new_rect_width, new_rect_height)
    
    return None  # No suitable place found

# Example usage
surface_width = 50
surface_height = 20
existing_rectangles = [
    Rectangle(5, 5, 10, 5),
    Rectangle(20, 10, 10, 5),
    Rectangle(35, 2, 5, 15)
]

new_rect_width = 6
new_rect_height = 3

new_rectangle = place_new_rectangle(surface_width, surface_height, existing_rectangles, new_rect_width, new_rect_height)
if new_rectangle:
    print(f"Placed new rectangle at: ({new_rectangle.x}, {new_rectangle.y})")
else:
    print("No suitable place found")

Explanation

get_maximal_free_rectangles: Generates vertical and horizontal lines based on the edges of the existing rectangles, then partitions the space into candidate free rectangles and checks if they are truly free.
intersects: Helper function to check if two rectangles overlap.
place_new_rectangle: Finds a suitable free rectangle that can accommodate the new rectangle and returns its position.

Maybe I should have specified a language to use! Is Python ok ?

J.Hilk

The approach you're hinting at involves partitioning the free space into maximal rectangles and then checking these against the size of the new rectangle to be placed

You won't be able to get around some kind of grid. It's a matter on how fine you make it. Probably Pixels ?

I think the situation you describe is usually handled by some kind of "ScanLine Algorithm"

Traverse the surface with a horizontal scanline from top to bottom (or a vertical scanline from left to right).
Track intersections of the scanline with the edges of the existing rectangles.
Between intersections, you'll identify spans of free space.

JonB

@J-Hilk
Hi, thanks for prompt response. You have given me a good starting thought, and at least provided me with one phrase, "scanline algorithm", to give me a handle on what sort of terms I might search for.

I had a brief read of the link. Looks complicated, only "sketched out"! Don't suppose you know of anywhere which might publish an algorithm (C++, other or any "descriptive language") I could implement from? Like Knuth did :)

J.Hilk

@JonB I could ask the generative AI ? :D

class Rectangle:
    def __init__(self, x, y, width, height):
        self.x = x
        self.y = y
        self.width = width
        self.height = height

def get_maximal_free_rectangles(surface_width, surface_height, existing_rectangles):
    # Generate vertical and horizontal sweep lines
    vertical_lines = {0, surface_width}
    horizontal_lines = {0, surface_height}
    
    for rect in existing_rectangles:
        vertical_lines.add(rect.x)
        vertical_lines.add(rect.x + rect.width)
        horizontal_lines.add(rect.y)
        horizontal_lines.add(rect.y + rect.height)
    
    vertical_lines = sorted(vertical_lines)
    horizontal_lines = sorted(horizontal_lines)
    
    # Identify maximal free rectangles
    free_rectangles = []
    for i in range(len(horizontal_lines) - 1):
        for j in range(len(vertical_lines) - 1):
            x1, x2 = vertical_lines[j], vertical_lines[j+1]
            y1, y2 = horizontal_lines[i], horizontal_lines[i+1]
            candidate_rect = Rectangle(x1, y1, x2-x1, y2-y1)
            
            if not any(intersects(candidate_rect, rect) for rect in existing_rectangles):
                free_rectangles.append(candidate_rect)
    
    return free_rectangles

def intersects(rect1, rect2):
    return not (rect1.x >= rect2.x + rect2.width or
                rect1.x + rect1.width <= rect2.x or
                rect1.y >= rect2.y + rect2.height or
                rect1.y + rect1.height <= rect2.y)

def place_new_rectangle(surface_width, surface_height, existing_rectangles, new_rect_width, new_rect_height):
    free_rectangles = get_maximal_free_rectangles(surface_width, surface_height, existing_rectangles)
    
    for free_rect in free_rectangles:
        if free_rect.width >= new_rect_width and free_rect.height >= new_rect_height:
            return Rectangle(free_rect.x, free_rect.y, new_rect_width, new_rect_height)
    
    return None  # No suitable place found

# Example usage
surface_width = 50
surface_height = 20
existing_rectangles = [
    Rectangle(5, 5, 10, 5),
    Rectangle(20, 10, 10, 5),
    Rectangle(35, 2, 5, 15)
]

new_rect_width = 6
new_rect_height = 3

new_rectangle = place_new_rectangle(surface_width, surface_height, existing_rectangles, new_rect_width, new_rect_height)
if new_rectangle:
    print(f"Placed new rectangle at: ({new_rectangle.x}, {new_rectangle.y})")
else:
    print("No suitable place found")

Explanation

get_maximal_free_rectangles: Generates vertical and horizontal lines based on the edges of the existing rectangles, then partitions the space into candidate free rectangles and checks if they are truly free.
intersects: Helper function to check if two rectangles overlap.
place_new_rectangle: Finds a suitable free rectangle that can accommodate the new rectangle and returns its position.

Maybe I should have specified a language to use! Is Python ok ?

JonB

@J-Hilk
Jeez, I hate that! How would you describe the question/problem? If you try it for me, can you let me know how you phrased that?

In a quick diversion which I know is OT. Why is this so damned difficult and essentially different for an algorithm versus actual human? I believe we are only really glorified C++ programs ;-) When I look to identify spaces I really don't think behind the scenes I am doing anything remotely like "using repeated scan lines and amalgamating them". I just spot the spaces! What's so hard/different? :)

Your post crossed with mine. Python is fine. Did you get that from ChatGPT? How did you pose the question?

J.Hilk

@JonB I more or less copied your OP, and added, give me example code. 🤷‍♂️

But my prompt was open for days with all kind of different programming related questions already asked. So you may get different results

JoeCFD

@JonB Can you reorder them after each insertion? For example, after each insertion in row 0, try to align them to left and you can check if this row has enough space for your new insertion. If not, check the second row. Sort of like the game: tetris?

JonB

@J-Hilk
I have only scanned the code with my eyes. There is something I do not follow. get_maximal_free_rectangles() seems to return some unique list of free rectangles. But when I think about it in my head I (believe, unless I am mistaken) see many different ways I could partition the free space? E.g. just think of a free space area shaped like an L. That is two rectangles. But for the bottom left intersection corner I could allocate that "square" at that point to either the vertical or the horizontal free rectangle? Or, does the algorithm produce overlapping free rectangular areas, so you would get the bottom-left corner free area allocated to both vertical & horizontal rectangles?

JonB

@J-Hilk said in Algorithm for finding "free space" between objects on a surface:

@JonB I more or less copied your OP, and added, give me example code. 🤷‍♂️

Then what's the point of being a human any longer...? :(

JonB

@JoeCFD
Never having played Tetris I'm not quite sure what you mean. But I think it involves moving the existing items over to "pack them all together" so you get a single big blob of space left over?

Let me ask you this: You are eating your dinner at the dining room table. You already have some plates, glasses, salt & pepper cellars, etc. dotted all over the table. Now you want to add a ketchup bottle. Do you proceed by moving all the existing items to one side of the table so that you can now see a big area where you might place the ketchup? I don't think so (unless you really are OCD)! ;-) I want to leave items where they are and just find some spaces between them where I could add a new item!

JoeCFD

@JonB Think about sometimes you do need to move them a bit to get some good space and location to fit the ketchup bottle for convenience to all people at the table. Otherwise, sort the spaces left and find the best fit quickly.

J.Hilk

@JonB said in Algorithm for finding "free space" between objects on a surface:

@J-Hilk said in Algorithm for finding "free space" between objects on a surface:

@JonB I more or less copied your OP, and added, give me example code. 🤷‍♂️

Then what's the point of being a human any longer...? :(

to like and subribe and consume product of course

JonB

@J-Hilk
I know :) I meant that answer was pretty good! I did not realise it would focus so well on the question.

When I pasted it into ChatGPT it did get the gist but gave me rather a different algorithm. Dividing into grid and storing bools. No sorting. I believe the one you got is better for my case. I think I had to ask it for sweep lines (which I wouldn't have known about) to get something more like yours, but still not identical! All very interesting and a bit frustrating.

@JoeCFD
Atm I have a "large" kitchen table and about 6 (small) items on it :)

JonB

@J-Hilk
It's interesting. I have now implemented the algorithm per your code above pasted from ChatGPT.

It turns out get_maximal_free_rectangles() returns a "large" number of rectangles, often quite small, which do cover the whole "free" area. Maybe that's why it's "maximal" rather than "minimal". The problem then is that, over time as more items are added onto the surface in various positions there may not be any individual free areas left to satisfy place_new_rectangle() for a new item when we can see there still is enough room. Because the numerous smaller rectangles can be "amalgamated" into a suitable larger area. I will look at doing this on the result set but it's not straightforward.

Otherwise I might have to revisit the alternative algorithm in my ChatGPT chat, perhaps that actually fits my needs better than this way....

J.Hilk

:D

I take no responsibility to LLM-Generated code. Especially once that is more complicated than Hello World

Pl45m4

@JonB

Some (hopefully helpful) input:

For one of my university courses some years ago I developed a simulation/algo for a circle packing problem.
We had to prove that five is the maximum of unit circles r=1 fitting in a circle r=3 when placed randomly (+ no overlap) and calculate the probability for each case with a maximum of three, four and five coins.
(seven in theory possible while six will never be max, since the only way to place six allows to place a seventh)

There was even a similar Havard (or Cambridge) test, math class applicants had to solve in order to pass or so (don't remember and can't find it right now).
Except they had to prove it mathematically while we had to code a simulation and find the probablilites for every case.
They had like 1 day, we had couple weeks :P

See Wiki: here and here (case 7).

You idea seems to be something like that, except your items seem to be variable and not all the same dimensions/geometry, right?! Which makes it a bit more difficult, while using rects instead of circles might be easier in your case.

Let me see if I can find some of that code (Python).

QGraphicsView is just another grid while your items are just rectangles :)
We used an occupancy grid for our simulation (at least for the visual part), so should be doable, kinda.. :D

There are also some general "solver" implementations out there, like this one here

https://github.com/fontanf/packingsolver

JonB

@Pl45m4
I am now good on the algorithm. The one I am using (via @J-Hilk/ChatGPT) gives me a satisfactory answer I can work with and place my objects.