4 * Copyright (c) 2010 - 2013 Simon Porritt (simon.porritt@gmail.com)
6 * licensed under the MIT license.
8 * a set of Bezier curve functions that deal with Beziers, used by jsPlumb, and perhaps useful for other people. These functions work with Bezier
9 * curves of arbitrary degree.
11 * - functions are all in the 'jsBezier' namespace.
13 * - all input points should be in the format {x:.., y:..}. all output points are in this format too.
15 * - all input curves should be in the format [ {x:.., y:..}, {x:.., y:..}, {x:.., y:..}, {x:.., y:..} ]
17 * - 'location' as used as an input here refers to a decimal in the range 0-1 inclusive, which indicates a point some proportion along the length
18 * of the curve. location as output has the same format and meaning.
24 * distanceFromCurve(point, curve)
26 * Calculates the distance that the given point lies from the given Bezier. Note that it is computed relative to the center of the Bezier,
27 * so if you have stroked the curve with a wide pen you may wish to take that into account! The distance returned is relative to the values
28 * of the curve and the point - it will most likely be pixels.
30 * gradientAtPoint(curve, location)
32 * Calculates the gradient to the curve at the given location, as a decimal between 0 and 1 inclusive.
34 * gradientAtPointAlongCurveFrom (curve, location)
36 * Calculates the gradient at the point on the given curve that is 'distance' units from location.
38 * nearestPointOnCurve(point, curve)
40 * Calculates the nearest point to the given point on the given curve. The return value of this is a JS object literal, containing both the
41 *point's coordinates and also the 'location' of the point (see above), for example: { point:{x:551,y:150}, location:0.263365 }.
43 * pointOnCurve(curve, location)
45 * Calculates the coordinates of the point on the given Bezier curve at the given location.
47 * pointAlongCurveFrom(curve, location, distance)
49 * Calculates the coordinates of the point on the given curve that is 'distance' units from location. 'distance' should be in the same coordinate
50 * space as that used to construct the Bezier curve. For an HTML Canvas usage, for example, distance would be a measure of pixels.
52 * locationAlongCurveFrom(curve, location, distance)
54 * Calculates the location on the given curve that is 'distance' units from location. 'distance' should be in the same coordinate
55 * space as that used to construct the Bezier curve. For an HTML Canvas usage, for example, distance would be a measure of pixels.
57 * perpendicularToCurveAt(curve, location, length, distance)
59 * Calculates the perpendicular to the given curve at the given location. length is the length of the line you wish for (it will be centered
60 * on the point at 'location'). distance is optional, and allows you to specify a point along the path from the given location as the center of
61 * the perpendicular returned. The return value of this is an array of two points: [ {x:...,y:...}, {x:...,y:...} ].
68 if(typeof Math.sgn == "undefined") {
69 Math.sgn = function(x) { return x == 0 ? 0 : x > 0 ? 1 :-1; };
73 subtract : function(v1, v2) { return {x:v1.x - v2.x, y:v1.y - v2.y }; },
74 dotProduct : function(v1, v2) { return (v1.x * v2.x) + (v1.y * v2.y); },
75 square : function(v) { return Math.sqrt((v.x * v.x) + (v.y * v.y)); },
76 scale : function(v, s) { return {x:v.x * s, y:v.y * s }; }
80 flatnessTolerance = Math.pow(2.0,-maxRecursion-1);
83 * Calculates the distance that the point lies from the curve.
85 * @param point a point in the form {x:567, y:3342}
86 * @param curve a Bezier curve in the form [{x:..., y:...}, {x:..., y:...}, {x:..., y:...}, {x:..., y:...}]. note that this is currently
87 * hardcoded to assume cubiz beziers, but would be better off supporting any degree.
88 * @return a JS object literal containing location and distance, for example: {location:0.35, distance:10}. Location is analogous to the location
89 * argument you pass to the pointOnPath function: it is a ratio of distance travelled along the curve. Distance is the distance in pixels from
90 * the point to the curve.
92 var _distanceFromCurve = function(point, curve) {
94 w = _convertToBezier(point, curve),
95 degree = curve.length - 1, higherDegree = (2 * degree) - 1,
96 numSolutions = _findRoots(w, higherDegree, candidates, 0),
97 v = Vectors.subtract(point, curve[0]), dist = Vectors.square(v), t = 0.0;
99 for (var i = 0; i < numSolutions; i++) {
100 v = Vectors.subtract(point, _bezier(curve, degree, candidates[i], null, null));
101 var newDist = Vectors.square(v);
102 if (newDist < dist) {
107 v = Vectors.subtract(point, curve[degree]);
108 newDist = Vectors.square(v);
109 if (newDist < dist) {
113 return {location:t, distance:dist};
116 * finds the nearest point on the curve to the given point.
118 var _nearestPointOnCurve = function(point, curve) {
119 var td = _distanceFromCurve(point, curve);
120 return {point:_bezier(curve, curve.length - 1, td.location, null, null), location:td.location};
122 var _convertToBezier = function(point, curve) {
123 var degree = curve.length - 1, higherDegree = (2 * degree) - 1,
124 c = [], d = [], cdTable = [], w = [],
125 z = [ [1.0, 0.6, 0.3, 0.1], [0.4, 0.6, 0.6, 0.4], [0.1, 0.3, 0.6, 1.0] ];
127 for (var i = 0; i <= degree; i++) c[i] = Vectors.subtract(curve[i], point);
128 for (var i = 0; i <= degree - 1; i++) {
129 d[i] = Vectors.subtract(curve[i+1], curve[i]);
130 d[i] = Vectors.scale(d[i], 3.0);
132 for (var row = 0; row <= degree - 1; row++) {
133 for (var column = 0; column <= degree; column++) {
134 if (!cdTable[row]) cdTable[row] = [];
135 cdTable[row][column] = Vectors.dotProduct(d[row], c[column]);
138 for (i = 0; i <= higherDegree; i++) {
139 if (!w[i]) w[i] = [];
141 w[i].x = parseFloat(i) / higherDegree;
143 var n = degree, m = degree-1;
144 for (var k = 0; k <= n + m; k++) {
145 var lb = Math.max(0, k - m),
147 for (i = lb; i <= ub; i++) {
149 w[i+j].y += cdTable[j][i] * z[j][i];
155 * counts how many roots there are.
157 var _findRoots = function(w, degree, t, depth) {
158 var left = [], right = [],
159 left_count, right_count,
160 left_t = [], right_t = [];
162 switch (_getCrossingCount(w, degree)) {
167 if (depth >= maxRecursion) {
168 t[0] = (w[0].x + w[degree].x) / 2.0;
171 if (_isFlatEnough(w, degree)) {
172 t[0] = _computeXIntercept(w, degree);
178 _bezier(w, degree, 0.5, left, right);
179 left_count = _findRoots(left, degree, left_t, depth+1);
180 right_count = _findRoots(right, degree, right_t, depth+1);
181 for (var i = 0; i < left_count; i++) t[i] = left_t[i];
182 for (var i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
183 return (left_count+right_count);
185 var _getCrossingCount = function(curve, degree) {
186 var n_crossings = 0, sign, old_sign;
187 sign = old_sign = Math.sgn(curve[0].y);
188 for (var i = 1; i <= degree; i++) {
189 sign = Math.sgn(curve[i].y);
190 if (sign != old_sign) n_crossings++;
195 var _isFlatEnough = function(curve, degree) {
197 intercept_1, intercept_2, left_intercept, right_intercept,
198 a, b, c, det, dInv, a1, b1, c1, a2, b2, c2;
199 a = curve[0].y - curve[degree].y;
200 b = curve[degree].x - curve[0].x;
201 c = curve[0].x * curve[degree].y - curve[degree].x * curve[0].y;
203 var max_distance_above = max_distance_below = 0.0;
205 for (var i = 1; i < degree; i++) {
206 var value = a * curve[i].x + b * curve[i].y + c;
207 if (value > max_distance_above)
208 max_distance_above = value;
209 else if (value < max_distance_below)
210 max_distance_below = value;
213 a1 = 0.0; b1 = 1.0; c1 = 0.0; a2 = a; b2 = b;
214 c2 = c - max_distance_above;
215 det = a1 * b2 - a2 * b1;
217 intercept_1 = (b1 * c2 - b2 * c1) * dInv;
218 a2 = a; b2 = b; c2 = c - max_distance_below;
219 det = a1 * b2 - a2 * b1;
221 intercept_2 = (b1 * c2 - b2 * c1) * dInv;
222 left_intercept = Math.min(intercept_1, intercept_2);
223 right_intercept = Math.max(intercept_1, intercept_2);
224 error = right_intercept - left_intercept;
225 return (error < flatnessTolerance)? 1 : 0;
227 var _computeXIntercept = function(curve, degree) {
228 var XLK = 1.0, YLK = 0.0,
229 XNM = curve[degree].x - curve[0].x, YNM = curve[degree].y - curve[0].y,
230 XMK = curve[0].x - 0.0, YMK = curve[0].y - 0.0,
231 det = XNM*YLK - YNM*XLK, detInv = 1.0/det,
232 S = (XNM*YMK - YNM*XMK) * detInv;
233 return 0.0 + XLK * S;
235 var _bezier = function(curve, degree, t, left, right) {
237 for (var j =0; j <= degree; j++) temp[0][j] = curve[j];
238 for (var i = 1; i <= degree; i++) {
239 for (var j =0 ; j <= degree - i; j++) {
240 if (!temp[i]) temp[i] = [];
241 if (!temp[i][j]) temp[i][j] = {};
242 temp[i][j].x = (1.0 - t) * temp[i-1][j].x + t * temp[i-1][j+1].x;
243 temp[i][j].y = (1.0 - t) * temp[i-1][j].y + t * temp[i-1][j+1].y;
247 for (j = 0; j <= degree; j++) left[j] = temp[j][0];
249 for (j = 0; j <= degree; j++) right[j] = temp[degree-j][j];
251 return (temp[degree][0]);
254 var _curveFunctionCache = {};
255 var _getCurveFunctions = function(order) {
256 var fns = _curveFunctionCache[order];
259 var f_term = function() { return function(t) { return Math.pow(t, order); }; },
260 l_term = function() { return function(t) { return Math.pow((1-t), order); }; },
261 c_term = function(c) { return function(t) { return c; }; },
262 t_term = function() { return function(t) { return t; }; },
263 one_minus_t_term = function() { return function(t) { return 1-t; }; },
264 _termFunc = function(terms) {
267 for (var i = 0; i < terms.length; i++) p = p * terms[i](t);
272 fns.push(new f_term()); // first is t to the power of the curve order
273 for (var i = 1; i < order; i++) {
274 var terms = [new c_term(order)];
275 for (var j = 0 ; j < (order - i); j++) terms.push(new t_term());
276 for (var j = 0 ; j < i; j++) terms.push(new one_minus_t_term());
277 fns.push(new _termFunc(terms));
279 fns.push(new l_term()); // last is (1-t) to the power of the curve order
281 _curveFunctionCache[order] = fns;
289 * calculates a point on the curve, for a Bezier of arbitrary order.
290 * @param curve an array of control points, eg [{x:10,y:20}, {x:50,y:50}, {x:100,y:100}, {x:120,y:100}]. For a cubic bezier this should have four points.
291 * @param location a decimal indicating the distance along the curve the point should be located at. this is the distance along the curve as it travels, taking the way it bends into account. should be a number from 0 to 1, inclusive.
293 var _pointOnPath = function(curve, location) {
294 var cc = _getCurveFunctions(curve.length - 1),
296 for (var i = 0; i < curve.length ; i++) {
297 _x = _x + (curve[i].x * cc[i](location));
298 _y = _y + (curve[i].y * cc[i](location));
304 var _dist = function(p1,p2) {
305 return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
308 var _isPoint = function(curve) {
309 return curve[0].x == curve[1].x && curve[0].y == curve[1].y;
313 * finds the point that is 'distance' along the path from 'location'. this method returns both the x,y location of the point and also
314 * its 'location' (proportion of travel along the path); the method below - _pointAlongPathFrom - calls this method and just returns the
317 var _pointAlongPath = function(curve, location, distance) {
319 if (_isPoint(curve)) {
326 var prev = _pointOnPath(curve, location),
329 direction = distance > 0 ? 1 : -1,
332 while (tally < Math.abs(distance)) {
333 curLoc += (0.005 * direction);
334 cur = _pointOnPath(curve, curLoc);
335 tally += _dist(cur, prev);
338 return {point:cur, location:curLoc};
341 var _length = function(curve) {
342 if (_isPoint(curve)) return 0;
344 var prev = _pointOnPath(curve, 0),
351 curLoc += (0.005 * direction);
352 cur = _pointOnPath(curve, curLoc);
353 tally += _dist(cur, prev);
360 * finds the point that is 'distance' along the path from 'location'.
362 var _pointAlongPathFrom = function(curve, location, distance) {
363 return _pointAlongPath(curve, location, distance).point;
367 * finds the location that is 'distance' along the path from 'location'.
369 var _locationAlongPathFrom = function(curve, location, distance) {
370 return _pointAlongPath(curve, location, distance).location;
374 * returns the gradient of the curve at the given location, which is a decimal between 0 and 1 inclusive.
376 * thanks // http://bimixual.org/AnimationLibrary/beziertangents.html
378 var _gradientAtPoint = function(curve, location) {
379 var p1 = _pointOnPath(curve, location),
380 p2 = _pointOnPath(curve.slice(0, curve.length - 1), location),
381 dy = p2.y - p1.y, dx = p2.x - p1.x;
382 return dy == 0 ? Infinity : Math.atan(dy / dx);
386 returns the gradient of the curve at the point which is 'distance' from the given location.
387 if this point is greater than location 1, the gradient at location 1 is returned.
388 if this point is less than location 0, the gradient at location 0 is returned.
390 var _gradientAtPointAlongPathFrom = function(curve, location, distance) {
391 var p = _pointAlongPath(curve, location, distance);
392 if (p.location > 1) p.location = 1;
393 if (p.location < 0) p.location = 0;
394 return _gradientAtPoint(curve, p.location);
398 * calculates a line that is 'length' pixels long, perpendicular to, and centered on, the path at 'distance' pixels from the given location.
399 * if distance is not supplied, the perpendicular for the given location is computed (ie. we set distance to zero).
401 var _perpendicularToPathAt = function(curve, location, length, distance) {
402 distance = distance == null ? 0 : distance;
403 var p = _pointAlongPath(curve, location, distance),
404 m = _gradientAtPoint(curve, p.location),
405 _theta2 = Math.atan(-1 / m),
406 y = length / 2 * Math.sin(_theta2),
407 x = length / 2 * Math.cos(_theta2);
408 return [{x:p.point.x + x, y:p.point.y + y}, {x:p.point.x - x, y:p.point.y - y}];
411 var jsBezier = window.jsBezier = {
412 distanceFromCurve : _distanceFromCurve,
413 gradientAtPoint : _gradientAtPoint,
414 gradientAtPointAlongCurveFrom : _gradientAtPointAlongPathFrom,
415 nearestPointOnCurve : _nearestPointOnCurve,
416 pointOnCurve : _pointOnPath,
417 pointAlongCurveFrom : _pointAlongPathFrom,
418 perpendicularToCurveAt : _perpendicularToPathAt,
419 locationAlongCurveFrom:_locationAlongPathFrom,