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