]> git.proxmox.com Git - extjs.git/blame - extjs/packages/charts/src/draw/PathUtil.js
projects / extjs.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
add extjs 6.0.1 sources
[extjs.git] / extjs / packages / charts / src / draw / PathUtil.js
CommitLineData
6527f429
DM		 1/**\r
2 * @private\r
3 * Singleton that provides methods used by the Ext.draw.Path\r
4 * for hit testing and finding path intersection points.\r
5 */\r
6Ext.define('Ext.draw.PathUtil', function () {\r
7 var abs = Math.abs,\r
8 pow = Math.pow,\r
9 cos = Math.cos,\r
10 acos = Math.acos,\r
11 sqrt = Math.sqrt,\r
12 PI = Math.PI;\r
13\r
14 // For extra info see: http://pomax.github.io/bezierinfo/\r
15\r
16 return {\r
17 singleton: true,\r
18\r
19 requires: [\r
20 'Ext.draw.overrides.Path',\r
21 'Ext.draw.overrides.sprite.Path',\r
22 'Ext.draw.overrides.sprite.Instancing',\r
23 'Ext.draw.overrides.Surface'\r
24 ],\r
25\r
26 /**\r
27 * @private\r
28 * Finds roots of a cubic equation in t, where t lies in the interval of [0,1].\r
29 * Based on http://www.particleincell.com/blog/2013/cubic-line-intersection/\r
30 * @param P {Number[]} Cubic equation coefficients.\r
31 * @return {Number[]} Returns an array of parametric intersection locations along the cubic,\r
32 * with -1 indicating an out-of-bounds intersection\r
33 * (before or after the end point or in the imaginary plane).\r
34 */\r
35 cubicRoots: function (P) {\r
36 var a = P[0],\r
37 b = P[1],\r
38 c = P[2],\r
39 d = P[3];\r
40\r
41 if (a === 0) {\r
42 return this.quadraticRoots(b, c, d);\r
43 }\r
44\r
45 var A = b / a,\r
46 B = c / a,\r
47 C = d / a,\r
48\r
49 Q = (3*B - pow(A, 2)) / 9,\r
50 R = (9*A*B - 27*C - 2*pow(A, 3)) / 54,\r
51 D = pow(Q, 3) + pow(R, 2), // Polynomial discriminant.\r
52 t = [],\r
53 S, T, Im, th, i,\r
54\r
55 sign = Ext.Number.sign;\r
56\r
57 if (D >= 0) { // Complex or duplicate roots.\r
58 S = sign(R + sqrt(D)) * pow(abs(R + sqrt(D)), 1/3);\r
59 T = sign(R - sqrt(D)) * pow(abs(R - sqrt(D)), 1/3);\r
60\r
61 t[0] = -A/3 + (S + T); // Real root.\r
62 t[1] = -A/3 - (S + T)/2; // Real part of complex root.\r
63 t[2] = t[1]; // Real part of complex root.\r
64 Im = abs(sqrt(3) * (S - T)/2); // Complex part of root pair.\r
65\r
66 // Discard complex roots.\r
67 if (Im !== 0) {\r
68 t[1] =- 1;\r
69 t[2] =- 1;\r
70 }\r
71\r
72 } else { // Distinct real roots.\r
73 th = acos(R / sqrt(-pow(Q, 3)));\r
74\r
75 t[0] = 2*sqrt(-Q)*cos(th/3) - A/3;\r
76 t[1] = 2*sqrt(-Q)*cos((th + 2*PI)/3) - A/3;\r
77 t[2] = 2*sqrt(-Q)*cos((th + 4*PI)/3) - A/3;\r
78 }\r
79\r
80 // Discard out of spec roots.\r
81 for (i = 0; i < 3; i++) {\r
82 if (t[i] < 0 || t[i] > 1) {\r
83 t[i] = -1;\r
84 }\r
85 }\r
86\r
87 return t;\r
88 },\r
89\r
90 /**\r
91 * @private\r
92 * Finds roots of a quadratic equation in t, where t lies in the interval of [0,1].\r
93 * Takes three quadratic equation coefficients as parameters.\r
94 * @param a {Number}\r
95 * @param b {Number}\r
96 * @param c {Number}\r
97 * @return {Array}\r
98 */\r
99 quadraticRoots: function (a, b, c) {\r
100 var D, rD, t, i;\r
101 if (a === 0) {\r
102 return this.linearRoot(b, c);\r
103 }\r
104 D = b*b - 4*a*c;\r
105 if (D === 0) { // One real root.\r
106 t = [-b/(2*a)];\r
107 } else if (D > 0) { // Distinct real roots.\r
108 rD = sqrt(D);\r
109 t = [(-b - rD) / (2*a), (-b + rD) / (2*a)];\r
110 } else { // Complex roots.\r
111 return [];\r
112 }\r
113 for (i = 0; i < t.length; i++) {\r
114 if (t[i] < 0 || t[i] > 1) {\r
115 t[i] = -1;\r
116 }\r
117 }\r
118 return t;\r
119 },\r
120\r
121 /**\r
122 * @private\r
123 * Finds roots of a linear equation in t, where t lies in the interval of [0,1].\r
124 * Takes two linear equation coefficients as parameters.\r
125 * @param a {Number}\r
126 * @param b {Number}\r
127 * @return {Array}\r
128 */\r
129 linearRoot: function (a, b) {\r
130 var t = -b/a;\r
131 if (a === 0 || t < 0 || t > 1) {\r
132 return [];\r
133 }\r
134 return [t];\r
135 },\r
136\r
137 /**\r
138 * @private\r
139 * Calculates the coefficients of a cubic function for the given coordinates.\r
140 * @param P0 {Number}\r
141 * @param P1 {Number}\r
142 * @param P2 {Number}\r
143 * @param P3 {Number}\r
144 * @return {Array}\r
145 */\r
146 bezierCoeffs: function (P0, P1, P2, P3) {\r
147 var Z = [];\r
148 Z[0] = -P0 + 3*P1 - 3*P2 + P3;\r
149 Z[1] = 3*P0 - 6*P1 + 3*P2;\r
150 Z[2] = -3*P0 + 3*P1;\r
151 Z[3] = P0;\r
152 return Z;\r
153 },\r
154\r
155 /**\r
156 * @private\r
157 * Computes intersection points between a cubic spline and a line segment.\r
158 * Takes in x/y components of cubic control points and line segment start/end points\r
159 * as parameters.\r
160 * @param px1 {Number}\r
161 * @param px2 {Number}\r
162 * @param px3 {Number}\r
163 * @param px4 {Number}\r
164 * @param py1 {Number}\r
165 * @param py2 {Number}\r
166 * @param py3 {Number}\r
167 * @param py4 {Number}\r
168 * @param x1 {Number}\r
169 * @param y1 {Number}\r
170 * @param x2 {Number}\r
171 * @param y2 {Number}\r
172 * @return {Array} Array of intersection points, where each intersection point\r
173 * is itself a two-item array [x,y].\r
174 */\r
175 cubicLineIntersections: function (px1, px2, px3, px4, py1, py2, py3, py4,\r
176 x1, y1, x2, y2) {\r
177 var P = [],\r
178 intersections = [],\r
179\r
180 // Finding line equation coefficients.\r
181 A = y1 - y2,\r
182 B = x2 - x1,\r
183 C = x1 * (y2 - y1) - y1 * (x2 - x1),\r
184\r
185 // Finding cubic Bezier curve equation coefficients.\r
186 bx = this.bezierCoeffs(px1, px2, px3, px4),\r
187 by = this.bezierCoeffs(py1, py2, py3, py4),\r
188\r
189 i, r, s,\r
190 t, tt, ttt,\r
191 cx, cy;\r
192\r
193 P[0] = A*bx[0] + B*by[0]; // t^3\r
194 P[1] = A*bx[1] + B*by[1]; // t^2\r
195 P[2] = A*bx[2] + B*by[2]; // t\r
196 P[3] = A*bx[3] + B*by[3] + C; // 1\r
197\r
198 r = this.cubicRoots(P);\r
199\r
200 // Verify the roots are in bounds of the linear segment.\r
201 for (i = 0; i < r.length; i++) {\r
202 t = r[i];\r
203\r
204 if (t < 0 || t > 1) {\r
205 continue;\r
206 }\r
207\r
208 tt = t*t;\r
209 ttt = tt*t;\r
210\r
211 cx = bx[0]*ttt + bx[1]*tt + bx[2]*t + bx[3];\r
212 cy = by[0]*ttt + by[1]*tt + by[2]*t + by[3];\r
213\r
214 // Above is intersection point assuming infinitely long line segment,\r
215 // make sure we are also in bounds of the line.\r
216 if ((x2 - x1) !== 0) { // If not vertical line\r
217 s = (cx - x1) / (x2 - x1);\r
218 } else {\r
219 s = (cy - y1) / (y2 - y1);\r
220 }\r
221 // In bounds?\r
222 if (!(s < 0 || s > 1)) {\r
223 intersections.push([cx, cy]);\r
224 }\r
225 }\r
226 return intersections;\r
227 },\r
228\r
229 /**\r
230 * @private\r
231 * Splits cubic Bezier curve into two cubic Bezier curves at point z,\r
232 * where z belongs to a range of [0, 1].\r
233 * Accepts cubic coefficients and point z as parameters.\r
234 * @param P1 {Number}\r
235 * @param P2 {Number}\r
236 * @param P3 {Number}\r
237 * @param P4 {Number}\r
238 * @param z Point to split the given curve at.\r
239 * @return {Array} Two-item array, where each item is itself an array\r
240 * of cubic coefficients.\r
241 */\r
242 splitCubic: function (P1, P2, P3, P4, z) {\r
243 var zz = z * z,\r
244 zzz = z * zz,\r
245 iz = z - 1,\r
246 izz = iz * iz,\r
247 izzz = iz * izz,\r
248 // Common point for both curves.\r
249 P = zzz * P4 - 3 * zz * iz * P3 + 3 * z * izz * P2 - izzz * P1;\r
250\r
251 return [\r
252 [\r
253 P1,\r
254 z * P2 - iz * P1,\r
255 zz * P3 - 2 * z * iz * P2 + izz * P1,\r
256 P\r
257 ],\r
258 [\r
259 P,\r
260 zz * P4 - 2 * z * iz * P3 + izz * P2,\r
261 z * P4 - iz * P3,\r
262 P4\r
263 ]\r
264 ]\r
265 },\r
266\r
267 /**\r
268 * @private\r
269 * Returns the dimension of a cubic Bezier curve in a single direction.\r
270 * @param a {Number}\r
271 * @param b {Number}\r
272 * @param c {Number}\r
273 * @param d {Number}\r
274 * @return {Array} Two-item array representing cubic's range in the given direction.\r
275 */\r
276 cubicDimension: function (a, b, c, d) {\r
277 var qa = 3 * (-a + 3 * (b - c) + d),\r
278 qb = 6 * (a - 2 * b + c),\r
279 qc = -3 * (a - b), x, y,\r
280 min = Math.min(a, d),\r
281 max = Math.max(a, d), delta;\r
282\r
283 if (qa === 0) {\r
284 if (qb === 0) {\r
285 return [min, max];\r
286 } else {\r
287 x = -qc / qb;\r
288 if (0 < x && x < 1) {\r
289 y = this.interpolateCubic(a, b, c, d, x);\r
290 min = Math.min(min, y);\r
291 max = Math.max(max, y);\r
292 }\r
293 }\r
294 } else {\r
295 delta = qb * qb - 4 * qa * qc;\r
296 if (delta >= 0) {\r
297 delta = sqrt(delta);\r
298 x = (delta - qb) / 2 / qa;\r
299 if (0 < x && x < 1) {\r
300 y = this.interpolateCubic(a, b, c, d, x);\r
301 min = Math.min(min, y);\r
302 max = Math.max(max, y);\r
303 }\r
304 if (delta > 0) {\r
305 x -= delta / qa;\r
306 if (0 < x && x < 1) {\r
307 y = this.interpolateCubic(a, b, c, d, x);\r
308 min = Math.min(min, y);\r
309 max = Math.max(max, y);\r
310 }\r
311 }\r
312 }\r
313 }\r
314 return [min, max];\r
315 },\r
316\r
317 /**\r
318 * @private\r
319 * Calculates a value of a cubic function at the given point t. In other words\r
320 * returns a * (1 - t) ^ 3 + 3 * b (1 - t) ^ 2 * t + 3 * c (1 - t) * t ^ 3 + d * t ^ 3\r
321 * for given a, b, c, d and t, where t belongs to an interval of [0, 1].\r
322 * @param a {Number}\r
323 * @param b {Number}\r
324 * @param c {Number}\r
325 * @param d {Number}\r
326 * @param t {Number}\r
327 * @return {Number}\r
328 */\r
329 interpolateCubic: function (a, b, c, d, t) {\r
330 if (t === 0) {\r
331 return a;\r
332 }\r
333 if (t === 1) {\r
334 return d;\r
335 }\r
336 var rate = (1 - t) / t;\r
337 return t * t * t * (d + rate * (3 * c + rate * (3 * b + rate * a)));\r
338 },\r
339\r
340 /**\r
341 * @private\r
342 * Computes intersection points between two cubic Bezier curve segments.\r
343 * Takes x/y components of control points for two Bezier curve segments.\r
344 * @param ax1 {Number}\r
345 * @param ax2 {Number}\r
346 * @param ax3 {Number}\r
347 * @param ax4 {Number}\r
348 * @param ay1 {Number}\r
349 * @param ay2 {Number}\r
350 * @param ay3 {Number}\r
351 * @param ay4 {Number}\r
352 * @param bx1 {Number}\r
353 * @param bx2 {Number}\r
354 * @param bx3 {Number}\r
355 * @param bx4 {Number}\r
356 * @param by1 {Number}\r
357 * @param by2 {Number}\r
358 * @param by3 {Number}\r
359 * @param by4 {Number}\r
360 * @return {Array} Array of intersection points, where each intersection point\r
361 * is itself a two-item array [x,y].\r
362 */\r
363 cubicsIntersections: function (ax1, ax2, ax3, ax4, ay1, ay2, ay3, ay4,\r
364 bx1, bx2, bx3, bx4, by1, by2, by3, by4) {\r
365 var me = this,\r
366 axDim = me.cubicDimension(ax1, ax2, ax3, ax4),\r
367 ayDim = me.cubicDimension(ay1, ay2, ay3, ay4),\r
368 bxDim = me.cubicDimension(bx1, bx2, bx3, bx4),\r
369 byDim = me.cubicDimension(by1, by2, by3, by4),\r
370 splitAx, splitAy, splitBx, splitBy,\r
371 points = [];\r
372\r
373 // Curves' bounding boxes don't intersect.\r
374 if (axDim[0] > bxDim[1] || axDim[1] < bxDim[0] || ayDim[0] > byDim[1] || ayDim[1] < byDim[0]) {\r
375 return [];\r
376 }\r
377 // Both curves occupy sub-pixel areas which is effectively their intersection point.\r
378 if (abs(ay1 - ay2) < 1 && abs(ay3 - ay4) < 1 && abs(ax1 - ax4) < 1 && abs(ax2 - ax3) < 1 &&\r
379 abs(by1 - by2) < 1 && abs(by3 - by4) < 1 && abs(bx1 - bx4) < 1 && abs(bx2 - bx3) < 1) {\r
380 return [[ (ax1 + ax4) * 0.5, (ay1 + ay2) * 0.5 ]];\r
381 }\r
382\r
383 splitAx = me.splitCubic(ax1, ax2, ax3, ax4, 0.5);\r
384 splitAy = me.splitCubic(ay1, ay2, ay3, ay4, 0.5);\r
385 splitBx = me.splitCubic(bx1, bx2, bx3, bx4, 0.5);\r
386 splitBy = me.splitCubic(by1, by2, by3, by4, 0.5);\r
387\r
388 points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[0].concat(splitAy[0], splitBx[0], splitBy[0])));\r
389 points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[0].concat(splitAy[0], splitBx[1], splitBy[1])));\r
390 points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[1].concat(splitAy[1], splitBx[0], splitBy[0])));\r
391 points.push.apply(points, me.cubicsIntersections.apply(me, splitAx[1].concat(splitAy[1], splitBx[1], splitBy[1])));\r
392\r
393 return points;\r
394 },\r
395\r
396 /**\r
397 * @private\r
398 * Returns the point [x,y] where two line segments intersect or null.\r
399 * Takes x/y components of the start and end point of the segments as parameters.\r
400 * Based on Paul Bourke's explanation:\r
401 * http://paulbourke.net/geometry/pointlineplane/\r
402 * @param x1 {Number}\r
403 * @param y1 {Number}\r
404 * @param x2 {Number}\r
405 * @param y2 {Number}\r
406 * @param x3 {Number}\r
407 * @param y3 {Number}\r
408 * @param x4 {Number}\r
409 * @param y4 {Number}\r
410 * @return {Number[]|null}\r
411 */\r
412 linesIntersection: function (x1, y1, x2, y2, x3, y3, x4, y4) {\r
413 var d = (x2 - x1) * (y4 - y3) - (y2 - y1) * (x4 - x3),\r
414 ua, ub;\r
415 if (d === 0) { // Lines are parallel.\r
416 return null;\r
417 }\r
418 ua = ( (x4 - x3) * (y1 - y3) - (x1 - x3) * (y4 - y3) ) / d;\r
419 ub = ( (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3) ) / d;\r
420 if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) {\r
421 return [\r
422 x1 + ua * (x2 - x1), // x\r
423 y1 + ua * (y2 - y1) // y\r
424 ];\r
425 }\r
426 return null; // The intersection point is outside one or both segments.\r
427 },\r
428\r
429 /**\r
430 * @private\r
431 * Checks if a point belongs to a line segment.\r
432 * Takes x/y components of the start and end points of the segment and the point's\r
433 * coordinates as parameters.\r
434 * @param x1 {Number}\r
435 * @param y1 {Number}\r
436 * @param x2 {Number}\r
437 * @param y2 {Number}\r
438 * @param x {Number}\r
439 * @param y {Number}\r
440 * @return {Boolean}\r
441 */\r
442 pointOnLine: function (x1, y1, x2, y2, x, y) {\r
443 var t, _;\r
444 if (abs(x2 - x1) < abs(y2 - y1)) {\r
445 _ = x1;\r
446 x1 = y1;\r
447 y1 = _;\r
448 _ = x2;\r
449 x2 = y2;\r
450 y2 = _;\r
451 _ = x;\r
452 x = y;\r
453 y = _;\r
454 }\r
455 t = (x - x1) / (x2 - x1);\r
456 if (t < 0 || t > 1) {\r
457 return false;\r
458 }\r
459 return abs(y1 + t * (y2 - y1) - y) < 4;\r
460 },\r
461\r
462 /**\r
463 * @private\r
464 * Checks if a point belongs to a cubic Bezier curve segment.\r
465 * Takes x/y components of the control points of the segment and the point's\r
466 * coordinates as parameters.\r
467 * @param px1 {Number}\r
468 * @param px2 {Number}\r
469 * @param px3 {Number}\r
470 * @param px4 {Number}\r
471 * @param py1 {Number}\r
472 * @param py2 {Number}\r
473 * @param py3 {Number}\r
474 * @param py4 {Number}\r
475 * @param x {Number}\r
476 * @param y {Number}\r
477 * @return {Boolean}\r
478 */\r
479 pointOnCubic: function (px1, px2, px3, px4, py1, py2, py3, py4, x, y) {\r
480 // Finding cubic Bezier curve equation coefficients.\r
481 var me = this,\r
482 bx = me.bezierCoeffs(px1, px2, px3, px4),\r
483 by = me.bezierCoeffs(py1, py2, py3, py4),\r
484 i, j, rx, ry, t;\r
485\r
486 bx[3] -= x;\r
487 by[3] -= y;\r
488\r
489 rx = me.cubicRoots(bx);\r
490 ry = me.cubicRoots(by);\r
491\r
492 for (i = 0; i < rx.length; i++) {\r
493 t = rx[i];\r
494 for (j = 0; j < ry.length; j++) {\r
495 // TODO: for more accurate results tolerance should be dynamic\r
496 // TODO: based on the length and shape of the segment.\r
497 if (t >= 0 && t <= 1 && abs(t - ry[j]) < 0.05) {\r
498 return true;\r
499 }\r
500 }\r
501 }\r
502\r
503 return false;\r
504 }\r
505\r
506 };\r
507});\r
ExtJS JS Framework