'Modified 2D irregular bin packing

Usually, bin packing algorithms compute the tightest packed solution. I want to calculate the opposite, in my case the solution with the most space between the packed objects is needed - or an approximation thereof. I tried googling for such an algorithm, but I can only find "normal" bin packing solutions.

Given information:

  • n polygons out of at least 10 shapes which can be approximated to rectangles, though I'd prefer polygons
  • a bin, which can be approximated by a rectangle, but again I'd prefer working with a polygon
  • m preloaded objects which can not be moved and have the same available shapes as the polygons that are to be placed

I need an approximation to pack given polygons into a given space with the highest distance between the objects. The bin contains preloaded immovable objects, which, to be honest, I have no idea how to handle.

So here are my questions: How do I even start with this project? Is there a term for packing with the most space between objects? Are there any existing projects/ libraries on that topic? And how does one handle pre-packed objects?

PS: I looked into libnest2D, but I have a hard time understanding what's happening there. So far, I have some code snippets for packing with preloaded objects and for packing with a certain minimum distance between objects, but I couldn't do both at the same time. And again I have no idea how to modify the code to not get the tightest packed solution but the loosest packed one.

PPS: I also asked this in some stack exchange forums a week ago, but so far no answers



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source