# New package: BinaryTreeRectanglePacking.jl (N-dimensions)

**URL:** <https://discourse.julialang.org/t/new-package-binarytreerectanglepacking-jl-n-dimensions/44847>\
**Category:** Optimization (Mathematical)\
**Tags:** package\
**Created:** [August 13, 2020, 2:47am UTC](https://discourse.julialang.org/t/new-package-binarytreerectanglepacking-jl-n-dimensions/44847 "2020-08-13T02:47:45Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![OliverEvans96](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oliverevans96/32/4177_2.png) [@OliverEvans96](https://discourse.julialang.org/u/OliverEvans96)\
**Post date:** [August 13, 2020, 2:47am UTC](https://discourse.julialang.org/t/new-package-binarytreerectanglepacking-jl-n-dimensions/44847/1 "2020-08-13T02:47:45Z")

</div>

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](https://blackpawn.com/texts/lightmaps/default.html) about lightmap/sprite packing and generalized it to N dimensions. I took the binary tree datastructure from the [AbstractTrees.jl examples](https://github.com/JuliaCollections/AbstractTrees.jl/tree/master/examples).

[Here is the code on Github](https://github.com/OliverEvans96/BinaryTreeRectanglePacking.jl)

Here are a few example runs in 2D:

![fig1](https://global.discourse-cdn.com/julialang/original/3X/9/6/9676b87b1b2796fd5d5f06e4d22e9a1e5b172408.png)

![fig2](https://global.discourse-cdn.com/julialang/original/3X/4/3/43f7cf6a2a1b5b8ec546064ef037c3e1fdcf3fb6.png)

![fig3](https://global.discourse-cdn.com/julialang/original/3X/4/d/4d68e36a3701850f5d7f1ed8cf5827255cdbd7f8.png)

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

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [August 13, 2020, 8:55am UTC](https://discourse.julialang.org/t/new-package-binarytreerectanglepacking-jl-n-dimensions/44847/2 "2020-08-13T08:55:09Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![OliverEvans96](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oliverevans96/32/4177_2.png) [@OliverEvans96](https://discourse.julialang.org/u/OliverEvans96)\
**Post date:** [August 13, 2020, 3:52pm UTC](https://discourse.julialang.org/t/new-package-binarytreerectanglepacking-jl-n-dimensions/44847/3 "2020-08-13T15:52:48Z")

</div>

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:

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