1 /* 2 Copyright 2008-2024 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 <https://www.gnu.org/licenses/> 30 and <https://opensource.org/licenses/MIT/>. 31 */ 32 33 /*global JXG: true, define: true*/ 34 /*jslint nomen: true, plusplus: true*/ 35 36 /** 37 * @fileoverview This file contains the Math.Geometry namespace for calculating algebraic/geometric 38 * stuff like intersection points, angles, midpoint, and so on. 39 */ 40 41 import JXG from "../jxg.js"; 42 import Const from "../base/constants.js"; 43 import Coords from "../base/coords.js"; 44 import Mat from "./math.js"; 45 import Numerics from "./numerics.js"; 46 import Type from "../utils/type.js"; 47 import Expect from "../utils/expect.js"; 48 49 /** 50 * Math.Geometry namespace definition. This namespace holds geometrical algorithms, 51 * especially intersection algorithms. 52 * @name JXG.Math.Geometry 53 * @namespace 54 */ 55 Mat.Geometry = {}; 56 57 // the splitting is necessary due to the shortcut for the circumcircleMidpoint method to circumcenter. 58 59 JXG.extend( 60 Mat.Geometry, 61 /** @lends JXG.Math.Geometry */ { 62 /* ***************************************/ 63 /* *** GENERAL GEOMETRIC CALCULATIONS ****/ 64 /* ***************************************/ 65 66 /** 67 * Calculates the angle defined by the points A, B, C. 68 * @param {JXG.Point|Array} A A point or [x,y] array. 69 * @param {JXG.Point|Array} B Another point or [x,y] array. 70 * @param {JXG.Point|Array} C A circle - no, of course the third point or [x,y] array. 71 * @deprecated Use {@link JXG.Math.Geometry.rad} instead. 72 * @see #rad 73 * @see #trueAngle 74 * @returns {Number} The angle in radian measure. 75 */ 76 angle: function (A, B, C) { 77 var u, 78 v, 79 s, 80 t, 81 a = [], 82 b = [], 83 c = []; 84 85 JXG.deprecated("Geometry.angle()", "Geometry.rad()"); 86 if (A.coords) { 87 a[0] = A.coords.usrCoords[1]; 88 a[1] = A.coords.usrCoords[2]; 89 } else { 90 a[0] = A[0]; 91 a[1] = A[1]; 92 } 93 94 if (B.coords) { 95 b[0] = B.coords.usrCoords[1]; 96 b[1] = B.coords.usrCoords[2]; 97 } else { 98 b[0] = B[0]; 99 b[1] = B[1]; 100 } 101 102 if (C.coords) { 103 c[0] = C.coords.usrCoords[1]; 104 c[1] = C.coords.usrCoords[2]; 105 } else { 106 c[0] = C[0]; 107 c[1] = C[1]; 108 } 109 110 u = a[0] - b[0]; 111 v = a[1] - b[1]; 112 s = c[0] - b[0]; 113 t = c[1] - b[1]; 114 115 return Math.atan2(u * t - v * s, u * s + v * t); 116 }, 117 118 /** 119 * Calculates the angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 120 * @param {JXG.Point|Array} A Point or [x,y] array 121 * @param {JXG.Point|Array} B Point or [x,y] array 122 * @param {JXG.Point|Array} C Point or [x,y] array 123 * @see #rad 124 * @returns {Number} The angle in degrees. 125 */ 126 trueAngle: function (A, B, C) { 127 return this.rad(A, B, C) * 57.295779513082323; // *180.0/Math.PI; 128 }, 129 130 /** 131 * Calculates the internal angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 132 * @param {JXG.Point|Array} A Point or [x,y] array 133 * @param {JXG.Point|Array} B Point or [x,y] array 134 * @param {JXG.Point|Array} C Point or [x,y] array 135 * @see #trueAngle 136 * @returns {Number} Angle in radians. 137 */ 138 rad: function (A, B, C) { 139 var ax, ay, bx, by, cx, cy, phi; 140 141 if (A.coords) { 142 ax = A.coords.usrCoords[1]; 143 ay = A.coords.usrCoords[2]; 144 } else { 145 ax = A[0]; 146 ay = A[1]; 147 } 148 149 if (B.coords) { 150 bx = B.coords.usrCoords[1]; 151 by = B.coords.usrCoords[2]; 152 } else { 153 bx = B[0]; 154 by = B[1]; 155 } 156 157 if (C.coords) { 158 cx = C.coords.usrCoords[1]; 159 cy = C.coords.usrCoords[2]; 160 } else { 161 cx = C[0]; 162 cy = C[1]; 163 } 164 165 phi = Math.atan2(cy - by, cx - bx) - Math.atan2(ay - by, ax - bx); 166 167 if (phi < 0) { 168 phi += 6.2831853071795862; 169 } 170 171 return phi; 172 }, 173 174 /** 175 * Calculates a point on the bisection line between the three points A, B, C. 176 * As a result, the bisection line is defined by two points: 177 * Parameter B and the point with the coordinates calculated in this function. 178 * Does not work for ideal points. 179 * @param {JXG.Point} A Point 180 * @param {JXG.Point} B Point 181 * @param {JXG.Point} C Point 182 * @param [board=A.board] Reference to the board 183 * @returns {JXG.Coords} Coordinates of the second point defining the bisection. 184 */ 185 angleBisector: function (A, B, C, board) { 186 var phiA, 187 phiC, 188 phi, 189 Ac = A.coords.usrCoords, 190 Bc = B.coords.usrCoords, 191 Cc = C.coords.usrCoords, 192 x, 193 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( 202 Const.COORDS_BY_USER, 203 [1, (Ac[1] + Cc[1]) * 0.5, (Ac[2] + Cc[2]) * 0.5], 204 board 205 ); 206 } 207 208 // Non-parallel lines 209 x = Ac[1] - Bc[1]; 210 y = Ac[2] - Bc[2]; 211 phiA = Math.atan2(y, x); 212 213 x = Cc[1] - Bc[1]; 214 y = Cc[2] - Bc[2]; 215 phiC = Math.atan2(y, x); 216 217 phi = (phiA + phiC) * 0.5; 218 219 if (phiA > phiC) { 220 phi += Math.PI; 221 } 222 223 x = Math.cos(phi) + Bc[1]; 224 y = Math.sin(phi) + Bc[2]; 225 226 return new Coords(Const.COORDS_BY_USER, [1, x, y], board); 227 }, 228 229 // /** 230 // * Calculates a point on the m-section line between the three points A, B, C. 231 // * As a result, the m-section line is defined by two points: 232 // * Parameter B and the point with the coordinates calculated in this function. 233 // * The m-section generalizes the bisector to any real number. 234 // * For example, the trisectors of an angle are simply the 1/3-sector and the 2/3-sector. 235 // * Does not work for ideal points. 236 // * @param {JXG.Point} A Point 237 // * @param {JXG.Point} B Point 238 // * @param {JXG.Point} C Point 239 // * @param {Number} m Number 240 // * @param [board=A.board] Reference to the board 241 // * @returns {JXG.Coords} Coordinates of the second point defining the bisection. 242 // */ 243 // angleMsector: function (A, B, C, m, board) { 244 // var phiA, phiC, phi, 245 // Ac = A.coords.usrCoords, 246 // Bc = B.coords.usrCoords, 247 // Cc = C.coords.usrCoords, 248 // x, y; 249 250 // if (!Type.exists(board)) { 251 // board = A.board; 252 // } 253 254 // // Parallel lines 255 // if (Bc[0] === 0) { 256 // return new Coords(Const.COORDS_BY_USER, 257 // [1, (Ac[1] + Cc[1]) * m, (Ac[2] + Cc[2]) * m], board); 258 // } 259 260 // // Non-parallel lines 261 // x = Ac[1] - Bc[1]; 262 // y = Ac[2] - Bc[2]; 263 // phiA = Math.atan2(y, x); 264 265 // x = Cc[1] - Bc[1]; 266 // y = Cc[2] - Bc[2]; 267 // phiC = Math.atan2(y, x); 268 269 // phi = phiA + ((phiC - phiA) * m); 270 271 // if (phiA - phiC > Math.PI) { 272 // phi += 2*m*Math.PI; 273 // } 274 275 // x = Math.cos(phi) + Bc[1]; 276 // y = Math.sin(phi) + Bc[2]; 277 278 // return new Coords(Const.COORDS_BY_USER, [1, x, y], board); 279 // }, 280 281 /** 282 * Reflects the point along the line. 283 * @param {JXG.Line} line Axis of reflection. 284 * @param {JXG.Point} point Point to reflect. 285 * @param [board=point.board] Reference to the board 286 * @returns {JXG.Coords} Coordinates of the reflected point. 287 */ 288 reflection: function (line, point, board) { 289 // (v,w) defines the slope of the line 290 var x0, 291 y0, 292 x1, 293 y1, 294 v, 295 w, 296 mu, 297 pc = point.coords.usrCoords, 298 p1c = line.point1.coords.usrCoords, 299 p2c = line.point2.coords.usrCoords; 300 301 if (!Type.exists(board)) { 302 board = point.board; 303 } 304 305 v = p2c[1] - p1c[1]; 306 w = p2c[2] - p1c[2]; 307 308 x0 = pc[1] - p1c[1]; 309 y0 = pc[2] - p1c[2]; 310 311 mu = (v * y0 - w * x0) / (v * v + w * w); 312 313 // point + mu*(-y,x) is the perpendicular foot 314 x1 = pc[1] + 2 * mu * w; 315 y1 = pc[2] - 2 * mu * v; 316 317 return new Coords(Const.COORDS_BY_USER, [x1, y1], board); 318 }, 319 320 /** 321 * Computes the new position of a point which is rotated 322 * around a second point (called rotpoint) by the angle phi. 323 * @param {JXG.Point} rotpoint Center of the rotation 324 * @param {JXG.Point} point point to be rotated 325 * @param {Number} phi rotation angle in arc length 326 * @param {JXG.Board} [board=point.board] Reference to the board 327 * @returns {JXG.Coords} Coordinates of the new position. 328 */ 329 rotation: function (rotpoint, point, phi, board) { 330 var x0, 331 y0, 332 c, 333 s, 334 x1, 335 y1, 336 pc = point.coords.usrCoords, 337 rotpc = rotpoint.coords.usrCoords; 338 339 if (!Type.exists(board)) { 340 board = point.board; 341 } 342 343 x0 = pc[1] - rotpc[1]; 344 y0 = pc[2] - rotpc[2]; 345 346 c = Math.cos(phi); 347 s = Math.sin(phi); 348 349 x1 = x0 * c - y0 * s + rotpc[1]; 350 y1 = x0 * s + y0 * c + rotpc[2]; 351 352 return new Coords(Const.COORDS_BY_USER, [x1, y1], board); 353 }, 354 355 /** 356 * Calculates the coordinates of a point on the perpendicular to the given line through 357 * the given point. 358 * @param {JXG.Line} line A line. 359 * @param {JXG.Point} point Point which is projected to the line. 360 * @param {JXG.Board} [board=point.board] Reference to the board 361 * @returns {Array} Array of length two containing coordinates of a point on the perpendicular to the given line 362 * through the given point and boolean flag "change". 363 */ 364 perpendicular: function (line, point, board) { 365 var x, 366 y, 367 change, 368 c, 369 z, 370 A = line.point1.coords.usrCoords, 371 B = line.point2.coords.usrCoords, 372 C = point.coords.usrCoords; 373 374 if (!Type.exists(board)) { 375 board = point.board; 376 } 377 378 // special case: point is the first point of the line 379 if (point === line.point1) { 380 x = A[1] + B[2] - A[2]; 381 y = A[2] - B[1] + A[1]; 382 z = A[0] * B[0]; 383 384 if (Math.abs(z) < Mat.eps) { 385 x = B[2]; 386 y = -B[1]; 387 } 388 c = [z, x, y]; 389 change = true; 390 391 // special case: point is the second point of the line 392 } else if (point === line.point2) { 393 x = B[1] + A[2] - B[2]; 394 y = B[2] - A[1] + B[1]; 395 z = A[0] * B[0]; 396 397 if (Math.abs(z) < Mat.eps) { 398 x = A[2]; 399 y = -A[1]; 400 } 401 c = [z, x, y]; 402 change = false; 403 404 // special case: point lies somewhere else on the line 405 } else if (Math.abs(Mat.innerProduct(C, line.stdform, 3)) < Mat.eps) { 406 x = C[1] + B[2] - C[2]; 407 y = C[2] - B[1] + C[1]; 408 z = B[0]; 409 410 if (Math.abs(z) < Mat.eps) { 411 x = B[2]; 412 y = -B[1]; 413 } 414 415 change = true; 416 if ( 417 Math.abs(z) > Mat.eps && 418 Math.abs(x - C[1]) < Mat.eps && 419 Math.abs(y - C[2]) < Mat.eps 420 ) { 421 x = C[1] + A[2] - C[2]; 422 y = C[2] - A[1] + C[1]; 423 change = false; 424 } 425 c = [z, x, y]; 426 427 // general case: point does not lie on the line 428 // -> calculate the foot of the dropped perpendicular 429 } else { 430 c = [0, line.stdform[1], line.stdform[2]]; 431 c = Mat.crossProduct(c, C); // perpendicuar to line 432 c = Mat.crossProduct(c, line.stdform); // intersection of line and perpendicular 433 change = true; 434 } 435 436 return [new Coords(Const.COORDS_BY_USER, c, board), change]; 437 }, 438 439 /** 440 * @deprecated Please use {@link JXG.Math.Geometry.circumcenter} instead. 441 */ 442 circumcenterMidpoint: function () { 443 JXG.deprecated("Geometry.circumcenterMidpoint()", "Geometry.circumcenter()"); 444 this.circumcenter.apply(this, arguments); 445 }, 446 447 /** 448 * Calculates the center of the circumcircle of the three given points. 449 * @param {JXG.Point} point1 Point 450 * @param {JXG.Point} point2 Point 451 * @param {JXG.Point} point3 Point 452 * @param {JXG.Board} [board=point1.board] Reference to the board 453 * @returns {JXG.Coords} Coordinates of the center of the circumcircle of the given points. 454 */ 455 circumcenter: function (point1, point2, point3, board) { 456 var u, 457 v, 458 m1, 459 m2, 460 A = point1.coords.usrCoords, 461 B = point2.coords.usrCoords, 462 C = point3.coords.usrCoords; 463 464 if (!Type.exists(board)) { 465 board = point1.board; 466 } 467 468 u = [B[0] - A[0], -B[2] + A[2], B[1] - A[1]]; 469 v = [(A[0] + B[0]) * 0.5, (A[1] + B[1]) * 0.5, (A[2] + B[2]) * 0.5]; 470 m1 = Mat.crossProduct(u, v); 471 472 u = [C[0] - B[0], -C[2] + B[2], C[1] - B[1]]; 473 v = [(B[0] + C[0]) * 0.5, (B[1] + C[1]) * 0.5, (B[2] + C[2]) * 0.5]; 474 m2 = Mat.crossProduct(u, v); 475 476 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(m1, m2), board); 477 }, 478 479 /** 480 * Calculates the Euclidean distance for two given arrays of the same length. 481 * @param {Array} array1 Array of Number 482 * @param {Array} array2 Array of Number 483 * @param {Number} [n] Length of the arrays. Default is the minimum length of the given arrays. 484 * @returns {Number} Euclidean distance of the given vectors. 485 */ 486 distance: function (array1, array2, n) { 487 var i, 488 sum = 0; 489 490 if (!n) { 491 n = Math.min(array1.length, array2.length); 492 } 493 494 for (i = 0; i < n; i++) { 495 sum += (array1[i] - array2[i]) * (array1[i] - array2[i]); 496 } 497 498 return Math.sqrt(sum); 499 }, 500 501 /** 502 * Calculates Euclidean distance for two given arrays of the same length. 503 * If one of the arrays contains a zero in the first coordinate, and the Euclidean distance 504 * is different from zero it is a point at infinity and we return Infinity. 505 * @param {Array} array1 Array containing elements of type number. 506 * @param {Array} array2 Array containing elements of type number. 507 * @param {Number} [n] Length of the arrays. Default is the minimum length of the given arrays. 508 * @returns {Number} Euclidean (affine) distance of the given vectors. 509 */ 510 affineDistance: function (array1, array2, n) { 511 var d; 512 513 d = this.distance(array1, array2, n); 514 515 if ( 516 d > Mat.eps && 517 (Math.abs(array1[0]) < Mat.eps || Math.abs(array2[0]) < Mat.eps) 518 ) { 519 return Infinity; 520 } 521 522 return d; 523 }, 524 525 /** 526 * Affine ratio of three collinear points a, b, c: (c - a) / (b - a). 527 * If r > 1 or r < 0 then c is outside of the segment ab. 528 * 529 * @param {Array|JXG.Coords} a 530 * @param {Array|JXG.Coords} b 531 * @param {Array|JXG.Coords} c 532 * @returns {Number} affine ratio (c - a) / (b - a) 533 */ 534 affineRatio: function (a, b, c) { 535 var r = 0.0, 536 dx; 537 538 if (Type.exists(a.usrCoords)) { 539 a = a.usrCoords; 540 } 541 if (Type.exists(b.usrCoords)) { 542 b = b.usrCoords; 543 } 544 if (Type.exists(c.usrCoords)) { 545 c = c.usrCoords; 546 } 547 548 dx = b[1] - a[1]; 549 550 if (Math.abs(dx) > Mat.eps) { 551 r = (c[1] - a[1]) / dx; 552 } else { 553 r = (c[2] - a[2]) / (b[2] - a[2]); 554 } 555 return r; 556 }, 557 558 /** 559 * Sort vertices counter clockwise starting with the first point. 560 * 561 * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 562 * 563 * @returns {Array} 564 */ 565 sortVertices: function (p) { 566 var ll, 567 ps = Expect.each(p, Expect.coordsArray), 568 N = ps.length, 569 lastPoint = null; 570 571 // If the last point equals the first point, we take the last point out of the array. 572 // It may be that the several points at the end of the array are equal to the first point. 573 // The polygonal chain is been closed by JSXGraph, but this may also have been done by the user. 574 // Therefore, we use a while lopp to pop the last points. 575 while ( 576 ps[0][0] === ps[N - 1][0] && 577 ps[0][1] === ps[N - 1][1] && 578 ps[0][2] === ps[N - 1][2] 579 ) { 580 lastPoint = ps.pop(); 581 N--; 582 } 583 // Find the point with the lowest y value 584 // for (i = 1; i < N; i++) { 585 // if ((ps[i][2] < ps[0][2]) || 586 // // if the current and the lowest point have the same y value, pick the one with 587 // // the lowest x value. 588 // (Math.abs(ps[i][2] - ps[0][2]) < Mat.eps && ps[i][1] < ps[0][1])) { 589 // console.log(i, 0); 590 // ps = Type.swap(ps, i, 0); 591 // } 592 // } 593 594 ll = ps[0]; 595 // Sort ps in increasing order of the angle between a point and the first point ll. 596 // If a point is equal to the first point ll, the angle is defined to be -Infinity. 597 // Otherwise, atan2 would return zero, which is a value which also attained by points 598 // on the same horizontal line. 599 ps.sort(function (a, b) { 600 var rad1 = 601 a[2] === ll[2] && a[1] === ll[1] 602 ? -Infinity 603 : Math.atan2(a[2] - ll[2], a[1] - ll[1]), 604 rad2 = 605 b[2] === ll[2] && b[1] === ll[1] 606 ? -Infinity 607 : Math.atan2(b[2] - ll[2], b[1] - ll[1]); 608 609 return rad1 - rad2; 610 }); 611 612 // If the last point has been taken out of the array, we put it in again. 613 if (lastPoint !== null) { 614 ps.push(lastPoint); 615 } 616 617 return ps; 618 }, 619 620 /** 621 * Signed triangle area of the three points given. 622 * 623 * @param {JXG.Point|JXG.Coords|Array} p1 624 * @param {JXG.Point|JXG.Coords|Array} p2 625 * @param {JXG.Point|JXG.Coords|Array} p3 626 * 627 * @returns {Number} 628 */ 629 signedTriangle: function (p1, p2, p3) { 630 var A = Expect.coordsArray(p1), 631 B = Expect.coordsArray(p2), 632 C = Expect.coordsArray(p3); 633 634 return 0.5 * ((B[1] - A[1]) * (C[2] - A[2]) - (B[2] - A[2]) * (C[1] - A[1])); 635 }, 636 637 /** 638 * Determine the signed area of a non-selfintersecting polygon. 639 * Surveyor's Formula 640 * 641 * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 642 * @param {Boolean} [sort=true] 643 * 644 * @returns {Number} 645 */ 646 signedPolygon: function (p, sort) { 647 var i, 648 N, 649 A = 0, 650 ps = Expect.each(p, Expect.coordsArray); 651 652 if (sort === undefined) { 653 sort = true; 654 } 655 656 if (!sort) { 657 ps = this.sortVertices(ps); 658 } else { 659 // Make sure the polygon is closed. If it is already closed this won't change the sum because the last 660 // summand will be 0. 661 ps.unshift(ps[ps.length - 1]); 662 } 663 664 N = ps.length; 665 666 for (i = 1; i < N; i++) { 667 A += ps[i - 1][1] * ps[i][2] - ps[i][1] * ps[i - 1][2]; 668 } 669 670 return 0.5 * A; 671 }, 672 673 /** 674 * Calculate the complex hull of a point cloud. 675 * 676 * @param {Array} points An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 677 * 678 * @returns {Array} 679 */ 680 GrahamScan: function (points) { 681 var i, 682 M = 1, 683 ps = Expect.each(points, Expect.coordsArray), 684 N = ps.length; 685 686 ps = this.sortVertices(ps); 687 N = ps.length; 688 689 for (i = 2; i < N; i++) { 690 while (this.signedTriangle(ps[M - 1], ps[M], ps[i]) <= 0) { 691 if (M > 1) { 692 M -= 1; 693 } else if (i === N - 1) { 694 break; 695 } 696 i += 1; 697 } 698 699 M += 1; 700 ps = Type.swap(ps, M, i); 701 } 702 703 return ps.slice(0, M); 704 }, 705 706 /** 707 * A line can be a segment, a straight, or a ray. So it is not always delimited by point1 and point2 708 * calcStraight determines the visual start point and end point of the line. A segment is only drawn 709 * from start to end point, a straight line is drawn until it meets the boards boundaries. 710 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 711 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and 712 * set by this method. 713 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set 714 * by this method. 715 * @param {Number} margin Optional margin, to avoid the display of the small sides of lines. 716 * @returns null 717 * @see Line 718 * @see JXG.Line 719 */ 720 calcStraight: function (el, point1, point2, margin) { 721 var takePoint1, 722 takePoint2, 723 intersection, 724 intersect1, 725 intersect2, 726 straightFirst, 727 straightLast, 728 c, p1, p2; 729 730 if (!Type.exists(margin)) { 731 // Enlarge the drawable region slightly. This hides the small sides 732 // of thick lines in most cases. 733 margin = 10; 734 } 735 736 straightFirst = Type.evaluate(el.visProp.straightfirst); 737 straightLast = Type.evaluate(el.visProp.straightlast); 738 739 // If one of the point is an ideal point in homogeneous coordinates 740 // drawing of line segments or rays are not possible. 741 if (Math.abs(point1.scrCoords[0]) < Mat.eps) { 742 straightFirst = true; 743 } 744 if (Math.abs(point2.scrCoords[0]) < Mat.eps) { 745 straightLast = true; 746 } 747 748 // Do nothing in case of line segments (inside or outside of the board) 749 if (!straightFirst && !straightLast) { 750 return; 751 } 752 753 // Compute the stdform of the line in screen coordinates. 754 c = []; 755 c[0] = 756 el.stdform[0] - 757 (el.stdform[1] * el.board.origin.scrCoords[1]) / el.board.unitX + 758 (el.stdform[2] * el.board.origin.scrCoords[2]) / el.board.unitY; 759 c[1] = el.stdform[1] / el.board.unitX; 760 c[2] = -el.stdform[2] / el.board.unitY; 761 762 // If p1=p2 763 if (isNaN(c[0] + c[1] + c[2])) { 764 return; 765 } 766 767 takePoint1 = false; 768 takePoint2 = false; 769 770 // Line starts at point1 and point1 is inside the board 771 takePoint1 = 772 !straightFirst && 773 Math.abs(point1.usrCoords[0]) >= Mat.eps && 774 point1.scrCoords[1] >= 0.0 && 775 point1.scrCoords[1] <= el.board.canvasWidth && 776 point1.scrCoords[2] >= 0.0 && 777 point1.scrCoords[2] <= el.board.canvasHeight; 778 779 // Line ends at point2 and point2 is inside the board 780 takePoint2 = 781 !straightLast && 782 Math.abs(point2.usrCoords[0]) >= Mat.eps && 783 point2.scrCoords[1] >= 0.0 && 784 point2.scrCoords[1] <= el.board.canvasWidth && 785 point2.scrCoords[2] >= 0.0 && 786 point2.scrCoords[2] <= el.board.canvasHeight; 787 788 // Intersect the line with the four borders of the board. 789 intersection = this.meetLineBoard(c, el.board, margin); 790 intersect1 = intersection[0]; 791 intersect2 = intersection[1]; 792 793 /** 794 * At this point we have four points: 795 * point1 and point2 are the first and the second defining point on the line, 796 * intersect1, intersect2 are the intersections of the line with border around the board. 797 */ 798 799 /* 800 * Here we handle rays where both defining points are outside of the board. 801 */ 802 // If both points are outside and the complete ray is outside we do nothing 803 if (!takePoint1 && !takePoint2) { 804 // Ray starting at point 1 805 if ( 806 !straightFirst && 807 straightLast && 808 !this.isSameDirection(point1, point2, intersect1) && 809 !this.isSameDirection(point1, point2, intersect2) 810 ) { 811 return; 812 } 813 814 // Ray starting at point 2 815 if ( 816 straightFirst && 817 !straightLast && 818 !this.isSameDirection(point2, point1, intersect1) && 819 !this.isSameDirection(point2, point1, intersect2) 820 ) { 821 return; 822 } 823 } 824 825 /* 826 * If at least one of the defining points is outside of the board 827 * we take intersect1 or intersect2 as one of the end points 828 * The order is also important for arrows of axes 829 */ 830 if (!takePoint1) { 831 if (!takePoint2) { 832 // Two border intersection points are used 833 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 834 p1 = intersect1; 835 p2 = intersect2; 836 } else { 837 p2 = intersect1; 838 p1 = intersect2; 839 } 840 } else { 841 // One border intersection points is used 842 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 843 p1 = intersect1; 844 } else { 845 p1 = intersect2; 846 } 847 } 848 } else { 849 if (!takePoint2) { 850 // One border intersection points is used 851 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 852 p2 = intersect2; 853 } else { 854 p2 = intersect1; 855 } 856 } 857 } 858 859 if (p1) { 860 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1)); 861 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords); 862 } 863 864 if (p2) { 865 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1)); 866 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords); 867 } 868 }, 869 870 /** 871 * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2. 872 * 873 * This method adjusts the line's delimiting points taking into account its nature, the viewport defined 874 * by the board. 875 * 876 * A segment is delimited by start and end point, a straight line or ray is delimited until it meets the 877 * boards boundaries. However, if the line has infinite ticks, it will be delimited by the projection of 878 * the boards vertices onto itself. 879 * 880 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 881 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and 882 * set by this method. 883 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set 884 * by this method. 885 * @see Line 886 * @see JXG.Line 887 */ 888 calcLineDelimitingPoints: function (el, point1, point2) { 889 var distP1P2, 890 boundingBox, 891 lineSlope, 892 intersect1, 893 intersect2, 894 straightFirst, 895 straightLast, 896 c, 897 p1, 898 p2, 899 takePoint1 = false, 900 takePoint2 = false; 901 902 straightFirst = Type.evaluate(el.visProp.straightfirst); 903 straightLast = Type.evaluate(el.visProp.straightlast); 904 905 // If one of the point is an ideal point in homogeneous coordinates 906 // drawing of line segments or rays are not possible. 907 if (Math.abs(point1.scrCoords[0]) < Mat.eps) { 908 straightFirst = true; 909 } 910 if (Math.abs(point2.scrCoords[0]) < Mat.eps) { 911 straightLast = true; 912 } 913 914 // Compute the stdform of the line in screen coordinates. 915 c = []; 916 c[0] = 917 el.stdform[0] - 918 (el.stdform[1] * el.board.origin.scrCoords[1]) / el.board.unitX + 919 (el.stdform[2] * el.board.origin.scrCoords[2]) / el.board.unitY; 920 c[1] = el.stdform[1] / el.board.unitX; 921 c[2] = -el.stdform[2] / el.board.unitY; 922 923 // p1=p2 924 if (isNaN(c[0] + c[1] + c[2])) { 925 return; 926 } 927 928 takePoint1 = !straightFirst; 929 takePoint2 = !straightLast; 930 // Intersect the board vertices on the line to establish the available visual space for the infinite ticks 931 // Based on the slope of the line we can optimise and only project the two outer vertices 932 933 // boundingBox = [x1, y1, x2, y2] upper left, lower right vertices 934 boundingBox = el.board.getBoundingBox(); 935 lineSlope = el.getSlope(); 936 if (lineSlope >= 0) { 937 // project vertices (x2,y1) (x1, y2) 938 intersect1 = this.projectPointToLine( 939 { coords: { usrCoords: [1, boundingBox[2], boundingBox[1]] } }, 940 el, 941 el.board 942 ); 943 intersect2 = this.projectPointToLine( 944 { coords: { usrCoords: [1, boundingBox[0], boundingBox[3]] } }, 945 el, 946 el.board 947 ); 948 } else { 949 // project vertices (x1, y1) (x2, y2) 950 intersect1 = this.projectPointToLine( 951 { coords: { usrCoords: [1, boundingBox[0], boundingBox[1]] } }, 952 el, 953 el.board 954 ); 955 intersect2 = this.projectPointToLine( 956 { coords: { usrCoords: [1, boundingBox[2], boundingBox[3]] } }, 957 el, 958 el.board 959 ); 960 } 961 962 /** 963 * we have four points: 964 * point1 and point2 are the first and the second defining point on the line, 965 * intersect1, intersect2 are the intersections of the line with border around the board. 966 */ 967 968 /* 969 * Here we handle rays/segments where both defining points are outside of the board. 970 */ 971 if (!takePoint1 && !takePoint2) { 972 // Segment, if segment does not cross the board, do nothing 973 if (!straightFirst && !straightLast) { 974 distP1P2 = point1.distance(Const.COORDS_BY_USER, point2); 975 // if intersect1 not between point1 and point2 976 if ( 977 Math.abs( 978 point1.distance(Const.COORDS_BY_USER, intersect1) + 979 intersect1.distance(Const.COORDS_BY_USER, point2) - 980 distP1P2 981 ) > Mat.eps 982 ) { 983 return; 984 } 985 // if insersect2 not between point1 and point2 986 if ( 987 Math.abs( 988 point1.distance(Const.COORDS_BY_USER, intersect2) + 989 intersect2.distance(Const.COORDS_BY_USER, point2) - 990 distP1P2 991 ) > Mat.eps 992 ) { 993 return; 994 } 995 } 996 997 // If both points are outside and the complete ray is outside we do nothing 998 // Ray starting at point 1 999 if ( 1000 !straightFirst && 1001 straightLast && 1002 !this.isSameDirection(point1, point2, intersect1) && 1003 !this.isSameDirection(point1, point2, intersect2) 1004 ) { 1005 return; 1006 } 1007 1008 // Ray starting at point 2 1009 if ( 1010 straightFirst && 1011 !straightLast && 1012 !this.isSameDirection(point2, point1, intersect1) && 1013 !this.isSameDirection(point2, point1, intersect2) 1014 ) { 1015 return; 1016 } 1017 } 1018 1019 /* 1020 * If at least one of the defining points is outside of the board 1021 * we take intersect1 or intersect2 as one of the end points 1022 * The order is also important for arrows of axes 1023 */ 1024 if (!takePoint1) { 1025 if (!takePoint2) { 1026 // Two border intersection points are used 1027 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 1028 p1 = intersect1; 1029 p2 = intersect2; 1030 } else { 1031 p2 = intersect1; 1032 p1 = intersect2; 1033 } 1034 } else { 1035 // One border intersection points is used 1036 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 1037 p1 = intersect1; 1038 } else { 1039 p1 = intersect2; 1040 } 1041 } 1042 } else { 1043 if (!takePoint2) { 1044 // One border intersection points is used 1045 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 1046 p2 = intersect2; 1047 } else { 1048 p2 = intersect1; 1049 } 1050 } 1051 } 1052 1053 if (p1) { 1054 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1)); 1055 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords); 1056 } 1057 1058 if (p2) { 1059 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1)); 1060 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords); 1061 } 1062 }, 1063 1064 /** 1065 * Calculates the visProp.position corresponding to a given angle. 1066 * @param {number} angle angle in radians. Must be in range (-2pi,2pi). 1067 */ 1068 calcLabelQuadrant: function (angle) { 1069 var q; 1070 if (angle < 0) { 1071 angle += 2 * Math.PI; 1072 } 1073 q = Math.floor((angle + Math.PI / 8) / (Math.PI / 4)) % 8; 1074 return ["rt", "urt", "top", "ulft", "lft", "llft", "lrt"][q]; 1075 }, 1076 1077 /** 1078 * The vectors <tt>p2-p1</tt> and <tt>i2-i1</tt> are supposed to be collinear. If their cosine is positive 1079 * they point into the same direction otherwise they point in opposite direction. 1080 * @param {JXG.Coords} p1 1081 * @param {JXG.Coords} p2 1082 * @param {JXG.Coords} i1 1083 * @param {JXG.Coords} i2 1084 * @returns {Boolean} True, if <tt>p2-p1</tt> and <tt>i2-i1</tt> point into the same direction 1085 */ 1086 isSameDir: function (p1, p2, i1, i2) { 1087 var dpx = p2.usrCoords[1] - p1.usrCoords[1], 1088 dpy = p2.usrCoords[2] - p1.usrCoords[2], 1089 dix = i2.usrCoords[1] - i1.usrCoords[1], 1090 diy = i2.usrCoords[2] - i1.usrCoords[2]; 1091 1092 if (Math.abs(p2.usrCoords[0]) < Mat.eps) { 1093 dpx = p2.usrCoords[1]; 1094 dpy = p2.usrCoords[2]; 1095 } 1096 1097 if (Math.abs(p1.usrCoords[0]) < Mat.eps) { 1098 dpx = -p1.usrCoords[1]; 1099 dpy = -p1.usrCoords[2]; 1100 } 1101 1102 return dpx * dix + dpy * diy >= 0; 1103 }, 1104 1105 /** 1106 * If you're looking from point "start" towards point "s" and you can see the point "p", return true. 1107 * Otherwise return false. 1108 * @param {JXG.Coords} start The point you're standing on. 1109 * @param {JXG.Coords} p The point in which direction you're looking. 1110 * @param {JXG.Coords} s The point that should be visible. 1111 * @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. 1112 */ 1113 isSameDirection: function (start, p, s) { 1114 var dx, 1115 dy, 1116 sx, 1117 sy, 1118 r = false; 1119 1120 dx = p.usrCoords[1] - start.usrCoords[1]; 1121 dy = p.usrCoords[2] - start.usrCoords[2]; 1122 1123 sx = s.usrCoords[1] - start.usrCoords[1]; 1124 sy = s.usrCoords[2] - start.usrCoords[2]; 1125 1126 if (Math.abs(dx) < Mat.eps) { 1127 dx = 0; 1128 } 1129 1130 if (Math.abs(dy) < Mat.eps) { 1131 dy = 0; 1132 } 1133 1134 if (Math.abs(sx) < Mat.eps) { 1135 sx = 0; 1136 } 1137 1138 if (Math.abs(sy) < Mat.eps) { 1139 sy = 0; 1140 } 1141 1142 if (dx >= 0 && sx >= 0) { 1143 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0); 1144 } else if (dx <= 0 && sx <= 0) { 1145 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0); 1146 } 1147 1148 return r; 1149 }, 1150 1151 /** 1152 * Determinant of three points in the Euclidean plane. 1153 * Zero, if the points are collinear. Used to determine of a point q is left or 1154 * right to a segment defined by points p1 and p2. 1155 * 1156 * @param {Array} p1 Coordinates of the first point of the segment. Array of length 3. First coordinate is equal to 1. 1157 * @param {Array} p2 Coordinates of the second point of the segment. Array of length 3. First coordinate is equal to 1. 1158 * @param {Array} q Coordinates of the point. Array of length 3. First coordinate is equal to 1. 1159 * @return {Number} Signed area of the triangle formed by these three points. 1160 * 1161 * @see #windingNumber 1162 */ 1163 det3p: function (p1, p2, q) { 1164 return (p1[1] - q[1]) * (p2[2] - q[2]) - (p2[1] - q[1]) * (p1[2] - q[2]); 1165 }, 1166 1167 /** 1168 * Winding number of a point in respect to a polygon path. 1169 * 1170 * The point is regarded outside if the winding number is zero, 1171 * inside otherwise. The algorithm tries to find degenerate cases, i.e. 1172 * if the point is on the path. This is regarded as "outside". 1173 * If the point is a vertex of the path, it is regarded as "inside". 1174 * 1175 * Implementation of algorithm 7 from "The point in polygon problem for 1176 * arbitrary polygons" by Kai Hormann and Alexander Agathos, Computational Geometry, 1177 * Volume 20, Issue 3, November 2001, Pages 131-144. 1178 * 1179 * @param {Array} usrCoords Homogenous coordinates of the point 1180 * @param {Array} path Array of points / coords determining a path, i.e. the vertices of the polygon / path. The array elements 1181 * do not have to be full points, but have to have a subobject "coords" or should be of type JXG.Coords. 1182 * @param {Boolean} [doNotClosePath=false] If true the last point of the path is not connected to the first point. 1183 * This is necessary if the path consists of two or more closed subpaths, e.g. if the figure has a hole. 1184 * 1185 * @return {Number} Winding number of the point. The point is 1186 * regarded outside if the winding number is zero, 1187 * inside otherwise. 1188 */ 1189 windingNumber: function (usrCoords, path, doNotClosePath) { 1190 var wn = 0, 1191 le = path.length, 1192 x = usrCoords[1], 1193 y = usrCoords[2], 1194 p0, 1195 p1, 1196 p2, 1197 d, 1198 sign, 1199 i, 1200 off = 0; 1201 1202 if (le === 0) { 1203 return 0; 1204 } 1205 1206 doNotClosePath = doNotClosePath || false; 1207 if (doNotClosePath) { 1208 off = 1; 1209 } 1210 1211 // Infinite points are declared outside 1212 if (isNaN(x) || isNaN(y)) { 1213 return 1; 1214 } 1215 1216 if (Type.exists(path[0].coords)) { 1217 p0 = path[0].coords; 1218 p1 = path[le - 1].coords; 1219 } else { 1220 p0 = path[0]; 1221 p1 = path[le - 1]; 1222 } 1223 // Handle the case if the point is the first vertex of the path, i.e. inside. 1224 if (p0.usrCoords[1] === x && p0.usrCoords[2] === y) { 1225 return 1; 1226 } 1227 1228 for (i = 0; i < le - off; i++) { 1229 // Consider the edge from p1 = path[i] to p2 = path[i+1]isClosedPath 1230 if (Type.exists(path[i].coords)) { 1231 p1 = path[i].coords.usrCoords; 1232 p2 = path[(i + 1) % le].coords.usrCoords; 1233 } else { 1234 p1 = path[i].usrCoords; 1235 p2 = path[(i + 1) % le].usrCoords; 1236 } 1237 1238 // If one of the two points p1, p2 is undefined or infinite, 1239 // move on. 1240 if ( 1241 p1[0] === 0 || 1242 p2[0] === 0 || 1243 isNaN(p1[1]) || 1244 isNaN(p2[1]) || 1245 isNaN(p1[2]) || 1246 isNaN(p2[2]) 1247 ) { 1248 continue; 1249 } 1250 1251 if (p2[2] === y) { 1252 if (p2[1] === x) { 1253 return 1; 1254 } 1255 if (p1[2] === y && p2[1] > x === p1[1] < x) { 1256 return 0; 1257 } 1258 } 1259 1260 if (p1[2] < y !== p2[2] < y) { 1261 // Crossing 1262 sign = 2 * (p2[2] > p1[2] ? 1 : 0) - 1; 1263 if (p1[1] >= x) { 1264 if (p2[1] > x) { 1265 wn += sign; 1266 } else { 1267 d = this.det3p(p1, p2, usrCoords); 1268 if (d === 0) { 1269 // Point is on line, i.e. outside 1270 return 0; 1271 } 1272 if (d > 0 + Mat.eps === p2[2] > p1[2]) { 1273 // Right crossing 1274 wn += sign; 1275 } 1276 } 1277 } else { 1278 if (p2[1] > x) { 1279 d = this.det3p(p1, p2, usrCoords); 1280 if (d > 0 + Mat.eps === p2[2] > p1[2]) { 1281 // Right crossing 1282 wn += sign; 1283 } 1284 } 1285 } 1286 } 1287 } 1288 1289 return wn; 1290 }, 1291 1292 /** 1293 * Decides if a point (x,y) is inside of a path / polygon. 1294 * Does not work correct if the path has hole. In this case, windingNumber is the preferred method. 1295 * Implements W. Randolf Franklin's pnpoly method. 1296 * 1297 * See <a href="https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html">https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html</a>. 1298 * 1299 * @param {Number} x_in x-coordinate (screen or user coordinates) 1300 * @param {Number} y_in y-coordinate (screen or user coordinates) 1301 * @param {Array} path Array of points / coords determining a path, i.e. the vertices of the polygon / path. The array elements 1302 * do not have to be full points, but have to have a subobject "coords" or should be of type JXG.Coords. 1303 * @param {Number} [coord_type=JXG.COORDS_BY_SCREEN] Type of coordinates used here. 1304 * Possible values are <b>JXG.COORDS_BY_USER</b> and <b>JXG.COORDS_BY_SCREEN</b>. 1305 * Default value is JXG.COORDS_BY_SCREEN. 1306 * 1307 * @returns {Boolean} if (x_in, y_in) is inside of the polygon. 1308 * @see JXG.Polygon.hasPoint 1309 * @see JXG.Polygon.pnpoly 1310 * @see #windingNumber 1311 * 1312 * @example 1313 * var pol = board.create('polygon', [[-1,2], [2,2], [-1,4]]); 1314 * var p = board.create('point', [4, 3]); 1315 * var txt = board.create('text', [-1, 0.5, function() { 1316 * return 'Point A is inside of the polygon = ' + 1317 * JXG.Math.Geometry.pnpoly(p.X(), p.Y(), JXG.COORDS_BY_USER, pol.vertices); 1318 * }]); 1319 * 1320 * </pre><div id="JXG4656ed42-f965-4e35-bb66-c334a4529683" class="jxgbox" style="width: 300px; height: 300px;"></div> 1321 * <script type="text/javascript"> 1322 * (function() { 1323 * var board = JXG.JSXGraph.initBoard('JXG4656ed42-f965-4e35-bb66-c334a4529683', 1324 * {boundingbox: [-2, 5, 5,-2], axis: true, showcopyright: false, shownavigation: false}); 1325 * var pol = board.create('polygon', [[-1,2], [2,2], [-1,4]]); 1326 * var p = board.create('point', [4, 3]); 1327 * var txt = board.create('text', [-1, 0.5, function() { 1328 * return 'Point A is inside of the polygon = ' + JXG.Math.Geometry.pnpoly(p.X(), p.Y(), JXG.COORDS_BY_USER, pol.vertices); 1329 * }]); 1330 * 1331 * })(); 1332 * 1333 * </script><pre> 1334 * 1335 */ 1336 pnpoly: function (x_in, y_in, path, coord_type) { 1337 var i, j, vi, vj, len, 1338 x, y, crds, 1339 v = path, 1340 isIn = false; 1341 1342 if (coord_type === Const.COORDS_BY_USER) { 1343 crds = new Coords(Const.COORDS_BY_USER, [x_in, y_in], this.board); 1344 x = crds.scrCoords[1]; 1345 y = crds.scrCoords[2]; 1346 } else { 1347 x = x_in; 1348 y = y_in; 1349 } 1350 1351 len = path.length; 1352 for (i = 0, j = len - 2; i < len - 1; j = i++) { 1353 vi = Type.exists(v[i].coords) ? v[i].coords : v[i]; 1354 vj = Type.exists(v[j].coords) ? v[j].coords : v[j]; 1355 1356 if ( 1357 vi.scrCoords[2] > y !== vj.scrCoords[2] > y && 1358 x < 1359 ((vj.scrCoords[1] - vi.scrCoords[1]) * (y - vi.scrCoords[2])) / 1360 (vj.scrCoords[2] - vi.scrCoords[2]) + 1361 vi.scrCoords[1] 1362 ) { 1363 isIn = !isIn; 1364 } 1365 } 1366 1367 return isIn; 1368 }, 1369 1370 /****************************************/ 1371 /**** INTERSECTIONS ****/ 1372 /****************************************/ 1373 1374 /** 1375 * Generate the function which computes the coordinates of the intersection point. 1376 * Primarily used in {@link JXG.Point#createIntersectionPoint}. 1377 * @param {JXG.Board} board object 1378 * @param {JXG.Line,JXG.Circle_JXG.Line,JXG.Circle_Number|Function} el1,el2,i The result will be a intersection point on el1 and el2. 1379 * i determines the intersection point if two points are available: <ul> 1380 * <li>i==0: use the positive square root,</li> 1381 * <li>i==1: use the negative square root.</li></ul> 1382 * See further {@link JXG.Point#createIntersectionPoint}. 1383 * @param {Boolean} alwaysintersect. Flag that determines if segments and arc can have an outer intersection point 1384 * on their defining line or circle. 1385 * @returns {Function} Function returning a {@link JXG.Coords} object that determines 1386 * the intersection point. 1387 */ 1388 intersectionFunction: function (board, el1, el2, i, j, alwaysintersect) { 1389 var func, 1390 that = this, 1391 el1_isArcType = false, 1392 el2_isArcType = false; 1393 1394 el1_isArcType = 1395 el1.elementClass === Const.OBJECT_CLASS_CURVE && 1396 (el1.type === Const.OBJECT_TYPE_ARC || el1.type === Const.OBJECT_TYPE_SECTOR) 1397 ? true 1398 : false; 1399 el2_isArcType = 1400 el2.elementClass === Const.OBJECT_CLASS_CURVE && 1401 (el2.type === Const.OBJECT_TYPE_ARC || el2.type === Const.OBJECT_TYPE_SECTOR) 1402 ? true 1403 : false; 1404 1405 if ( 1406 (el1.elementClass === Const.OBJECT_CLASS_CURVE || 1407 el2.elementClass === Const.OBJECT_CLASS_CURVE) && 1408 (el1.elementClass === Const.OBJECT_CLASS_CURVE || 1409 el1.elementClass === Const.OBJECT_CLASS_CIRCLE) && 1410 (el2.elementClass === Const.OBJECT_CLASS_CURVE || 1411 el2.elementClass === Const.OBJECT_CLASS_CIRCLE) /*&& 1412 !(el1_isArcType && el2_isArcType)*/ 1413 ) { 1414 // curve - curve 1415 // with the exception that both elements are arc types 1416 /** @ignore */ 1417 func = function () { 1418 return that.meetCurveCurve(el1, el2, i, j, el1.board); 1419 }; 1420 } else if ( 1421 (el1.elementClass === Const.OBJECT_CLASS_CURVE && 1422 !el1_isArcType && 1423 el2.elementClass === Const.OBJECT_CLASS_LINE) || 1424 (el2.elementClass === Const.OBJECT_CLASS_CURVE && 1425 !el2_isArcType && 1426 el1.elementClass === Const.OBJECT_CLASS_LINE) 1427 ) { 1428 // curve - line (this includes intersections between conic sections and lines) 1429 // with the exception that the curve is of arc type 1430 /** @ignore */ 1431 func = function () { 1432 return that.meetCurveLine(el1, el2, i, el1.board, Type.evaluate(alwaysintersect)); 1433 }; 1434 } else if ( 1435 el1.type === Const.OBJECT_TYPE_POLYGON || 1436 el2.type === Const.OBJECT_TYPE_POLYGON 1437 ) { 1438 // polygon - other 1439 // Uses the Greiner-Hormann clipping algorithm 1440 // Not implemented: polygon - point 1441 1442 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1443 // line - path 1444 /** @ignore */ 1445 func = function () { 1446 var first1 = Type.evaluate(el1.visProp.straightfirst), 1447 last1 = Type.evaluate(el1.visProp.straightlast), 1448 first2 = Type.evaluate(el2.visProp.straightfirst), 1449 last2 = Type.evaluate(el2.visProp.straightlast), 1450 a_not; 1451 1452 a_not = (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)); 1453 return that.meetPolygonLine(el2, el1, i, el1.board, a_not); 1454 }; 1455 } else if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1456 // path - line 1457 func = function () { 1458 var first1 = Type.evaluate(el1.visProp.straightfirst), 1459 last1 = Type.evaluate(el1.visProp.straightlast), 1460 first2 = Type.evaluate(el2.visProp.straightfirst), 1461 last2 = Type.evaluate(el2.visProp.straightlast), 1462 a_not; 1463 1464 a_not = (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)); 1465 return that.meetPolygonLine(el1, el2, i, el1.board, a_not); 1466 }; 1467 } else { 1468 // path - path 1469 /** @ignore */ 1470 func = function () { 1471 return that.meetPathPath(el1, el2, i, el1.board); 1472 }; 1473 } 1474 } else if ( 1475 el1.elementClass === Const.OBJECT_CLASS_LINE && 1476 el2.elementClass === Const.OBJECT_CLASS_LINE 1477 ) { 1478 // line - line, lines may also be segments. 1479 /** @ignore */ 1480 func = function () { 1481 var res, 1482 c, 1483 first1 = Type.evaluate(el1.visProp.straightfirst), 1484 last1 = Type.evaluate(el1.visProp.straightlast), 1485 first2 = Type.evaluate(el2.visProp.straightfirst), 1486 last2 = Type.evaluate(el2.visProp.straightlast); 1487 1488 /** 1489 * If one of the lines is a segment or ray and 1490 * the intersection point should disappear if outside 1491 * of the segment or ray we call 1492 * meetSegmentSegment 1493 */ 1494 if ( 1495 !Type.evaluate(alwaysintersect) && 1496 (!first1 || !last1 || !first2 || !last2) 1497 ) { 1498 res = that.meetSegmentSegment( 1499 el1.point1.coords.usrCoords, 1500 el1.point2.coords.usrCoords, 1501 el2.point1.coords.usrCoords, 1502 el2.point2.coords.usrCoords 1503 ); 1504 1505 if ( 1506 (!first1 && res[1] < 0) || 1507 (!last1 && res[1] > 1) || 1508 (!first2 && res[2] < 0) || 1509 (!last2 && res[2] > 1) 1510 ) { 1511 // Non-existent 1512 c = [0, NaN, NaN]; 1513 } else { 1514 c = res[0]; 1515 } 1516 1517 return new Coords(Const.COORDS_BY_USER, c, el1.board); 1518 } 1519 1520 return that.meet(el1.stdform, el2.stdform, i, el1.board); 1521 }; 1522 } else { 1523 // All other combinations of circles and lines, 1524 // Arc types are treated as circles. 1525 /** @ignore */ 1526 func = function () { 1527 var res = that.meet(el1.stdform, el2.stdform, i, el1.board), 1528 has = true, 1529 first, 1530 last, 1531 r; 1532 1533 if (Type.evaluate(alwaysintersect)) { 1534 return res; 1535 } 1536 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1537 first = Type.evaluate(el1.visProp.straightfirst); 1538 last = Type.evaluate(el1.visProp.straightlast); 1539 if (!first || !last) { 1540 r = that.affineRatio(el1.point1.coords, el1.point2.coords, res); 1541 if ((!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps)) { 1542 return new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board); 1543 } 1544 } 1545 } 1546 if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1547 first = Type.evaluate(el2.visProp.straightfirst); 1548 last = Type.evaluate(el2.visProp.straightlast); 1549 if (!first || !last) { 1550 r = that.affineRatio(el2.point1.coords, el2.point2.coords, res); 1551 if ((!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps)) { 1552 return new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board); 1553 } 1554 } 1555 } 1556 if (el1_isArcType) { 1557 has = that.coordsOnArc(el1, res); 1558 if (has && el2_isArcType) { 1559 has = that.coordsOnArc(el2, res); 1560 } 1561 if (!has) { 1562 return new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board); 1563 } 1564 } 1565 return res; 1566 }; 1567 } 1568 1569 return func; 1570 }, 1571 1572 otherIntersectionFunction: function (input, others, alwaysintersect, precision) { 1573 var func, board, 1574 el1, el2, 1575 that = this; 1576 1577 el1 = input[0]; 1578 el2 = input[1]; 1579 board = el1.board; 1580 func = function () { 1581 var i, k, c, d, 1582 isClose, 1583 le = others.length, 1584 eps = Type.evaluate(precision); 1585 1586 for (i = le; i >= 0; i--) { 1587 if (el1.elementClass === Const.OBJECT_CLASS_CIRCLE && 1588 [Const.OBJECT_CLASS_CIRCLE, Const.OBJECT_CLASS_LINE].indexOf(el2.elementClass) >= 0) { 1589 // circle, circle|line 1590 c = that.meet(el1.stdform, el2.stdform, i, board); 1591 } else if (el1.elementClass === Const.OBJECT_CLASS_CURVE && 1592 [Const.OBJECT_CLASS_CURVE, Const.OBJECT_CLASS_CIRCLE].indexOf(el2.elementClass) >= 0) { 1593 // curve, circle|curve 1594 c = that.meetCurveCurve(el1, el2, i, 0, board, 'segment'); 1595 } else if (el1.elementClass === Const.OBJECT_CLASS_CURVE && el2.elementClass === Const.OBJECT_CLASS_LINE) { 1596 // curve, line 1597 if (Type.exists(el1.dataX)) { 1598 c = JXG.Math.Geometry.meetCurveLine(el1, el2, i, el1.board, Type.evaluate(alwaysintersect)); 1599 } else { 1600 c = JXG.Math.Geometry.meetCurveLineContinuous(el1, el2, i, el1.board); 1601 } 1602 } 1603 1604 // If the intersection is close to one of the points in other 1605 // we have to search for another intersection point. 1606 isClose = false; 1607 for (k = 0; !isClose && k < le; k++) { 1608 d = c.distance(JXG.COORDS_BY_USER, others[k].coords); 1609 if (d < eps) { 1610 isClose = true; 1611 } 1612 } 1613 if (!isClose) { 1614 // We are done, the intersection is away from any other 1615 // intersection point. 1616 return c; 1617 } 1618 } 1619 // Otherwise we return the last intersection point 1620 return c; 1621 }; 1622 return func; 1623 }, 1624 1625 /** 1626 * Generate the function which computes the data of the intersection. 1627 */ 1628 intersectionFunction3D: function (view, el1, el2, i) { 1629 var func, 1630 that = this; 1631 1632 if (el1.type === Const.OBJECT_TYPE_PLANE3D) { 1633 if (el2.type === Const.OBJECT_TYPE_PLANE3D) { 1634 func = () => view.intersectionPlanePlane(el1, el2)[i]; 1635 } else if (el2.type === Const.OBJECT_TYPE_SPHERE3D) { 1636 func = that.meetPlaneSphere(el1, el2); 1637 } 1638 } else if (el1.type === Const.OBJECT_TYPE_SPHERE3D) { 1639 if (el2.type === Const.OBJECT_TYPE_PLANE3D) { 1640 func = that.meetPlaneSphere(el2, el1); 1641 } else if (el2.type === Const.OBJECT_TYPE_SPHERE3D) { 1642 func = that.meetSphereSphere(el1, el2); 1643 } 1644 } 1645 1646 return func; 1647 }, 1648 1649 /** 1650 * Returns true if the coordinates are on the arc element, 1651 * false otherwise. Usually, coords is an intersection 1652 * on the circle line. Now it is decided if coords are on the 1653 * circle restricted to the arc line. 1654 * @param {Arc} arc arc or sector element 1655 * @param {JXG.Coords} coords Coords object of an intersection 1656 * @returns {Boolean} 1657 * @private 1658 */ 1659 coordsOnArc: function (arc, coords) { 1660 var angle = this.rad(arc.radiuspoint, arc.center, coords.usrCoords.slice(1)), 1661 alpha = 0.0, 1662 beta = this.rad(arc.radiuspoint, arc.center, arc.anglepoint), 1663 ev_s = Type.evaluate(arc.visProp.selection); 1664 1665 if ((ev_s === "minor" && beta > Math.PI) || (ev_s === "major" && beta < Math.PI)) { 1666 alpha = beta; 1667 beta = 2 * Math.PI; 1668 } 1669 if (angle < alpha || angle > beta) { 1670 return false; 1671 } 1672 return true; 1673 }, 1674 1675 /** 1676 * Computes the intersection of a pair of lines, circles or both. 1677 * It uses the internal data array stdform of these elements. 1678 * @param {Array} el1 stdform of the first element (line or circle) 1679 * @param {Array} el2 stdform of the second element (line or circle) 1680 * @param {Number|Function} i Index of the intersection point that should be returned. 1681 * @param board Reference to the board. 1682 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 1683 * Which point will be returned is determined by i. 1684 */ 1685 meet: function (el1, el2, i, board) { 1686 var result, 1687 eps = Mat.eps; 1688 1689 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { 1690 // line line 1691 result = this.meetLineLine(el1, el2, i, board); 1692 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { 1693 // circle line 1694 result = this.meetLineCircle(el2, el1, i, board); 1695 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { 1696 // line circle 1697 result = this.meetLineCircle(el1, el2, i, board); 1698 } else { 1699 // circle circle 1700 result = this.meetCircleCircle(el1, el2, i, board); 1701 } 1702 1703 return result; 1704 }, 1705 1706 /** 1707 * Intersection of the line with the board 1708 * @param {Array} line stdform of the line in screen coordinates 1709 * @param {JXG.Board} board reference to a board. 1710 * @param {Number} margin optional margin, to avoid the display of the small sides of lines. 1711 * @returns {Array} [intersection coords 1, intersection coords 2] 1712 */ 1713 meetLineBoard: function (line, board, margin) { 1714 // Intersect the line with the four borders of the board. 1715 var s = [], 1716 intersect1, 1717 intersect2, 1718 i, j; 1719 1720 if (!Type.exists(margin)) { 1721 margin = 0; 1722 } 1723 1724 // top 1725 s[0] = Mat.crossProduct(line, [margin, 0, 1]); 1726 // left 1727 s[1] = Mat.crossProduct(line, [margin, 1, 0]); 1728 // bottom 1729 s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]); 1730 // right 1731 s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]); 1732 1733 // Normalize the intersections 1734 for (i = 0; i < 4; i++) { 1735 if (Math.abs(s[i][0]) > Mat.eps) { 1736 for (j = 2; j > 0; j--) { 1737 s[i][j] /= s[i][0]; 1738 } 1739 s[i][0] = 1.0; 1740 } 1741 } 1742 1743 // line is parallel to "left", take "top" and "bottom" 1744 if (Math.abs(s[1][0]) < Mat.eps) { 1745 intersect1 = s[0]; // top 1746 intersect2 = s[2]; // bottom 1747 // line is parallel to "top", take "left" and "right" 1748 } else if (Math.abs(s[0][0]) < Mat.eps) { 1749 intersect1 = s[1]; // left 1750 intersect2 = s[3]; // right 1751 // left intersection out of board (above) 1752 } else if (s[1][2] < 0) { 1753 intersect1 = s[0]; // top 1754 1755 // right intersection out of board (below) 1756 if (s[3][2] > board.canvasHeight) { 1757 intersect2 = s[2]; // bottom 1758 } else { 1759 intersect2 = s[3]; // right 1760 } 1761 // left intersection out of board (below) 1762 } else if (s[1][2] > board.canvasHeight) { 1763 intersect1 = s[2]; // bottom 1764 1765 // right intersection out of board (above) 1766 if (s[3][2] < 0) { 1767 intersect2 = s[0]; // top 1768 } else { 1769 intersect2 = s[3]; // right 1770 } 1771 } else { 1772 intersect1 = s[1]; // left 1773 1774 // right intersection out of board (above) 1775 if (s[3][2] < 0) { 1776 intersect2 = s[0]; // top 1777 // right intersection out of board (below) 1778 } else if (s[3][2] > board.canvasHeight) { 1779 intersect2 = s[2]; // bottom 1780 } else { 1781 intersect2 = s[3]; // right 1782 } 1783 } 1784 1785 return [ 1786 new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board), 1787 new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board) 1788 ]; 1789 }, 1790 1791 /** 1792 * Intersection of two lines. 1793 * @param {Array} l1 stdform of the first line 1794 * @param {Array} l2 stdform of the second line 1795 * @param {number} i unused 1796 * @param {JXG.Board} board Reference to the board. 1797 * @returns {JXG.Coords} Coordinates of the intersection point. 1798 */ 1799 meetLineLine: function (l1, l2, i, board) { 1800 var s = isNaN(l1[5] + l2[5]) ? [0, 0, 0] : Mat.crossProduct(l1, l2); 1801 1802 // Make intersection of parallel lines more robust: 1803 if (Math.abs(s[0]) < 1.0e-14) { 1804 s[0] = 0; 1805 } 1806 return new Coords(Const.COORDS_BY_USER, s, board); 1807 }, 1808 1809 /** 1810 * Intersection of line and circle. 1811 * @param {Array} lin stdform of the line 1812 * @param {Array} circ stdform of the circle 1813 * @param {number|function} i number of the returned intersection point. 1814 * i==0: use the positive square root, 1815 * i==1: use the negative square root. 1816 * @param {JXG.Board} board Reference to a board. 1817 * @returns {JXG.Coords} Coordinates of the intersection point 1818 */ 1819 meetLineCircle: function (lin, circ, i, board) { 1820 var a, b, c, d, n, A, B, C, k, t; 1821 1822 // Radius is zero, return center of circle 1823 if (circ[4] < Mat.eps) { 1824 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) { 1825 return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board); 1826 } 1827 1828 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board); 1829 } 1830 c = circ[0]; 1831 b = circ.slice(1, 3); 1832 a = circ[3]; 1833 d = lin[0]; 1834 n = lin.slice(1, 3); 1835 1836 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 1837 /* 1838 var nn = n[0]*n[0]+n[1]*n[1]; 1839 A = a*nn; 1840 B = (b[0]*n[1]-b[1]*n[0])*nn; 1841 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 1842 */ 1843 A = a; 1844 B = b[0] * n[1] - b[1] * n[0]; 1845 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 1846 1847 k = B * B - 4 * A * C; 1848 if (k > -Mat.eps * Mat.eps) { 1849 k = Math.sqrt(Math.abs(k)); 1850 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)]; 1851 1852 return Type.evaluate(i) === 0 1853 ? new Coords( 1854 Const.COORDS_BY_USER, 1855 [-t[0] * -n[1] - d * n[0], -t[0] * n[0] - d * n[1]], 1856 board 1857 ) 1858 : new Coords( 1859 Const.COORDS_BY_USER, 1860 [-t[1] * -n[1] - d * n[0], -t[1] * n[0] - d * n[1]], 1861 board 1862 ); 1863 } 1864 1865 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1866 }, 1867 1868 /** 1869 * Intersection of two circles. 1870 * @param {Array} circ1 stdform of the first circle 1871 * @param {Array} circ2 stdform of the second circle 1872 * @param {number|function} i number of the returned intersection point. 1873 * i==0: use the positive square root, 1874 * i==1: use the negative square root. 1875 * @param {JXG.Board} board Reference to the board. 1876 * @returns {JXG.Coords} Coordinates of the intersection point 1877 */ 1878 meetCircleCircle: function (circ1, circ2, i, board) { 1879 var radicalAxis; 1880 1881 // Radius is zero, return center of circle, if on other circle 1882 if (circ1[4] < Mat.eps) { 1883 if ( 1884 Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < 1885 Mat.eps 1886 ) { 1887 return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board); 1888 } 1889 1890 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1891 } 1892 1893 // Radius is zero, return center of circle, if on other circle 1894 if (circ2[4] < Mat.eps) { 1895 if ( 1896 Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < 1897 Mat.eps 1898 ) { 1899 return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board); 1900 } 1901 1902 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1903 } 1904 1905 radicalAxis = [ 1906 circ2[3] * circ1[0] - circ1[3] * circ2[0], 1907 circ2[3] * circ1[1] - circ1[3] * circ2[1], 1908 circ2[3] * circ1[2] - circ1[3] * circ2[2], 1909 0, 1910 1, 1911 Infinity, 1912 Infinity, 1913 Infinity 1914 ]; 1915 radicalAxis = Mat.normalize(radicalAxis); 1916 1917 return this.meetLineCircle(radicalAxis, circ1, i, board); 1918 }, 1919 1920 /** 1921 * Compute an intersection of the curves c1 and c2. 1922 * We want to find values t1, t2 such that 1923 * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 1924 * 1925 * Methods: segment-wise intersections (default) or generalized Newton method. 1926 * @param {JXG.Curve} c1 Curve, Line or Circle 1927 * @param {JXG.Curve} c2 Curve, Line or Circle 1928 * @param {Number|Function} nr the nr-th intersection point will be returned. 1929 * @param {Number} t2ini not longer used. 1930 * @param {JXG.Board} [board=c1.board] Reference to a board object. 1931 * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'. 1932 * @returns {JXG.Coords} intersection point 1933 */ 1934 meetCurveCurve: function (c1, c2, nr, t2ini, board, method) { 1935 var co; 1936 1937 if (Type.exists(method) && method === "newton") { 1938 co = Numerics.generalizedNewton(c1, c2, Type.evaluate(nr), t2ini); 1939 } else { 1940 if (c1.bezierDegree === 3 || c2.bezierDegree === 3) { 1941 co = this.meetBezierCurveRedBlueSegments(c1, c2, nr); 1942 } else { 1943 co = this.meetCurveRedBlueSegments(c1, c2, nr); 1944 } 1945 } 1946 1947 return new Coords(Const.COORDS_BY_USER, co, board); 1948 }, 1949 1950 /** 1951 * Intersection of curve with line, 1952 * Order of input does not matter for el1 and el2. 1953 * From version 0.99.7 on this method calls 1954 * {@link JXG.Math.Geometry.meetCurveLineDiscrete}. 1955 * If higher precision is needed, {@link JXG.Math.Geometry.meetCurveLineContinuous} 1956 * has to be used. 1957 * 1958 * @param {JXG.Curve|JXG.Line} el1 Curve or Line 1959 * @param {JXG.Curve|JXG.Line} el2 Curve or Line 1960 * @param {Number|Function} nr the nr-th intersection point will be returned. 1961 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1962 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection 1963 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1964 * the ideal point [0,1,0] is returned. 1965 */ 1966 meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) { 1967 var v = [0, NaN, NaN], 1968 cu, 1969 li; 1970 1971 if (!Type.exists(board)) { 1972 board = el1.board; 1973 } 1974 1975 if (el1.elementClass === Const.OBJECT_CLASS_CURVE) { 1976 cu = el1; 1977 li = el2; 1978 } else { 1979 cu = el2; 1980 li = el1; 1981 } 1982 1983 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect); 1984 1985 return v; 1986 }, 1987 1988 /** 1989 * Intersection of line and curve, continuous case. 1990 * Finds the nr-the intersection point 1991 * Uses {@link JXG.Math.Geometry.meetCurveLineDiscrete} as a first approximation. 1992 * A more exact solution is then found with {@link JXG.Math.Numerics.root}. 1993 * 1994 * @param {JXG.Curve} cu Curve 1995 * @param {JXG.Line} li Line 1996 * @param {NumberFunction} nr Will return the nr-th intersection point. 1997 * @param {JXG.Board} board 1998 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 1999 * line defined by the segment 2000 * @returns {JXG.Coords} Coords object containing the intersection. 2001 */ 2002 meetCurveLineContinuous: function (cu, li, nr, board, testSegment) { 2003 var func0, func1, 2004 t, v, x, y, z, 2005 eps = Mat.eps, 2006 epsLow = Mat.eps, 2007 steps, 2008 delta, 2009 tnew, tmin, fmin, 2010 i, ft; 2011 2012 v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment); 2013 x = v.usrCoords[1]; 2014 y = v.usrCoords[2]; 2015 2016 func0 = function (t) { 2017 var c1, c2; 2018 2019 if (t > cu.maxX() || t < cu.minX()) { 2020 return Infinity; 2021 } 2022 c1 = cu.X(t) - x; 2023 c2 = cu.Y(t) - y; 2024 return c1 * c1 + c2 * c2; 2025 // return c1 * (cu.X(t + h) - cu.X(t - h)) + c2 * (cu.Y(t + h) - cu.Y(t - h)) / h; 2026 }; 2027 2028 func1 = function (t) { 2029 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 2030 return v * v; 2031 }; 2032 2033 // Find t 2034 steps = 50; 2035 delta = (cu.maxX() - cu.minX()) / steps; 2036 tnew = cu.minX(); 2037 fmin = 0.0001; //eps; 2038 tmin = NaN; 2039 for (i = 0; i < steps; i++) { 2040 t = Numerics.root(func0, [ 2041 Math.max(tnew, cu.minX()), 2042 Math.min(tnew + delta, cu.maxX()) 2043 ]); 2044 ft = Math.abs(func0(t)); 2045 if (ft <= fmin) { 2046 fmin = ft; 2047 tmin = t; 2048 if (fmin < eps) { 2049 break; 2050 } 2051 } 2052 2053 tnew += delta; 2054 } 2055 t = tmin; 2056 // Compute "exact" t 2057 t = Numerics.root(func1, [ 2058 Math.max(t - delta, cu.minX()), 2059 Math.min(t + delta, cu.maxX()) 2060 ]); 2061 2062 ft = func1(t); 2063 // Is the point on the line? 2064 if (isNaN(ft) || Math.abs(ft) > epsLow) { 2065 z = 0.0; //NaN; 2066 } else { 2067 z = 1.0; 2068 } 2069 2070 return new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board); 2071 }, 2072 2073 /** 2074 * Intersection of line and curve, discrete case. 2075 * Segments are treated as lines. 2076 * Finding the nr-th intersection point should work for all nr. 2077 * @param {JXG.Curve} cu 2078 * @param {JXG.Line} li 2079 * @param {Number|Function} nr 2080 * @param {JXG.Board} board 2081 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 2082 * line defined by the segment 2083 * 2084 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 2085 * the ideal point [0,1,0] is returned. 2086 */ 2087 meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) { 2088 var i, j, 2089 n = Type.evaluate(nr), 2090 p1, p2, 2091 p, q, 2092 lip1 = li.point1.coords.usrCoords, 2093 lip2 = li.point2.coords.usrCoords, 2094 d, res, 2095 cnt = 0, 2096 len = cu.numberPoints, 2097 ev_sf = Type.evaluate(li.visProp.straightfirst), 2098 ev_sl = Type.evaluate(li.visProp.straightlast); 2099 2100 // In case, no intersection will be found we will take this 2101 q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board); 2102 2103 if (lip1[0] === 0.0) { 2104 lip1 = [1, lip2[1] + li.stdform[2], lip2[2] - li.stdform[1]]; 2105 } else if (lip2[0] === 0.0) { 2106 lip2 = [1, lip1[1] + li.stdform[2], lip1[2] - li.stdform[1]]; 2107 } 2108 2109 p2 = cu.points[0].usrCoords; 2110 for (i = 1; i < len; i += cu.bezierDegree) { 2111 p1 = p2.slice(0); 2112 p2 = cu.points[i].usrCoords; 2113 d = this.distance(p1, p2); 2114 2115 // The defining points are not identical 2116 if (d > Mat.eps) { 2117 if (cu.bezierDegree === 3) { 2118 res = this.meetBeziersegmentBeziersegment( 2119 [ 2120 cu.points[i - 1].usrCoords.slice(1), 2121 cu.points[i].usrCoords.slice(1), 2122 cu.points[i + 1].usrCoords.slice(1), 2123 cu.points[i + 2].usrCoords.slice(1) 2124 ], 2125 [lip1.slice(1), lip2.slice(1)], 2126 testSegment 2127 ); 2128 } else { 2129 res = [this.meetSegmentSegment(p1, p2, lip1, lip2)]; 2130 } 2131 2132 for (j = 0; j < res.length; j++) { 2133 p = res[j]; 2134 if (0 <= p[1] && p[1] <= 1) { 2135 if (cnt === n) { 2136 /** 2137 * If the intersection point is not part of the segment, 2138 * this intersection point is set to non-existent. 2139 * This prevents jumping behavior of the intersection points. 2140 * But it may be discussed if it is the desired behavior. 2141 */ 2142 if ( 2143 testSegment && 2144 ((!ev_sf && p[2] < 0) || (!ev_sl && p[2] > 1)) 2145 ) { 2146 return q; // break; 2147 } 2148 2149 q = new Coords(Const.COORDS_BY_USER, p[0], board); 2150 return q; // break; 2151 } 2152 cnt += 1; 2153 } 2154 } 2155 } 2156 } 2157 2158 return q; 2159 }, 2160 2161 /** 2162 * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter). 2163 * We go through each segment of the red curve and search if there is an intersection with a segment of the blue curve. 2164 * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines 2165 * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on 2166 * the property bezierDegree of the curves. 2167 * <p> 2168 * This method works also for transformed curves, since only the already 2169 * transformed points are used. 2170 * 2171 * @param {JXG.Curve} red 2172 * @param {JXG.Curve} blue 2173 * @param {Number|Function} nr 2174 */ 2175 meetCurveRedBlueSegments: function (red, blue, nr) { 2176 var i, 2177 j, 2178 n = Type.evaluate(nr), 2179 red1, 2180 red2, 2181 blue1, 2182 blue2, 2183 m, 2184 minX, 2185 maxX, 2186 iFound = 0, 2187 lenBlue = blue.numberPoints, //points.length, 2188 lenRed = red.numberPoints; //points.length; 2189 2190 if (lenBlue <= 1 || lenRed <= 1) { 2191 return [0, NaN, NaN]; 2192 } 2193 2194 for (i = 1; i < lenRed; i++) { 2195 red1 = red.points[i - 1].usrCoords; 2196 red2 = red.points[i].usrCoords; 2197 minX = Math.min(red1[1], red2[1]); 2198 maxX = Math.max(red1[1], red2[1]); 2199 2200 blue2 = blue.points[0].usrCoords; 2201 for (j = 1; j < lenBlue; j++) { 2202 blue1 = blue2; 2203 blue2 = blue.points[j].usrCoords; 2204 2205 if ( 2206 Math.min(blue1[1], blue2[1]) < maxX && 2207 Math.max(blue1[1], blue2[1]) > minX 2208 ) { 2209 m = this.meetSegmentSegment(red1, red2, blue1, blue2); 2210 if ( 2211 m[1] >= 0.0 && 2212 m[2] >= 0.0 && 2213 // The two segments meet in the interior or at the start points 2214 ((m[1] < 1.0 && m[2] < 1.0) || 2215 // One of the curve is intersected in the very last point 2216 (i === lenRed - 1 && m[1] === 1.0) || 2217 (j === lenBlue - 1 && m[2] === 1.0)) 2218 ) { 2219 if (iFound === n) { 2220 return m[0]; 2221 } 2222 2223 iFound++; 2224 } 2225 } 2226 } 2227 } 2228 2229 return [0, NaN, NaN]; 2230 }, 2231 2232 /** 2233 * (Virtual) Intersection of two segments. 2234 * @param {Array} p1 First point of segment 1 using normalized homogeneous coordinates [1,x,y] 2235 * @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 2236 * @param {Array} q1 First point of segment 2 using normalized homogeneous coordinates [1,x,y] 2237 * @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 2238 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 2239 * of the intersection point. The second and third entry give the position of the intersection with respect 2240 * to the definiting parameters. For example, the second entry t is defined by: intersection point = p1 + t * deltaP, where 2241 * deltaP = (p2 - p1) when both parameters are coordinates, and deltaP = p2 if p2 is a point at infinity. 2242 * If the two segments are collinear, [[0,0,0], Infinity, Infinity] is returned. 2243 **/ 2244 meetSegmentSegment: function (p1, p2, q1, q2) { 2245 var t, 2246 u, 2247 i, 2248 d, 2249 li1 = Mat.crossProduct(p1, p2), 2250 li2 = Mat.crossProduct(q1, q2), 2251 c = Mat.crossProduct(li1, li2); 2252 2253 if (Math.abs(c[0]) < Mat.eps) { 2254 return [c, Infinity, Infinity]; 2255 } 2256 2257 // Normalize the intersection coordinates 2258 c[1] /= c[0]; 2259 c[2] /= c[0]; 2260 c[0] /= c[0]; 2261 2262 // Now compute in principle: 2263 // t = dist(c - p1) / dist(p2 - p1) and 2264 // u = dist(c - q1) / dist(q2 - q1) 2265 // However: the points q1, q2, p1, p2 might be ideal points - or in general - the 2266 // coordinates might be not normalized. 2267 // Note that the z-coordinates of p2 and q2 are used to determine whether it should be interpreted 2268 // as a segment coordinate or a direction. 2269 i = Math.abs(p2[1] - p2[0] * p1[1]) < Mat.eps ? 2 : 1; 2270 d = p1[i] / p1[0]; 2271 t = (c[i] - d) / (p2[0] !== 0 ? p2[i] / p2[0] - d : p2[i]); 2272 2273 i = Math.abs(q2[1] - q2[0] * q1[1]) < Mat.eps ? 2 : 1; 2274 d = q1[i] / q1[0]; 2275 u = (c[i] - d) / (q2[0] !== 0 ? q2[i] / q2[0] - d : q2[i]); 2276 2277 return [c, t, u]; 2278 }, 2279 2280 /** 2281 * Find the n-th intersection point of two pathes, usually given by polygons. Uses parts of the 2282 * Greiner-Hormann algorithm in JXG.Math.Clip. 2283 * 2284 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} path1 2285 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} path2 2286 * @param {Number|Function} n 2287 * @param {JXG.Board} board 2288 * 2289 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 2290 * the ideal point [0,0,0] is returned. 2291 * 2292 */ 2293 meetPathPath: function (path1, path2, nr, board) { 2294 var S, C, len, intersections, 2295 n = Type.evaluate(nr); 2296 2297 S = JXG.Math.Clip._getPath(path1, board); 2298 len = S.length; 2299 if ( 2300 len > 0 && 2301 this.distance(S[0].coords.usrCoords, S[len - 1].coords.usrCoords, 3) < Mat.eps 2302 ) { 2303 S.pop(); 2304 } 2305 2306 C = JXG.Math.Clip._getPath(path2, board); 2307 len = C.length; 2308 if ( 2309 len > 0 && 2310 this.distance(C[0].coords.usrCoords, C[len - 1].coords.usrCoords, 3) < 2311 Mat.eps * Mat.eps 2312 ) { 2313 C.pop(); 2314 } 2315 2316 // Handle cases where at least one of the paths is empty 2317 if (nr < 0 || JXG.Math.Clip.isEmptyCase(S, C, "intersection")) { 2318 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 2319 } 2320 2321 JXG.Math.Clip.makeDoublyLinkedList(S); 2322 JXG.Math.Clip.makeDoublyLinkedList(C); 2323 2324 intersections = JXG.Math.Clip.findIntersections(S, C, board)[0]; 2325 if (n < intersections.length) { 2326 return intersections[n].coords; 2327 } 2328 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 2329 }, 2330 2331 /** 2332 * Find the n-th intersection point between a polygon and a line. 2333 * @param {JXG.Polygon} path 2334 * @param {JXG.Line} line 2335 * @param {Number|Function} nr 2336 * @param {JXG.Board} board 2337 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points of the line are tested for intersection. 2338 * 2339 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 2340 * the ideal point [0,0,0] is returned. 2341 */ 2342 meetPolygonLine: function (path, line, nr, board, alwaysIntersect) { 2343 var i, 2344 n = Type.evaluate(nr), 2345 res, 2346 border, 2347 crds = [0, 0, 0], 2348 len = path.borders.length, 2349 intersections = []; 2350 2351 for (i = 0; i < len; i++) { 2352 border = path.borders[i]; 2353 res = this.meetSegmentSegment( 2354 border.point1.coords.usrCoords, 2355 border.point2.coords.usrCoords, 2356 line.point1.coords.usrCoords, 2357 line.point2.coords.usrCoords 2358 ); 2359 2360 if ( 2361 (!alwaysIntersect || (res[2] >= 0 && res[2] < 1)) && 2362 res[1] >= 0 && 2363 res[1] < 1 2364 ) { 2365 intersections.push(res[0]); 2366 } 2367 } 2368 2369 if (n >= 0 && n < intersections.length) { 2370 crds = intersections[n]; 2371 } 2372 return new Coords(Const.COORDS_BY_USER, crds, board); 2373 }, 2374 2375 meetPlaneSphere: function (el1, el2) { 2376 var dis = function () { 2377 return ( 2378 el1.normal[0] * el2.center.X() 2379 + el1.normal[1] * el2.center.Y() 2380 + el1.normal[2] * el2.center.Z() 2381 - el1.d 2382 ); 2383 }; 2384 return [ 2385 [ 2386 // Center 2387 function () { 2388 return el2.center.X() - dis() * el1.normal[0]; 2389 }, 2390 function () { 2391 return el2.center.Y() - dis() * el1.normal[1]; 2392 }, 2393 function () { 2394 return el2.center.Z() - dis() * el1.normal[2]; 2395 } 2396 ], 2397 [ 2398 // Normal 2399 () => el1.normal[0], 2400 () => el1.normal[1], 2401 () => el1.normal[2] 2402 ], 2403 function () { 2404 // Radius (returns NaN if spheres don't touch) 2405 var r = el2.Radius(), 2406 s = dis(); 2407 return Math.sqrt(r * r - s * s); 2408 } 2409 ]; 2410 }, 2411 2412 meetSphereSphere: function (el1, el2) { 2413 var skew = function () { 2414 var dist = el1.center.distance(el2.center), 2415 r1 = el1.Radius(), 2416 r2 = el2.Radius(); 2417 return (r1 - r2) * (r1 + r2) / (dist * dist); 2418 }; 2419 return [ 2420 [ 2421 // Center 2422 function () { 2423 var s = skew(); 2424 return 0.5 * ((1 - s) * el1.center.X() + (1 + s) * el2.center.X()); 2425 }, 2426 function () { 2427 var s = skew(); 2428 return 0.5 * ((1 - s) * el1.center.Y() + (1 + s) * el2.center.Y()); 2429 }, 2430 function () { 2431 var s = skew(); 2432 return 0.5 * ((1 - s) * el1.center.Z() + (1 + s) * el2.center.Z()); 2433 } 2434 ], 2435 [ 2436 // Normal 2437 () => el2.center.X() - el1.center.X(), 2438 () => el2.center.Y() - el1.center.Y(), 2439 () => el2.center.Z() - el1.center.Z() 2440 ], 2441 function () { 2442 // Radius (returns NaN if spheres don't touch) 2443 var dist = el1.center.distance(el2.center), 2444 r1 = el1.Radius(), 2445 r2 = el2.Radius(), 2446 s = skew(), 2447 rIxnSq = 0.5 * (r1 * r1 + r2 * r2 - 0.5 * dist * dist * (1 + s * s)); 2448 return Math.sqrt(rIxnSq); 2449 } 2450 ]; 2451 }, 2452 2453 /****************************************/ 2454 /**** BEZIER CURVE ALGORITHMS ****/ 2455 /****************************************/ 2456 2457 /** 2458 * Splits a Bezier curve segment defined by four points into 2459 * two Bezier curve segments. Dissection point is t=1/2. 2460 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 2461 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2462 * @returns {Array} Array consisting of two coordinate arrays for Bezier curves. 2463 */ 2464 _bezierSplit: function (curve) { 2465 var p0, p1, p2, p00, p22, p000; 2466 2467 p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5]; 2468 p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5]; 2469 p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5]; 2470 2471 p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5]; 2472 p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5]; 2473 2474 p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5]; 2475 2476 return [ 2477 [curve[0], p0, p00, p000], 2478 [p000, p22, p2, curve[3]] 2479 ]; 2480 }, 2481 2482 /** 2483 * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment 2484 * from its control points. 2485 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 2486 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2487 * @returns {Array} Bounding box [minX, maxY, maxX, minY] 2488 */ 2489 _bezierBbox: function (curve) { 2490 var bb = []; 2491 2492 if (curve.length === 4) { 2493 // bezierDegree == 3 2494 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX 2495 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY 2496 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX 2497 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY 2498 } else { 2499 // bezierDegree == 1 2500 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX 2501 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY 2502 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX 2503 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY 2504 } 2505 2506 return bb; 2507 }, 2508 2509 /** 2510 * Decide if two Bezier curve segments overlap by comparing their bounding boxes. 2511 * @param {Array} bb1 Bounding box of the first Bezier curve segment 2512 * @param {Array} bb2 Bounding box of the second Bezier curve segment 2513 * @returns {Boolean} true if the bounding boxes overlap, false otherwise. 2514 */ 2515 _bezierOverlap: function (bb1, bb2) { 2516 return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1]; 2517 }, 2518 2519 /** 2520 * Append list of intersection points to a list. 2521 * @private 2522 */ 2523 _bezierListConcat: function (L, Lnew, t1, t2) { 2524 var i, 2525 t2exists = Type.exists(t2), 2526 start = 0, 2527 len = Lnew.length, 2528 le = L.length; 2529 2530 if ( 2531 le > 0 && 2532 len > 0 && 2533 ((L[le - 1][1] === 1 && Lnew[0][1] === 0) || 2534 (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0)) 2535 ) { 2536 start = 1; 2537 } 2538 2539 for (i = start; i < len; i++) { 2540 if (t2exists) { 2541 Lnew[i][2] *= 0.5; 2542 Lnew[i][2] += t2; 2543 } 2544 2545 Lnew[i][1] *= 0.5; 2546 Lnew[i][1] += t1; 2547 2548 L.push(Lnew[i]); 2549 } 2550 }, 2551 2552 /** 2553 * Find intersections of two Bezier curve segments by recursive subdivision. 2554 * Below maxlevel determine intersections by intersection line segments. 2555 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 2556 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2557 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 2558 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2559 * @param {Number} level Recursion level 2560 * @returns {Array} List of intersection points (up to nine). Each intersection point is an 2561 * array of length three (homogeneous coordinates) plus preimages. 2562 */ 2563 _bezierMeetSubdivision: function (red, blue, level) { 2564 var bbb, 2565 bbr, 2566 ar, 2567 b0, 2568 b1, 2569 r0, 2570 r1, 2571 m, 2572 p0, 2573 p1, 2574 q0, 2575 q1, 2576 L = [], 2577 maxLev = 5; // Maximum recursion level 2578 2579 bbr = this._bezierBbox(blue); 2580 bbb = this._bezierBbox(red); 2581 2582 if (!this._bezierOverlap(bbr, bbb)) { 2583 return []; 2584 } 2585 2586 if (level < maxLev) { 2587 ar = this._bezierSplit(red); 2588 r0 = ar[0]; 2589 r1 = ar[1]; 2590 2591 ar = this._bezierSplit(blue); 2592 b0 = ar[0]; 2593 b1 = ar[1]; 2594 2595 this._bezierListConcat( 2596 L, 2597 this._bezierMeetSubdivision(r0, b0, level + 1), 2598 0.0, 2599 0.0 2600 ); 2601 this._bezierListConcat( 2602 L, 2603 this._bezierMeetSubdivision(r0, b1, level + 1), 2604 0, 2605 0.5 2606 ); 2607 this._bezierListConcat( 2608 L, 2609 this._bezierMeetSubdivision(r1, b0, level + 1), 2610 0.5, 2611 0.0 2612 ); 2613 this._bezierListConcat( 2614 L, 2615 this._bezierMeetSubdivision(r1, b1, level + 1), 2616 0.5, 2617 0.5 2618 ); 2619 2620 return L; 2621 } 2622 2623 // Make homogeneous coordinates 2624 q0 = [1].concat(red[0]); 2625 q1 = [1].concat(red[3]); 2626 p0 = [1].concat(blue[0]); 2627 p1 = [1].concat(blue[3]); 2628 2629 m = this.meetSegmentSegment(q0, q1, p0, p1); 2630 2631 if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) { 2632 return [m]; 2633 } 2634 2635 return []; 2636 }, 2637 2638 /** 2639 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 2640 */ 2641 _bezierLineMeetSubdivision: function (red, blue, level, testSegment) { 2642 var bbb, bbr, ar, 2643 r0, r1, 2644 m, 2645 p0, p1, q0, q1, 2646 L = [], 2647 maxLev = 5; // Maximum recursion level 2648 2649 bbb = this._bezierBbox(blue); 2650 bbr = this._bezierBbox(red); 2651 2652 if (testSegment && !this._bezierOverlap(bbr, bbb)) { 2653 return []; 2654 } 2655 2656 if (level < maxLev) { 2657 ar = this._bezierSplit(red); 2658 r0 = ar[0]; 2659 r1 = ar[1]; 2660 2661 this._bezierListConcat( 2662 L, 2663 this._bezierLineMeetSubdivision(r0, blue, level + 1), 2664 0.0 2665 ); 2666 this._bezierListConcat( 2667 L, 2668 this._bezierLineMeetSubdivision(r1, blue, level + 1), 2669 0.5 2670 ); 2671 2672 return L; 2673 } 2674 2675 // Make homogeneous coordinates 2676 q0 = [1].concat(red[0]); 2677 q1 = [1].concat(red[3]); 2678 p0 = [1].concat(blue[0]); 2679 p1 = [1].concat(blue[1]); 2680 2681 m = this.meetSegmentSegment(q0, q1, p0, p1); 2682 2683 if (m[1] >= 0.0 && m[1] <= 1.0) { 2684 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) { 2685 return [m]; 2686 } 2687 } 2688 2689 return []; 2690 }, 2691 2692 /** 2693 * Find the nr-th intersection point of two Bezier curve segments. 2694 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 2695 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2696 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 2697 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2698 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 2699 * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus 2700 * preimages [x,y], t_1, t_2] of the two Bezier curve segments. 2701 * 2702 */ 2703 meetBeziersegmentBeziersegment: function (red, blue, testSegment) { 2704 var L, L2, i; 2705 2706 if (red.length === 4 && blue.length === 4) { 2707 L = this._bezierMeetSubdivision(red, blue, 0); 2708 } else { 2709 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment); 2710 } 2711 2712 L.sort(function (a, b) { 2713 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]); 2714 }); 2715 2716 L2 = []; 2717 for (i = 0; i < L.length; i++) { 2718 // Only push entries different from their predecessor 2719 if (i === 0 || L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2]) { 2720 L2.push(L[i]); 2721 } 2722 } 2723 return L2; 2724 }, 2725 2726 /** 2727 * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3. 2728 * @param {JXG.Curve} red Curve with bezierDegree == 3 2729 * @param {JXG.Curve} blue Curve with bezierDegree == 3 2730 * @param {Number|Function} nr The number of the intersection point which should be returned. 2731 * @returns {Array} The homogeneous coordinates of the nr-th intersection point. 2732 */ 2733 meetBezierCurveRedBlueSegments: function (red, blue, nr) { 2734 var p, i, j, k, 2735 n = Type.evaluate(nr), 2736 po, tmp, 2737 redArr, 2738 blueArr, 2739 bbr, 2740 bbb, 2741 intersections, 2742 startRed = 0, 2743 startBlue = 0, 2744 lenBlue, lenRed, 2745 L = []; 2746 2747 if (blue.numberPoints < blue.bezierDegree + 1 || red.numberPoints < red.bezierDegree + 1) { 2748 return [0, NaN, NaN]; 2749 } 2750 if (red.bezierDegree === 1 && blue.bezierDegree === 3) { 2751 tmp = red; 2752 red = blue; 2753 blue = tmp; 2754 } 2755 2756 lenBlue = blue.numberPoints - blue.bezierDegree; 2757 lenRed = red.numberPoints - red.bezierDegree; 2758 2759 // For sectors, we ignore the "legs" 2760 if (red.type === Const.OBJECT_TYPE_SECTOR) { 2761 startRed = 3; 2762 lenRed -= 3; 2763 } 2764 if (blue.type === Const.OBJECT_TYPE_SECTOR) { 2765 startBlue = 3; 2766 lenBlue -= 3; 2767 } 2768 2769 for (i = startRed; i < lenRed; i += red.bezierDegree) { 2770 p = red.points; 2771 redArr = [p[i].usrCoords.slice(1), p[i + 1].usrCoords.slice(1)]; 2772 if (red.bezierDegree === 3) { 2773 redArr[2] = p[i + 2].usrCoords.slice(1); 2774 redArr[3] = p[i + 3].usrCoords.slice(1); 2775 } 2776 2777 bbr = this._bezierBbox(redArr); 2778 2779 for (j = startBlue; j < lenBlue; j += blue.bezierDegree) { 2780 p = blue.points; 2781 blueArr = [p[j].usrCoords.slice(1), p[j + 1].usrCoords.slice(1)]; 2782 if (blue.bezierDegree === 3) { 2783 blueArr[2] = p[j + 2].usrCoords.slice(1); 2784 blueArr[3] = p[j + 3].usrCoords.slice(1); 2785 } 2786 2787 bbb = this._bezierBbox(blueArr); 2788 if (this._bezierOverlap(bbr, bbb)) { 2789 intersections = this.meetBeziersegmentBeziersegment(redArr, blueArr); 2790 if (intersections.length === 0) { 2791 continue; 2792 } 2793 for (k = 0; k < intersections.length; k++) { 2794 po = intersections[k]; 2795 if ( 2796 po[1] < -Mat.eps || 2797 po[1] > 1 + Mat.eps || 2798 po[2] < -Mat.eps || 2799 po[2] > 1 + Mat.eps 2800 ) { 2801 continue; 2802 } 2803 L.push(po); 2804 } 2805 if (L.length > n) { 2806 return L[n][0]; 2807 } 2808 } 2809 } 2810 } 2811 if (L.length > n) { 2812 return L[n][0]; 2813 } 2814 2815 return [0, NaN, NaN]; 2816 }, 2817 2818 bezierSegmentEval: function (t, curve) { 2819 var f, 2820 x, 2821 y, 2822 t1 = 1.0 - t; 2823 2824 x = 0; 2825 y = 0; 2826 2827 f = t1 * t1 * t1; 2828 x += f * curve[0][0]; 2829 y += f * curve[0][1]; 2830 2831 f = 3.0 * t * t1 * t1; 2832 x += f * curve[1][0]; 2833 y += f * curve[1][1]; 2834 2835 f = 3.0 * t * t * t1; 2836 x += f * curve[2][0]; 2837 y += f * curve[2][1]; 2838 2839 f = t * t * t; 2840 x += f * curve[3][0]; 2841 y += f * curve[3][1]; 2842 2843 return [1.0, x, y]; 2844 }, 2845 2846 /** 2847 * Generate the defining points of a 3rd degree bezier curve that approximates 2848 * a circle sector defined by three coordinate points A, B, C, each defined by an array of length three. 2849 * The coordinate arrays are given in homogeneous coordinates. 2850 * @param {Array} A First point 2851 * @param {Array} B Second point (intersection point) 2852 * @param {Array} C Third point 2853 * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve. 2854 * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1. 2855 */ 2856 bezierArc: function (A, B, C, withLegs, sgn) { 2857 var p1, p2, p3, p4, 2858 r, 2859 phi, beta, delta, 2860 // PI2 = Math.PI * 0.5, 2861 x = B[1], 2862 y = B[2], 2863 z = B[0], 2864 dataX = [], 2865 dataY = [], 2866 co, si, 2867 ax, ay, 2868 bx, by, 2869 k, v, d, 2870 matrix; 2871 2872 r = this.distance(B, A); 2873 2874 // x,y, z is intersection point. Normalize it. 2875 x /= z; 2876 y /= z; 2877 2878 phi = this.rad(A.slice(1), B.slice(1), C.slice(1)); 2879 if (sgn === -1) { 2880 phi = 2 * Math.PI - phi; 2881 } 2882 2883 // Always divide the arc into four Bezier arcs. 2884 // Otherwise, the position of gliders on this arc 2885 // will be wrong. 2886 delta = phi / 4; 2887 2888 2889 p1 = A; 2890 p1[1] /= p1[0]; 2891 p1[2] /= p1[0]; 2892 p1[0] /= p1[0]; 2893 2894 p4 = p1.slice(0); 2895 2896 if (withLegs) { 2897 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]]; 2898 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]]; 2899 } else { 2900 dataX = [p1[1]]; 2901 dataY = [p1[2]]; 2902 } 2903 2904 while (phi > Mat.eps) { 2905 // if (phi > PI2) { 2906 // beta = PI2; 2907 // phi -= PI2; 2908 // } else { 2909 // beta = phi; 2910 // phi = 0; 2911 // } 2912 if (phi > delta) { 2913 beta = delta; 2914 phi -= delta; 2915 } else { 2916 beta = phi; 2917 phi = 0; 2918 } 2919 2920 co = Math.cos(sgn * beta); 2921 si = Math.sin(sgn * beta); 2922 2923 matrix = [ 2924 [1, 0, 0], 2925 [x * (1 - co) + y * si, co, -si], 2926 [y * (1 - co) - x * si, si, co] 2927 ]; 2928 v = Mat.matVecMult(matrix, p1); 2929 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]]; 2930 2931 ax = p1[1] - x; 2932 ay = p1[2] - y; 2933 bx = p4[1] - x; 2934 by = p4[2] - y; 2935 d = Mat.hypot(ax + bx, ay + by); 2936 2937 if (Math.abs(by - ay) > Mat.eps) { 2938 k = ((((ax + bx) * (r / d - 0.5)) / (by - ay)) * 8) / 3; 2939 } else { 2940 k = ((((ay + by) * (r / d - 0.5)) / (ax - bx)) * 8) / 3; 2941 } 2942 2943 p2 = [1, p1[1] - k * ay, p1[2] + k * ax]; 2944 p3 = [1, p4[1] + k * by, p4[2] - k * bx]; 2945 2946 Type.concat(dataX, [p2[1], p3[1], p4[1]]); 2947 Type.concat(dataY, [p2[2], p3[2], p4[2]]); 2948 p1 = p4.slice(0); 2949 } 2950 2951 if (withLegs) { 2952 Type.concat(dataX, [ 2953 p4[1] + 0.333 * (x - p4[1]), 2954 p4[1] + 0.666 * (x - p4[1]), 2955 x 2956 ]); 2957 Type.concat(dataY, [ 2958 p4[2] + 0.333 * (y - p4[2]), 2959 p4[2] + 0.666 * (y - p4[2]), 2960 y 2961 ]); 2962 } 2963 2964 return [dataX, dataY]; 2965 }, 2966 2967 /****************************************/ 2968 /**** PROJECTIONS ****/ 2969 /****************************************/ 2970 2971 /** 2972 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 2973 * nearest one of the two intersection points of the line through the given point and the circles 2974 * center. 2975 * @param {JXG.Point|JXG.Coords} point Point to project or coords object to project. 2976 * @param {JXG.Circle} circle Circle on that the point is projected. 2977 * @param {JXG.Board} [board=point.board] Reference to the board 2978 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2979 */ 2980 projectPointToCircle: function (point, circle, board) { 2981 var dist, 2982 P, 2983 x, 2984 y, 2985 factor, 2986 M = circle.center.coords.usrCoords; 2987 2988 if (!Type.exists(board)) { 2989 board = point.board; 2990 } 2991 2992 // gave us a point 2993 if (Type.isPoint(point)) { 2994 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords); 2995 P = point.coords.usrCoords; 2996 // gave us coords 2997 } else { 2998 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords); 2999 P = point.usrCoords; 3000 } 3001 3002 if (Math.abs(dist) < Mat.eps) { 3003 dist = Mat.eps; 3004 } 3005 3006 factor = circle.Radius() / dist; 3007 x = M[1] + factor * (P[1] - M[1]); 3008 y = M[2] + factor * (P[2] - M[2]); 3009 3010 return new Coords(Const.COORDS_BY_USER, [x, y], board); 3011 }, 3012 3013 /** 3014 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 3015 * intersection point of the given line and its perpendicular through the given point. 3016 * @param {JXG.Point|JXG.Coords} point Point to project. 3017 * @param {JXG.Line} line Line on that the point is projected. 3018 * @param {JXG.Board} [board=point.board|board=line.board] Reference to a board. 3019 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 3020 */ 3021 projectPointToLine: function (point, line, board) { 3022 var v = [0, line.stdform[1], line.stdform[2]], 3023 coords; 3024 3025 if (!Type.exists(board)) { 3026 if (Type.exists(point.coords)) { 3027 board = point.board; 3028 } else { 3029 board = line.board; 3030 } 3031 } 3032 3033 if (Type.exists(point.coords)) { 3034 coords = point.coords.usrCoords; 3035 } else { 3036 coords = point.usrCoords; 3037 } 3038 3039 v = Mat.crossProduct(v, coords); 3040 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(v, line.stdform), board); 3041 }, 3042 3043 /** 3044 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 3045 * segment defined by two coordinate arrays. 3046 * @param {Array} p Point to project. 3047 * @param {Array} q1 Start point of the line segment on that the point is projected. 3048 * @param {Array} q2 End point of the line segment on that the point is projected. 3049 * @returns {Array} The coordinates of the projection of the given point on the given segment 3050 * and the factor that determines the projected point as a convex combination of the 3051 * two endpoints q1 and q2 of the segment. 3052 */ 3053 projectCoordsToSegment: function (p, q1, q2) { 3054 var t, 3055 denom, 3056 s = [q2[1] - q1[1], q2[2] - q1[2]], 3057 v = [p[1] - q1[1], p[2] - q1[2]]; 3058 3059 /** 3060 * If the segment has length 0, i.e. is a point, 3061 * the projection is equal to that point. 3062 */ 3063 if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) { 3064 return [q1, 0]; 3065 } 3066 3067 t = Mat.innerProduct(v, s); 3068 denom = Mat.innerProduct(s, s); 3069 t /= denom; 3070 3071 return [[1, t * s[0] + q1[1], t * s[1] + q1[2]], t]; 3072 }, 3073 3074 /** 3075 * Finds the coordinates of the closest point on a Bezier segment of a 3076 * {@link JXG.Curve} to a given coordinate array. 3077 * @param {Array} pos Point to project in homogeneous coordinates. 3078 * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3. 3079 * @param {Number} start Number of the Bezier segment of the curve. 3080 * @returns {Array} The coordinates of the projection of the given point 3081 * on the given Bezier segment and the preimage of the curve which 3082 * determines the closest point. 3083 */ 3084 projectCoordsToBeziersegment: function (pos, curve, start) { 3085 var t0, 3086 /** @ignore */ 3087 minfunc = function (t) { 3088 var z = [1, curve.X(start + t), curve.Y(start + t)]; 3089 3090 z[1] -= pos[1]; 3091 z[2] -= pos[2]; 3092 3093 return z[1] * z[1] + z[2] * z[2]; 3094 }; 3095 3096 t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]); 3097 3098 return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0]; 3099 }, 3100 3101 /** 3102 * Calculates the coordinates of the projection of a given point on a given curve. 3103 * Uses {@link JXG.Math.Geometry.projectCoordsToCurve}. 3104 * 3105 * @param {JXG.Point} point Point to project. 3106 * @param {JXG.Curve} curve Curve on that the point is projected. 3107 * @param {JXG.Board} [board=point.board] Reference to a board. 3108 * @see #projectCoordsToCurve 3109 * @returns {Array} [JXG.Coords, position] The coordinates of the projection of the given 3110 * point on the given graph and the relative position on the curve (real number). 3111 */ 3112 projectPointToCurve: function (point, curve, board) { 3113 if (!Type.exists(board)) { 3114 board = point.board; 3115 } 3116 3117 var x = point.X(), 3118 y = point.Y(), 3119 t = point.position, 3120 result; 3121 3122 if (!Type.exists(t)) { 3123 t = Type.evaluate(curve.visProp.curvetype) === 'functiongraph' ? x : 0.0; 3124 } 3125 result = this.projectCoordsToCurve(x, y, t, curve, board); 3126 3127 // point.position = result[1]; 3128 3129 return result; 3130 }, 3131 3132 /** 3133 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 3134 * function graphs this is the 3135 * intersection point of the curve and the parallel to y-axis through the given point. 3136 * @param {Number} x coordinate to project. 3137 * @param {Number} y coordinate to project. 3138 * @param {Number} t start value for newtons method 3139 * @param {JXG.Curve} curve Curve on that the point is projected. 3140 * @param {JXG.Board} [board=curve.board] Reference to a board. 3141 * @see #projectPointToCurve 3142 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given curve and 3143 * the position on the curve. 3144 */ 3145 projectCoordsToCurve: function (x, y, t, curve, board) { 3146 var newCoords, newCoordsObj, 3147 i, j, mindist, dist, lbda, 3148 v, coords, d, p1, p2, res, minfunc, 3149 t_new, f_new, f_old, 3150 delta, delta1, delta2, steps, minX, maxX, 3151 infty = Number.POSITIVE_INFINITY; 3152 3153 if (!Type.exists(board)) { 3154 board = curve.board; 3155 } 3156 3157 if (Type.evaluate(curve.visProp.curvetype) === "plot") { 3158 t = 0; 3159 mindist = infty; 3160 if (curve.numberPoints === 0) { 3161 newCoords = [0, 1, 1]; 3162 } else { 3163 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 3164 } 3165 3166 if (curve.numberPoints > 1) { 3167 v = [1, x, y]; 3168 if (curve.bezierDegree === 3) { 3169 j = 0; 3170 } else { 3171 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 3172 } 3173 for (i = 0; i < curve.numberPoints - 1; i++) { 3174 if (curve.bezierDegree === 3) { 3175 res = this.projectCoordsToBeziersegment(v, curve, j); 3176 } else { 3177 p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)]; 3178 res = this.projectCoordsToSegment(v, p1, p2); 3179 } 3180 lbda = res[1]; 3181 coords = res[0]; 3182 3183 if (0.0 <= lbda && lbda <= 1.0) { 3184 dist = this.distance(coords, v); 3185 d = i + lbda; 3186 } else if (lbda < 0.0) { 3187 coords = p1; 3188 dist = this.distance(p1, v); 3189 d = i; 3190 } else if (lbda > 1.0 && i === curve.numberPoints - 2) { 3191 coords = p2; 3192 dist = this.distance(coords, v); 3193 d = curve.numberPoints - 1; 3194 } 3195 3196 if (dist < mindist) { 3197 mindist = dist; 3198 t = d; 3199 newCoords = coords; 3200 } 3201 3202 if (curve.bezierDegree === 3) { 3203 j++; 3204 i += 2; 3205 } else { 3206 p1 = p2; 3207 } 3208 } 3209 } 3210 3211 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board); 3212 } else { 3213 // 'parameter', 'polar', 'functiongraph' 3214 3215 if (Type.evaluate(curve.visProp.curvetype) === 'functiongraph') { 3216 let dy = Math.abs(y - curve.Y(x)); 3217 if (!isNaN(dy)) { 3218 minX = x - dy; 3219 maxX = x + dy; 3220 } else { 3221 minX = curve.minX(); 3222 maxX = curve.maxX(); 3223 } 3224 } else { 3225 minX = curve.minX(); 3226 maxX = curve.maxX(); 3227 } 3228 3229 /** @ignore */ 3230 minfunc = function (t) { 3231 var dx, dy; 3232 if (t < curve.minX() || t > curve.maxX()) { 3233 return Infinity; 3234 } 3235 dx = x - curve.X(t); 3236 dy = y - curve.Y(t); 3237 return dx * dx + dy * dy; 3238 }; 3239 3240 f_old = minfunc(t); 3241 steps = 50; 3242 3243 delta = (maxX - minX) / steps; 3244 t_new = minX; 3245 3246 for (i = 0; i < steps; i++) { 3247 f_new = minfunc(t_new); 3248 3249 if (f_new < f_old || f_old === Infinity || isNaN(f_old)) { 3250 t = t_new; 3251 f_old = f_new; 3252 } 3253 3254 t_new += delta; 3255 } 3256 3257 // t = Numerics.root(Numerics.D(minfunc), t); 3258 // Ensure that minfunc is defined on the 3259 // enclsoing interval [t-delta1, t+delta2] 3260 delta1 = delta; 3261 for (i = 0; 3262 i < 20 && isNaN(minfunc(t - delta1)); 3263 i++, delta1 *= 0.5); 3264 3265 if (isNaN(minfunc(t - delta1))) { 3266 delta1 = 0.0; 3267 } 3268 delta2 = delta; 3269 for (i = 0; 3270 i < 20 && isNaN(minfunc(t + delta2)); 3271 i++, delta2 *= 0.5); 3272 if (isNaN(minfunc(t + delta2))) { 3273 delta2 = 0.0; 3274 } 3275 3276 t = Numerics.fminbr(minfunc, [ 3277 Math.max(t - delta1, minX), 3278 Math.min(t + delta2, maxX) 3279 ]); 3280 3281 // Distinction between closed and open curves is not necessary. 3282 // If closed, the cyclic projection shift will work anyhow 3283 // if (Math.abs(curve.X(minX) - curve.X(maxX)) < Mat.eps && 3284 // Math.abs(curve.Y(minX) - curve.Y(maxX)) < Mat.eps) { 3285 // // Cyclically 3286 // if (t < minX) {console.log(t) 3287 // t = maxX + t - minX; 3288 // } 3289 // if (t > maxX) { 3290 // t = minX + t - maxX; 3291 // } 3292 // } else { 3293 t = t < minX ? minX : t; 3294 t = t > maxX ? maxX : t; 3295 // } 3296 3297 newCoordsObj = new Coords( 3298 Const.COORDS_BY_USER, 3299 [curve.X(t), curve.Y(t)], 3300 board 3301 ); 3302 } 3303 3304 return [curve.updateTransform(newCoordsObj), t]; 3305 }, 3306 3307 /** 3308 * Calculates the coordinates of the closest orthogonal projection of a given coordinate array onto the 3309 * border of a polygon. 3310 * @param {Array} p Point to project. 3311 * @param {JXG.Polygon} pol Polygon element 3312 * @returns {Array} The coordinates of the closest projection of the given point to the border of the polygon. 3313 */ 3314 projectCoordsToPolygon: function (p, pol) { 3315 var i, 3316 len = pol.vertices.length, 3317 d_best = Infinity, 3318 d, 3319 projection, 3320 proj, 3321 bestprojection; 3322 3323 for (i = 0; i < len - 1; i++) { 3324 projection = JXG.Math.Geometry.projectCoordsToSegment( 3325 p, 3326 pol.vertices[i].coords.usrCoords, 3327 pol.vertices[i + 1].coords.usrCoords 3328 ); 3329 3330 if (0 <= projection[1] && projection[1] <= 1) { 3331 d = JXG.Math.Geometry.distance(projection[0], p, 3); 3332 proj = projection[0]; 3333 } else if (projection[1] < 0) { 3334 d = JXG.Math.Geometry.distance(pol.vertices[i].coords.usrCoords, p, 3); 3335 proj = pol.vertices[i].coords.usrCoords; 3336 } else { 3337 d = JXG.Math.Geometry.distance(pol.vertices[i + 1].coords.usrCoords, p, 3); 3338 proj = pol.vertices[i + 1].coords.usrCoords; 3339 } 3340 if (d < d_best) { 3341 bestprojection = proj.slice(0); 3342 d_best = d; 3343 } 3344 } 3345 return bestprojection; 3346 }, 3347 3348 /** 3349 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 3350 * one or more curves of curveType 'plot'. Uses {@link JXG.Math.Geometry.projectPointToCurve}. 3351 * @param {JXG.Point} point Point to project. 3352 * @param {JXG.Turtle} turtle on that the point is projected. 3353 * @param {JXG.Board} [board=point.board] Reference to a board. 3354 * @returns {Array} [JXG.Coords, position] Array containing the coordinates of the projection of the given point on the turtle and 3355 * the position on the turtle. 3356 */ 3357 projectPointToTurtle: function (point, turtle, board) { 3358 var newCoords, 3359 t, 3360 x, 3361 y, 3362 i, 3363 dist, 3364 el, 3365 minEl, 3366 res, 3367 newPos, 3368 np = 0, 3369 npmin = 0, 3370 mindist = Number.POSITIVE_INFINITY, 3371 len = turtle.objects.length; 3372 3373 if (!Type.exists(board)) { 3374 board = point.board; 3375 } 3376 3377 // run through all curves of this turtle 3378 for (i = 0; i < len; i++) { 3379 el = turtle.objects[i]; 3380 3381 if (el.elementClass === Const.OBJECT_CLASS_CURVE) { 3382 res = this.projectPointToCurve(point, el); 3383 newCoords = res[0]; 3384 newPos = res[1]; 3385 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 3386 3387 if (dist < mindist) { 3388 x = newCoords.usrCoords[1]; 3389 y = newCoords.usrCoords[2]; 3390 t = newPos; 3391 mindist = dist; 3392 minEl = el; 3393 npmin = np; 3394 } 3395 np += el.numberPoints; 3396 } 3397 } 3398 3399 newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board); 3400 // point.position = t + npmin; 3401 // return minEl.updateTransform(newCoords); 3402 return [minEl.updateTransform(newCoords), t + npmin]; 3403 }, 3404 3405 /** 3406 * Trivial projection of a point to another point. 3407 * @param {JXG.Point} point Point to project (not used). 3408 * @param {JXG.Point} dest Point on that the point is projected. 3409 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 3410 */ 3411 projectPointToPoint: function (point, dest) { 3412 return dest.coords; 3413 }, 3414 3415 /** 3416 * 3417 * @param {JXG.Point|JXG.Coords} point 3418 * @param {JXG.Board} [board] 3419 */ 3420 projectPointToBoard: function (point, board) { 3421 var i, 3422 l, 3423 c, 3424 brd = board || point.board, 3425 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx 3426 config = [ 3427 // left 3428 [1, 1, 0, 0, 3, 0, 1], 3429 // top 3430 [-1, 2, 1, 0, 1, 2, 1], 3431 // right 3432 [-1, 1, 2, 2, 1, 2, 3], 3433 // bottom 3434 [1, 2, 3, 0, 3, 2, 3] 3435 ], 3436 coords = point.coords || point, 3437 bbox = brd.getBoundingBox(); 3438 3439 for (i = 0; i < 4; i++) { 3440 c = config[i]; 3441 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) { 3442 // define border 3443 l = Mat.crossProduct( 3444 [1, bbox[c[3]], bbox[c[4]]], 3445 [1, bbox[c[5]], bbox[c[6]]] 3446 ); 3447 l[3] = 0; 3448 l = Mat.normalize(l); 3449 3450 // project point 3451 coords = this.projectPointToLine({ coords: coords }, { stdform: l }, brd); 3452 } 3453 } 3454 3455 return coords; 3456 }, 3457 3458 /** 3459 * Given a the coordinates of a point, finds the nearest point on the given 3460 * parametric curve or surface, and returns its view-space coordinates. 3461 * @param {Array} pScr Screen coordinates to project. 3462 * @param {JXG.Curve3D|JXG.Surface3D} target Parametric curve or surface to project to. 3463 * @param {Array} params Parameters of point on the target, initially specifying the starting point of 3464 * the search. The parameters are modified in place during the search, ending up at the nearest point. 3465 * @returns {Array} Array of length 4 containing the coordinates of the nearest point on the curve or surface. 3466 */ 3467 projectCoordsToParametric: function (p, target, params) { 3468 // The variables and parameters for the Cobyla constrained 3469 // minimization algorithm are explained in the Cobyla.js comments 3470 var rhobeg, // initial size of simplex (Cobyla) 3471 rhoend, // finial size of simplex (Cobyla) 3472 iprint = 0, // no console output (Cobyla) 3473 maxfun = 200, // call objective function at most 200 times (Cobyla) 3474 dim = params.length, 3475 _minFunc; // objective function (Cobyla) 3476 3477 // adapt simplex size to parameter range 3478 if (dim === 1) { 3479 rhobeg = 0.1 * (target.range[1] - target.range[0]); 3480 } else if (dim === 2) { 3481 rhobeg = 0.1 * Math.min( 3482 target.range_u[1] - target.range_u[0], 3483 target.range_v[1] - target.range_v[0] 3484 ); 3485 } 3486 rhoend = rhobeg / 5e6; 3487 3488 // minimize screen distance to cursor 3489 _minFunc = function (n, m, w, con) { 3490 // var xDiff = p[0] - target.X(...w), 3491 // yDiff = p[1] - target.Y(...w), 3492 // zDiff = p[2] - target.Z(...w); 3493 var xDiff = p[0] - target.X.apply(null, w), 3494 yDiff = p[1] - target.Y.apply(null, w), 3495 zDiff = p[2] - target.Z.apply(null, w); 3496 3497 if (n === 1) { 3498 con[0] = w[0] - target.range[0]; 3499 con[1] = -w[0] + target.range[1]; 3500 } else if (n === 2) { 3501 con[0] = w[0] - target.range_u[0]; 3502 con[1] = -w[0] + target.range_u[1]; 3503 con[2] = w[1] - target.range_v[0]; 3504 con[3] = -w[1] + target.range_v[1]; 3505 } 3506 return xDiff * xDiff + yDiff * yDiff + zDiff * zDiff; 3507 }; 3508 Mat.Nlp.FindMinimum(_minFunc, dim, 2 * dim, params, rhobeg, rhoend, iprint, maxfun); 3509 3510 // return [1, target.X(...params), target.Y(...params), target.Z(...params)]; 3511 return [1, target.X.apply(null, params), target.Y.apply(null, params), target.Z.apply(null, params)]; 3512 }, 3513 3514 /** 3515 * Given a the screen coordinates of a point, finds the point on the 3516 * given parametric curve or surface which is nearest in screen space, 3517 * and returns its view-space coordinates. 3518 * @param {Array} pScr Screen coordinates to project. 3519 * @param {JXG.Curve3D|JXG.Surface3D} target Parametric curve or surface to project to. 3520 * @param {Array} params Parameters of point on the target, initially specifying the starting point of 3521 * the search. The parameters are modified in place during the search, ending up at the nearest point. 3522 * @returns {Array} Array of length 4 containing the coordinates of the nearest point on the curve or surface. 3523 */ 3524 projectScreenCoordsToParametric: function (pScr, target, params) { 3525 // The variables and parameters for the Cobyla constrained 3526 // minimization algorithm are explained in the Cobyla.js comments 3527 var rhobeg, // initial size of simplex (Cobyla) 3528 rhoend, // finial size of simplex (Cobyla) 3529 iprint = 0, // no console output (Cobyla) 3530 maxfun = 200, // call objective function at most 200 times (Cobyla) 3531 dim = params.length, 3532 _minFunc; // objective function (Cobyla) 3533 3534 // adapt simplex size to parameter range 3535 if (dim === 1) { 3536 rhobeg = 0.1 * (target.range[1] - target.range[0]); 3537 } else if (dim === 2) { 3538 rhobeg = 0.1 * Math.min( 3539 target.range_u[1] - target.range_u[0], 3540 target.range_v[1] - target.range_v[0] 3541 ); 3542 } 3543 rhoend = rhobeg / 5e6; 3544 3545 // minimize screen distance to cursor 3546 _minFunc = function (n, m, w, con) { 3547 // var c3d = [ 3548 // 1, 3549 // target.X(...w), 3550 // target.Y(...w), 3551 // target.Z(...w) 3552 // ], 3553 var c3d = [ 3554 1, 3555 target.X.apply(null, w), 3556 target.Y.apply(null, w), 3557 target.Z.apply(null, w) 3558 ], 3559 c2d = target.view.project3DTo2D(c3d), 3560 xDiff = pScr[0] - c2d[1], 3561 yDiff = pScr[1] - c2d[2]; 3562 3563 if (n === 1) { 3564 con[0] = w[0] - target.range[0]; 3565 con[1] = -w[0] + target.range[1]; 3566 } else if (n === 2) { 3567 con[0] = w[0] - target.range_u[0]; 3568 con[1] = -w[0] + target.range_u[1]; 3569 con[2] = w[1] - target.range_v[0]; 3570 con[3] = -w[1] + target.range_v[1]; 3571 } 3572 return xDiff * xDiff + yDiff * yDiff; 3573 }; 3574 Mat.Nlp.FindMinimum(_minFunc, dim, 2 * dim, params, rhobeg, rhoend, iprint, maxfun); 3575 3576 // return [1, target.X(...params), target.Y(...params), target.Z(...params)]; 3577 return [1, target.X.apply(null, params), target.Y.apply(null, params), target.Z.apply(null, params)]; 3578 }, 3579 3580 /** 3581 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 3582 * coordinates. For lines this can be line.stdform. 3583 * @param {Array} point Homogeneous coordinates of a point. 3584 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 3585 * @returns {Number} Distance of the point to the line. 3586 */ 3587 distPointLine: function (point, line) { 3588 var a = line[1], 3589 b = line[2], 3590 c = line[0], 3591 nom; 3592 3593 if (Math.abs(a) + Math.abs(b) < Mat.eps) { 3594 return Number.POSITIVE_INFINITY; 3595 } 3596 3597 nom = a * point[1] + b * point[2] + c; 3598 a *= a; 3599 b *= b; 3600 3601 return Math.abs(nom) / Math.sqrt(a + b); 3602 }, 3603 3604 /** 3605 * Determine the (Euclidean) distance between a point q and a line segment 3606 * defined by two points p1 and p2. In case p1 equals p2, the distance to this 3607 * point is returned. 3608 * 3609 * @param {Array} q Homogeneous coordinates of q 3610 * @param {Array} p1 Homogeneous coordinates of p1 3611 * @param {Array} p2 Homogeneous coordinates of p2 3612 * @returns {Number} Distance of q to line segment [p1, p2] 3613 */ 3614 distPointSegment: function (q, p1, p2) { 3615 var x, y, dx, dy, 3616 den, lbda, 3617 eps = Mat.eps * Mat.eps, 3618 huge = 1000000; 3619 3620 // Difference q - p1 3621 x = q[1] - p1[1]; 3622 y = q[2] - p1[2]; 3623 x = (x === Infinity) ? huge : (x === -Infinity) ? -huge : x; 3624 y = (y === Infinity) ? huge : (y === -Infinity) ? -huge : y; 3625 3626 // Difference p2 - p1 3627 dx = p2[1] - p1[1]; 3628 dy = p2[2] - p1[2]; 3629 dx = (dx === Infinity) ? huge : (dx === -Infinity) ? -huge : dx; 3630 dy = (dy === Infinity) ? huge : (dy === -Infinity) ? -huge : dy; 3631 3632 // If den==0 then p1 and p2 are identical 3633 // In this case the distance to p1 is returned 3634 den = dx * dx + dy * dy; 3635 if (den > eps) { 3636 lbda = (x * dx + y * dy) / den; 3637 if (lbda < 0.0) { 3638 lbda = 0.0; 3639 } else if (lbda > 1.0) { 3640 lbda = 1.0; 3641 } 3642 x -= lbda * dx; 3643 y -= lbda * dy; 3644 } 3645 3646 return Mat.hypot(x, y); 3647 }, 3648 3649 /** 3650 * Helper function to create curve which displays a Reuleaux polygons. 3651 * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically, 3652 * these point list is the array vertices of a regular polygon. 3653 * @param {Number} nr Number of vertices 3654 * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values 3655 * for the start and the end of the paramtric curve. array may be used as parent array of a 3656 * {@link JXG.Curve}. 3657 * 3658 * @example 3659 * var A = brd.create('point',[-2,-2]); 3660 * var B = brd.create('point',[0,1]); 3661 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 3662 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 3663 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 3664 * 3665 * </pre><div class="jxgbox" id="JXG2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div> 3666 * <script type="text/javascript"> 3667 * var brd = JXG.JSXGraph.initBoard('JXG2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false}); 3668 * var A = brd.create('point',[-2,-2]); 3669 * var B = brd.create('point',[0,1]); 3670 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 3671 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 3672 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 3673 * </script><pre> 3674 */ 3675 reuleauxPolygon: function (points, nr) { 3676 var beta, 3677 pi2 = Math.PI * 2, 3678 pi2_n = pi2 / nr, 3679 diag = (nr - 1) / 2, 3680 d = 0, 3681 makeFct = function (which, trig) { 3682 return function (t, suspendUpdate) { 3683 var t1 = ((t % pi2) + pi2) % pi2, 3684 j = Math.floor(t1 / pi2_n) % nr; 3685 3686 if (!suspendUpdate) { 3687 d = points[0].Dist(points[diag]); 3688 beta = Mat.Geometry.rad( 3689 [points[0].X() + 1, points[0].Y()], 3690 points[0], 3691 points[diag % nr] 3692 ); 3693 } 3694 3695 if (isNaN(j)) { 3696 return j; 3697 } 3698 3699 t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta; 3700 3701 return points[j][which]() + d * Math[trig](t1); 3702 }; 3703 }; 3704 3705 return [makeFct("X", "cos"), makeFct("Y", "sin"), 0, pi2]; 3706 }, 3707 3708 meet3Planes: function (n1, d1, n2, d2, n3, d3) { 3709 var p = [0, 0, 0], 3710 n31, 3711 n12, 3712 n23, 3713 denom, 3714 i; 3715 3716 n31 = Mat.crossProduct(n3, n1); 3717 n12 = Mat.crossProduct(n1, n2); 3718 n23 = Mat.crossProduct(n2, n3); 3719 denom = Mat.innerProduct(n1, n23, 3); 3720 for (i = 0; i < 3; i++) { 3721 p[i] = (d1 * n23[i] + d2 * n31[i] + d3 * n12[i]) / denom; 3722 } 3723 return p; 3724 }, 3725 3726 meetPlanePlane: function (v11, v12, v21, v22) { 3727 var i, 3728 no1, 3729 no2, 3730 v = [0, 0, 0], 3731 w = [0, 0, 0]; 3732 3733 for (i = 0; i < 3; i++) { 3734 v[i] = Type.evaluate(v11[i]); 3735 w[i] = Type.evaluate(v12[i]); 3736 } 3737 no1 = Mat.crossProduct(v, w); 3738 3739 for (i = 0; i < 3; i++) { 3740 v[i] = Type.evaluate(v21[i]); 3741 w[i] = Type.evaluate(v22[i]); 3742 } 3743 no2 = Mat.crossProduct(v, w); 3744 3745 return Mat.crossProduct(no1, no2); 3746 }, 3747 3748 project3DTo3DPlane: function (point, normal, foot) { 3749 // TODO: homogeneous 3D coordinates 3750 var sol = [0, 0, 0], 3751 le, 3752 d1, 3753 d2, 3754 lbda; 3755 3756 foot = foot || [0, 0, 0]; 3757 3758 le = Mat.norm(normal); 3759 d1 = Mat.innerProduct(point, normal, 3); 3760 d2 = Mat.innerProduct(foot, normal, 3); 3761 // (point - lbda * normal / le) * normal / le == foot * normal / le 3762 // => (point * normal - foot * normal) == lbda * le 3763 lbda = (d1 - d2) / le; 3764 sol = Mat.axpy(-lbda, normal, point); 3765 3766 return sol; 3767 }, 3768 3769 getPlaneBounds: function (v1, v2, q, s, e) { 3770 var s1, s2, e1, e2, mat, rhs, sol; 3771 3772 if (v1[2] + v2[0] !== 0) { 3773 mat = [ 3774 [v1[0], v2[0]], 3775 [v1[1], v2[1]] 3776 ]; 3777 rhs = [s - q[0], s - q[1]]; 3778 3779 sol = Numerics.Gauss(mat, rhs); 3780 s1 = sol[0]; 3781 s2 = sol[1]; 3782 3783 rhs = [e - q[0], e - q[1]]; 3784 sol = Numerics.Gauss(mat, rhs); 3785 e1 = sol[0]; 3786 e2 = sol[1]; 3787 return [s1, e1, s2, e2]; 3788 } 3789 return null; 3790 } 3791 } 3792 ); 3793 3794 export default Mat.Geometry; 3795