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 * <p> 1156 * Non-homogeneous version. 1157 * 1158 * @param {Array|JXG.Point} p1 First point or its coordinates of the segment. Point object or array of length 3. First (homogeneous) coordinate is equal to 1. 1159 * @param {Array|JXG.Point} p2 Second point or its coordinates of the segment. Point object or array of length 3. First (homogeneous) coordinate is equal to 1. 1160 * @param {Array|JXG.Point} q Point or its coordinates. Point object or array of length 3. First (homogeneous) coordinate is equal to 1. 1161 * @return {Number} Signed area of the triangle formed by these three points. 1162 * 1163 * @see #windingNumber 1164 */ 1165 det3p: function (p1, p2, q) { 1166 var pp1, pp2, qq; 1167 1168 if (Type.isPoint(p1)) { 1169 pp1 = p1.Coords(true); 1170 } else { 1171 pp1 = p1; 1172 } 1173 if (Type.isPoint(p2)) { 1174 pp2 = p2.Coords(true); 1175 } else { 1176 pp2 = p2; 1177 } 1178 if (Type.isPoint(q)) { 1179 qq = q.Coords(true); 1180 } else { 1181 qq = q; 1182 } 1183 1184 return (pp1[1] - qq[1]) * (pp2[2] - qq[2]) - (pp2[1] - qq[1]) * (pp1[2] - qq[2]); 1185 }, 1186 1187 /** 1188 * Winding number of a point in respect to a polygon path. 1189 * 1190 * The point is regarded outside if the winding number is zero, 1191 * inside otherwise. The algorithm tries to find degenerate cases, i.e. 1192 * if the point is on the path. This is regarded as "outside". 1193 * If the point is a vertex of the path, it is regarded as "inside". 1194 * 1195 * Implementation of algorithm 7 from "The point in polygon problem for 1196 * arbitrary polygons" by Kai Hormann and Alexander Agathos, Computational Geometry, 1197 * Volume 20, Issue 3, November 2001, Pages 131-144. 1198 * 1199 * @param {Array} usrCoords Homogenous coordinates of the point 1200 * @param {Array} path Array of points / coords determining a path, i.e. the vertices of the polygon / path. The array elements 1201 * do not have to be full points, but have to have a subobject "coords" or should be of type JXG.Coords. 1202 * @param {Boolean} [doNotClosePath=false] If true the last point of the path is not connected to the first point. 1203 * This is necessary if the path consists of two or more closed subpaths, e.g. if the figure has a hole. 1204 * 1205 * @return {Number} Winding number of the point. The point is 1206 * regarded outside if the winding number is zero, 1207 * inside otherwise. 1208 */ 1209 windingNumber: function (usrCoords, path, doNotClosePath) { 1210 var wn = 0, 1211 le = path.length, 1212 x = usrCoords[1], 1213 y = usrCoords[2], 1214 p0, 1215 p1, 1216 p2, 1217 d, 1218 sign, 1219 i, 1220 off = 0; 1221 1222 if (le === 0) { 1223 return 0; 1224 } 1225 1226 doNotClosePath = doNotClosePath || false; 1227 if (doNotClosePath) { 1228 off = 1; 1229 } 1230 1231 // Infinite points are declared outside 1232 if (isNaN(x) || isNaN(y)) { 1233 return 1; 1234 } 1235 1236 if (Type.exists(path[0].coords)) { 1237 p0 = path[0].coords; 1238 p1 = path[le - 1].coords; 1239 } else { 1240 p0 = path[0]; 1241 p1 = path[le - 1]; 1242 } 1243 // Handle the case if the point is the first vertex of the path, i.e. inside. 1244 if (p0.usrCoords[1] === x && p0.usrCoords[2] === y) { 1245 return 1; 1246 } 1247 1248 for (i = 0; i < le - off; i++) { 1249 // Consider the edge from p1 = path[i] to p2 = path[i+1]isClosedPath 1250 if (Type.exists(path[i].coords)) { 1251 p1 = path[i].coords.usrCoords; 1252 p2 = path[(i + 1) % le].coords.usrCoords; 1253 } else { 1254 p1 = path[i].usrCoords; 1255 p2 = path[(i + 1) % le].usrCoords; 1256 } 1257 1258 // If one of the two points p1, p2 is undefined or infinite, 1259 // move on. 1260 if ( 1261 p1[0] === 0 || 1262 p2[0] === 0 || 1263 isNaN(p1[1]) || 1264 isNaN(p2[1]) || 1265 isNaN(p1[2]) || 1266 isNaN(p2[2]) 1267 ) { 1268 continue; 1269 } 1270 1271 if (p2[2] === y) { 1272 if (p2[1] === x) { 1273 return 1; 1274 } 1275 if (p1[2] === y && p2[1] > x === p1[1] < x) { 1276 return 0; 1277 } 1278 } 1279 1280 if (p1[2] < y !== p2[2] < y) { 1281 // Crossing 1282 sign = 2 * (p2[2] > p1[2] ? 1 : 0) - 1; 1283 if (p1[1] >= x) { 1284 if (p2[1] > x) { 1285 wn += sign; 1286 } else { 1287 d = this.det3p(p1, p2, usrCoords); 1288 if (d === 0) { 1289 // Point is on line, i.e. outside 1290 return 0; 1291 } 1292 if (d > 0 + Mat.eps === p2[2] > p1[2]) { 1293 // Right crossing 1294 wn += sign; 1295 } 1296 } 1297 } else { 1298 if (p2[1] > x) { 1299 d = this.det3p(p1, p2, usrCoords); 1300 if (d > 0 + Mat.eps === p2[2] > p1[2]) { 1301 // Right crossing 1302 wn += sign; 1303 } 1304 } 1305 } 1306 } 1307 } 1308 1309 return wn; 1310 }, 1311 1312 /** 1313 * Decides if a point (x,y) is inside of a path / polygon. 1314 * Does not work correct if the path has hole. In this case, windingNumber is the preferred method. 1315 * Implements W. Randolf Franklin's pnpoly method. 1316 * 1317 * See <a href="https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html">https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html</a>. 1318 * 1319 * @param {Number} x_in x-coordinate (screen or user coordinates) 1320 * @param {Number} y_in y-coordinate (screen or user coordinates) 1321 * @param {Array} path Array of points / coords determining a path, i.e. the vertices of the polygon / path. The array elements 1322 * do not have to be full points, but have to have a subobject "coords" or should be of type JXG.Coords. 1323 * @param {Number} [coord_type=JXG.COORDS_BY_SCREEN] Type of coordinates used here. 1324 * Possible values are <b>JXG.COORDS_BY_USER</b> and <b>JXG.COORDS_BY_SCREEN</b>. 1325 * Default value is JXG.COORDS_BY_SCREEN. 1326 * 1327 * @returns {Boolean} if (x_in, y_in) is inside of the polygon. 1328 * @see JXG.Polygon.hasPoint 1329 * @see JXG.Polygon.pnpoly 1330 * @see #windingNumber 1331 * 1332 * @example 1333 * var pol = board.create('polygon', [[-1,2], [2,2], [-1,4]]); 1334 * var p = board.create('point', [4, 3]); 1335 * var txt = board.create('text', [-1, 0.5, function() { 1336 * return 'Point A is inside of the polygon = ' + 1337 * JXG.Math.Geometry.pnpoly(p.X(), p.Y(), JXG.COORDS_BY_USER, pol.vertices); 1338 * }]); 1339 * 1340 * </pre><div id="JXG4656ed42-f965-4e35-bb66-c334a4529683" class="jxgbox" style="width: 300px; height: 300px;"></div> 1341 * <script type="text/javascript"> 1342 * (function() { 1343 * var board = JXG.JSXGraph.initBoard('JXG4656ed42-f965-4e35-bb66-c334a4529683', 1344 * {boundingbox: [-2, 5, 5,-2], axis: true, showcopyright: false, shownavigation: false}); 1345 * var pol = board.create('polygon', [[-1,2], [2,2], [-1,4]]); 1346 * var p = board.create('point', [4, 3]); 1347 * var txt = board.create('text', [-1, 0.5, function() { 1348 * return 'Point A is inside of the polygon = ' + JXG.Math.Geometry.pnpoly(p.X(), p.Y(), JXG.COORDS_BY_USER, pol.vertices); 1349 * }]); 1350 * 1351 * })(); 1352 * 1353 * </script><pre> 1354 * 1355 */ 1356 pnpoly: function (x_in, y_in, path, coord_type) { 1357 var i, j, vi, vj, len, 1358 x, y, crds, 1359 v = path, 1360 isIn = false; 1361 1362 if (coord_type === Const.COORDS_BY_USER) { 1363 crds = new Coords(Const.COORDS_BY_USER, [x_in, y_in], this.board); 1364 x = crds.scrCoords[1]; 1365 y = crds.scrCoords[2]; 1366 } else { 1367 x = x_in; 1368 y = y_in; 1369 } 1370 1371 len = path.length; 1372 for (i = 0, j = len - 2; i < len - 1; j = i++) { 1373 vi = Type.exists(v[i].coords) ? v[i].coords : v[i]; 1374 vj = Type.exists(v[j].coords) ? v[j].coords : v[j]; 1375 1376 if ( 1377 vi.scrCoords[2] > y !== vj.scrCoords[2] > y && 1378 x < 1379 ((vj.scrCoords[1] - vi.scrCoords[1]) * (y - vi.scrCoords[2])) / 1380 (vj.scrCoords[2] - vi.scrCoords[2]) + 1381 vi.scrCoords[1] 1382 ) { 1383 isIn = !isIn; 1384 } 1385 } 1386 1387 return isIn; 1388 }, 1389 1390 /****************************************/ 1391 /**** INTERSECTIONS ****/ 1392 /****************************************/ 1393 1394 /** 1395 * Generate the function which computes the coordinates of the intersection point. 1396 * Primarily used in {@link JXG.Point#createIntersectionPoint}. 1397 * @param {JXG.Board} board object 1398 * @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. 1399 * i determines the intersection point if two points are available: <ul> 1400 * <li>i==0: use the positive square root,</li> 1401 * <li>i==1: use the negative square root.</li></ul> 1402 * See further {@link JXG.Point#createIntersectionPoint}. 1403 * @param {Boolean} alwaysintersect. Flag that determines if segments and arc can have an outer intersection point 1404 * on their defining line or circle. 1405 * @returns {Function} Function returning a {@link JXG.Coords} object that determines 1406 * the intersection point. 1407 */ 1408 intersectionFunction: function (board, el1, el2, i, j, alwaysintersect) { 1409 var func, 1410 that = this, 1411 el1_isArcType = false, 1412 el2_isArcType = false; 1413 1414 el1_isArcType = 1415 el1.elementClass === Const.OBJECT_CLASS_CURVE && 1416 (el1.type === Const.OBJECT_TYPE_ARC || el1.type === Const.OBJECT_TYPE_SECTOR) 1417 ? true 1418 : false; 1419 el2_isArcType = 1420 el2.elementClass === Const.OBJECT_CLASS_CURVE && 1421 (el2.type === Const.OBJECT_TYPE_ARC || el2.type === Const.OBJECT_TYPE_SECTOR) 1422 ? true 1423 : false; 1424 1425 if ( 1426 (el1.elementClass === Const.OBJECT_CLASS_CURVE || 1427 el2.elementClass === Const.OBJECT_CLASS_CURVE) && 1428 (el1.elementClass === Const.OBJECT_CLASS_CURVE || 1429 el1.elementClass === Const.OBJECT_CLASS_CIRCLE) && 1430 (el2.elementClass === Const.OBJECT_CLASS_CURVE || 1431 el2.elementClass === Const.OBJECT_CLASS_CIRCLE) /*&& 1432 !(el1_isArcType && el2_isArcType)*/ 1433 ) { 1434 // curve - curve 1435 // with the exception that both elements are arc types 1436 /** @ignore */ 1437 func = function () { 1438 return that.meetCurveCurve(el1, el2, i, j, el1.board); 1439 }; 1440 } else if ( 1441 (el1.elementClass === Const.OBJECT_CLASS_CURVE && 1442 !el1_isArcType && 1443 el2.elementClass === Const.OBJECT_CLASS_LINE) || 1444 (el2.elementClass === Const.OBJECT_CLASS_CURVE && 1445 !el2_isArcType && 1446 el1.elementClass === Const.OBJECT_CLASS_LINE) 1447 ) { 1448 // curve - line (this includes intersections between conic sections and lines) 1449 // with the exception that the curve is of arc type 1450 /** @ignore */ 1451 func = function () { 1452 return that.meetCurveLine(el1, el2, i, el1.board, Type.evaluate(alwaysintersect)); 1453 }; 1454 } else if ( 1455 el1.type === Const.OBJECT_TYPE_POLYGON || 1456 el2.type === Const.OBJECT_TYPE_POLYGON 1457 ) { 1458 // polygon - other 1459 // Uses the Greiner-Hormann clipping algorithm 1460 // Not implemented: polygon - point 1461 1462 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1463 // line - path 1464 /** @ignore */ 1465 func = function () { 1466 var first1 = Type.evaluate(el1.visProp.straightfirst), 1467 last1 = Type.evaluate(el1.visProp.straightlast), 1468 first2 = Type.evaluate(el2.visProp.straightfirst), 1469 last2 = Type.evaluate(el2.visProp.straightlast), 1470 a_not; 1471 1472 a_not = (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)); 1473 return that.meetPolygonLine(el2, el1, i, el1.board, a_not); 1474 }; 1475 } else if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1476 // path - line 1477 func = function () { 1478 var first1 = Type.evaluate(el1.visProp.straightfirst), 1479 last1 = Type.evaluate(el1.visProp.straightlast), 1480 first2 = Type.evaluate(el2.visProp.straightfirst), 1481 last2 = Type.evaluate(el2.visProp.straightlast), 1482 a_not; 1483 1484 a_not = (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)); 1485 return that.meetPolygonLine(el1, el2, i, el1.board, a_not); 1486 }; 1487 } else { 1488 // path - path 1489 /** @ignore */ 1490 func = function () { 1491 return that.meetPathPath(el1, el2, i, el1.board); 1492 }; 1493 } 1494 } else if ( 1495 el1.elementClass === Const.OBJECT_CLASS_LINE && 1496 el2.elementClass === Const.OBJECT_CLASS_LINE 1497 ) { 1498 // line - line, lines may also be segments. 1499 /** @ignore */ 1500 func = function () { 1501 var res, 1502 c, 1503 first1 = Type.evaluate(el1.visProp.straightfirst), 1504 last1 = Type.evaluate(el1.visProp.straightlast), 1505 first2 = Type.evaluate(el2.visProp.straightfirst), 1506 last2 = Type.evaluate(el2.visProp.straightlast); 1507 1508 /** 1509 * If one of the lines is a segment or ray and 1510 * the intersection point should disappear if outside 1511 * of the segment or ray we call 1512 * meetSegmentSegment 1513 */ 1514 if ( 1515 !Type.evaluate(alwaysintersect) && 1516 (!first1 || !last1 || !first2 || !last2) 1517 ) { 1518 res = that.meetSegmentSegment( 1519 el1.point1.coords.usrCoords, 1520 el1.point2.coords.usrCoords, 1521 el2.point1.coords.usrCoords, 1522 el2.point2.coords.usrCoords 1523 ); 1524 1525 if ( 1526 (!first1 && res[1] < 0) || 1527 (!last1 && res[1] > 1) || 1528 (!first2 && res[2] < 0) || 1529 (!last2 && res[2] > 1) 1530 ) { 1531 // Non-existent 1532 c = [0, NaN, NaN]; 1533 } else { 1534 c = res[0]; 1535 } 1536 1537 return new Coords(Const.COORDS_BY_USER, c, el1.board); 1538 } 1539 1540 return that.meet(el1.stdform, el2.stdform, i, el1.board); 1541 }; 1542 } else { 1543 // All other combinations of circles and lines, 1544 // Arc types are treated as circles. 1545 /** @ignore */ 1546 func = function () { 1547 var res = that.meet(el1.stdform, el2.stdform, i, el1.board), 1548 has = true, 1549 first, 1550 last, 1551 r; 1552 1553 if (Type.evaluate(alwaysintersect)) { 1554 return res; 1555 } 1556 if (el1.elementClass === Const.OBJECT_CLASS_LINE) { 1557 first = Type.evaluate(el1.visProp.straightfirst); 1558 last = Type.evaluate(el1.visProp.straightlast); 1559 if (!first || !last) { 1560 r = that.affineRatio(el1.point1.coords, el1.point2.coords, res); 1561 if ((!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps)) { 1562 return new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board); 1563 } 1564 } 1565 } 1566 if (el2.elementClass === Const.OBJECT_CLASS_LINE) { 1567 first = Type.evaluate(el2.visProp.straightfirst); 1568 last = Type.evaluate(el2.visProp.straightlast); 1569 if (!first || !last) { 1570 r = that.affineRatio(el2.point1.coords, el2.point2.coords, res); 1571 if ((!last && r > 1 + Mat.eps) || (!first && r < 0 - Mat.eps)) { 1572 return new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board); 1573 } 1574 } 1575 } 1576 if (el1_isArcType) { 1577 has = that.coordsOnArc(el1, res); 1578 if (has && el2_isArcType) { 1579 has = that.coordsOnArc(el2, res); 1580 } 1581 if (!has) { 1582 return new Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], el1.board); 1583 } 1584 } 1585 return res; 1586 }; 1587 } 1588 1589 return func; 1590 }, 1591 1592 otherIntersectionFunction: function (input, others, alwaysintersect, precision) { 1593 var func, board, 1594 el1, el2, 1595 that = this; 1596 1597 el1 = input[0]; 1598 el2 = input[1]; 1599 board = el1.board; 1600 func = function () { 1601 var i, k, c, d, 1602 isClose, 1603 le = others.length, 1604 eps = Type.evaluate(precision); 1605 1606 for (i = le; i >= 0; i--) { 1607 if (el1.elementClass === Const.OBJECT_CLASS_CIRCLE && 1608 [Const.OBJECT_CLASS_CIRCLE, Const.OBJECT_CLASS_LINE].indexOf(el2.elementClass) >= 0) { 1609 // circle, circle|line 1610 c = that.meet(el1.stdform, el2.stdform, i, board); 1611 } else if (el1.elementClass === Const.OBJECT_CLASS_CURVE && 1612 [Const.OBJECT_CLASS_CURVE, Const.OBJECT_CLASS_CIRCLE].indexOf(el2.elementClass) >= 0) { 1613 // curve, circle|curve 1614 c = that.meetCurveCurve(el1, el2, i, 0, board, 'segment'); 1615 } else if (el1.elementClass === Const.OBJECT_CLASS_CURVE && el2.elementClass === Const.OBJECT_CLASS_LINE) { 1616 // curve, line 1617 if (Type.exists(el1.dataX)) { 1618 c = JXG.Math.Geometry.meetCurveLine(el1, el2, i, el1.board, Type.evaluate(alwaysintersect)); 1619 } else { 1620 c = JXG.Math.Geometry.meetCurveLineContinuous(el1, el2, i, el1.board); 1621 } 1622 } 1623 1624 // If the intersection is close to one of the points in other 1625 // we have to search for another intersection point. 1626 isClose = false; 1627 for (k = 0; !isClose && k < le; k++) { 1628 d = c.distance(JXG.COORDS_BY_USER, others[k].coords); 1629 if (d < eps) { 1630 isClose = true; 1631 } 1632 } 1633 if (!isClose) { 1634 // We are done, the intersection is away from any other 1635 // intersection point. 1636 return c; 1637 } 1638 } 1639 // Otherwise we return the last intersection point 1640 return c; 1641 }; 1642 return func; 1643 }, 1644 1645 /** 1646 * Generate the function which computes the data of the intersection. 1647 */ 1648 intersectionFunction3D: function (view, el1, el2, i) { 1649 var func, 1650 that = this; 1651 1652 if (el1.type === Const.OBJECT_TYPE_PLANE3D) { 1653 if (el2.type === Const.OBJECT_TYPE_PLANE3D) { 1654 func = () => view.intersectionPlanePlane(el1, el2)[i]; 1655 } else if (el2.type === Const.OBJECT_TYPE_SPHERE3D) { 1656 func = that.meetPlaneSphere(el1, el2); 1657 } 1658 } else if (el1.type === Const.OBJECT_TYPE_SPHERE3D) { 1659 if (el2.type === Const.OBJECT_TYPE_PLANE3D) { 1660 func = that.meetPlaneSphere(el2, el1); 1661 } else if (el2.type === Const.OBJECT_TYPE_SPHERE3D) { 1662 func = that.meetSphereSphere(el1, el2); 1663 } 1664 } 1665 1666 return func; 1667 }, 1668 1669 /** 1670 * Returns true if the coordinates are on the arc element, 1671 * false otherwise. Usually, coords is an intersection 1672 * on the circle line. Now it is decided if coords are on the 1673 * circle restricted to the arc line. 1674 * @param {Arc} arc arc or sector element 1675 * @param {JXG.Coords} coords Coords object of an intersection 1676 * @returns {Boolean} 1677 * @private 1678 */ 1679 coordsOnArc: function (arc, coords) { 1680 var angle = this.rad(arc.radiuspoint, arc.center, coords.usrCoords.slice(1)), 1681 alpha = 0.0, 1682 beta = this.rad(arc.radiuspoint, arc.center, arc.anglepoint), 1683 ev_s = Type.evaluate(arc.visProp.selection); 1684 1685 if ((ev_s === "minor" && beta > Math.PI) || (ev_s === "major" && beta < Math.PI)) { 1686 alpha = beta; 1687 beta = 2 * Math.PI; 1688 } 1689 if (angle < alpha || angle > beta) { 1690 return false; 1691 } 1692 return true; 1693 }, 1694 1695 /** 1696 * Computes the intersection of a pair of lines, circles or both. 1697 * It uses the internal data array stdform of these elements. 1698 * @param {Array} el1 stdform of the first element (line or circle) 1699 * @param {Array} el2 stdform of the second element (line or circle) 1700 * @param {Number|Function} i Index of the intersection point that should be returned. 1701 * @param board Reference to the board. 1702 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 1703 * Which point will be returned is determined by i. 1704 */ 1705 meet: function (el1, el2, i, board) { 1706 var result, 1707 eps = Mat.eps; 1708 1709 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { 1710 // line line 1711 result = this.meetLineLine(el1, el2, i, board); 1712 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { 1713 // circle line 1714 result = this.meetLineCircle(el2, el1, i, board); 1715 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { 1716 // line circle 1717 result = this.meetLineCircle(el1, el2, i, board); 1718 } else { 1719 // circle circle 1720 result = this.meetCircleCircle(el1, el2, i, board); 1721 } 1722 1723 return result; 1724 }, 1725 1726 /** 1727 * Intersection of the line with the board 1728 * @param {Array} line stdform of the line in screen coordinates 1729 * @param {JXG.Board} board reference to a board. 1730 * @param {Number} margin optional margin, to avoid the display of the small sides of lines. 1731 * @returns {Array} [intersection coords 1, intersection coords 2] 1732 */ 1733 meetLineBoard: function (line, board, margin) { 1734 // Intersect the line with the four borders of the board. 1735 var s = [], 1736 intersect1, 1737 intersect2, 1738 i, j; 1739 1740 if (!Type.exists(margin)) { 1741 margin = 0; 1742 } 1743 1744 // top 1745 s[0] = Mat.crossProduct(line, [margin, 0, 1]); 1746 // left 1747 s[1] = Mat.crossProduct(line, [margin, 1, 0]); 1748 // bottom 1749 s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]); 1750 // right 1751 s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]); 1752 1753 // Normalize the intersections 1754 for (i = 0; i < 4; i++) { 1755 if (Math.abs(s[i][0]) > Mat.eps) { 1756 for (j = 2; j > 0; j--) { 1757 s[i][j] /= s[i][0]; 1758 } 1759 s[i][0] = 1.0; 1760 } 1761 } 1762 1763 // line is parallel to "left", take "top" and "bottom" 1764 if (Math.abs(s[1][0]) < Mat.eps) { 1765 intersect1 = s[0]; // top 1766 intersect2 = s[2]; // bottom 1767 // line is parallel to "top", take "left" and "right" 1768 } else if (Math.abs(s[0][0]) < Mat.eps) { 1769 intersect1 = s[1]; // left 1770 intersect2 = s[3]; // right 1771 // left intersection out of board (above) 1772 } else if (s[1][2] < 0) { 1773 intersect1 = s[0]; // top 1774 1775 // right intersection out of board (below) 1776 if (s[3][2] > board.canvasHeight) { 1777 intersect2 = s[2]; // bottom 1778 } else { 1779 intersect2 = s[3]; // right 1780 } 1781 // left intersection out of board (below) 1782 } else if (s[1][2] > board.canvasHeight) { 1783 intersect1 = s[2]; // bottom 1784 1785 // right intersection out of board (above) 1786 if (s[3][2] < 0) { 1787 intersect2 = s[0]; // top 1788 } else { 1789 intersect2 = s[3]; // right 1790 } 1791 } else { 1792 intersect1 = s[1]; // left 1793 1794 // right intersection out of board (above) 1795 if (s[3][2] < 0) { 1796 intersect2 = s[0]; // top 1797 // right intersection out of board (below) 1798 } else if (s[3][2] > board.canvasHeight) { 1799 intersect2 = s[2]; // bottom 1800 } else { 1801 intersect2 = s[3]; // right 1802 } 1803 } 1804 1805 return [ 1806 new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board), 1807 new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board) 1808 ]; 1809 }, 1810 1811 /** 1812 * Intersection of two lines. 1813 * @param {Array} l1 stdform of the first line 1814 * @param {Array} l2 stdform of the second line 1815 * @param {number} i unused 1816 * @param {JXG.Board} board Reference to the board. 1817 * @returns {JXG.Coords} Coordinates of the intersection point. 1818 */ 1819 meetLineLine: function (l1, l2, i, board) { 1820 var s = isNaN(l1[5] + l2[5]) ? [0, 0, 0] : Mat.crossProduct(l1, l2); 1821 1822 // Make intersection of parallel lines more robust: 1823 if (Math.abs(s[0]) < 1.0e-14) { 1824 s[0] = 0; 1825 } 1826 return new Coords(Const.COORDS_BY_USER, s, board); 1827 }, 1828 1829 /** 1830 * Intersection of line and circle. 1831 * @param {Array} lin stdform of the line 1832 * @param {Array} circ stdform of the circle 1833 * @param {number|function} i number of the returned intersection point. 1834 * i==0: use the positive square root, 1835 * i==1: use the negative square root. 1836 * @param {JXG.Board} board Reference to a board. 1837 * @returns {JXG.Coords} Coordinates of the intersection point 1838 */ 1839 meetLineCircle: function (lin, circ, i, board) { 1840 var a, b, c, d, n, A, B, C, k, t; 1841 1842 // Radius is zero, return center of circle 1843 if (circ[4] < Mat.eps) { 1844 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) { 1845 return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board); 1846 } 1847 1848 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board); 1849 } 1850 c = circ[0]; 1851 b = circ.slice(1, 3); 1852 a = circ[3]; 1853 d = lin[0]; 1854 n = lin.slice(1, 3); 1855 1856 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 1857 /* 1858 var nn = n[0]*n[0]+n[1]*n[1]; 1859 A = a*nn; 1860 B = (b[0]*n[1]-b[1]*n[0])*nn; 1861 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 1862 */ 1863 A = a; 1864 B = b[0] * n[1] - b[1] * n[0]; 1865 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 1866 1867 k = B * B - 4 * A * C; 1868 if (k > -Mat.eps * Mat.eps) { 1869 k = Math.sqrt(Math.abs(k)); 1870 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)]; 1871 1872 return Type.evaluate(i) === 0 1873 ? new Coords( 1874 Const.COORDS_BY_USER, 1875 [-t[0] * -n[1] - d * n[0], -t[0] * n[0] - d * n[1]], 1876 board 1877 ) 1878 : new Coords( 1879 Const.COORDS_BY_USER, 1880 [-t[1] * -n[1] - d * n[0], -t[1] * n[0] - d * n[1]], 1881 board 1882 ); 1883 } 1884 1885 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1886 }, 1887 1888 /** 1889 * Intersection of two circles. 1890 * @param {Array} circ1 stdform of the first circle 1891 * @param {Array} circ2 stdform of the second circle 1892 * @param {number|function} i number of the returned intersection point. 1893 * i==0: use the positive square root, 1894 * i==1: use the negative square root. 1895 * @param {JXG.Board} board Reference to the board. 1896 * @returns {JXG.Coords} Coordinates of the intersection point 1897 */ 1898 meetCircleCircle: function (circ1, circ2, i, board) { 1899 var radicalAxis; 1900 1901 // Radius is zero, return center of circle, if on other circle 1902 if (circ1[4] < Mat.eps) { 1903 if ( 1904 Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < 1905 Mat.eps 1906 ) { 1907 return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board); 1908 } 1909 1910 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1911 } 1912 1913 // Radius is zero, return center of circle, if on other circle 1914 if (circ2[4] < Mat.eps) { 1915 if ( 1916 Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < 1917 Mat.eps 1918 ) { 1919 return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board); 1920 } 1921 1922 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1923 } 1924 1925 radicalAxis = [ 1926 circ2[3] * circ1[0] - circ1[3] * circ2[0], 1927 circ2[3] * circ1[1] - circ1[3] * circ2[1], 1928 circ2[3] * circ1[2] - circ1[3] * circ2[2], 1929 0, 1930 1, 1931 Infinity, 1932 Infinity, 1933 Infinity 1934 ]; 1935 radicalAxis = Mat.normalize(radicalAxis); 1936 1937 return this.meetLineCircle(radicalAxis, circ1, i, board); 1938 }, 1939 1940 /** 1941 * Compute an intersection of the curves c1 and c2. 1942 * We want to find values t1, t2 such that 1943 * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 1944 * 1945 * Methods: segment-wise intersections (default) or generalized Newton method. 1946 * @param {JXG.Curve} c1 Curve, Line or Circle 1947 * @param {JXG.Curve} c2 Curve, Line or Circle 1948 * @param {Number|Function} nr the nr-th intersection point will be returned. 1949 * @param {Number} t2ini not longer used. 1950 * @param {JXG.Board} [board=c1.board] Reference to a board object. 1951 * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'. 1952 * @returns {JXG.Coords} intersection point 1953 */ 1954 meetCurveCurve: function (c1, c2, nr, t2ini, board, method) { 1955 var co; 1956 1957 if (Type.exists(method) && method === "newton") { 1958 co = Numerics.generalizedNewton(c1, c2, Type.evaluate(nr), t2ini); 1959 } else { 1960 if (c1.bezierDegree === 3 || c2.bezierDegree === 3) { 1961 co = this.meetBezierCurveRedBlueSegments(c1, c2, nr); 1962 } else { 1963 co = this.meetCurveRedBlueSegments(c1, c2, nr); 1964 } 1965 } 1966 1967 return new Coords(Const.COORDS_BY_USER, co, board); 1968 }, 1969 1970 /** 1971 * Intersection of curve with line, 1972 * Order of input does not matter for el1 and el2. 1973 * From version 0.99.7 on this method calls 1974 * {@link JXG.Math.Geometry.meetCurveLineDiscrete}. 1975 * If higher precision is needed, {@link JXG.Math.Geometry.meetCurveLineContinuous} 1976 * has to be used. 1977 * 1978 * @param {JXG.Curve|JXG.Line} el1 Curve or Line 1979 * @param {JXG.Curve|JXG.Line} el2 Curve or Line 1980 * @param {Number|Function} nr the nr-th intersection point will be returned. 1981 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1982 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection 1983 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1984 * the ideal point [0,1,0] is returned. 1985 */ 1986 meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) { 1987 var v = [0, NaN, NaN], 1988 cu, 1989 li; 1990 1991 if (!Type.exists(board)) { 1992 board = el1.board; 1993 } 1994 1995 if (el1.elementClass === Const.OBJECT_CLASS_CURVE) { 1996 cu = el1; 1997 li = el2; 1998 } else { 1999 cu = el2; 2000 li = el1; 2001 } 2002 2003 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect); 2004 2005 return v; 2006 }, 2007 2008 /** 2009 * Intersection of line and curve, continuous case. 2010 * Finds the nr-the intersection point 2011 * Uses {@link JXG.Math.Geometry.meetCurveLineDiscrete} as a first approximation. 2012 * A more exact solution is then found with {@link JXG.Math.Numerics.root}. 2013 * 2014 * @param {JXG.Curve} cu Curve 2015 * @param {JXG.Line} li Line 2016 * @param {NumberFunction} nr Will return the nr-th intersection point. 2017 * @param {JXG.Board} board 2018 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 2019 * line defined by the segment 2020 * @returns {JXG.Coords} Coords object containing the intersection. 2021 */ 2022 meetCurveLineContinuous: function (cu, li, nr, board, testSegment) { 2023 var func0, func1, 2024 t, v, x, y, z, 2025 eps = Mat.eps, 2026 epsLow = Mat.eps, 2027 steps, 2028 delta, 2029 tnew, tmin, fmin, 2030 i, ft; 2031 2032 v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment); 2033 x = v.usrCoords[1]; 2034 y = v.usrCoords[2]; 2035 2036 func0 = function (t) { 2037 var c1, c2; 2038 2039 if (t > cu.maxX() || t < cu.minX()) { 2040 return Infinity; 2041 } 2042 c1 = cu.X(t) - x; 2043 c2 = cu.Y(t) - y; 2044 return c1 * c1 + c2 * c2; 2045 // return c1 * (cu.X(t + h) - cu.X(t - h)) + c2 * (cu.Y(t + h) - cu.Y(t - h)) / h; 2046 }; 2047 2048 func1 = function (t) { 2049 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 2050 return v * v; 2051 }; 2052 2053 // Find t 2054 steps = 50; 2055 delta = (cu.maxX() - cu.minX()) / steps; 2056 tnew = cu.minX(); 2057 fmin = 0.0001; //eps; 2058 tmin = NaN; 2059 for (i = 0; i < steps; i++) { 2060 t = Numerics.root(func0, [ 2061 Math.max(tnew, cu.minX()), 2062 Math.min(tnew + delta, cu.maxX()) 2063 ]); 2064 ft = Math.abs(func0(t)); 2065 if (ft <= fmin) { 2066 fmin = ft; 2067 tmin = t; 2068 if (fmin < eps) { 2069 break; 2070 } 2071 } 2072 2073 tnew += delta; 2074 } 2075 t = tmin; 2076 // Compute "exact" t 2077 t = Numerics.root(func1, [ 2078 Math.max(t - delta, cu.minX()), 2079 Math.min(t + delta, cu.maxX()) 2080 ]); 2081 2082 ft = func1(t); 2083 // Is the point on the line? 2084 if (isNaN(ft) || Math.abs(ft) > epsLow) { 2085 z = 0.0; //NaN; 2086 } else { 2087 z = 1.0; 2088 } 2089 2090 return new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board); 2091 }, 2092 2093 /** 2094 * Intersection of line and curve, discrete case. 2095 * Segments are treated as lines. 2096 * Finding the nr-th intersection point should work for all nr. 2097 * @param {JXG.Curve} cu 2098 * @param {JXG.Line} li 2099 * @param {Number|Function} nr 2100 * @param {JXG.Board} board 2101 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 2102 * line defined by the segment 2103 * 2104 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 2105 * the ideal point [0,1,0] is returned. 2106 */ 2107 meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) { 2108 var i, j, 2109 n = Type.evaluate(nr), 2110 p1, p2, 2111 p, q, 2112 lip1 = li.point1.coords.usrCoords, 2113 lip2 = li.point2.coords.usrCoords, 2114 d, res, 2115 cnt = 0, 2116 len = cu.numberPoints, 2117 ev_sf = Type.evaluate(li.visProp.straightfirst), 2118 ev_sl = Type.evaluate(li.visProp.straightlast); 2119 2120 // In case, no intersection will be found we will take this 2121 q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board); 2122 2123 if (lip1[0] === 0.0) { 2124 lip1 = [1, lip2[1] + li.stdform[2], lip2[2] - li.stdform[1]]; 2125 } else if (lip2[0] === 0.0) { 2126 lip2 = [1, lip1[1] + li.stdform[2], lip1[2] - li.stdform[1]]; 2127 } 2128 2129 p2 = cu.points[0].usrCoords; 2130 for (i = 1; i < len; i += cu.bezierDegree) { 2131 p1 = p2.slice(0); 2132 p2 = cu.points[i].usrCoords; 2133 d = this.distance(p1, p2); 2134 2135 // The defining points are not identical 2136 if (d > Mat.eps) { 2137 if (cu.bezierDegree === 3) { 2138 res = this.meetBeziersegmentBeziersegment( 2139 [ 2140 cu.points[i - 1].usrCoords.slice(1), 2141 cu.points[i].usrCoords.slice(1), 2142 cu.points[i + 1].usrCoords.slice(1), 2143 cu.points[i + 2].usrCoords.slice(1) 2144 ], 2145 [lip1.slice(1), lip2.slice(1)], 2146 testSegment 2147 ); 2148 } else { 2149 res = [this.meetSegmentSegment(p1, p2, lip1, lip2)]; 2150 } 2151 2152 for (j = 0; j < res.length; j++) { 2153 p = res[j]; 2154 if (0 <= p[1] && p[1] <= 1) { 2155 if (cnt === n) { 2156 /** 2157 * If the intersection point is not part of the segment, 2158 * this intersection point is set to non-existent. 2159 * This prevents jumping behavior of the intersection points. 2160 * But it may be discussed if it is the desired behavior. 2161 */ 2162 if ( 2163 testSegment && 2164 ((!ev_sf && p[2] < 0) || (!ev_sl && p[2] > 1)) 2165 ) { 2166 return q; // break; 2167 } 2168 2169 q = new Coords(Const.COORDS_BY_USER, p[0], board); 2170 return q; // break; 2171 } 2172 cnt += 1; 2173 } 2174 } 2175 } 2176 } 2177 2178 return q; 2179 }, 2180 2181 /** 2182 * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter). 2183 * We go through each segment of the red curve and search if there is an intersection with a segment of the blue curve. 2184 * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines 2185 * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on 2186 * the property bezierDegree of the curves. 2187 * <p> 2188 * This method works also for transformed curves, since only the already 2189 * transformed points are used. 2190 * 2191 * @param {JXG.Curve} red 2192 * @param {JXG.Curve} blue 2193 * @param {Number|Function} nr 2194 */ 2195 meetCurveRedBlueSegments: function (red, blue, nr) { 2196 var i, 2197 j, 2198 n = Type.evaluate(nr), 2199 red1, 2200 red2, 2201 blue1, 2202 blue2, 2203 m, 2204 minX, 2205 maxX, 2206 iFound = 0, 2207 lenBlue = blue.numberPoints, //points.length, 2208 lenRed = red.numberPoints; //points.length; 2209 2210 if (lenBlue <= 1 || lenRed <= 1) { 2211 return [0, NaN, NaN]; 2212 } 2213 2214 for (i = 1; i < lenRed; i++) { 2215 red1 = red.points[i - 1].usrCoords; 2216 red2 = red.points[i].usrCoords; 2217 minX = Math.min(red1[1], red2[1]); 2218 maxX = Math.max(red1[1], red2[1]); 2219 2220 blue2 = blue.points[0].usrCoords; 2221 for (j = 1; j < lenBlue; j++) { 2222 blue1 = blue2; 2223 blue2 = blue.points[j].usrCoords; 2224 2225 if ( 2226 Math.min(blue1[1], blue2[1]) < maxX && 2227 Math.max(blue1[1], blue2[1]) > minX 2228 ) { 2229 m = this.meetSegmentSegment(red1, red2, blue1, blue2); 2230 if ( 2231 m[1] >= 0.0 && 2232 m[2] >= 0.0 && 2233 // The two segments meet in the interior or at the start points 2234 ((m[1] < 1.0 && m[2] < 1.0) || 2235 // One of the curve is intersected in the very last point 2236 (i === lenRed - 1 && m[1] === 1.0) || 2237 (j === lenBlue - 1 && m[2] === 1.0)) 2238 ) { 2239 if (iFound === n) { 2240 return m[0]; 2241 } 2242 2243 iFound++; 2244 } 2245 } 2246 } 2247 } 2248 2249 return [0, NaN, NaN]; 2250 }, 2251 2252 /** 2253 * (Virtual) Intersection of two segments. 2254 * @param {Array} p1 First point of segment 1 using normalized homogeneous coordinates [1,x,y] 2255 * @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 2256 * @param {Array} q1 First point of segment 2 using normalized homogeneous coordinates [1,x,y] 2257 * @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 2258 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 2259 * of the intersection point. The second and third entry give the position of the intersection with respect 2260 * to the definiting parameters. For example, the second entry t is defined by: intersection point = p1 + t * deltaP, where 2261 * deltaP = (p2 - p1) when both parameters are coordinates, and deltaP = p2 if p2 is a point at infinity. 2262 * If the two segments are collinear, [[0,0,0], Infinity, Infinity] is returned. 2263 **/ 2264 meetSegmentSegment: function (p1, p2, q1, q2) { 2265 var t, 2266 u, 2267 i, 2268 d, 2269 li1 = Mat.crossProduct(p1, p2), 2270 li2 = Mat.crossProduct(q1, q2), 2271 c = Mat.crossProduct(li1, li2); 2272 2273 if (Math.abs(c[0]) < Mat.eps) { 2274 return [c, Infinity, Infinity]; 2275 } 2276 2277 // Normalize the intersection coordinates 2278 c[1] /= c[0]; 2279 c[2] /= c[0]; 2280 c[0] /= c[0]; 2281 2282 // Now compute in principle: 2283 // t = dist(c - p1) / dist(p2 - p1) and 2284 // u = dist(c - q1) / dist(q2 - q1) 2285 // However: the points q1, q2, p1, p2 might be ideal points - or in general - the 2286 // coordinates might be not normalized. 2287 // Note that the z-coordinates of p2 and q2 are used to determine whether it should be interpreted 2288 // as a segment coordinate or a direction. 2289 i = Math.abs(p2[1] - p2[0] * p1[1]) < Mat.eps ? 2 : 1; 2290 d = p1[i] / p1[0]; 2291 t = (c[i] - d) / (p2[0] !== 0 ? p2[i] / p2[0] - d : p2[i]); 2292 2293 i = Math.abs(q2[1] - q2[0] * q1[1]) < Mat.eps ? 2 : 1; 2294 d = q1[i] / q1[0]; 2295 u = (c[i] - d) / (q2[0] !== 0 ? q2[i] / q2[0] - d : q2[i]); 2296 2297 return [c, t, u]; 2298 }, 2299 2300 /** 2301 * Find the n-th intersection point of two pathes, usually given by polygons. Uses parts of the 2302 * Greiner-Hormann algorithm in JXG.Math.Clip. 2303 * 2304 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} path1 2305 * @param {JXG.Circle|JXG.Curve|JXG.Polygon} path2 2306 * @param {Number|Function} n 2307 * @param {JXG.Board} board 2308 * 2309 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 2310 * the ideal point [0,0,0] is returned. 2311 * 2312 */ 2313 meetPathPath: function (path1, path2, nr, board) { 2314 var S, C, len, intersections, 2315 n = Type.evaluate(nr); 2316 2317 S = JXG.Math.Clip._getPath(path1, board); 2318 len = S.length; 2319 if ( 2320 len > 0 && 2321 this.distance(S[0].coords.usrCoords, S[len - 1].coords.usrCoords, 3) < Mat.eps 2322 ) { 2323 S.pop(); 2324 } 2325 2326 C = JXG.Math.Clip._getPath(path2, board); 2327 len = C.length; 2328 if ( 2329 len > 0 && 2330 this.distance(C[0].coords.usrCoords, C[len - 1].coords.usrCoords, 3) < 2331 Mat.eps * Mat.eps 2332 ) { 2333 C.pop(); 2334 } 2335 2336 // Handle cases where at least one of the paths is empty 2337 if (nr < 0 || JXG.Math.Clip.isEmptyCase(S, C, "intersection")) { 2338 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 2339 } 2340 2341 JXG.Math.Clip.makeDoublyLinkedList(S); 2342 JXG.Math.Clip.makeDoublyLinkedList(C); 2343 2344 intersections = JXG.Math.Clip.findIntersections(S, C, board)[0]; 2345 if (n < intersections.length) { 2346 return intersections[n].coords; 2347 } 2348 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 2349 }, 2350 2351 /** 2352 * Find the n-th intersection point between a polygon and a line. 2353 * @param {JXG.Polygon} path 2354 * @param {JXG.Line} line 2355 * @param {Number|Function} nr 2356 * @param {JXG.Board} board 2357 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points of the line are tested for intersection. 2358 * 2359 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 2360 * the ideal point [0,0,0] is returned. 2361 */ 2362 meetPolygonLine: function (path, line, nr, board, alwaysIntersect) { 2363 var i, 2364 n = Type.evaluate(nr), 2365 res, 2366 border, 2367 crds = [0, 0, 0], 2368 len = path.borders.length, 2369 intersections = []; 2370 2371 for (i = 0; i < len; i++) { 2372 border = path.borders[i]; 2373 res = this.meetSegmentSegment( 2374 border.point1.coords.usrCoords, 2375 border.point2.coords.usrCoords, 2376 line.point1.coords.usrCoords, 2377 line.point2.coords.usrCoords 2378 ); 2379 2380 if ( 2381 (!alwaysIntersect || (res[2] >= 0 && res[2] < 1)) && 2382 res[1] >= 0 && 2383 res[1] < 1 2384 ) { 2385 intersections.push(res[0]); 2386 } 2387 } 2388 2389 if (n >= 0 && n < intersections.length) { 2390 crds = intersections[n]; 2391 } 2392 return new Coords(Const.COORDS_BY_USER, crds, board); 2393 }, 2394 2395 meetPlaneSphere: function (el1, el2) { 2396 var dis = function () { 2397 return ( 2398 el1.normal[0] * el2.center.X() 2399 + el1.normal[1] * el2.center.Y() 2400 + el1.normal[2] * el2.center.Z() 2401 - el1.d 2402 ); 2403 }; 2404 return [ 2405 [ 2406 // Center 2407 function () { 2408 return el2.center.X() - dis() * el1.normal[0]; 2409 }, 2410 function () { 2411 return el2.center.Y() - dis() * el1.normal[1]; 2412 }, 2413 function () { 2414 return el2.center.Z() - dis() * el1.normal[2]; 2415 } 2416 ], 2417 [ 2418 // Normal 2419 () => el1.normal[0], 2420 () => el1.normal[1], 2421 () => el1.normal[2] 2422 ], 2423 function () { 2424 // Radius (returns NaN if spheres don't touch) 2425 var r = el2.Radius(), 2426 s = dis(); 2427 return Math.sqrt(r * r - s * s); 2428 } 2429 ]; 2430 }, 2431 2432 meetSphereSphere: function (el1, el2) { 2433 var skew = function () { 2434 var dist = el1.center.distance(el2.center), 2435 r1 = el1.Radius(), 2436 r2 = el2.Radius(); 2437 return (r1 - r2) * (r1 + r2) / (dist * dist); 2438 }; 2439 return [ 2440 [ 2441 // Center 2442 function () { 2443 var s = skew(); 2444 return 0.5 * ((1 - s) * el1.center.X() + (1 + s) * el2.center.X()); 2445 }, 2446 function () { 2447 var s = skew(); 2448 return 0.5 * ((1 - s) * el1.center.Y() + (1 + s) * el2.center.Y()); 2449 }, 2450 function () { 2451 var s = skew(); 2452 return 0.5 * ((1 - s) * el1.center.Z() + (1 + s) * el2.center.Z()); 2453 } 2454 ], 2455 [ 2456 // Normal 2457 () => el2.center.X() - el1.center.X(), 2458 () => el2.center.Y() - el1.center.Y(), 2459 () => el2.center.Z() - el1.center.Z() 2460 ], 2461 function () { 2462 // Radius (returns NaN if spheres don't touch) 2463 var dist = el1.center.distance(el2.center), 2464 r1 = el1.Radius(), 2465 r2 = el2.Radius(), 2466 s = skew(), 2467 rIxnSq = 0.5 * (r1 * r1 + r2 * r2 - 0.5 * dist * dist * (1 + s * s)); 2468 return Math.sqrt(rIxnSq); 2469 } 2470 ]; 2471 }, 2472 2473 /****************************************/ 2474 /**** BEZIER CURVE ALGORITHMS ****/ 2475 /****************************************/ 2476 2477 /** 2478 * Splits a Bezier curve segment defined by four points into 2479 * two Bezier curve segments. Dissection point is t=1/2. 2480 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 2481 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2482 * @returns {Array} Array consisting of two coordinate arrays for Bezier curves. 2483 */ 2484 _bezierSplit: function (curve) { 2485 var p0, p1, p2, p00, p22, p000; 2486 2487 p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5]; 2488 p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5]; 2489 p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5]; 2490 2491 p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5]; 2492 p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5]; 2493 2494 p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5]; 2495 2496 return [ 2497 [curve[0], p0, p00, p000], 2498 [p000, p22, p2, curve[3]] 2499 ]; 2500 }, 2501 2502 /** 2503 * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment 2504 * from its control points. 2505 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 2506 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2507 * @returns {Array} Bounding box [minX, maxY, maxX, minY] 2508 */ 2509 _bezierBbox: function (curve) { 2510 var bb = []; 2511 2512 if (curve.length === 4) { 2513 // bezierDegree == 3 2514 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX 2515 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY 2516 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX 2517 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY 2518 } else { 2519 // bezierDegree == 1 2520 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX 2521 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY 2522 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX 2523 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY 2524 } 2525 2526 return bb; 2527 }, 2528 2529 /** 2530 * Decide if two Bezier curve segments overlap by comparing their bounding boxes. 2531 * @param {Array} bb1 Bounding box of the first Bezier curve segment 2532 * @param {Array} bb2 Bounding box of the second Bezier curve segment 2533 * @returns {Boolean} true if the bounding boxes overlap, false otherwise. 2534 */ 2535 _bezierOverlap: function (bb1, bb2) { 2536 return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1]; 2537 }, 2538 2539 /** 2540 * Append list of intersection points to a list. 2541 * @private 2542 */ 2543 _bezierListConcat: function (L, Lnew, t1, t2) { 2544 var i, 2545 t2exists = Type.exists(t2), 2546 start = 0, 2547 len = Lnew.length, 2548 le = L.length; 2549 2550 if ( 2551 le > 0 && 2552 len > 0 && 2553 ((L[le - 1][1] === 1 && Lnew[0][1] === 0) || 2554 (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0)) 2555 ) { 2556 start = 1; 2557 } 2558 2559 for (i = start; i < len; i++) { 2560 if (t2exists) { 2561 Lnew[i][2] *= 0.5; 2562 Lnew[i][2] += t2; 2563 } 2564 2565 Lnew[i][1] *= 0.5; 2566 Lnew[i][1] += t1; 2567 2568 L.push(Lnew[i]); 2569 } 2570 }, 2571 2572 /** 2573 * Find intersections of two Bezier curve segments by recursive subdivision. 2574 * Below maxlevel determine intersections by intersection line segments. 2575 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 2576 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2577 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 2578 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2579 * @param {Number} level Recursion level 2580 * @returns {Array} List of intersection points (up to nine). Each intersection point is an 2581 * array of length three (homogeneous coordinates) plus preimages. 2582 */ 2583 _bezierMeetSubdivision: function (red, blue, level) { 2584 var bbb, 2585 bbr, 2586 ar, 2587 b0, 2588 b1, 2589 r0, 2590 r1, 2591 m, 2592 p0, 2593 p1, 2594 q0, 2595 q1, 2596 L = [], 2597 maxLev = 5; // Maximum recursion level 2598 2599 bbr = this._bezierBbox(blue); 2600 bbb = this._bezierBbox(red); 2601 2602 if (!this._bezierOverlap(bbr, bbb)) { 2603 return []; 2604 } 2605 2606 if (level < maxLev) { 2607 ar = this._bezierSplit(red); 2608 r0 = ar[0]; 2609 r1 = ar[1]; 2610 2611 ar = this._bezierSplit(blue); 2612 b0 = ar[0]; 2613 b1 = ar[1]; 2614 2615 this._bezierListConcat( 2616 L, 2617 this._bezierMeetSubdivision(r0, b0, level + 1), 2618 0.0, 2619 0.0 2620 ); 2621 this._bezierListConcat( 2622 L, 2623 this._bezierMeetSubdivision(r0, b1, level + 1), 2624 0, 2625 0.5 2626 ); 2627 this._bezierListConcat( 2628 L, 2629 this._bezierMeetSubdivision(r1, b0, level + 1), 2630 0.5, 2631 0.0 2632 ); 2633 this._bezierListConcat( 2634 L, 2635 this._bezierMeetSubdivision(r1, b1, level + 1), 2636 0.5, 2637 0.5 2638 ); 2639 2640 return L; 2641 } 2642 2643 // Make homogeneous coordinates 2644 q0 = [1].concat(red[0]); 2645 q1 = [1].concat(red[3]); 2646 p0 = [1].concat(blue[0]); 2647 p1 = [1].concat(blue[3]); 2648 2649 m = this.meetSegmentSegment(q0, q1, p0, p1); 2650 2651 if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) { 2652 return [m]; 2653 } 2654 2655 return []; 2656 }, 2657 2658 /** 2659 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 2660 */ 2661 _bezierLineMeetSubdivision: function (red, blue, level, testSegment) { 2662 var bbb, bbr, ar, 2663 r0, r1, 2664 m, 2665 p0, p1, q0, q1, 2666 L = [], 2667 maxLev = 5; // Maximum recursion level 2668 2669 bbb = this._bezierBbox(blue); 2670 bbr = this._bezierBbox(red); 2671 2672 if (testSegment && !this._bezierOverlap(bbr, bbb)) { 2673 return []; 2674 } 2675 2676 if (level < maxLev) { 2677 ar = this._bezierSplit(red); 2678 r0 = ar[0]; 2679 r1 = ar[1]; 2680 2681 this._bezierListConcat( 2682 L, 2683 this._bezierLineMeetSubdivision(r0, blue, level + 1), 2684 0.0 2685 ); 2686 this._bezierListConcat( 2687 L, 2688 this._bezierLineMeetSubdivision(r1, blue, level + 1), 2689 0.5 2690 ); 2691 2692 return L; 2693 } 2694 2695 // Make homogeneous coordinates 2696 q0 = [1].concat(red[0]); 2697 q1 = [1].concat(red[3]); 2698 p0 = [1].concat(blue[0]); 2699 p1 = [1].concat(blue[1]); 2700 2701 m = this.meetSegmentSegment(q0, q1, p0, p1); 2702 2703 if (m[1] >= 0.0 && m[1] <= 1.0) { 2704 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) { 2705 return [m]; 2706 } 2707 } 2708 2709 return []; 2710 }, 2711 2712 /** 2713 * Find the nr-th intersection point of two Bezier curve segments. 2714 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 2715 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2716 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 2717 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 2718 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 2719 * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus 2720 * preimages [x,y], t_1, t_2] of the two Bezier curve segments. 2721 * 2722 */ 2723 meetBeziersegmentBeziersegment: function (red, blue, testSegment) { 2724 var L, L2, i; 2725 2726 if (red.length === 4 && blue.length === 4) { 2727 L = this._bezierMeetSubdivision(red, blue, 0); 2728 } else { 2729 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment); 2730 } 2731 2732 L.sort(function (a, b) { 2733 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]); 2734 }); 2735 2736 L2 = []; 2737 for (i = 0; i < L.length; i++) { 2738 // Only push entries different from their predecessor 2739 if (i === 0 || L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2]) { 2740 L2.push(L[i]); 2741 } 2742 } 2743 return L2; 2744 }, 2745 2746 /** 2747 * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3. 2748 * @param {JXG.Curve} red Curve with bezierDegree == 3 2749 * @param {JXG.Curve} blue Curve with bezierDegree == 3 2750 * @param {Number|Function} nr The number of the intersection point which should be returned. 2751 * @returns {Array} The homogeneous coordinates of the nr-th intersection point. 2752 */ 2753 meetBezierCurveRedBlueSegments: function (red, blue, nr) { 2754 var p, i, j, k, 2755 n = Type.evaluate(nr), 2756 po, tmp, 2757 redArr, 2758 blueArr, 2759 bbr, 2760 bbb, 2761 intersections, 2762 startRed = 0, 2763 startBlue = 0, 2764 lenBlue, lenRed, 2765 L = []; 2766 2767 if (blue.numberPoints < blue.bezierDegree + 1 || red.numberPoints < red.bezierDegree + 1) { 2768 return [0, NaN, NaN]; 2769 } 2770 if (red.bezierDegree === 1 && blue.bezierDegree === 3) { 2771 tmp = red; 2772 red = blue; 2773 blue = tmp; 2774 } 2775 2776 lenBlue = blue.numberPoints - blue.bezierDegree; 2777 lenRed = red.numberPoints - red.bezierDegree; 2778 2779 // For sectors, we ignore the "legs" 2780 if (red.type === Const.OBJECT_TYPE_SECTOR) { 2781 startRed = 3; 2782 lenRed -= 3; 2783 } 2784 if (blue.type === Const.OBJECT_TYPE_SECTOR) { 2785 startBlue = 3; 2786 lenBlue -= 3; 2787 } 2788 2789 for (i = startRed; i < lenRed; i += red.bezierDegree) { 2790 p = red.points; 2791 redArr = [p[i].usrCoords.slice(1), p[i + 1].usrCoords.slice(1)]; 2792 if (red.bezierDegree === 3) { 2793 redArr[2] = p[i + 2].usrCoords.slice(1); 2794 redArr[3] = p[i + 3].usrCoords.slice(1); 2795 } 2796 2797 bbr = this._bezierBbox(redArr); 2798 2799 for (j = startBlue; j < lenBlue; j += blue.bezierDegree) { 2800 p = blue.points; 2801 blueArr = [p[j].usrCoords.slice(1), p[j + 1].usrCoords.slice(1)]; 2802 if (blue.bezierDegree === 3) { 2803 blueArr[2] = p[j + 2].usrCoords.slice(1); 2804 blueArr[3] = p[j + 3].usrCoords.slice(1); 2805 } 2806 2807 bbb = this._bezierBbox(blueArr); 2808 if (this._bezierOverlap(bbr, bbb)) { 2809 intersections = this.meetBeziersegmentBeziersegment(redArr, blueArr); 2810 if (intersections.length === 0) { 2811 continue; 2812 } 2813 for (k = 0; k < intersections.length; k++) { 2814 po = intersections[k]; 2815 if ( 2816 po[1] < -Mat.eps || 2817 po[1] > 1 + Mat.eps || 2818 po[2] < -Mat.eps || 2819 po[2] > 1 + Mat.eps 2820 ) { 2821 continue; 2822 } 2823 L.push(po); 2824 } 2825 if (L.length > n) { 2826 return L[n][0]; 2827 } 2828 } 2829 } 2830 } 2831 if (L.length > n) { 2832 return L[n][0]; 2833 } 2834 2835 return [0, NaN, NaN]; 2836 }, 2837 2838 bezierSegmentEval: function (t, curve) { 2839 var f, 2840 x, 2841 y, 2842 t1 = 1.0 - t; 2843 2844 x = 0; 2845 y = 0; 2846 2847 f = t1 * t1 * t1; 2848 x += f * curve[0][0]; 2849 y += f * curve[0][1]; 2850 2851 f = 3.0 * t * t1 * t1; 2852 x += f * curve[1][0]; 2853 y += f * curve[1][1]; 2854 2855 f = 3.0 * t * t * t1; 2856 x += f * curve[2][0]; 2857 y += f * curve[2][1]; 2858 2859 f = t * t * t; 2860 x += f * curve[3][0]; 2861 y += f * curve[3][1]; 2862 2863 return [1.0, x, y]; 2864 }, 2865 2866 /** 2867 * Generate the defining points of a 3rd degree bezier curve that approximates 2868 * a circle sector defined by three coordinate points A, B, C, each defined by an array of length three. 2869 * The coordinate arrays are given in homogeneous coordinates. 2870 * @param {Array} A First point 2871 * @param {Array} B Second point (intersection point) 2872 * @param {Array} C Third point 2873 * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve. 2874 * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1. 2875 */ 2876 bezierArc: function (A, B, C, withLegs, sgn) { 2877 var p1, p2, p3, p4, 2878 r, 2879 phi, beta, delta, 2880 // PI2 = Math.PI * 0.5, 2881 x = B[1], 2882 y = B[2], 2883 z = B[0], 2884 dataX = [], 2885 dataY = [], 2886 co, si, 2887 ax, ay, 2888 bx, by, 2889 k, v, d, 2890 matrix; 2891 2892 r = this.distance(B, A); 2893 2894 // x,y, z is intersection point. Normalize it. 2895 x /= z; 2896 y /= z; 2897 2898 phi = this.rad(A.slice(1), B.slice(1), C.slice(1)); 2899 if (sgn === -1) { 2900 phi = 2 * Math.PI - phi; 2901 } 2902 2903 // Always divide the arc into four Bezier arcs. 2904 // Otherwise, the position of gliders on this arc 2905 // will be wrong. 2906 delta = phi / 4; 2907 2908 2909 p1 = A; 2910 p1[1] /= p1[0]; 2911 p1[2] /= p1[0]; 2912 p1[0] /= p1[0]; 2913 2914 p4 = p1.slice(0); 2915 2916 if (withLegs) { 2917 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]]; 2918 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]]; 2919 } else { 2920 dataX = [p1[1]]; 2921 dataY = [p1[2]]; 2922 } 2923 2924 while (phi > Mat.eps) { 2925 // if (phi > PI2) { 2926 // beta = PI2; 2927 // phi -= PI2; 2928 // } else { 2929 // beta = phi; 2930 // phi = 0; 2931 // } 2932 if (phi > delta) { 2933 beta = delta; 2934 phi -= delta; 2935 } else { 2936 beta = phi; 2937 phi = 0; 2938 } 2939 2940 co = Math.cos(sgn * beta); 2941 si = Math.sin(sgn * beta); 2942 2943 matrix = [ 2944 [1, 0, 0], 2945 [x * (1 - co) + y * si, co, -si], 2946 [y * (1 - co) - x * si, si, co] 2947 ]; 2948 v = Mat.matVecMult(matrix, p1); 2949 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]]; 2950 2951 ax = p1[1] - x; 2952 ay = p1[2] - y; 2953 bx = p4[1] - x; 2954 by = p4[2] - y; 2955 d = Mat.hypot(ax + bx, ay + by); 2956 2957 if (Math.abs(by - ay) > Mat.eps) { 2958 k = ((((ax + bx) * (r / d - 0.5)) / (by - ay)) * 8) / 3; 2959 } else { 2960 k = ((((ay + by) * (r / d - 0.5)) / (ax - bx)) * 8) / 3; 2961 } 2962 2963 p2 = [1, p1[1] - k * ay, p1[2] + k * ax]; 2964 p3 = [1, p4[1] + k * by, p4[2] - k * bx]; 2965 2966 Type.concat(dataX, [p2[1], p3[1], p4[1]]); 2967 Type.concat(dataY, [p2[2], p3[2], p4[2]]); 2968 p1 = p4.slice(0); 2969 } 2970 2971 if (withLegs) { 2972 Type.concat(dataX, [ 2973 p4[1] + 0.333 * (x - p4[1]), 2974 p4[1] + 0.666 * (x - p4[1]), 2975 x 2976 ]); 2977 Type.concat(dataY, [ 2978 p4[2] + 0.333 * (y - p4[2]), 2979 p4[2] + 0.666 * (y - p4[2]), 2980 y 2981 ]); 2982 } 2983 2984 return [dataX, dataY]; 2985 }, 2986 2987 /****************************************/ 2988 /**** PROJECTIONS ****/ 2989 /****************************************/ 2990 2991 /** 2992 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 2993 * nearest one of the two intersection points of the line through the given point and the circles 2994 * center. 2995 * @param {JXG.Point|JXG.Coords} point Point to project or coords object to project. 2996 * @param {JXG.Circle} circle Circle on that the point is projected. 2997 * @param {JXG.Board} [board=point.board] Reference to the board 2998 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2999 */ 3000 projectPointToCircle: function (point, circle, board) { 3001 var dist, 3002 P, 3003 x, 3004 y, 3005 factor, 3006 M = circle.center.coords.usrCoords; 3007 3008 if (!Type.exists(board)) { 3009 board = point.board; 3010 } 3011 3012 // gave us a point 3013 if (Type.isPoint(point)) { 3014 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords); 3015 P = point.coords.usrCoords; 3016 // gave us coords 3017 } else { 3018 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords); 3019 P = point.usrCoords; 3020 } 3021 3022 if (Math.abs(dist) < Mat.eps) { 3023 dist = Mat.eps; 3024 } 3025 3026 factor = circle.Radius() / dist; 3027 x = M[1] + factor * (P[1] - M[1]); 3028 y = M[2] + factor * (P[2] - M[2]); 3029 3030 return new Coords(Const.COORDS_BY_USER, [x, y], board); 3031 }, 3032 3033 /** 3034 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 3035 * intersection point of the given line and its perpendicular through the given point. 3036 * @param {JXG.Point|JXG.Coords} point Point to project. 3037 * @param {JXG.Line} line Line on that the point is projected. 3038 * @param {JXG.Board} [board=point.board|board=line.board] Reference to a board. 3039 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 3040 */ 3041 projectPointToLine: function (point, line, board) { 3042 var v = [0, line.stdform[1], line.stdform[2]], 3043 coords; 3044 3045 if (!Type.exists(board)) { 3046 if (Type.exists(point.coords)) { 3047 board = point.board; 3048 } else { 3049 board = line.board; 3050 } 3051 } 3052 3053 if (Type.exists(point.coords)) { 3054 coords = point.coords.usrCoords; 3055 } else { 3056 coords = point.usrCoords; 3057 } 3058 3059 v = Mat.crossProduct(v, coords); 3060 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(v, line.stdform), board); 3061 }, 3062 3063 /** 3064 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 3065 * segment defined by two coordinate arrays. 3066 * @param {Array} p Point to project. 3067 * @param {Array} q1 Start point of the line segment on that the point is projected. 3068 * @param {Array} q2 End point of the line segment on that the point is projected. 3069 * @returns {Array} The coordinates of the projection of the given point on the given segment 3070 * and the factor that determines the projected point as a convex combination of the 3071 * two endpoints q1 and q2 of the segment. 3072 */ 3073 projectCoordsToSegment: function (p, q1, q2) { 3074 var t, 3075 denom, 3076 s = [q2[1] - q1[1], q2[2] - q1[2]], 3077 v = [p[1] - q1[1], p[2] - q1[2]]; 3078 3079 /** 3080 * If the segment has length 0, i.e. is a point, 3081 * the projection is equal to that point. 3082 */ 3083 if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) { 3084 return [q1, 0]; 3085 } 3086 3087 t = Mat.innerProduct(v, s); 3088 denom = Mat.innerProduct(s, s); 3089 t /= denom; 3090 3091 return [[1, t * s[0] + q1[1], t * s[1] + q1[2]], t]; 3092 }, 3093 3094 /** 3095 * Finds the coordinates of the closest point on a Bezier segment of a 3096 * {@link JXG.Curve} to a given coordinate array. 3097 * @param {Array} pos Point to project in homogeneous coordinates. 3098 * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3. 3099 * @param {Number} start Number of the Bezier segment of the curve. 3100 * @returns {Array} The coordinates of the projection of the given point 3101 * on the given Bezier segment and the preimage of the curve which 3102 * determines the closest point. 3103 */ 3104 projectCoordsToBeziersegment: function (pos, curve, start) { 3105 var t0, 3106 /** @ignore */ 3107 minfunc = function (t) { 3108 var z = [1, curve.X(start + t), curve.Y(start + t)]; 3109 3110 z[1] -= pos[1]; 3111 z[2] -= pos[2]; 3112 3113 return z[1] * z[1] + z[2] * z[2]; 3114 }; 3115 3116 t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]); 3117 3118 return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0]; 3119 }, 3120 3121 /** 3122 * Calculates the coordinates of the projection of a given point on a given curve. 3123 * Uses {@link JXG.Math.Geometry.projectCoordsToCurve}. 3124 * 3125 * @param {JXG.Point} point Point to project. 3126 * @param {JXG.Curve} curve Curve on that the point is projected. 3127 * @param {JXG.Board} [board=point.board] Reference to a board. 3128 * @see #projectCoordsToCurve 3129 * @returns {Array} [JXG.Coords, position] The coordinates of the projection of the given 3130 * point on the given graph and the relative position on the curve (real number). 3131 */ 3132 projectPointToCurve: function (point, curve, board) { 3133 if (!Type.exists(board)) { 3134 board = point.board; 3135 } 3136 3137 var x = point.X(), 3138 y = point.Y(), 3139 t = point.position, 3140 result; 3141 3142 if (!Type.exists(t)) { 3143 t = Type.evaluate(curve.visProp.curvetype) === 'functiongraph' ? x : 0.0; 3144 } 3145 result = this.projectCoordsToCurve(x, y, t, curve, board); 3146 // point.position = result[1]; 3147 3148 return result; 3149 }, 3150 3151 /** 3152 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 3153 * function graphs this is the 3154 * intersection point of the curve and the parallel to y-axis through the given point. 3155 * @param {Number} x coordinate to project. 3156 * @param {Number} y coordinate to project. 3157 * @param {Number} t start value for newtons method 3158 * @param {JXG.Curve} curve Curve on that the point is projected. 3159 * @param {JXG.Board} [board=curve.board] Reference to a board. 3160 * @see #projectPointToCurve 3161 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given curve and 3162 * the position on the curve. 3163 */ 3164 projectCoordsToCurve: function (x, y, t, curve, board) { 3165 var newCoords, newCoordsObj, 3166 i, j, mindist, dist, lbda, 3167 v, coords, d, p1, p2, res, minfunc, 3168 t_new, f_new, f_old, dy, 3169 delta, delta1, delta2, steps, 3170 minX, maxX, minX_glob, maxX_glob, 3171 infty = Number.POSITIVE_INFINITY; 3172 3173 if (!Type.exists(board)) { 3174 board = curve.board; 3175 } 3176 3177 if (Type.evaluate(curve.visProp.curvetype) === "plot") { 3178 t = 0; 3179 mindist = infty; 3180 if (curve.numberPoints === 0) { 3181 newCoords = [0, 1, 1]; 3182 } else { 3183 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 3184 } 3185 3186 if (curve.numberPoints > 1) { 3187 v = [1, x, y]; 3188 if (curve.bezierDegree === 3) { 3189 j = 0; 3190 } else { 3191 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 3192 } 3193 for (i = 0; i < curve.numberPoints - 1; i++) { 3194 if (curve.bezierDegree === 3) { 3195 res = this.projectCoordsToBeziersegment(v, curve, j); 3196 } else { 3197 p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)]; 3198 res = this.projectCoordsToSegment(v, p1, p2); 3199 } 3200 lbda = res[1]; 3201 coords = res[0]; 3202 3203 if (0.0 <= lbda && lbda <= 1.0) { 3204 dist = this.distance(coords, v); 3205 d = i + lbda; 3206 } else if (lbda < 0.0) { 3207 coords = p1; 3208 dist = this.distance(p1, v); 3209 d = i; 3210 } else if (lbda > 1.0 && i === curve.numberPoints - 2) { 3211 coords = p2; 3212 dist = this.distance(coords, v); 3213 d = curve.numberPoints - 1; 3214 } 3215 3216 if (dist < mindist) { 3217 mindist = dist; 3218 t = d; 3219 newCoords = coords; 3220 } 3221 3222 if (curve.bezierDegree === 3) { 3223 j++; 3224 i += 2; 3225 } else { 3226 p1 = p2; 3227 } 3228 } 3229 } 3230 3231 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board); 3232 } else { 3233 // 'parameter', 'polar', 'functiongraph' 3234 3235 minX_glob = curve.minX(); 3236 maxX_glob = curve.maxX(); 3237 minX = minX_glob; 3238 maxX = maxX_glob; 3239 3240 if (Type.evaluate(curve.visProp.curvetype) === 'functiongraph') { 3241 // Restrict the possible position of t 3242 // to the projection of a circle to the x-axis (= t-axis) 3243 dy = Math.abs(y - curve.Y(x)); 3244 if (!isNaN(dy)) { 3245 minX = x - dy; 3246 maxX = x + dy; 3247 } 3248 } 3249 3250 /** 3251 * @ignore 3252 * Find t such that the Euclidean distance between 3253 * [x, y] and [curve.X(t), curve.Y(t)] 3254 * is minimized. 3255 */ 3256 minfunc = function (t) { 3257 var dx, dy; 3258 3259 if (t < minX_glob || t > curve.maxX_glob) { 3260 return Infinity; 3261 } 3262 dx = x - curve.X(t); 3263 dy = y - curve.Y(t); 3264 return dx * dx + dy * dy; 3265 }; 3266 3267 // Search t which minimizes minfunc(t) 3268 // in discrete steps 3269 f_old = minfunc(t); 3270 steps = 50; 3271 delta = (maxX - minX) / steps; 3272 t_new = minX; 3273 for (i = 0; i < steps; i++) { 3274 f_new = minfunc(t_new); 3275 3276 if (f_new < f_old || f_old === Infinity || isNaN(f_old)) { 3277 t = t_new; 3278 f_old = f_new; 3279 } 3280 3281 t_new += delta; 3282 } 3283 3284 // t = Numerics.root(Numerics.D(minfunc), t); 3285 3286 // Ensure that minfunc is defined on the 3287 // enclosing interval [t-delta1, t+delta2] 3288 delta1 = delta; 3289 for (i = 0; i < 20 && isNaN(minfunc(t - delta1)); i++, delta1 *= 0.5); 3290 if (isNaN(minfunc(t - delta1))) { 3291 delta1 = 0.0; 3292 } 3293 delta2 = delta; 3294 for (i = 0; i < 20 && isNaN(minfunc(t + delta2)); i++, delta2 *= 0.5); 3295 if (isNaN(minfunc(t + delta2))) { 3296 delta2 = 0.0; 3297 } 3298 3299 // Finally, apply mathemetical optimization in the determined interval 3300 t = Numerics.fminbr(minfunc, [ 3301 Math.max(t - delta1, minX), 3302 Math.min(t + delta2, maxX) 3303 ]); 3304 3305 // Distinction between closed and open curves is not necessary. 3306 // If closed, the cyclic projection shift will work anyhow 3307 // if (Math.abs(curve.X(minX) - curve.X(maxX)) < Mat.eps && 3308 // Math.abs(curve.Y(minX) - curve.Y(maxX)) < Mat.eps) { 3309 // // Cyclically 3310 // if (t < minX) {console.log(t) 3311 // t = maxX + t - minX; 3312 // } 3313 // if (t > maxX) { 3314 // t = minX + t - maxX; 3315 // } 3316 // } else { 3317 3318 t = t < minX_glob ? minX_glob : t; 3319 t = t > maxX_glob ? maxX_glob : t; 3320 // } 3321 3322 newCoordsObj = new Coords( 3323 Const.COORDS_BY_USER, 3324 [curve.X(t), curve.Y(t)], 3325 board 3326 ); 3327 } 3328 3329 return [curve.updateTransform(newCoordsObj), t]; 3330 }, 3331 3332 /** 3333 * Calculates the coordinates of the closest orthogonal projection of a given coordinate array onto the 3334 * border of a polygon. 3335 * @param {Array} p Point to project. 3336 * @param {JXG.Polygon} pol Polygon element 3337 * @returns {Array} The coordinates of the closest projection of the given point to the border of the polygon. 3338 */ 3339 projectCoordsToPolygon: function (p, pol) { 3340 var i, 3341 len = pol.vertices.length, 3342 d_best = Infinity, 3343 d, 3344 projection, 3345 proj, 3346 bestprojection; 3347 3348 for (i = 0; i < len - 1; i++) { 3349 projection = JXG.Math.Geometry.projectCoordsToSegment( 3350 p, 3351 pol.vertices[i].coords.usrCoords, 3352 pol.vertices[i + 1].coords.usrCoords 3353 ); 3354 3355 if (0 <= projection[1] && projection[1] <= 1) { 3356 d = JXG.Math.Geometry.distance(projection[0], p, 3); 3357 proj = projection[0]; 3358 } else if (projection[1] < 0) { 3359 d = JXG.Math.Geometry.distance(pol.vertices[i].coords.usrCoords, p, 3); 3360 proj = pol.vertices[i].coords.usrCoords; 3361 } else { 3362 d = JXG.Math.Geometry.distance(pol.vertices[i + 1].coords.usrCoords, p, 3); 3363 proj = pol.vertices[i + 1].coords.usrCoords; 3364 } 3365 if (d < d_best) { 3366 bestprojection = proj.slice(0); 3367 d_best = d; 3368 } 3369 } 3370 return bestprojection; 3371 }, 3372 3373 /** 3374 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 3375 * one or more curves of curveType 'plot'. Uses {@link JXG.Math.Geometry.projectPointToCurve}. 3376 * @param {JXG.Point} point Point to project. 3377 * @param {JXG.Turtle} turtle on that the point is projected. 3378 * @param {JXG.Board} [board=point.board] Reference to a board. 3379 * @returns {Array} [JXG.Coords, position] Array containing the coordinates of the projection of the given point on the turtle and 3380 * the position on the turtle. 3381 */ 3382 projectPointToTurtle: function (point, turtle, board) { 3383 var newCoords, 3384 t, 3385 x, 3386 y, 3387 i, 3388 dist, 3389 el, 3390 minEl, 3391 res, 3392 newPos, 3393 np = 0, 3394 npmin = 0, 3395 mindist = Number.POSITIVE_INFINITY, 3396 len = turtle.objects.length; 3397 3398 if (!Type.exists(board)) { 3399 board = point.board; 3400 } 3401 3402 // run through all curves of this turtle 3403 for (i = 0; i < len; i++) { 3404 el = turtle.objects[i]; 3405 3406 if (el.elementClass === Const.OBJECT_CLASS_CURVE) { 3407 res = this.projectPointToCurve(point, el); 3408 newCoords = res[0]; 3409 newPos = res[1]; 3410 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 3411 3412 if (dist < mindist) { 3413 x = newCoords.usrCoords[1]; 3414 y = newCoords.usrCoords[2]; 3415 t = newPos; 3416 mindist = dist; 3417 minEl = el; 3418 npmin = np; 3419 } 3420 np += el.numberPoints; 3421 } 3422 } 3423 3424 newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board); 3425 // point.position = t + npmin; 3426 // return minEl.updateTransform(newCoords); 3427 return [minEl.updateTransform(newCoords), t + npmin]; 3428 }, 3429 3430 /** 3431 * Trivial projection of a point to another point. 3432 * @param {JXG.Point} point Point to project (not used). 3433 * @param {JXG.Point} dest Point on that the point is projected. 3434 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 3435 */ 3436 projectPointToPoint: function (point, dest) { 3437 return dest.coords; 3438 }, 3439 3440 /** 3441 * 3442 * @param {JXG.Point|JXG.Coords} point 3443 * @param {JXG.Board} [board] 3444 */ 3445 projectPointToBoard: function (point, board) { 3446 var i, 3447 l, 3448 c, 3449 brd = board || point.board, 3450 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx 3451 config = [ 3452 // left 3453 [1, 1, 0, 0, 3, 0, 1], 3454 // top 3455 [-1, 2, 1, 0, 1, 2, 1], 3456 // right 3457 [-1, 1, 2, 2, 1, 2, 3], 3458 // bottom 3459 [1, 2, 3, 0, 3, 2, 3] 3460 ], 3461 coords = point.coords || point, 3462 bbox = brd.getBoundingBox(); 3463 3464 for (i = 0; i < 4; i++) { 3465 c = config[i]; 3466 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) { 3467 // define border 3468 l = Mat.crossProduct( 3469 [1, bbox[c[3]], bbox[c[4]]], 3470 [1, bbox[c[5]], bbox[c[6]]] 3471 ); 3472 l[3] = 0; 3473 l = Mat.normalize(l); 3474 3475 // project point 3476 coords = this.projectPointToLine({ coords: coords }, { stdform: l }, brd); 3477 } 3478 } 3479 3480 return coords; 3481 }, 3482 3483 /** 3484 * Given a the coordinates of a point, finds the nearest point on the given 3485 * parametric curve or surface, and returns its view-space coordinates. 3486 * @param {Array} pScr Screen coordinates to project. 3487 * @param {JXG.Curve3D|JXG.Surface3D} target Parametric curve or surface to project to. 3488 * @param {Array} params Parameters of point on the target, initially specifying the starting point of 3489 * the search. The parameters are modified in place during the search, ending up at the nearest point. 3490 * @returns {Array} Array of length 4 containing the coordinates of the nearest point on the curve or surface. 3491 */ 3492 projectCoordsToParametric: function (p, target, params) { 3493 // The variables and parameters for the Cobyla constrained 3494 // minimization algorithm are explained in the Cobyla.js comments 3495 var rhobeg, // initial size of simplex (Cobyla) 3496 rhoend, // finial size of simplex (Cobyla) 3497 iprint = 0, // no console output (Cobyla) 3498 maxfun = 200, // call objective function at most 200 times (Cobyla) 3499 dim = params.length, 3500 _minFunc; // objective function (Cobyla) 3501 3502 // adapt simplex size to parameter range 3503 if (dim === 1) { 3504 rhobeg = 0.1 * (target.range[1] - target.range[0]); 3505 } else if (dim === 2) { 3506 rhobeg = 0.1 * Math.min( 3507 target.range_u[1] - target.range_u[0], 3508 target.range_v[1] - target.range_v[0] 3509 ); 3510 } 3511 rhoend = rhobeg / 5e6; 3512 3513 // minimize screen distance to cursor 3514 _minFunc = function (n, m, w, con) { 3515 // var xDiff = p[0] - target.X(...w), 3516 // yDiff = p[1] - target.Y(...w), 3517 // zDiff = p[2] - target.Z(...w); 3518 var xDiff = p[0] - target.X.apply(null, w), 3519 yDiff = p[1] - target.Y.apply(null, w), 3520 zDiff = p[2] - target.Z.apply(null, w); 3521 3522 if (n === 1) { 3523 con[0] = w[0] - target.range[0]; 3524 con[1] = -w[0] + target.range[1]; 3525 } else if (n === 2) { 3526 con[0] = w[0] - target.range_u[0]; 3527 con[1] = -w[0] + target.range_u[1]; 3528 con[2] = w[1] - target.range_v[0]; 3529 con[3] = -w[1] + target.range_v[1]; 3530 } 3531 return xDiff * xDiff + yDiff * yDiff + zDiff * zDiff; 3532 }; 3533 Mat.Nlp.FindMinimum(_minFunc, dim, 2 * dim, params, rhobeg, rhoend, iprint, maxfun); 3534 3535 // return [1, target.X(...params), target.Y(...params), target.Z(...params)]; 3536 return [1, target.X.apply(null, params), target.Y.apply(null, params), target.Z.apply(null, params)]; 3537 }, 3538 3539 /** 3540 * Given a the screen coordinates of a point, finds the point on the 3541 * given parametric curve or surface which is nearest in screen space, 3542 * and returns its view-space coordinates. 3543 * @param {Array} pScr Screen coordinates to project. 3544 * @param {JXG.Curve3D|JXG.Surface3D} target Parametric curve or surface to project to. 3545 * @param {Array} params Parameters of point on the target, initially specifying the starting point of 3546 * the search. The parameters are modified in place during the search, ending up at the nearest point. 3547 * @returns {Array} Array of length 4 containing the coordinates of the nearest point on the curve or surface. 3548 */ 3549 projectScreenCoordsToParametric: function (pScr, target, params) { 3550 // The variables and parameters for the Cobyla constrained 3551 // minimization algorithm are explained in the Cobyla.js comments 3552 var rhobeg, // initial size of simplex (Cobyla) 3553 rhoend, // finial size of simplex (Cobyla) 3554 iprint = 0, // no console output (Cobyla) 3555 maxfun = 200, // call objective function at most 200 times (Cobyla) 3556 dim = params.length, 3557 _minFunc; // objective function (Cobyla) 3558 3559 // adapt simplex size to parameter range 3560 if (dim === 1) { 3561 rhobeg = 0.1 * (target.range[1] - target.range[0]); 3562 } else if (dim === 2) { 3563 rhobeg = 0.1 * Math.min( 3564 target.range_u[1] - target.range_u[0], 3565 target.range_v[1] - target.range_v[0] 3566 ); 3567 } 3568 rhoend = rhobeg / 5e6; 3569 3570 // minimize screen distance to cursor 3571 _minFunc = function (n, m, w, con) { 3572 // var c3d = [ 3573 // 1, 3574 // target.X(...w), 3575 // target.Y(...w), 3576 // target.Z(...w) 3577 // ], 3578 var c3d = [ 3579 1, 3580 target.X.apply(null, w), 3581 target.Y.apply(null, w), 3582 target.Z.apply(null, w) 3583 ], 3584 c2d = target.view.project3DTo2D(c3d), 3585 xDiff = pScr[0] - c2d[1], 3586 yDiff = pScr[1] - c2d[2]; 3587 3588 if (n === 1) { 3589 con[0] = w[0] - target.range[0]; 3590 con[1] = -w[0] + target.range[1]; 3591 } else if (n === 2) { 3592 con[0] = w[0] - target.range_u[0]; 3593 con[1] = -w[0] + target.range_u[1]; 3594 con[2] = w[1] - target.range_v[0]; 3595 con[3] = -w[1] + target.range_v[1]; 3596 } 3597 return xDiff * xDiff + yDiff * yDiff; 3598 }; 3599 Mat.Nlp.FindMinimum(_minFunc, dim, 2 * dim, params, rhobeg, rhoend, iprint, maxfun); 3600 3601 // return [1, target.X(...params), target.Y(...params), target.Z(...params)]; 3602 return [1, target.X.apply(null, params), target.Y.apply(null, params), target.Z.apply(null, params)]; 3603 }, 3604 3605 /** 3606 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 3607 * coordinates. For lines this can be line.stdform. 3608 * @param {Array} point Homogeneous coordinates of a point. 3609 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 3610 * @returns {Number} Distance of the point to the line. 3611 */ 3612 distPointLine: function (point, line) { 3613 var a = line[1], 3614 b = line[2], 3615 c = line[0], 3616 nom; 3617 3618 if (Math.abs(a) + Math.abs(b) < Mat.eps) { 3619 return Number.POSITIVE_INFINITY; 3620 } 3621 3622 nom = a * point[1] + b * point[2] + c; 3623 a *= a; 3624 b *= b; 3625 3626 return Math.abs(nom) / Math.sqrt(a + b); 3627 }, 3628 3629 /** 3630 * Determine the (Euclidean) distance between a point q and a line segment 3631 * defined by two points p1 and p2. In case p1 equals p2, the distance to this 3632 * point is returned. 3633 * 3634 * @param {Array} q Homogeneous coordinates of q 3635 * @param {Array} p1 Homogeneous coordinates of p1 3636 * @param {Array} p2 Homogeneous coordinates of p2 3637 * @returns {Number} Distance of q to line segment [p1, p2] 3638 */ 3639 distPointSegment: function (q, p1, p2) { 3640 var x, y, dx, dy, 3641 den, lbda, 3642 eps = Mat.eps * Mat.eps, 3643 huge = 1000000; 3644 3645 // Difference q - p1 3646 x = q[1] - p1[1]; 3647 y = q[2] - p1[2]; 3648 x = (x === Infinity) ? huge : (x === -Infinity) ? -huge : x; 3649 y = (y === Infinity) ? huge : (y === -Infinity) ? -huge : y; 3650 3651 // Difference p2 - p1 3652 dx = p2[1] - p1[1]; 3653 dy = p2[2] - p1[2]; 3654 dx = (dx === Infinity) ? huge : (dx === -Infinity) ? -huge : dx; 3655 dy = (dy === Infinity) ? huge : (dy === -Infinity) ? -huge : dy; 3656 3657 // If den==0 then p1 and p2 are identical 3658 // In this case the distance to p1 is returned 3659 den = dx * dx + dy * dy; 3660 if (den > eps) { 3661 lbda = (x * dx + y * dy) / den; 3662 if (lbda < 0.0) { 3663 lbda = 0.0; 3664 } else if (lbda > 1.0) { 3665 lbda = 1.0; 3666 } 3667 x -= lbda * dx; 3668 y -= lbda * dy; 3669 } 3670 3671 return Mat.hypot(x, y); 3672 }, 3673 3674 /** 3675 * Helper function to create curve which displays a Reuleaux polygons. 3676 * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically, 3677 * these point list is the array vertices of a regular polygon. 3678 * @param {Number} nr Number of vertices 3679 * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values 3680 * for the start and the end of the paramtric curve. array may be used as parent array of a 3681 * {@link JXG.Curve}. 3682 * 3683 * @example 3684 * var A = brd.create('point',[-2,-2]); 3685 * var B = brd.create('point',[0,1]); 3686 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 3687 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 3688 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 3689 * 3690 * </pre><div class="jxgbox" id="JXG2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div> 3691 * <script type="text/javascript"> 3692 * var brd = JXG.JSXGraph.initBoard('JXG2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false}); 3693 * var A = brd.create('point',[-2,-2]); 3694 * var B = brd.create('point',[0,1]); 3695 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 3696 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 3697 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 3698 * </script><pre> 3699 */ 3700 reuleauxPolygon: function (points, nr) { 3701 var beta, 3702 pi2 = Math.PI * 2, 3703 pi2_n = pi2 / nr, 3704 diag = (nr - 1) / 2, 3705 d = 0, 3706 makeFct = function (which, trig) { 3707 return function (t, suspendUpdate) { 3708 var t1 = ((t % pi2) + pi2) % pi2, 3709 j = Math.floor(t1 / pi2_n) % nr; 3710 3711 if (!suspendUpdate) { 3712 d = points[0].Dist(points[diag]); 3713 beta = Mat.Geometry.rad( 3714 [points[0].X() + 1, points[0].Y()], 3715 points[0], 3716 points[diag % nr] 3717 ); 3718 } 3719 3720 if (isNaN(j)) { 3721 return j; 3722 } 3723 3724 t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta; 3725 3726 return points[j][which]() + d * Math[trig](t1); 3727 }; 3728 }; 3729 3730 return [makeFct("X", "cos"), makeFct("Y", "sin"), 0, pi2]; 3731 }, 3732 3733 meet3Planes: function (n1, d1, n2, d2, n3, d3) { 3734 var p = [0, 0, 0], 3735 n31, 3736 n12, 3737 n23, 3738 denom, 3739 i; 3740 3741 n31 = Mat.crossProduct(n3, n1); 3742 n12 = Mat.crossProduct(n1, n2); 3743 n23 = Mat.crossProduct(n2, n3); 3744 denom = Mat.innerProduct(n1, n23, 3); 3745 for (i = 0; i < 3; i++) { 3746 p[i] = (d1 * n23[i] + d2 * n31[i] + d3 * n12[i]) / denom; 3747 } 3748 return p; 3749 }, 3750 3751 meetPlanePlane: function (v11, v12, v21, v22) { 3752 var i, 3753 no1, 3754 no2, 3755 v = [0, 0, 0], 3756 w = [0, 0, 0]; 3757 3758 for (i = 0; i < 3; i++) { 3759 v[i] = Type.evaluate(v11[i]); 3760 w[i] = Type.evaluate(v12[i]); 3761 } 3762 no1 = Mat.crossProduct(v, w); 3763 3764 for (i = 0; i < 3; i++) { 3765 v[i] = Type.evaluate(v21[i]); 3766 w[i] = Type.evaluate(v22[i]); 3767 } 3768 no2 = Mat.crossProduct(v, w); 3769 3770 return Mat.crossProduct(no1, no2); 3771 }, 3772 3773 project3DTo3DPlane: function (point, normal, foot) { 3774 // TODO: homogeneous 3D coordinates 3775 var sol = [0, 0, 0], 3776 le, 3777 d1, 3778 d2, 3779 lbda; 3780 3781 foot = foot || [0, 0, 0]; 3782 3783 le = Mat.norm(normal); 3784 d1 = Mat.innerProduct(point, normal, 3); 3785 d2 = Mat.innerProduct(foot, normal, 3); 3786 // (point - lbda * normal / le) * normal / le == foot * normal / le 3787 // => (point * normal - foot * normal) == lbda * le 3788 lbda = (d1 - d2) / le; 3789 sol = Mat.axpy(-lbda, normal, point); 3790 3791 return sol; 3792 }, 3793 3794 getPlaneBounds: function (v1, v2, q, s, e) { 3795 var s1, s2, e1, e2, mat, rhs, sol; 3796 3797 if (v1[2] + v2[0] !== 0) { 3798 mat = [ 3799 [v1[0], v2[0]], 3800 [v1[1], v2[1]] 3801 ]; 3802 rhs = [s - q[0], s - q[1]]; 3803 3804 sol = Numerics.Gauss(mat, rhs); 3805 s1 = sol[0]; 3806 s2 = sol[1]; 3807 3808 rhs = [e - q[0], e - q[1]]; 3809 sol = Numerics.Gauss(mat, rhs); 3810 e1 = sol[0]; 3811 e2 = sol[1]; 3812 return [s1, e1, s2, e2]; 3813 } 3814 return null; 3815 } 3816 } 3817 ); 3818 3819 export default Mat.Geometry; 3820