NearestPoint.js 6.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. (function() {
  2. var MAXDEPTH = 64, EPSILON = Math.pow(2.0,-MAXDEPTH-1), DEGREE = 3, W_DEGREE = 5;
  3. var V2Sub = function(from, p) { return {x:from.x - p.x, y:from.y - p.y }; };
  4. var V2Dot = function(v1, v2) { return (v1.x * v2.x) + (v1.y * v2.y); };
  5. var V2SquaredLength = function(v) { return (v.x * v.x) + (v.y * v.y); };
  6. var V2ScaleII = function(v, s) { return {x:v.x * s, y:v.y * s }; };
  7. var DistanceFromCurve = function(P, V) {
  8. var w, n_solutions, t;
  9. var t_candidate = new Array(W_DEGREE);
  10. w = ConvertToBezierForm(P, V);
  11. n_solutions = FindRoots(w, W_DEGREE, t_candidate, 0);
  12. var dist, new_dist, p, v, i;
  13. v = V2Sub(P, V[0]);
  14. dist = V2SquaredLength(v);
  15. t = 0.0;
  16. for (i = 0; i < n_solutions; i++) {
  17. p = Bezier(V, DEGREE, t_candidate[i],
  18. null, null);
  19. v = V2Sub(P, p);
  20. new_dist = V2SquaredLength(v);
  21. if (new_dist < dist) {
  22. dist = new_dist;
  23. t = t_candidate[i];
  24. }
  25. }
  26. v = V2Sub(P, V[DEGREE]);
  27. new_dist = V2SquaredLength(v);
  28. if (new_dist < dist) {
  29. dist = new_dist;
  30. t = 1.0;
  31. }
  32. return {t:t,d:dist};
  33. };
  34. var NearestPointOnCurve = function(P, V) {
  35. var td = DistanceFromCurve(P, V);
  36. return Bezier(V, DEGREE, td.t, null, null);
  37. };
  38. var ConvertToBezierForm = function(P, V) {
  39. var i, j, k, m, n, ub, lb, w, row, column;
  40. var c = new Array(DEGREE+1), d = new Array(DEGREE);
  41. var cdTable = [];
  42. 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] ];
  43. for (i = 0; i <= DEGREE; i++)
  44. c[i] = V2Sub(V[i], P);
  45. for (i = 0; i <= DEGREE - 1; i++) {
  46. d[i] = V2Sub(V[i+1], V[i]);
  47. d[i] = V2ScaleII(d[i], 3.0);
  48. }
  49. for (row = 0; row <= DEGREE - 1; row++) {
  50. for (column = 0; column <= DEGREE; column++) {
  51. if (!cdTable[row]) cdTable[row] = [];
  52. cdTable[row][column] = V2Dot(d[row], c[column]);
  53. }
  54. }
  55. w = [];
  56. for (i = 0; i <= W_DEGREE; i++) {
  57. if (!w[i]) w[i] = [];
  58. w[i].y = 0.0;
  59. w[i].x = parseFloat(i) / W_DEGREE;
  60. }
  61. n = DEGREE;
  62. m = DEGREE-1;
  63. for (k = 0; k <= n + m; k++) {
  64. lb = Math.max(0, k - m);
  65. ub = Math.min(k, n);
  66. for (i = lb; i <= ub; i++) {
  67. j = k - i;
  68. w[i+j].y += cdTable[j][i] * z[j][i];
  69. }
  70. }
  71. return (w);
  72. };
  73. var FindRoots = function(w, degree, t, depth) {
  74. var i;
  75. var Left = new Array(W_DEGREE+1), Right = new Array(W_DEGREE+1);
  76. var left_count, right_count;
  77. var left_t = new Array(W_DEGREE+1), right_t = new Array(W_DEGREE+1);
  78. switch (CrossingCount(w, degree)) {
  79. case 0 : {
  80. return 0;
  81. }
  82. case 1 : {
  83. if (depth >= MAXDEPTH) {
  84. t[0] = (w[0].x + w[W_DEGREE].x) / 2.0;
  85. return 1;
  86. }
  87. if (ControlPolygonFlatEnough(w, degree)) {
  88. t[0] = ComputeXIntercept(w, degree);
  89. return 1;
  90. }
  91. break;
  92. }
  93. }
  94. Bezier(w, degree, 0.5, Left, Right);
  95. left_count = FindRoots(Left, degree, left_t, depth+1);
  96. right_count = FindRoots(Right, degree, right_t, depth+1);
  97. for (i = 0; i < left_count; i++) t[i] = left_t[i];
  98. for (i = 0; i < right_count; i++) t[i+left_count] = right_t[i];
  99. return (left_count+right_count);
  100. };
  101. var CrossingCount = function(V, degree) {
  102. var n_crossings = 0;
  103. var sign, old_sign;
  104. var SGN = function(x) { return x == 0 ? 0 : x > 0 ? 1 :-1; };
  105. sign = old_sign = SGN(V[0].y);
  106. for (var i = 1; i <= degree; i++) {
  107. sign = SGN(V[i].y);
  108. if (sign != old_sign) n_crossings++;
  109. old_sign = sign;
  110. }
  111. return n_crossings;
  112. };
  113. var ControlPolygonFlatEnough = function(V, degree) {
  114. var value, error;
  115. var intercept_1, intercept_2, left_intercept, right_intercept;
  116. var a, b, c, det, dInv, a1, b1, c1, a2, b2, c2;
  117. a = V[0].y - V[degree].y;
  118. b = V[degree].x - V[0].x;
  119. c = V[0].x * V[degree].y - V[degree].x * V[0].y;
  120. var max_distance_above = max_distance_below = 0.0;
  121. for (var i = 1; i < degree; i++)
  122. {
  123. value = a * V[i].x + b * V[i].y + c;
  124. if (value > max_distance_above)
  125. {
  126. max_distance_above = value;
  127. }
  128. else if (value < max_distance_below)
  129. {
  130. max_distance_below = value;
  131. }
  132. }
  133. a1 = 0.0;
  134. b1 = 1.0;
  135. c1 = 0.0;
  136. a2 = a;
  137. b2 = b;
  138. c2 = c - max_distance_above;
  139. det = a1 * b2 - a2 * b1;
  140. dInv = 1.0/det;
  141. intercept_1 = (b1 * c2 - b2 * c1) * dInv;
  142. a2 = a;
  143. b2 = b;
  144. c2 = c - max_distance_below;
  145. det = a1 * b2 - a2 * b1;
  146. dInv = 1.0/det;
  147. intercept_2 = (b1 * c2 - b2 * c1) * dInv;
  148. left_intercept = Math.min(intercept_1, intercept_2);
  149. right_intercept = Math.max(intercept_1, intercept_2);
  150. error = right_intercept - left_intercept;
  151. return (error < EPSILON)? 1 : 0;
  152. };
  153. var ComputeXIntercept = function(V, degree) {
  154. var XLK, YLK, XNM, YNM, XMK, YMK, det, detInv, S, T, X, Y;
  155. XLK = 1.0 - 0.0;
  156. YLK = 0.0 - 0.0;
  157. XNM = V[degree].x - V[0].x;
  158. YNM = V[degree].y - V[0].y;
  159. XMK = V[0].x - 0.0;
  160. YMK = V[0].y - 0.0;
  161. det = XNM*YLK - YNM*XLK;
  162. detInv = 1.0/det;
  163. S = (XNM*YMK - YNM*XMK) * detInv;
  164. X = 0.0 + XLK * S;
  165. return X;
  166. };
  167. var Bezier = function(V, degree, t, Left, Right) {
  168. var Vtemp = new Array();
  169. for (var j =0; j <= degree; j++) {
  170. if (!Vtemp[0]) Vtemp[0] = [];
  171. Vtemp[0][j] = V[j];
  172. }
  173. for (var i = 1; i <= degree; i++) {
  174. for (var j =0 ; j <= degree - i; j++) {
  175. if (!Vtemp[i]) Vtemp[i] = [];
  176. if (!Vtemp[i][j]) Vtemp[i][j] = {};
  177. Vtemp[i][j].x = (1.0 - t) * Vtemp[i-1][j].x + t * Vtemp[i-1][j+1].x;
  178. Vtemp[i][j].y = (1.0 - t) * Vtemp[i-1][j].y + t * Vtemp[i-1][j+1].y;
  179. }
  180. }
  181. if (Left != null)
  182. for (j = 0; j <= degree; j++) Left[j] = Vtemp[j][0];
  183. if (Right != null)
  184. for (j = 0; j <= degree; j++) Right[j] = Vtemp[degree-j][j];
  185. return (Vtemp[degree][0]);
  186. };
  187. var bezCurve = [
  188. { x:0.0, y:0.0 },
  189. { x:1.0, y:2.0 },
  190. { x:3.0, y:3.0 },
  191. { x:4.0, y:2.0 }
  192. ];
  193. var arbPoint = { x:3.5, y:2.0 };
  194. var pointOnCurve;
  195. pointOnCurve = NearestPointOnCurve(arbPoint, bezCurve);
  196. jsPlumb.DistanceFromCurve = DistanceFromCurve;
  197. jsPlumb.NearestPointOnCurve = NearestPointOnCurve;
  198. })();