Add path-reorder extension/tool

[oskay]

For the EggBot, we have the "reorder paths for speed" extension. It would be nice to have something similar for AxiDraw.

Possible approach: Add as an extension that is not part of the AxiDraw software, per se-- similar to the Arrange > Restack extension.

Possible approach: Add as a checkbox, and do so automatically at print time.

[oskay]

I have a preliminary beta version of a basic path-reordering extension -- based on an earlier version in the EggBot project -- ready for beta test and attached to this comment. If anyone watching would like to help out with this project, please give this extension a try and let me know how it works for you.

Unlike the earlier version from EggBot, this new version:

1. Works on the entire document, not on selected objects. It turns out that operating on selected objects, rather than the entire document, slows down operation considerably when large numbers objects are selected. It becomes quickly unusable (many minutes) with more than a couple of hundred objects selected. By passing the full document instead, it is possible to operate on documents with up to 10,000 objects in a matter of a minute or so.

2. Is intended to respect grouping. It uses a recursive search through the document, and (should) only sort objects within a group, and within a layer, with a restriction that it is only one layer deep. (That is groups on layers -- which are a kind of group -- are not sorted). In the previous version that worked on selected objects, one could select objects on multiple layers, but then their layer position could be disturbed in the process. For best results, select all objects in all layers, and ungroup all objects before using this extension.

3. Only works on paths. We can add additional object types to process in a future version (using the same object-to-path approach as in AxiDraw control), if this approach seems good otherwise. For the time being, it is recommended to convert all objects to paths before trying it.

4. Does not report any statistics. Or really, interact with you in any other ways either.

Additional notes:

• How to install: Unzip the archive, and copy the contents (two files) into your Inkscape extensions directory.
• This is a very basic extension-- proof of principle only. None the less, it may prove useful already, especially if you're plotting a huge number of paths. We have seen remarkable improvements on some of those files with thousands of separate paths.
• While often helpful, this reordering extension is really just a simple computation, very far from a genuine optimization. It uses what is called a "greedy" algorithm: it starts with a randomly chosen path, and then picks the nearest not-yet-chosen path as the next one in the sequence. However, it will usually pick an ordering that is significantly better than a random or arbitrary walk between the paths. Future versions may have additional optimizations that are applied after this greedy first pass (n-pair swapping, path reversing, etc.). Getting to "perfect" TSP optimization -- with no lines crossing -- is not really helpful. We are after reducing the pen-up movement distance. Getting to 90% of optimal would be a great goal. Getting to 100% is computationally expensive, and not much beter.
• We are separating this optimization into a separate function, rather than building it into AxiDraw control. There are arguments in favor of both locations. As a separate routine, you can easily and directly preview what it will do to your file, before you print. And, you can save the changes to your file, even without printing. This is a big help if you're going to print something 50 times. On the other hand, optimizing during each plot would make the process more seamless, but also would make the machine appear to operate more slowly -- while your computer re-orders the plot.

reorder-prerelease.zip

[Daekkyn]

I've made an extension that might be what you want: https://github.com/Daekkyn/inkscapeOptimizePath

It currently only works with straight line segments though.

[oskay]

@Daekkyn Is this an improvement over the beta above?

[Daekkyn]

@oskay No, this was written from scratch.

[oskay]

Whether it is "better" or not does not depend on whether it was written from scratch.

The one posted above works on any paths, and is designed to respect grouping-- that is the harder part. It looks like yours does not handle groups or layers or transforms, but is more efficient?

[Daekkyn]

Both extensions do different things. The one above simply reorders the path, which is good in some cases. Mine completely rebuilds the drawing by joining as much as possible all the line segments and ensuring that each edge is traversed exactly one time, even if multiple line are overlapping. This allows the pen to stay on paper for much longer which drastically reduced drawing times when there are a lot of line segments. It is a first version that can be improved to handle more types of paths.

[oskay]

I understand the reason for having an extension like this, but for general use, it is going to be problematic to require that the document be fully ungrouped before plotting.

I am concerned about the dependencies with approach. This extension, along with its dependencies, appears (at first glance) to be vastly larger than the existing AxiDraw software.

[Daekkyn]

Removing the dependency should be quite easy, the depth first search algorithm is easy to implement. Handling groups is also quite simple. I will continue to work on it.

[Daekkyn]

I made a pull request for the eggbot reorder path extension: evil-mad/EggBot#91
It can now reverse path direction. I don't know the details of the eggbot project, but I'm not sure it's necessary to have 2 distinct extensions, one for eggbot and one for axidraw.

[oskay]

Yes, we've seen the pull request.