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

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.