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