Computational complexity and form of investment

Question

I have SVG contours that I need to pack into a given rectangle as efficiently as possible (as little as a waste of space). After some research, I discovered bin packing algorithms that seem to deal with boxes, rather than curved random shapes (my SVG forms are quite complex and include Beziers, etc.).

AFAIK, there is no deterministic algorithm for actually wrapping abstract forms.

I would like to be wrong here, which would be ideal (to have a mathematical deterministic method for packing them). If I am right, but no, then what is the best way to approach this problem?

Subject Name - Form Attachment, Attachment Problem, or Attachment Process .

In Shape Nesting, there is no single / unified algorithm or mathematical method for nesting shapes and getting as little space as possible.

• The first method is a packing algorithm (creates an imaginary bounding box for each shape and uses a rectangular 2D algorithm to pack bounding frames). This method is fast but least effective against space waste.

• The 2nd method is a kind of stepwise rotation. The algorithm rotates the figure in steps and checks to see if it fits in space. This is better than the packaging method for space waste, but it is painstakingly slow,

What are some other examples in the class to achieve a solution to this problem?

Answer 1

[Edit1] new answer

as already mentioned, before bin packaging is NP complete (solid), forget about the algebraic solution Known approaches:

• generate and test

  either you check all the possible problems and remember the best solution, or gradually add elements (not all at the same time) one by one the same way. This basically what you are doing now without the right heuristic is unusually slow. But it has better space efficiency (the first is much better, but much slower) O(N!)

• use sorting elements by size

  something like this , it is much faster than almost O(N.log(N)) (according to the sorting algorithm used). Space efficiency is highly dependent on a range of sizes and the number of elements. For rectangular shapes, this is the best approach (the fastest and most convenient even for N>1000 ). For complex forms, this is not a good way, but look at that, maybe you have an idea ...

• use of a neural network

  This is an extremely vague approach without any guarantee of a solution, but the best possible efficiency / runtime ratio is possible.

• I think there might be some kind of field approach

  I sow several to create graphic layouts. All objects create fields (attractive and repulsive), so they become semi-stable.

  • First, all items are in a random place.
  • When the motion stop remembers the best decision and shakes all the objects a little or randomizes their position again.
  • Loop several times

  This approach is much faster than genere and test , and can provide a very close solution, but it can hang in the local min / max or fluctuate if the fields are not optimally selected. For example, all objects can have a constant force of attraction to each other, and the repulsive force becomes stronger only when the objects are very close. You must prevent objects from overlapping (either by strong repulsion or by collision tests). You must also create some moment of rotation, for example, with this repulsive force. It is different at any vertex, so it creates a moment of rotation (which can automatically align similar sides closer to each other). You can also have a semi-stable state with large distances between points, and after finding the best solution, just turn off the repulsion fields so that they stick together. Sometimes this may have better results several times not ... here is a good example for calculating graph layout

  • Logic for strategically placing items in a container with minimal overlapping connections
  • Demonstration with the same QA

  And here is the solver for placing sliders in 2D:

  • How to implement a constraint solver for two-dimensional geometry?

---

[Edit0] old answer before reformulating the question

I do not understand what you want to achieve.

• have an SVG image and want to divide its parts into rectangular areas
  • filled as can be
  • smallest empty space in them
  • image resizing
• have an svg image and want to change its shapes to suit any purpose
  • If so, more information is needed.

[solution for 1]

• create a list of points for the entire SVG in the global SVG space (all points are converted)
  • for the line you need to add 2 points.
  • for rectangles 4 points
  • circle / elipse / bezier / eliptic arc 8 points
• find local centers of mass
  • use the classic approach
  • or it can speed up the process by calculating the average density of points on the x, y axis separately, and then just check all the combinations of the found positions of the local max density if they really are the center of the subclass or not.
• the entire center of the subcluster is the center of your region
  • Now find the farthest points that are still part of your cluster (they are close enough to neighboring points).
  • create a rectangular area that spans all points from the subcluster.
  • you can also delete all used points from the list
• repeat all valid subclasses
  • until all points are used

another inaccurate but simpler approach:

• find svg size
• create a svg planar map with some accuracy, for example, int map [256] [256].
  • card size can be constant or with the same aspect as SVG
• clear card from 0
• for any point SVG binds the associated display point to 1 (or inc or something else)
• now only a segmented map and you will find your objects
  • After segmentation, you have the position and size of all objects
  • therefore, finding bounding boxes should be easy.

Answer 2

You can start with a variant of the rectangle packing algorithm and add a rotation. There is a “Guillotine bin packer” method, and you can upload paper and library to github.