`linemerge`: add a global optimiser to improve on the current greedy implementation

[theomega]

I'm using the linemerge operation in combination with splitall a lot to construct a new SVG with new paths hoping that there are as little as possible paths. I'm often not 100% satisfied with the results. Often there would be a solution to capture most/all points in a single path, but the implementation rather only finds small sub-paths.

After looking at the code, I think the current implementation is rather basic:

• It randomly picks a line which has not been processed yet
• Repeats the following:
  • Takes the end point of the current line and searching for another line with the closest starting point within the tolerance
  • If such a line is found, the two lines are joined
  • If no such line can be found, break the repeat

Especially if you have a network of paths (where from a single point is involved in multiple paths), this algorithm is often not finding the optimal solution.

Although, an optimal solution is up for definition. Would it be optimal to have the least amount of paths? Or optimize for having as long as possible paths? Or optimize for paths with as little pen-up-travel as possible?

Every implementation would most likely be a lot more complex (both with regards to run-time but also with regards to implementation), so I'm not sure if this is something which vpype wants do do better.

I don't have a good solution at hand, but I wanted to get the discussion started. Maybe someone has already found some good algorithms for this? Or maybe I'm wrong and doing something wrong.

Example where the linemerge does not achieve great results:

• Input file: https://gist.github.com/29d128cfa1981bc7f0fe7f19934a6a6e
• Vypye only reducing the file down to 2300 paths where there is most likely (but I might be wrong here) actually a version with a single path.

  vpype read lion_0.1.svg stat splitall stat linemerge stat
  ========= Stats ========= 
  Current page size: (1998.0, 1021.0)
  Layer 1
  Length: 153819.32249758646
  Pen-up length: 17457.144205914872
  Total length: 171276.46670350133
  Mean pen-up length: 5.61142533137733
  Median pen-up length: 3.8479002962654754
  Path count: 3112
  Segment count: 21497
  Mean segment length: 7.155385518797342
  Bounds: (641.9081, 53.0234, 1181.3106, 730.4076)
  Totals
  Layer count: 1
  Length: 153819.32249758646
  Pen-up length: 17457.144205914872
  Total length: 171276.46670350133
  Path count: 3112
  Segment count: 21497
  Mean segment length: 7.155385518797342
  Bounds: (641.9081, 53.0234, 1181.3106, 730.4076)
  ========================= 
  ========= Stats ========= 
  Current page size: (1998.0, 1021.0)
  Layer 1
  Length: 153819.32249758742
  Pen-up length: 17457.144205914872
  Total length: 171276.4667035023
  Mean pen-up length: 0.8121112860957793
  Median pen-up length: 0.0
  Path count: 21497
  Segment count: 21497
  Mean segment length: 7.155385518797386
  Bounds: (641.9081, 53.0234, 1181.3106, 730.4076)
  Totals
  Layer count: 1
  Length: 153819.32249758742
  Pen-up length: 17457.144205914872
  Total length: 171276.4667035023
  Path count: 21497
  Segment count: 21497
  Mean segment length: 7.155385518797386
  Bounds: (641.9081, 53.0234, 1181.3106, 730.4076)
  ========================= 
  ========= Stats ========= 
  Current page size: (1998.0, 1021.0)
  Layer 1
  Length: 153824.25821345355
  Pen-up length: 59583.81956929929
  Total length: 213408.07778275284
  Mean pen-up length: 25.917276889647365
  Median pen-up length: 19.6467207808326
  Path count: 2300
  Segment count: 40694
  Mean segment length: 3.780023055326425
  Bounds: (641.9081, 53.0234, 1181.3106, 730.4076)
  Totals
  Layer count: 1
  Length: 153824.25821345355
  Pen-up length: 59583.81956929929
  Total length: 213408.07778275284
  Path count: 2300
  Segment count: 40694
  Mean segment length: 3.780023055326425
  Bounds: (641.9081, 53.0234, 1181.3106, 730.4076)
  ========================= 

[theomega]

Here are some scientific reads: Finding even the longest simple path between two points in a graph (so it contains a vertex at most once) is already NP Hard in general according to wikipedia. That sounds like finding the real optimal solution will be indeed, as I was mentioning computationally intense...

[abey79]

Basically, vpype implements a greedy algorithm, and indeed does not attempt any further optimisation. My philosophy so far has been that there is little benefit to spend 10 minutes running an optimiser in order to cut plotting time down by 5 minutes. Of course, these are made up numbers and there would certainly be advantages to a more optimised algorithm.

Here is a very good article on the related topic of path reordering (linesort): https://nb.paulbutler.org/optimizing-plots-with-tsp-solver/ It's a very interesting read. In this case the goal is to minimise the pen-up distance. In the article, the greedy solution is used to seed a better optimiser. As the article notes, the computational cost increases very rapidly to find a better solution.

All in all, I'd be very open to having a better optimiser in vpype, or at least a prototype of it to have a better idea of the cost/benefits. It's just not very high on my priority list, so I'd be looking for help on this ;)

[theomega]

Yep, I get that and I completely agree with your approach.

With some pen plotters, the quality might improve if you have less pen-up and pen-downs and less travel. So it might not only be about printing time but also about quality...

[abey79]

That's a good point, yes. Let's see if someone would be willing to chime in and help on this front.

[tatarize]

Only a particular number of nodes will be within merging range. In theory that'll give you a set number of paths by definition. If you have 34 odd numbered nodes, you must by definition have 17 different paths. Since odd numbered nodes must start a path or end a path. You will therefore always have the same number of paths, though their lengths can absolutely vary.

[tatarize]

Vypye only reducing the file down to 2300 paths where there is most likely (but I might be wrong here) actually a version with a single path.

No. 2300 likely is the minimum number of paths. Basically it means there are 4600 nodes of an odd order. There are absolutely more than 2 nodes with an odd number of attached segments therefore there can be no single walk which solves the entire graph. This is not a Eulerian graph. https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

[tatarize]

That said there is a pretty easy algorithm to make a non-eulerian graph into a eulerian graph. Namely double it. Then all your nodes are even and by definition there is a single walk that reaches every node. If you wanted to go over the same graph twice, for any contiguous graph you could do it without ever lifting your pen.

[abey79]

Implemented in #266