1 function d3_svg_line(projection) {

     2   var x = d3_svg_lineX,

     3       y = d3_svg_lineY,

     4       interpolate = "linear",

     5       interpolator = d3_svg_lineInterpolators[interpolate],

     6       tension = .7;

     7 

     8   function line(d) {

     9     return d.length < 1 ? null : "M" + interpolator(projection(d3_svg_linePoints(this, d, x, y)), tension);

    10   }

    11 

    12   line.x = function(v) {

    13     if (!arguments.length) return x;

    14     x = v;

    15     return line;

    16   };

    17 

    18   line.y = function(v) {

    19     if (!arguments.length) return y;

    20     y = v;

    21     return line;

    22   };

    23 

    24   line.interpolate = function(v) {

    25     if (!arguments.length) return interpolate;

    26     interpolator = d3_svg_lineInterpolators[interpolate = v];

    27     return line;

    28   };

    29 

    30   line.tension = function(v) {

    31     if (!arguments.length) return tension;

    32     tension = v;

    33     return line;

    34   };

    35 

    36   return line;

    37 }

    38 

    39 d3.svg.line = function() {

    40   return d3_svg_line(Object);

    41 };

    42 

    43 // Converts the specified array of data into an array of points

    44 // (x-y tuples), by evaluating the specified `x` and `y` functions on each

    45 // data point. The `this` context of the evaluated functions is the specified

    46 // "self" object; each function is passed the current datum and index.

    47 function d3_svg_linePoints(self, d, x, y) {

    48   var points = [],

    49       i = -1,

    50       n = d.length,

    51       fx = typeof x === "function",

    52       fy = typeof y === "function",

    53       value;

    54   if (fx && fy) {

    55     while (++i < n) points.push([

    56       x.call(self, value = d[i], i),

    57       y.call(self, value, i)

    58     ]);

    59   } else if (fx) {

    60     while (++i < n) points.push([x.call(self, d[i], i), y]);

    61   } else if (fy) {

    62     while (++i < n) points.push([x, y.call(self, d[i], i)]);

    63   } else {

    64     while (++i < n) points.push([x, y]);

    65   }

    66   return points;

    67 }

    68 

    69 // The default `x` property, which references d[0].

    70 function d3_svg_lineX(d) {

    71   return d[0];

    72 }

    73 

    74 // The default `y` property, which references d[1].

    75 function d3_svg_lineY(d) {

    76   return d[1];

    77 }

    78 

    79 // The various interpolators supported by the `line` class.

    80 var d3_svg_lineInterpolators = {

    81   "linear": d3_svg_lineLinear,

    82   "step-before": d3_svg_lineStepBefore,

    83   "step-after": d3_svg_lineStepAfter,

    84   "basis": d3_svg_lineBasis,

    85   "basis-open": d3_svg_lineBasisOpen,

    86   "basis-closed": d3_svg_lineBasisClosed,

    87   "bundle": d3_svg_lineBundle,

    88   "cardinal": d3_svg_lineCardinal,

    89   "cardinal-open": d3_svg_lineCardinalOpen,

    90   "cardinal-closed": d3_svg_lineCardinalClosed,

    91   "monotone": d3_svg_lineMonotone

    92 };

    93 

    94 // Linear interpolation; generates "L" commands.

    95 function d3_svg_lineLinear(points) {

    96   var i = 0,

    97       n = points.length,

    98       p = points[0],

    99       path = [p[0], ",", p[1]];

   100   while (++i < n) path.push("L", (p = points[i])[0], ",", p[1]);

   101   return path.join("");

   102 }

   103 

   104 // Step interpolation; generates "H" and "V" commands.

   105 function d3_svg_lineStepBefore(points) {

   106   var i = 0,

   107       n = points.length,

   108       p = points[0],

   109       path = [p[0], ",", p[1]];

   110   while (++i < n) path.push("V", (p = points[i])[1], "H", p[0]);

   111   return path.join("");

   112 }

   113 

   114 // Step interpolation; generates "H" and "V" commands.

   115 function d3_svg_lineStepAfter(points) {

   116   var i = 0,

   117       n = points.length,

   118       p = points[0],

   119       path = [p[0], ",", p[1]];

   120   while (++i < n) path.push("H", (p = points[i])[0], "V", p[1]);

   121   return path.join("");

   122 }

   123 

   124 // Open cardinal spline interpolation; generates "C" commands.

   125 function d3_svg_lineCardinalOpen(points, tension) {

   126   return points.length < 4

   127       ? d3_svg_lineLinear(points)

   128       : points[1] + d3_svg_lineHermite(points.slice(1, points.length - 1),

   129         d3_svg_lineCardinalTangents(points, tension));

   130 }

   131 

   132 // Closed cardinal spline interpolation; generates "C" commands.

   133 function d3_svg_lineCardinalClosed(points, tension) {

   134   return points.length < 3

   135       ? d3_svg_lineLinear(points)

   136       : points[0] + d3_svg_lineHermite((points.push(points[0]), points),

   137         d3_svg_lineCardinalTangents([points[points.length - 2]]

   138         .concat(points, [points[1]]), tension));

   139 }

   140 

   141 // Cardinal spline interpolation; generates "C" commands.

   142 function d3_svg_lineCardinal(points, tension, closed) {

   143   return points.length < 3

   144       ? d3_svg_lineLinear(points)

   145       : points[0] + d3_svg_lineHermite(points,

   146         d3_svg_lineCardinalTangents(points, tension));

   147 }

   148 

   149 // Hermite spline construction; generates "C" commands.

   150 function d3_svg_lineHermite(points, tangents) {

   151   if (tangents.length < 1

   152       || (points.length != tangents.length

   153       && points.length != tangents.length + 2)) {

   154     return d3_svg_lineLinear(points);

   155   }

   156 

   157   var quad = points.length != tangents.length,

   158       path = "",

   159       p0 = points[0],

   160       p = points[1],

   161       t0 = tangents[0],

   162       t = t0,

   163       pi = 1;

   164 

   165   if (quad) {

   166     path += "Q" + (p[0] - t0[0] * 2 / 3) + "," + (p[1] - t0[1] * 2 / 3)

   167         + "," + p[0] + "," + p[1];

   168     p0 = points[1];

   169     pi = 2;

   170   }

   171 

   172   if (tangents.length > 1) {

   173     t = tangents[1];

   174     p = points[pi];

   175     pi++;

   176     path += "C" + (p0[0] + t0[0]) + "," + (p0[1] + t0[1])

   177         + "," + (p[0] - t[0]) + "," + (p[1] - t[1])

   178         + "," + p[0] + "," + p[1];

   179     for (var i = 2; i < tangents.length; i++, pi++) {

   180       p = points[pi];

   181       t = tangents[i];

   182       path += "S" + (p[0] - t[0]) + "," + (p[1] - t[1])

   183           + "," + p[0] + "," + p[1];

   184     }

   185   }

   186 

   187   if (quad) {

   188     var lp = points[pi];

   189     path += "Q" + (p[0] + t[0] * 2 / 3) + "," + (p[1] + t[1] * 2 / 3)

   190         + "," + lp[0] + "," + lp[1];

   191   }

   192 

   193   return path;

   194 }

   195 

   196 // Generates tangents for a cardinal spline.

   197 function d3_svg_lineCardinalTangents(points, tension) {

   198   var tangents = [],

   199       a = (1 - tension) / 2,

   200       p0,

   201       p1 = points[0],

   202       p2 = points[1],

   203       i = 1,

   204       n = points.length;

   205   while (++i < n) {

   206     p0 = p1;

   207     p1 = p2;

   208     p2 = points[i];

   209     tangents.push([a * (p2[0] - p0[0]), a * (p2[1] - p0[1])]);

   210   }

   211   return tangents;

   212 }

   213 

   214 // B-spline interpolation; generates "C" commands.

   215 function d3_svg_lineBasis(points) {

   216   if (points.length < 3) return d3_svg_lineLinear(points);

   217   var i = 1,

   218       n = points.length,

   219       pi = points[0],

   220       x0 = pi[0],

   221       y0 = pi[1],

   222       px = [x0, x0, x0, (pi = points[1])[0]],

   223       py = [y0, y0, y0, pi[1]],

   224       path = [x0, ",", y0];

   225   d3_svg_lineBasisBezier(path, px, py);

   226   while (++i < n) {

   227     pi = points[i];

   228     px.shift(); px.push(pi[0]);

   229     py.shift(); py.push(pi[1]);

   230     d3_svg_lineBasisBezier(path, px, py);

   231   }

   232   i = -1;

   233   while (++i < 2) {

   234     px.shift(); px.push(pi[0]);

   235     py.shift(); py.push(pi[1]);

   236     d3_svg_lineBasisBezier(path, px, py);

   237   }

   238   return path.join("");

   239 }

   240 

   241 // Open B-spline interpolation; generates "C" commands.

   242 function d3_svg_lineBasisOpen(points) {

   243   if (points.length < 4) return d3_svg_lineLinear(points);

   244   var path = [],

   245       i = -1,

   246       n = points.length,

   247       pi,

   248       px = [0],

   249       py = [0];

   250   while (++i < 3) {

   251     pi = points[i];

   252     px.push(pi[0]);

   253     py.push(pi[1]);

   254   }

   255   path.push(d3_svg_lineDot4(d3_svg_lineBasisBezier3, px)

   256     + "," + d3_svg_lineDot4(d3_svg_lineBasisBezier3, py));

   257   --i; while (++i < n) {

   258     pi = points[i];

   259     px.shift(); px.push(pi[0]);

   260     py.shift(); py.push(pi[1]);

   261     d3_svg_lineBasisBezier(path, px, py);

   262   }

   263   return path.join("");

   264 }

   265 

   266 // Closed B-spline interpolation; generates "C" commands.

   267 function d3_svg_lineBasisClosed(points) {

   268   var path,

   269       i = -1,

   270       n = points.length,

   271       m = n + 4,

   272       pi,

   273       px = [],

   274       py = [];

   275   while (++i < 4) {

   276     pi = points[i % n];

   277     px.push(pi[0]);

   278     py.push(pi[1]);

   279   }

   280   path = [

   281     d3_svg_lineDot4(d3_svg_lineBasisBezier3, px), ",",

   282     d3_svg_lineDot4(d3_svg_lineBasisBezier3, py)

   283   ];

   284   --i; while (++i < m) {

   285     pi = points[i % n];

   286     px.shift(); px.push(pi[0]);

   287     py.shift(); py.push(pi[1]);

   288     d3_svg_lineBasisBezier(path, px, py);

   289   }

   290   return path.join("");

   291 }

   292 

   293 function d3_svg_lineBundle(points, tension) {

   294   var n = points.length - 1,

   295       x0 = points[0][0],

   296       y0 = points[0][1],

   297       dx = points[n][0] - x0,

   298       dy = points[n][1] - y0,

   299       i = -1,

   300       p,

   301       t;

   302   while (++i <= n) {

   303     p = points[i];

   304     t = i / n;

   305     p[0] = tension * p[0] + (1 - tension) * (x0 + t * dx);

   306     p[1] = tension * p[1] + (1 - tension) * (y0 + t * dy);

   307   }

   308   return d3_svg_lineBasis(points);

   309 }

   310 

   311 // Returns the dot product of the given four-element vectors.

   312 function d3_svg_lineDot4(a, b) {

   313   return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + a[3] * b[3];

   314 }

   315 

   316 // Matrix to transform basis (b-spline) control points to bezier

   317 // control points. Derived from FvD 11.2.8.

   318 var d3_svg_lineBasisBezier1 = [0, 2/3, 1/3, 0],

   319     d3_svg_lineBasisBezier2 = [0, 1/3, 2/3, 0],

   320     d3_svg_lineBasisBezier3 = [0, 1/6, 2/3, 1/6];

   321 

   322 // Pushes a "C" Bézier curve onto the specified path array, given the

   323 // two specified four-element arrays which define the control points.

   324 function d3_svg_lineBasisBezier(path, x, y) {

   325   path.push(

   326       "C", d3_svg_lineDot4(d3_svg_lineBasisBezier1, x),

   327       ",", d3_svg_lineDot4(d3_svg_lineBasisBezier1, y),

   328       ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, x),

   329       ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, y),

   330       ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, x),

   331       ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, y));

   332 }

   333 

   334 // Computes the slope from points p0 to p1.

   335 function d3_svg_lineSlope(p0, p1) {

   336   return (p1[1] - p0[1]) / (p1[0] - p0[0]);

   337 }

   338 

   339 // Compute three-point differences for the given points.

   340 // http://en.wikipedia.org/wiki/Cubic_Hermite_spline#Finite_difference

   341 function d3_svg_lineFiniteDifferences(points) {

   342   var i = 0,

   343       j = points.length - 1,

   344       m = [],

   345       p0 = points[0],

   346       p1 = points[1],

   347       d = m[0] = d3_svg_lineSlope(p0, p1);

   348   while (++i < j) {

   349     m[i] = d + (d = d3_svg_lineSlope(p0 = p1, p1 = points[i + 1]));

   350   }

   351   m[i] = d;

   352   return m;

   353 }

   354 

   355 // Interpolates the given points using Fritsch-Carlson Monotone cubic Hermite

   356 // interpolation. Returns an array of tangent vectors. For details, see

   357 // http://en.wikipedia.org/wiki/Monotone_cubic_interpolation

   358 function d3_svg_lineMonotoneTangents(points) {

   359   var tangents = [],

   360       d,

   361       a,

   362       b,

   363       s,

   364       m = d3_svg_lineFiniteDifferences(points),

   365       i = -1,

   366       j = points.length - 1;

   367 

   368   // The first two steps are done by computing finite-differences:

   369   // 1. Compute the slopes of the secant lines between successive points.

   370   // 2. Initialize the tangents at every point as the average of the secants.

   371 

   372   // Then, for each segment…

   373   while (++i < j) {

   374     d = d3_svg_lineSlope(points[i], points[i + 1]);

   375 

   376     // 3. If two successive yk = y{k + 1} are equal (i.e., d is zero), then set

   377     // mk = m{k + 1} = 0 as the spline connecting these points must be flat to

   378     // preserve monotonicity. Ignore step 4 and 5 for those k.

   379 

   380     if (Math.abs(d) < 1e-6) {

   381       m[i] = m[i + 1] = 0;

   382     } else {

   383       // 4. Let ak = mk / dk and bk = m{k + 1} / dk.

   384       a = m[i] / d;

   385       b = m[i + 1] / d;

   386 

   387       // 5. Prevent overshoot and ensure monotonicity by restricting the

   388       // magnitude of vector <ak, bk> to a circle of radius 3.

   389       s = a * a + b * b;

   390       if (s > 9) {

   391         s = d * 3 / Math.sqrt(s);

   392         m[i] = s * a;

   393         m[i + 1] = s * b;

   394       }

   395     }

   396   }

   397 

   398   // Compute the normalized tangent vector from the slopes. Note that if x is

   399   // not monotonic, it's possible that the slope will be infinite, so we protect

   400   // against NaN by setting the coordinate to zero.

   401   i = -1; while (++i <= j) {

   402     s = (points[Math.min(j, i + 1)][0] - points[Math.max(0, i - 1)][0])

   403       / (6 * (1 + m[i] * m[i]));

   404     tangents.push([s || 0, m[i] * s || 0]);

   405   }

   406 

   407   return tangents;

   408 }

   409 

   410 function d3_svg_lineMonotone(points) {

   411   return points.length < 3

   412       ? d3_svg_lineLinear(points)

   413       : points[0] +

   414         d3_svg_lineHermite(points, d3_svg_lineMonotoneTangents(points));

   415 }