1
\$\begingroup\$

Here's my problem: I need to fit rectangles in a polygon but in "certain way".
I have few rectangular shapes (of different sizes) and I need to put them on a polygon.

My first idea was to always try to put them on the top right of the previously placed shape, and if it is not possible, on the bottom left angle of the previously placed shape. It works but it does not looks great, since it does not take into account the placement of the previously placed shape (sometimes the last placed shape is not the most logical).

From this, I imagine we could have a kind of "navmesh": when a shape is placed, it says that nothing more can be placed here and that it needs to find a better place.

Here is how it should look: enter image description here

Imagine I have the above case, and I want to add one rectangular shape... it shoud go like this: enter image description here

... with enough space to welcome a new rectangular shape that could possible fit on the blank space.

So... what I want is to place my shapes on the far top and then on the far left.

Do you guys have any ideas how to do this? Maybe this kind of algorithm already exists and I don't know the name?

Thanks !

\$\endgroup\$
  • 2
    \$\begingroup\$ When you say ' I need to fit rectangles in a polygon but in "certain way"' do you mean that they should be inside the polygon in such a way that they are "sorted" ? Or can they just be randomly inside, as long as they don't collide with each other ? Also when you say "inside a polygon" do you mean the shape could be a triangle or another polygon, or is it always a rectangle? \$\endgroup\$ – TomTsagk Jun 13 '18 at 13:46
  • \$\begingroup\$ By a certain way I mean sorted yes, like if you were placing photo inside a book. And yes, when I say polygon, in my case it will always be a rectangle. thanks! \$\endgroup\$ – Izzo Jun 13 '18 at 13:56
1
\$\begingroup\$

Depending on your use case, Texture Packing (to build Texture Atlas) may be relevant for you. This wiki Article has a section "Explanations and algorithms" with a link to a PDF "A thousand ways to pack the bin"

\$\endgroup\$
  • \$\begingroup\$ Hey! Thanks for you help, the pdf helped me a lot. I'm taking the approach named " Maximal rectangle bottom left" (page 19) and I'd like to know if you have an idea to find the "free area rectangles" ? \$\endgroup\$ – Izzo Jun 13 '18 at 15:45
  • 2
    \$\begingroup\$ This is currently a link only answer. Could you expand and explain what they could do to solve their issue without needing to go to another page? (You can use links to support your post.) \$\endgroup\$ – Alexandre Vaillancourt Jun 13 '18 at 16:38
  • \$\begingroup\$ @Izzo see also Fast Optimizing Rectangle Packing Algorithm for Building CSS Sprites \$\endgroup\$ – Theraot Jul 30 '18 at 8:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.