d3js - Transition between 2 paths

Question

I am trying to tween 2 path with the same number of segments. I am using the method described by Mike Bostock here: https://gist.github.com/mbostock/3916621 :

svg.append("path")
    .attr("transform", "translate(180,150)scale(2,2)")
    .attr("d", d0)
    .call(transition, d0, d1);

function transition(path, d0, d1) {
  path.transition()
      .duration(2000)
      .attrTween("d", pathTween(d1, 4))
      .each("end", function() { d3.select(this).call(transition, d1, d0); });
}

function pathTween(d1, precision) {
  return function() {
    var path0 = this,
        path1 = path0.cloneNode(),
        n0 = path0.getTotalLength(),
        n1 = (path1.setAttribute("d", d1), path1).getTotalLength();

    // Uniform sampling of distance based on specified precision.
    var distances = [0], i = 0, dt = precision / Math.max(n0, n1);
    while ((i += dt) < 1) distances.push(i);
    distances.push(1);

    // Compute point-interpolators at each distance.
    var points = distances.map(function(t) {
      var p0 = path0.getPointAtLength(t * n0),
          p1 = path1.getPointAtLength(t * n1);
      return d3.interpolate([p0.x, p0.y], [p1.x, p1.y]);
    });

    return function(t) {
      return t < 1 ? "M" + points.map(function(p) { return p(t); }).join("L") : d1;
    };
  };
}

It gives very good results however I am facing a silly problem. I'd like to find a way to associate a segment from my first path to another one in the 2nd path to get a better tweening.

For example, here: http://jsfiddle.net/2brqoo5p/1/ the 2 path have similar shapes but the tweening is much more complicated than what it could be. Is there a way to fix this?

Many thanks

Answer 1

IMHO...

You'll likely not find any utilities/libaries/etc that will do this for you. You will have to write your own. Or wait for someone to do it for you. Or pay someone.

The only solution I can imagine for this question is fairly tedious. If I find time, I might write up a demo and update this answer. No promises, though. In fact, this code only seems useful for closed loops like in the demo you linked.

Here's the idea in pseudocode. It is rather brute-force, though.

# convert both SVG path `d` attributes from strings to arrays of points
list_1  = convert('#path1')
list_2  = convert('#path2')

min_dist   = 9999
min_pt_set = {}

for each point in list_1 -> (p1)
    for each point in list_2 -> (p2)
        # find the pair of points with the least distance between them
        if (min_dist > dist(p1, p2))
            min_dist = dist(p1, p2)
            min_pt_set = {p1, p2}

# reorder list_1 so that p1 is the first element.
# reorder list_2 so that p2 is the first element.

# convert both lists back into svg path strings

# write the path strings back to the svg `d` attributes.

After reordering you may need some sort of check for direction. If the paths are defined in opposing directions, you may need to reverse the operations of one path.

I don't know of any algorithm that will work for all cases. What you chose will likely depend on the situation you're coding for. You might try 'Least Sum of Squares' or maybe just check points adjacent to p1 and p2 and solve for least distance.

I hope someone has a better solution than I. This is an interesting question.

See Also:

1. http://www.w3.org/TR/SVG/paths.html
2. Scripting <path> data in SVG (reading and modifying) -- mentions method of parsing svg path.