# Cutting Optimizer (Nesting)

Source of documentation: [<span>https://translate.google.com/translate?hl=de&amp;sl=fr&amp;tl=en&amp;u=https%3A%2F%2Fwiki.fablab-lannion.org%2Findex.php%3Ftitle%3DCutOptim</span>](https://translate.google.com/translate?hl=de&sl=fr&tl=en&u=https%3A%2F%2Fwiki.fablab-lannion.org%2Findex.php%3Ftitle%3DCutOptim)

# <span class="notranslate">CutOptim</span>

[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/vuM9aIv0VBjAtpMp-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/vuM9aIv0VBjAtpMp-grafik.png)

## <span class="notranslate"> <span class="mw-headline">Presentation</span></span>

<span class="notranslate"> All the users of the laser cutter have probably been confronted with the problem: my drawing does not fit in the wood sheet at my disposal or even in the laser cutter!</span> <span class="notranslate"> To try to remedy this problem, I started writing an optimization program for placing objects on a sheet.</span>   
<span class="notranslate"> For interested readers, this is a variant of a problem well known in the world of optimization (bin packing problem). By doing a little research on the Web, there are also many links to programs performing this task, but the free versions are often very limited, they are content to optimize the cutting of rectangles.</span> <span class="notranslate"> This can help a furniture manufacturer, but it's too limiting for a laser cutter!</span>

  
<span class="notranslate"> This program reads an input SVG file containing the objects to be placed and outputs a second SVG file containing the placed objects.</span>   
<span class="notranslate"> It can be used as is (command line, no GUI!) Or as an extension inkscape which then provides the GUI.</span>

## <span class="notranslate"> <span class="mw-headline">Environment</span></span>

<span class="notranslate"> As mentioned above, this program can be used alone or as an inkscape extension.</span>   
<span class="notranslate"> The work to be done can take a relatively long time, it is better to run it on a modern processor, but if you are in no hurry ...</span>   
<span class="notranslate"> The memory consumption is reasonable, no need to rush to buy new RAMs!</span>

## <span class="notranslate"> S<span class="mw-headline">oftware</span></span>

<span class="notranslate"> First of all as it is a program written in C ++ for a performance issue, it must be compiled on your machine.</span>   
<span class="notranslate"> I wrote this program under Linux / Ubuntu (compiled with gcc), but since there is no system dependency, it should work as it is under any other version of Linux.</span> <span class="notranslate"> For fans of Windows (there is!), I created a Visual Studio project that allows to compile on this platform.</span> <span class="notranslate"> For Mac users, sorry I do not have it, you will have to fend for yourself, but the C ++ used is really standard, it should work as soon as you have access to a compiler.</span> <span class="notranslate"> For information, I did not change the code between Linux and Windows, that's saying!</span>

### <span class="notranslate"> <span class="mw-headline">Linux installation</span></span>

<span class="notranslate"> The code is available here: [https://github.com/thierry7100/CutOptim](https://github.com/thierry7100/CutOptim) For the uninitiated, you clone (or download) the directory, it comes in the form of a .zip archive, which must be extracted.</span> <span class="notranslate"> Then you open a terminal, go to the created directory and launch the commands:</span>

1. <span class="notranslate"> make release</span>
2. <span class="notranslate"> make install: this will copy the software to the directory ~ / .local / bin which is in the list of executable directories, which will allow you to use it directly (this may be specific Ubuntu, it's up to you put the program elsewhere on another system.</span>
3. <span class="notranslate"> make install\_inkscape: this will copy the program to the inkscape extension directory (~ / .config / inkscape / extensions).</span> <span class="notranslate"> If you want to make this extension available for all accounts on your machine, copy the file cutoptim.inx + the executable into / usr / share / inkscape / extensions (you must be root).</span>

<span class="notranslate"> If you have opted for the inkscape extension, at the next start you will have a Fablab / Laser Cutting Optimizer extension</span>

```bash
cd ~
git clone https://github.com/thierry7100/CutOptim.git
cd CutOptim
make release
#make install
 
#try
~/CutOptim/bin/Release/CutOptim
```

### <span class="notranslate"> <span class="mw-headline">Windows installation</span></span>

<span class="notranslate"> The code is available here: [https://github.com/thierry7100/CutOptim](https://github.com/thierry7100/CutOptim).</span>

<span class="notranslate">For the uninitiated, you clone (or download) the directory, it comes in the form of a .zip archive, which must be extracted.</span> <span class="notranslate"> Then you launch Visual Studio, you can get a free version for special purposes, see [Visual Studio Community Edition v17](https://visualstudio.microsoft.com/thank-you-downloading-visual-studio/?sku=Community&rel=17) (You also need to install Windows SDK-Version 10.0.16299.0 within Visual Studio Installer). </span>

[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/l2GZ6d1moOjxUUNl-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/l2GZ6d1moOjxUUNl-grafik.png)

[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/IfZMCwOt0d7KZ8Uj-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/IfZMCwOt0d7KZ8Uj-grafik.png)

<span class="notranslate">Then, once Visual studio started, you have the CutOptim project, then:</span>

1. <span class="notranslate"> You ask to generate the release version of the project if it is not the one that appears in the menu bar.</span>
2. <span class="notranslate"> You choose the platform (x86 or x64) of your choice.</span> <span class="notranslate"> By default the file is configured in x64, if you have a 32bit version of Windows, change to x86.</span>
3. <span class="notranslate"> You click Generate / Generate Solution, the compilation starts and after a few seconds, your program is available.</span>
4. <span class="notranslate"> Then, under windows, better use this program as extension inkscape, the command line is hardly used?</span> <span class="notranslate"> !</span> <span class="notranslate"> To do this, copy the cutoptim.inx and CutOptm / x64 / Release / CutOptim.exe files to the inkscape extensions directory.</span> <span class="notranslate"> This can be found via the Edit / Preferences / System command, but it is usually under C: \\ USERS \\ &lt;Your user name&gt; \\ AppData \\ Roaming / inkscape / extensions.</span> <span class="notranslate"> Attention, to see this directory, you will have to validate the visualization of hidden files under the explorer of files, if it were not done.</span>

<span class="notranslate"> As in Linux, at the next start of inkscape you will have a Fablab / Laser Cutting Optimizer extension</span>

## <span class="notranslate"> <span class="mw-headline">Operation</span></span>

<span class="notranslate"> The input and output format of the files is the SVG format, available on many software programs.</span> <span class="notranslate"> If you use inkscape, it is the native format, the program has been tested in this context.</span> <span class="notranslate"> It should also work with files from other drawing software that generates SVG.</span> <span class="notranslate"> If you have a problem tell me (<thierry@fablab-lannion.org>)</span>   
  
<span class="notranslate"> Description of the process:</span>

1. <span class="notranslate"> The inkscape document (at least its size) can usually be of importance, here it sets the size of the sheet used for cutting.</span> <span class="notranslate"> You will need to set a document size compatible with your material (and the cutter, of course!).</span>
2. <span class="notranslate"> First of all, the program reads the inkscape document, it only considers paths or simple objects.</span> <span class="notranslate"> The texts not transformed in the way, the images ... are ignored.</span> <span class="notranslate"> I therefore advise to turn everything into a path before launching the program.</span> <span class="notranslate"> Inkscape Ctrl + A then Objects in Path (SHIFT + Ctrl + C). Unclosed paths are also ingnorated, the software is only able to process shapes with a closed outline.</span>
3. <span class="notranslate"> Paths can be placed anywhere, in the sheet or out, it does not matter.</span> <span class="notranslate"> To a certain extent, they can even be superimposed (see below).</span>
4. <span class="notranslate"> Then, from these paths, the program creates polygons approaching the paths (with an error of less than 0.1mm on average).</span>
5. <span class="notranslate"> Then the program "enlarges" these polygons to prevent paths from touching each other in the final result.</span> <span class="notranslate"> The size of the enlargement is configurable.</span>
6. <span class="notranslate"> The program then takes these enlarged polygons and will try to place them in a way that is not optimal but good.</span> <span class="notranslate"> Why not optimal because the problem is difficult (complete NP in mathematical terms) and requires a very long time even for simple configurations.</span> <span class="notranslate"> The basic idea here is to start from the largest polygon, then to place the sorted polygons by decreasing size such that a vertex of the polygon to be placed is positioned on a vertex of an already placed polygon.</span> <span class="notranslate"> This reduces the space of possibilities, even if it remains very large!</span>
7. <span class="notranslate"> The "best" configuration is obtained when the size of the convex hull is minimal.</span> <span class="notranslate"> Another mathematical term!</span> <span class="notranslate"> The convex hull is the smallest convex hull containing all points of all plotted polygons.</span> <span class="notranslate"> Intuitively, this maximizes the free space on the plate, which is the desired result.</span> <span class="notranslate"> Be careful, it is not necessarily the smallest rectangle, the convex envelope is not usually a rectangle!</span>
8. <span class="notranslate"> To place the paths, the software is allowed to turn the objects, unless you block this possibility.</span> <span class="notranslate"> Depending on your needs (non-homogeneous material) you may have to limit rotations to 0 and 180 ° for example, or even to block any rotation (this will be the case for example with printed fabric).</span>

### <span class="notranslate"> <span class="mw-headline">Program Options under inkscape</span></span>

[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/UAxKRDEsCI6GW5JB-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/UAxKRDEsCI6GW5JB-grafik.png)

<span class="notranslate"> The program has many options detailed below:</span>

- <span class="notranslate"> Units: Always use the mm, the program is not tested for other choices.</span>
- <span class="notranslate"> Min distance between objects: This is the size of which polygons will be enlarged.</span> <span class="notranslate"> This value must be greater than 0.8mm, the approximation by polygons is not perfect.</span>
- <span class="notranslate"> Max length of single segment: as explained above the software will try to find a good configuration by positioning vertices on other vertices.</span> <span class="notranslate"> It can be interesting in some cases to "add" vertices to have more possibilities.</span> <span class="notranslate"> If an edge is larger than the specified size, it will be broken into multiple segments, with additional vertices.</span> <span class="notranslate"> Do not abuse this option, too low a value will slow down the treatment tremendously.</span> <span class="notranslate"> Do not go below 100mm in most cases, even if the value 0 is allowed to indicate that you do NOT want to use this possibility.</span>
- <span class="notranslate"> Optimizing level: as indicated above the program places the polygons in order of decreasing size (we place the largest pebbles first ...).</span> <span class="notranslate"> This sometimes leads to clearly suboptimal situations.</span> <span class="notranslate"> By increasing this parameter, the software will optimize the placement of a group of N polygons.</span> <span class="notranslate"> This gives better results, but be careful, it considerably increases the treatment time.</span> <span class="notranslate"> Do not exceed 2 or 3, if the default value of 1 does not give good results.</span> <span class="notranslate"> If you draw has 300 vertices already placed (rather low value actually) and you allow rotations in steps of 10 °, use N = 2 will multiply operations by 36 \* 300!</span> <span class="notranslate"> And for N = 3 by (36 \* 300) ²!</span>
- <span class="notranslate"> Keep original layer in output.</span> <span class="notranslate"> If you do not trust!, You can check this option, the original shapes will be kept as well as those placed, but placed in different layers.</span> <span class="notranslate"> You will be able to check the work done.</span>
- <span class="notranslate"> Select option for largest element placement.</span> <span class="notranslate"> The first item can be placed where you want on the page.</span> <span class="notranslate"> Usually at the top left, but the center also gives good results.</span>
- <span class="notranslate"> If this option is checked, the rotation angle of each object will be chosen from 4 to make the edge coincide with one of the two of the vertex on which the object is going. to be positioned.</span> <span class="notranslate"> This option is economical in processing time (at most 4 tests) but can give less good results than the fixing of the angle of rotation.</span> <span class="notranslate"> The results are worse when the segments are very short, if the input form is not a polygon for example.</span>
- <span class="notranslate"> Try rotation by (0 no rotation allowed): This option is incompatible with the previous one, it is only valid if the previous option is NOT checked.</span> <span class="notranslate"> In this case, the objects are positioned on discrete rotation steps.</span> <span class="notranslate"> 0 means that rotations are prohibited, this is useful when the material is not homogeneous.</span> <span class="notranslate"> For MDF, no restrictions, but for wood or even plywood, if you want to respect the direction of the wood, rotations are not advisable.</span> <span class="notranslate"> Choose 180 ° in this case.</span> <span class="notranslate"> Attention, low values ​​greatly increase the calculation time.</span> <span class="notranslate"> With 10 °, there are 36 times more calculations than with 0 °!</span> <span class="notranslate"> If the input shapes are rectangular, a value of 90 ° gives good results.</span>
- <span class="notranslate"> In practice, we often deal with situations or related objects.</span> <span class="notranslate"> For example, a plate with fixing holes.</span> <span class="notranslate"> If this box is checked, the software checks if the path is included in another one, and if it is, it will not process it but link it to the larger path.</span> <span class="notranslate"> Once it is placed, the same transformation (rotation / translation) will be applied to the "small" included object.</span> <span class="notranslate"> Attention the software is not able to recover the space released in holes, you have to leave a little work anyway.</span>
- <span class="notranslate"> Debug file generation: If this box is checked, a debug file (Debug\_CutOptim.txt) is created in the inkscape extension directory.</span> <span class="notranslate"> This can be used to understand what has (badly) happened.</span>

### <span class="notranslate"> <span class="mw-headline">Program options via the command line</span></span>

<span class="notranslate"> The software has pretty much the same options as via inkscape, with some additions.</span>

```bash
eridur-cutoptim.exe [OPTION...] [optional args]
 
  -f, --file SVG Input File     File (default: TestPoly1.svg)
  -o, --output SVG Output File  Output file
      --positional arg          File to be processed
  -h, --help                    Print help
  -d, --distance 1.0            Min distance between paths to be cut
  -m, --max_length 1000.0       Max length of one segment, break than longer
  -l, --optimizing_level 1      Optimizing level, process list_size elements together
      --debug_level 0           Level of debug info in specific debug file
      --debug_file              Generate debug info from inkscape (default: true)
  -k, --original                Output Original layer
  -n, --nested                  Keep nested path together (default: true)
  -y, --layer_output 0          Output internal layers : 1 Input layer, 2 Polygon, 4 Large polygon, 8 Hull layer, 16 Placed Polygon layer, OR these values to output multiple layers
  -a, --angle 90.0              Rotation step
  -r, --free_rot                allow free rotation (default: true)
  -p, --firstpos Position of largest object on the sheet
                                Position of largest object
```

## <span class="notranslate"> <span class="mw-headline">Possible developments / known limitations  
</span></span>

- <span class="notranslate"> No doubt a lot of things, to you to propose and even to realize, the code is open!</span>
- <span class="notranslate">the colors and layers of the objects do not play a role yet</span>
- <span class="notranslate">generates trashy results in a lot of situations</span>
- <span class="notranslate">there is no solution to remove duplicate edges</span>
- <span class="notranslate">there is no solution to allow zero distance between the parts</span>
- <span class="notranslate">known Bugs:</span>
    - <span class="notranslate">does not work for parts which have lines it it (groups with things like living hinge flex pattern) and ignores groups of objects</span>

<table border="1" id="bkmrk-example-input-output" style="border-collapse: collapse; width: 99.9734%;"><colgroup><col style="width: 6.98138%;"></col><col style="width: 47.7528%;"></col><col style="width: 45.2658%;"></col></colgroup><thead><tr><td>**Example**</td><td>**Input**</td><td>**Output**</td></tr></thead><tbody><tr><td>1</td><td>[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/4Q8HZUOpW0MHCjBj-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/4Q8HZUOpW0MHCjBj-grafik.png)

</td><td>[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/PF9MlbArg57oZ3yJ-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/PF9MlbArg57oZ3yJ-grafik.png)

</td></tr><tr><td>2</td><td>[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/Cdihjlg5jvplQ8Aa-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/Cdihjlg5jvplQ8Aa-grafik.png)

</td><td>[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/GWdQONJ6IS6EkWqC-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/GWdQONJ6IS6EkWqC-grafik.png)

</td></tr><tr><td>3</td><td>[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/8NlKQIDeNi7RdmFb-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/8NlKQIDeNi7RdmFb-grafik.png)

</td><td>[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/xjurtJDfLiNMT0Vv-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/xjurtJDfLiNMT0Vv-grafik.png)

</td></tr></tbody></table>

<span class="notranslate">as soon as you have more than one open path (e.g. a line with 2 points) CutOptim **will crash**</span>

<table border="1" id="bkmrk-is-okay-%28open-contou" style="border-collapse: collapse; width: 99.9734%; height: 76.2334px;"><colgroup><col style="width: 49.9668%;"></col><col style="width: 49.9668%;"></col></colgroup><thead><tr style="height: 38.1167px;"><td style="height: 38.1167px;">**is okay (open contour will be deleted while nesting)**</td><td style="height: 38.1167px;">**will crash**</td></tr></thead><tbody><tr style="height: 38.1167px;"><td style="height: 38.1167px;">[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/Nknh3Gk3io3RFOIX-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/Nknh3Gk3io3RFOIX-grafik.png)</td><td style="height: 38.1167px;">[![grafik.png](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/scaled-1680-/4gNDQUkqokRE54OC-grafik.png)](https://wiki.stadtfabrikanten.org/uploads/images/gallery/2025-05/4gNDQUkqokRE54OC-grafik.png)</td></tr></tbody></table>

## <span class="notranslate"> <span class="mw-headline">Bibliography</span></span>

<span class="notranslate"> As indicated the subject is well known in the scientific world, I used the two following articles</span>

- <span class="notranslate"> Waste minimization in irregular stock cutting published in 2014 by Doraid Dalalah, Samir Khrais and Khaled Bataineh.</span> <span class="notranslate"> This article gives the basis of what is achieved.</span>
- <span class="notranslate"> Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation published in 2018 by Ranga P. Abeysooriya, Julia A. Bennell and Antonio Martinez-Sykora</span>

<span class="notranslate"> Good reading !</span>