Hi all,

I needed to pack lots of rectangles into a larger rectangle for my current project, and found that there wasn’t yet a suitable Julia algorithm, so I wrote one up and I thought I’d share it. I took the algorithm from this blog post about lightmap/sprite packing and generalized it to N dimensions. I took the binary tree datastructure from the AbstractTrees.jl examples.

Here is the code on Github

Here are a few example runs in 2D:

This is is my first Julia package I’m posting public, so I’d love any feedback on the algorithm, the code correctness/efficiency, or the package structure. I haven’t actually added it to the package repository yet, but I imagine that isn’t too hard.

Any suggestions/PRs are welcome!

Cheers,

Oliver

5 Likes

Awesome

Would be amazing, if we could add that to:

Where I already ported 2 algorithms!

I think there is quite a bit of value to conform to the same interface and being able to just switch out the algorithm

3 Likes

Great! If I had found your repo first, I probably wouldn’t have written it myself, since it’s basically the same algorithm , although I generalized to N dimensions. I’d be glad to somehow include my generalization into your existing binary tree algorithm in Packing.jl.

Two discussion points are occurring to me:

- If we have an N-dimensional binary tree algorithm and a 2-dimensional guillotine algorithm, it seems like we need to expand the interface to N-dimensions, and throw an error when trying to use the guillotine algorithm for N != 2. Does this seem appropriate? Any thoughts here?
- I went back and forth for a while about using GeometryBasics.jl. On one hand, I like using existing packages and a common interface. But on the other hand, it seems like a
`GeometryBasics.Rect`

must have a position, which is not relevant for the input to a packing problem. So I ended up not using it in an attempt not to require extraneous input data, especially since I wasn’t using any `GeometryBasics`

methods. Do you know if it’s possible to have a size-only `Rect`

? Does the extra `0, 0`

not seem like a big deal to you? Do you think it’s advantageous to use the existing package in this situation?

Thanks for the reply - I’d love to hear your thoughts!

Oliver