Sorting and shortest path optimization

[lianzaozi]

After comparative testing, I found that the plotter software does not have the shortest path optimization function. The current sorting is based on the order of reading primitives in the dxf document. The order of storing geometric primitives in the dxf document is only the order of primitive drawing. If the path planning is done in the order of geometric primitive drawing, this will result in a very long empty trip. The path planning that you said with libreCAD is a way. However, when the number of geometric primitives in dxf is relatively large, it is very difficult to use libreCAD for path planning, so I think that the addition of the shortest path planning function in the plotter software can bring great convenience, and can minimize the empty walk The time of the trip.

[svenhb]

Yes, you are right. Sorting by shortest distance I implemented yet (not released). I'm not sure if it is ok to revers drawing direction of some primitives to optimize path lengths a bit more. For pen-plotters it's probably ok, for routers may be not...

[lianzaozi]

The shortest path effect in the open source software dxf2gcode is excellent, you can learn from the algorithm code. I know that some people use Dijkstra's algorithm as the shortest path algorithm.

[lianzaozi]

Generally speaking, the direction can be reversed during the shortest sorting process, which generally has no effect. However, some processing occasions must be processed in a certain order. In fact, you can refer to the method of dxf2gcode. After sorting, you can also allow users to adjust the direction of the geometric primitives.

[lianzaozi]

Hello. I think that when the software reads the dxf file, the software sorts the shortest path of the read geometric primitives according to the algorithm. After the sorting is completed, if the user feels that the sorting result of some geometric primitives is not the result he wants, he can allow the user to adjust the direction of the primitives and the order of certain primitives. The shortest path sorting can be used as the default sorting method of the software. At present, the software has the sorting order according to the drawing order of geometric primitives as an option for the user to choose, which will be better.

[svenhb]

The sorting method on dxf2gcode looks to complicated to me (it's using TSP). Reversing the order of geometric primitives will not work for tangential axis and perhaps not work for other special use cases - if done G-Code level. Perhaps I need to implement a intermediate level to be able to reverse the order of primitives, before translating the "Pen up/down" possibilities.

[lianzaozi]

Genetic Algorithm TSP

This is an experiment of applying Genetic Algorithm to Travelling Salesman Problem, as well as visualizing the algorithm.

Applying Genetic Algorithm to Travelling Salesman Problem http://parano.github.io/GeneticAlgorithm-TSP/

js source code https://github.com/parano/GeneticAlgorithm-TSP

TSP optimization algorithm for LaserGRBL software www.google.it/search?q=traveling+salesman+problem

[svenhb]

Check Sort objects option in new release

[lianzaozi]

The newly added function of sorting according to the shortest path in the software, I think the effect is very good after testing.

[lianzaozi]

I think the shortest path sorting algorithm needs further optimization. In the screenshot below, I think it will take less time to start and finish processing from the position pointed by the blue arrow. Perhaps the current software algorithm may have considered other reasons that I have not considered, leading to the current shortest path sorting method.

This is the dxf file I used for testing

ellipse.zip

[svenhb]

Should be fixed in 1.5.0.1 Check new option

[lianzaozi]

Now check the newly added function option "Allow new start point in closed path" The shortest path sorting effect of the ellipse is very good

I used the circle test and found that the shortest path sorting effect is the best if the circle is subdivided into small straight lines.

When the GCode generated by setting the circle is G02 and G03, the sort result

When the GCode generated by setting the circle is G01, the sort result

[svenhb]

I made an extra function to handle full circle made of G2/G3 to move the start-point arround the circumfence. In my example it worked, in yours not - I will check.

[svenhb]

Check new release for fixed start point in G2 G3

[lianzaozi]

Version V1.5.0.2 of the software will cause some graphics elements in dxf to fail to display. Is the reason related to the newly added "correct start point within G2 / G3 circle" function?

The screenshot image1 below is a screenshot of the software version V1.5.0.2

image2 is a screenshot of the software version V1.5.0.1

setup

test dxf file

test3.zip

[svenhb]

There was a bug in the implementation of #132 Please check new release

[lianzaozi]

Thank you very much.

Now the problem that some geometric primitives cannot be displayed has been solved in the software version V1.5.0.3.

Now I found a problem. When I did not check "Allow new start point in closed path" and "Avoid G2/G3 commands", the GCode generated by circles and arcs was G01. In version V1.5.0.1, if "Avoid G2/G3 commands" and "Avoid G2/G3 commands" are not checked, the GCode generated by circles and arcs is G03 and G02.

I hope that when "Avoid G2/G3 commands" and "Avoid G2/G3 commands" are not checked, the GCode generated by circles and arcs is G03 and G02.

[svenhb]

You need to check the yellow info-line after import....
Some options will check "Avoid G2/G3" internally - like clipping. The applied options can be seen in the yellow line:

[lianzaozi]

Sorry, it was my mistake. I activated the clipping function, which caused the circle and arc to generate G01. This is not a software error.

The circle sorting of version V1.5.0.3 works well

[svenhb]

Thanks for testing