Catmull–Rom Curves

README.md

Cubic Catmull–Rom curves with (b) uniform, (c) chordal and (d) centripetal parameterization. From Yuksel et. al: “Uniform parameterization overshoots and often generates cusps and intersections within short curve segments, while chord-length parameterization exhibits similar behavior for longer curve segments. Centripetal parameterization is the only one that guarantees no intersections within curve segments.”

d3.js

!function(t,h){"object"==typeof exports&&"undefined"!=typeof module?h(exports):"function"==typeof define&&define.amd?define("d3-path",["exports"],h):h(t.d3_path={})}(this,function(t){"use strict";function h(){this.beginPath()}function i(){return new h}var s=Math.PI,_=2*s,n=1e-6;h.prototype=i.prototype={beginPath:function(){this._x0=this._y0=this._x1=this._y1=null,this._=[]},moveTo:function(t,h){this._.push("M",this._x0=this._x1=+t,",",this._y0=this._y1=+h)},closePath:function(){null!==this._x1&&(this._x1=this._x0,this._y1=this._y0,this._.push("Z"))},lineTo:function(t,h){this._.push("L",this._x1=+t,",",this._y1=+h)},quadraticCurveTo:function(t,h,i,s){this._.push("Q",+t,",",+h,",",this._x1=+i,",",this._y1=+s)},bezierCurveTo:function(t,h,i,s,_,n){this._.push("C",+t,",",+h,",",+i,",",+s,",",this._x1=+_,",",this._y1=+n)},arcTo:function(t,h,i,s,_){t=+t,h=+h,i=+i,s=+s,_=+_;var e=this._x1,o=this._y1,u=i-t,a=s-h,r=e-t,f=o-h,p=r*r+f*f;if(0>_)throw new Error("negative radius: "+_);if(null===this._x1)this._.push("M",this._x1=t,",",this._y1=h);else if(p>n)if(Math.abs(f*u-a*r)>n&&_){var c=i-e,x=s-o,y=u*u+a*a,M=c*c+x*x,l=Math.sqrt(y),d=Math.sqrt(p),v=_*Math.tan((Math.PI-Math.acos((y+p-M)/(2*l*d)))/2),b=v/d,g=v/l;Math.abs(b-1)>n&&this._.push("L",t+b*r,",",h+b*f),this._.push("A",_,",",_,",0,0,",+(f*c>r*x),",",this._x1=t+g*u,",",this._y1=h+g*a)}else this._.push("L",this._x1=t,",",this._y1=h);else;},arc:function(t,h,i,e,o){t=+t,h=+h,i=+i;var u=i*Math.cos(e),a=i*Math.sin(e),r=t+u,f=h+a,p=Math.abs(o-e);if(0>i)throw new Error("negative radius: "+i);null===this._x1?this._.push("M",r,",",f):(Math.abs(this._x1-r)>n||Math.abs(this._y1-f)>n)&&this._.push("L",r,",",f),p>=_-n?this._.push("A",i,",",i,",0,1,1,",t-u,",",h-a,"A",i,",",i,",0,1,1,",this._x1=r,",",this._y1=f):this._.push("A",i,",",i,",0,",+(p>=s),",1,",this._x1=t+i*Math.cos(o),",",this._y1=h+i*Math.sin(o))},rect:function(t,h,i,s){this._.push("M",this._x0=this._x1=+t,",",this._y0=this._y1=+h,"h",+i,"v",+s,"h",-i,"Z")},toString:function(){return this._.join("")}};var e="0.0.2";t.version=e,t.path=i});!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports,require("d3-path")):"function"==typeof define&&define.amd?define("d3-shape",["exports","d3-path"],i):i(t.d3_shape={},t.d3_path)}(this,function(t,i){"use strict";function s(t,i,s){t._context.bezierCurveTo((2*t._x0+t._x1)/3,(2*t._y0+t._y1)/3,(t._x0+2*t._x1)/3,(t._y0+2*t._y1)/3,(t._x0+4*t._x1+i)/6,(t._y0+4*t._y1+s)/6)}function _(t){return new h(t)}function h(t){this._context=t}function e(t){return new n(t)}function n(t){this._context=t}function a(t){return new o(t)}function o(t){this._context=t}function c(t){return new x(t)}function x(t){this._context=t}function r(t){return null==t||1===(t=+t)?_:function(i){return new l(i,t)}}function l(t,i){this._basis=_(t),this._beta=i}function u(t){return function(i){return new y(i,t)}}function y(t,i){this._context=t,this._k=(null==i?1:1-i)/6}function f(t){return function(i){return new p(i,t)}}function p(t,i){this._context=t,this._k=(null==i?1:1-i)/6}function b(t){return function(i){return new k(i,t)}}function k(t,i){this._context=t,this._k=(null==i?1:1-i)/6}function d(t){return function(i){return new v(i,t)}}function v(t,i){this._context=t,this._alpha2=(this._alpha=null==i?0:+i)/2}function T(t){return new w(t)}function w(t){this._context=t}function m(t){var i,s,_=t.length-1,h=new Array(_),e=new Array(_),n=new Array(_);for(h[0]=0,e[0]=2,n[0]=t[0]+2*t[1],i=1;_-1>i;++i)h[i]=1,e[i]=4,n[i]=4*t[i]+2*t[i+1];for(h[_-1]=2,e[_-1]=7,n[_-1]=8*t[_-1]+t[_],i=1;_>i;++i)s=h[i]/e[i-1],e[i]-=s,n[i]-=s*n[i-1];for(h[_-1]=n[_-1]/e[_-1],i=_-2;i>=0;--i)h[i]=(n[i]-h[i+1])/e[i];for(e[_-1]=(t[_]+h[_-1])/2,i=0;_-1>i;++i)e[i]=2*t[i+1]-h[i+1];return[h,e]}function N(t){return new E(t)}function E(t){this._context=t}function S(t){return new g(t)}function g(t){this._context=t}function P(t){return new z(t)}function z(t){this._context=t}function C(t){return new A(t)}function A(t){this._context=t}function M(t){return t[0]}function j(t){return t[1]}function q(t){return function(){return t}}function B(){return!0}function D(){function t(t){var s,_=!1;p||(k=y(s=i.path()));for(var e,n=0,a=t.length;a>n;++n)!l(e=t[n],n)===_&&((_=!_)?k.lineStart():k.lineEnd()),_&&k.point(+h(e,n),+o(e,n));return _&&k.lineEnd(),p?void 0:(k=null,s+""||null)}var s=M,h=s,n=j,o=n,x=!0,l=B,y=c,p=null,k=null;return t.x=function(i){return arguments.length?(s=i,h="function"==typeof i?s:q(s),t):s},t.y=function(i){return arguments.length?(n=i,o="function"==typeof i?n:q(n),t):n},t.defined=function(i){return arguments.length?(x=i,l="function"==typeof i?x:q(x),t):x},t.interpolate=function(i,s){if(!arguments.length)return y;if("function"==typeof i)y=i;else switch(i+""){case"linear-closed":y=N;break;case"step":y=S;break;case"step-before":y=C;break;case"step-after":y=P;break;case"basis":y=_;break;case"basis-open":y=a;break;case"basis-closed":y=e;break;case"bundle":y=r(s);break;case"cardinal":y=u(s);break;case"cardinal-open":y=b(s);break;case"cardinal-closed":y=f(s);break;case"catmull-rom":y=d(s);break;case"cubic":y=T;break;default:y=c}return null!=p&&(k=y(p)),t},t.context=function(i){return arguments.length?(null==i?p=k=null:k=y(p=i),t):p},t}h.prototype={lineStart:function(){this._x0=this._x1=this._y0=this._y1=NaN,this._state=0},lineEnd:function(){switch(this._state){case 1:this._context.closePath();break;case 3:s(this,this._x1,this._y1);case 2:this._context.lineTo(this._x1,this._y1)}},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2,this._context.lineTo((5*this._x1+t)/6,(5*this._y1+i)/6);break;case 2:this._state=3;default:s(this,t,i)}this._x0=this._x1,this._x1=t,this._y0=this._y1,this._y1=i}},n.prototype={lineStart:function(){this._x0=this._x1=this._x2=this._x3=this._x4=this._y0=this._y1=this._y2=this._y3=this._y4=NaN,this._state=0},lineEnd:function(){switch(this._state){case 1:this._context.moveTo(this._x2,this._y2),this._context.closePath();break;case 2:this._context.moveTo((this._x2+2*this._x3)/3,(this._y2+2*this._y3)/3),this._context.lineTo((this._x3+2*this._x2)/3,(this._y3+2*this._y2)/3),this._context.closePath();break;case 3:this.point(this._x2,this._y2),this.point(this._x3,this._y3),this.point(this._x4,this._y4)}},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._x2=t,this._y2=i;break;case 1:this._state=2,this._x3=t,this._y3=i;break;case 2:this._state=3,this._x4=t,this._y4=i,this._context.moveTo((this._x0+4*this._x1+t)/6,(this._y0+4*this._y1+i)/6);break;default:s(this,t,i)}this._x0=this._x1,this._x1=t,this._y0=this._y1,this._y1=i}},o.prototype={lineStart:function(){this._x0=this._x1=this._y0=this._y1=NaN,this._state=0},lineEnd:function(){3===this._state&&this._context.closePath()},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1;break;case 1:this._state=2;break;case 2:this._state=3,this._context.moveTo((this._x0+4*this._x1+t)/6,(this._y0+4*this._y1+i)/6);break;case 3:this._state=4;default:s(this,t,i)}this._x0=this._x1,this._x1=t,this._y0=this._y1,this._y1=i}},x.prototype={lineStart:function(){this._state=0},lineEnd:function(){1===this._state&&this._context.closePath()},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2;default:this._context.lineTo(t,i)}}},l.prototype={lineStart:function(){this._x=[],this._y=[],this._basis.lineStart()},lineEnd:function(){var t=this._x,i=this._y,s=t.length-1;if(s>0)for(var _,h=t[0],e=i[0],n=t[s]-h,a=i[s]-e,o=-1;++o<=s;)_=o/s,this._basis.point(this._beta*t[o]+(1-this._beta)*(h+_*n),this._beta*i[o]+(1-this._beta)*(e+_*a));this._x=this._y=null,this._basis.lineEnd()},point:function(t,i){this._x.push(+t),this._y.push(+i)}},y.prototype={lineStart:function(){this._x0=this._x1=this._x2=this._y0=this._y1=this._y2=NaN,this._state=0},lineEnd:function(){switch(this._state){case 1:this._context.closePath();break;case 2:this._context.lineTo(this._x2,this._y2);break;case 3:this._context.bezierCurveTo(this._x1+this._k*(this._x2-this._x0),this._y1+this._k*(this._y2-this._y0),this._x2,this._y2,this._x2,this._y2)}},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2;break;case 2:this._state=3,this._context.bezierCurveTo(this._x1,this._y1,this._x2+this._k*(this._x1-t),this._y2+this._k*(this._y1-i),this._x2,this._y2);break;default:this._context.bezierCurveTo(this._x1+this._k*(this._x2-this._x0),this._y1+this._k*(this._y2-this._y0),this._x2+this._k*(this._x1-t),this._y2+this._k*(this._y1-i),this._x2,this._y2)}this._x0=this._x1,this._x1=this._x2,this._x2=t,this._y0=this._y1,this._y1=this._y2,this._y2=i}},p.prototype={lineStart:function(){this._x0=this._x1=this._x2=this._x3=this._x4=this._x5=this._y0=this._y1=this._y2=this._y3=this._y4=this._y5=NaN,this._state=0},lineEnd:function(){switch(this._state){case 1:this._context.moveTo(this._x3,this._y3),this._context.closePath();break;case 2:this._context.lineTo(this._x3,this._y3),this._context.closePath();break;case 3:this.point(this._x3,this._y3),this.point(this._x4,this._y4),this.point(this._x5,this._y5)}},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._x3=t,this._y3=i;break;case 1:this._state=2,this._context.moveTo(this._x4=t,this._y4=i);break;case 2:this._state=3,this._x5=t,this._y5=i;break;default:this._context.bezierCurveTo(this._x1+this._k*(this._x2-this._x0),this._y1+this._k*(this._y2-this._y0),this._x2+this._k*(this._x1-t),this._y2+this._k*(this._y1-i),this._x2,this._y2)}this._x0=this._x1,this._x1=this._x2,this._x2=t,this._y0=this._y1,this._y1=this._y2,this._y2=i}},k.prototype={lineStart:function(){this._x0=this._x1=this._x2=this._y0=this._y1=this._y2=NaN,this._state=0},lineEnd:function(){switch(this._state){case 2:case 3:this._context.closePath()}},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1;break;case 1:this._state=2,this._context.moveTo(t,i);break;case 2:this._state=3;break;case 3:this._state=4;default:this._context.bezierCurveTo(this._x1+this._k*(this._x2-this._x0),this._y1+this._k*(this._y2-this._y0),this._x2+this._k*(this._x1-t),this._y2+this._k*(this._y1-i),this._x2,this._y2)}this._x0=this._x1,this._x1=this._x2,this._x2=t,this._y0=this._y1,this._y1=this._y2,this._y2=i}},v.prototype={lineStart:function(){this._x0=this._x1=this._x2=this._y0=this._y1=this._y2=this._l01_a=this._l12_a=this._l23_a=this._l01_2a=this._l12_2a=this._l23_2a=NaN,this._state=0},lineEnd:function(){switch(this._state){case 1:this._context.closePath();break;case 2:this._context.lineTo(this._x2,this._y2);break;case 3:var t=2*this._l01_2a+3*this._l01_a*this._l12_a+this._l12_2a,i=3*this._l01_a*(this._l01_a+this._l12_a);this._context.bezierCurveTo((this._x1*t-this._x0*this._l12_2a+this._x2*this._l01_2a)/i,(this._y1*t-this._y0*this._l12_2a+this._y2*this._l01_2a)/i,this._x2,this._y2,this._x2,this._y2)}},point:function(t,i){if(t=+t,i=+i,this._state){var s=this._x2-t,_=this._y2-i,h=s*s+_*_;this._l23_a=Math.pow(h,this._alpha2),this._l23_2a=Math.pow(h,this._alpha)}switch(this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2;break;case 2:var e=2*this._l23_2a+3*this._l23_a*this._l12_a+this._l12_2a,n=3*this._l23_a*(this._l23_a+this._l12_a);this._state=3,this._context.bezierCurveTo(this._x1,this._y1,(this._x2*e+this._x1*this._l23_2a-t*this._l12_2a)/n,(this._y2*e+this._y1*this._l23_2a-i*this._l12_2a)/n,this._x2,this._y2);break;default:var a=2*this._l01_2a+3*this._l01_a*this._l12_a+this._l12_2a,e=2*this._l23_2a+3*this._l23_a*this._l12_a+this._l12_2a,o=3*this._l01_a*(this._l01_a+this._l12_a),n=3*this._l23_a*(this._l23_a+this._l12_a);this._context.bezierCurveTo((this._x1*a-this._x0*this._l12_2a+this._x2*this._l01_2a)/o,(this._y1*a-this._y0*this._l12_2a+this._y2*this._l01_2a)/o,(this._x2*e+this._x1*this._l23_2a-t*this._l12_2a)/n,(this._y2*e+this._y1*this._l23_2a-i*this._l12_2a)/n,this._x2,this._y2)}this._l01_a=this._l12_a,this._l12_a=this._l23_a,this._l01_2a=this._l12_2a,this._l12_2a=this._l23_2a,this._x0=this._x1,this._x1=this._x2,this._x2=t,this._y0=this._y1,this._y1=this._y2,this._y2=i}},w.prototype={lineStart:function(){this._x=[],this._y=[]},lineEnd:function(){var t=this._x,i=this._y,s=t.length;switch(s){case 0:break;case 1:this._context.moveTo(t[0],i[0]),this._context.closePath();break;case 2:this._context.moveTo(t[0],i[0]),this._context.lineTo(t[1],i[1]);break;default:var _=m(t),h=m(i);this._context.moveTo(t[0],i[0]);for(var e=0,s=t.length;s-1>e;++e)this._context.bezierCurveTo(_[0][e],h[0][e],_[1][e],h[1][e],t[e+1],i[e+1])}this._x=this._y=null},point:function(t,i){this._x.push(+t),this._y.push(+i)}},E.prototype={lineStart:function(){this._state=0},lineEnd:function(){this._context.closePath()},point:function(t,i){t=+t,i=+i,this._state?this._context.lineTo(t,i):(this._state=1,this._context.moveTo(t,i))}},g.prototype={lineStart:function(){this._x=this._y=NaN,this._state=0},lineEnd:function(){switch(this._state){case 1:this._context.closePath();break;case 2:this._context.lineTo(this._x,this._y)}},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2;default:var s=(this._x+t)/2;this._context.lineTo(s,this._y),this._context.lineTo(s,i)}this._x=t,this._y=i}},z.prototype={lineStart:function(){this._y=NaN,this._state=0},lineEnd:function(){1===this._state&&this._context.closePath()},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2;default:this._context.lineTo(t,this._y),this._context.lineTo(t,i)}this._y=i}},A.prototype={lineStart:function(){this._x=NaN,this._state=0},lineEnd:function(){1===this._state&&this._context.closePath()},point:function(t,i){switch(t=+t,i=+i,this._state){case 0:this._state=1,this._context.moveTo(t,i);break;case 1:this._state=2;default:this._context.lineTo(this._x,i),this._context.lineTo(t,i)}this._x=t}};var F="0.0.2";t.version=F,t.line=D});

example-centripetal.png

example-chordal.png

example-uniform.png

index.html

<!DOCTYPE html>
<meta charset="utf-8">
<style>

div {
  margin: 0 122px;
  width: 715px;
  height: 471px;
  overflow: hidden;
  position: relative;
}

canvas,
img {
  position: absolute;
}

</style>
<div>
  <img src="example-uniform.png" style="left:-3px;top:-1px;">
  <canvas data-alpha="0.0" width="715" height="471"></canvas>
</div>
<div>
  <img src="example-chordal.png" style="left:-4px;top:-2px;">
  <canvas data-alpha="1.0" width="715" height="471"></canvas>
</div>
<div>
  <img src="example-centripetal.png" style="left:-4px;top:-1px;">
  <canvas data-alpha="0.5" width="715" height="471"></canvas>
</div>
<script src="d3.js"></script>
<script>

var points = [
  [133.5, 424.0],
  [ 56.5, 352.0],
  [344.0,  73.0],
  [360.5,  88.0],
  [593.0, 412.5],
  [621.5, 386.0],
  [662.5, 129.0]
];

[].forEach.call(document.querySelectorAll("canvas"), function(canvas) {
  var context = canvas.getContext("2d");

  var line = d3_shape.line()
      .context(context)
      .interpolate("catmull-rom", canvas.getAttribute("data-alpha"));

  context.beginPath();
  line(points);
  context.lineWidth = 1.5;
  context.strokeStyle = "white";
  context.stroke();
});

if (self.frameElement) self.frameElement.style.height = 471 * 3 + "px";

</script>

thumbnail.png