123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201 |
- (function() {
- var MAXDEPTH = 64, EPSILON = Math.pow(2.0,-MAXDEPTH-1), DEGREE = 3, W_DEGREE = 5;
- var V2Sub = function(from, p) { return {x:from.x - p.x, y:from.y - p.y }; };
- var V2Dot = function(v1, v2) { return (v1.x * v2.x) + (v1.y * v2.y); };
- var V2SquaredLength = function(v) { return (v.x * v.x) + (v.y * v.y); };
- var V2ScaleII = function(v, s) { return {x:v.x * s, y:v.y * s }; };
- var DistanceFromCurve = function(P, V) {
- var w, n_solutions, t;
- var t_candidate = new Array(W_DEGREE);
- w = ConvertToBezierForm(P, V);
- n_solutions = FindRoots(w, W_DEGREE, t_candidate, 0);
- var dist, new_dist, p, v, i;
- v = V2Sub(P, V[0]);
- dist = V2SquaredLength(v);
- t = 0.0;
- for (i = 0; i < n_solutions; i++) {
- p = Bezier(V, DEGREE, t_candidate[i],
- null, null);
- v = V2Sub(P, p);
- new_dist = V2SquaredLength(v);
- if (new_dist < dist) {
- dist = new_dist;
- t = t_candidate[i];
- }
- }
- v = V2Sub(P, V[DEGREE]);
- new_dist = V2SquaredLength(v);
- if (new_dist < dist) {
- dist = new_dist;
- t = 1.0;
- }
- return {t:t,d:dist};
- };
- var NearestPointOnCurve = function(P, V) {
- var td = DistanceFromCurve(P, V);
- return Bezier(V, DEGREE, td.t, null, null);
- };
- var ConvertToBezierForm = function(P, V) {
- var i, j, k, m, n, ub, lb, w, row, column;
- var c = new Array(DEGREE+1), d = new Array(DEGREE);
- var cdTable = [];
- var 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] ];
- for (i = 0; i <= DEGREE; i++)
- c[i] = V2Sub(V[i], P);
- for (i = 0; i <= DEGREE - 1; i++) {
- d[i] = V2Sub(V[i+1], V[i]);
- d[i] = V2ScaleII(d[i], 3.0);
- }
- for (row = 0; row <= DEGREE - 1; row++) {
- for (column = 0; column <= DEGREE; column++) {
- if (!cdTable[row]) cdTable[row] = [];
- cdTable[row][column] = V2Dot(d[row], c[column]);
- }
- }
- w = [];
- for (i = 0; i <= W_DEGREE; i++) {
- if (!w[i]) w[i] = [];
- w[i].y = 0.0;
- w[i].x = parseFloat(i) / W_DEGREE;
- }
- n = DEGREE;
- m = DEGREE-1;
- for (k = 0; k <= n + m; k++) {
- lb = Math.max(0, k - m);
- ub = Math.min(k, n);
- for (i = lb; i <= ub; i++) {
- j = k - i;
- w[i+j].y += cdTable[j][i] * z[j][i];
- }
- }
- return (w);
- };
- var FindRoots = function(w, degree, t, depth) {
- var i;
- var Left = new Array(W_DEGREE+1), Right = new Array(W_DEGREE+1);
- var left_count, right_count;
- var left_t = new Array(W_DEGREE+1), right_t = new Array(W_DEGREE+1);
- switch (CrossingCount(w, degree)) {
- case 0 : {
- return 0;
- }
- case 1 : {
- if (depth >= MAXDEPTH) {
- t[0] = (w[0].x + w[W_DEGREE].x) / 2.0;
- return 1;
- }
- if (ControlPolygonFlatEnough(w, degree)) {
- t[0] = ComputeXIntercept(w, degree);
- return 1;
- }
- break;
- }
- }
- Bezier(w, degree, 0.5, Left, Right);
- left_count = FindRoots(Left, degree, left_t, depth+1);
- right_count = FindRoots(Right, degree, right_t, depth+1);
- for (i = 0; i < left_count; i++) t[i] = left_t[i];
- for (i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
- return (left_count+right_count);
- };
- var CrossingCount = function(V, degree) {
- var n_crossings = 0;
- var sign, old_sign;
- var SGN = function(x) { return x == 0 ? 0 : x > 0 ? 1 :-1; };
- sign = old_sign = SGN(V[0].y);
- for (var i = 1; i <= degree; i++) {
- sign = SGN(V[i].y);
- if (sign != old_sign) n_crossings++;
- old_sign = sign;
- }
- return n_crossings;
- };
- var ControlPolygonFlatEnough = function(V, degree) {
- var value, error;
- var intercept_1, intercept_2, left_intercept, right_intercept;
- var a, b, c, det, dInv, a1, b1, c1, a2, b2, c2;
- a = V[0].y - V[degree].y;
- b = V[degree].x - V[0].x;
- c = V[0].x * V[degree].y - V[degree].x * V[0].y;
- var max_distance_above = max_distance_below = 0.0;
-
- for (var i = 1; i < degree; i++)
- {
- value = a * V[i].x + b * V[i].y + c;
-
- if (value > max_distance_above)
- {
- max_distance_above = value;
- }
- else if (value < max_distance_below)
- {
- max_distance_below = value;
- }
- }
- a1 = 0.0;
- b1 = 1.0;
- c1 = 0.0;
- a2 = a;
- b2 = b;
- c2 = c - max_distance_above;
- det = a1 * b2 - a2 * b1;
- dInv = 1.0/det;
- intercept_1 = (b1 * c2 - b2 * c1) * dInv;
- a2 = a;
- b2 = b;
- c2 = c - max_distance_below;
- det = a1 * b2 - a2 * b1;
- dInv = 1.0/det;
- intercept_2 = (b1 * c2 - b2 * c1) * dInv;
- left_intercept = Math.min(intercept_1, intercept_2);
- right_intercept = Math.max(intercept_1, intercept_2);
- error = right_intercept - left_intercept;
- return (error < EPSILON)? 1 : 0;
- };
- var ComputeXIntercept = function(V, degree) {
- var XLK, YLK, XNM, YNM, XMK, YMK, det, detInv, S, T, X, Y;
- XLK = 1.0 - 0.0;
- YLK = 0.0 - 0.0;
- XNM = V[degree].x - V[0].x;
- YNM = V[degree].y - V[0].y;
- XMK = V[0].x - 0.0;
- YMK = V[0].y - 0.0;
- det = XNM*YLK - YNM*XLK;
- detInv = 1.0/det;
- S = (XNM*YMK - YNM*XMK) * detInv;
- X = 0.0 + XLK * S;
- return X;
- };
- var Bezier = function(V, degree, t, Left, Right) {
- var Vtemp = new Array();
- for (var j =0; j <= degree; j++) {
- if (!Vtemp[0]) Vtemp[0] = [];
- Vtemp[0][j] = V[j];
- }
- for (var i = 1; i <= degree; i++) {
- for (var j =0 ; j <= degree - i; j++) {
- if (!Vtemp[i]) Vtemp[i] = [];
- if (!Vtemp[i][j]) Vtemp[i][j] = {};
- Vtemp[i][j].x = (1.0 - t) * Vtemp[i-1][j].x + t * Vtemp[i-1][j+1].x;
- Vtemp[i][j].y = (1.0 - t) * Vtemp[i-1][j].y + t * Vtemp[i-1][j+1].y;
- }
- }
- if (Left != null)
- for (j = 0; j <= degree; j++) Left[j] = Vtemp[j][0];
- if (Right != null)
- for (j = 0; j <= degree; j++) Right[j] = Vtemp[degree-j][j];
- return (Vtemp[degree][0]);
- };
- var bezCurve = [
- { x:0.0, y:0.0 },
- { x:1.0, y:2.0 },
- { x:3.0, y:3.0 },
- { x:4.0, y:2.0 }
- ];
- var arbPoint = { x:3.5, y:2.0 };
- var pointOnCurve;
- pointOnCurve = NearestPointOnCurve(arbPoint, bezCurve);
- jsPlumb.DistanceFromCurve = DistanceFromCurve;
- jsPlumb.NearestPointOnCurve = NearestPointOnCurve;
- })();
|