Computational complexity and shape nesting

[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