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

[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.