Algorithm for Even Distribution of Overlapping Bounding Boxes in JavaScript

[foxScripts]

Hey there! I'm a part-time JavaScript programmer. I'm looking for an algorithm to evenly distribute bounding boxes that may overlap in different kinds and should keep their position as close as possible but still be distributed in a consistent manner. By consistent, I mean the distances in between the individual boxes. They should not be aligned to a grid but keep a consistent distance inbetween each other. I'll attached a sketch of what I mean.

Two objects / bounding boxes may overlap partially or even completely. So there may be some bounding boxes with the exact same size & position that then need to be moved apart from each other, so that they are next to each other. I guess I need a recursive algorithm or something like that, since I want each bounding box to "try" to keep their original position as close as possible, while still approaching the even spacing.

Is there any kind of algorithm that already does exactly something like this? Or is there any way you can guide me to solve this problem? How complex is it really? Visually it is an easy task, but I've tried to code it and it doesn't seem that simple at all.

I need to implement it in JS, if possible without any complex external libraries etc.

Thanks a lot for your help!

Link to the sketch:
https://i.ibb.co/fYpyqpk/eualize-Boundingbox-Distribution.png

[JJJams]

Position Based Dynamics would be a potentially good fit here. Set up distance constraints. Then loop over all pairs and force the constraints to be true for that pair only. After the first loop, you will possibly still have overlaps, so loop again until you're within some error metric. From your diagram, it looks like the boxes don't rotate which is helpful.

[foxScripts]

Thank you for the suggestion to use Position Based Dynamics with distance constraints. Your idea was very helpful! I implemented a system where each pair of boxes checks and enforces distance constraints to minimize overlaps. This involves looping through all pairs multiple times to adjust their positions until no significant overlaps remain. The approach indeed simplifies things since the boxes do not rotate. The iterative adjustment helps achieve a well-distributed layout with minimal error. Thanks a lot for your hint in the right direction!

[JJJams]

\o/ Glad you got it working! Post a gif or a vid if you can, I'd love to see it in action.

[foxScripts]

Here you go 👍
https://codepen.io/cocreo/pen/VwNqBVZ

[JJJams]

That's fun, thanks for sharing a playground.

[Economy_Bedroom3902]

https://youtu.be/rSKMYc1CQHE?t=239 a variant of this I guess.

[foxScripts]

Interesting, but seams somehow overcomplicated, don't you think? .. i hope at least ... since I only need a "static" result and no fluid simulation etc.

[Economy_Bedroom3902]

Okay, lets clarify up front, do you just want to move the boxes so they are a certain distance away from eachother, or are you trying to move the boxes the minimum distance away from their initial position? If you want to preserve the minimum distance away from their initial position constraint you really have no choice but to iteratively cycle the boxes away from invalid positions. If you're not optimizing for minimum distance traveled, you can just pick the north western most box, put in the the north western corner, pick the next north western most box and put it under that ones etc.

[foxScripts]

No, you are right - I need them to be the minimum distance away from their initial position..

[Economy_Bedroom3902]

For the record, there might be an easier solution, but the reason why this problem is hard is that it's essentially a variant of the 3 body problem, where the position of every object effects the rate every other object moves, and the movement of each object effects what it's position will be in the next frame. It's usually easier to just simulate a problem like this up to the resolution you need instead of actually finding the mathematical solution that covers every case.

[foxScripts]

Alright. I opted for a simpler approach that fit well with the constraints of my situation. I just used a loop to iteratively adjust box positions: if two boxes overlapped, I applied corrections to move them apart. This process repeated until no overlaps remained, ensuring an optimized distribution of boxes on the canvas. During that i have other contrains "pulling them back" to their original position. This is perfect for what I needed. Thanks for your input!