I am working with metallic shapes which are curved and highly irregular. The initial order of them is random and by default they are merely sorted by size, which is simple. However the resulting order is neither optimal, nor "good".

A smaller frame means less material used, so an optimization is desired. The shapes themselves are planar, so the ordering happens in a 2D space. Ordering is also only relevant with respect to x-axis, meaning that elements are not placed above/below/diagonal to each other, but always one after the other.

Bruteforcing this is non-viable, because I am aware that this problem is NP-hard, since in order to find all possible frame-lengths I'd first need all permutations of which there are n!. In addition to this the calculation of the frame length is rather costly.

A frame with metallic shapes can be envisioned like this:

[ (((c((cCCc( ]

Where the curved symbols represent the metallic shapes and the outer brackets are the frame borders.

So far I am left thinking that finding the optimal solution is not feasible, but finding a good solution might be. There is a lot on material available on optimization and on cutting the cost of material use, mainly I am looking for advice on literature that comes as close to my challenge as possible. What should I look into?

  • $\begingroup$ If I understand well, this is a Travelling Salesman Problem. For every pair of shapes, you can compute a distance along x-axis between their centers, if they are one after the other. The aim is to find the best route visiting all shapes. $\endgroup$ – Vince Apr 3 at 9:22
  • $\begingroup$ It is. Though the problem is also with finding every possible pair of shapes. Assume we have 4 shapes, abcd. Then the is 6 possible pairings: ab, ac, ad, bc, bd, cd. However with ab != ba this amount doubles, so we can think of the graph as directional, i.e. like finding the optimal path. This reduces the problem, but is still an issue. Finding the pairings for 20-30 elements already takes enormous amounts of time, therefore a greedy approach may be the way to go. $\endgroup$ – Mär Apr 3 at 9:29
  • $\begingroup$ Ok, I think an heuristic solution is highly dependant of the type of shapes considered/expected. Maybe you can give some precisions on it to bound the problem. Of course in the very general case, solving shapes overlap is already a very tough problem. $\endgroup$ – Vince Apr 3 at 9:57
  • $\begingroup$ As described we are dealing with metallic lines in the shape irregular curves of a specified thickness. I am looking into simplifying the problem to work with convex shapes (or something close to that) instead of the original shape itself, but it is hard to describe the shapes in question more closely by text and I cannot show a picture. $\endgroup$ – Mär Apr 3 at 10:12

Your Answer

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

Browse other questions tagged or ask your own question.