Another week, another problem

-
The project I am working on at the moment requires solving several computer graphics problems. I mentioned a while ago the polygon offsetting problem. Today my problem is about placing polygons on pages to be printed. I want to make the listing as short as possible, thereby packing the polygons in fewer pages is desired.

Trying not to reinvent the wheel I googled around first. Of course the first problem of the googling thing is to figure out what is the popular name of the problem you are interested on (and believe me, I am yet to find an "original" problem never thought and wrote about it before). My first searches suggested Cutting stock problem, but  it was not exactly my case. It is a pity as in 2007 a dynamic programming solution was published. So moving on I found the best fit to be the Bin packing problem.  Again, an NP hard problem.

Wikipedia article suggested the heuristic of the first fit algorithm, that is known to provide good (but not optimal) solutions without too much work. The idea is as follows:
  1. First sort all the polygons in descending order of height.
  2. Next, try to fit a polygon in the available pages, leaving it there at the first fit.
  3. If no room was found, add a new page and fit the polygon in that page.
  4. Repeat until all polygons are allocated to a page.
The first results were much better than my naïve, first implementation: If it does not fit in the current page, just open a new one :-)

I have added later a small variation that tries to add the polygon not only at the current orientation but also rotating it 90 degrees. This has improved a bit the efficiency, but I guess the best approach here might be to find the rotation that creates the minimum bounding box for each polygon before attempting to perform the fit.

Still, I can see that there is still a lot of empty space on the pages of my output and that a more thoughtful approach can take advantage of part of it. Any help is appreciated!!!

Update: Nesting problem is the popular name in the CAD environment.

Comments

Clinton Keith said…
Interesting. I worked at a company that was developing CAD nesting solutions for sheet metal cutting in the mid-80s. Nasty problem, especially given the power of PCs back then.
5:53 pm
misan said…
Thanks Clinton. There are lots of published articles on the topic, using simulated annealing, genetic algorithms, dynamic/integer programing but not a single open source library :-)

I guess I will have to create my own implementation of one of them.
5:50 pm
Post a Comment

Popular posts from this blog

VFD control with Arduino using RS485 link

-
Image
Variable Frequency Drives ( VFD ) allow the control of spindles so speed can accurately be controlled and a detailed acceleration profile for the spindle and reverse rotation can all be handled. In essence a VFD is an three phase inverter for three-phase AC motor. I am using a popular (I mean cheap) Chinese VFD and though the reference manual is not great, I could see there is a built-in RS-485 port. I usually control the start, stop and speed selection using the keyboard on the unit but I thought it will be more useful if I could control everything from the same Arduino is doing our CNC table control. Some cheap RS-485 off eBay and some lines of code later, I can start, stop and change the speed from an Arduino. What a cool thing to have! Some configuration of your VFD are needed before you can use it like that.  You need to set PD163=1 (I am using address 1 in the code). PD=164=1 (for setting serial to 9600bps) and PD165=0 (for using ASCII and 8N1 character format)
Read more

How to get sinusoidal s-curve for a stepper motor

-
Image
After some experimentation, and delving a bit into the math of motion, I realized there can be a significant difference on the motion of a machine by just making small changes. A common and popular approach to smooth one axis of motion is to use a trapezoidal speed pattern, where acceleration and deceleration are uniformly accelerated movements (aka constant acceleration motion) separated by a portion happening at cruising speed. The problem comes with the fact that, while that approach is simple to understand and to code, it does contain sudden changes in the acceleration, that show as spikes on the acceleration derivative, called jerk. These sudden changes in the acceleration translate into undesired vibration in our machines. Most of that can be eliminated by selecting a motion pattern that does not contain sudden changes of acceleration. If we chose a mathematical function for our speed whose second derivative is continuous, then we reduce system vibration quite a lot. One ma
Read more

Stepper motor step signal timing calculation

-
Image
While we use stepper motors in many devices, the timing of the step signals is not always well understood. Most of us can see how a fixed speed is a bad idea unless the speed of motion is really slow, but it is fixed speed what is really to generate with simple code. You just can use the Arduino Blink example to send a fixed frequency of pulses to a stepper motor driver. If too slow, just reduce the delay value. But for most real-life applications variable speed controls will perform better. These systems will speed up the motor to a given maximum speed and it will slow it down to stop at the desired step count. But understanding the math behind this process is sometimes not obvious. Let us start with the simple case of the so-called trapezoidal speed motion profile. Here motion takes place in three phases: acceleration, constant speed (cruising) and deceleration. But the point is how can our code create such a behavior. Stepper motor drivers usually accept two signals to control
Read more