Free-form nesting

Overview

It is called "free-form nesting" to obtain a layout of free-form plate parts inside a rectangle material in order to cut them out of the rectangle. We are developing a program to generate such layouts of parts automatically. Our program provides layouts for more than one sheets of materials at once, instead of generating a layout for a sheet one by one, so that the human workload for grouping plate parts into sheets is reduced.

Flow of the nesting process

1. The CAD data for plate parts are input and preprocessed; additional lines and labels are removed.
2. A few directions to place is determined for each part. It is done semi-automatically by using a function to detect directions of long edges in a part.
3. Sizes of rectangle materials are input.
4. Parts are nested automatically inside the rectangles.

The input parts are approximated as sets of scanlines and sorted in decreasing order of size:

Similarity between parts are checked, and the sorted list is modified so that similar items are placed in consecutive positions in the list:

The sorted input parts are placed in plates, also approximated as sets of scanlines, either at the leftmost or the bottom-most positions by first-fit decreasing algorithm:

The objective of the algorithm is to minimize the rightmost unused area:

Example of application (parts of ships)

Shapes of parts used for internal structure of a ship are so complicated that it is not trivial to place them inside a rectangle. Parts are categorized with respect to steel types and thickness, and the parts of each category are cut out of rectangle steel plates whose sizes are predetermined as the standard. We want to obtain layouts of parts so as to minimize the cost of the plates. Skilled operators so far have been working for laying out the parts on the screen of the CAD. Our automatic nester can do the same work within equal or less time.

Example of a layout