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