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