Computational complexity and shape nesting

Question

I have SVG abirtrary paths which i need to pack as efficiently as possible within a given rectangle(as less waste of space as possible). After some research i found the bin packing algorithms which seems to be dealing with boxes and not curved random shapes(my SVG shapes are quite complex and include beziers etc.).

AFAIK, there is no deterministic algorithm for actually packing abstract shapes.

I wish to be proven wrong here which would be ideal(having a mathematical deterministic method for packing them). In case I am right however and there is not, what would be the best approach to this problem

The subject name is Shape Nesting, Nesting Problem or Nesting Process.

In Shape Nesting there is no single/uniform algorithm or mathematical method for nesting shapes and getting the least space waste possible.

• The 1st method is the packing algorithm(creates an imaginary bounding box for each shape and uses a rectangular 2D algorithm to pack the bounding boxes). This method is fast but the least efficient in regards to space waste.

• The 2nd method is some kind of incremental rotation. The algorithm rotates the shape at incremental steps and checks if it fits in the space. This is better than the packing method in regards to space waste but it is painstakingly slow,

What are some other classroom examples for achieving a solution to this problem?

Answer 1

[Edit1] new answer

as mentioned before bin-packing is NP complete (hard) so forget about algebraic solution known approaches are:

1. generate and test

   either you test all possibility of the problem and remember the best solution or incrementally add items (not all at once) one by one with the same way. It is basically what you are doing now without proper heuristic is unusably slow. But has the best space efficiency (the first one is much better but much slower) O(N!)

2. take advantage of sorting items by size

   something like this it is much faster almost O(N.log(N)) (according to used sorting algorithm). Space efficiency strongly depends on the items size range and count. For rectangular shapes is this the best approach (fastest and usable even for N>1000). For complex shapes is this not a good way but look at it anyway maybe you get some idea ...

3. use of Neural network

   This is extremly vague approach without any warrant of solution but possible best space efficiency/runtime ratio

4. I think there could be some field approach out there

   I sow a few for generating graph layouts. All items create fields (booth attractive and repulsive) so they are moving to semi-stable state.

   • At first all items are at random locations
   • When the movement stop remember best solution and shake all items a little or randomize their position again.
   • Cycle this few times

   This approach is much faster then genere and test and can provide very close solution to it but it can hang in local min/max or oscillate if the fields are not optimally choosed. For example all items can have constant attractive force to each other and repulsive force getting stronger only when the items are very close. You have to prevent overlapping of items (either by stronger repulsion or by collision tests). You have also to create some rotation moment for example with that repulsive force. It differs on any vertex so it creates a rotation moment (that can automatically align similar sides closer together). Also you can have semi-stable state with big distances between items and after finding best solution just turn off repulsion fields so they stick together. Sometimes it can have better results some times not ... here is nice example for graph layout computation

   • Logic to strategically place items in a container with minimum overlapping connections
   • Demo from the same QA

   And here solver for placing sliders in 2D:

   • How to implement a constraint solver for 2-D geometry?

---

[Edit0] old answer before reformulating the question

I am not clear what you want to achieve.

1. have SVG picture and want to separate its parts to rectangular regions
   • as filled as can be
   • least empty space in them
   • no shape change in picture
2. have svg picture and want to change its shapes according to some purpose
   • if this is the case some additional info is needed

[solution for 1]

1. create a list of points for whole SVG in global SVG space (all points are transformed)
   • for line you need add 2 points
   • for rectangles 4 points
   • circle/elipse/bezier/eliptic arc 8 points
2. find local centres of mass
   • use classical approach
   • or can speed things up by computing the average density of points per x,y axis separately and after that just check all combinations of found positions of local max of densities if they really are sub cluster center or not.
3. all sub cluster center is the center of your region
   • now find the most far points which are still part of your cluster (the are close enough to neighbour points)
   • create rectangular area that cover all points from sub cluster.
   • you also can remove all used points from list
4. repeat fro all valid sub clusters
   • until all points are used

another not precise but simpler approach is:

1. find SVG size
2. create planar map of svg with some precision for example int map[256][256].
   • size of map can be constant or with the same aspect as SVG
3. clear map with 0
4. for any point of SVG set related map point to 1 (or inc or whatever)
5. now just segmentate map and you will have find your objects
   • after segmentation you have position and size of all objects
   • so finding of bounding boxes should be easy

Answer 2

You can start with a variant of the rectangle bin-packing algorithm and add rotation. There is a method "Guillotine bin packer" and you can download a paper and a library at github.