New package: BinaryTreeRectanglePacking.jl (N-dimensions)

Specific Domains Optimization (Mathematical)
1

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:

fig1

fig2

fig3

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
2

Awesome :slight_smile:
Would be amazing, if we could add that to:
https://github.com/JuliaGeometry/Packing.jl
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 :wink:

3 Likes
3

Great! If I had found your repo first, I probably wouldn’t have written it myself, since it’s basically the same algorithm :laughing:, 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:

  1. 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?
  2. 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