1 /* 2 Copyright 2008-2022 3 Matthias Ehmann, 4 Michael Gerhaeuser, 5 Carsten Miller, 6 Bianca Valentin, 7 Andreas Walter, 8 Alfred Wassermann, 9 Peter Wilfahrt 10 11 This file is part of JSXGraph. 12 13 JSXGraph is free software dual licensed under the GNU LGPL or MIT License. 14 15 You can redistribute it and/or modify it under the terms of the 16 17 * GNU Lesser General Public License as published by 18 the Free Software Foundation, either version 3 of the License, or 19 (at your option) any later version 20 OR 21 * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT 22 23 JSXGraph is distributed in the hope that it will be useful, 24 but WITHOUT ANY WARRANTY; without even the implied warranty of 25 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 26 GNU Lesser General Public License for more details. 27 28 You should have received a copy of the GNU Lesser General Public License and 29 the MIT License along with JSXGraph. If not, see <http://www.gnu.org/licenses/> 30 and <http://opensource.org/licenses/MIT/>. 31 */ 32 33 34 /*global JXG: true, define: true*/ 35 /*jslint nomen: true, plusplus: true*/ 36 37 /* depends: 38 jxg 39 base/constants 40 base/coords 41 math/math 42 math/numerics 43 utils/type 44 */ 45 46 /** 47 * @fileoverview This file contains the Math.Geometry namespace for calculating algebraic/geometric 48 * stuff like intersection points, angles, midpoint, and so on. 49 */ 50 51 define([ 52 'jxg', 'base/constants', 'base/coords', 'math/math', 'math/numerics', 'utils/type', 'utils/expect' 53 ], function (JXG, Const, Coords, Mat, Numerics, Type, Expect) { 54 55 "use strict"; 56 57 /** 58 * Math.Geometry namespace definition. This namespace holds geometrical algorithms, 59 * especially intersection algorithms. 60 * @name JXG.Math.Geometry 61 * @namespace 62 */ 63 Mat.Geometry = {}; 64 65 // the splitting is necessary due to the shortcut for the circumcircleMidpoint method to circumcenter. 66 67 JXG.extend(Mat.Geometry, /** @lends JXG.Math.Geometry */ { 68 /* ***************************************/ 69 /* *** GENERAL GEOMETRIC CALCULATIONS ****/ 70 /* ***************************************/ 71 72 /** 73 * Calculates the angle defined by the points A, B, C. 74 * @param {JXG.Point,Array} A A point or [x,y] array. 75 * @param {JXG.Point,Array} B Another point or [x,y] array. 76 * @param {JXG.Point,Array} C A circle - no, of course the third point or [x,y] array. 77 * @deprecated Use {@link JXG.Math.Geometry.rad} instead. 78 * @see #rad 79 * @see #trueAngle 80 * @returns {Number} The angle in radian measure. 81 */ 82 angle: function (A, B, C) { 83 var u, v, s, t, 84 a = [], 85 b = [], 86 c = []; 87 88 JXG.deprecated('Geometry.angle()', 'Geometry.rad()'); 89 if (A.coords) { 90 a[0] = A.coords.usrCoords[1]; 91 a[1] = A.coords.usrCoords[2]; 92 } else { 93 a[0] = A[0]; 94 a[1] = A[1]; 95 } 96 97 if (B.coords) { 98 b[0] = B.coords.usrCoords[1]; 99 b[1] = B.coords.usrCoords[2]; 100 } else { 101 b[0] = B[0]; 102 b[1] = B[1]; 103 } 104 105 if (C.coords) { 106 c[0] = C.coords.usrCoords[1]; 107 c[1] = C.coords.usrCoords[2]; 108 } else { 109 c[0] = C[0]; 110 c[1] = C[1]; 111 } 112 113 u = a[0] - b[0]; 114 v = a[1] - b[1]; 115 s = c[0] - b[0]; 116 t = c[1] - b[1]; 117 118 return Math.atan2(u * t - v * s, u * s + v * t); 119 }, 120 121 /** 122 * Calculates the angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 123 * @param {JXG.Point,Array} A Point or [x,y] array 124 * @param {JXG.Point,Array} B Point or [x,y] array 125 * @param {JXG.Point,Array} C Point or [x,y] array 126 * @see #rad 127 * @returns {Number} The angle in degrees. 128 */ 129 trueAngle: function (A, B, C) { 130 return this.rad(A, B, C) * 57.295779513082323; // *180.0/Math.PI; 131 }, 132 133 /** 134 * Calculates the internal angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 135 * @param {JXG.Point,Array} A Point or [x,y] array 136 * @param {JXG.Point,Array} B Point or [x,y] array 137 * @param {JXG.Point,Array} C Point or [x,y] array 138 * @see #trueAngle 139 * @returns {Number} Angle in radians. 140 */ 141 rad: function (A, B, C) { 142 var ax, ay, bx, by, cx, cy, phi; 143 144 if (A.coords) { 145 ax = A.coords.usrCoords[1]; 146 ay = A.coords.usrCoords[2]; 147 } else { 148 ax = A[0]; 149 ay = A[1]; 150 } 151 152 if (B.coords) { 153 bx = B.coords.usrCoords[1]; 154 by = B.coords.usrCoords[2]; 155 } else { 156 bx = B[0]; 157 by = B[1]; 158 } 159 160 if (C.coords) { 161 cx = C.coords.usrCoords[1]; 162 cy = C.coords.usrCoords[2]; 163 } else { 164 cx = C[0]; 165 cy = C[1]; 166 } 167 168 phi = Math.atan2(cy - by, cx - bx) - Math.atan2(ay - by, ax - bx); 169 170 if (phi < 0) { 171 phi += 6.2831853071795862; 172 } 173 174 return phi; 175 }, 176 177 /** 178 * Calculates a point on the bisection line between the three points A, B, C. 179 * As a result, the bisection line is defined by two points: 180 * Parameter B and the point with the coordinates calculated in this function. 181 * Does not work for ideal points. 182 * @param {JXG.Point} A Point 183 * @param {JXG.Point} B Point 184 * @param {JXG.Point} C Point 185 * @param [board=A.board] Reference to the board 186 * @returns {JXG.Coords} Coordinates of the second point defining the bisection. 187 */ 188 angleBisector: function (A, B, C, board) { 189 var phiA, phiC, phi, 190 Ac = A.coords.usrCoords, 191 Bc = B.coords.usrCoords, 192 Cc = C.coords.usrCoords, 193 x, y; 194 195 if (!Type.exists(board)) { 196 board = A.board; 197 } 198 199 // Parallel lines 200 if (Bc[0] === 0) { 201 return new Coords(Const.COORDS_BY_USER, 202 [1, (Ac[1] + Cc[1]) * 0.5, (Ac[2] + Cc[2]) * 0.5], board); 203 } 204 205 // Non-parallel lines 206 x = Ac[1] - Bc[1]; 207 y = Ac[2] - Bc[2]; 208 phiA = Math.atan2(y, x); 209 210 x = Cc[1] - Bc[1]; 211 y = Cc[2] - Bc[2]; 212 phiC = Math.atan2(y, x); 213 214 phi = (phiA + phiC) * 0.5; 215 216 if (phiA > phiC) { 217 phi += Math.PI; 218 } 219 220 x = Math.cos(phi) + Bc[1]; 221 y = Math.sin(phi) + Bc[2]; 222 223 return new Coords(Const.COORDS_BY_USER, [1, x, y], board); 224 }, 225 226 // /** 227 // * Calculates a point on the m-section line between the three points A, B, C. 228 // * As a result, the m-section line is defined by two points: 229 // * Parameter B and the point with the coordinates calculated in this function. 230 // * The m-section generalizes the bisector to any real number. 231 // * For example, the trisectors of an angle are simply the 1/3-sector and the 2/3-sector. 232 // * Does not work for ideal points. 233 // * @param {JXG.Point} A Point 234 // * @param {JXG.Point} B Point 235 // * @param {JXG.Point} C Point 236 // * @param {Number} m Number 237 // * @param [board=A.board] Reference to the board 238 // * @returns {JXG.Coords} Coordinates of the second point defining the bisection. 239 // */ 240 // angleMsector: function (A, B, C, m, board) { 241 // var phiA, phiC, phi, 242 // Ac = A.coords.usrCoords, 243 // Bc = B.coords.usrCoords, 244 // Cc = C.coords.usrCoords, 245 // x, y; 246 247 // if (!Type.exists(board)) { 248 // board = A.board; 249 // } 250 251 // // Parallel lines 252 // if (Bc[0] === 0) { 253 // return new Coords(Const.COORDS_BY_USER, 254 // [1, (Ac[1] + Cc[1]) * m, (Ac[2] + Cc[2]) * m], board); 255 // } 256 257 // // Non-parallel lines 258 // x = Ac[1] - Bc[1]; 259 // y = Ac[2] - Bc[2]; 260 // phiA = Math.atan2(y, x); 261 262 // x = Cc[1] - Bc[1]; 263 // y = Cc[2] - Bc[2]; 264 // phiC = Math.atan2(y, x); 265 266 // phi = phiA + ((phiC - phiA) * m); 267 268 // if (phiA - phiC > Math.PI) { 269 // phi += 2*m*Math.PI; 270 // } 271 272 // x = Math.cos(phi) + Bc[1]; 273 // y = Math.sin(phi) + Bc[2]; 274 275 // return new Coords(Const.COORDS_BY_USER, [1, x, y], board); 276 // }, 277 278 /** 279 * Reflects the point along the line. 280 * @param {JXG.Line} line Axis of reflection. 281 * @param {JXG.Point} point Point to reflect. 282 * @param [board=point.board] Reference to the board 283 * @returns {JXG.Coords} Coordinates of the reflected point. 284 */ 285 reflection: function (line, point, board) { 286 // (v,w) defines the slope of the line 287 var x0, y0, x1, y1, v, w, mu, 288 pc = point.coords.usrCoords, 289 p1c = line.point1.coords.usrCoords, 290 p2c = line.point2.coords.usrCoords; 291 292 if (!Type.exists(board)) { 293 board = point.board; 294 } 295 296 v = p2c[1] - p1c[1]; 297 w = p2c[2] - p1c[2]; 298 299 x0 = pc[1] - p1c[1]; 300 y0 = pc[2] - p1c[2]; 301 302 mu = (v * y0 - w * x0) / (v * v + w * w); 303 304 // point + mu*(-y,x) is the perpendicular foot 305 x1 = pc[1] + 2 * mu * w; 306 y1 = pc[2] - 2 * mu * v; 307 308 return new Coords(Const.COORDS_BY_USER, [x1, y1], board); 309 }, 310 311 /** 312 * Computes the new position of a point which is rotated 313 * around a second point (called rotpoint) by the angle phi. 314 * @param {JXG.Point} rotpoint Center of the rotation 315 * @param {JXG.Point} point point to be rotated 316 * @param {Number} phi rotation angle in arc length 317 * @param {JXG.Board} [board=point.board] Reference to the board 318 * @returns {JXG.Coords} Coordinates of the new position. 319 */ 320 rotation: function (rotpoint, point, phi, board) { 321 var x0, y0, c, s, x1, y1, 322 pc = point.coords.usrCoords, 323 rotpc = rotpoint.coords.usrCoords; 324 325 if (!Type.exists(board)) { 326 board = point.board; 327 } 328 329 x0 = pc[1] - rotpc[1]; 330 y0 = pc[2] - rotpc[2]; 331 332 c = Math.cos(phi); 333 s = Math.sin(phi); 334 335 x1 = x0 * c - y0 * s + rotpc[1]; 336 y1 = x0 * s + y0 * c + rotpc[2]; 337 338 return new Coords(Const.COORDS_BY_USER, [x1, y1], board); 339 }, 340 341 /** 342 * Calculates the coordinates of a point on the perpendicular to the given line through 343 * the given point. 344 * @param {JXG.Line} line A line. 345 * @param {JXG.Point} point Point which is projected to the line. 346 * @param {JXG.Board} [board=point.board] Reference to the board 347 * @returns {Array} Array of length two containing coordinates of a point on the perpendicular to the given line 348 * through the given point and boolean flag "change". 349 */ 350 perpendicular: function (line, point, board) { 351 var x, y, change, 352 c, z, 353 A = line.point1.coords.usrCoords, 354 B = line.point2.coords.usrCoords, 355 C = point.coords.usrCoords; 356 357 if (!Type.exists(board)) { 358 board = point.board; 359 } 360 361 // special case: point is the first point of the line 362 if (point === line.point1) { 363 x = A[1] + B[2] - A[2]; 364 y = A[2] - B[1] + A[1]; 365 z = A[0] * B[0]; 366 367 if (Math.abs(z) < Mat.eps) { 368 x = B[2]; 369 y = -B[1]; 370 } 371 c = [z, x, y]; 372 change = true; 373 374 // special case: point is the second point of the line 375 } else if (point === line.point2) { 376 x = B[1] + A[2] - B[2]; 377 y = B[2] - A[1] + B[1]; 378 z = A[0] * B[0]; 379 380 if (Math.abs(z) < Mat.eps) { 381 x = A[2]; 382 y = -A[1]; 383 } 384 c = [z, x, y]; 385 change = false; 386 387 // special case: point lies somewhere else on the line 388 } else if (Math.abs(Mat.innerProduct(C, line.stdform, 3)) < Mat.eps) { 389 x = C[1] + B[2] - C[2]; 390 y = C[2] - B[1] + C[1]; 391 z = B[0]; 392 393 if (Math.abs(z) < Mat.eps) { 394 x = B[2]; 395 y = -B[1]; 396 } 397 398 change = true; 399 if (Math.abs(z) > Mat.eps && Math.abs(x - C[1]) < Mat.eps && Math.abs(y - C[2]) < Mat.eps) { 400 x = C[1] + A[2] - C[2]; 401 y = C[2] - A[1] + C[1]; 402 change = false; 403 } 404 c = [z, x, y]; 405 406 // general case: point does not lie on the line 407 // -> calculate the foot of the dropped perpendicular 408 } else { 409 c = [0, line.stdform[1], line.stdform[2]]; 410 c = Mat.crossProduct(c, C); // perpendicuar to line 411 c = Mat.crossProduct(c, line.stdform); // intersection of line and perpendicular 412 change = true; 413 } 414 415 return [new Coords(Const.COORDS_BY_USER, c, board), change]; 416 }, 417 418 /** 419 * @deprecated Please use {@link JXG.Math.Geometry.circumcenter} instead. 420 */ 421 circumcenterMidpoint: function () { 422 JXG.deprecated('Geometry.circumcenterMidpoint()', 'Geometry.circumcenter()'); 423 this.circumcenter.apply(this, arguments); 424 }, 425 426 /** 427 * Calculates the center of the circumcircle of the three given points. 428 * @param {JXG.Point} point1 Point 429 * @param {JXG.Point} point2 Point 430 * @param {JXG.Point} point3 Point 431 * @param {JXG.Board} [board=point1.board] Reference to the board 432 * @returns {JXG.Coords} Coordinates of the center of the circumcircle of the given points. 433 */ 434 circumcenter: function (point1, point2, point3, board) { 435 var u, v, m1, m2, 436 A = point1.coords.usrCoords, 437 B = point2.coords.usrCoords, 438 C = point3.coords.usrCoords; 439 440 if (!Type.exists(board)) { 441 board = point1.board; 442 } 443 444 u = [B[0] - A[0], -B[2] + A[2], B[1] - A[1]]; 445 v = [(A[0] + B[0]) * 0.5, (A[1] + B[1]) * 0.5, (A[2] + B[2]) * 0.5]; 446 m1 = Mat.crossProduct(u, v); 447 448 u = [C[0] - B[0], -C[2] + B[2], C[1] - B[1]]; 449 v = [(B[0] + C[0]) * 0.5, (B[1] + C[1]) * 0.5, (B[2] + C[2]) * 0.5]; 450 m2 = Mat.crossProduct(u, v); 451 452 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(m1, m2), board); 453 }, 454 455 /** 456 * Calculates the Euclidean distance for two given arrays of the same length. 457 * @param {Array} array1 Array of Number 458 * @param {Array} array2 Array of Number 459 * @param {Number} [n] Length of the arrays. Default is the minimum length of the given arrays. 460 * @returns {Number} Euclidean distance of the given vectors. 461 */ 462 distance: function (array1, array2, n) { 463 var i, 464 sum = 0; 465 466 if (!n) { 467 n = Math.min(array1.length, array2.length); 468 } 469 470 for (i = 0; i < n; i++) { 471 sum += (array1[i] - array2[i]) * (array1[i] - array2[i]); 472 } 473 474 return Math.sqrt(sum); 475 }, 476 477 /** 478 * Calculates Euclidean distance for two given arrays of the same length. 479 * If one of the arrays contains a zero in the first coordinate, and the Euclidean distance 480 * is different from zero it is a point at infinity and we return Infinity. 481 * @param {Array} array1 Array containing elements of type number. 482 * @param {Array} array2 Array containing elements of type number. 483 * @param {Number} [n] Length of the arrays. Default is the minimum length of the given arrays. 484 * @returns {Number} Euclidean (affine) distance of the given vectors. 485 */ 486 affineDistance: function (array1, array2, n) { 487 var d; 488 489 d = this.distance(array1, array2, n); 490 491 if (d > Mat.eps && (Math.abs(array1[0]) < Mat.eps || Math.abs(array2[0]) < Mat.eps)) { 492 return Infinity; 493 } 494 495 return d; 496 }, 497 498 /** 499 * Affine ratio of three collinear points a, b, c: (c - a) / (b - a). 500 * If r > 1 or r < 0 then c is outside of the segment ab. 501 * 502 * @param {Array|JXG.Coords} a 503 * @param {Array|JXG.Coords} b 504 * @param {Array|JXG.Coords} c 505 * @returns {Number} affine ratio (c - a) / (b - a) 506 */ 507 affineRatio: function(a, b, c) { 508 var r = 0.0, dx; 509 510 if (Type.exists(a.usrCoords)) { 511 a = a.usrCoords; 512 } 513 if (Type.exists(b.usrCoords)) { 514 b = b.usrCoords; 515 } 516 if (Type.exists(c.usrCoords)) { 517 c = c.usrCoords; 518 } 519 520 dx = b[1] - a[1]; 521 522 if (Math.abs(dx) > Mat.eps) { 523 r = (c[1] - a[1]) / dx; 524 } else { 525 r = (c[2] - a[2]) / (b[2] - a[2]); 526 } 527 return r; 528 }, 529 530 /** 531 * Sort vertices counter clockwise starting with the first point. 532 * 533 * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 534 * 535 * @returns {Array} 536 */ 537 sortVertices: function (p) { 538 var ll, 539 ps = Expect.each(p, Expect.coordsArray), 540 N = ps.length, 541 lastPoint = null; 542 543 // If the last point equals the first point, we take the last point out of the array. 544 // It may be that the several points at the end of the array are equal to the first point. 545 // The polygonal chain is been closed by JSXGraph, but this may also have been done by the user. 546 // Therefore, we use a while lopp to pop the last points. 547 while (ps[0][0] === ps[N - 1][0] && ps[0][1] === ps[N - 1][1] && ps[0][2] === ps[N - 1][2]) { 548 lastPoint = ps.pop(); 549 N--; 550 } 551 // Find the point with the lowest y value 552 // for (i = 1; i < N; i++) { 553 // if ((ps[i][2] < ps[0][2]) || 554 // // if the current and the lowest point have the same y value, pick the one with 555 // // the lowest x value. 556 // (Math.abs(ps[i][2] - ps[0][2]) < Mat.eps && ps[i][1] < ps[0][1])) { 557 // console.log(i, 0); 558 // ps = Type.swap(ps, i, 0); 559 // } 560 // } 561 562 ll = ps[0]; 563 // Sort ps in increasing order of the angle between a point and the first point ll. 564 // If a point is equal to the first point ll, the angle is defined to be -Infinity. 565 // Otherwise, atan2 would return zero, which is a value which also attained by points 566 // on the same horizontal line. 567 ps.sort(function (a, b) { 568 var rad1 = (a[2] === ll[2] && a[1] === ll[1]) ? -Infinity : Math.atan2(a[2] - ll[2], a[1] - ll[1]), 569 rad2 = (b[2] === ll[2] && b[1] === ll[1]) ? -Infinity : Math.atan2(b[2] - ll[2], b[1] - ll[1]); 570 571 return rad1 - rad2; 572 }); 573 574 // If the last point has been taken out of the array, we put it in again. 575 if (lastPoint !== null) { 576 ps.push(lastPoint); 577 } 578 579 return ps; 580 }, 581 582 /** 583 * Signed triangle area of the three points given. 584 * 585 * @param {JXG.Point|JXG.Coords|Array} p1 586 * @param {JXG.Point|JXG.Coords|Array} p2 587 * @param {JXG.Point|JXG.Coords|Array} p3 588 * 589 * @returns {Number} 590 */ 591 signedTriangle: function (p1, p2, p3) { 592 var A = Expect.coordsArray(p1), 593 B = Expect.coordsArray(p2), 594 C = Expect.coordsArray(p3); 595 596 return 0.5 * ((B[1] - A[1]) * (C[2] - A[2]) - (B[2] - A[2]) * (C[1] - A[1])); 597 }, 598 599 /** 600 * Determine the signed area of a non-selfintersecting polygon. 601 * Surveyor's Formula 602 * 603 * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 604 * @param {Boolean} [sort=true] 605 * 606 * @returns {Number} 607 */ 608 signedPolygon: function (p, sort) { 609 var i, N, 610 A = 0, 611 ps = Expect.each(p, Expect.coordsArray); 612 613 if (sort === undefined) { 614 sort = true; 615 } 616 617 if (!sort) { 618 ps = this.sortVertices(ps); 619 } else { 620 // Make sure the polygon is closed. If it is already closed this won't change the sum because the last 621 // summand will be 0. 622 ps.unshift(ps[ps.length - 1]); 623 } 624 625 N = ps.length; 626 627 for (i = 1; i < N; i++) { 628 A += ps[i - 1][1] * ps[i][2] - ps[i][1] * ps[i - 1][2]; 629 } 630 631 return 0.5 * A; 632 }, 633 634 /** 635 * Calculate the complex hull of a point cloud. 636 * 637 * @param {Array} points An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 638 * 639 * @returns {Array} 640 */ 641 GrahamScan: function (points) { 642 var i, 643 M = 1, 644 ps = Expect.each(points, Expect.coordsArray), 645 N = ps.length; 646 647 ps = this.sortVertices(ps); 648 N = ps.length; 649 650 for (i = 2; i < N; i++) { 651 while (this.signedTriangle(ps[M - 1], ps[M], ps[i]) <= 0) { 652 if (M > 1) { 653 M -= 1; 654 } else if (i === N - 1) { 655 break; 656 } 657 i += 1; 658 } 659 660 M += 1; 661 ps = Type.swap(ps, M, i); 662 } 663 664 return ps.slice(0, M); 665 }, 666 667 /** 668 * A line can be a segment, a straight, or a ray. So it is not always delimited by point1 and point2 669 * calcStraight determines the visual start point and end point of the line. A segment is only drawn 670 * from start to end point, a straight line is drawn until it meets the boards boundaries. 671 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 672 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and 673 * set by this method. 674 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set 675 * by this method. 676 * @param {Number} margin Optional margin, to avoid the display of the small sides of lines. 677 * @returns null 678 * @see Line 679 * @see JXG.Line 680 */ 681 calcStraight: function (el, point1, point2, margin) { 682 var takePoint1, takePoint2, intersection, intersect1, intersect2, straightFirst, straightLast, 683 c, p1, p2; 684 685 if (!Type.exists(margin)) { 686 // Enlarge the drawable region slightly. This hides the small sides 687 // of thick lines in most cases. 688 margin = 10; 689 } 690 691 straightFirst = Type.evaluate(el.visProp.straightfirst); 692 straightLast = Type.evaluate(el.visProp.straightlast); 693 694 // If one of the point is an ideal point in homogeneous coordinates 695 // drawing of line segments or rays are not possible. 696 if (Math.abs(point1.scrCoords[0]) < Mat.eps) { 697 straightFirst = true; 698 } 699 if (Math.abs(point2.scrCoords[0]) < Mat.eps) { 700 straightLast = true; 701 } 702 703 // Do nothing in case of line segments (inside or outside of the board) 704 if (!straightFirst && !straightLast) { 705 return; 706 } 707 708 // Compute the stdform of the line in screen coordinates. 709 c = []; 710 c[0] = el.stdform[0] - 711 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX + 712 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY; 713 c[1] = el.stdform[1] / el.board.unitX; 714 c[2] = -el.stdform[2] / el.board.unitY; 715 716 // p1=p2 717 if (isNaN(c[0] + c[1] + c[2])) { 718 return; 719 } 720 721 takePoint1 = false; 722 takePoint2 = false; 723 724 // Line starts at point1 and point1 is inside the board 725 takePoint1 = !straightFirst && 726 Math.abs(point1.usrCoords[0]) >= Mat.eps && 727 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth && 728 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight; 729 730 // Line ends at point2 and point2 is inside the board 731 takePoint2 = !straightLast && 732 Math.abs(point2.usrCoords[0]) >= Mat.eps && 733 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth && 734 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight; 735 736 // Intersect the line with the four borders of the board. 737 intersection = this.meetLineBoard(c, el.board, margin); 738 intersect1 = intersection[0]; 739 intersect2 = intersection[1]; 740 741 /** 742 * At this point we have four points: 743 * point1 and point2 are the first and the second defining point on the line, 744 * intersect1, intersect2 are the intersections of the line with border around the board. 745 */ 746 747 /* 748 * Here we handle rays where both defining points are outside of the board. 749 */ 750 // If both points are outside and the complete ray is outside we do nothing 751 if (!takePoint1 && !takePoint2) { 752 // Ray starting at point 1 753 if (!straightFirst && straightLast && 754 !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) { 755 return; 756 } 757 758 // Ray starting at point 2 759 if (straightFirst && !straightLast && 760 !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) { 761 return; 762 } 763 } 764 765 /* 766 * If at least one of the defining points is outside of the board 767 * we take intersect1 or intersect2 as one of the end points 768 * The order is also important for arrows of axes 769 */ 770 if (!takePoint1) { 771 if (!takePoint2) { 772 // Two border intersection points are used 773 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 774 p1 = intersect1; 775 p2 = intersect2; 776 } else { 777 p2 = intersect1; 778 p1 = intersect2; 779 } 780 } else { 781 // One border intersection points is used 782 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 783 p1 = intersect1; 784 } else { 785 p1 = intersect2; 786 } 787 } 788 } else { 789 if (!takePoint2) { 790 // One border intersection points is used 791 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 792 p2 = intersect2; 793 } else { 794 p2 = intersect1; 795 } 796 } 797 } 798 799 if (p1) { 800 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1)); 801 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords); 802 } 803 804 if (p2) { 805 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1)); 806 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords); 807 } 808 }, 809 810 /** 811 * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2. 812 * 813 * This method adjusts the line's delimiting points taking into account its nature, the viewport defined 814 * by the board. 815 * 816 * A segment is delimited by start and end point, a straight line or ray is delimited until it meets the 817 * boards boundaries. However, if the line has infinite ticks, it will be delimited by the projection of 818 * the boards vertices onto itself. 819 * 820 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 821 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and 822 * set by this method. 823 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set 824 * by this method. 825 * @see Line 826 * @see JXG.Line 827 */ 828 calcLineDelimitingPoints: function (el, point1, point2) { 829 var distP1P2, boundingBox, lineSlope, 830 intersect1, intersect2, straightFirst, straightLast, 831 c, p1, p2, 832 takePoint1 = false, 833 takePoint2 = false; 834 835 straightFirst = Type.evaluate(el.visProp.straightfirst); 836 straightLast = Type.evaluate(el.visProp.straightlast); 837 838 // If one of the point is an ideal point in homogeneous coordinates 839 // drawing of line segments or rays are not possible. 840 if (Math.abs(point1.scrCoords[0]) < Mat.eps) { 841 straightFirst = true; 842 } 843 if (Math.abs(point2.scrCoords[0]) < Mat.eps) { 844 straightLast = true; 845 } 846 847 // Compute the stdform of the line in screen coordinates. 848 c = []; 849 c[0] = el.stdform[0] - 850 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX + 851 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY; 852 c[1] = el.stdform[1] / el.board.unitX; 853 c[2] = -el.stdform[2] / el.board.unitY; 854 855 // p1=p2 856 if (isNaN(c[0] + c[1] + c[2])) { 857 return; 858 } 859 860 takePoint1 = !straightFirst; 861 takePoint2 = !straightLast; 862 // Intersect the board vertices on the line to establish the available visual space for the infinite ticks 863 // Based on the slope of the line we can optimise and only project the two outer vertices 864 865 // boundingBox = [x1, y1, x2, y2] upper left, lower right vertices 866 boundingBox = el.board.getBoundingBox(); 867 lineSlope = el.getSlope(); 868 if (lineSlope >= 0) { 869 // project vertices (x2,y1) (x1, y2) 870 intersect1 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[2], boundingBox[1]] } }, el, el.board); 871 intersect2 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[0], boundingBox[3]] } }, el, el.board); 872 } else { 873 // project vertices (x1, y1) (x2, y2) 874 intersect1 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[0], boundingBox[1]] } }, el, el.board); 875 intersect2 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[2], boundingBox[3]] } }, el, el.board); 876 } 877 878 /** 879 * we have four points: 880 * point1 and point2 are the first and the second defining point on the line, 881 * intersect1, intersect2 are the intersections of the line with border around the board. 882 */ 883 884 /* 885 * Here we handle rays/segments where both defining points are outside of the board. 886 */ 887 if (!takePoint1 && !takePoint2) { 888 // Segment, if segment does not cross the board, do nothing 889 if (!straightFirst && !straightLast) { 890 distP1P2 = point1.distance(Const.COORDS_BY_USER, point2); 891 // if intersect1 not between point1 and point2 892 if (Math.abs(point1.distance(Const.COORDS_BY_USER, intersect1) + 893 intersect1.distance(Const.COORDS_BY_USER, point2) - distP1P2) > Mat.eps) { 894 return; 895 } 896 // if insersect2 not between point1 and point2 897 if (Math.abs(point1.distance(Const.COORDS_BY_USER, intersect2) + 898 intersect2.distance(Const.COORDS_BY_USER, point2) - distP1P2) > Mat.eps) { 899 return; 900 } 901 } 902 903 // If both points are outside and the complete ray is outside we do nothing 904 // Ray starting at point 1 905 if (!straightFirst && straightLast && 906 !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) { 907 return; 908 } 909 910 // Ray starting at point 2 911 if (straightFirst && !straightLast && 912 !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) { 913 return; 914 } 915 } 916 917 /* 918 * If at least one of the defining points is outside of the board 919 * we take intersect1 or intersect2 as one of the end points 920 * The order is also important for arrows of axes 921 */ 922 if (!takePoint1) { 923 if (!takePoint2) { 924 // Two border intersection points are used 925 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 926 p1 = intersect1; 927 p2 = intersect2; 928 } else { 929 p2 = intersect1; 930 p1 = intersect2; 931 } 932 } else { 933 // One border intersection points is used 934 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 935 p1 = intersect1; 936 } else { 937 p1 = intersect2; 938 } 939 } 940 } else { 941 if (!takePoint2) { 942 // One border intersection points is used 943 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 944 p2 = intersect2; 945 } else { 946 p2 = intersect1; 947 } 948 } 949 } 950 951 if (p1) { 952 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1)); 953 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords); 954 } 955 956 if (p2) { 957 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1)); 958 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords); 959 } 960 }, 961 962 /** 963 * Calculates the visProp.position corresponding to a given angle. 964 * @param {number} angle angle in radians. Must be in range (-2pi,2pi). 965 */ 966 calcLabelQuadrant: function(angle) { 967 var q; 968 if (angle < 0) { 969 angle += 2*Math.PI; 970 } 971 q = Math.floor((angle+Math.PI/8)/(Math.PI/4))%8; 972 return ['rt','urt','top','ulft','lft','llft','lrt'][q]; 973 }, 974 975 /** 976 * The vectors <tt>p2-p1</tt> and <tt>i2-i1</tt> are supposed to be collinear. If their cosine is positive 977 * they point into the same direction otherwise they point in opposite direction. 978 * @param {JXG.Coords} p1 979 * @param {JXG.Coords} p2 980 * @param {JXG.Coords} i1 981 * @param {JXG.Coords} i2 982 * @returns {Boolean} True, if <tt>p2-p1</tt> and <tt>i2-i1</tt> point into the same direction 983 */ 984 isSameDir: function (p1, p2, i1, i2) { 985 var dpx = p2.usrCoords[1] - p1.usrCoords[1], 986 dpy = p2.usrCoords[2] - p1.usrCoords[2], 987 dix = i2.usrCoords[1] - i1.usrCoords[1], 988 diy = i2.usrCoords[2] - i1.usrCoords[2]; 989 990 if (Math.abs(p2.usrCoords[0]) < Mat.eps) { 991 dpx = p2.usrCoords[1]; 992 dpy = p2.usrCoords[2]; 993 } 994 995 if (Math.abs(p1.usrCoords[0]) < Mat.eps) { 996 dpx = -p1.usrCoords[1]; 997 dpy = -p1.usrCoords[2]; 998 } 999 1000 return dpx * dix + dpy * diy >= 0; 1001 }, 1002 1003 /** 1004 * If you're looking from point "start" towards point "s" and you can see the point "p", return true. 1005 * Otherwise return false. 1006 * @param {JXG.Coords} start The point you're standing on. 1007 * @param {JXG.Coords} p The point in which direction you're looking. 1008 * @param {JXG.Coords} s The point that should be visible. 1009 * @returns {Boolean} True, if from start the point p is in the same direction as s is, that means s-start = k*(p-start) with k>=0. 1010 */ 1011 isSameDirection: function (start, p, s) { 1012 var dx, dy, sx, sy, r = false; 1013 1014 dx = p.usrCoords[1] - start.usrCoords[1]; 1015 dy = p.usrCoords[2] - start.usrCoords[2]; 1016 1017 sx = s.usrCoords[1] - start.usrCoords[1]; 1018 sy = s.usrCoords[2] - start.usrCoords[2]; 1019 1020 if (Math.abs(dx) < Mat.eps) { 1021 dx = 0; 1022 } 1023 1024 if (Math.abs(dy) < Mat.eps) { 1025 dy = 0; 1026 } 1027 1028 if (Math.abs(sx) < Mat.eps) { 1029 sx = 0; 1030 } 1031 1032 if (Math.abs(sy) < Mat.eps) { 1033 sy = 0; 1034 } 1035 1036 if (dx >= 0 && sx >= 0) { 1037 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0); 1038 } else if (dx <= 0 && sx <= 0) { 1039 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0); 1040 } 1041 1042 return r; 1043 }, 1044 1045 /****************************************/ 1046 /**** INTERSECTIONS ****/ 1047 /****************************************/ 1048 1049 /** 1050 * Generate the function which computes the coordinates of the intersection point. 1051 * Primarily used in {@link JXG.Point#createIntersectionPoint}. 1052 * @param {JXG.Board} board object 1053 * @param {JXG.Line,JXG.Circle_JXG.Line,JXG.Circle_Number} el1,el2,i The result will be a intersection point on el1 and el2. 1054 * i determines the intersection point if two points are available: <ul> 1055 * <li>i==0: use the positive square root,</li> 1056 * <li>i==1: use the negative square root.</li></ul> 1057 * See further {@link JXG.Point#createIntersectionPoint}. 1058 * @param {Boolean} alwaysintersect. Flag that determines if segments and arc can have an outer intersection point 1059 * on their defining line or circle. 1060 * @returns {Function} Function returning a {@link JXG.Coords} object that determines 1061 * the intersection point. 1062 */ 1063 intersectionFunction: function (board, el1, el2, i, j, alwaysintersect) { 1064 var func, that = this, 1065 el1_isArcType = false, 1066 el2_isArcType = false; 1067 1068 el1_isArcType = (el1.elementClass === Const.OBJECT_CLASS_CURVE && 1069 (el1.type === Const.OBJECT_TYPE_ARC || el1.type === Const.OBJECT_TYPE_SECTOR) 1070 ) ? true : false; 1071 el2_isArcType = (el2.elementClass === Const.OBJECT_CLASS_CURVE && 1072 (el2.type === Const.OBJECT_TYPE_ARC || el2.type === Const.OBJECT_TYPE_SECTOR) 1073 ) ? true : false; 1074 1075 if ((el1.elementClass === Const.OBJECT_CLASS_CURVE || el2.elementClass === Const.OBJECT_CLASS_CURVE) && 1076 (el1.elementClass === Const.OBJECT_CLASS_CURVE || el1.elementClass === Const.OBJECT_CLASS_CIRCLE) && 1077 (el2.elementClass === Const.OBJECT_CLASS_CURVE || el2.elementClass === Const.OBJECT_CLASS_CIRCLE) /*&& 1078 !(el1_isArcType && el2_isArcType)*/ ) { 1079 // curve - curve 1080 // with the exception that both elements are arc types 1081 /** @ignore */ 1082 func = function () { 1083 return that.meetCurveCurve(el1, el2, i, j, el1.board); 1084 }; 1085 1086 } else if (( 1087 el1.elementClass === Const.OBJECT_CLASS_CURVE && 1088 !el1_isArcType && 1089 el2.elementClass === Const.OBJECT_CLASS_LINE 1090 ) || 1091 ( 1092 el2.elementClass === Const.OBJECT_CLASS_CURVE && 1093 !el2_isArcType && 1094 el1.elementClass === Const.OBJECT_CLASS_LINE 1095 ) 1096 ) { 1097 // curve - line (this includes intersections between conic sections and lines) 1098 // with the exception that the curve is of arc type 1099 /** @ignore */ 1100 func = function () { 1101 return that.meetCurveLine(el1, el2, i, el1.board, alwaysintersect); 1102 }; 1103 1104 } else if (el1.type === Const.OBJECT_TYPE_POLYGON || el2.type === Const.OBJECT_TYPE_POLYGON) { 1105 // polygon - other 1106 // Uses the Greiner-Hormann clipping algorithm 1107 // Not implemented: polygon - point 1108 1109 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1110 // line - path 1111 /** @ignore */ 1112 func = function () { 1113 return that.meetPolygonLine(el2, el1, i, el1.board, alwaysintersect); 1114 }; 1115 } else if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1116 // path - line 1117 func = function () { 1118 return that.meetPolygonLine(el1, el2, i, el1.board, alwaysintersect); 1119 }; 1120 } else { 1121 // path - path 1122 /** @ignore */ 1123 func = function () { 1124 return that.meetPathPath(el1, el2, i, el1.board); 1125 }; 1126 } 1127 1128 } else if (el1.elementClass === Const.OBJECT_CLASS_LINE && el2.elementClass === Const.OBJECT_CLASS_LINE) { 1129 // line - line, lines may also be segments. 1130 /** @ignore */ 1131 func = function () { 1132 var res, c, 1133 first1 = Type.evaluate(el1.visProp.straightfirst), 1134 last1 = Type.evaluate(el1.visProp.straightlast), 1135 first2 = Type.evaluate(el2.visProp.straightfirst), 1136 last2 = Type.evaluate(el2.visProp.straightlast); 1137 1138 /** 1139 * If one of the lines is a segment or ray and 1140 * the intersection point should disappear if outside 1141 * of the segment or ray we call 1142 * meetSegmentSegment 1143 */ 1144 if (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)) { 1145 res = that.meetSegmentSegment( 1146 el1.point1.coords.usrCoords, 1147 el1.point2.coords.usrCoords, 1148 el2.point1.coords.usrCoords, 1149 el2.point2.coords.usrCoords 1150 ); 1151 1152 if ((!first1 && res[1] < 0) || (!last1 && res[1] > 1) || 1153 (!first2 && res[2] < 0) || (!last2 && res[2] > 1)) { 1154 // Non-existent 1155 c = [0, NaN, NaN]; 1156 } else { 1157 c = res[0]; 1158 } 1159 1160 return (new Coords(Const.COORDS_BY_USER, c, el1.board)); 1161 } 1162 1163 return that.meet(el1.stdform, el2.stdform, i, el1.board); 1164 }; 1165 } else { 1166 // All other combinations of circles and lines, 1167 // Arc types are treated as circles. 1168 /** @ignore */ 1169 func = function () { 1170 var res = that.meet(el1.stdform, el2.stdform, i, el1.board), 1171 has = true, 1172 first, last, r, dx; 1173 1174 if (alwaysintersect) { 1175 return res; 1176 } 1177 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1178 first = Type.evaluate(el1.visProp.straightfirst); 1179 last = Type.evaluate(el1.visProp.straightlast); 1180 if (!first || !last) { 1181 r = that.affineRatio(el1.point1.coords, el1.point2.coords, res); 1182 if ( (!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps) ) { 1183 return (new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board)); 1184 } 1185 } 1186 } 1187 if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1188 first = Type.evaluate(el2.visProp.straightfirst); 1189 last = Type.evaluate(el2.visProp.straightlast); 1190 if (!first || !last) { 1191 r = that.affineRatio(el2.point1.coords, el2.point2.coords, res); 1192 if ( (!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps) ) { 1193 return (new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board)); 1194 } 1195 } 1196 } 1197 if (el1_isArcType) { 1198 has = that.coordsOnArc(el1, res); 1199 if (has && el2_isArcType) { 1200 has = that.coordsOnArc(el2, res); 1201 } 1202 if (!has) { 1203 return (new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board)); 1204 } 1205 } 1206 return res; 1207 }; 1208 } 1209 1210 return func; 1211 }, 1212 1213 /** 1214 * Returns true if the coordinates are on the arc element, 1215 * false otherwise. Usually, coords is an intersection 1216 * on the circle line. Now it is decided if coords are on the 1217 * circle restricted to the arc line. 1218 * @param {Arc} arc arc or sector element 1219 * @param {JXG.Coords} coords Coords object of an intersection 1220 * @returns {Boolean} 1221 * @private 1222 */ 1223 coordsOnArc: function(arc, coords) { 1224 var angle = this.rad(arc.radiuspoint, arc.center, coords.usrCoords.slice(1)), 1225 alpha = 0.0, 1226 beta = this.rad(arc.radiuspoint, arc.center, arc.anglepoint), 1227 ev_s = Type.evaluate(arc.visProp.selection); 1228 1229 if ((ev_s === 'minor' && beta > Math.PI) || 1230 (ev_s === 'major' && beta < Math.PI)) { 1231 alpha = beta; 1232 beta = 2 * Math.PI; 1233 } 1234 if (angle < alpha || angle > beta) { 1235 return false; 1236 } 1237 return true; 1238 }, 1239 1240 /** 1241 * Computes the intersection of a pair of lines, circles or both. 1242 * It uses the internal data array stdform of these elements. 1243 * @param {Array} el1 stdform of the first element (line or circle) 1244 * @param {Array} el2 stdform of the second element (line or circle) 1245 * @param {Number} i Index of the intersection point that should be returned. 1246 * @param board Reference to the board. 1247 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 1248 * Which point will be returned is determined by i. 1249 */ 1250 meet: function (el1, el2, i, board) { 1251 var result, 1252 eps = Mat.eps; 1253 1254 // line line 1255 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { 1256 result = this.meetLineLine(el1, el2, i, board); 1257 // circle line 1258 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { 1259 result = this.meetLineCircle(el2, el1, i, board); 1260 // line circle 1261 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { 1262 result = this.meetLineCircle(el1, el2, i, board); 1263 // circle circle 1264 } else { 1265 result = this.meetCircleCircle(el1, el2, i, board); 1266 } 1267 1268 return result; 1269 }, 1270 1271 /** 1272 * Intersection of the line with the board 1273 * @param {Array} line stdform of the line in screen coordinates 1274 * @param {JXG.Board} board reference to a board. 1275 * @param {Number} margin optional margin, to avoid the display of the small sides of lines. 1276 * @returns {Array} [intersection coords 1, intersection coords 2] 1277 */ 1278 meetLineBoard: function (line, board, margin) { 1279 // Intersect the line with the four borders of the board. 1280 var s = [], intersect1, intersect2, i, j; 1281 1282 if (!Type.exists(margin)) { 1283 margin = 0; 1284 } 1285 1286 // top 1287 s[0] = Mat.crossProduct(line, [margin, 0, 1]); 1288 // left 1289 s[1] = Mat.crossProduct(line, [margin, 1, 0]); 1290 // bottom 1291 s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]); 1292 // right 1293 s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]); 1294 1295 // Normalize the intersections 1296 for (i = 0; i < 4; i++) { 1297 if (Math.abs(s[i][0]) > Mat.eps) { 1298 for (j = 2; j > 0; j--) { 1299 s[i][j] /= s[i][0]; 1300 } 1301 s[i][0] = 1.0; 1302 } 1303 } 1304 1305 // line is parallel to "left", take "top" and "bottom" 1306 if (Math.abs(s[1][0]) < Mat.eps) { 1307 intersect1 = s[0]; // top 1308 intersect2 = s[2]; // bottom 1309 // line is parallel to "top", take "left" and "right" 1310 } else if (Math.abs(s[0][0]) < Mat.eps) { 1311 intersect1 = s[1]; // left 1312 intersect2 = s[3]; // right 1313 // left intersection out of board (above) 1314 } else if (s[1][2] < 0) { 1315 intersect1 = s[0]; // top 1316 1317 // right intersection out of board (below) 1318 if (s[3][2] > board.canvasHeight) { 1319 intersect2 = s[2]; // bottom 1320 } else { 1321 intersect2 = s[3]; // right 1322 } 1323 // left intersection out of board (below) 1324 } else if (s[1][2] > board.canvasHeight) { 1325 intersect1 = s[2]; // bottom 1326 1327 // right intersection out of board (above) 1328 if (s[3][2] < 0) { 1329 intersect2 = s[0]; // top 1330 } else { 1331 intersect2 = s[3]; // right 1332 } 1333 } else { 1334 intersect1 = s[1]; // left 1335 1336 // right intersection out of board (above) 1337 if (s[3][2] < 0) { 1338 intersect2 = s[0]; // top 1339 // right intersection out of board (below) 1340 } else if (s[3][2] > board.canvasHeight) { 1341 intersect2 = s[2]; // bottom 1342 } else { 1343 intersect2 = s[3]; // right 1344 } 1345 } 1346 1347 intersect1 = new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board); 1348 intersect2 = new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board); 1349 return [intersect1, intersect2]; 1350 }, 1351 1352 /** 1353 * Intersection of two lines. 1354 * @param {Array} l1 stdform of the first line 1355 * @param {Array} l2 stdform of the second line 1356 * @param {number} i unused 1357 * @param {JXG.Board} board Reference to the board. 1358 * @returns {JXG.Coords} Coordinates of the intersection point. 1359 */ 1360 meetLineLine: function (l1, l2, i, board) { 1361 /* 1362 var s = Mat.crossProduct(l1, l2); 1363 1364 if (Math.abs(s[0]) > Mat.eps) { 1365 s[1] /= s[0]; 1366 s[2] /= s[0]; 1367 s[0] = 1.0; 1368 } 1369 */ 1370 var s = isNaN(l1[5] + l2[5]) ? [0, 0, 0] : Mat.crossProduct(l1, l2); 1371 return new Coords(Const.COORDS_BY_USER, s, board); 1372 }, 1373 1374 /** 1375 * Intersection of line and circle. 1376 * @param {Array} lin stdform of the line 1377 * @param {Array} circ stdform of the circle 1378 * @param {number} i number of the returned intersection point. 1379 * i==0: use the positive square root, 1380 * i==1: use the negative square root. 1381 * @param {JXG.Board} board Reference to a board. 1382 * @returns {JXG.Coords} Coordinates of the intersection point 1383 */ 1384 meetLineCircle: function (lin, circ, i, board) { 1385 var a, b, c, d, n, 1386 A, B, C, k, t; 1387 1388 // Radius is zero, return center of circle 1389 if (circ[4] < Mat.eps) { 1390 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) { 1391 return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board); 1392 } 1393 1394 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board); 1395 } 1396 c = circ[0]; 1397 b = circ.slice(1, 3); 1398 a = circ[3]; 1399 d = lin[0]; 1400 n = lin.slice(1, 3); 1401 1402 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 1403 /* 1404 var nn = n[0]*n[0]+n[1]*n[1]; 1405 A = a*nn; 1406 B = (b[0]*n[1]-b[1]*n[0])*nn; 1407 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 1408 */ 1409 A = a; 1410 B = (b[0] * n[1] - b[1] * n[0]); 1411 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 1412 1413 k = B * B - 4 * A * C; 1414 if (k > -Mat.eps * Mat.eps) { 1415 k = Math.sqrt(Math.abs(k)); 1416 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)]; 1417 1418 return ((i === 0) ? 1419 new Coords(Const.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0], -t[0] * n[0] - d * n[1]], board) : 1420 new Coords(Const.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0], -t[1] * n[0] - d * n[1]], board) 1421 ); 1422 } 1423 1424 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1425 }, 1426 1427 /** 1428 * Intersection of two circles. 1429 * @param {Array} circ1 stdform of the first circle 1430 * @param {Array} circ2 stdform of the second circle 1431 * @param {number} i number of the returned intersection point. 1432 * i==0: use the positive square root, 1433 * i==1: use the negative square root. 1434 * @param {JXG.Board} board Reference to the board. 1435 * @returns {JXG.Coords} Coordinates of the intersection point 1436 */ 1437 meetCircleCircle: function (circ1, circ2, i, board) { 1438 var radicalAxis; 1439 1440 // Radius is zero, return center of circle, if on other circle 1441 if (circ1[4] < Mat.eps) { 1442 if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < Mat.eps) { 1443 return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board); 1444 } 1445 1446 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1447 } 1448 1449 // Radius is zero, return center of circle, if on other circle 1450 if (circ2[4] < Mat.eps) { 1451 if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < Mat.eps) { 1452 return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board); 1453 } 1454 1455 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1456 } 1457 1458 radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0], 1459 circ2[3] * circ1[1] - circ1[3] * circ2[1], 1460 circ2[3] * circ1[2] - circ1[3] * circ2[2], 1461 0, 1, Infinity, Infinity, Infinity]; 1462 radicalAxis = Mat.normalize(radicalAxis); 1463 1464 return this.meetLineCircle(radicalAxis, circ1, i, board); 1465 }, 1466 1467 /** 1468 * Compute an intersection of the curves c1 and c2. 1469 * We want to find values t1, t2 such that 1470 * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 1471 * 1472 * Methods: segment-wise intersections (default) or generalized Newton method. 1473 * @param {JXG.Curve} c1 Curve, Line or Circle 1474 * @param {JXG.Curve} c2 Curve, Line or Circle 1475 * @param {Number} nr the nr-th intersection point will be returned. 1476 * @param {Number} t2ini not longer used. 1477 * @param {JXG.Board} [board=c1.board] Reference to a board object. 1478 * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'. 1479 * @returns {JXG.Coords} intersection point 1480 */ 1481 meetCurveCurve: function (c1, c2, nr, t2ini, board, method) { 1482 var co; 1483 1484 if (Type.exists(method) && method === 'newton') { 1485 co = Numerics.generalizedNewton(c1, c2, nr, t2ini); 1486 } else { 1487 if (c1.bezierDegree === 3 || c2.bezierDegree === 3) { 1488 co = this.meetBezierCurveRedBlueSegments(c1, c2, nr); 1489 } else { 1490 co = this.meetCurveRedBlueSegments(c1, c2, nr); 1491 } 1492 } 1493 1494 return (new Coords(Const.COORDS_BY_USER, co, board)); 1495 }, 1496 1497 /** 1498 * Intersection of curve with line, 1499 * Order of input does not matter for el1 and el2. 1500 * From version 0.99.7 on this method calls 1501 * {@link JXG.Math.Geometry.meetCurveLineDiscrete}. 1502 * If higher precision is needed, {@link JXG.Math.Geometry.meetCurveLineContinuous} 1503 * has to be used. 1504 * 1505 * @param {JXG.Curve,JXG.Line} el1 Curve or Line 1506 * @param {JXG.Curve,JXG.Line} el2 Curve or Line 1507 * @param {Number} nr the nr-th intersection point will be returned. 1508 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1509 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection 1510 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1511 * the ideal point [0,1,0] is returned. 1512 */ 1513 meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) { 1514 var v = [0, NaN, NaN], cu, li; 1515 1516 if (!Type.exists(board)) { 1517 board = el1.board; 1518 } 1519 1520 if (el1.elementClass === Const.OBJECT_CLASS_CURVE) { 1521 cu = el1; 1522 li = el2; 1523 } else { 1524 cu = el2; 1525 li = el1; 1526 } 1527 1528 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect); 1529 1530 return v; 1531 }, 1532 1533 /** 1534 * Intersection of line and curve, continuous case. 1535 * Finds the nr-the intersection point 1536 * Uses {@link JXG.Math.Geometry.meetCurveLineDiscrete} as a first approximation. 1537 * A more exact solution is then found with {@link JXG.Math.Numerics.root}. 1538 * 1539 * @param {JXG.Curve} cu Curve 1540 * @param {JXG.Line} li Line 1541 * @param {Number} nr Will return the nr-th intersection point. 1542 * @param {JXG.Board} board 1543 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 1544 * line defined by the segment 1545 * @returns {JXG.Coords} Coords object containing the intersection. 1546 */ 1547 meetCurveLineContinuous: function (cu, li, nr, board, testSegment) { 1548 var t, func0, func1, v, x, y, z, 1549 eps = Mat.eps, 1550 epsLow = Mat.eps, 1551 steps, delta, tnew, i, 1552 tmin, fmin, ft; 1553 1554 v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment); 1555 x = v.usrCoords[1]; 1556 y = v.usrCoords[2]; 1557 1558 func0 = function (t) { 1559 var c1, c2; 1560 1561 if (t > cu.maxX() || t < cu.minX()) { 1562 return Infinity; 1563 } 1564 c1 = x - cu.X(t); 1565 c2 = y - cu.Y(t); 1566 return c1 * c1 + c2 * c2; 1567 }; 1568 1569 func1 = function (t) { 1570 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1571 return v * v; 1572 }; 1573 1574 // Find t 1575 steps = 50; 1576 delta = (cu.maxX() - cu.minX()) / steps; 1577 tnew = cu.minX(); 1578 1579 fmin = 0.0001; //eps; 1580 tmin = NaN; 1581 for (i = 0; i < steps; i++) { 1582 t = Numerics.root(func0, [Math.max(tnew, cu.minX()), Math.min(tnew + delta, cu.maxX())]); 1583 ft = Math.abs(func0(t)); 1584 if (ft <= fmin) { 1585 fmin = ft; 1586 tmin = t; 1587 if (fmin < eps) { 1588 break; 1589 } 1590 } 1591 1592 tnew += delta; 1593 } 1594 t = tmin; 1595 // Compute "exact" t 1596 t = Numerics.root(func1, [Math.max(t - delta, cu.minX()), Math.min(t + delta, cu.maxX())]); 1597 1598 ft = func1(t); 1599 // Is the point on the line? 1600 if (isNaN(ft) || Math.abs(ft) > epsLow) { 1601 z = 0.0; //NaN; 1602 } else { 1603 z = 1.0; 1604 } 1605 1606 return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1607 }, 1608 1609 /** 1610 * Intersection of line and curve, discrete case. 1611 * Segments are treated as lines. 1612 * Finding the nr-th intersection point should work for all nr. 1613 * @param {JXG.Curve} cu 1614 * @param {JXG.Line} li 1615 * @param {Number} nr 1616 * @param {JXG.Board} board 1617 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 1618 * line defined by the segment 1619 * 1620 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1621 * the ideal point [0,1,0] is returned. 1622 */ 1623 meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) { 1624 var i, j, 1625 p1, p2, p, q, 1626 lip1 = li.point1.coords.usrCoords, 1627 lip2 = li.point2.coords.usrCoords, 1628 d, res, 1629 cnt = 0, 1630 len = cu.numberPoints, 1631 ev_sf = Type.evaluate(li.visProp.straightfirst), 1632 ev_sl = Type.evaluate(li.visProp.straightlast); 1633 1634 // In case, no intersection will be found we will take this 1635 q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board); 1636 1637 if (lip1[0] === 0.0) { 1638 lip1 = [1, lip2[1] + li.stdform[2], lip2[2] - li.stdform[1]]; 1639 } else if (lip2[0] === 0.0) { 1640 lip2 = [1, lip1[1] + li.stdform[2], lip1[2] - li.stdform[1]]; 1641 } 1642 1643 p2 = cu.points[0].usrCoords; 1644 for (i = 1; i < len; i += cu.bezierDegree) { 1645 p1 = p2.slice(0); 1646 p2 = cu.points[i].usrCoords; 1647 d = this.distance(p1, p2); 1648 1649 // The defining points are not identical 1650 if (d > Mat.eps) { 1651 if (cu.bezierDegree === 3) { 1652 res = this.meetBeziersegmentBeziersegment([ 1653 cu.points[i - 1].usrCoords.slice(1), 1654 cu.points[i].usrCoords.slice(1), 1655 cu.points[i + 1].usrCoords.slice(1), 1656 cu.points[i + 2].usrCoords.slice(1) 1657 ], [ 1658 lip1.slice(1), 1659 lip2.slice(1) 1660 ], testSegment); 1661 } else { 1662 res = [this.meetSegmentSegment(p1, p2, lip1, lip2)]; 1663 } 1664 1665 for (j = 0; j < res.length; j++) { 1666 p = res[j]; 1667 if (0 <= p[1] && p[1] <= 1) { 1668 if (cnt === nr) { 1669 /** 1670 * If the intersection point is not part of the segment, 1671 * this intersection point is set to non-existent. 1672 * This prevents jumping behavior of the intersection points. 1673 * But it may be discussed if it is the desired behavior. 1674 */ 1675 if (testSegment && 1676 ((!ev_sf && p[2] < 0) || (!ev_sl && p[2] > 1))) { 1677 return q; // break; 1678 } 1679 1680 q = new Coords(Const.COORDS_BY_USER, p[0], board); 1681 return q; // break; 1682 } 1683 cnt += 1; 1684 } 1685 } 1686 } 1687 } 1688 1689 return q; 1690 }, 1691 1692 /** 1693 * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter). 1694 * We go through each segment of the red curve and search if there is an intersection with a segemnt of the blue curve. 1695 * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines 1696 * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on 1697 * the property bezierDegree of the curves. 1698 * <p> 1699 * This method works also for transformed curves, since only the already 1700 * transformed points are used. 1701 * 1702 * @param {JXG.Curve} red 1703 * @param {JXG.Curve} blue 1704 * @param {Number} nr 1705 */ 1706 meetCurveRedBlueSegments: function (red, blue, nr) { 1707 var i, j, 1708 red1, red2, blue1, blue2, m, 1709 minX, maxX, 1710 iFound = 0, 1711 lenBlue = blue.numberPoints, //points.length, 1712 lenRed = red.numberPoints; //points.length; 1713 1714 if (lenBlue <= 1 || lenRed <= 1) { 1715 return [0, NaN, NaN]; 1716 } 1717 1718 for (i = 1; i < lenRed; i++) { 1719 red1 = red.points[i - 1].usrCoords; 1720 red2 = red.points[i].usrCoords; 1721 minX = Math.min(red1[1], red2[1]); 1722 maxX = Math.max(red1[1], red2[1]); 1723 1724 blue2 = blue.points[0].usrCoords; 1725 for (j = 1; j < lenBlue; j++) { 1726 blue1 = blue2; 1727 blue2 = blue.points[j].usrCoords; 1728 1729 if (Math.min(blue1[1], blue2[1]) < maxX && Math.max(blue1[1], blue2[1]) > minX) { 1730 m = this.meetSegmentSegment(red1, red2, blue1, blue2); 1731 if (m[1] >= 0.0 && m[2] >= 0.0 && 1732 // The two segments meet in the interior or at the start points 1733 ((m[1] < 1.0 && m[2] < 1.0) || 1734 // One of the curve is intersected in the very last point 1735 (i === lenRed - 1 && m[1] === 1.0) || 1736 (j === lenBlue - 1 && m[2] === 1.0))) { 1737 if (iFound === nr) { 1738 return m[0]; 1739 } 1740 1741 iFound++; 1742 } 1743 } 1744 } 1745 } 1746 1747 return [0, NaN, NaN]; 1748 }, 1749 1750 /** 1751 * (Virtual) Intersection of two segments. 1752 * @param {Array} p1 First point of segment 1 using normalized homogeneous coordinates [1,x,y] 1753 * @param {Array} p2 Second point or direction of segment 1 using normalized homogeneous coordinates [1,x,y] or point at infinity [0,x,y], respectively 1754 * @param {Array} q1 First point of segment 2 using normalized homogeneous coordinates [1,x,y] 1755 * @param {Array} q2 Second point or direction of segment 2 using normalized homogeneous coordinates [1,x,y] or point at infinity [0,x,y], respectively 1756 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 1757 * of the intersection point. The second and third entry give the position of the intersection with respect 1758 * to the definiting parameters. For example, the second entry t is defined by: intersection point = p1 + t * deltaP, where 1759 * deltaP = (p2 - p1) when both parameters are coordinates, and deltaP = p2 if p2 is a point at infinity. 1760 * If the two segments are collinear, [[0,0,0], Infinity, Infinity] is returned. 1761 **/ 1762 meetSegmentSegment: function (p1, p2, q1, q2) { 1763 var t, u, i, d, 1764 li1 = Mat.crossProduct(p1, p2), 1765 li2 = Mat.crossProduct(q1, q2), 1766 c = Mat.crossProduct(li1, li2); 1767 1768 if (Math.abs(c[0]) < Mat.eps) { 1769 return [c, Infinity, Infinity]; 1770 } 1771 1772 // Normalize the intersection coordinates 1773 c[1] /= c[0]; 1774 c[2] /= c[0]; 1775 c[0] /= c[0]; 1776 1777 // Now compute in principle: 1778 // t = dist(c - p1) / dist(p2 - p1) and 1779 // u = dist(c - q1) / dist(q2 - q1) 1780 // However: the points q1, q2, p1, p2 might be ideal points - or in general - the 1781 // coordinates might be not normalized. 1782 // Note that the z-coordinates of p2 and q2 are used to determine whether it should be interpreted 1783 // as a segment coordinate or a direction. 1784 i = (Math.abs(p2[1] - p2[0] * p1[1]) < Mat.eps) ? 2 : 1; 1785 d = p1[i] / p1[0]; 1786 t = (c[i] - d) / ( (p2[0] !== 0) ? (p2[i] / p2[0] - d) : p2[i] ); 1787 1788 i = (Math.abs(q2[1] - q2[0] * q1[1]) < Mat.eps) ? 2 : 1; 1789 d = q1[i] / q1[0]; 1790 u = (c[i] - d) / ( (q2[0] !== 0) ? (q2[i] / q2[0] - d) : q2[i] ); 1791 1792 return [c, t, u]; 1793 }, 1794 1795 /** 1796 * Find the n-th intersection point of two pathes, usually given by polygons. Uses parts of the 1797 * Greiner-Hormann algorithm in JXG.Math.Clip. 1798 * 1799 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} path1 1800 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} path2 1801 * @param {Number} n 1802 * @param {JXG.Board} board 1803 * 1804 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1805 * the ideal point [0,0,0] is returned. 1806 * 1807 */ 1808 meetPathPath: function(path1, path2, nr, board) { 1809 var S, C, len, intersections; 1810 1811 S = JXG.Math.Clip._getPath(path1, board); 1812 len = S.length; 1813 if (len > 0 && this.distance(S[0].coords.usrCoords, S[len - 1].coords.usrCoords, 3) < Mat.eps) { 1814 S.pop(); 1815 } 1816 1817 C = JXG.Math.Clip._getPath(path2, board); 1818 len = C.length; 1819 if (len > 0 && this.distance(C[0].coords.usrCoords, C[len - 1].coords.usrCoords, 3) < Mat.eps * Mat.eps) { 1820 C.pop(); 1821 } 1822 1823 // Handle cases where at least one of the paths is empty 1824 if (nr < 0 || JXG.Math.Clip.isEmptyCase(S, C, 'intersection')) { 1825 return (new Coords(Const.COORDS_BY_USER, [0, 0, 0], board)); 1826 } 1827 1828 JXG.Math.Clip.makeDoublyLinkedList(S); 1829 JXG.Math.Clip.makeDoublyLinkedList(C); 1830 1831 intersections = JXG.Math.Clip.findIntersections(S, C, board)[0]; 1832 if (nr < intersections.length) { 1833 return intersections[nr].coords; 1834 } 1835 return (new Coords(Const.COORDS_BY_USER, [0, 0, 0], board)); 1836 }, 1837 1838 /** 1839 * Find the n-th intersection point between a polygon and a line. 1840 * @param {JXG.Polygon} path 1841 * @param {JXG.Line} line 1842 * @param {Number} nr 1843 * @param {JXG.Board} board 1844 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points of the line are tested for intersection. 1845 * 1846 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1847 * the ideal point [0,0,0] is returned. 1848 */ 1849 meetPolygonLine: function(path, line, nr, board, alwaysIntersect) { 1850 var i, res, border, 1851 crds = [0,0,0], 1852 len = path.borders.length, 1853 intersections = []; 1854 1855 for (i = 0; i < len; i++) { 1856 border = path.borders[i]; 1857 res = this.meetSegmentSegment( 1858 border.point1.coords.usrCoords, 1859 border.point2.coords.usrCoords, 1860 line.point1.coords.usrCoords, 1861 line.point2.coords.usrCoords); 1862 1863 if ( 1864 (!alwaysIntersect || (res[2] >= 0 && res[2] < 1)) && 1865 res[1] >= 0 && res[1] < 1) { 1866 intersections.push(res[0]); 1867 } 1868 } 1869 1870 if (nr >= 0 && nr < intersections.length) { 1871 crds = intersections[nr]; 1872 } 1873 return (new Coords(Const.COORDS_BY_USER, crds, board)); 1874 }, 1875 1876 /****************************************/ 1877 /**** BEZIER CURVE ALGORITHMS ****/ 1878 /****************************************/ 1879 1880 /** 1881 * Splits a Bezier curve segment defined by four points into 1882 * two Bezier curve segments. Dissection point is t=1/2. 1883 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1884 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1885 * @returns {Array} Array consisting of two coordinate arrays for Bezier curves. 1886 */ 1887 _bezierSplit: function (curve) { 1888 var p0, p1, p2, p00, p22, p000; 1889 1890 p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5]; 1891 p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5]; 1892 p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5]; 1893 1894 p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5]; 1895 p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5]; 1896 1897 p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5]; 1898 1899 return [[curve[0], p0, p00, p000], [p000, p22, p2, curve[3]]]; 1900 }, 1901 1902 /** 1903 * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment 1904 * from its control points. 1905 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1906 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1907 * @returns {Array} Bounding box [minX, maxY, maxX, minY] 1908 */ 1909 _bezierBbox: function (curve) { 1910 var bb = []; 1911 1912 if (curve.length === 4) { // bezierDegree == 3 1913 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX 1914 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY 1915 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX 1916 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY 1917 } else { // bezierDegree == 1 1918 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX 1919 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY 1920 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX 1921 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY 1922 } 1923 1924 return bb; 1925 }, 1926 1927 /** 1928 * Decide if two Bezier curve segments overlap by comparing their bounding boxes. 1929 * @param {Array} bb1 Bounding box of the first Bezier curve segment 1930 * @param {Array} bb2 Bounding box of the second Bezier curve segment 1931 * @returns {Boolean} true if the bounding boxes overlap, false otherwise. 1932 */ 1933 _bezierOverlap: function (bb1, bb2) { 1934 return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1]; 1935 }, 1936 1937 /** 1938 * Append list of intersection points to a list. 1939 * @private 1940 */ 1941 _bezierListConcat: function (L, Lnew, t1, t2) { 1942 var i, 1943 t2exists = Type.exists(t2), 1944 start = 0, 1945 len = Lnew.length, 1946 le = L.length; 1947 1948 if (le > 0 && len > 0 && 1949 ((L[le - 1][1] === 1 && Lnew[0][1] === 0) || 1950 (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0))) { 1951 start = 1; 1952 } 1953 1954 for (i = start; i < len; i++) { 1955 if (t2exists) { 1956 Lnew[i][2] *= 0.5; 1957 Lnew[i][2] += t2; 1958 } 1959 1960 Lnew[i][1] *= 0.5; 1961 Lnew[i][1] += t1; 1962 1963 L.push(Lnew[i]); 1964 } 1965 }, 1966 1967 /** 1968 * Find intersections of two Bezier curve segments by recursive subdivision. 1969 * Below maxlevel determine intersections by intersection line segments. 1970 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 1971 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1972 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 1973 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1974 * @param {Number} level Recursion level 1975 * @returns {Array} List of intersection points (up to nine). Each intersection point is an 1976 * array of length three (homogeneous coordinates) plus preimages. 1977 */ 1978 _bezierMeetSubdivision: function (red, blue, level) { 1979 var bbb, bbr, 1980 ar, b0, b1, r0, r1, m, 1981 p0, p1, q0, q1, 1982 L = [], 1983 maxLev = 5; // Maximum recursion level 1984 1985 bbr = this._bezierBbox(blue); 1986 bbb = this._bezierBbox(red); 1987 1988 if (!this._bezierOverlap(bbr, bbb)) { 1989 return []; 1990 } 1991 1992 if (level < maxLev) { 1993 ar = this._bezierSplit(red); 1994 r0 = ar[0]; 1995 r1 = ar[1]; 1996 1997 ar = this._bezierSplit(blue); 1998 b0 = ar[0]; 1999 b1 = ar[1]; 2000 2001 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b0, level + 1), 0.0, 0.0); 2002 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b1, level + 1), 0, 0.5); 2003 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b0, level + 1), 0.5, 0.0); 2004 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b1, level + 1), 0.5, 0.5); 2005 2006 return L; 2007 } 2008 2009 // Make homogeneous coordinates 2010 q0 = [1].concat(red[0]); 2011 q1 = [1].concat(red[3]); 2012 p0 = [1].concat(blue[0]); 2013 p1 = [1].concat(blue[3]); 2014 2015 m = this.meetSegmentSegment(q0, q1, p0, p1); 2016 2017 if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) { 2018 return [m]; 2019 } 2020 2021 return []; 2022 }, 2023 2024 /** 2025 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 2026 */ 2027 _bezierLineMeetSubdivision: function (red, blue, level, testSegment) { 2028 var bbb, bbr, 2029 ar, r0, r1, m, 2030 p0, p1, q0, q1, 2031 L = [], 2032 maxLev = 5; // Maximum recursion level 2033 2034 bbb = this._bezierBbox(blue); 2035 bbr = this._bezierBbox(red); 2036 2037 if (testSegment && !this._bezierOverlap(bbr, bbb)) { 2038 return []; 2039 } 2040 2041 if (level < maxLev) { 2042 ar = this._bezierSplit(red); 2043 r0 = ar[0]; 2044 r1 = ar[1]; 2045 2046 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r0, blue, level + 1), 0.0); 2047 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r1, blue, level + 1), 0.5); 2048 2049 return L; 2050 } 2051 2052 // Make homogeneous coordinates 2053 q0 = [1].concat(red[0]); 2054 q1 = [1].concat(red[3]); 2055 p0 = [1].concat(blue[0]); 2056 p1 = [1].concat(blue[1]); 2057 2058 m = this.meetSegmentSegment(q0, q1, p0, p1); 2059 2060 if (m[1] >= 0.0 && m[1] <= 1.0) { 2061 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) { 2062 return [m]; 2063 } 2064 } 2065 2066 return []; 2067 }, 2068 2069 /** 2070 * Find the nr-th intersection point of two Bezier curve segments. 2071 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 2072 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2073 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 2074 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2075 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 2076 * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus 2077 * preimages [x,y], t_1, t_2] of the two Bezier curve segments. 2078 * 2079 */ 2080 meetBeziersegmentBeziersegment: function (red, blue, testSegment) { 2081 var L, L2, i; 2082 2083 if (red.length === 4 && blue.length === 4) { 2084 L = this._bezierMeetSubdivision(red, blue, 0); 2085 } else { 2086 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment); 2087 } 2088 2089 L.sort(function (a, b) { 2090 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]); 2091 }); 2092 2093 L2 = []; 2094 for (i = 0; i < L.length; i++) { 2095 // Only push entries different from their predecessor 2096 if (i === 0 || (L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2])) { 2097 L2.push(L[i]); 2098 } 2099 } 2100 return L2; 2101 }, 2102 2103 /** 2104 * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3. 2105 * @param {JXG.Curve} red Curve with bezierDegree == 3 2106 * @param {JXG.Curve} blue Curve with bezierDegree == 3 2107 * @param {Number} nr The number of the intersection point which should be returned. 2108 * @returns {Array} The homogeneous coordinates of the nr-th intersection point. 2109 */ 2110 meetBezierCurveRedBlueSegments: function (red, blue, nr) { 2111 var p, i, j, k, po, 2112 redArr, blueArr, 2113 bbr, bbb, intersections, 2114 startRed = 0, 2115 startBlue = 0, 2116 lenBlue = blue.numberPoints, 2117 lenRed = red.numberPoints, 2118 L = []; 2119 2120 if (lenBlue < blue.bezierDegree + 1 || lenRed < red.bezierDegree + 1) { 2121 return [0, NaN, NaN]; 2122 } 2123 lenBlue -= blue.bezierDegree; 2124 lenRed -= red.bezierDegree; 2125 2126 // For sectors, we ignore the "legs" 2127 if (red.type === Const.OBJECT_TYPE_SECTOR) { 2128 startRed = 3; 2129 lenRed -= 3; 2130 } 2131 if (blue.type === Const.OBJECT_TYPE_SECTOR) { 2132 startBlue = 3; 2133 lenBlue -= 3; 2134 } 2135 2136 for (i = startRed; i < lenRed; i += red.bezierDegree) { 2137 p = red.points; 2138 redArr = [ 2139 p[i].usrCoords.slice(1), 2140 p[i + 1].usrCoords.slice(1) 2141 ]; 2142 if (red.bezierDegree === 3) { 2143 redArr[2] = p[i + 2].usrCoords.slice(1); 2144 redArr[3] = p[i + 3].usrCoords.slice(1); 2145 } 2146 2147 bbr = this._bezierBbox(redArr); 2148 2149 for (j = startBlue; j < lenBlue; j += blue.bezierDegree) { 2150 p = blue.points; 2151 blueArr = [ 2152 p[j].usrCoords.slice(1), 2153 p[j + 1].usrCoords.slice(1) 2154 ]; 2155 if (blue.bezierDegree === 3) { 2156 blueArr[2] = p[j + 2].usrCoords.slice(1); 2157 blueArr[3] = p[j + 3].usrCoords.slice(1); 2158 } 2159 2160 bbb = this._bezierBbox(blueArr); 2161 if (this._bezierOverlap(bbr, bbb)) { 2162 intersections = this.meetBeziersegmentBeziersegment(redArr, blueArr); 2163 if (intersections.length === 0) { 2164 continue; 2165 } 2166 for (k = 0; k < intersections.length; k++) { 2167 po = intersections[k]; 2168 if (po[1] < -Mat.eps || 2169 po[1] > 1 + Mat.eps || 2170 po[2] < -Mat.eps || 2171 po[2] > 1 + Mat.eps) { 2172 continue; 2173 } 2174 L.push(po); 2175 } 2176 if (L.length > nr) { 2177 return L[nr][0]; 2178 } 2179 } 2180 } 2181 } 2182 if (L.length > nr) { 2183 return L[nr][0]; 2184 } 2185 2186 return [0, NaN, NaN]; 2187 }, 2188 2189 bezierSegmentEval: function (t, curve) { 2190 var f, x, y, 2191 t1 = 1.0 - t; 2192 2193 x = 0; 2194 y = 0; 2195 2196 f = t1 * t1 * t1; 2197 x += f * curve[0][0]; 2198 y += f * curve[0][1]; 2199 2200 f = 3.0 * t * t1 * t1; 2201 x += f * curve[1][0]; 2202 y += f * curve[1][1]; 2203 2204 f = 3.0 * t * t * t1; 2205 x += f * curve[2][0]; 2206 y += f * curve[2][1]; 2207 2208 f = t * t * t; 2209 x += f * curve[3][0]; 2210 y += f * curve[3][1]; 2211 2212 return [1.0, x, y]; 2213 }, 2214 2215 /** 2216 * Generate the defining points of a 3rd degree bezier curve that approximates 2217 * a circle sector defined by three coordinate points A, B, C, each defined by an array of length three. 2218 * The coordinate arrays are given in homogeneous coordinates. 2219 * @param {Array} A First point 2220 * @param {Array} B Second point (intersection point) 2221 * @param {Array} C Third point 2222 * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve. 2223 * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1. 2224 */ 2225 bezierArc: function (A, B, C, withLegs, sgn) { 2226 var p1, p2, p3, p4, 2227 r, phi, beta, 2228 PI2 = Math.PI * 0.5, 2229 x = B[1], 2230 y = B[2], 2231 z = B[0], 2232 dataX = [], dataY = [], 2233 co, si, ax, ay, bx, by, k, v, d, matrix; 2234 2235 r = this.distance(B, A); 2236 2237 // x,y, z is intersection point. Normalize it. 2238 x /= z; 2239 y /= z; 2240 2241 phi = this.rad(A.slice(1), B.slice(1), C.slice(1)); 2242 if (sgn === -1) { 2243 phi = 2 * Math.PI - phi; 2244 } 2245 2246 p1 = A; 2247 p1[1] /= p1[0]; 2248 p1[2] /= p1[0]; 2249 p1[0] /= p1[0]; 2250 2251 p4 = p1.slice(0); 2252 2253 if (withLegs) { 2254 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]]; 2255 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]]; 2256 } else { 2257 dataX = [p1[1]]; 2258 dataY = [p1[2]]; 2259 } 2260 2261 while (phi > Mat.eps) { 2262 if (phi > PI2) { 2263 beta = PI2; 2264 phi -= PI2; 2265 } else { 2266 beta = phi; 2267 phi = 0; 2268 } 2269 2270 co = Math.cos(sgn * beta); 2271 si = Math.sin(sgn * beta); 2272 2273 matrix = [ 2274 [1, 0, 0], 2275 [x * (1 - co) + y * si, co, -si], 2276 [y * (1 - co) - x * si, si, co] 2277 ]; 2278 v = Mat.matVecMult(matrix, p1); 2279 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]]; 2280 2281 ax = p1[1] - x; 2282 ay = p1[2] - y; 2283 bx = p4[1] - x; 2284 by = p4[2] - y; 2285 2286 d = Math.sqrt((ax + bx) * (ax + bx) + (ay + by) * (ay + by)); 2287 2288 if (Math.abs(by - ay) > Mat.eps) { 2289 k = (ax + bx) * (r / d - 0.5) / (by - ay) * 8 / 3; 2290 } else { 2291 k = (ay + by) * (r / d - 0.5) / (ax - bx) * 8 / 3; 2292 } 2293 2294 p2 = [1, p1[1] - k * ay, p1[2] + k * ax]; 2295 p3 = [1, p4[1] + k * by, p4[2] - k * bx]; 2296 2297 dataX = dataX.concat([p2[1], p3[1], p4[1]]); 2298 dataY = dataY.concat([p2[2], p3[2], p4[2]]); 2299 p1 = p4.slice(0); 2300 } 2301 2302 if (withLegs) { 2303 dataX = dataX.concat([ p4[1] + 0.333 * (x - p4[1]), p4[1] + 0.666 * (x - p4[1]), x]); 2304 dataY = dataY.concat([ p4[2] + 0.333 * (y - p4[2]), p4[2] + 0.666 * (y - p4[2]), y]); 2305 } 2306 2307 return [dataX, dataY]; 2308 }, 2309 2310 /****************************************/ 2311 /**** PROJECTIONS ****/ 2312 /****************************************/ 2313 2314 /** 2315 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 2316 * nearest one of the two intersection points of the line through the given point and the circles 2317 * center. 2318 * @param {JXG.Point,JXG.Coords} point Point to project or coords object to project. 2319 * @param {JXG.Circle} circle Circle on that the point is projected. 2320 * @param {JXG.Board} [board=point.board] Reference to the board 2321 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2322 */ 2323 projectPointToCircle: function (point, circle, board) { 2324 var dist, P, x, y, factor, 2325 M = circle.center.coords.usrCoords; 2326 2327 if (!Type.exists(board)) { 2328 board = point.board; 2329 } 2330 2331 // gave us a point 2332 if (Type.isPoint(point)) { 2333 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords); 2334 P = point.coords.usrCoords; 2335 // gave us coords 2336 } else { 2337 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords); 2338 P = point.usrCoords; 2339 } 2340 2341 if (Math.abs(dist) < Mat.eps) { 2342 dist = Mat.eps; 2343 } 2344 2345 factor = circle.Radius() / dist; 2346 x = M[1] + factor * (P[1] - M[1]); 2347 y = M[2] + factor * (P[2] - M[2]); 2348 2349 return new Coords(Const.COORDS_BY_USER, [x, y], board); 2350 }, 2351 2352 /** 2353 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 2354 * intersection point of the given line and its perpendicular through the given point. 2355 * @param {JXG.Point|JXG.Coords} point Point to project. 2356 * @param {JXG.Line} line Line on that the point is projected. 2357 * @param {JXG.Board} [board=point.board|board=line.board] Reference to a board. 2358 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 2359 */ 2360 projectPointToLine: function (point, line, board) { 2361 var v = [0, line.stdform[1], line.stdform[2]], 2362 coords; 2363 2364 if (!Type.exists(board)) { 2365 if (Type.exists(point.coords)) { 2366 board = point.board; 2367 } else { 2368 board = line.board; 2369 } 2370 } 2371 2372 if (Type.exists(point.coords)) { 2373 coords = point.coords.usrCoords; 2374 } else { 2375 coords = point.usrCoords; 2376 } 2377 2378 v = Mat.crossProduct(v, coords); 2379 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(v, line.stdform), board); 2380 }, 2381 2382 /** 2383 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 2384 * segment defined by two coordinate arrays. 2385 * @param {Array} p Point to project. 2386 * @param {Array} q1 Start point of the line segment on that the point is projected. 2387 * @param {Array} q2 End point of the line segment on that the point is projected. 2388 * @returns {Array} The coordinates of the projection of the given point on the given segment 2389 * and the factor that determines the projected point as a convex combination of the 2390 * two endpoints q1 and q2 of the segment. 2391 */ 2392 projectCoordsToSegment: function (p, q1, q2) { 2393 var t, denom, 2394 s = [q2[1] - q1[1], q2[2] - q1[2]], 2395 v = [p[1] - q1[1], p[2] - q1[2]]; 2396 2397 /** 2398 * If the segment has length 0, i.e. is a point, 2399 * the projection is equal to that point. 2400 */ 2401 if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) { 2402 return [q1, 0]; 2403 } 2404 2405 t = Mat.innerProduct(v, s); 2406 denom = Mat.innerProduct(s, s); 2407 t /= denom; 2408 2409 return [ [1, t * s[0] + q1[1], t * s[1] + q1[2]], t]; 2410 }, 2411 2412 /** 2413 * Finds the coordinates of the closest point on a Bezier segment of a 2414 * {@link JXG.Curve} to a given coordinate array. 2415 * @param {Array} pos Point to project in homogeneous coordinates. 2416 * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3. 2417 * @param {Number} start Number of the Bezier segment of the curve. 2418 * @returns {Array} The coordinates of the projection of the given point 2419 * on the given Bezier segment and the preimage of the curve which 2420 * determines the closest point. 2421 */ 2422 projectCoordsToBeziersegment: function (pos, curve, start) { 2423 var t0, 2424 /** @ignore */ 2425 minfunc = function (t) { 2426 var z = [1, curve.X(start + t), curve.Y(start + t)]; 2427 2428 z[1] -= pos[1]; 2429 z[2] -= pos[2]; 2430 2431 return z[1] * z[1] + z[2] * z[2]; 2432 }; 2433 2434 t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]); 2435 2436 return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0]; 2437 }, 2438 2439 /** 2440 * Calculates the coordinates of the projection of a given point on a given curve. 2441 * Uses {@link JXG.Math.Geometry.projectCoordsToCurve}. 2442 * 2443 * @param {JXG.Point} point Point to project. 2444 * @param {JXG.Curve} curve Curve on that the point is projected. 2445 * @param {JXG.Board} [board=point.board] Reference to a board. 2446 * @see #projectCoordsToCurve 2447 * @returns {Array} [JXG.Coords, position] The coordinates of the projection of the given 2448 * point on the given graph and the relative position on the curve (real number). 2449 */ 2450 projectPointToCurve: function (point, curve, board) { 2451 if (!Type.exists(board)) { 2452 board = point.board; 2453 } 2454 2455 var x = point.X(), 2456 y = point.Y(), 2457 t = point.position || 0.0, 2458 result = this.projectCoordsToCurve(x, y, t, curve, board); 2459 2460 // point.position = result[1]; 2461 2462 return result; 2463 }, 2464 2465 /** 2466 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 2467 * function graphs this is the 2468 * intersection point of the curve and the parallel to y-axis through the given point. 2469 * @param {Number} x coordinate to project. 2470 * @param {Number} y coordinate to project. 2471 * @param {Number} t start value for newtons method 2472 * @param {JXG.Curve} curve Curve on that the point is projected. 2473 * @param {JXG.Board} [board=curve.board] Reference to a board. 2474 * @see #projectPointToCurve 2475 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given curve and 2476 * the position on the curve. 2477 */ 2478 projectCoordsToCurve: function (x, y, t, curve, board) { 2479 var newCoords, newCoordsObj, i, j, 2480 mindist, dist, lbda, v, coords, d, 2481 p1, p2, res, 2482 minfunc, t_new, f_new, f_old, delta, steps, 2483 minX, maxX, 2484 infty = Number.POSITIVE_INFINITY; 2485 2486 if (!Type.exists(board)) { 2487 board = curve.board; 2488 } 2489 2490 2491 if (Type.evaluate(curve.visProp.curvetype) === 'plot') { 2492 t = 0; 2493 mindist = infty; 2494 if (curve.numberPoints === 0) { 2495 newCoords = [0, 1, 1]; 2496 } else { 2497 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 2498 } 2499 2500 if (curve.numberPoints > 1) { 2501 v = [1, x, y]; 2502 if (curve.bezierDegree === 3) { 2503 j = 0; 2504 } else { 2505 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 2506 } 2507 for (i = 0; i < curve.numberPoints - 1; i++) { 2508 if (curve.bezierDegree === 3) { 2509 res = this.projectCoordsToBeziersegment(v, curve, j); 2510 } else { 2511 p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)]; 2512 res = this.projectCoordsToSegment(v, p1, p2); 2513 } 2514 lbda = res[1]; 2515 coords = res[0]; 2516 2517 if (0.0 <= lbda && lbda <= 1.0) { 2518 dist = this.distance(coords, v); 2519 d = i + lbda; 2520 } else if (lbda < 0.0) { 2521 coords = p1; 2522 dist = this.distance(p1, v); 2523 d = i; 2524 } else if (lbda > 1.0 && i === curve.numberPoints - 2) { 2525 coords = p2; 2526 dist = this.distance(coords, v); 2527 d = curve.numberPoints - 1; 2528 } 2529 2530 if (dist < mindist) { 2531 mindist = dist; 2532 t = d; 2533 newCoords = coords; 2534 } 2535 2536 if (curve.bezierDegree === 3) { 2537 j++; 2538 i += 2; 2539 } else { 2540 p1 = p2; 2541 } 2542 } 2543 } 2544 2545 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board); 2546 } else { // 'parameter', 'polar', 'functiongraph' 2547 /** @ignore */ 2548 minfunc = function (t) { 2549 var dx, dy; 2550 if (t < curve.minX() || t > curve.maxX()) { 2551 return Infinity; 2552 } 2553 dx = x - curve.X(t); 2554 dy = y - curve.Y(t); 2555 return dx * dx + dy * dy; 2556 }; 2557 2558 f_old = minfunc(t); 2559 steps = 50; 2560 minX = curve.minX(); 2561 maxX = curve.maxX(); 2562 2563 delta = (maxX - minX) / steps; 2564 t_new = minX; 2565 2566 for (i = 0; i < steps; i++) { 2567 f_new = minfunc(t_new); 2568 2569 if (f_new < f_old || f_old === Infinity) { 2570 t = t_new; 2571 f_old = f_new; 2572 } 2573 2574 t_new += delta; 2575 } 2576 2577 //t = Numerics.root(Numerics.D(minfunc), t); 2578 t = Numerics.fminbr(minfunc, [Math.max(t - delta, minX), Math.min(t + delta, maxX)]); 2579 2580 // Distinction between closed and open curves is not necessary. 2581 // If closed, the cyclic projection shift will work anyhow 2582 // if (Math.abs(curve.X(minX) - curve.X(maxX)) < Mat.eps && 2583 // Math.abs(curve.Y(minX) - curve.Y(maxX)) < Mat.eps) { 2584 // // Cyclically 2585 // if (t < minX) { 2586 // t = maxX + t - minX; 2587 // } 2588 // if (t > maxX) { 2589 // t = minX + t - maxX; 2590 // } 2591 // } else { 2592 t = (t < minX) ? minX : t; 2593 t = (t > maxX) ? maxX : t; 2594 // } 2595 2596 newCoordsObj = new Coords(Const.COORDS_BY_USER, [curve.X(t), curve.Y(t)], board); 2597 } 2598 2599 return [curve.updateTransform(newCoordsObj), t]; 2600 }, 2601 2602 /** 2603 * Calculates the coordinates of the closest orthogonal projection of a given coordinate array onto the 2604 * border of a polygon. 2605 * @param {Array} p Point to project. 2606 * @param {JXG.Polygon} pol Polygon element 2607 * @returns {Array} The coordinates of the closest projection of the given point to the border of the polygon. 2608 */ 2609 projectCoordsToPolygon: function (p, pol) { 2610 var i, 2611 len = pol.vertices.length, 2612 d_best = Infinity, 2613 d, 2614 projection, proj, 2615 bestprojection; 2616 2617 for (i = 0; i < len - 1; i++) { 2618 projection = JXG.Math.Geometry.projectCoordsToSegment( 2619 p, 2620 pol.vertices[i].coords.usrCoords, 2621 pol.vertices[i + 1].coords.usrCoords 2622 ); 2623 2624 if (0 <= projection[1] && projection[1] <= 1) { 2625 d = JXG.Math.Geometry.distance(projection[0], p, 3); 2626 proj = projection[0]; 2627 } else if (projection[1] < 0) { 2628 d = JXG.Math.Geometry.distance(pol.vertices[i].coords.usrCoords, p, 3); 2629 proj = pol.vertices[i].coords.usrCoords; 2630 } else { 2631 d = JXG.Math.Geometry.distance(pol.vertices[i + 1].coords.usrCoords, p, 3); 2632 proj = pol.vertices[i + 1].coords.usrCoords; 2633 } 2634 if (d < d_best) { 2635 bestprojection = proj.slice(0); 2636 d_best = d; 2637 } 2638 } 2639 return bestprojection; 2640 }, 2641 2642 /** 2643 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 2644 * one or more curves of curveType 'plot'. Uses {@link JXG.Math.Geometry.projectPointToCurve}. 2645 * @param {JXG.Point} point Point to project. 2646 * @param {JXG.Turtle} turtle on that the point is projected. 2647 * @param {JXG.Board} [board=point.board] Reference to a board. 2648 * @returns {Array} [JXG.Coords, position] Array containing the coordinates of the projection of the given point on the turtle and 2649 * the position on the turtle. 2650 */ 2651 projectPointToTurtle: function (point, turtle, board) { 2652 var newCoords, t, x, y, i, dist, el, minEl, 2653 res, newPos, 2654 np = 0, 2655 npmin = 0, 2656 mindist = Number.POSITIVE_INFINITY, 2657 len = turtle.objects.length; 2658 2659 if (!Type.exists(board)) { 2660 board = point.board; 2661 } 2662 2663 // run through all curves of this turtle 2664 for (i = 0; i < len; i++) { 2665 el = turtle.objects[i]; 2666 2667 if (el.elementClass === Const.OBJECT_CLASS_CURVE) { 2668 res = this.projectPointToCurve(point, el); 2669 newCoords = res[0]; 2670 newPos = res[1]; 2671 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 2672 2673 if (dist < mindist) { 2674 x = newCoords.usrCoords[1]; 2675 y = newCoords.usrCoords[2]; 2676 t = newPos; 2677 mindist = dist; 2678 minEl = el; 2679 npmin = np; 2680 } 2681 np += el.numberPoints; 2682 } 2683 } 2684 2685 newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board); 2686 // point.position = t + npmin; 2687 // return minEl.updateTransform(newCoords); 2688 return [minEl.updateTransform(newCoords), t + npmin]; 2689 }, 2690 2691 /** 2692 * Trivial projection of a point to another point. 2693 * @param {JXG.Point} point Point to project (not used). 2694 * @param {JXG.Point} dest Point on that the point is projected. 2695 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2696 */ 2697 projectPointToPoint: function (point, dest) { 2698 return dest.coords; 2699 }, 2700 2701 /** 2702 * 2703 * @param {JXG.Point|JXG.Coords} point 2704 * @param {JXG.Board} [board] 2705 */ 2706 projectPointToBoard: function (point, board) { 2707 var i, l, c, 2708 brd = board || point.board, 2709 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx 2710 config = [ 2711 // left 2712 [1, 1, 0, 0, 3, 0, 1], 2713 // top 2714 [-1, 2, 1, 0, 1, 2, 1], 2715 // right 2716 [-1, 1, 2, 2, 1, 2, 3], 2717 // bottom 2718 [1, 2, 3, 0, 3, 2, 3] 2719 ], 2720 coords = point.coords || point, 2721 bbox = brd.getBoundingBox(); 2722 2723 for (i = 0; i < 4; i++) { 2724 c = config[i]; 2725 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) { 2726 // define border 2727 l = Mat.crossProduct([1, bbox[c[3]], bbox[c[4]]], [1, bbox[c[5]], bbox[c[6]]]); 2728 l[3] = 0; 2729 l = Mat.normalize(l); 2730 2731 // project point 2732 coords = this.projectPointToLine({coords: coords}, {stdform: l}, brd); 2733 } 2734 } 2735 2736 return coords; 2737 }, 2738 2739 /** 2740 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 2741 * coordinates. For lines this can be line.stdform. 2742 * @param {Array} point Homogeneous coordinates of a point. 2743 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 2744 * @returns {Number} Distance of the point to the line. 2745 */ 2746 distPointLine: function (point, line) { 2747 var a = line[1], 2748 b = line[2], 2749 c = line[0], 2750 nom; 2751 2752 if (Math.abs(a) + Math.abs(b) < Mat.eps) { 2753 return Number.POSITIVE_INFINITY; 2754 } 2755 2756 nom = a * point[1] + b * point[2] + c; 2757 a *= a; 2758 b *= b; 2759 2760 return Math.abs(nom) / Math.sqrt(a + b); 2761 }, 2762 2763 /** 2764 * Helper function to create curve which displays a Reuleaux polygons. 2765 * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically, 2766 * these point list is the array vertices of a regular polygon. 2767 * @param {Number} nr Number of vertices 2768 * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values 2769 * for the start and the end of the paramtric curve. array may be used as parent array of a 2770 * {@link JXG.Curve}. 2771 * 2772 * @example 2773 * var A = brd.create('point',[-2,-2]); 2774 * var B = brd.create('point',[0,1]); 2775 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2776 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2777 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2778 * 2779 * </pre><div class="jxgbox" id="JXG2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div> 2780 * <script type="text/javascript"> 2781 * var brd = JXG.JSXGraph.initBoard('JXG2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false}); 2782 * var A = brd.create('point',[-2,-2]); 2783 * var B = brd.create('point',[0,1]); 2784 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2785 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2786 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2787 * </script><pre> 2788 */ 2789 reuleauxPolygon: function (points, nr) { 2790 var beta, 2791 pi2 = Math.PI * 2, 2792 pi2_n = pi2 / nr, 2793 diag = (nr - 1) / 2, 2794 d = 0, 2795 makeFct = function (which, trig) { 2796 return function (t, suspendUpdate) { 2797 var t1 = (t % pi2 + pi2) % pi2, 2798 j = Math.floor(t1 / pi2_n) % nr; 2799 2800 if (!suspendUpdate) { 2801 d = points[0].Dist(points[diag]); 2802 beta = Mat.Geometry.rad([points[0].X() + 1, points[0].Y()], points[0], points[diag % nr]); 2803 } 2804 2805 if (isNaN(j)) { 2806 return j; 2807 } 2808 2809 t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta; 2810 2811 return points[j][which]() + d * Math[trig](t1); 2812 }; 2813 }; 2814 2815 return [makeFct('X', 'cos'), makeFct('Y', 'sin'), 0, pi2]; 2816 }, 2817 2818 2819 meet3Planes: function (n1, d1, n2, d2, n3, d3) { 2820 var p = [0, 0, 0], 2821 n31, n12, n23, denom, 2822 i; 2823 2824 n31 = Mat.crossProduct(n3, n1); 2825 n12 = Mat.crossProduct(n1, n2); 2826 n23 = Mat.crossProduct(n2, n3); 2827 denom = Mat.innerProduct(n1, n23, 3); 2828 for (i = 0; i < 3; i++) { 2829 p[i] = (d1 * n23[i] + d2 * n31[i] + d3 * n12[i]) / denom; 2830 } 2831 return p; 2832 }, 2833 2834 2835 meetPlanePlane: function (v11, v12, v21, v22) { 2836 var i, no1, no2, 2837 v = [0, 0, 0], 2838 w = [0, 0, 0]; 2839 2840 for (i = 0; i < 3; i++) { 2841 v[i] = Type.evaluate(v11[i]); 2842 w[i] = Type.evaluate(v12[i]); 2843 } 2844 no1 = Mat.crossProduct(v, w); 2845 2846 for (i = 0; i < 3; i++) { 2847 v[i] = Type.evaluate(v21[i]); 2848 w[i] = Type.evaluate(v22[i]); 2849 } 2850 no2 = Mat.crossProduct(v, w); 2851 2852 return Mat.crossProduct(no1, no2); 2853 }, 2854 2855 project3DTo3DPlane: function (point, normal, foot) { 2856 // TODO: homogeneous 3D coordinates 2857 var sol = [0, 0, 0], 2858 le, d1, d2, lbda; 2859 2860 foot = foot || [0, 0, 0]; 2861 2862 le = Mat.norm(normal); 2863 d1 = Mat.innerProduct(point, normal, 3); 2864 d2 = Mat.innerProduct(foot, normal, 3); 2865 // (point - lbda * normal / le) * normal / le == foot * normal / le 2866 // => (point * normal - foot * normal) == lbda * le 2867 lbda = (d1 - d2) / le; 2868 sol = Mat.axpy(-lbda, normal, point); 2869 2870 return sol; 2871 }, 2872 2873 getPlaneBounds: function (v1, v2, q, s, e) { 2874 var s1, s2, e1, e2, mat, rhs, sol; 2875 2876 if (v1[2] + v2[0] !== 0) { 2877 mat = [ 2878 [v1[0], v2[0]], 2879 [v1[1], v2[1]] 2880 ]; 2881 rhs = [s - q[0], s - q[1]]; 2882 2883 sol = Numerics.Gauss(mat, rhs); 2884 s1 = sol[0]; 2885 s2 = sol[1]; 2886 2887 rhs = [e - q[0], e - q[1]]; 2888 sol = Numerics.Gauss(mat, rhs); 2889 e1 = sol[0]; 2890 e2 = sol[1]; 2891 return [s1, e1, s2, e2]; 2892 } 2893 return null; 2894 }, 2895 2896 }); 2897 2898 return Mat.Geometry; 2899 }); 2900