-
Notifications
You must be signed in to change notification settings - Fork 311
/
Copy pathmonotone.js
104 lines (91 loc) · 3.13 KB
/
monotone.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
function sign(x) {
return x < 0 ? -1 : 1;
}
// Calculate the slopes of the tangents (Hermite-type interpolation) based on
// the following paper: Steffen, M. 1990. A Simple Method for Monotonic
// Interpolation in One Dimension. Astronomy and Astrophysics, Vol. 239, NO.
// NOV(II), P. 443, 1990.
function slope3(that, x2, y2) {
var h0 = that._x1 - that._x0,
h1 = x2 - that._x1,
s0 = (that._y1 - that._y0) / (h0 || h1 < 0 && -0),
s1 = (y2 - that._y1) / (h1 || h0 < 0 && -0),
p = (s0 * h1 + s1 * h0) / (h0 + h1);
return (sign(s0) + sign(s1)) * Math.min(Math.abs(s0), Math.abs(s1), 0.5 * Math.abs(p)) || 0;
}
// Calculate a one-sided slope.
function slope2(that, t) {
var h = that._x1 - that._x0;
return h ? (3 * (that._y1 - that._y0) / h - t) / 2 : t;
}
// According to https://en.wikipedia.org/wiki/Cubic_Hermite_spline#Representations
// "you can express cubic Hermite interpolation in terms of cubic Bézier curves
// with respect to the four values p0, p0 + m0 / 3, p1 - m1 / 3, p1".
function point(that, t0, t1) {
var x0 = that._x0,
y0 = that._y0,
x1 = that._x1,
y1 = that._y1,
dx = (x1 - x0) / 3;
that._context.bezierCurveTo(x0 + dx, y0 + dx * t0, x1 - dx, y1 - dx * t1, x1, y1);
}
function MonotoneX(context) {
this._context = context;
}
MonotoneX.prototype = {
areaStart: function() {
this._line = 0;
},
areaEnd: function() {
this._line = NaN;
},
lineStart: function() {
this._x0 = this._x1 =
this._y0 = this._y1 =
this._t0 = NaN;
this._point = 0;
},
lineEnd: function() {
switch (this._point) {
case 2: this._context.lineTo(this._x1, this._y1); break;
case 3: point(this, this._t0, slope2(this, this._t0)); break;
}
if (this._line || (this._line !== 0 && this._point === 1)) this._context.closePath();
this._line = 1 - this._line;
},
point: function(x, y) {
var t1 = NaN;
x = +x, y = +y;
if (x === this._x1 && y === this._y1) return; // Ignore coincident points.
switch (this._point) {
case 0: this._point = 1; this._line ? this._context.lineTo(x, y) : this._context.moveTo(x, y); break;
case 1: this._point = 2; break;
case 2: this._point = 3; point(this, slope2(this, t1 = slope3(this, x, y)), t1); break;
default: point(this, this._t0, t1 = slope3(this, x, y)); break;
}
this._x0 = this._x1, this._x1 = x;
this._y0 = this._y1, this._y1 = y;
this._t0 = t1;
}
}
function MonotoneY(context) {
this._context = new ReflectContext(context);
}
(MonotoneY.prototype = Object.create(MonotoneX.prototype)).point = function(x, y) {
MonotoneX.prototype.point.call(this, y, x);
};
function ReflectContext(context) {
this._context = context;
}
ReflectContext.prototype = {
moveTo: function(x, y) { this._context.moveTo(y, x); },
closePath: function() { this._context.closePath(); },
lineTo: function(x, y) { this._context.lineTo(y, x); },
bezierCurveTo: function(x1, y1, x2, y2, x, y) { this._context.bezierCurveTo(y1, x1, y2, x2, y, x); }
};
export function monotoneX(context) {
return new MonotoneX(context);
}
export function monotoneY(context) {
return new MonotoneY(context);
}