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