1 /**
  2  * @private Converts the specified b-spline curve segment to a bezier curve
  3  * compatible with SVG "C".
  4  *
  5  * @param p0 the first control point.
  6  * @param p1 the second control point.
  7  * @param p2 the third control point.
  8  * @param p3 the fourth control point.
  9  */
 10 pv.SvgScene.pathBasis = (function() {
 11 
 12   /**
 13    * Matrix to transform basis (b-spline) control points to bezier control
 14    * points. Derived from FvD 11.2.8.
 15    */
 16   var basis = [
 17     [ 1/6, 2/3, 1/6,   0 ],
 18     [   0, 2/3, 1/3,   0 ],
 19     [   0, 1/3, 2/3,   0 ],
 20     [   0, 1/6, 2/3, 1/6 ]
 21   ];
 22 
 23   /**
 24    * Returns the point that is the weighted sum of the specified control points,
 25    * using the specified weights. This method requires that there are four
 26    * weights and four control points.
 27    */
 28   function weight(w, p0, p1, p2, p3) {
 29     return {
 30       x: w[0] * p0.left + w[1] * p1.left + w[2] * p2.left + w[3] * p3.left,
 31       y: w[0] * p0.top  + w[1] * p1.top  + w[2] * p2.top  + w[3] * p3.top
 32     };
 33   }
 34 
 35   var convert = function(p0, p1, p2, p3) {
 36     var b1 = weight(basis[1], p0, p1, p2, p3),
 37         b2 = weight(basis[2], p0, p1, p2, p3),
 38         b3 = weight(basis[3], p0, p1, p2, p3);
 39     return "C" + b1.x + "," + b1.y
 40          + "," + b2.x + "," + b2.y
 41          + "," + b3.x + "," + b3.y;
 42   };
 43 
 44   convert.segment = function(p0, p1, p2, p3) {
 45     var b0 = weight(basis[0], p0, p1, p2, p3),
 46         b1 = weight(basis[1], p0, p1, p2, p3),
 47         b2 = weight(basis[2], p0, p1, p2, p3),
 48         b3 = weight(basis[3], p0, p1, p2, p3);
 49     return "M" + b0.x + "," + b0.y
 50          + "C" + b1.x + "," + b1.y
 51          + "," + b2.x + "," + b2.y
 52          + "," + b3.x + "," + b3.y;
 53   };
 54 
 55   return convert;
 56 })();
 57 
 58 /**
 59  * @private Interpolates the given points using the basis spline interpolation.
 60  * Returns an SVG path without the leading M instruction to allow path
 61  * appending.
 62  *
 63  * @param points the array of points.
 64  */
 65 pv.SvgScene.curveBasis = function(points) {
 66   if (points.length <= 2) return "";
 67   var path = "",
 68       p0 = points[0],
 69       p1 = p0,
 70       p2 = p0,
 71       p3 = points[1];
 72   path += this.pathBasis(p0, p1, p2, p3);
 73   for (var i = 2; i < points.length; i++) {
 74     p0 = p1;
 75     p1 = p2;
 76     p2 = p3;
 77     p3 = points[i];
 78     path += this.pathBasis(p0, p1, p2, p3);
 79   }
 80   /* Cycle through to get the last point. */
 81   path += this.pathBasis(p1, p2, p3, p3);
 82   path += this.pathBasis(p2, p3, p3, p3);
 83   return path;
 84 };
 85 
 86 /**
 87  * @private Interpolates the given points using the basis spline interpolation.
 88  * If points.length == tangents.length then a regular Hermite interpolation is
 89  * performed, if points.length == tangents.length + 2 then the first and last
 90  * segments are filled in with cubic bazier segments.  Returns an array of path
 91  * strings.
 92  *
 93  * @param points the array of points.
 94  */
 95 pv.SvgScene.curveBasisSegments = function(points) {
 96   if (points.length <= 2) return "";
 97   var paths = [],
 98       p0 = points[0],
 99       p1 = p0,
100       p2 = p0,
101       p3 = points[1],
102       firstPath = this.pathBasis.segment(p0, p1, p2, p3);
103 
104   p0 = p1;
105   p1 = p2;
106   p2 = p3;
107   p3 = points[2];
108   paths.push(firstPath + this.pathBasis(p0, p1, p2, p3)); // merge first & second path
109   for (var i = 3; i < points.length; i++) {
110     p0 = p1;
111     p1 = p2;
112     p2 = p3;
113     p3 = points[i];
114     paths.push(this.pathBasis.segment(p0, p1, p2, p3));
115   }
116 
117   // merge last & second-to-last path
118   paths.push(this.pathBasis.segment(p1, p2, p3, p3) + this.pathBasis(p2, p3, p3, p3));
119   return paths;
120 };
121 
122 /**
123  * @private Interpolates the given points with respective tangents using the cubic
124  * Hermite spline interpolation. If points.length == tangents.length then a regular
125  * Hermite interpolation is performed, if points.length == tangents.length + 2 then
126  * the first and last segments are filled in with cubic bazier segments.
127  * Returns an SVG path without the leading M instruction to allow path appending.
128  *
129  * @param points the array of points.
130  * @param tangents the array of tangent vectors.
131  */
132 pv.SvgScene.curveHermite = function(points, tangents) {
133   if (tangents.length < 1
134       || (points.length != tangents.length
135       && points.length != tangents.length + 2)) return "";
136   var quad = points.length != tangents.length,
137       path = "",
138       p0 = points[0],
139       p = points[1],
140       t0 = tangents[0],
141       t = t0,
142       pi = 1;
143 
144   if (quad) {
145     path += "Q" + (p.left - t0.x * 2 / 3) + ","  + (p.top - t0.y * 2 / 3)
146         + "," + p.left + "," + p.top;
147     p0 = points[1];
148     pi = 2;
149   }
150 
151   if (tangents.length > 1) {
152     t = tangents[1];
153     p = points[pi];
154     pi++;
155     path += "C" + (p0.left + t0.x) + "," + (p0.top + t0.y)
156         + "," + (p.left - t.x) + "," + (p.top - t.y)
157         + "," + p.left + "," + p.top;
158     for (var i = 2; i < tangents.length; i++, pi++) {
159       p = points[pi];
160       t = tangents[i];
161       path += "S" + (p.left - t.x) + "," + (p.top - t.y)
162           + "," + p.left + "," + p.top;
163     }
164   }
165 
166   if (quad) {
167     var lp = points[pi];
168     path += "Q" + (p.left + t.x * 2 / 3) + ","  + (p.top + t.y * 2 / 3) + ","
169         + lp.left + "," + lp.top;
170   }
171 
172   return path;
173 };
174 
175 /**
176  * @private Interpolates the given points with respective tangents using the
177  * cubic Hermite spline interpolation. Returns an array of path strings.
178  *
179  * @param points the array of points.
180  * @param tangents the array of tangent vectors.
181  */
182 pv.SvgScene.curveHermiteSegments = function(points, tangents) {
183   if (tangents.length < 1
184       || (points.length != tangents.length
185       && points.length != tangents.length + 2)) return [];
186   var quad = points.length != tangents.length,
187       paths = [],
188       p0 = points[0],
189       p = p0,
190       t0 = tangents[0],
191       t = t0,
192       pi = 1;
193 
194   if (quad) {
195     p = points[1];
196     paths.push("M" + p0.left + "," + p0.top
197         + "Q" + (p.left - t.x * 2 / 3) + "," + (p.top - t.y * 2 / 3)
198         + "," + p.left + "," + p.top);
199     pi = 2;
200   }
201 
202   for (var i = 1; i < tangents.length; i++, pi++) {
203     p0 = p;
204     t0 = t;
205     p = points[pi];
206     t = tangents[i];
207     paths.push("M" + p0.left + "," + p0.top
208         + "C" + (p0.left + t0.x) + "," + (p0.top + t0.y)
209         + "," + (p.left - t.x) + "," + (p.top - t.y)
210         + "," + p.left + "," + p.top);
211   }
212 
213   if (quad) {
214     var lp = points[pi];
215     paths.push("M" + p.left + "," + p.top
216         + "Q" + (p.left + t.x * 2 / 3) + ","  + (p.top + t.y * 2 / 3) + ","
217         + lp.left + "," + lp.top);
218   }
219 
220   return paths;
221 };
222 
223 /**
224  * @private Computes the tangents for the given points needed for cardinal
225  * spline interpolation. Returns an array of tangent vectors. Note: that for n
226  * points only the n-2 well defined tangents are returned.
227  *
228  * @param points the array of points.
229  * @param tension the tension of hte cardinal spline.
230  */
231 pv.SvgScene.cardinalTangents = function(points, tension) {
232   var tangents = [],
233       a = (1 - tension) / 2,
234       p0 = points[0],
235       p1 = points[1],
236       p2 = points[2];
237 
238   for (var i = 3; i < points.length; i++) {
239     tangents.push({x: a * (p2.left - p0.left), y: a * (p2.top - p0.top)});
240     p0 = p1;
241     p1 = p2;
242     p2 = points[i];
243   }
244 
245   tangents.push({x: a * (p2.left - p0.left), y: a * (p2.top - p0.top)});
246   return tangents;
247 };
248 
249 /**
250  * @private Interpolates the given points using cardinal spline interpolation.
251  * Returns an SVG path without the leading M instruction to allow path
252  * appending.
253  *
254  * @param points the array of points.
255  * @param tension the tension of hte cardinal spline.
256  */
257 pv.SvgScene.curveCardinal = function(points, tension) {
258   if (points.length <= 2) return "";
259   return this.curveHermite(points, this.cardinalTangents(points, tension));
260 };
261 
262 /**
263  * @private Interpolates the given points using cardinal spline interpolation.
264  * Returns an array of path strings.
265  *
266  * @param points the array of points.
267  * @param tension the tension of hte cardinal spline.
268  */
269 pv.SvgScene.curveCardinalSegments = function(points, tension) {
270   if (points.length <= 2) return "";
271   return this.curveHermiteSegments(points, this.cardinalTangents(points, tension));
272 };
273 
274 /**
275  * @private Interpolates the given points using Fritsch-Carlson Monotone cubic
276  * Hermite interpolation. Returns an array of tangent vectors.
277  *
278  * @param points the array of points.
279  */
280 pv.SvgScene.monotoneTangents = function(points) {
281   var tangents = [],
282       d = [],
283       m = [],
284       dx = [],
285       k = 0;
286 
287   /* Compute the slopes of the secant lines between successive points. */
288   for (k = 0; k < points.length-1; k++) {
289     d[k] = (points[k+1].top - points[k].top)/(points[k+1].left - points[k].left);
290   }
291 
292   /* Initialize the tangents at every point as the average of the secants. */
293   m[0] = d[0];
294   dx[0] = points[1].left - points[0].left;
295   for (k = 1; k < points.length - 1; k++) {
296     m[k] = (d[k-1]+d[k])/2;
297     dx[k] = (points[k+1].left - points[k-1].left)/2;
298   }
299   m[k] = d[k-1];
300   dx[k] = (points[k].left - points[k-1].left);
301 
302   /* Step 3. Very important, step 3. Yep. Wouldn't miss it. */
303   for (k = 0; k < points.length - 1; k++) {
304     if (d[k] == 0) {
305       m[ k ] = 0;
306       m[k+1] = 0;
307     }
308   }
309 
310   /* Step 4 + 5. Out of 5 or more steps. */
311   for (k = 0; k < points.length - 1; k++) {
312     if ((Math.abs(m[k]) < 1e-5) || (Math.abs(m[k+1]) < 1e-5)) continue;
313     var ak = m[k] / d[k],
314         bk = m[k + 1] / d[k],
315         s = ak * ak + bk * bk; // monotone constant (?)
316     if (s > 9) {
317       var tk = 3 / Math.sqrt(s);
318       m[k] = tk * ak * d[k];
319       m[k + 1] = tk * bk * d[k];
320     }
321   }
322 
323   var len;
324   for (var i = 0; i < points.length; i++) {
325     len = 1 + m[i] * m[i]; // pv.vector(1, m[i]).norm().times(dx[i]/3)
326     tangents.push({x: dx[i] / 3 / len, y: m[i] * dx[i] / 3 / len});
327   }
328 
329   return tangents;
330 };
331 
332 /**
333  * @private Interpolates the given points using Fritsch-Carlson Monotone cubic
334  * Hermite interpolation. Returns an SVG path without the leading M instruction
335  * to allow path appending.
336  *
337  * @param points the array of points.
338  */
339 pv.SvgScene.curveMonotone = function(points) {
340   if (points.length <= 2) return "";
341   return this.curveHermite(points, this.monotoneTangents(points));
342 }
343 
344 /**
345  * @private Interpolates the given points using Fritsch-Carlson Monotone cubic
346  * Hermite interpolation.
347  * Returns an array of path strings.
348  *
349  * @param points the array of points.
350  */
351 pv.SvgScene.curveMonotoneSegments = function(points) {
352   if (points.length <= 2) return "";
353   return this.curveHermiteSegments(points, this.monotoneTangents(points));
354 };
355