bezier.js 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153
  1. function closestPointToBezier( _curve, _p )
  2. {
  3. if( _curve == null )
  4. {
  5. return 0;
  6. }
  7. // record distances from point to endpoints
  8. var x0 = _curve.start.x;
  9. var y0 = _curve.start.y;
  10. var deltaX = x0-_p.x;
  11. var deltaY = y0-_p.y;
  12. var d0 = Math.sqrt(deltaX*deltaX + deltaY*deltaY);
  13. var x1 = _curve.end.x;
  14. var y1 = _curve.end.y;
  15. deltaX = x1-_p.x;
  16. deltaY = y1-_p.y;
  17. var d1 = Math.sqrt(deltaX*deltaX + deltaY*deltaY);
  18. var n = 2; // degree of input Bezier curve
  19. // array of control points
  20. var v = [];
  21. v.push(_curve.cp1);v.push(_curve.cp2);
  22. /*for( var i=0; i<=n; ++i )
  23. {
  24. v.push(_curve.getControlPoint(i));
  25. }*/
  26. // instaead of power form, convert the function whose zeros are required to Bezier form
  27. var w = toBezierForm(_p, v);
  28. // Find roots of the Bezier curve with control points stored in 'w' (algorithm is recursive, this is root depth of 0)
  29. var roots = findRoots(w, 2*n-1, 0);
  30. // compare the candidate distances to the endpoints and declare a winner :)
  31. if( d0 < d1 )
  32. {
  33. var tMinimum = 0;
  34. __dMinimum = d0;
  35. }
  36. else
  37. {
  38. tMinimum = 1;
  39. __dMinimum = d1;
  40. }
  41. // tbd - compare 2-norm squared
  42. for( i=0; i<roots.length; ++i )
  43. {
  44. var t = roots[i];
  45. if( t >= 0 && t <= 1 )
  46. {
  47. deltaX = _curve.getX(t) - _p.x;
  48. deltaY = _curve.getY(t) - _p.y;
  49. var d = Math.sqrt(deltaX*deltaX + deltaY*deltaY);
  50. if( d < __dMinimum )
  51. {
  52. tMinimum = t;
  53. __dMinimum = d;
  54. }
  55. }
  56. }
  57. // tbd - alternate optima.
  58. return tMinimum;
  59. }
  60. // compute control points of the polynomial resulting from the inner product of B(t)-P and B'(t), constructing the result as a Bezier
  61. // curve of order 2n-1, where n is the degree of B(t).
  62. function toBezierForm(_p, _v)
  63. {
  64. var row = 0; // row index
  65. var column = 0; // column index
  66. var c = []; // V(i) - P
  67. var d = []; // V(i+1) - V(i)
  68. var w = []; // control-points for Bezier curve whose zeros represent candidates for closest point to the input parametric curve
  69. var n = _v.length-1; // degree of B(t)
  70. var degree = 2*n-1; // degree of B(t) . P
  71. var pX = _p.x;
  72. var pY = _p.y;
  73. for( var i =0; i<=n; ++i )
  74. {
  75. var v = _v[i];
  76. c[i] = new Point(v.x - pX, v.y - pY);
  77. }
  78. var s = Number(n);
  79. for( i=0; i<=n-1; ++i )
  80. {
  81. v = _v[i];
  82. var v1 = _v[i+1];
  83. d[i] = new Point( s*(v1.x-v.x), s*(v1.y-v.y) );
  84. }
  85. var cd = [];
  86. // inner product table
  87. for( row=0; row<=n-1; ++row )
  88. {
  89. var di = d[row];
  90. var dX = di.x;
  91. var dY = di.y;
  92. for( var col =0; col<=n; ++col )
  93. {
  94. var k = getLinearIndex(n+1, row, col);
  95. cd[k] = dX*c[col].x + dY*c[col].y;
  96. k++;
  97. }
  98. }
  99. // Bezier is uniform parameterized
  100. var dInv = 1.0 / degree;
  101. for( i=0; i<=degree; ++i )
  102. {
  103. w[i] = new Point(Number(i)*dInv, 0);
  104. }
  105. // reference to appropriate pre-computed coefficients
  106. var z = n == 3 ? Z_CUBIC : Z_QUAD;
  107. // accumulate y-coords of the control points along the skew diagonal of the (n-1) x n matrix of c.d and z values
  108. var m = n-1;
  109. for( k=0; k<=n+m; ++k )
  110. {
  111. var lb = Math.max(0, k-m);
  112. var ub = Math.min(k, n);
  113. for( i=lb; i<=ub; ++i)
  114. {
  115. var j = k - i;
  116. var p = w[i+j];
  117. var index = getLinearIndex(n+1, j, i);
  118. p.y += cd[index]*z[index];
  119. w[i+j] = p;
  120. }
  121. }
  122. return w;
  123. }
  124. // convert 2D array indices in a k x n matrix to a linear index (this is an interim step ahead of a future implementation optimized for 1D array indexing)
  125. function getLinearIndex(_n, _row, _col)
  126. {
  127. // no range-checking; you break it ... you buy it!
  128. return _row*_n + _col;
  129. }