evil-mad
Reorder paths: path reversal is now possible
Improves the greedy algorithm by allowing paths to be reversed (some path commands like A are not supported). Also, it now handles groups by considering them as a single path so it will not modify the order inside of the group. At the moment, it cannot reverse a group.
Thank you for this contribution, Daekkyn.
I've been working on a separate set of improvements to this extension (diving into groups and so forth), and I'm a little conflicted about merging this for a few reasons.
(1) The big idea implemented (reversing paths in the TSP) is unambiguously a step forward. (2) I am concerned about the non-implemented path commands. The fallback that you've implemented, to simply not reverse those paths is fine and appropriate. It substitutes some efficiency for backwards compatibility: Perfect. (3) It would be good to see tests on a wide-ranging variety of paths, produced in a wide variety of different styles, and by a wide variety of different programs, to ensure that this really does work as intended. (4) It is worth considering a completely different approach to the problem (see below).
To the extent that this extension is intended to produce output that can be used on the EggBot, AxiDraw, or other tools that may be expecting it, one could consider the following approach:
(A) Have the reorder extension "label" each path that should be reversed, perhaps with an attribute like tspRev="true".
(B) Modify the code that plots the resulting SVG to that it plots such-labeled paths in the reverse order.
The potential advantages of this approach are:
- Reversing the paths to print in the opposite order would be essentially trivial, and costs a negligible amount of computation time, if one does so at the point where the path is a list of XY segments ( https://github.com/evil-mad/EggBot/blob/master/inkscape_driver/eggbot.py#L957 ).
- It will work on all SVG paths that can be plotted.
- It requires only trivial testing to establish that it works correctly.
- It improves the speed of the Reorder extension, since it does not also have to perform the path reversing.
The big disadvantage of this approach is:
- It will only reverse paths if the plotting software is looking for that label. It won't work "in general".
I'm open to discussion on it. :)
I have already tested on many SVGs and it worked, but more testing is always good.
I guess adding a label is also an option, but I'm not a big fan of adding a non SVG-standard elements if there is another solution. I agree that it's easier to implement and test. However the speed improvement would be negligible, reversing the paths has a linear complexity and takes milliseconds on practice, even on big files. The ideal solution would be if Inkscape provided an API to access the Reverse command in the Path menu, but it doesn't seem to be possible for now. All in all, I think both options are viable except that this one is already implemented and ready to merge. As there is a UI option to prevent path reversal you would get the same behavior as before so there is no risk.
I was suggesting an attribute on the SVG path tag, not a different element. ( Per the SVG specification, this kind of thing explicitly allowed: "SVG allows inclusion of attributes from foreign namespaces on any SVG element. " https://www.w3.org/TR/SVG/extend.html ).
In any case, let's discuss the code a little bit. Looking a bit deeper, I'm concerned that there are quite a few changes in the code that aren't just about path reversal. This makes it much harder to integrate (or even compare) with the other changes that I've been working on.
- I'd like to see only a single feature change per pull request. How about just adding the reverse function, as a starting point? Yes, there are other things that should be changed, but they really should be on independent PRs so that they can be reviewed and approved independently. (A number of these would fly through.)
- Your flattened path says
#Sorry-- that is not encouraging. There may be more elegant solutions, which might handle an arbitrary number of nesting layers. For example, the solution posted at: https://stackoverflow.com/questions/42421452/convert-and-join-multiple-nested-list-of-lists - Inside the reverse function, I would advocate against adding an error message. An unsupported character in the path may not mean that the path is bad, or that it will plot poorly, just that it can't be optimized in this particular way.
- Yes, we can remove the group handling and only keep the reversal.
- This solution is correct, just not very readable. We can split this line into multiple
for. - I think the user should know about unsupported character as it means that the result will not be as good as it could be.