Free Software For 'Nested Shape Determination'?

This one is for those of you who deal in fabrication...jabber asks: "I'm looking for some free and open software that would do 2D 'shape nesting'. If you needed to cut some shapes out of a flat plane of material, for example, how could you arrange the shapes on the material to get the most useful area (and the least amount of wasted material)? Shape Nesting is used for sheet and slab metal cutting, vinyl sign making, and can even be applied to quilting. There are other features to consider like grain direction (in the case of cutting shapes in wood), and variable sizing (since some applications can allow one side of the flat plane to vary), and minimum distance between shapes (since torch-cutting tends to destroy more material than a laser, for example). I'm sure that software like this exists, and I've seen expensive proprietary applications in CAD/CAM, but is there anything available freely? I prefer source-code, since I could then add any of the features that are missing. Any ideas?"

Comments

Funny Coincedence

[nebby]

I recently saw ESR talk at Cornell University, and he actually mentioned this topic. He was talking about how he goes around advising software companies as to what extent they should include open source in their business model. One specific example he drew when the question was asked if he's ever told a company to keep everything closed was this :) He referred to a company who designed a software package for logging companies which would maximize their output by doing the currect cuts on each log (depending on the size, shape, and grain)

Now I may be wrong, but this tells me that your odds of finding such a package are extremely low, or at least that if you do find one, it won't be nearly up to par as its commercial equivalent.

modern day geek.

Re:Funny Coincedence

[Andy Dodd]

It was posted for CSLUG consumption, I don't know what ESR's opinion is on posting for mass consumption. And anyway, the server it was hosted on has been down for about 2 weeks as its primary users (Myself and one other guy) aren't in Ithaca.

I'll talk to Aron (the guy that taped/captured/posted it) and see if he thinks we should contact ESR first about it.

Warning: It's 2 CDs worth (MPEG format, about 2 hours of video.)

Re:Funny Coincedence

[RGRistroph]

Really ? Do you know if the talk is posted somewhere -- his talks don't seem to be archived on his site. (I don't know if anyone would have that recorded or transcribed, anyway.)

It seems to me that the classical no-fetters-for-software argument would say that society would benefit if all the timber mills used the efficient algorithm, thus forcing them to compete in other ways. What should happen is that one company's advantage in a better cut-planner should be only temporary, not artificially extended through government granted monopoly, so that the business has to keep getting better instead of resting on it's one accomplishment. Of course, some of us, including me, believe that the ability to imitate or copy what others are doing should not be restricted even if it is bad for the economy, and that more freedom for individuals is always good.

As for as the software itself, this could be a really interesting project. Ideally, you would want a fairly easy way to specify input and output formats, so that it could be extended to floor plans and circuit layout and other areas were there are already well-estabished formats. You should also be able to plug and play the optimization algorithm and the fitness metrics. This would be really fun to design and implement. It could easily be a thesis project.

calculus

[jeffstar]

We do a lot of things like that in Calculus in High School, so it shouldn't be much harder than that. Those weren't nested but it's the same idea.

We have this technology

[nonlinear]

The company I work for has a software package that can do this. The software can perform optimizations based on any type (and number) of design variables you can define. Currently we are using this technolosy to optimize the shape of structures for energy absorbtion in cars. It's pretty neat, the parts design themselves. However, we've also used this same technique to optimize the floor plans of manufacturing plants. Not to mention the uses for it in solving logistical problems. (For any of you optimization gurus out there, this is not a gradient based technique :)

nested shape determination

[hollywude]

I'm not in the business, so I can't comment on software for this problem, but one obstacle is that the problem is NP-complete, which means that aany software you find will be estimating the best solution, and likely not actually finding it.