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