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.elementClass === Const.OBJECT_CLASS_LINE && el2.elementClass === Const.OBJECT_CLASS_LINE) { 1105 // line - line, lines may also be segments. 1106 /** @ignore */ 1107 func = function () { 1108 var res, c, 1109 first1 = Type.evaluate(el1.visProp.straightfirst), 1110 last1 = Type.evaluate(el1.visProp.straightlast), 1111 first2 = Type.evaluate(el2.visProp.straightfirst), 1112 last2 = Type.evaluate(el2.visProp.straightlast); 1113 1114 /** 1115 * If one of the lines is a segment or ray and 1116 * the intersection point should disappear if outside 1117 * of the segment or ray we call 1118 * meetSegmentSegment 1119 */ 1120 if (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)) { 1121 res = that.meetSegmentSegment( 1122 el1.point1.coords.usrCoords, 1123 el1.point2.coords.usrCoords, 1124 el2.point1.coords.usrCoords, 1125 el2.point2.coords.usrCoords 1126 ); 1127 1128 if ((!first1 && res[1] < 0) || (!last1 && res[1] > 1) || 1129 (!first2 && res[2] < 0) || (!last2 && res[2] > 1)) { 1130 // Non-existent 1131 c = [0, NaN, NaN]; 1132 } else { 1133 c = res[0]; 1134 } 1135 1136 return (new Coords(Const.COORDS_BY_USER, c, el1.board)); 1137 } 1138 1139 return that.meet(el1.stdform, el2.stdform, i, el1.board); 1140 }; 1141 } else { 1142 // All other combinations of circles and lines, 1143 // Arc types are treated as circles. 1144 /** @ignore */ 1145 func = function () { 1146 var res = that.meet(el1.stdform, el2.stdform, i, el1.board), 1147 has = true, 1148 first, last, r, dx; 1149 1150 if (alwaysintersect) { 1151 return res; 1152 } 1153 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1154 first = Type.evaluate(el1.visProp.straightfirst); 1155 last = Type.evaluate(el1.visProp.straightlast); 1156 if (!first || !last) { 1157 r = that.affineRatio(el1.point1.coords, el1.point2.coords, res); 1158 if ( (!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps) ) { 1159 return (new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board)); 1160 } 1161 } 1162 } 1163 if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1164 first = Type.evaluate(el2.visProp.straightfirst); 1165 last = Type.evaluate(el2.visProp.straightlast); 1166 if (!first || !last) { 1167 r = that.affineRatio(el2.point1.coords, el2.point2.coords, res); 1168 if ( (!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps) ) { 1169 return (new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board)); 1170 } 1171 } 1172 } 1173 if (el1_isArcType) { 1174 has = that.coordsOnArc(el1, res); 1175 if (has && el2_isArcType) { 1176 has = that.coordsOnArc(el2, res); 1177 } 1178 if (!has) { 1179 return (new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board)); 1180 } 1181 } 1182 return res; 1183 }; 1184 } 1185 1186 return func; 1187 }, 1188 1189 /** 1190 * Returns true if the coordinates are on the arc element, 1191 * false otherwise. Usually, coords is an intersection 1192 * on the circle line. Now it is decided if coords are on the 1193 * circle restricted to the arc line. 1194 * @param {Arc} arc arc or sector element 1195 * @param {JXG.Coords} coords Coords object of an intersection 1196 * @returns {Boolean} 1197 * @private 1198 */ 1199 coordsOnArc: function(arc, coords) { 1200 var angle = this.rad(arc.radiuspoint, arc.center, coords.usrCoords.slice(1)), 1201 alpha = 0.0, 1202 beta = this.rad(arc.radiuspoint, arc.center, arc.anglepoint), 1203 ev_s = Type.evaluate(arc.visProp.selection); 1204 1205 if ((ev_s === 'minor' && beta > Math.PI) || 1206 (ev_s === 'major' && beta < Math.PI)) { 1207 alpha = beta; 1208 beta = 2 * Math.PI; 1209 } 1210 if (angle < alpha || angle > beta) { 1211 return false; 1212 } 1213 return true; 1214 }, 1215 1216 /** 1217 * Computes the intersection of a pair of lines, circles or both. 1218 * It uses the internal data array stdform of these elements. 1219 * @param {Array} el1 stdform of the first element (line or circle) 1220 * @param {Array} el2 stdform of the second element (line or circle) 1221 * @param {Number} i Index of the intersection point that should be returned. 1222 * @param board Reference to the board. 1223 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 1224 * Which point will be returned is determined by i. 1225 */ 1226 meet: function (el1, el2, i, board) { 1227 var result, 1228 eps = Mat.eps; 1229 1230 // line line 1231 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { 1232 result = this.meetLineLine(el1, el2, i, board); 1233 // circle line 1234 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { 1235 result = this.meetLineCircle(el2, el1, i, board); 1236 // line circle 1237 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { 1238 result = this.meetLineCircle(el1, el2, i, board); 1239 // circle circle 1240 } else { 1241 result = this.meetCircleCircle(el1, el2, i, board); 1242 } 1243 1244 return result; 1245 }, 1246 1247 /** 1248 * Intersection of the line with the board 1249 * @param {Array} line stdform of the line in screen coordinates 1250 * @param {JXG.Board} board reference to a board. 1251 * @param {Number} margin optional margin, to avoid the display of the small sides of lines. 1252 * @returns {Array} [intersection coords 1, intersection coords 2] 1253 */ 1254 meetLineBoard: function (line, board, margin) { 1255 // Intersect the line with the four borders of the board. 1256 var s = [], intersect1, intersect2, i, j; 1257 1258 if (!Type.exists(margin)) { 1259 margin = 0; 1260 } 1261 1262 // top 1263 s[0] = Mat.crossProduct(line, [margin, 0, 1]); 1264 // left 1265 s[1] = Mat.crossProduct(line, [margin, 1, 0]); 1266 // bottom 1267 s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]); 1268 // right 1269 s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]); 1270 1271 // Normalize the intersections 1272 for (i = 0; i < 4; i++) { 1273 if (Math.abs(s[i][0]) > Mat.eps) { 1274 for (j = 2; j > 0; j--) { 1275 s[i][j] /= s[i][0]; 1276 } 1277 s[i][0] = 1.0; 1278 } 1279 } 1280 1281 // line is parallel to "left", take "top" and "bottom" 1282 if (Math.abs(s[1][0]) < Mat.eps) { 1283 intersect1 = s[0]; // top 1284 intersect2 = s[2]; // bottom 1285 // line is parallel to "top", take "left" and "right" 1286 } else if (Math.abs(s[0][0]) < Mat.eps) { 1287 intersect1 = s[1]; // left 1288 intersect2 = s[3]; // right 1289 // left intersection out of board (above) 1290 } else if (s[1][2] < 0) { 1291 intersect1 = s[0]; // top 1292 1293 // right intersection out of board (below) 1294 if (s[3][2] > board.canvasHeight) { 1295 intersect2 = s[2]; // bottom 1296 } else { 1297 intersect2 = s[3]; // right 1298 } 1299 // left intersection out of board (below) 1300 } else if (s[1][2] > board.canvasHeight) { 1301 intersect1 = s[2]; // bottom 1302 1303 // right intersection out of board (above) 1304 if (s[3][2] < 0) { 1305 intersect2 = s[0]; // top 1306 } else { 1307 intersect2 = s[3]; // right 1308 } 1309 } else { 1310 intersect1 = s[1]; // left 1311 1312 // right intersection out of board (above) 1313 if (s[3][2] < 0) { 1314 intersect2 = s[0]; // top 1315 // right intersection out of board (below) 1316 } else if (s[3][2] > board.canvasHeight) { 1317 intersect2 = s[2]; // bottom 1318 } else { 1319 intersect2 = s[3]; // right 1320 } 1321 } 1322 1323 intersect1 = new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board); 1324 intersect2 = new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board); 1325 return [intersect1, intersect2]; 1326 }, 1327 1328 /** 1329 * Intersection of two lines. 1330 * @param {Array} l1 stdform of the first line 1331 * @param {Array} l2 stdform of the second line 1332 * @param {number} i unused 1333 * @param {JXG.Board} board Reference to the board. 1334 * @returns {JXG.Coords} Coordinates of the intersection point. 1335 */ 1336 meetLineLine: function (l1, l2, i, board) { 1337 /* 1338 var s = Mat.crossProduct(l1, l2); 1339 1340 if (Math.abs(s[0]) > Mat.eps) { 1341 s[1] /= s[0]; 1342 s[2] /= s[0]; 1343 s[0] = 1.0; 1344 } 1345 */ 1346 var s = isNaN(l1[5] + l2[5]) ? [0, 0, 0] : Mat.crossProduct(l1, l2); 1347 return new Coords(Const.COORDS_BY_USER, s, board); 1348 }, 1349 1350 /** 1351 * Intersection of line and circle. 1352 * @param {Array} lin stdform of the line 1353 * @param {Array} circ stdform of the circle 1354 * @param {number} i number of the returned intersection point. 1355 * i==0: use the positive square root, 1356 * i==1: use the negative square root. 1357 * @param {JXG.Board} board Reference to a board. 1358 * @returns {JXG.Coords} Coordinates of the intersection point 1359 */ 1360 meetLineCircle: function (lin, circ, i, board) { 1361 var a, b, c, d, n, 1362 A, B, C, k, t; 1363 1364 // Radius is zero, return center of circle 1365 if (circ[4] < Mat.eps) { 1366 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) { 1367 return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board); 1368 } 1369 1370 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board); 1371 } 1372 c = circ[0]; 1373 b = circ.slice(1, 3); 1374 a = circ[3]; 1375 d = lin[0]; 1376 n = lin.slice(1, 3); 1377 1378 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 1379 /* 1380 var nn = n[0]*n[0]+n[1]*n[1]; 1381 A = a*nn; 1382 B = (b[0]*n[1]-b[1]*n[0])*nn; 1383 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 1384 */ 1385 A = a; 1386 B = (b[0] * n[1] - b[1] * n[0]); 1387 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 1388 1389 k = B * B - 4 * A * C; 1390 if (k > -Mat.eps * Mat.eps) { 1391 k = Math.sqrt(Math.abs(k)); 1392 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)]; 1393 1394 return ((i === 0) ? 1395 new Coords(Const.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0], -t[0] * n[0] - d * n[1]], board) : 1396 new Coords(Const.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0], -t[1] * n[0] - d * n[1]], board) 1397 ); 1398 } 1399 1400 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1401 }, 1402 1403 /** 1404 * Intersection of two circles. 1405 * @param {Array} circ1 stdform of the first circle 1406 * @param {Array} circ2 stdform of the second circle 1407 * @param {number} i number of the returned intersection point. 1408 * i==0: use the positive square root, 1409 * i==1: use the negative square root. 1410 * @param {JXG.Board} board Reference to the board. 1411 * @returns {JXG.Coords} Coordinates of the intersection point 1412 */ 1413 meetCircleCircle: function (circ1, circ2, i, board) { 1414 var radicalAxis; 1415 1416 // Radius is zero, return center of circle, if on other circle 1417 if (circ1[4] < Mat.eps) { 1418 if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < Mat.eps) { 1419 return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board); 1420 } 1421 1422 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1423 } 1424 1425 // Radius is zero, return center of circle, if on other circle 1426 if (circ2[4] < Mat.eps) { 1427 if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < Mat.eps) { 1428 return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board); 1429 } 1430 1431 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1432 } 1433 1434 radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0], 1435 circ2[3] * circ1[1] - circ1[3] * circ2[1], 1436 circ2[3] * circ1[2] - circ1[3] * circ2[2], 1437 0, 1, Infinity, Infinity, Infinity]; 1438 radicalAxis = Mat.normalize(radicalAxis); 1439 1440 return this.meetLineCircle(radicalAxis, circ1, i, board); 1441 }, 1442 1443 /** 1444 * Compute an intersection of the curves c1 and c2. 1445 * We want to find values t1, t2 such that 1446 * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 1447 * 1448 * Methods: segment-wise intersections (default) or generalized Newton method. 1449 * @param {JXG.Curve} c1 Curve, Line or Circle 1450 * @param {JXG.Curve} c2 Curve, Line or Circle 1451 * @param {Number} nr the nr-th intersection point will be returned. 1452 * @param {Number} t2ini not longer used. 1453 * @param {JXG.Board} [board=c1.board] Reference to a board object. 1454 * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'. 1455 * @returns {JXG.Coords} intersection point 1456 */ 1457 meetCurveCurve: function (c1, c2, nr, t2ini, board, method) { 1458 var co; 1459 1460 if (Type.exists(method) && method === 'newton') { 1461 co = Numerics.generalizedNewton(c1, c2, nr, t2ini); 1462 } else { 1463 if (c1.bezierDegree === 3 || c2.bezierDegree === 3) { 1464 co = this.meetBezierCurveRedBlueSegments(c1, c2, nr); 1465 } else { 1466 co = this.meetCurveRedBlueSegments(c1, c2, nr); 1467 } 1468 } 1469 1470 return (new Coords(Const.COORDS_BY_USER, co, board)); 1471 }, 1472 1473 /** 1474 * Intersection of curve with line, 1475 * Order of input does not matter for el1 and el2. 1476 * From version 0.99.7 on this method calls 1477 * {@link JXG.Math.Geometry.meetCurveLineDiscrete}. 1478 * If higher precision is needed, {@link JXG.Math.Geometry.meetCurveLineContinuous} 1479 * has to be used. 1480 * 1481 * @param {JXG.Curve,JXG.Line} el1 Curve or Line 1482 * @param {JXG.Curve,JXG.Line} el2 Curve or Line 1483 * @param {Number} nr the nr-th intersection point will be returned. 1484 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1485 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection 1486 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1487 * the ideal point [0,1,0] is returned. 1488 */ 1489 meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) { 1490 var v = [0, NaN, NaN], cu, li; 1491 1492 if (!Type.exists(board)) { 1493 board = el1.board; 1494 } 1495 1496 if (el1.elementClass === Const.OBJECT_CLASS_CURVE) { 1497 cu = el1; 1498 li = el2; 1499 } else { 1500 cu = el2; 1501 li = el1; 1502 } 1503 1504 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect); 1505 1506 return v; 1507 }, 1508 1509 /** 1510 * Intersection of line and curve, continuous case. 1511 * Finds the nr-the intersection point 1512 * Uses {@link JXG.Math.Geometry.meetCurveLineDiscrete} as a first approximation. 1513 * A more exact solution is then found with {@link JXG.Math.Numerics.root}. 1514 * 1515 * @param {JXG.Curve} cu Curve 1516 * @param {JXG.Line} li Line 1517 * @param {Number} nr Will return the nr-th intersection point. 1518 * @param {JXG.Board} board 1519 * @returns {JXG.Coords} Coords object containing the intersection. 1520 */ 1521 meetCurveLineContinuous: function (cu, li, nr, board, testSegment) { 1522 var t, func0, func1, v, x, y, z, 1523 eps = Mat.eps, 1524 epsLow = Mat.eps, 1525 steps, delta, tnew, i, 1526 tmin, fmin, ft; 1527 1528 v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment); 1529 x = v.usrCoords[1]; 1530 y = v.usrCoords[2]; 1531 1532 func0 = function (t) { 1533 var c1, c2; 1534 1535 if (t > cu.maxX() || t < cu.minX()) { 1536 return Infinity; 1537 } 1538 c1 = x - cu.X(t); 1539 c2 = y - cu.Y(t); 1540 return c1 * c1 + c2 * c2; 1541 }; 1542 1543 func1 = function (t) { 1544 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1545 return v * v; 1546 }; 1547 1548 // Find t 1549 steps = 50; 1550 delta = (cu.maxX() - cu.minX()) / steps; 1551 tnew = cu.minX(); 1552 1553 fmin = 0.0001; //eps; 1554 tmin = NaN; 1555 for (i = 0; i < steps; i++) { 1556 t = Numerics.root(func0, [Math.max(tnew, cu.minX()), Math.min(tnew + delta, cu.maxX())]); 1557 ft = Math.abs(func0(t)); 1558 if (ft <= fmin) { 1559 fmin = ft; 1560 tmin = t; 1561 if (fmin < eps) { 1562 break; 1563 } 1564 } 1565 1566 tnew += delta; 1567 } 1568 t = tmin; 1569 // Compute "exact" t 1570 t = Numerics.root(func1, [Math.max(t - delta, cu.minX()), Math.min(t + delta, cu.maxX())]); 1571 1572 ft = func1(t); 1573 // Is the point on the line? 1574 if (isNaN(ft) || Math.abs(ft) > epsLow) { 1575 z = 0.0; //NaN; 1576 } else { 1577 z = 1.0; 1578 } 1579 1580 return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1581 }, 1582 1583 1584 /** 1585 * Intersection of line and curve, discrete case. 1586 * Segments are treated as lines. 1587 * Finding the nr-th intersection point should work for all nr. 1588 * @param {JXG.Curve} cu 1589 * @param {JXG.Line} li 1590 * @param {Number} nr 1591 * @param {JXG.Board} board 1592 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 1593 * line defined by the segment 1594 * 1595 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1596 * the ideal point [0,1,0] is returned. 1597 */ 1598 meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) { 1599 var i, j, 1600 p1, p2, p, q, 1601 lip1 = li.point1.coords.usrCoords, 1602 lip2 = li.point2.coords.usrCoords, 1603 d, res, 1604 cnt = 0, 1605 len = cu.numberPoints, 1606 ev_sf = Type.evaluate(li.visProp.straightfirst), 1607 ev_sl = Type.evaluate(li.visProp.straightlast); 1608 1609 // In case, no intersection will be found we will take this 1610 q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board); 1611 1612 if (lip1[0] === 0.0) { 1613 lip1 = [1, lip2[1] + li.stdform[2], lip2[2] - li.stdform[1]]; 1614 } else if (lip2[0] === 0.0) { 1615 lip2 = [1, lip1[1] + li.stdform[2], lip1[2] - li.stdform[1]]; 1616 } 1617 1618 p2 = cu.points[0].usrCoords; 1619 for (i = 1; i < len; i += cu.bezierDegree) { 1620 p1 = p2.slice(0); 1621 p2 = cu.points[i].usrCoords; 1622 d = this.distance(p1, p2); 1623 1624 // The defining points are not identical 1625 if (d > Mat.eps) { 1626 if (cu.bezierDegree === 3) { 1627 res = this.meetBeziersegmentBeziersegment([ 1628 cu.points[i - 1].usrCoords.slice(1), 1629 cu.points[i].usrCoords.slice(1), 1630 cu.points[i + 1].usrCoords.slice(1), 1631 cu.points[i + 2].usrCoords.slice(1) 1632 ], [ 1633 lip1.slice(1), 1634 lip2.slice(1) 1635 ], testSegment); 1636 } else { 1637 res = [this.meetSegmentSegment(p1, p2, lip1, lip2)]; 1638 } 1639 1640 for (j = 0; j < res.length; j++) { 1641 p = res[j]; 1642 if (0 <= p[1] && p[1] <= 1) { 1643 if (cnt === nr) { 1644 /** 1645 * If the intersection point is not part of the segment, 1646 * this intersection point is set to non-existent. 1647 * This prevents jumping behavior of the intersection points. 1648 * But it may be discussed if it is the desired behavior. 1649 */ 1650 if (testSegment && 1651 ((!ev_sf && p[2] < 0) || (!ev_sl && p[2] > 1))) { 1652 return q; // break; 1653 } 1654 1655 q = new Coords(Const.COORDS_BY_USER, p[0], board); 1656 return q; // break; 1657 } 1658 cnt += 1; 1659 } 1660 } 1661 } 1662 } 1663 1664 return q; 1665 }, 1666 1667 /** 1668 * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter). 1669 * We go through each segment of the red curve and search if there is an intersection with a segemnt of the blue curve. 1670 * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines 1671 * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on 1672 * the property bezierDegree of the curves. 1673 * <p> 1674 * This method works also for transformed curves, since only the already 1675 * transformed points are used. 1676 * 1677 * @param {JXG.Curve} red 1678 * @param {JXG.Curve} blue 1679 * @param {Number} nr 1680 */ 1681 meetCurveRedBlueSegments: function (red, blue, nr) { 1682 var i, j, 1683 red1, red2, blue1, blue2, m, 1684 minX, maxX, 1685 iFound = 0, 1686 lenBlue = blue.numberPoints, //points.length, 1687 lenRed = red.numberPoints; //points.length; 1688 1689 if (lenBlue <= 1 || lenRed <= 1) { 1690 return [0, NaN, NaN]; 1691 } 1692 1693 for (i = 1; i < lenRed; i++) { 1694 red1 = red.points[i - 1].usrCoords; 1695 red2 = red.points[i].usrCoords; 1696 minX = Math.min(red1[1], red2[1]); 1697 maxX = Math.max(red1[1], red2[1]); 1698 1699 blue2 = blue.points[0].usrCoords; 1700 for (j = 1; j < lenBlue; j++) { 1701 blue1 = blue2; 1702 blue2 = blue.points[j].usrCoords; 1703 1704 if (Math.min(blue1[1], blue2[1]) < maxX && Math.max(blue1[1], blue2[1]) > minX) { 1705 m = this.meetSegmentSegment(red1, red2, blue1, blue2); 1706 if (m[1] >= 0.0 && m[2] >= 0.0 && 1707 // The two segments meet in the interior or at the start points 1708 ((m[1] < 1.0 && m[2] < 1.0) || 1709 // One of the curve is intersected in the very last point 1710 (i === lenRed - 1 && m[1] === 1.0) || 1711 (j === lenBlue - 1 && m[2] === 1.0))) { 1712 if (iFound === nr) { 1713 return m[0]; 1714 } 1715 1716 iFound++; 1717 } 1718 } 1719 } 1720 } 1721 1722 return [0, NaN, NaN]; 1723 }, 1724 1725 /** 1726 * (Virtual) Intersection of two segments. 1727 * @param {Array} p1 First point of segment 1 using normalized homogeneous coordinates [1,x,y] 1728 * @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 1729 * @param {Array} q1 First point of segment 2 using normalized homogeneous coordinates [1,x,y] 1730 * @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 1731 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 1732 * of the intersection point. The second and third entry give the position of the intersection with respect 1733 * to the definiting parameters. For example, the second entry t is defined by: intersection point = p1 + t * deltaP, where 1734 * deltaP = (p2 - p1) when both parameters are coordinates, and deltaP = p2 if p2 is a point at infinity. 1735 * If the two segments are collinear, [[0,0,0], Infinity, Infinity] is returned. 1736 **/ 1737 meetSegmentSegment: function (p1, p2, q1, q2) { 1738 var t, u, i, d, 1739 li1 = Mat.crossProduct(p1, p2), 1740 li2 = Mat.crossProduct(q1, q2), 1741 c = Mat.crossProduct(li1, li2); 1742 1743 if (Math.abs(c[0]) < Mat.eps) { 1744 return [c, Infinity, Infinity]; 1745 } 1746 1747 // Normalize the intersection coordinates 1748 c[1] /= c[0]; 1749 c[2] /= c[0]; 1750 c[0] /= c[0]; 1751 1752 // Now compute in principle: 1753 // t = dist(c - p1) / dist(p2 - p1) and 1754 // u = dist(c - q1) / dist(q2 - q1) 1755 // However: the points q1, q2, p1, p2 might be ideal points - or in general - the 1756 // coordinates might be not normalized. 1757 // Note that the z-coordinates of p2 and q2 are used to determine whether it should be interpreted 1758 // as a segment coordinate or a direction. 1759 i = (Math.abs(p2[1] - p2[0] * p1[1]) < Mat.eps) ? 2 : 1; 1760 d = p1[i] / p1[0]; 1761 t = (c[i] - d) / ( (p2[0] !== 0) ? (p2[i] / p2[0] - d) : p2[i] ); 1762 1763 i = (Math.abs(q2[1] - q2[0] * q1[1]) < Mat.eps) ? 2 : 1; 1764 d = q1[i] / q1[0]; 1765 u = (c[i] - d) / ( (q2[0] !== 0) ? (q2[i] / q2[0] - d) : q2[i] ); 1766 1767 return [c, t, u]; 1768 }, 1769 1770 /****************************************/ 1771 /**** BEZIER CURVE ALGORITHMS ****/ 1772 /****************************************/ 1773 1774 /** 1775 * Splits a Bezier curve segment defined by four points into 1776 * two Bezier curve segments. Dissection point is t=1/2. 1777 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1778 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1779 * @returns {Array} Array consisting of two coordinate arrays for Bezier curves. 1780 */ 1781 _bezierSplit: function (curve) { 1782 var p0, p1, p2, p00, p22, p000; 1783 1784 p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5]; 1785 p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5]; 1786 p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5]; 1787 1788 p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5]; 1789 p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5]; 1790 1791 p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5]; 1792 1793 return [[curve[0], p0, p00, p000], [p000, p22, p2, curve[3]]]; 1794 }, 1795 1796 /** 1797 * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment 1798 * from its control points. 1799 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1800 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1801 * @returns {Array} Bounding box [minX, maxY, maxX, minY] 1802 */ 1803 _bezierBbox: function (curve) { 1804 var bb = []; 1805 1806 if (curve.length === 4) { // bezierDegree == 3 1807 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX 1808 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY 1809 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX 1810 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY 1811 } else { // bezierDegree == 1 1812 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX 1813 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY 1814 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX 1815 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY 1816 } 1817 1818 return bb; 1819 }, 1820 1821 /** 1822 * Decide if two Bezier curve segments overlap by comparing their bounding boxes. 1823 * @param {Array} bb1 Bounding box of the first Bezier curve segment 1824 * @param {Array} bb2 Bounding box of the second Bezier curve segment 1825 * @returns {Boolean} true if the bounding boxes overlap, false otherwise. 1826 */ 1827 _bezierOverlap: function (bb1, bb2) { 1828 return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1]; 1829 }, 1830 1831 /** 1832 * Append list of intersection points to a list. 1833 * @private 1834 */ 1835 _bezierListConcat: function (L, Lnew, t1, t2) { 1836 var i, 1837 t2exists = Type.exists(t2), 1838 start = 0, 1839 len = Lnew.length, 1840 le = L.length; 1841 1842 if (le > 0 && len > 0 && 1843 ((L[le - 1][1] === 1 && Lnew[0][1] === 0) || 1844 (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0))) { 1845 start = 1; 1846 } 1847 1848 for (i = start; i < len; i++) { 1849 if (t2exists) { 1850 Lnew[i][2] *= 0.5; 1851 Lnew[i][2] += t2; 1852 } 1853 1854 Lnew[i][1] *= 0.5; 1855 Lnew[i][1] += t1; 1856 1857 L.push(Lnew[i]); 1858 } 1859 }, 1860 1861 /** 1862 * Find intersections of two Bezier curve segments by recursive subdivision. 1863 * Below maxlevel determine intersections by intersection line segments. 1864 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 1865 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1866 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 1867 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1868 * @param {Number} level Recursion level 1869 * @returns {Array} List of intersection points (up to nine). Each intersection point is an 1870 * array of length three (homogeneous coordinates) plus preimages. 1871 */ 1872 _bezierMeetSubdivision: function (red, blue, level) { 1873 var bbb, bbr, 1874 ar, b0, b1, r0, r1, m, 1875 p0, p1, q0, q1, 1876 L = [], 1877 maxLev = 5; // Maximum recursion level 1878 1879 bbr = this._bezierBbox(blue); 1880 bbb = this._bezierBbox(red); 1881 1882 if (!this._bezierOverlap(bbr, bbb)) { 1883 return []; 1884 } 1885 1886 if (level < maxLev) { 1887 ar = this._bezierSplit(red); 1888 r0 = ar[0]; 1889 r1 = ar[1]; 1890 1891 ar = this._bezierSplit(blue); 1892 b0 = ar[0]; 1893 b1 = ar[1]; 1894 1895 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b0, level + 1), 0.0, 0.0); 1896 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b1, level + 1), 0, 0.5); 1897 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b0, level + 1), 0.5, 0.0); 1898 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b1, level + 1), 0.5, 0.5); 1899 1900 return L; 1901 } 1902 1903 // Make homogeneous coordinates 1904 q0 = [1].concat(red[0]); 1905 q1 = [1].concat(red[3]); 1906 p0 = [1].concat(blue[0]); 1907 p1 = [1].concat(blue[3]); 1908 1909 m = this.meetSegmentSegment(q0, q1, p0, p1); 1910 1911 if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) { 1912 return [m]; 1913 } 1914 1915 return []; 1916 }, 1917 1918 /** 1919 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 1920 */ 1921 _bezierLineMeetSubdivision: function (red, blue, level, testSegment) { 1922 var bbb, bbr, 1923 ar, r0, r1, m, 1924 p0, p1, q0, q1, 1925 L = [], 1926 maxLev = 5; // Maximum recursion level 1927 1928 bbb = this._bezierBbox(blue); 1929 bbr = this._bezierBbox(red); 1930 1931 if (testSegment && !this._bezierOverlap(bbr, bbb)) { 1932 return []; 1933 } 1934 1935 if (level < maxLev) { 1936 ar = this._bezierSplit(red); 1937 r0 = ar[0]; 1938 r1 = ar[1]; 1939 1940 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r0, blue, level + 1), 0.0); 1941 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r1, blue, level + 1), 0.5); 1942 1943 return L; 1944 } 1945 1946 // Make homogeneous coordinates 1947 q0 = [1].concat(red[0]); 1948 q1 = [1].concat(red[3]); 1949 p0 = [1].concat(blue[0]); 1950 p1 = [1].concat(blue[1]); 1951 1952 m = this.meetSegmentSegment(q0, q1, p0, p1); 1953 1954 if (m[1] >= 0.0 && m[1] <= 1.0) { 1955 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) { 1956 return [m]; 1957 } 1958 } 1959 1960 return []; 1961 }, 1962 1963 /** 1964 * Find the nr-th intersection point of two Bezier curve segments. 1965 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 1966 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1967 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 1968 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1969 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 1970 * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus 1971 * preimages [x,y], t_1, t_2] of the two Bezier curve segments. 1972 * 1973 */ 1974 meetBeziersegmentBeziersegment: function (red, blue, testSegment) { 1975 var L, L2, i; 1976 1977 if (red.length === 4 && blue.length === 4) { 1978 L = this._bezierMeetSubdivision(red, blue, 0); 1979 } else { 1980 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment); 1981 } 1982 1983 L.sort(function (a, b) { 1984 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]); 1985 }); 1986 1987 L2 = []; 1988 for (i = 0; i < L.length; i++) { 1989 // Only push entries different from their predecessor 1990 if (i === 0 || (L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2])) { 1991 L2.push(L[i]); 1992 } 1993 } 1994 return L2; 1995 }, 1996 1997 /** 1998 * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3. 1999 * @param {JXG.Curve} red Curve with bezierDegree == 3 2000 * @param {JXG.Curve} blue Curve with bezierDegree == 3 2001 * @param {Number} nr The number of the intersection point which should be returned. 2002 * @returns {Array} The homogeneous coordinates of the nr-th intersection point. 2003 */ 2004 meetBezierCurveRedBlueSegments: function (red, blue, nr) { 2005 var p, i, j, k, po, 2006 redArr, blueArr, 2007 bbr, bbb, intersections, 2008 startRed = 0, 2009 startBlue = 0, 2010 lenBlue = blue.numberPoints, 2011 lenRed = red.numberPoints, 2012 L = []; 2013 2014 if (lenBlue < blue.bezierDegree + 1 || lenRed < red.bezierDegree + 1) { 2015 return [0, NaN, NaN]; 2016 } 2017 lenBlue -= blue.bezierDegree; 2018 lenRed -= red.bezierDegree; 2019 2020 // For sectors, we ignore the "legs" 2021 if (red.type === Const.OBJECT_TYPE_SECTOR) { 2022 startRed = 3; 2023 lenRed -= 3; 2024 } 2025 if (blue.type === Const.OBJECT_TYPE_SECTOR) { 2026 startBlue = 3; 2027 lenBlue -= 3; 2028 } 2029 2030 for (i = startRed; i < lenRed; i += red.bezierDegree) { 2031 p = red.points; 2032 redArr = [ 2033 p[i].usrCoords.slice(1), 2034 p[i + 1].usrCoords.slice(1) 2035 ]; 2036 if (red.bezierDegree === 3) { 2037 redArr[2] = p[i + 2].usrCoords.slice(1); 2038 redArr[3] = p[i + 3].usrCoords.slice(1); 2039 } 2040 2041 bbr = this._bezierBbox(redArr); 2042 2043 for (j = startBlue; j < lenBlue; j += blue.bezierDegree) { 2044 p = blue.points; 2045 blueArr = [ 2046 p[j].usrCoords.slice(1), 2047 p[j + 1].usrCoords.slice(1) 2048 ]; 2049 if (blue.bezierDegree === 3) { 2050 blueArr[2] = p[j + 2].usrCoords.slice(1); 2051 blueArr[3] = p[j + 3].usrCoords.slice(1); 2052 } 2053 2054 bbb = this._bezierBbox(blueArr); 2055 if (this._bezierOverlap(bbr, bbb)) { 2056 intersections = this.meetBeziersegmentBeziersegment(redArr, blueArr); 2057 if (intersections.length === 0) { 2058 continue; 2059 } 2060 for (k = 0; k < intersections.length; k++) { 2061 po = intersections[k]; 2062 if (po[1] < -Mat.eps || 2063 po[1] > 1 + Mat.eps || 2064 po[2] < -Mat.eps || 2065 po[2] > 1 + Mat.eps) { 2066 continue; 2067 } 2068 L.push(po); 2069 } 2070 if (L.length > nr) { 2071 return L[nr][0]; 2072 } 2073 } 2074 } 2075 } 2076 if (L.length > nr) { 2077 return L[nr][0]; 2078 } 2079 2080 return [0, NaN, NaN]; 2081 }, 2082 2083 bezierSegmentEval: function (t, curve) { 2084 var f, x, y, 2085 t1 = 1.0 - t; 2086 2087 x = 0; 2088 y = 0; 2089 2090 f = t1 * t1 * t1; 2091 x += f * curve[0][0]; 2092 y += f * curve[0][1]; 2093 2094 f = 3.0 * t * t1 * t1; 2095 x += f * curve[1][0]; 2096 y += f * curve[1][1]; 2097 2098 f = 3.0 * t * t * t1; 2099 x += f * curve[2][0]; 2100 y += f * curve[2][1]; 2101 2102 f = t * t * t; 2103 x += f * curve[3][0]; 2104 y += f * curve[3][1]; 2105 2106 return [1.0, x, y]; 2107 }, 2108 2109 /** 2110 * Generate the defining points of a 3rd degree bezier curve that approximates 2111 * a circle sector defined by three coordinate points A, B, C, each defined by an array of length three. 2112 * The coordinate arrays are given in homogeneous coordinates. 2113 * @param {Array} A First point 2114 * @param {Array} B Second point (intersection point) 2115 * @param {Array} C Third point 2116 * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve. 2117 * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1. 2118 */ 2119 bezierArc: function (A, B, C, withLegs, sgn) { 2120 var p1, p2, p3, p4, 2121 r, phi, beta, 2122 PI2 = Math.PI * 0.5, 2123 x = B[1], 2124 y = B[2], 2125 z = B[0], 2126 dataX = [], dataY = [], 2127 co, si, ax, ay, bx, by, k, v, d, matrix; 2128 2129 r = this.distance(B, A); 2130 2131 // x,y, z is intersection point. Normalize it. 2132 x /= z; 2133 y /= z; 2134 2135 phi = this.rad(A.slice(1), B.slice(1), C.slice(1)); 2136 if (sgn === -1) { 2137 phi = 2 * Math.PI - phi; 2138 } 2139 2140 p1 = A; 2141 p1[1] /= p1[0]; 2142 p1[2] /= p1[0]; 2143 p1[0] /= p1[0]; 2144 2145 p4 = p1.slice(0); 2146 2147 if (withLegs) { 2148 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]]; 2149 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]]; 2150 } else { 2151 dataX = [p1[1]]; 2152 dataY = [p1[2]]; 2153 } 2154 2155 while (phi > Mat.eps) { 2156 if (phi > PI2) { 2157 beta = PI2; 2158 phi -= PI2; 2159 } else { 2160 beta = phi; 2161 phi = 0; 2162 } 2163 2164 co = Math.cos(sgn * beta); 2165 si = Math.sin(sgn * beta); 2166 2167 matrix = [ 2168 [1, 0, 0], 2169 [x * (1 - co) + y * si, co, -si], 2170 [y * (1 - co) - x * si, si, co] 2171 ]; 2172 v = Mat.matVecMult(matrix, p1); 2173 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]]; 2174 2175 ax = p1[1] - x; 2176 ay = p1[2] - y; 2177 bx = p4[1] - x; 2178 by = p4[2] - y; 2179 2180 d = Math.sqrt((ax + bx) * (ax + bx) + (ay + by) * (ay + by)); 2181 2182 if (Math.abs(by - ay) > Mat.eps) { 2183 k = (ax + bx) * (r / d - 0.5) / (by - ay) * 8 / 3; 2184 } else { 2185 k = (ay + by) * (r / d - 0.5) / (ax - bx) * 8 / 3; 2186 } 2187 2188 p2 = [1, p1[1] - k * ay, p1[2] + k * ax]; 2189 p3 = [1, p4[1] + k * by, p4[2] - k * bx]; 2190 2191 dataX = dataX.concat([p2[1], p3[1], p4[1]]); 2192 dataY = dataY.concat([p2[2], p3[2], p4[2]]); 2193 p1 = p4.slice(0); 2194 } 2195 2196 if (withLegs) { 2197 dataX = dataX.concat([ p4[1] + 0.333 * (x - p4[1]), p4[1] + 0.666 * (x - p4[1]), x]); 2198 dataY = dataY.concat([ p4[2] + 0.333 * (y - p4[2]), p4[2] + 0.666 * (y - p4[2]), y]); 2199 } 2200 2201 return [dataX, dataY]; 2202 }, 2203 2204 /****************************************/ 2205 /**** PROJECTIONS ****/ 2206 /****************************************/ 2207 2208 /** 2209 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 2210 * nearest one of the two intersection points of the line through the given point and the circles 2211 * center. 2212 * @param {JXG.Point,JXG.Coords} point Point to project or coords object to project. 2213 * @param {JXG.Circle} circle Circle on that the point is projected. 2214 * @param {JXG.Board} [board=point.board] Reference to the board 2215 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2216 */ 2217 projectPointToCircle: function (point, circle, board) { 2218 var dist, P, x, y, factor, 2219 M = circle.center.coords.usrCoords; 2220 2221 if (!Type.exists(board)) { 2222 board = point.board; 2223 } 2224 2225 // gave us a point 2226 if (Type.isPoint(point)) { 2227 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords); 2228 P = point.coords.usrCoords; 2229 // gave us coords 2230 } else { 2231 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords); 2232 P = point.usrCoords; 2233 } 2234 2235 if (Math.abs(dist) < Mat.eps) { 2236 dist = Mat.eps; 2237 } 2238 2239 factor = circle.Radius() / dist; 2240 x = M[1] + factor * (P[1] - M[1]); 2241 y = M[2] + factor * (P[2] - M[2]); 2242 2243 return new Coords(Const.COORDS_BY_USER, [x, y], board); 2244 }, 2245 2246 /** 2247 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 2248 * intersection point of the given line and its perpendicular through the given point. 2249 * @param {JXG.Point|JXG.Coords} point Point to project. 2250 * @param {JXG.Line} line Line on that the point is projected. 2251 * @param {JXG.Board} [board=point.board|board=line.board] Reference to a board. 2252 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 2253 */ 2254 projectPointToLine: function (point, line, board) { 2255 var v = [0, line.stdform[1], line.stdform[2]], 2256 coords; 2257 2258 if (!Type.exists(board)) { 2259 if (Type.exists(point.coords)) { 2260 board = point.board; 2261 } else { 2262 board = line.board; 2263 } 2264 } 2265 2266 if (Type.exists(point.coords)) { 2267 coords = point.coords.usrCoords; 2268 } else { 2269 coords = point.usrCoords; 2270 } 2271 2272 v = Mat.crossProduct(v, coords); 2273 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(v, line.stdform), board); 2274 }, 2275 2276 /** 2277 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 2278 * segment defined by two coordinate arrays. 2279 * @param {Array} p Point to project. 2280 * @param {Array} q1 Start point of the line segment on that the point is projected. 2281 * @param {Array} q2 End point of the line segment on that the point is projected. 2282 * @returns {Array} The coordinates of the projection of the given point on the given segment 2283 * and the factor that determines the projected point as a convex combination of the 2284 * two endpoints q1 and q2 of the segment. 2285 */ 2286 projectCoordsToSegment: function (p, q1, q2) { 2287 var t, denom, 2288 s = [q2[1] - q1[1], q2[2] - q1[2]], 2289 v = [p[1] - q1[1], p[2] - q1[2]]; 2290 2291 /** 2292 * If the segment has length 0, i.e. is a point, 2293 * the projection is equal to that point. 2294 */ 2295 if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) { 2296 return [q1, 0]; 2297 } 2298 2299 t = Mat.innerProduct(v, s); 2300 denom = Mat.innerProduct(s, s); 2301 t /= denom; 2302 2303 return [ [1, t * s[0] + q1[1], t * s[1] + q1[2]], t]; 2304 }, 2305 2306 /** 2307 * Finds the coordinates of the closest point on a Bezier segment of a 2308 * {@link JXG.Curve} to a given coordinate array. 2309 * @param {Array} pos Point to project in homogeneous coordinates. 2310 * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3. 2311 * @param {Number} start Number of the Bezier segment of the curve. 2312 * @returns {Array} The coordinates of the projection of the given point 2313 * on the given Bezier segment and the preimage of the curve which 2314 * determines the closest point. 2315 */ 2316 projectCoordsToBeziersegment: function (pos, curve, start) { 2317 var t0, 2318 /** @ignore */ 2319 minfunc = function (t) { 2320 var z = [1, curve.X(start + t), curve.Y(start + t)]; 2321 2322 z[1] -= pos[1]; 2323 z[2] -= pos[2]; 2324 2325 return z[1] * z[1] + z[2] * z[2]; 2326 }; 2327 2328 t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]); 2329 2330 return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0]; 2331 }, 2332 2333 /** 2334 * Calculates the coordinates of the projection of a given point on a given curve. 2335 * Uses {@link JXG.Math.Geometry.projectCoordsToCurve}. 2336 * 2337 * @param {JXG.Point} point Point to project. 2338 * @param {JXG.Curve} curve Curve on that the point is projected. 2339 * @param {JXG.Board} [board=point.board] Reference to a board. 2340 * @see #projectCoordsToCurve 2341 * @returns {Array} [JXG.Coords, position] The coordinates of the projection of the given 2342 * point on the given graph and the relative position on the curve (real number). 2343 */ 2344 projectPointToCurve: function (point, curve, board) { 2345 if (!Type.exists(board)) { 2346 board = point.board; 2347 } 2348 2349 var x = point.X(), 2350 y = point.Y(), 2351 t = point.position || 0.0, 2352 result = this.projectCoordsToCurve(x, y, t, curve, board); 2353 2354 // point.position = result[1]; 2355 2356 return result; 2357 }, 2358 2359 /** 2360 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 2361 * function graphs this is the 2362 * intersection point of the curve and the parallel to y-axis through the given point. 2363 * @param {Number} x coordinate to project. 2364 * @param {Number} y coordinate to project. 2365 * @param {Number} t start value for newtons method 2366 * @param {JXG.Curve} curve Curve on that the point is projected. 2367 * @param {JXG.Board} [board=curve.board] Reference to a board. 2368 * @see #projectPointToCurve 2369 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given curve and 2370 * the position on the curve. 2371 */ 2372 projectCoordsToCurve: function (x, y, t, curve, board) { 2373 var newCoords, newCoordsObj, i, j, 2374 mindist, dist, lbda, v, coords, d, 2375 p1, p2, res, 2376 minfunc, t_new, f_new, f_old, delta, steps, 2377 minX, maxX, 2378 infty = Number.POSITIVE_INFINITY; 2379 2380 if (!Type.exists(board)) { 2381 board = curve.board; 2382 } 2383 2384 2385 if (Type.evaluate(curve.visProp.curvetype) === 'plot') { 2386 t = 0; 2387 mindist = infty; 2388 if (curve.numberPoints === 0) { 2389 newCoords = [0, 1, 1]; 2390 } else { 2391 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 2392 } 2393 2394 if (curve.numberPoints > 1) { 2395 v = [1, x, y]; 2396 if (curve.bezierDegree === 3) { 2397 j = 0; 2398 } else { 2399 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 2400 } 2401 for (i = 0; i < curve.numberPoints - 1; i++) { 2402 if (curve.bezierDegree === 3) { 2403 res = this.projectCoordsToBeziersegment(v, curve, j); 2404 } else { 2405 p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)]; 2406 res = this.projectCoordsToSegment(v, p1, p2); 2407 } 2408 lbda = res[1]; 2409 coords = res[0]; 2410 2411 if (0.0 <= lbda && lbda <= 1.0) { 2412 dist = this.distance(coords, v); 2413 d = i + lbda; 2414 } else if (lbda < 0.0) { 2415 coords = p1; 2416 dist = this.distance(p1, v); 2417 d = i; 2418 } else if (lbda > 1.0 && i === curve.numberPoints - 2) { 2419 coords = p2; 2420 dist = this.distance(coords, v); 2421 d = curve.numberPoints - 1; 2422 } 2423 2424 if (dist < mindist) { 2425 mindist = dist; 2426 t = d; 2427 newCoords = coords; 2428 } 2429 2430 if (curve.bezierDegree === 3) { 2431 j++; 2432 i += 2; 2433 } else { 2434 p1 = p2; 2435 } 2436 } 2437 } 2438 2439 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board); 2440 } else { // 'parameter', 'polar', 'functiongraph' 2441 /** @ignore */ 2442 minfunc = function (t) { 2443 var dx, dy; 2444 if (t < curve.minX() || t > curve.maxX()) { 2445 return Infinity; 2446 } 2447 dx = x - curve.X(t); 2448 dy = y - curve.Y(t); 2449 return dx * dx + dy * dy; 2450 }; 2451 2452 f_old = minfunc(t); 2453 steps = 50; 2454 minX = curve.minX(); 2455 maxX = curve.maxX(); 2456 2457 delta = (maxX - minX) / steps; 2458 t_new = minX; 2459 2460 for (i = 0; i < steps; i++) { 2461 f_new = minfunc(t_new); 2462 2463 if (f_new < f_old || f_old === Infinity) { 2464 t = t_new; 2465 f_old = f_new; 2466 } 2467 2468 t_new += delta; 2469 } 2470 2471 //t = Numerics.root(Numerics.D(minfunc), t); 2472 t = Numerics.fminbr(minfunc, [Math.max(t - delta, minX), Math.min(t + delta, maxX)]); 2473 2474 // Distinction between closed and open curves is not necessary. 2475 // If closed, the cyclic projection shift will work anyhow 2476 // if (Math.abs(curve.X(minX) - curve.X(maxX)) < Mat.eps && 2477 // Math.abs(curve.Y(minX) - curve.Y(maxX)) < Mat.eps) { 2478 // // Cyclically 2479 // if (t < minX) { 2480 // t = maxX + t - minX; 2481 // } 2482 // if (t > maxX) { 2483 // t = minX + t - maxX; 2484 // } 2485 // } else { 2486 t = (t < minX) ? minX : t; 2487 t = (t > maxX) ? maxX : t; 2488 // } 2489 2490 newCoordsObj = new Coords(Const.COORDS_BY_USER, [curve.X(t), curve.Y(t)], board); 2491 } 2492 2493 return [curve.updateTransform(newCoordsObj), t]; 2494 }, 2495 2496 /** 2497 * Calculates the coordinates of the closest orthogonal projection of a given coordinate array onto the 2498 * border of a polygon. 2499 * @param {Array} p Point to project. 2500 * @param {JXG.Polygon} pol Polygon element 2501 * @returns {Array} The coordinates of the closest projection of the given point to the border of the polygon. 2502 */ 2503 projectCoordsToPolygon: function (p, pol) { 2504 var i, 2505 len = pol.vertices.length, 2506 d_best = Infinity, 2507 d, 2508 projection, proj, 2509 bestprojection; 2510 2511 for (i = 0; i < len - 1; i++) { 2512 projection = JXG.Math.Geometry.projectCoordsToSegment( 2513 p, 2514 pol.vertices[i].coords.usrCoords, 2515 pol.vertices[i + 1].coords.usrCoords 2516 ); 2517 2518 if (0 <= projection[1] && projection[1] <= 1) { 2519 d = JXG.Math.Geometry.distance(projection[0], p, 3); 2520 proj = projection[0]; 2521 } else if (projection[1] < 0) { 2522 d = JXG.Math.Geometry.distance(pol.vertices[i].coords.usrCoords, p, 3); 2523 proj = pol.vertices[i].coords.usrCoords; 2524 } else { 2525 d = JXG.Math.Geometry.distance(pol.vertices[i + 1].coords.usrCoords, p, 3); 2526 proj = pol.vertices[i + 1].coords.usrCoords; 2527 } 2528 if (d < d_best) { 2529 bestprojection = proj.slice(0); 2530 d_best = d; 2531 } 2532 } 2533 return bestprojection; 2534 }, 2535 2536 /** 2537 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 2538 * one or more curves of curveType 'plot'. Uses {@link JXG.Math.Geometry.projectPointToCurve}. 2539 * @param {JXG.Point} point Point to project. 2540 * @param {JXG.Turtle} turtle on that the point is projected. 2541 * @param {JXG.Board} [board=point.board] Reference to a board. 2542 * @returns {Array} [JXG.Coords, position] Array containing the coordinates of the projection of the given point on the turtle and 2543 * the position on the turtle. 2544 */ 2545 projectPointToTurtle: function (point, turtle, board) { 2546 var newCoords, t, x, y, i, dist, el, minEl, 2547 res, newPos, 2548 np = 0, 2549 npmin = 0, 2550 mindist = Number.POSITIVE_INFINITY, 2551 len = turtle.objects.length; 2552 2553 if (!Type.exists(board)) { 2554 board = point.board; 2555 } 2556 2557 // run through all curves of this turtle 2558 for (i = 0; i < len; i++) { 2559 el = turtle.objects[i]; 2560 2561 if (el.elementClass === Const.OBJECT_CLASS_CURVE) { 2562 res = this.projectPointToCurve(point, el); 2563 newCoords = res[0]; 2564 newPos = res[1]; 2565 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 2566 2567 if (dist < mindist) { 2568 x = newCoords.usrCoords[1]; 2569 y = newCoords.usrCoords[2]; 2570 t = newPos; 2571 mindist = dist; 2572 minEl = el; 2573 npmin = np; 2574 } 2575 np += el.numberPoints; 2576 } 2577 } 2578 2579 newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board); 2580 // point.position = t + npmin; 2581 // return minEl.updateTransform(newCoords); 2582 return [minEl.updateTransform(newCoords), t + npmin]; 2583 }, 2584 2585 /** 2586 * Trivial projection of a point to another point. 2587 * @param {JXG.Point} point Point to project (not used). 2588 * @param {JXG.Point} dest Point on that the point is projected. 2589 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2590 */ 2591 projectPointToPoint: function (point, dest) { 2592 return dest.coords; 2593 }, 2594 2595 /** 2596 * 2597 * @param {JXG.Point|JXG.Coords} point 2598 * @param {JXG.Board} [board] 2599 */ 2600 projectPointToBoard: function (point, board) { 2601 var i, l, c, 2602 brd = board || point.board, 2603 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx 2604 config = [ 2605 // left 2606 [1, 1, 0, 0, 3, 0, 1], 2607 // top 2608 [-1, 2, 1, 0, 1, 2, 1], 2609 // right 2610 [-1, 1, 2, 2, 1, 2, 3], 2611 // bottom 2612 [1, 2, 3, 0, 3, 2, 3] 2613 ], 2614 coords = point.coords || point, 2615 bbox = brd.getBoundingBox(); 2616 2617 for (i = 0; i < 4; i++) { 2618 c = config[i]; 2619 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) { 2620 // define border 2621 l = Mat.crossProduct([1, bbox[c[3]], bbox[c[4]]], [1, bbox[c[5]], bbox[c[6]]]); 2622 l[3] = 0; 2623 l = Mat.normalize(l); 2624 2625 // project point 2626 coords = this.projectPointToLine({coords: coords}, {stdform: l}, brd); 2627 } 2628 } 2629 2630 return coords; 2631 }, 2632 2633 /** 2634 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 2635 * coordinates. For lines this can be line.stdform. 2636 * @param {Array} point Homogeneous coordinates of a point. 2637 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 2638 * @returns {Number} Distance of the point to the line. 2639 */ 2640 distPointLine: function (point, line) { 2641 var a = line[1], 2642 b = line[2], 2643 c = line[0], 2644 nom; 2645 2646 if (Math.abs(a) + Math.abs(b) < Mat.eps) { 2647 return Number.POSITIVE_INFINITY; 2648 } 2649 2650 nom = a * point[1] + b * point[2] + c; 2651 a *= a; 2652 b *= b; 2653 2654 return Math.abs(nom) / Math.sqrt(a + b); 2655 }, 2656 2657 /** 2658 * Helper function to create curve which displays a Reuleaux polygons. 2659 * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically, 2660 * these point list is the array vertices of a regular polygon. 2661 * @param {Number} nr Number of vertices 2662 * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values 2663 * for the start and the end of the paramtric curve. array may be used as parent array of a 2664 * {@link JXG.Curve}. 2665 * 2666 * @example 2667 * var A = brd.create('point',[-2,-2]); 2668 * var B = brd.create('point',[0,1]); 2669 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2670 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2671 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2672 * 2673 * </pre><div class="jxgbox" id="JXG2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div> 2674 * <script type="text/javascript"> 2675 * var brd = JXG.JSXGraph.initBoard('JXG2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false}); 2676 * var A = brd.create('point',[-2,-2]); 2677 * var B = brd.create('point',[0,1]); 2678 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2679 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2680 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2681 * </script><pre> 2682 */ 2683 reuleauxPolygon: function (points, nr) { 2684 var beta, 2685 pi2 = Math.PI * 2, 2686 pi2_n = pi2 / nr, 2687 diag = (nr - 1) / 2, 2688 d = 0, 2689 makeFct = function (which, trig) { 2690 return function (t, suspendUpdate) { 2691 var t1 = (t % pi2 + pi2) % pi2, 2692 j = Math.floor(t1 / pi2_n) % nr; 2693 2694 if (!suspendUpdate) { 2695 d = points[0].Dist(points[diag]); 2696 beta = Mat.Geometry.rad([points[0].X() + 1, points[0].Y()], points[0], points[diag % nr]); 2697 } 2698 2699 if (isNaN(j)) { 2700 return j; 2701 } 2702 2703 t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta; 2704 2705 return points[j][which]() + d * Math[trig](t1); 2706 }; 2707 }; 2708 2709 return [makeFct('X', 'cos'), makeFct('Y', 'sin'), 0, pi2]; 2710 }, 2711 2712 2713 meet3Planes: function (n1, d1, n2, d2, n3, d3) { 2714 var p = [0, 0, 0], 2715 n31, n12, n23, denom, 2716 i; 2717 2718 n31 = Mat.crossProduct(n3, n1); 2719 n12 = Mat.crossProduct(n1, n2); 2720 n23 = Mat.crossProduct(n2, n3); 2721 denom = Mat.innerProduct(n1, n23, 3); 2722 for (i = 0; i < 3; i++) { 2723 p[i] = (d1 * n23[i] + d2 * n31[i] + d3 * n12[i]) / denom; 2724 } 2725 return p; 2726 }, 2727 2728 2729 meetPlanePlane: function (v11, v12, v21, v22) { 2730 var i, no1, no2, 2731 v = [0, 0, 0], 2732 w = [0, 0, 0]; 2733 2734 for (i = 0; i < 3; i++) { 2735 v[i] = Type.evaluate(v11[i]); 2736 w[i] = Type.evaluate(v12[i]); 2737 } 2738 no1 = Mat.crossProduct(v, w); 2739 2740 for (i = 0; i < 3; i++) { 2741 v[i] = Type.evaluate(v21[i]); 2742 w[i] = Type.evaluate(v22[i]); 2743 } 2744 no2 = Mat.crossProduct(v, w); 2745 2746 return Mat.crossProduct(no1, no2); 2747 }, 2748 2749 project3DTo3DPlane: function (point, normal, foot) { 2750 // TODO: homogeneous 3D coordinates 2751 var sol = [0, 0, 0], 2752 le, d1, d2, lbda; 2753 2754 foot = foot || [0, 0, 0]; 2755 2756 le = Mat.norm(normal); 2757 d1 = Mat.innerProduct(point, normal, 3); 2758 d2 = Mat.innerProduct(foot, normal, 3); 2759 // (point - lbda * normal / le) * normal / le == foot * normal / le 2760 // => (point * normal - foot * normal) == lbda * le 2761 lbda = (d1 - d2) / le; 2762 sol = Mat.axpy(-lbda, normal, point); 2763 2764 return sol; 2765 }, 2766 2767 getPlaneBounds: function (v1, v2, q, s, e) { 2768 var s1, s2, e1, e2, mat, rhs, sol; 2769 2770 if (v1[2] + v2[0] !== 0) { 2771 mat = [ 2772 [v1[0], v2[0]], 2773 [v1[1], v2[1]] 2774 ]; 2775 rhs = [s - q[0], s - q[1]]; 2776 2777 sol = Numerics.Gauss(mat, rhs); 2778 s1 = sol[0]; 2779 s2 = sol[1]; 2780 2781 rhs = [e - q[0], e - q[1]]; 2782 sol = Numerics.Gauss(mat, rhs); 2783 e1 = sol[0]; 2784 e2 = sol[1]; 2785 return [s1, e1, s2, e2]; 2786 } 2787 return null; 2788 }, 2789 2790 }); 2791 2792 return Mat.Geometry; 2793 }); 2794