thierry7100 / cutoptim

inkscape extension dealing with 2D-irregular shapes bin packing, used to minimize waste when laser cutting iregular shapes.

Presentation

All the users of 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! To try to solve this problem, I started writing an optimization program for placing objects on a sheet. For interested readers, this is a variant of a well known problem in operational research (bin packing problem). By doing a little search on the Web, there are also links to applications performing this task, but the free versions are often very limited, they are limited optimizing the cutting of rectangles.

This program reads an input SVG file containing the objects to be placed and outputs a second SVG file containing the placed objects. It can be used as is (command line, no graphical interface!) Or as an extension inkscape which then provides the GUI.

Environment

As mentioned above, this program can be used alone or as an inkscape extension. The processing can take a relatively long time, it is better to run this program on a modern processor, but if you are in no hurry ... The memory consumption is reasonable, no need to rush to buy new RAMs! The program has been tested both on Linux and Windows, so it should work on both systems.

The Software

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

Linux installation

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

• make release
• make install: this will copy the software into the directory ~/.local / bin which is in the list of executable directories, which will allow you to use it directly (this may be specific to Ubuntu, to you to put the program elsewhere on another system.
• make install_inkscape: this will copy the program to the inkscape extension directory (~/.config/inkscape / extensions). 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).

If you have opted for the inkscape extension, at the next start you will have a Fablab / Laser Cutting Optimizer extension

Windows installation

The code is available here: 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. Then you launch Visual Studio, you can get a free version for a specific purpose, see https://visualstudio.microsoft.com/thank-you-downloading-visual-studio/?sku=Community&rel=16 Then, once Visual Studio is started, you open the CutOptim project, then:

• You ask to generate the Release version of the project if it is not the one that appears in the menu bar.
• You choose the platform (x86 or x64) of your choice. By default the file is configured in x64, if you have a 32bit version of Windows, change to x86.
• Then choose Generate / Generate Solution, compilation starts and after a few seconds, your program is available.
• Then, under windows, it is better to use this program like extension inkscape, the command line hardly being used? ! To do this, copy the cutoptim.inx and CutOptm / x64 / Release / CutOptim.exe files to the inkscape extensions directory. This can be found via the Edit / Preferences / System command, but it is usually under C: \ USERS \ Your user name\ AppData \ Roaming / inkscape / extensions. 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. As in Linux, the next startup of inkscape you will have a Fablab / Laser Cutting Optimizer

Operation

The input and output format of the files is the SVG format, available on many software programs. If you use inkscape, it is the native format, the program has been tested in this context. It should also work with files from other drawing software that generates SVG. If you have a problem tell me ([email protected])

Description of the process:

• The inkscape document (at least its size) can generally be of importance, here it sets the size of the sheet used for cutting. You will need to set a document size compatible with your material (and the cutter, of course!).
• First, the program reads the inkscape document, it only considers paths or simple objects. The text strings not transformed into paths, the pictures ... are simply ignored. I therefore advise to turn everything into a path before launching the program. Inkscape Ctrl + A then Objects in Path (SHIFT + Ctrl + C). Unclosed paths are also ignored, the software is only able to process shapes with a closed outline.
• The paths can be placed anywhere, on the sheet or outside, it does not matter. To a certain extent, they can even be superimposed (see below).
• Then, from these paths, the program creates polygons approaching the paths (with an error of less than 0.1mm on average).
• Then the program "enlarges" these polygons to prevent paths from touching each other in the final result. The size of the enlargement is configurable.
• The program then takes these enlarged polygons and will try to place them in a way that is not optimal but good. Why not optimal because the problem is difficult (complete NP in mathematical terms) and requires a very long time even for simple configurations. 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. This reduces the space of possibilities, even if it remains very large!
• The "best" configuration is obtained when the size of the convex hull is minimal. Another mathematical term! The convex hull is the smallest convex form containing all points of all plotted polygons. Intuitively, this maximizes the free space on the sheet, which is the desired result. Be careful, it is not necessarily the smallest rectangle, the convex hull is not usually a rectangle!
• To place the paths, the software is allowed to rotate the objects, unless you block this possibility. 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).

Program options as inkscape extension

The program has many options detailed below:

• Units: Always use mm, the program is not tested for other choices. Sorry for inches users, you will have to test this !
• Min distance between objects: This is the size at which the created polygons will be enlarged. This value must be greater than 0.8mm, the approximation by polygons is not perfect.
• Max length of single segment: As explained above the software will try to find a good configuration by positioning vertices on other vertices. It can be interesting in some cases to "add" vertices to have more possibilities. If an edge is longer than the specified size, it will be broken into multiple segments, with additional vertices. Do not abuse this option, too low a value will slow down the treatment tremendously. 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.
• Optimizing level: as indicated above the program places the polygons in order of decreasing size (we place the largest pebbles first ...). This sometimes leads to clearly suboptimal situations. By increasing this parameter, the software will optimize the placement of a group of N polygons. This gives better results, but be careful, it considerably increases the treatment time. Do not exceed 2 or 3, if the default value of 1 does not give good results. 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! And for N = 3 by (36 * 300) ²!
• Keep original layer in output: If you do not trust the program (!), you can check this option, the original shapes will be kept as well as those placed, but placed in different layers. You will be able to check the work done.
• Select option for largest element placement: The first item can be placed where you want on the page. Usually at the top left, but the center also gives good results.
• Allow free rotation of paths, angle parameter not used : If this option is checked, the angle of rotation 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 will be positioned. 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. The results are worse when the segments are very short, if the input form is not a polygon for example.
• 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. In this case, the objects are positioned on discrete rotation steps. 0 means that rotations are prohibited, this is useful when the material is not homogeneous. For MDF, no restrictions, but for wood or even plywood, if you want to respect the direction of the wood, rotations are not advisable. Choose 180 ° in this case. Attention, low values ​​greatly increase the calculation time. With 10 °, there are 36 times more calculations than with 0 °! If the input shapes are rectangular, a value of 90 ° gives good results.
• Attach nested path to the bigger one : In practice, we often deal with situations or related objects. For example, a plate with fixing holes. 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. Once it is placed, the same transformation (rotation / translation) will be applied to the "small" included object. Attention the software is not able to recover the space released in holes, you have to leave a little work anyway.
• Debug file generation: If this box is checked, a debug file (Debug_CutOptim.txt) is created in the inkscape extension directory. This can be used to understand what happened when it goes wrong.

Comand line options

The program has the following options which are listed when typing CutOptim -h from the command line. For the explanations, please refer to the previous chapter, the command line options are the same as when used as an inkscape extension.

thierry@thierry-UX410UAR:~/Programmes/CutOptim$ CutOptim -h

• example command line options Usage: CutOptim [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) -c, --use_cache Set to 1 to enable cache. Cache operation is currently bugged and should NOT be used, default is 0 -q --rect_cost" Add overall rectangle area * factor to cost function. Default factor is 0.0 -p, --firstpos Position of largest object on the sheet

Next steps

The program could be improved, both in performance and optimization result. I will work loosely on both topics, but you want to contribute, you are welcome !

References

As mentionned, this is a well known research topic, I have used to scientific papers when designing this software

1. Waste minimization in irregular stock cutting published in 2014 by Doraid Dalalah, Samir Khrais and Khaled Bataineh. I have used this paper as the main input of this work.
2. 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.

Libraries and other contributions

• For command line processing I have used cxxopts (https://github.com/jarro2783/cxxopts)
• For SVG processing I have used nanosvg (https://github.com/memononen/nanosvg)
• For convex hull computation I have used a result from tyhe project Nayuki (https://www.nayuki.io/page/convex-hull-algorithm)

Thanks a lot for sharing these contributions !

cutoptim's Issues

Packing SVG images

Hello,

quick question - Is there a easy way to make this work for SVG images (basically polygons filled with color and other polygons)?

Im looking for something that could solve bin packing problem of multiple images and this one looks promising.

Test Data

Hi thierry7100,
Your CutOptim is really good,i want to run in my machine，but i do not have test data(like TestPoly1.svg).Could you provide some test data？Thank you very much!

The output from the extension could not be parsed

Creating the issue mostly for others being able to find the solution.
Error:

Solution: #8

There was no SVG output generated. Cannot continue

Not sure what's happening or how to fix it. This message comes up in the dialogue box - There was no SVG output generated. Cannot continue.

Using as an inkscape extension on windows.

I checked the debug file, and it looks like it should be working.

Entering TransformPaths
Shape 0 id:rect1412 Stroke[1 000000] width:0.655465
Shape 1 id:rect1414 Stroke[1 000000] width:0.655466
Shape 2 id:path2750 Stroke[1 000000] width:0.655466
Shape 3 id:path2748 Stroke[1 000000] width:0.655466
Shape 4 id:path2746 Stroke[1 000000] width:0.655466
Shape 5 id:path2736 Stroke[1 000000] width:0.655466
Shape 6 id:path2720 Stroke[1 000000] width:0.655466
Shape 7 id:path2718 Stroke[1 000000] width:0.655466
Shape 8 id:path2716 Stroke[1 000000] width:0.655466
Shape 9 id:path2714 Stroke[1 000000] width:0.655466
Shape 10 id:path2712 Stroke[1 000000] width:0.655466
Shape 11 id:path2688 Stroke[1 000000] width:0.655466
Shape 12 id:path2686 Stroke[1 000000] width:0.655466
Shape 13 id:path2684 Stroke[1 000000] width:0.655466
Shape 14 id:path2682 Stroke[1 000000] width:0.655466
Shape 15 id:path2680 Stroke[1 000000] width:0.655466
Shape 16 id:path2678 Stroke[1 000000] width:0.655466
Shape 17 id:path2676 Stroke[1 000000] width:0.655466
Shape 18 id:path2674 Stroke[1 000000] width:0.655466
Shape 19 id:path2672 Stroke[1 000000] width:0.655466
Shape 20 id:path2660 Stroke[1 000000] width:0.655466
Shape 21 id:path2658 Stroke[1 000000] width:0.655466
Shape 22 id:path2654 Stroke[1 000000] width:0.655466
Shape 23 id:path2652 Stroke[1 000000] width:0.655466
Shape 24 id:path2650 Stroke[1 000000] width:0.655466
Shape 25 id:path2648 Stroke[1 000000] width:0.655466
Shape 26 id:path2646 Stroke[1 000000] width:0.655466
Shape 27 id:path2644 Stroke[1 000000] width:0.655466
Shape 28 id:path2642 Stroke[1 000000] width:0.655466
Shape 29 id:path2640 Stroke[1 000000] width:0.655466
Shape 30 id:path2638 Stroke[1 000000] width:0.655466
Shape 31 id:path2636 Stroke[1 000000] width:0.655466
Shape 32 id:path2634 Stroke[1 000000] width:0.655466
Shape 33 id:path2632 Stroke[1 000000] width:0.655466
Shape 34 id:path2630 Stroke[1 000000] width:0.655466
Shape 35 id:path2628 Stroke[1 000000] width:0.655466
Shape 36 id:path2626 Stroke[1 000000] width:0.655466
Shape 37 id:path2622 Stroke[1 000000] width:0.655466
Shape 38 id:path2620 Stroke[1 000000] width:0.655466
Shape 39 id:path2618 Stroke[1 000000] width:0.655466
Shape 40 id:path2616 Stroke[1 000000] width:0.655466
Shape 41 id:path2610 Stroke[1 000000] width:0.655466
Shape 42 id:path2608 Stroke[1 000000] width:0.655466
Shape 43 id:path2606 Stroke[1 000000] width:0.655466
Shape 44 id:path2604 Stroke[1 000000] width:0.655466
Shape 45 id:path2602 Stroke[1 000000] width:0.655466
Shape 46 id:path2600 Stroke[1 000000] width:0.655466
Shape 47 id:path2598 Stroke[1 000000] width:0.655466
Shape 48 id:path2596 Stroke[1 000000] width:0.655466
Shape 49 id:path2594 Stroke[1 000000] width:0.655466
Shape 50 id:path2592 Stroke[1 000000] width:0.655466
Shape 51 id:path2590 Stroke[1 000000] width:0.655466
Shape 52 id:path2588 Stroke[1 000000] width:0.655466
Shape 53 id:path2586 Stroke[1 000000] width:0.655466
Shape 54 id:path2582 Stroke[1 000000] width:0.655466
Shape 55 id:path2580 Stroke[1 000000] width:0.655466
Shape 56 id:path2578 Stroke[1 000000] width:0.655466
Shape 57 id:path2576 Stroke[1 000000] width:0.655466
Shape 58 id:path2574 Stroke[1 000000] width:0.655466
Shape 59 id:path2572 Stroke[1 000000] width:0.655466
Shape 60 id:path2570 Stroke[1 000000] width:0.655466
Shape 61 id:path2568 Stroke[1 000000] width:0.655466
Shape 62 id:path2566 Stroke[1 000000] width:0.655466
Shape 63 id:path2564 Stroke[1 000000] width:0.655466
Shape 64 id:path2562 Stroke[1 000000] width:0.655466
Shape 65 id:path2560 Stroke[1 000000] width:0.655466
Shape 66 id:path2558 Stroke[1 000000] width:0.655466
Shape 67 id:path2556 Stroke[1 000000] width:0.655466
Shape 68 id:path2554 Stroke[1 000000] width:0.655466
Shape 69 id:path2552 Stroke[1 000000] width:0.655466
Shape 70 id:path2550 Stroke[1 000000] width:0.655466
Shape 71 id:path2548 Stroke[1 000000] width:0.655466
Shape 72 id:path2546 Stroke[1 000000] width:0.655466
Shape 73 id:path2544 Stroke[1 000000] width:0.655466
Shape 74 id:path2542 Stroke[1 000000] width:0.655466
Shape 75 id:path2540 Stroke[1 000000] width:0.655466
Shape 76 id:path2538 Stroke[1 000000] width:0.655466
Shape 77 id:path2536 Stroke[1 000000] width:0.655466
Shape 78 id:path2534 Stroke[1 000000] width:0.655466
Shape 79 id:path2532 Stroke[1 000000] width:0.655466
Shape 80 id:path2530 Stroke[1 000000] width:0.655466
Shape 81 id:path2528 Stroke[1 000000] width:0.655466
Shape 82 id:path2526 Stroke[1 000000] width:0.655466
Shape 83 id:path2524 Stroke[1 000000] width:0.655466
Shape 84 id:path2522 Stroke[1 000000] width:0.655466
Shape 85 id:path2520 Stroke[1 000000] width:0.655466
Shape 86 id:path2518 Stroke[1 000000] width:0.655466
Shape 87 id:path2516 Stroke[1 000000] width:0.655466
Shape 88 id:path2514 Stroke[1 000000] width:0.655466
Shape 89 id:path2512 Stroke[1 000000] width:0.655466
Shape 90 id:path2510 Stroke[1 000000] width:0.655466
Shape 91 id:path2508 Stroke[1 000000] width:0.655466
Shape 92 id:path2506 Stroke[1 000000] width:0.655466
Shape 93 id:path2504 Stroke[1 000000] width:0.655466
Shape 94 id:path2502 Stroke[1 000000] width:0.655466
Shape 95 id:path2500 Stroke[1 000000] width:0.655466
Shape 96 id:path2498 Stroke[1 000000] width:0.655466
Shape 97 id:path2496 Stroke[1 000000] width:0.655466
Shape 98 id:path2494 Stroke[1 000000] width:0.655466
Shape 99 id:path2492 Stroke[1 000000] width:0.655466
Shape 100 id:path2490 Stroke[1 000000] width:0.655466
Shape 101 id:path2488 Stroke[1 000000] width:0.655466
Shape 102 id:path2486 Stroke[1 000000] width:0.655466
Shape 103 id:path2484 Stroke[1 000000] width:0.655466
Shape 104 id:path2482 Stroke[1 000000] width:0.655466
Shape 105 id:path2480 Stroke[1 000000] width:0.655466
Shape 106 id:path2478 Stroke[1 000000] width:0.655466
Shape 107 id:path2476 Stroke[1 000000] width:0.655466
Shape 108 id:path2474 Stroke[1 000000] width:0.655466
Shape 109 id:path2472 Stroke[1 000000] width:0.655466
Shape 110 id:path2470 Stroke[1 000000] width:0.655466
Shape 111 id:path2468 Stroke[1 000000] width:0.655466
Shape 112 id:path2466 Stroke[1 000000] width:0.655466
Shape 113 id:path2464 Stroke[1 000000] width:0.655466
Shape 114 id:path2462 Stroke[1 000000] width:0.655466
Shape 115 id:path2460 Stroke[1 000000] width:0.655466
Shape 116 id:path2458 Stroke[1 000000] width:0.655466
Shape 117 id:path2456 Stroke[1 000000] width:0.655466
Shape 118 id:path2454 Stroke[1 000000] width:0.655466
Shape 119 id:path2452 Stroke[1 000000] width:0.655466
Shape 120 id:path2450 Stroke[1 000000] width:0.655466
Shape 121 id:path2448 Stroke[1 000000] width:0.655466
Shape 122 id:path2446 Stroke[1 000000] width:0.655466
Shape 123 id:path2444 Stroke[1 000000] width:0.655466
Shape 124 id:path2442 Stroke[1 000000] width:0.655466
Shape 125 id:path2440 Stroke[1 000000] width:0.655466
Shape 126 id:path2438 Stroke[1 000000] width:0.655466
Shape 127 id:path2436 Stroke[1 000000] width:0.655466
Shape 128 id:path2434 Stroke[1 000000] width:0.655466
Shape 129 id:path2432 Stroke[1 000000] width:0.655466
Shape 130 id:path2430 Stroke[1 000000] width:0.655466
Shape 131 id:path2428 Stroke[1 000000] width:0.655466
Shape 132 id:path2426 Stroke[1 000000] width:0.655466
Shape 133 id:path2424 Stroke[1 000000] width:0.655466
Shape 134 id:path2422 Stroke[1 000000] width:0.655466
Shape 135 id:path2420 Stroke[1 000000] width:0.655466
Shape 136 id:path2418 Stroke[1 000000] width:0.655466
Shape 137 id:path2416 Stroke[1 000000] width:0.655466
Shape 138 id:path2414 Stroke[1 000000] width:0.655466
Shape 139 id:path2412 Stroke[1 000000] width:0.655466
Shape 140 id:path2410 Stroke[1 000000] width:0.655466
Transform paths pass 2 : checking if paths are included in other ones
Shape_1/Path_0(rect1414_0) is included in rect1412_0
Shape_2/Path_0(path2750_0) is included in rect1412_0
Shape_3/Path_0(path2748_0) is included in rect1412_0
Shape_4/Path_0(path2746_0) is included in rect1412_0
Shape_4/Path_1(path2746_1) is included in rect1412_0
Shape_4/Path_2(path2746_2) is included in rect1412_0
Shape_4/Path_3(path2746_3) is included in rect1412_0
Shape_4/Path_4(path2746_4) is included in rect1412_0
Shape_4/Path_5(path2746_5) is included in rect1412_0
Shape_5/Path_0(path2736_0) is included in rect1412_0
Shape_6/Path_0(path2720_0) is included in rect1412_0
Shape_7/Path_0(path2718_0) is included in rect1412_0
Shape_8/Path_0(path2716_0) is included in rect1412_0
Shape_9/Path_0(path2714_0) is included in rect1412_0
Shape_10/Path_0(path2712_0) is included in rect1412_0
Shape_11/Path_0(path2688_0) is included in rect1412_0
Shape_12/Path_0(path2686_0) is included in rect1412_0
Shape_13/Path_0(path2684_0) is included in rect1412_0
Shape_14/Path_0(path2682_0) is included in rect1412_0
Shape_15/Path_0(path2680_0) is included in rect1412_0
Shape_16/Path_0(path2678_0) is included in rect1412_0
Shape_17/Path_0(path2676_0) is included in rect1412_0
Shape_18/Path_0(path2674_0) is included in rect1412_0
Shape_19/Path_0(path2672_0) is included in rect1412_0
Shape_20/Path_0(path2660_0) is included in rect1412_0
Shape_21/Path_0(path2658_0) is included in rect1412_0
Shape_22/Path_0(path2654_0) is included in rect1412_0
Shape_23/Path_0(path2652_0) is included in rect1412_0
Shape_24/Path_0(path2650_0) is included in rect1412_0
Shape_25/Path_0(path2648_0) is included in rect1412_0
Shape_26/Path_0(path2646_0) is included in rect1412_0
Shape_27/Path_0(path2644_0) is included in rect1412_0
Shape_28/Path_0(path2642_0) is included in rect1412_0
Shape_29/Path_0(path2640_0) is included in rect1412_0
Shape_30/Path_0(path2638_0) is included in rect1412_0
Shape_31/Path_0(path2636_0) is included in rect1412_0
Shape_32/Path_0(path2634_0) is included in rect1412_0
Shape_33/Path_0(path2632_0) is included in rect1412_0
Shape_34/Path_0(path2630_0) is included in rect1412_0
Shape_35/Path_0(path2628_0) is included in rect1412_0
Shape_36/Path_0(path2626_0) is included in rect1412_0
Shape_37/Path_0(path2622_0) is included in rect1412_0
Shape_38/Path_0(path2620_0) is included in rect1412_0
Shape_39/Path_0(path2618_0) is included in rect1412_0
Shape_40/Path_0(path2616_0) is included in rect1412_0
Shape_41/Path_0(path2610_0) is included in rect1412_0
Shape_42/Path_0(path2608_0) is included in rect1412_0
Shape_43/Path_0(path2606_0) is included in rect1412_0
Shape_44/Path_0(path2604_0) is included in rect1412_0
Shape_45/Path_0(path2602_0) is included in rect1412_0
Shape_46/Path_0(path2600_0) is included in rect1412_0
Shape_47/Path_0(path2598_0) is included in rect1412_0
Shape_48/Path_0(path2596_0) is included in rect1412_0
Shape_49/Path_0(path2594_0) is included in rect1412_0
Shape_50/Path_0(path2592_0) is included in rect1412_0
Shape_51/Path_0(path2590_0) is included in rect1412_0
Shape_52/Path_0(path2588_0) is included in rect1412_0
Shape_53/Path_0(path2586_0) is included in rect1412_0
Shape_54/Path_0(path2582_0) is included in rect1412_0
Shape_55/Path_0(path2580_0) is included in rect1412_0
Shape_56/Path_0(path2578_0) is included in rect1412_0
Shape_57/Path_0(path2576_0) is included in rect1412_0
Shape_58/Path_0(path2574_0) is included in rect1412_0
Shape_59/Path_0(path2572_0) is included in rect1412_0
Shape_60/Path_0(path2570_0) is included in rect1412_0
Shape_61/Path_0(path2568_0) is included in rect1412_0
Shape_62/Path_0(path2566_0) is included in rect1412_0
Shape_63/Path_0(path2564_0) is included in rect1412_0
Shape_64/Path_0(path2562_0) is included in rect1412_0
Shape_65/Path_0(path2560_0) is included in rect1412_0
Shape_66/Path_0(path2558_0) is included in rect1412_0
Shape_67/Path_0(path2556_0) is included in rect1412_0
Shape_68/Path_0(path2554_0) is included in rect1412_0
Shape_69/Path_0(path2552_0) is included in rect1412_0
Shape_70/Path_0(path2550_0) is included in rect1412_0
Shape_71/Path_0(path2548_0) is included in rect1412_0
Shape_72/Path_0(path2546_0) is included in rect1412_0
Shape_73/Path_0(path2544_0) is included in rect1412_0
Shape_74/Path_0(path2542_0) is included in rect1412_0
Shape_75/Path_0(path2540_0) is included in rect1412_0
Shape_76/Path_0(path2538_0) is included in rect1412_0
Shape_77/Path_0(path2536_0) is included in rect1412_0
Shape_78/Path_0(path2534_0) is included in rect1412_0
Shape_79/Path_0(path2532_0) is included in rect1412_0
Shape_80/Path_0(path2530_0) is included in rect1412_0
Shape_81/Path_0(path2528_0) is included in rect1412_0
Shape_82/Path_0(path2526_0) is included in rect1412_0
Shape_83/Path_0(path2524_0) is included in rect1412_0
Shape_84/Path_0(path2522_0) is included in rect1412_0
Shape_85/Path_0(path2520_0) is included in rect1412_0
Shape_86/Path_0(path2518_0) is included in rect1412_0
Shape_87/Path_0(path2516_0) is included in rect1412_0
Shape_88/Path_0(path2514_0) is included in rect1412_0
Shape_89/Path_0(path2512_0) is included in rect1412_0
Shape_90/Path_0(path2510_0) is included in rect1412_0
Shape_91/Path_0(path2508_0) is included in rect1412_0
Shape_92/Path_0(path2506_0) is included in rect1412_0
Shape_93/Path_0(path2504_0) is included in rect1412_0
Shape_94/Path_0(path2502_0) is included in rect1412_0
Shape_95/Path_0(path2500_0) is included in rect1412_0
Shape_96/Path_0(path2498_0) is included in rect1412_0
Shape_97/Path_0(path2496_0) is included in rect1412_0
Shape_98/Path_0(path2494_0) is included in rect1412_0
Shape_99/Path_0(path2492_0) is included in rect1412_0
Shape_100/Path_0(path2490_0) is included in rect1412_0
Shape_101/Path_0(path2488_0) is included in rect1412_0
Shape_102/Path_0(path2486_0) is included in rect1412_0
Shape_103/Path_0(path2484_0) is included in rect1412_0
Shape_104/Path_0(path2482_0) is included in rect1412_0
Shape_105/Path_0(path2480_0) is included in rect1412_0
Shape_106/Path_0(path2478_0) is included in rect1412_0
Shape_107/Path_0(path2476_0) is included in rect1412_0
Shape_108/Path_0(path2474_0) is included in rect1412_0
Shape_109/Path_0(path2472_0) is included in rect1412_0
Shape_110/Path_0(path2470_0) is included in rect1412_0
Shape_111/Path_0(path2468_0) is included in rect1412_0
Shape_112/Path_0(path2466_0) is included in rect1412_0
Shape_135/Path_0(path2420_0) is included in rect1412_0
Shape_136/Path_0(path2418_0) is included in rect1412_0
Shape_137/Path_0(path2416_0) is included in rect1412_0
Shape_138/Path_0(path2414_0) is included in rect1412_0
End of Transform paths
---------------- Entering EnlargePaths, elapsed time: 12ms
---------------- Exit EnlargePaths, elapsed time: 13ms

---------------- Entering BreakLongerEdges, elapsed time: 13ms
---------------- Exit BreakLongerEdges, elapsed time: 13ms

-------- BuilSingleListPath : There are 25 paths in the list
Path 0 id: rect1412_0 area 121460mm2 and 121 children
Path 1 id: path2434_0 area 1984.24mm2 and 0 children
Path 2 id: path2438_0 area 1621.38mm2 and 0 children
Path 3 id: path2422_0 area 1256.53mm2 and 0 children
Path 4 id: path2410_0 area 997.252mm2 and 0 children
Path 5 id: path2436_0 area 945.208mm2 and 0 children
Path 6 id: path2454_0 area 744.401mm2 and 0 children
Path 7 id: path2432_0 area 722.95mm2 and 0 children
Path 8 id: path2426_0 area 638.842mm2 and 0 children
Path 9 id: path2430_0 area 613.818mm2 and 0 children
Path 10 id: path2440_0 area 602.627mm2 and 0 children
Path 11 id: path2424_0 area 578.423mm2 and 0 children
Path 12 id: path2412_0 area 524.102mm2 and 0 children
Path 13 id: path2446_0 area 505.993mm2 and 0 children
Path 14 id: path2428_0 area 470.261mm2 and 0 children
Path 15 id: path2460_0 area 419.165mm2 and 0 children
Path 16 id: path2462_0 area 396.234mm2 and 0 children
Path 17 id: path2448_0 area 383.892mm2 and 0 children
Path 18 id: path2464_0 area 349.643mm2 and 0 children
Path 19 id: path2444_0 area 332.887mm2 and 0 children
Path 20 id: path2442_0 area 297.089mm2 and 0 children
Path 21 id: path2456_0 area 257.221mm2 and 0 children
Path 22 id: path2458_0 area 210.555mm2 and 0 children
Path 23 id: path2452_0 area 196.482mm2 and 0 children
Path 24 id: path2450_0 area 109.634mm2 and 0 children
----------- End of BuilSingleListPath ---------------------------

Time: 13.000000ms Enter Optimize with Optimizing level set to 2
----- Placing first polygon (rect1412_0) -----------
Entering PlaceFirst...
First polygon placed with rotation 0.000000° and translation (50.600000,0.000000)
-------------------- Placing Polygon (Free rotation)1: path2434_0 ------------------------------
Elapsed time 0.000000ms, for last polygon 0.000000ms
Level 1: Applying best move : (-415.154408,60.278297)/264.000000° to polygon 2 will place vertex 2 on vertex 3 of polygon 1
new hull with 8 vertices, area 129129.772075 Fixed polygon area 125065.846981
LargeConvexHull area :129129.772075 Cost= 129129.772075
CurFloating.Size=0
Level 2: Applying best move : (-305.757033,-8.214063)/-6.000000° to polygon 1 will place vertex 1 on vertex 0 of polygon 0
new hull with 7 vertices, area 126723.306418 Fixed polygon area 123444.464142
LargeConvexHull area :126723.306418 Cost= 129129.772075
CurFloating.Size=1
Element 1: Translation=(-410.134142,235.957076) rot=-94.000000 Hull area=133901.282495
-------------------- Placing Polygon (Free rotation)2: path2438_0 ------------------------------
Elapsed time 2.000000ms, for last polygon 2.000000ms
Level 1: Applying best move : (-153.453252,54.524191)/76.000000° to polygon 3 will place vertex 4 on vertex 4 of polygon 1
new hull with 8 vertices, area 132922.734133 Fixed polygon area 126322.376693
LargeConvexHull area :132922.734133 Cost= 132922.734133
CurFloating.Size=0
Level 1: Applying best move : (-153.453252,54.524191)/76.000000° to polygon 3 will place vertex 4 on vertex 4 of polygon 1
new hull with 7 vertices, area 132256.426046 Fixed polygon area 126322.376693
LargeConvexHull area :132256.426046 Cost= 132256.426046
CurFloating.Size=0
Level 2: Applying best move : (-409.033983,230.640913)/90.000000° to polygon 2 will place vertex 1 on vertex 3 of polygon 0
new hull with 6 vertices, area 131383.454644 Fixed polygon area 125065.846981
LargeConvexHull area :131383.454644 Cost= 132256.426046
CurFloating.Size=1
Element 1: Translation=(-153.453252,54.524191) rot=76.000000 Hull area=132256.426046
-------------------- Placing Polygon (Free rotation)3: path2422_0 ------------------------------
Elapsed time 4.000000ms, for last polygon 2.000000ms
Level 1: Applying best move : (-56.778443,196.682851)/278.000000° to polygon 4 will place vertex 3 on vertex 0 of polygon 2
new hull with 7 vertices, area 132368.280575 Fixed polygon area 127319.628703
LargeConvexHull area :132368.280575 Cost= 132368.280575
CurFloating.Size=0
Level 1: Applying best move : (-56.778443,196.682851)/278.000000° to polygon 4 will place vertex 3 on vertex 0 of polygon 2
new hull with 7 vertices, area 132256.426046 Fixed polygon area 127319.628703
LargeConvexHull area :132256.426046 Cost= 132256.426046
CurFloating.Size=0
Level 2: Applying best move : (-153.453252,54.524191)/76.000000° to polygon 3 will place vertex 4 on vertex 4 of polygon 1
new hull with 7 vertices, area 132256.426046 Fixed polygon area 126322.376693
LargeConvexHull area :132256.426046 Cost= 132256.426046
CurFloating.Size=1
Element 1: Translation=(-56.778443,196.682851) rot=278.000000 Hull area=132256.426046
-------------------- Placing Polygon (Free rotation)4: path2410_0 ------------------------------
Elapsed time 5.000000ms, for last polygon 1.000000ms
Level 1: Applying best move : (-371.841050,173.574588)/-83.000000° to polygon 5 will place vertex 4 on vertex 2 of polygon 4
new hull with 8 vertices, area 133053.861983 Fixed polygon area 128264.836419
LargeConvexHull area :133053.861983 Cost= 133053.861983
CurFloating.Size=0
Level 2: Applying best move : (-62.196562,202.723901)/165.000000° to polygon 4 will place vertex 0 on vertex 0 of polygon 2
new hull with 8 vertices, area 133053.861983 Fixed polygon area 127319.628703
LargeConvexHull area :133053.861983 Cost= 133053.861983
CurFloating.Size=1
Element 1: Translation=(-371.841050,173.574588) rot=-83.000000 Hull area=133053.861983
-------------------- Placing Polygon (Free rotation)5: path2436_0 ------------------------------
Elapsed time 7.000000ms, for last polygon 2.000000ms

Unable to place polygon 5, aborting

-------------------- Placing Polygon (Free rotation)6: path2454_0 ------------------------------
Elapsed time 7.000000ms, for last polygon 0.000000ms
Level 1: Applying best move : (-271.151197,122.297098)/61.000000° to polygon 7 will place vertex 0 on vertex 0 of polygon 5
new hull with 8 vertices, area 133053.861983 Fixed polygon area 128786.980245
LargeConvexHull area :133053.861983 Cost= 133053.861983
CurFloating.Size=0
Level 2: Applying best move : (-414.061254,-63.936255)/-138.000000° to polygon 6 will place vertex 0 on vertex 2 of polygon 3
new hull with 8 vertices, area 133053.861983 Fixed polygon area 128064.029778
LargeConvexHull area :133053.861983 Cost= 133053.861983
CurFloating.Size=1
Element 1: Translation=(-271.151197,122.297098) rot=61.000000 Hull area=133053.861983
-------------------- Placing Polygon (Free rotation)7: path2432_0 ------------------------------
Elapsed time 11.000000ms, for last polygon 4.000000ms
Level 1: Applying best move : (-174.102829,148.427253)/-273.000000° to polygon 8 will place vertex 0 on vertex 3 of polygon 5
new hull with 9 vertices, area 133252.681918 Fixed polygon area 129425.822000
LargeConvexHull area :133252.681918 Cost= 133252.681918
CurFloating.Size=0
Level 2: Applying best move : (-281.414952,108.866714)/-86.000000° to polygon 7 will place vertex 2 on vertex 3 of polygon 3
new hull with 9 vertices, area 133252.681918 Fixed polygon area 128786.980245
LargeConvexHull area :133252.681918 Cost= 133252.681918
CurFloating.Size=1
Element 1: Translation=(-174.102829,148.427253) rot=-273.000000 Hull area=133252.681918
-------------------- Placing Polygon (Free rotation)8: path2426_0 ------------------------------
Elapsed time 12.000000ms, for last polygon 1.000000ms
Level 1: Applying best move : (-249.109242,137.556799)/-14.000000° to polygon 9 will place vertex 0 on vertex 0 of polygon 6
new hull with 9 vertices, area 133376.387018 Fixed polygon area 130039.640306
LargeConvexHull area :133376.387018 Cost= 133376.387018
CurFloating.Size=0
Level 2: Applying best move : (-174.102829,148.427253)/-273.000000° to polygon 8 will place vertex 0 on vertex 3 of polygon 5
new hull with 9 vertices, area 133252.681918 Fixed polygon area 129425.822000
LargeConvexHull area :133252.681918 Cost= 133376.387018
CurFloating.Size=1
Element 1: Translation=(-250.141586,177.044265) rot=2.000000 Hull area=133450.153584
-------------------- Placing Polygon (Free rotation)9: path2430_0 ------------------------------
Elapsed time 15.000000ms, for last polygon 3.000000ms

Unable to place polygon 9, aborting

-------------------- Placing Polygon (Free rotation)10: path2440_0 ------------------------------
Elapsed time 17.000000ms, for last polygon 2.000000ms

Unable to place polygon 10, aborting

-------------------- Placing Polygon (Free rotation)11: path2424_0 ------------------------------
Elapsed time 17.000000ms, for last polygon 0.000000ms
Level 1: Applying best move : (-24.191495,143.954542)/-49.000000° to polygon 12 will place vertex 2 on vertex 2 of polygon 7
new hull with 8 vertices, area 134311.396222 Fixed polygon area 130528.347324
LargeConvexHull area :134311.396222 Cost= 134311.396222
CurFloating.Size=0
Level 2: Applying best move : (-194.606528,17.569045)/56.000000° to polygon 11 will place vertex 1 on vertex 4 of polygon 1
new hull with 8 vertices, area 134311.396222 Fixed polygon area 130004.245454
LargeConvexHull area :134311.396222 Cost= 134311.396222
CurFloating.Size=1
Element 1: Translation=(-24.191495,143.954542) rot=-49.000000 Hull area=134311.396222
-------------------- Placing Polygon (Free rotation)12: path2412_0 ------------------------------
Elapsed time 20.000000ms, for last polygon 3.000000ms
Level 1: Applying best move : (-422.760167,72.626967)/-83.000000° to polygon 13 will place vertex 1 on vertex 1 of polygon 7
new hull with 8 vertices, area 134311.396222 Fixed polygon area 131034.340242
LargeConvexHull area :134311.396222 Cost= 134311.396222
CurFloating.Size=0
Level 2: Applying best move : (-24.191495,143.954542)/-49.000000° to polygon 12 will place vertex 2 on vertex 2 of polygon 7
new hull with 8 vertices, area 134311.396222 Fixed polygon area 130528.347324
LargeConvexHull area :134311.396222 Cost= 134311.396222
CurFloating.Size=1
Element 1: Translation=(-422.760167,72.626967) rot=-83.000000 Hull area=134311.396222
-------------------- Placing Polygon (Free rotation)13: path2446_0 ------------------------------
Elapsed time 21.000000ms, for last polygon 1.000000ms
Level 1: Applying best move : (-232.622843,173.657029)/265.000000° to polygon 14 will place vertex 2 on vertex 0 of polygon 10
new hull with 9 vertices, area 134529.315843 Fixed polygon area 131504.601010
LargeConvexHull area :134529.315843 Cost= 134529.315843
CurFloating.Size=0
Level 2: Applying best move : (-422.760167,72.626967)/-83.000000° to polygon 13 will place vertex 1 on vertex 1 of polygon 7
new hull with 8 vertices, area 134311.396222 Fixed polygon area 131034.340242
LargeConvexHull area :134311.396222 Cost= 134529.315843
CurFloating.Size=1
Element 1: Translation=(-232.622843,173.657029) rot=265.000000 Hull area=134529.315843
-------------------- Placing Polygon (Free rotation)14: path2428_0 ------------------------------
Elapsed time 23.000000ms, for last polygon 2.000000ms

Unable to place polygon 14, aborting

-------------------- Placing Polygon (Free rotation)15: path2460_0 ------------------------------
Elapsed time 23.000000ms, for last polygon 0.000000ms

Unable to place polygon 15, aborting

-------------------- Placing Polygon (Free rotation)16: path2462_0 ------------------------------
Elapsed time 27.000000ms, for last polygon 4.000000ms

Unable to place polygon 16, aborting

-------------------- Placing Polygon (Free rotation)17: path2448_0 ------------------------------
Elapsed time 27.000000ms, for last polygon 0.000000ms

Unable to place polygon 17, aborting

-------------------- Placing Polygon (Free rotation)18: path2464_0 ------------------------------
Elapsed time 32.000000ms, for last polygon 5.000000ms

Unable to place polygon 18, aborting

-------------------- Placing Polygon (Free rotation)19: path2444_0 ------------------------------
Elapsed time 32.000000ms, for last polygon 0.000000ms
Level 1: Applying best move : (-439.831129,126.960519)/-18.000000° to polygon 20 will place vertex 0 on vertex 0 of polygon 10
new hull with 10 vertices, area 137143.657369 Fixed polygon area 131664.315899
LargeConvexHull area :137143.657369 Cost= 137143.657369
CurFloating.Size=0
Level 2: Applying best move : (-386.048394,198.368241)/-90.000000° to polygon 19 will place vertex 0 on vertex 3 of polygon 0
new hull with 9 vertices, area 136994.928626 Fixed polygon area 131367.226973
LargeConvexHull area :136994.928626 Cost= 137143.657369
CurFloating.Size=1
Element 1: Translation=(-439.831129,126.960519) rot=-18.000000 Hull area=137169.234616
-------------------- Placing Polygon (Free rotation)20: path2442_0 ------------------------------
Elapsed time 37.000000ms, for last polygon 5.000000ms
Level 1: Applying best move : (-448.233072,57.620939)/-59.000000° to polygon 21 will place vertex 2 on vertex 2 of polygon 2
new hull with 10 vertices, area 137569.006014 Fixed polygon area 131921.537234
LargeConvexHull area :137569.006014 Cost= 137569.006014
CurFloating.Size=0
Level 2: Applying best move : (-439.831129,126.960519)/-18.000000° to polygon 20 will place vertex 0 on vertex 0 of polygon 10
new hull with 10 vertices, area 137143.657369 Fixed polygon area 131664.315899
LargeConvexHull area :137143.657369 Cost= 137569.006014
CurFloating.Size=1
Element 1: Translation=(-448.233072,57.620939) rot=-59.000000 Hull area=137569.006014
-------------------- Placing Polygon (Free rotation)21: path2456_0 ------------------------------
Elapsed time 40.000000ms, for last polygon 3.000000ms
Level 1: Applying best move : (-403.124393,65.865812)/-143.000000° to polygon 22 will place vertex 2 on vertex 3 of polygon 11
new hull with 9 vertices, area 137998.846758 Fixed polygon area 132132.092285
LargeConvexHull area :137998.846758 Cost= 137998.846758
CurFloating.Size=0
Level 1: Applying best move : (-446.456877,-200.049139)/-59.000000° to polygon 22 will place vertex 1 on vertex 4 of polygon 8
new hull with 11 vertices, area 137933.217482 Fixed polygon area 132132.092285
LargeConvexHull area :137933.217482 Cost= 137933.217482
CurFloating.Size=0
Level 1: Applying best move : (-403.124393,65.865812)/-143.000000° to polygon 22 will place vertex 2 on vertex 3 of polygon 11
new hull with 12 vertices, area 137871.169351 Fixed polygon area 132132.092285
LargeConvexHull area :137871.169351 Cost= 137871.169351
CurFloating.Size=0
Level 2: Applying best move : (-433.198354,75.973988)/38.000000° to polygon 21 will place vertex 3 on vertex 2 of polygon 2
new hull with 10 vertices, area 137796.451451 Fixed polygon area 131921.537234
LargeConvexHull area :137796.451451 Cost= 137871.169351
CurFloating.Size=1
Element 1: Translation=(-403.124393,65.865812) rot=-143.000000 Hull area=137871.169351
-------------------- Placing Polygon (Free rotation)22: path2458_0 ------------------------------
Elapsed time 43.000000ms, for last polygon 3.000000ms
Level 1: Applying best move : (-450.940497,20.292343)/175.000000° to polygon 23 will place vertex 2 on vertex 4 of polygon 12
new hull with 11 vertices, area 138160.662919 Fixed polygon area 132328.574343
LargeConvexHull area :138160.662919 Cost= 138160.662919
CurFloating.Size=0
Level 1: Applying best move : (-450.940497,20.292343)/175.000000° to polygon 23 will place vertex 2 on vertex 4 of polygon 12
new hull with 12 vertices, area 137871.169351 Fixed polygon area 132328.574343
LargeConvexHull area :137871.169351 Cost= 137871.169351
CurFloating.Size=0
Level 2: Applying best move : (-403.124393,65.865812)/-143.000000° to polygon 22 will place vertex 2 on vertex 3 of polygon 11
new hull with 12 vertices, area 137871.169351 Fixed polygon area 132132.092285
LargeConvexHull area :137871.169351 Cost= 137871.169351
CurFloating.Size=1
Element 1: Translation=(-450.940497,20.292343) rot=175.000000 Hull area=137871.169351
-------------------- Placing Polygon (Free rotation)23: path2452_0 ------------------------------
Elapsed time 46.000000ms, for last polygon 3.000000ms
Level 1: Applying best move : (-452.050223,6.326805)/-1.000000° to polygon 24 will place vertex 4 on vertex 0 of polygon 6
new hull with 12 vertices, area 137871.169351 Fixed polygon area 132438.208510
LargeConvexHull area :137871.169351 Cost= 137871.169351
CurFloating.Size=0
Level 2: Applying best move : (-450.940497,20.292343)/175.000000° to polygon 23 will place vertex 2 on vertex 4 of polygon 12
new hull with 12 vertices, area 137871.169351 Fixed polygon area 132328.574343
LargeConvexHull area :137871.169351 Cost= 137871.169351
CurFloating.Size=1
Element 1: Translation=(-452.050223,6.326805) rot=-1.000000 Hull area=137871.169351
-------------------- Placing Polygon (Free rotation)24: path2450_0 ------------------------------
Elapsed time 50.000000ms, for last polygon 4.000000ms
Level 1: Applying best move : (-452.050223,6.326805)/-1.000000° to polygon 24 will place vertex 4 on vertex 0 of polygon 6
new hull with 12 vertices, area 137871.169351 Fixed polygon area 132438.208510
LargeConvexHull area :137871.169351 Cost= 137871.169351
CurFloating.Size=0
Optimization finished, elapsed time 0.051000s
nbRotation: 8698
nbTranslation: 8698
nbPointInPoly: 81317
nbIntersectPoly: 1882
nbPlacementImpossible: 8633
nbCheckAngles=18556
CacheMiss=18556
CacheHit OK=70
CacheHit KO=26014

Not compilable on Windows using Vistual Studio Community v17

hi,

trying to compile using recent Visual Studio 17 it fails with
"stdafx.cpp": No such file or directory CutOptim C:\Users\tomate\Downloads\CutOptim-master\CutOptim\CutOptim\c1xx

any idea how to adjust this to make it work again? i compiled this 1-2 years ago without problems but maybe with older Visual Studio version or so. on linux it works fine

regards, Mario

Unclosed shapes / open shapes

Hi,
i really love this plugin and using it for some shapes sometimes. But it also generates some messy output for some things like this:

This

gets this after nesting:

it would be great to check if the path is closed or open - we can easily do this in inkscape but i am not sure if its better to preprocess SVG with Python or within CutOptim (by sending a modified, tempoary SVG). Lines, which cannot be nested, should also not be deleted, but get unplaced.

regards, Mario