1 /* 2 Copyright 2008-2015 3 Matthias Ehmann, 4 Michael Gerhaeuser, 5 Carsten Miller, 6 Bianca Valentin, 7 Alfred Wassermann, 8 Peter Wilfahrt 9 10 This file is part of JSXGraph. 11 12 JSXGraph is free software dual licensed under the GNU LGPL or MIT License. 13 14 You can redistribute it and/or modify it under the terms of the 15 16 * GNU Lesser General Public License as published by 17 the Free Software Foundation, either version 3 of the License, or 18 (at your option) any later version 19 OR 20 * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT 21 22 JSXGraph is distributed in the hope that it will be useful, 23 but WITHOUT ANY WARRANTY; without even the implied warranty of 24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 25 GNU Lesser General Public License for more details. 26 27 You should have received a copy of the GNU Lesser General Public License and 28 the MIT License along with JSXGraph. If not, see <http://www.gnu.org/licenses/> 29 and <http://opensource.org/licenses/MIT/>. 30 */ 31 32 33 /*global JXG: true, define: true*/ 34 /*jslint nomen: true, plusplus: true*/ 35 36 /* depends: 37 jxg 38 base/constants 39 base/coords 40 math/math 41 math/numerics 42 utils/type 43 */ 44 45 /** 46 * @fileoverview This file contains the Math.Geometry namespace for calculating algebraic/geometric 47 * stuff like intersection points, angles, midpoint, and so on. 48 */ 49 50 define([ 51 'jxg', 'base/constants', 'base/coords', 'math/math', 'math/numerics', 'utils/type', 'utils/expect' 52 ], function (JXG, Const, Coords, Mat, Numerics, Type, Expect) { 53 54 "use strict"; 55 56 /** 57 * Math.Geometry namespace definition 58 * @name JXG.Math.Geometry 59 * @namespace 60 */ 61 Mat.Geometry = {}; 62 63 // the splitting is necessary due to the shortcut for the circumcircleMidpoint method to circumcenter. 64 65 JXG.extend(Mat.Geometry, /** @lends JXG.Math.Geometry */ { 66 /****************************************/ 67 /**** GENERAL GEOMETRIC CALCULATIONS ****/ 68 /****************************************/ 69 70 /** 71 * Calculates the angle defined by the points A, B, C. 72 * @param {JXG.Point,Array} A A point or [x,y] array. 73 * @param {JXG.Point,Array} B Another point or [x,y] array. 74 * @param {JXG.Point,Array} C A circle - no, of course the third point or [x,y] array. 75 * @deprecated Use {@link JXG.Math.Geometry#rad} instead. 76 * @see #rad 77 * @see #trueAngle 78 * @returns {Number} The angle in radian measure. 79 */ 80 angle: function (A, B, C) { 81 var u, v, s, t, 82 a = [], 83 b = [], 84 c = []; 85 86 if (A.coords) { 87 a[0] = A.coords.usrCoords[1]; 88 a[1] = A.coords.usrCoords[2]; 89 } else { 90 a[0] = A[0]; 91 a[1] = A[1]; 92 } 93 94 if (B.coords) { 95 b[0] = B.coords.usrCoords[1]; 96 b[1] = B.coords.usrCoords[2]; 97 } else { 98 b[0] = B[0]; 99 b[1] = B[1]; 100 } 101 102 if (C.coords) { 103 c[0] = C.coords.usrCoords[1]; 104 c[1] = C.coords.usrCoords[2]; 105 } else { 106 c[0] = C[0]; 107 c[1] = C[1]; 108 } 109 110 u = a[0] - b[0]; 111 v = a[1] - b[1]; 112 s = c[0] - b[0]; 113 t = c[1] - b[1]; 114 115 return Math.atan2(u * t - v * s, u * s + v * t); 116 }, 117 118 /** 119 * Calculates the angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 120 * @param {JXG.Point,Array} A Point or [x,y] array 121 * @param {JXG.Point,Array} B Point or [x,y] array 122 * @param {JXG.Point,Array} C Point or [x,y] array 123 * @see #rad 124 * @returns {Number} The angle in degrees. 125 */ 126 trueAngle: function (A, B, C) { 127 return this.rad(A, B, C) * 57.295779513082323; // *180.0/Math.PI; 128 }, 129 130 /** 131 * Calculates the internal angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 132 * @param {JXG.Point,Array} A Point or [x,y] array 133 * @param {JXG.Point,Array} B Point or [x,y] array 134 * @param {JXG.Point,Array} C Point or [x,y] array 135 * @see #trueAngle 136 * @returns {Number} Angle in radians. 137 */ 138 rad: function (A, B, C) { 139 var ax, ay, bx, by, cx, cy, phi; 140 141 if (A.coords) { 142 ax = A.coords.usrCoords[1]; 143 ay = A.coords.usrCoords[2]; 144 } else { 145 ax = A[0]; 146 ay = A[1]; 147 } 148 149 if (B.coords) { 150 bx = B.coords.usrCoords[1]; 151 by = B.coords.usrCoords[2]; 152 } else { 153 bx = B[0]; 154 by = B[1]; 155 } 156 157 if (C.coords) { 158 cx = C.coords.usrCoords[1]; 159 cy = C.coords.usrCoords[2]; 160 } else { 161 cx = C[0]; 162 cy = C[1]; 163 } 164 165 phi = Math.atan2(cy - by, cx - bx) - Math.atan2(ay - by, ax - bx); 166 167 if (phi < 0) { 168 phi += 6.2831853071795862; 169 } 170 171 return phi; 172 }, 173 174 /** 175 * Calculates a point on the bisection line between the three points A, B, C. 176 * As a result, the bisection line is defined by two points: 177 * Parameter B and the point with the coordinates calculated in this function. 178 * Does not work for ideal points. 179 * @param {JXG.Point} A Point 180 * @param {JXG.Point} B Point 181 * @param {JXG.Point} C Point 182 * @param [board=A.board] Reference to the board 183 * @returns {JXG.Coords} Coordinates of the second point defining the bisection. 184 */ 185 angleBisector: function (A, B, C, board) { 186 var phiA, phiC, phi, 187 Ac = A.coords.usrCoords, 188 Bc = B.coords.usrCoords, 189 Cc = C.coords.usrCoords, 190 x, y; 191 192 if (!Type.exists(board)) { 193 board = A.board; 194 } 195 196 // Parallel lines 197 if (Bc[0] === 0) { 198 return new Coords(Const.COORDS_BY_USER, 199 [1, (Ac[1] + Cc[1]) * 0.5, (Ac[2] + Cc[2]) * 0.5], board); 200 } 201 202 // Non-parallel lines 203 x = Ac[1] - Bc[1]; 204 y = Ac[2] - Bc[2]; 205 phiA = Math.atan2(y, x); 206 207 x = Cc[1] - Bc[1]; 208 y = Cc[2] - Bc[2]; 209 phiC = Math.atan2(y, x); 210 211 phi = (phiA + phiC) * 0.5; 212 213 if (phiA > phiC) { 214 phi += Math.PI; 215 } 216 217 x = Math.cos(phi) + Bc[1]; 218 y = Math.sin(phi) + Bc[2]; 219 220 return new Coords(Const.COORDS_BY_USER, [1, x, y], board); 221 }, 222 223 /** 224 * Reflects the point along the line. 225 * @param {JXG.Line} line Axis of reflection. 226 * @param {JXG.Point} point Point to reflect. 227 * @param [board=point.board] Reference to the board 228 * @returns {JXG.Coords} Coordinates of the reflected point. 229 */ 230 reflection: function (line, point, board) { 231 // (v,w) defines the slope of the line 232 var x0, y0, x1, y1, v, w, mu, 233 pc = point.coords.usrCoords, 234 p1c = line.point1.coords.usrCoords, 235 p2c = line.point2.coords.usrCoords; 236 237 if (!Type.exists(board)) { 238 board = point.board; 239 } 240 241 v = p2c[1] - p1c[1]; 242 w = p2c[2] - p1c[2]; 243 244 x0 = pc[1] - p1c[1]; 245 y0 = pc[2] - p1c[2]; 246 247 mu = (v * y0 - w * x0) / (v * v + w * w); 248 249 // point + mu*(-y,x) is the perpendicular foot 250 x1 = pc[1] + 2 * mu * w; 251 y1 = pc[2] - 2 * mu * v; 252 253 return new Coords(Const.COORDS_BY_USER, [x1, y1], board); 254 }, 255 256 /** 257 * Computes the new position of a point which is rotated 258 * around a second point (called rotpoint) by the angle phi. 259 * @param {JXG.Point} rotpoint Center of the rotation 260 * @param {JXG.Point} point point to be rotated 261 * @param {Number} phi rotation angle in arc length 262 * @param {JXG.Board} [board=point.board] Reference to the board 263 * @returns {JXG.Coords} Coordinates of the new position. 264 */ 265 rotation: function (rotpoint, point, phi, board) { 266 var x0, y0, c, s, x1, y1, 267 pc = point.coords.usrCoords, 268 rotpc = rotpoint.coords.usrCoords; 269 270 if (!Type.exists(board)) { 271 board = point.board; 272 } 273 274 x0 = pc[1] - rotpc[1]; 275 y0 = pc[2] - rotpc[2]; 276 277 c = Math.cos(phi); 278 s = Math.sin(phi); 279 280 x1 = x0 * c - y0 * s + rotpc[1]; 281 y1 = x0 * s + y0 * c + rotpc[2]; 282 283 return new Coords(Const.COORDS_BY_USER, [x1, y1], board); 284 }, 285 286 /** 287 * Calculates the coordinates of a point on the perpendicular to the given line through 288 * the given point. 289 * @param {JXG.Line} line A line. 290 * @param {JXG.Point} point Point which is projected to the line. 291 * @param {JXG.Board} [board=point.board] Reference to the board 292 * @returns {Array} Array of length two containing coordinates of a point on the perpendicular to the given line 293 * through the given point and boolean flag "change". 294 */ 295 perpendicular: function (line, point, board) { 296 var x, y, change, 297 c, z, 298 A = line.point1.coords.usrCoords, 299 B = line.point2.coords.usrCoords, 300 C = point.coords.usrCoords; 301 302 if (!Type.exists(board)) { 303 board = point.board; 304 } 305 306 // special case: point is the first point of the line 307 if (point === line.point1) { 308 x = A[1] + B[2] - A[2]; 309 y = A[2] - B[1] + A[1]; 310 z = A[0] * B[0]; 311 312 if (Math.abs(z) < Mat.eps) { 313 x = B[2]; 314 y = -B[1]; 315 } 316 c = [z, x, y]; 317 change = true; 318 319 // special case: point is the second point of the line 320 } else if (point === line.point2) { 321 x = B[1] + A[2] - B[2]; 322 y = B[2] - A[1] + B[1]; 323 z = A[0] * B[0]; 324 325 if (Math.abs(z) < Mat.eps) { 326 x = A[2]; 327 y = -A[1]; 328 } 329 c = [z, x, y]; 330 change = false; 331 332 // special case: point lies somewhere else on the line 333 } else if (Math.abs(Mat.innerProduct(C, line.stdform, 3)) < Mat.eps) { 334 x = C[1] + B[2] - C[2]; 335 y = C[2] - B[1] + C[1]; 336 z = B[0]; 337 338 if (Math.abs(z) < Mat.eps) { 339 x = B[2]; 340 y = -B[1]; 341 } 342 change = true; 343 344 if (Math.abs(z) > Mat.eps && Math.abs(x - C[1]) < Mat.eps && Math.abs(y - C[2]) < Mat.eps) { 345 x = C[1] + A[2] - C[2]; 346 y = C[2] - A[1] + C[1]; 347 change = false; 348 } 349 c = [z, x, y]; 350 351 // general case: point does not lie on the line 352 // -> calculate the foot of the dropped perpendicular 353 } else { 354 c = [0, line.stdform[1], line.stdform[2]]; 355 c = Mat.crossProduct(c, C); // perpendicuar to line 356 c = Mat.crossProduct(c, line.stdform); // intersection of line and perpendicular 357 change = true; 358 } 359 360 return [new Coords(Const.COORDS_BY_USER, c, board), change]; 361 }, 362 363 /** 364 * @deprecated Please use {@link JXG.Math.Geometry#circumcenter} instead. 365 */ 366 circumcenterMidpoint: JXG.shortcut(Mat.Geometry, 'circumcenter'), 367 368 /** 369 * Calculates the center of the circumcircle of the three given points. 370 * @param {JXG.Point} point1 Point 371 * @param {JXG.Point} point2 Point 372 * @param {JXG.Point} point3 Point 373 * @param {JXG.Board} [board=point1.board] Reference to the board 374 * @returns {JXG.Coords} Coordinates of the center of the circumcircle of the given points. 375 */ 376 circumcenter: function (point1, point2, point3, board) { 377 var u, v, m1, m2, 378 A = point1.coords.usrCoords, 379 B = point2.coords.usrCoords, 380 C = point3.coords.usrCoords; 381 382 if (!Type.exists(board)) { 383 board = point1.board; 384 } 385 386 u = [B[0] - A[0], -B[2] + A[2], B[1] - A[1]]; 387 v = [(A[0] + B[0]) * 0.5, (A[1] + B[1]) * 0.5, (A[2] + B[2]) * 0.5]; 388 m1 = Mat.crossProduct(u, v); 389 390 u = [C[0] - B[0], -C[2] + B[2], C[1] - B[1]]; 391 v = [(B[0] + C[0]) * 0.5, (B[1] + C[1]) * 0.5, (B[2] + C[2]) * 0.5]; 392 m2 = Mat.crossProduct(u, v); 393 394 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(m1, m2), board); 395 }, 396 397 /** 398 * Calculates the euclidean norm for two given arrays of the same length. 399 * @param {Array} array1 Array of Number 400 * @param {Array} array2 Array of Number 401 * @param {Number} [n] Length of the arrays. Default is the minimum length of the given arrays. 402 * @returns {Number} Euclidean distance of the given vectors. 403 */ 404 distance: function (array1, array2, n) { 405 var i, 406 sum = 0; 407 408 if (!n) { 409 n = Math.min(array1.length, array2.length); 410 } 411 412 for (i = 0; i < n; i++) { 413 sum += (array1[i] - array2[i]) * (array1[i] - array2[i]); 414 } 415 416 return Math.sqrt(sum); 417 }, 418 419 /** 420 * Calculates euclidean distance for two given arrays of the same length. 421 * If one of the arrays contains a zero in the first coordinate, and the euclidean distance 422 * is different from zero it is a point at infinity and we return Infinity. 423 * @param {Array} array1 Array containing elements of type number. 424 * @param {Array} array2 Array containing elements of type number. 425 * @param {Number} [n] Length of the arrays. Default is the minimum length of the given arrays. 426 * @returns {Number} Euclidean (affine) distance of the given vectors. 427 */ 428 affineDistance: function (array1, array2, n) { 429 var d; 430 431 d = this.distance(array1, array2, n); 432 433 if (d > Mat.eps && (Math.abs(array1[0]) < Mat.eps || Math.abs(array2[0]) < Mat.eps)) { 434 return Infinity; 435 } 436 437 return d; 438 }, 439 440 /** 441 * Sort vertices counter clockwise starting with the point with the lowest y coordinate. 442 * 443 * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 444 * 445 * @returns {Array} 446 */ 447 sortVertices: function (p) { 448 var i, ll, 449 ps = Expect.each(p, Expect.coordsArray), 450 N = ps.length; 451 452 // find the point with the lowest y value 453 for (i = 1; i < N; i++) { 454 if ((ps[i][2] < ps[0][2]) || 455 // if the current and the lowest point have the same y value, pick the one with 456 // the lowest x value. 457 (Math.abs(ps[i][2] - ps[0][2]) < Mat.eps && ps[i][1] < ps[0][1])) { 458 ps = Type.swap(ps, i, 0); 459 } 460 } 461 462 // sort ps in increasing order of the angle the points and the ll make with the x-axis 463 ll = ps.shift(); 464 ps.sort(function (a, b) { 465 // atan is monotonically increasing, as we are only interested in the sign of the difference 466 // evaluating atan is not necessary 467 var rad1 = Math.atan2(a[2] - ll[2], a[1] - ll[1]), 468 rad2 = Math.atan2(b[2] - ll[2], b[1] - ll[1]); 469 470 return rad1 - rad2; 471 }); 472 473 // put ll back into the array 474 ps.unshift(ll); 475 476 // put the last element also in the beginning 477 ps.unshift(ps[ps.length - 1]); 478 479 return ps; 480 }, 481 482 /** 483 * Signed triangle area of the three points given. 484 * 485 * @param {JXG.Point|JXG.Coords|Array} p1 486 * @param {JXG.Point|JXG.Coords|Array} p2 487 * @param {JXG.Point|JXG.Coords|Array} p3 488 * 489 * @returns {Number} 490 */ 491 signedTriangle: function (p1, p2, p3) { 492 var A = Expect.coordsArray(p1), 493 B = Expect.coordsArray(p2), 494 C = Expect.coordsArray(p3); 495 496 return 0.5 * ((B[1] - A[1]) * (C[2] - A[2]) - (B[2] - A[2]) * (C[1] - A[1])); 497 }, 498 499 /** 500 * Determine the signed area of a non-intersecting polygon. 501 * 502 * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 503 * @param {Boolean} [sort=true] 504 * 505 * @returns {Number} 506 */ 507 signedPolygon: function (p, sort) { 508 var i, N, 509 A = 0, 510 ps = Expect.each(p, Expect.coordsArray); 511 512 if (!sort) { 513 ps = this.sortVertices(ps); 514 } else { 515 // make sure the polygon is closed. If it is already closed this won't change the sum because the last 516 // summand will be 0. 517 ps.unshift(ps[ps.length - 1]); 518 } 519 520 N = ps.length; 521 522 for (i = 1; i < N; i++) { 523 A += ps[i - 1][1] * ps[i][2] - ps[i][1] * ps[i - 1][2]; 524 } 525 526 return 0.5 * A; 527 }, 528 529 /** 530 * Calculate the complex hull of a point cloud. 531 * 532 * @param {Array} points An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays. 533 * 534 * @returns {Array} 535 */ 536 GrahamScan: function (points) { 537 var i, ll, 538 M = 1, 539 ps = Expect.each(points, Expect.coordsArray), 540 N = ps.length; 541 542 543 ps = this.sortVertices(ps); 544 N = ps.length; 545 546 for (i = 2; i < N; i++) { 547 while (this.signedTriangle(ps[M - 1], ps[M], ps[i]) <= 0) { 548 if (M > 1) { 549 M -= 1; 550 } else if (i === N - 1) { 551 break; 552 } else { 553 i += 1; 554 } 555 } 556 557 M += 1; 558 ps = Type.swap(ps, M, i); 559 } 560 561 return ps.slice(0, M); 562 }, 563 564 /** 565 * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2 566 * calcStraight determines the visual start point and end point of the line. A segment is only drawn 567 * from start to end point, a straight line is drawn until it meets the boards boundaries. 568 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 569 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and 570 * set by this method. 571 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set 572 * by this method. 573 * @param {Number} margin Optional margin, to avoid the display of the small sides of lines. 574 * @see Line 575 * @see JXG.Line 576 */ 577 calcStraight: function (el, point1, point2, margin) { 578 var takePoint1, takePoint2, intersection, intersect1, intersect2, straightFirst, straightLast, 579 c, s, i, j, p1, p2; 580 581 if (!Type.exists(margin)) { 582 // Enlarge the drawable region slightly. This hides the small sides 583 // of thick lines in most cases. 584 margin = 10; 585 } 586 587 straightFirst = el.visProp.straightfirst; 588 straightLast = el.visProp.straightlast; 589 590 // If one of the point is an ideal point in homogeneous coordinates 591 // drawing of line segments or rays are not possible. 592 if (Math.abs(point1.scrCoords[0]) < Mat.eps) { 593 straightFirst = true; 594 } 595 if (Math.abs(point2.scrCoords[0]) < Mat.eps) { 596 straightLast = true; 597 } 598 599 // Do nothing in case of line segments (inside or outside of the board) 600 if (!straightFirst && !straightLast) { 601 return; 602 } 603 604 // Compute the stdform of the line in screen coordinates. 605 c = []; 606 c[0] = el.stdform[0] - 607 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX + 608 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY; 609 c[1] = el.stdform[1] / el.board.unitX; 610 c[2] = -el.stdform[2] / el.board.unitY; 611 612 // p1=p2 613 if (isNaN(c[0] + c[1] + c[2])) { 614 return; 615 } 616 617 takePoint1 = false; 618 takePoint2 = false; 619 620 // Line starts at point1 and point1 is inside the board 621 takePoint1 = !straightFirst && 622 Math.abs(point1.usrCoords[0]) >= Mat.eps && 623 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth && 624 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight; 625 626 // Line ends at point2 and point2 is inside the board 627 takePoint2 = !straightLast && 628 Math.abs(point2.usrCoords[0]) >= Mat.eps && 629 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth && 630 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight; 631 632 // Intersect the line with the four borders of the board. 633 intersection = this.meetLineBoard(c, el.board, margin); 634 intersect1 = intersection[0]; 635 intersect2 = intersection[1]; 636 637 /** 638 * At this point we have four points: 639 * point1 and point2 are the first and the second defining point on the line, 640 * intersect1, intersect2 are the intersections of the line with border around the board. 641 */ 642 643 /* 644 * Here we handle rays where both defining points are outside of the board. 645 */ 646 // If both points are outside and the complete ray is outside we do nothing 647 if (!takePoint1 && !takePoint2) { 648 // Ray starting at point 1 649 if (!straightFirst && straightLast && 650 !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) { 651 return; 652 } 653 654 // Ray starting at point 2 655 if (straightFirst && !straightLast && 656 !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) { 657 return; 658 } 659 } 660 661 /* 662 * If at least one of the defining points is outside of the board 663 * we take intersect1 or intersect2 as one of the end points 664 * The order is also important for arrows of axes 665 */ 666 if (!takePoint1) { 667 if (!takePoint2) { 668 // Two border intersection points are used 669 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 670 p1 = intersect1; 671 p2 = intersect2; 672 } else { 673 p2 = intersect1; 674 p1 = intersect2; 675 } 676 } else { 677 // One border intersection points is used 678 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 679 p1 = intersect1; 680 } else { 681 p1 = intersect2; 682 } 683 } 684 } else { 685 if (!takePoint2) { 686 // One border intersection points is used 687 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 688 p2 = intersect2; 689 } else { 690 p2 = intersect1; 691 } 692 } 693 } 694 695 if (p1) { 696 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1)); 697 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords); 698 } 699 700 if (p2) { 701 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1)); 702 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords); 703 } 704 }, 705 706 707 /** 708 * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2. 709 * 710 * This method adjusts the line's delimiting points taking into account its nature, the viewport defined 711 * by the board. 712 * 713 * A segment is delimited by start and end point, a straight line or ray is delimited until it meets the 714 * boards boundaries. However, if the line has infinite ticks, it will be delimited by the projection of 715 * the boards vertices onto itself. 716 * 717 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 718 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and 719 * set by this method. 720 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set 721 * by this method. 722 * @see Line 723 * @see JXG.Line 724 */ 725 calcLineDelimitingPoints: function (el, point1, point2) { 726 var distP1P2, boundingBox, lineSlope, 727 intersection, intersect1, intersect2, straightFirst, straightLast, 728 c, s, i, j, p1, p2, 729 takePoint1 = false, 730 takePoint2 = false; 731 732 straightFirst = el.visProp.straightfirst; 733 straightLast = el.visProp.straightlast; 734 735 // If one of the point is an ideal point in homogeneous coordinates 736 // drawing of line segments or rays are not possible. 737 if (Math.abs(point1.scrCoords[0]) < Mat.eps) { 738 straightFirst = true; 739 } 740 if (Math.abs(point2.scrCoords[0]) < Mat.eps) { 741 straightLast = true; 742 } 743 744 // Compute the stdform of the line in screen coordinates. 745 c = []; 746 c[0] = el.stdform[0] - 747 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX + 748 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY; 749 c[1] = el.stdform[1] / el.board.unitX; 750 c[2] = -el.stdform[2] / el.board.unitY; 751 752 // p1=p2 753 if (isNaN(c[0] + c[1] + c[2])) { 754 return; 755 } 756 757 takePoint1 = !straightFirst; 758 takePoint2 = !straightLast; 759 // Intersect the board vertices on the line to establish the available visual space for the infinite ticks 760 // Based on the slope of the line we can optimise and only project the two outer vertices 761 762 // boundingBox = [x1, y1, x2, y2] upper left, lower right vertices 763 boundingBox = el.board.getBoundingBox(); 764 lineSlope = el.getSlope(); 765 if (lineSlope >= 0) { 766 // project vertices (x2,y1) (x1, y2) 767 intersect1 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[2], boundingBox[1]] } }, el, el.board); 768 intersect2 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[0], boundingBox[3]] } }, el, el.board); 769 } else { 770 // project vertices (x1, y1) (x2, y2) 771 intersect1 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[0], boundingBox[1]] } }, el, el.board); 772 intersect2 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[2], boundingBox[3]] } }, el, el.board); 773 } 774 775 /** 776 * we have four points: 777 * point1 and point2 are the first and the second defining point on the line, 778 * intersect1, intersect2 are the intersections of the line with border around the board. 779 */ 780 781 /* 782 * Here we handle rays/segments where both defining points are outside of the board. 783 */ 784 if (!takePoint1 && !takePoint2) { 785 // Segment, if segment does not cross the board, do nothing 786 if (!straightFirst && !straightLast) { 787 distP1P2 = point1.distance(Const.COORDS_BY_USER, point2); 788 // if intersect1 not between point1 and point2 789 if (Math.abs(point1.distance(Const.COORDS_BY_USER, intersect1) + 790 intersect1.distance(Const.COORDS_BY_USER, point2) - distP1P2) > Mat.eps) { 791 return; 792 } 793 // if insersect2 not between point1 and point2 794 if (Math.abs(point1.distance(Const.COORDS_BY_USER, intersect2) + 795 intersect2.distance(Const.COORDS_BY_USER, point2) - distP1P2) > Mat.eps) { 796 return; 797 } 798 } 799 800 // If both points are outside and the complete ray is outside we do nothing 801 // Ray starting at point 1 802 if (!straightFirst && straightLast && 803 !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) { 804 return; 805 } 806 807 // Ray starting at point 2 808 if (straightFirst && !straightLast && 809 !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) { 810 return; 811 } 812 } 813 814 /* 815 * If at least one of the defining points is outside of the board 816 * we take intersect1 or intersect2 as one of the end points 817 * The order is also important for arrows of axes 818 */ 819 if (!takePoint1) { 820 if (!takePoint2) { 821 // Two border intersection points are used 822 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 823 p1 = intersect1; 824 p2 = intersect2; 825 } else { 826 p2 = intersect1; 827 p1 = intersect2; 828 } 829 } else { 830 // One border intersection points is used 831 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 832 p1 = intersect1; 833 } else { 834 p1 = intersect2; 835 } 836 } 837 } else { 838 if (!takePoint2) { 839 // One border intersection points is used 840 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 841 p2 = intersect2; 842 } else { 843 p2 = intersect1; 844 } 845 } 846 } 847 848 if (p1) { 849 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1)); 850 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords); 851 } 852 853 if (p2) { 854 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1)); 855 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords); 856 } 857 }, 858 859 /** 860 * The vectors <tt>p2-p1</tt> and <tt>i2-i1</tt> are supposed to be collinear. If their cosine is positive 861 * they point into the same direction otherwise they point in opposite direction. 862 * @param {JXG.Coords} p1 863 * @param {JXG.Coords} p2 864 * @param {JXG.Coords} i1 865 * @param {JXG.Coords} i2 866 * @returns {Boolean} True, if <tt>p2-p1</tt> and <tt>i2-i1</tt> point into the same direction 867 */ 868 isSameDir: function (p1, p2, i1, i2) { 869 var dpx = p2.usrCoords[1] - p1.usrCoords[1], 870 dpy = p2.usrCoords[2] - p1.usrCoords[2], 871 dix = i2.usrCoords[1] - i1.usrCoords[1], 872 diy = i2.usrCoords[2] - i1.usrCoords[2]; 873 874 if (Math.abs(p2.usrCoords[0]) < Mat.eps) { 875 dpx = p2.usrCoords[1]; 876 dpy = p2.usrCoords[2]; 877 } 878 879 if (Math.abs(p1.usrCoords[0]) < Mat.eps) { 880 dpx = -p1.usrCoords[1]; 881 dpy = -p1.usrCoords[2]; 882 } 883 884 return dpx * dix + dpy * diy >= 0; 885 }, 886 887 /** 888 * If you're looking from point "start" towards point "s" and can see the point "p", true is returned. Otherwise false. 889 * @param {JXG.Coords} start The point you're standing on. 890 * @param {JXG.Coords} p The point in which direction you're looking. 891 * @param {JXG.Coords} s The point that should be visible. 892 * @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. 893 */ 894 isSameDirection: function (start, p, s) { 895 var dx, dy, sx, sy, r = false; 896 897 dx = p.usrCoords[1] - start.usrCoords[1]; 898 dy = p.usrCoords[2] - start.usrCoords[2]; 899 900 sx = s.usrCoords[1] - start.usrCoords[1]; 901 sy = s.usrCoords[2] - start.usrCoords[2]; 902 903 if (Math.abs(dx) < Mat.eps) { 904 dx = 0; 905 } 906 907 if (Math.abs(dy) < Mat.eps) { 908 dy = 0; 909 } 910 911 if (Math.abs(sx) < Mat.eps) { 912 sx = 0; 913 } 914 915 if (Math.abs(sy) < Mat.eps) { 916 sy = 0; 917 } 918 919 if (dx >= 0 && sx >= 0) { 920 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0); 921 } else if (dx <= 0 && sx <= 0) { 922 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0); 923 } 924 925 return r; 926 }, 927 928 /****************************************/ 929 /**** INTERSECTIONS ****/ 930 /****************************************/ 931 932 /** 933 * Generate the function which computes the coordinates of the intersection point. 934 * Primarily used in {@link JXG.Point#createIntersectionPoint}. 935 * @param {JXG.Board} board object 936 * @param {JXG.Line,JXG.Circle_JXG.Line,JXG.Circle_Number} el1,el2,i The result will be a intersection point on el1 and el2. 937 * i determines the intersection point if two points are available: <ul> 938 * <li>i==0: use the positive square root,</li> 939 * <li>i==1: use the negative square root.</li></ul> 940 * See further {@see JXG.Point#createIntersectionPoint}. 941 * @param {Boolean} alwaysintersect. Flag that determines if segements and arc can have an outer intersection point 942 * on their defining line or circle. 943 * @returns {Function} Function returning a {@see JXG.Coords} object that determines the intersection point. 944 */ 945 intersectionFunction: function (board, el1, el2, i, j, alwaysintersect) { 946 var func, that = this; 947 948 if (el1.elementClass === Const.OBJECT_CLASS_CURVE && 949 el2.elementClass === Const.OBJECT_CLASS_CURVE) { 950 // curve - curve 951 /** @ignore */ 952 func = function () { 953 return that.meetCurveCurve(el1, el2, i, j, el1.board); 954 }; 955 956 //} else if ((el1.type === Const.OBJECT_TYPE_ARC && el2.elementClass === Const.OBJECT_CLASS_LINE) || 957 // // (el2.type === Const.OBJECT_TYPE_ARC && el1.elementClass === Const.OBJECT_CLASS_LINE)) { 958 // arc - line (arcs are of class curve, but are intersected like circles) 959 // TEMPORARY FIX!!! 960 /** @ignore */ 961 // // func = function () { 962 //return that..meet(el1.stdform, el2.stdform, i, el1.board); 963 //}; 964 965 } else if ((el1.elementClass === Const.OBJECT_CLASS_CURVE && el2.elementClass === Const.OBJECT_CLASS_LINE) || 966 (el2.elementClass === Const.OBJECT_CLASS_CURVE && el1.elementClass === Const.OBJECT_CLASS_LINE)) { 967 // curve - line (this includes intersections between conic sections and lines 968 /** @ignore */ 969 func = function () { 970 return that.meetCurveLine(el1, el2, i, el1.board, alwaysintersect); 971 }; 972 973 } else if (el1.elementClass === Const.OBJECT_CLASS_LINE && el2.elementClass === Const.OBJECT_CLASS_LINE) { 974 // line - line, lines may also be segments. 975 /** @ignore */ 976 func = function () { 977 var res, c, 978 first1 = el1.visProp.straightfirst, 979 first2 = el2.visProp.straightfirst, 980 last1 = el1.visProp.straightlast, 981 last2 = el2.visProp.straightlast; 982 983 /** 984 * If one of the lines is a segment or ray and 985 * the the intersection point shpould disappear if outside 986 * of the segment or ray we call 987 * meetSegmentSegment 988 */ 989 if (!alwaysintersect && (!first1 || !last1 || !first2 || !last2)) { 990 res = that.meetSegmentSegment( 991 el1.point1.coords.usrCoords, 992 el1.point2.coords.usrCoords, 993 el2.point1.coords.usrCoords, 994 el2.point2.coords.usrCoords, 995 el1.board 996 ); 997 998 if ((!first1 && res[1] < 0) || (!last1 && res[1] > 1) || 999 (!first2 && res[2] < 0) || (!last2 && res[2] > 1)) { 1000 // Non-existent 1001 c = [0, NaN, NaN]; 1002 } else { 1003 c = res[0]; 1004 } 1005 1006 return (new Coords(Const.COORDS_BY_USER, c, el1.board)); 1007 } 1008 1009 return that.meet(el1.stdform, el2.stdform, i, el1.board); 1010 }; 1011 } else { 1012 // All other combinations of circles and lines 1013 /** @ignore */ 1014 func = function () { 1015 return that.meet(el1.stdform, el2.stdform, i, el1.board); 1016 }; 1017 } 1018 1019 return func; 1020 }, 1021 1022 /** 1023 * Computes the intersection of a pair of lines, circles or both. 1024 * It uses the internal data array stdform of these elements. 1025 * @param {Array} el1 stdform of the first element (line or circle) 1026 * @param {Array} el2 stdform of the second element (line or circle) 1027 * @param {Number} i Index of the intersection point that should be returned. 1028 * @param board Reference to the board. 1029 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 1030 * Which point will be returned is determined by i. 1031 */ 1032 meet: function (el1, el2, i, board) { 1033 var result, 1034 eps = Mat.eps; 1035 1036 // line line 1037 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { 1038 result = this.meetLineLine(el1, el2, i, board); 1039 // circle line 1040 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { 1041 result = this.meetLineCircle(el2, el1, i, board); 1042 // line circle 1043 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { 1044 result = this.meetLineCircle(el1, el2, i, board); 1045 // circle circle 1046 } else { 1047 result = this.meetCircleCircle(el1, el2, i, board); 1048 } 1049 1050 return result; 1051 }, 1052 1053 /** 1054 * Intersection of the line with the board 1055 * @param {Array} line stdform of the line 1056 * @param {JXG.Board} board reference to a board. 1057 * @param {Number} margin optional margin, to avoid the display of the small sides of lines. 1058 * @return {Array} [intersection coords 1, intersection coords 2] 1059 */ 1060 meetLineBoard: function (line, board, margin) { 1061 // Intersect the line with the four borders of the board. 1062 var s = [], intersect1, intersect2, i, j; 1063 1064 if (!Type.exists(margin)) { 1065 margin = 0; 1066 } 1067 1068 // top 1069 s[0] = Mat.crossProduct(line, [margin, 0, 1]); 1070 // left 1071 s[1] = Mat.crossProduct(line, [margin, 1, 0]); 1072 // bottom 1073 s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]); 1074 // right 1075 s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]); 1076 1077 // Normalize the intersections 1078 for (i = 0; i < 4; i++) { 1079 if (Math.abs(s[i][0]) > Mat.eps) { 1080 for (j = 2; j > 0; j--) { 1081 s[i][j] /= s[i][0]; 1082 } 1083 s[i][0] = 1.0; 1084 } 1085 } 1086 1087 // line is parallel to "left", take "top" and "bottom" 1088 if (Math.abs(s[1][0]) < Mat.eps) { 1089 intersect1 = s[0]; // top 1090 intersect2 = s[2]; // bottom 1091 // line is parallel to "top", take "left" and "right" 1092 } else if (Math.abs(s[0][0]) < Mat.eps) { 1093 intersect1 = s[1]; // left 1094 intersect2 = s[3]; // right 1095 // left intersection out of board (above) 1096 } else if (s[1][2] < 0) { 1097 intersect1 = s[0]; // top 1098 1099 // right intersection out of board (below) 1100 if (s[3][2] > board.canvasHeight) { 1101 intersect2 = s[2]; // bottom 1102 } else { 1103 intersect2 = s[3]; // right 1104 } 1105 // left intersection out of board (below) 1106 } else if (s[1][2] > board.canvasHeight) { 1107 intersect1 = s[2]; // bottom 1108 1109 // right intersection out of board (above) 1110 if (s[3][2] < 0) { 1111 intersect2 = s[0]; // top 1112 } else { 1113 intersect2 = s[3]; // right 1114 } 1115 } else { 1116 intersect1 = s[1]; // left 1117 1118 // right intersection out of board (above) 1119 if (s[3][2] < 0) { 1120 intersect2 = s[0]; // top 1121 // right intersection out of board (below) 1122 } else if (s[3][2] > board.canvasHeight) { 1123 intersect2 = s[2]; // bottom 1124 } else { 1125 intersect2 = s[3]; // right 1126 } 1127 } 1128 1129 intersect1 = new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board); 1130 intersect2 = new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board); 1131 return [intersect1, intersect2]; 1132 }, 1133 1134 /** 1135 * Intersection of two lines. 1136 * @param {Array} l1 stdform of the first line 1137 * @param {Array} l2 stdform of the second line 1138 * @param {number} i unused 1139 * @param {JXG.Board} board Reference to the board. 1140 * @returns {JXG.Coords} Coordinates of the intersection point. 1141 */ 1142 meetLineLine: function (l1, l2, i, board) { 1143 /* 1144 var s = Mat.crossProduct(l1, l2); 1145 1146 if (Math.abs(s[0]) > Mat.eps) { 1147 s[1] /= s[0]; 1148 s[2] /= s[0]; 1149 s[0] = 1.0; 1150 } 1151 */ 1152 var s = isNaN(l1[5] + l2[5]) ? [0, 0, 0] : Mat.crossProduct(l1, l2); 1153 return new Coords(Const.COORDS_BY_USER, s, board); 1154 }, 1155 1156 /** 1157 * Intersection of line and circle. 1158 * @param {Array} lin stdform of the line 1159 * @param {Array} circ stdform of the circle 1160 * @param {number} i number of the returned intersection point. 1161 * i==0: use the positive square root, 1162 * i==1: use the negative square root. 1163 * @param {JXG.Board} board Reference to a board. 1164 * @returns {JXG.Coords} Coordinates of the intersection point 1165 */ 1166 meetLineCircle: function (lin, circ, i, board) { 1167 var a, b, c, d, n, 1168 A, B, C, k, t; 1169 1170 // Radius is zero, return center of circle 1171 if (circ[4] < Mat.eps) { 1172 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) { 1173 return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board); 1174 } 1175 1176 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board); 1177 } 1178 1179 c = circ[0]; 1180 b = circ.slice(1, 3); 1181 a = circ[3]; 1182 d = lin[0]; 1183 n = lin.slice(1, 3); 1184 1185 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 1186 /* 1187 var nn = n[0]*n[0]+n[1]*n[1]; 1188 A = a*nn; 1189 B = (b[0]*n[1]-b[1]*n[0])*nn; 1190 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 1191 */ 1192 A = a; 1193 B = (b[0] * n[1] - b[1] * n[0]); 1194 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 1195 1196 k = B * B - 4 * A * C; 1197 if (k >= 0) { 1198 k = Math.sqrt(k); 1199 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)]; 1200 1201 return ((i === 0) ? 1202 new Coords(Const.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0], -t[0] * n[0] - d * n[1]], board) : 1203 new Coords(Const.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0], -t[1] * n[0] - d * n[1]], board) 1204 ); 1205 } 1206 1207 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1208 }, 1209 1210 /** 1211 * Intersection of two circles. 1212 * @param {Array} circ1 stdform of the first circle 1213 * @param {Array} circ2 stdform of the second circle 1214 * @param {number} i number of the returned intersection point. 1215 * i==0: use the positive square root, 1216 * i==1: use the negative square root. 1217 * @param {JXG.Board} board Reference to the board. 1218 * @returns {JXG.Coords} Coordinates of the intersection point 1219 */ 1220 meetCircleCircle: function (circ1, circ2, i, board) { 1221 var radicalAxis; 1222 1223 // Radius are zero, return center of circle, if on other circle 1224 if (circ1[4] < Mat.eps) { 1225 if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < Mat.eps) { 1226 return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board); 1227 } 1228 1229 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1230 } 1231 1232 // Radius are zero, return center of circle, if on other circle 1233 if (circ2[4] < Mat.eps) { 1234 if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < Mat.eps) { 1235 return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board); 1236 } 1237 1238 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1239 } 1240 1241 radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0], 1242 circ2[3] * circ1[1] - circ1[3] * circ2[1], 1243 circ2[3] * circ1[2] - circ1[3] * circ2[2], 1244 0, 1, Infinity, Infinity, Infinity]; 1245 radicalAxis = Mat.normalize(radicalAxis); 1246 1247 return this.meetLineCircle(radicalAxis, circ1, i, board); 1248 }, 1249 1250 /** 1251 * Compute an intersection of the curves c1 and c2. 1252 * We want to find values t1, t2 such that 1253 * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 1254 * 1255 * Methods: segment-wise intersections (default) or generalized Newton method. 1256 * @param {JXG.Curve} c1 Curve, Line or Circle 1257 * @param {JXG.Curve} c2 Curve, Line or Circle 1258 * @param {Number} nr the nr-th intersection point will be returned. 1259 * @param {Number} t2ini not longer used. 1260 * @param {JXG.Board} [board=c1.board] Reference to a board object. 1261 * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'. 1262 * @returns {JXG.Coords} intersection point 1263 */ 1264 meetCurveCurve: function (c1, c2, nr, t2ini, board, method) { 1265 var co; 1266 1267 if (Type.exists(method) && method === 'newton') { 1268 co = Numerics.generalizedNewton(c1, c2, nr, t2ini); 1269 } else { 1270 if (c1.bezierDegree === 3 && c2.bezierDegree === 3) { 1271 co = this.meetBezierCurveRedBlueSegments(c1, c2, nr); 1272 } else { 1273 co = this.meetCurveRedBlueSegments(c1, c2, nr); 1274 } 1275 } 1276 1277 return (new Coords(Const.COORDS_BY_USER, co, board)); 1278 }, 1279 1280 /** 1281 * Intersection of curve with line, 1282 * Order of input does not matter for el1 and el2. 1283 * @param {JXG.Curve,JXG.Line} el1 Curve or Line 1284 * @param {JXG.Curve,JXG.Line} el2 Curve or Line 1285 * @param {Number} nr the nr-th intersection point will be returned. 1286 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1287 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection 1288 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1289 * the ideal point [0,1,0] is returned. 1290 */ 1291 meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) { 1292 var v = [0, NaN, NaN], i, cu, li; 1293 1294 if (!Type.exists(board)) { 1295 board = el1.board; 1296 } 1297 1298 if (el1.elementClass === Const.OBJECT_CLASS_CURVE) { 1299 cu = el1; 1300 li = el2; 1301 } else { 1302 cu = el2; 1303 li = el1; 1304 } 1305 1306 if (cu.visProp.curvetype === 'plot') { 1307 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect); 1308 } else { 1309 v = this.meetCurveLineContinuous(cu, li, nr, board); 1310 } 1311 1312 return v; 1313 }, 1314 1315 /** 1316 * Intersection of line and curve, continuous case. 1317 * Finds the nr-the intersection point 1318 * Uses {@link JXG.Math.Geometry#meetCurveLineDiscrete} as a first approximation. 1319 * A more exact solution is then found with {@link JXG.Math.Numerics#meetCurveLineDiscrete}. 1320 * 1321 * @param {JXG.Curve} cu Curve 1322 * @param {JXG.Line} li Line 1323 * @param {Number} nr Will return the nr-th intersection point. 1324 * @param {JXG.Board} board 1325 * 1326 */ 1327 meetCurveLineContinuous: function (cu, li, nr, board, testSegment) { 1328 var t, func0, func1, v, x, y, z, 1329 eps = Mat.eps * 10; 1330 1331 v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment); 1332 x = v.usrCoords[1]; 1333 y = v.usrCoords[2]; 1334 1335 func0 = function (t) { 1336 var c1 = x - cu.X(t), 1337 c2 = y - cu.Y(t); 1338 1339 return Math.sqrt(c1 * c1 + c2 * c2); 1340 }; 1341 1342 func1 = function (t) { 1343 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1344 return v * v; 1345 }; 1346 1347 // Find t 1348 t = Numerics.root(func0, [cu.minX(), cu.maxX()]); 1349 // Compute "exect" t 1350 t = Numerics.root(func1, t); 1351 1352 // Is the point on the line? 1353 if (Math.abs(func1(t)) > eps) { 1354 z = NaN; 1355 } else { 1356 z = 1.0; 1357 } 1358 1359 return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1360 }, 1361 1362 /** 1363 * Intersection of line and curve, continuous case. 1364 * Segments are treated as lines. Finding the nr-the intersection point 1365 * works for nr=0,1 only. 1366 * 1367 * @private 1368 * @deprecated 1369 * @param {JXG.Curve} cu Curve 1370 * @param {JXG.Line} li Line 1371 * @param {Number} nr Will return the nr-th intersection point. 1372 * @param {JXG.Board} board 1373 * 1374 * BUG: does not respect cu.minX() and cu.maxX() 1375 */ 1376 meetCurveLineContinuousOld: function (cu, li, nr, board) { 1377 var t, t2, i, func, z, 1378 tnew, steps, delta, tstart, tend, cux, cuy, 1379 eps = Mat.eps * 10; 1380 1381 func = function (t) { 1382 // return li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1383 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1384 return v * v; 1385 }; 1386 1387 // Find some intersection point 1388 if (this.meetCurveLineContinuous.t1memo) { 1389 tstart = this.meetCurveLineContinuous.t1memo; 1390 t = Numerics.root(func, tstart); 1391 } else { 1392 tstart = cu.minX(); 1393 tend = cu.maxX(); 1394 t = Numerics.root(func, [tstart, tend]); 1395 } 1396 1397 this.meetCurveLineContinuous.t1memo = t; 1398 cux = cu.X(t); 1399 cuy = cu.Y(t); 1400 1401 // Find second intersection point 1402 if (nr === 1) { 1403 if (this.meetCurveLineContinuous.t2memo) { 1404 tstart = this.meetCurveLineContinuous.t2memo; 1405 } 1406 t2 = Numerics.root(func, tstart); 1407 1408 if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) { 1409 steps = 20; 1410 delta = (cu.maxX() - cu.minX()) / steps; 1411 tnew = cu.minX(); 1412 1413 for (i = 0; i < steps; i++) { 1414 t2 = Numerics.root(func, [tnew, tnew + delta]); 1415 1416 if (Math.abs(func(t2)) <= eps && Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1) { 1417 break; 1418 } 1419 1420 tnew += delta; 1421 } 1422 } 1423 t = t2; 1424 this.meetCurveLineContinuous.t2memo = t; 1425 } 1426 1427 // Is the point on the line? 1428 if (Math.abs(func(t)) > eps) { 1429 z = NaN; 1430 } else { 1431 z = 1.0; 1432 } 1433 1434 return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1435 }, 1436 1437 /** 1438 * Intersection of line and curve, discrete case. 1439 * Segments are treated as lines. 1440 * Finding the nr-th intersection point should work for all nr. 1441 * @param {JXG.Curve} cu 1442 * @param {JXG.Line} li 1443 * @param {Number} nr 1444 * @param {JXG.Board} board 1445 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 1446 * line defined by the segment 1447 * 1448 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1449 * the ideal point [0,1,0] is returned. 1450 */ 1451 meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) { 1452 var i, j, 1453 p1, p2, p, q, 1454 lip1 = li.point1.coords.usrCoords, 1455 lip2 = li.point2.coords.usrCoords, 1456 d, res, 1457 cnt = 0, 1458 len = cu.numberPoints; 1459 1460 // In case, no intersection will be found we will take this 1461 q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board); 1462 1463 if (lip1[0] === 0.0) { 1464 lip1 = [1, lip2[1] + li.stdform[2], lip2[2] - li.stdform[1]]; 1465 } else if (lip2[0] === 0.0) { 1466 lip2 = [1, lip1[1] + li.stdform[2], lip1[2] - li.stdform[1]]; 1467 } 1468 1469 p2 = cu.points[0].usrCoords; 1470 for (i = 1; i < len; i++) { 1471 p1 = p2.slice(0); 1472 p2 = cu.points[i].usrCoords; 1473 d = this.distance(p1, p2); 1474 1475 // The defining points are not identical 1476 if (d > Mat.eps) { 1477 if (cu.bezierDegree === 3) { 1478 res = this.meetBeziersegmentBeziersegment([ 1479 cu.points[i - 1].usrCoords.slice(1), 1480 cu.points[i].usrCoords.slice(1), 1481 cu.points[i + 1].usrCoords.slice(1), 1482 cu.points[i + 2].usrCoords.slice(1) 1483 ], [ 1484 lip1.slice(1), 1485 lip2.slice(1) 1486 ], testSegment); 1487 1488 i += 2; 1489 } else { 1490 res = [this.meetSegmentSegment(p1, p2, lip1, lip2)]; 1491 } 1492 1493 for (j = 0; j < res.length; j++) { 1494 p = res[j]; 1495 if (0 <= p[1] && p[1] <= 1) { 1496 if (cnt === nr) { 1497 /** 1498 * If the intersection point is not part of the segment, 1499 * this intersection point is set to non-existent. 1500 * This prevents jumping of the intersection points. 1501 * But it may be discussed if it is the desired behavior. 1502 */ 1503 if (testSegment && ((!li.visProp.straightfirst && p[2] < 0) || 1504 (!li.visProp.straightlast && p[2] > 1))) { 1505 return q; // break; 1506 } 1507 1508 q = new Coords(Const.COORDS_BY_USER, p[0], board); 1509 return q; // break; 1510 } 1511 cnt += 1; 1512 } 1513 } 1514 } 1515 } 1516 1517 return q; 1518 }, 1519 1520 /** 1521 * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter). 1522 * We go through each segment of the red curve and search if there is an intersection with a segemnt of the blue curve. 1523 * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines 1524 * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on 1525 * the property bezierDegree of the curves. 1526 * 1527 * @param {JXG.Curve} red 1528 * @param {JXG.Curve} blue 1529 * @param {Number} nr 1530 */ 1531 meetCurveRedBlueSegments: function (red, blue, nr) { 1532 var i, j, 1533 red1, red2, blue1, blue2, m, 1534 minX, maxX, 1535 iFound = 0, 1536 lenBlue = blue.points.length, 1537 lenRed = red.points.length; 1538 1539 if (lenBlue <= 1 || lenRed <= 1) { 1540 return [0, NaN, NaN]; 1541 } 1542 1543 for (i = 1; i < lenRed; i++) { 1544 red1 = red.points[i - 1].usrCoords; 1545 red2 = red.points[i].usrCoords; 1546 minX = Math.min(red1[1], red2[1]); 1547 maxX = Math.max(red1[1], red2[1]); 1548 1549 blue2 = blue.points[0].usrCoords; 1550 for (j = 1; j < lenBlue; j++) { 1551 blue1 = blue2; 1552 blue2 = blue.points[j].usrCoords; 1553 1554 if (Math.min(blue1[1], blue2[1]) < maxX && Math.max(blue1[1], blue2[1]) > minX) { 1555 m = this.meetSegmentSegment(red1, red2, blue1, blue2); 1556 if (m[1] >= 0.0 && m[2] >= 0.0 && 1557 // The two segments meet in the interior or at the start points 1558 ((m[1] < 1.0 && m[2] < 1.0) || 1559 // One of the curve is intersected in the very last point 1560 (i === lenRed - 1 && m[1] === 1.0) || 1561 (j === lenBlue - 1 && m[2] === 1.0))) { 1562 if (iFound === nr) { 1563 return m[0]; 1564 } 1565 1566 iFound++; 1567 } 1568 } 1569 } 1570 } 1571 1572 return [0, NaN, NaN]; 1573 }, 1574 1575 /** 1576 * Intersection of two segments. 1577 * @param {Array} p1 First point of segment 1 using homogeneous coordinates [z,x,y] 1578 * @param {Array} p2 Second point of segment 1 using homogeneous coordinates [z,x,y] 1579 * @param {Array} q1 First point of segment 2 using homogeneous coordinates [z,x,y] 1580 * @param {Array} q2 Second point of segment 2 using homogeneous coordinates [z,x,y] 1581 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 1582 * of the intersection point. The second and third entry gives the position of the intersection between the 1583 * two defining points. For example, the second entry t is defined by: intersection point = t*p1 + (1-t)*p2. 1584 **/ 1585 meetSegmentSegment: function (p1, p2, q1, q2) { 1586 var t, u, diff, 1587 li1 = Mat.crossProduct(p1, p2), 1588 li2 = Mat.crossProduct(q1, q2), 1589 c = Mat.crossProduct(li1, li2), 1590 denom = c[0]; 1591 1592 if (Math.abs(denom) < Mat.eps) { 1593 return [c, Infinity, Infinity]; 1594 } 1595 1596 diff = [q1[1] - p1[1], q1[2] - p1[2]]; 1597 1598 // Because of speed issues, evalute the determinants directly 1599 t = (diff[0] * (q2[2] - q1[2]) - diff[1] * (q2[1] - q1[1])) / denom; 1600 u = (diff[0] * (p2[2] - p1[2]) - diff[1] * (p2[1] - p1[1])) / denom; 1601 1602 return [c, t, u]; 1603 }, 1604 1605 /****************************************/ 1606 /**** BEZIER CURVE ALGORITHMS ****/ 1607 /****************************************/ 1608 1609 /** 1610 * Splits a Bezier curve segment defined by four points into 1611 * two Bezier curve segments. Dissection point is t=1/2. 1612 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1613 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1614 * @returns {Array} Array consisting of two coordinate arrays for Bezier curves. 1615 */ 1616 _bezierSplit: function (curve) { 1617 var a = [], b = [], 1618 p0, p1, p2, p00, p22, p000; 1619 1620 p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5]; 1621 p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5]; 1622 p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5]; 1623 1624 p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5]; 1625 p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5]; 1626 1627 p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5]; 1628 1629 return [[curve[0], p0, p00, p000], [p000, p22, p2, curve[3]]]; 1630 }, 1631 1632 /** 1633 * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment 1634 * from its control points. 1635 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1636 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1637 * @returns {Array} Bounding box [minX, maxY, maxX, minY] 1638 */ 1639 _bezierBbox: function (curve) { 1640 var bb = []; 1641 1642 if (curve.length === 4) { // bezierDegree == 3 1643 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX 1644 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY 1645 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX 1646 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY 1647 } else { // bezierDegree == 1 1648 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX 1649 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY 1650 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX 1651 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY 1652 } 1653 1654 return bb; 1655 }, 1656 1657 /** 1658 * Decide if two Bezier curve segments overlap by comparing their bounding boxes. 1659 * @param {Array} bb1 Bounding box of the first Bezier curve segment 1660 * @param {Array} bb2 Bounding box of the second Bezier curve segment 1661 * @returns {Boolean} true if the bounding boxes overlap, false otherwise. 1662 */ 1663 _bezierOverlap: function (bb1, bb2) { 1664 return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1]; 1665 }, 1666 1667 /** 1668 * Append list of intersection points to a list. 1669 * @private 1670 */ 1671 _bezierListConcat: function (L, Lnew, t1, t2) { 1672 var i, 1673 t2exists = Type.exists(t2), 1674 start = 0, 1675 len = Lnew.length, 1676 le = L.length; 1677 1678 if (le > 0 && len > 0 && 1679 ((L[le - 1][1] === 1 && Lnew[0][1] === 0) || 1680 (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0))) { 1681 start = 1; 1682 } 1683 1684 for (i = start; i < len; i++) { 1685 if (t2exists) { 1686 Lnew[i][2] *= 0.5; 1687 Lnew[i][2] += t2; 1688 } 1689 1690 Lnew[i][1] *= 0.5; 1691 Lnew[i][1] += t1; 1692 1693 L.push(Lnew[i]); 1694 } 1695 }, 1696 1697 /** 1698 * Find intersections of two Bezier curve segments by recursive subdivision. 1699 * Below maxlevel determine intersections by intersection line segments. 1700 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 1701 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1702 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 1703 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1704 * @param {Number} level Recursion level 1705 * @returns {Array} List of intersection points (up to nine). Each intersction point is an 1706 * array of length three (homogeneous coordinates) plus preimages. 1707 */ 1708 _bezierMeetSubdivision: function (red, blue, level) { 1709 var bbb, bbr, 1710 ar, b0, b1, r0, r1, m, 1711 p0, p1, q0, q1, 1712 L = [], 1713 maxLev = 5; // Maximum recursion level 1714 1715 bbr = this._bezierBbox(blue); 1716 bbb = this._bezierBbox(red); 1717 1718 if (!this._bezierOverlap(bbr, bbb)) { 1719 return []; 1720 } 1721 1722 if (level < maxLev) { 1723 ar = this._bezierSplit(red); 1724 r0 = ar[0]; 1725 r1 = ar[1]; 1726 1727 ar = this._bezierSplit(blue); 1728 b0 = ar[0]; 1729 b1 = ar[1]; 1730 1731 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b0, level + 1), 0.0, 0.0); 1732 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b1, level + 1), 0, 0.5); 1733 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b0, level + 1), 0.5, 0.0); 1734 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b1, level + 1), 0.5, 0.5); 1735 1736 return L; 1737 } 1738 1739 // Make homogeneous coordinates 1740 q0 = [1].concat(red[0]); 1741 q1 = [1].concat(red[3]); 1742 p0 = [1].concat(blue[0]); 1743 p1 = [1].concat(blue[3]); 1744 1745 m = this.meetSegmentSegment(q0, q1, p0, p1); 1746 1747 if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) { 1748 return [m]; 1749 } 1750 1751 return []; 1752 }, 1753 1754 /** 1755 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 1756 */ 1757 _bezierLineMeetSubdivision: function (red, blue, level, testSegment) { 1758 var bbb, bbr, 1759 ar, r0, r1, m, 1760 p0, p1, q0, q1, 1761 L = [], 1762 maxLev = 5; // Maximum recursion level 1763 1764 bbb = this._bezierBbox(blue); 1765 bbr = this._bezierBbox(red); 1766 1767 if (testSegment && !this._bezierOverlap(bbr, bbb)) { 1768 return []; 1769 } 1770 1771 if (level < maxLev) { 1772 ar = this._bezierSplit(red); 1773 r0 = ar[0]; 1774 r1 = ar[1]; 1775 1776 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r0, blue, level + 1), 0.0); 1777 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r1, blue, level + 1), 0.5); 1778 1779 return L; 1780 } 1781 1782 // Make homogeneous coordinates 1783 q0 = [1].concat(red[0]); 1784 q1 = [1].concat(red[3]); 1785 p0 = [1].concat(blue[0]); 1786 p1 = [1].concat(blue[1]); 1787 1788 m = this.meetSegmentSegment(q0, q1, p0, p1); 1789 1790 if (m[1] >= 0.0 && m[1] <= 1.0) { 1791 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) { 1792 return [m]; 1793 } 1794 } 1795 1796 return []; 1797 }, 1798 1799 /** 1800 * Find the nr-th intersection point of two Bezier curve segments. 1801 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 1802 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1803 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 1804 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1805 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 1806 * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus 1807 * preimages [x,y], t_1, t_2] of the two Bezier curve segments. 1808 * 1809 */ 1810 meetBeziersegmentBeziersegment: function (red, blue, testSegment) { 1811 var L, n, L2, i; 1812 1813 if (red.length === 4 && blue.length === 4) { 1814 L = this._bezierMeetSubdivision(red, blue, 0); 1815 } else { 1816 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment); 1817 } 1818 1819 L.sort(function (a, b) { 1820 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]); 1821 }); 1822 1823 L2 = []; 1824 for (i = 0; i < L.length; i++) { 1825 // Only push entries different from their predecessor 1826 if (i === 0 || (L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2])) { 1827 L2.push(L[i]); 1828 } 1829 } 1830 return L2; 1831 }, 1832 1833 /** 1834 * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3. 1835 * @param {JXG.Curve} red Curve with bezierDegree == 3 1836 * @param {JXG.Curve} blue Curve with bezierDegree == 3 1837 * @param {Number} nr The number of the intersection point which should be returned. 1838 * @returns {Array} The homogeneous coordinates of the nr-th intersection point. 1839 */ 1840 meetBezierCurveRedBlueSegments: function (red, blue, nr) { 1841 var p, i, j, 1842 redArr, blueArr, 1843 bbr, bbb, 1844 lenBlue = blue.points.length, 1845 lenRed = red.points.length, 1846 L = []; 1847 1848 if (lenBlue < 4 || lenRed < 4) { 1849 return [0, NaN, NaN]; 1850 } 1851 1852 for (i = 0; i < lenRed - 3; i += 3) { 1853 p = red.points; 1854 redArr = [ 1855 [p[i].usrCoords[1], p[i].usrCoords[2]], 1856 [p[i + 1].usrCoords[1], p[i + 1].usrCoords[2]], 1857 [p[i + 2].usrCoords[1], p[i + 2].usrCoords[2]], 1858 [p[i + 3].usrCoords[1], p[i + 3].usrCoords[2]] 1859 ]; 1860 1861 bbr = this._bezierBbox(redArr); 1862 1863 for (j = 0; j < lenBlue - 3; j += 3) { 1864 p = blue.points; 1865 blueArr = [ 1866 [p[j].usrCoords[1], p[j].usrCoords[2]], 1867 [p[j + 1].usrCoords[1], p[j + 1].usrCoords[2]], 1868 [p[j + 2].usrCoords[1], p[j + 2].usrCoords[2]], 1869 [p[j + 3].usrCoords[1], p[j + 3].usrCoords[2]] 1870 ]; 1871 1872 bbb = this._bezierBbox(blueArr); 1873 if (this._bezierOverlap(bbr, bbb)) { 1874 L = L.concat(this.meetBeziersegmentBeziersegment(redArr, blueArr)); 1875 if (L.length > nr) { 1876 return L[nr][0]; 1877 } 1878 } 1879 } 1880 } 1881 if (L.length > nr) { 1882 return L[nr][0]; 1883 } 1884 1885 return [0, NaN, NaN]; 1886 }, 1887 1888 bezierSegmentEval: function (t, curve) { 1889 var f, x, y, 1890 t1 = 1.0 - t; 1891 1892 x = 0; 1893 y = 0; 1894 1895 f = t1 * t1 * t1; 1896 x += f * curve[0][0]; 1897 y += f * curve[0][1]; 1898 1899 f = 3.0 * t * t1 * t1; 1900 x += f * curve[1][0]; 1901 y += f * curve[1][1]; 1902 1903 f = 3.0 * t * t * t1; 1904 x += f * curve[2][0]; 1905 y += f * curve[2][1]; 1906 1907 f = t * t * t; 1908 x += f * curve[3][0]; 1909 y += f * curve[3][1]; 1910 1911 return [1.0, x, y]; 1912 }, 1913 1914 /** 1915 * Generate the defining points of a 3rd degree bezier curve that approximates 1916 * a cricle sector defined by three arrays A, B,C, each of length three. 1917 * The coordinate arrays are given in homogeneous coordinates. 1918 * @param {Array} A First point 1919 * @param {Array} B Second point (intersection point) 1920 * @param {Array} C Third point 1921 * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve. 1922 * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1. 1923 */ 1924 bezierArc: function (A, B, C, withLegs, sgn) { 1925 var p1, p2, p3, p4, 1926 r, phi, beta, 1927 PI2 = Math.PI * 0.5, 1928 x = B[1], 1929 y = B[2], 1930 z = B[0], 1931 dataX = [], dataY = [], 1932 co, si, ax, ay, bx, by, k, v, d, matrix; 1933 1934 r = this.distance(B, A); 1935 1936 // x,y, z is intersection point. Normalize it. 1937 x /= z; 1938 y /= z; 1939 1940 phi = this.rad(A.slice(1), B.slice(1), C.slice(1)); 1941 if (sgn === -1) { 1942 phi = 2 * Math.PI - phi; 1943 } 1944 1945 p1 = A; 1946 p1[1] /= p1[0]; 1947 p1[2] /= p1[0]; 1948 p1[0] /= p1[0]; 1949 1950 p4 = p1.slice(0); 1951 1952 if (withLegs) { 1953 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]]; 1954 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]]; 1955 } else { 1956 dataX = [p1[1]]; 1957 dataY = [p1[2]]; 1958 } 1959 1960 while (phi > Mat.eps) { 1961 if (phi > PI2) { 1962 beta = PI2; 1963 phi -= PI2; 1964 } else { 1965 beta = phi; 1966 phi = 0; 1967 } 1968 1969 co = Math.cos(sgn * beta); 1970 si = Math.sin(sgn * beta); 1971 1972 matrix = [ 1973 [1, 0, 0], 1974 [x * (1 - co) + y * si, co, -si], 1975 [y * (1 - co) - x * si, si, co] 1976 ]; 1977 v = Mat.matVecMult(matrix, p1); 1978 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]]; 1979 1980 ax = p1[1] - x; 1981 ay = p1[2] - y; 1982 bx = p4[1] - x; 1983 by = p4[2] - y; 1984 1985 d = Math.sqrt((ax + bx) * (ax + bx) + (ay + by) * (ay + by)); 1986 1987 if (Math.abs(by - ay) > Mat.eps) { 1988 k = (ax + bx) * (r / d - 0.5) / (by - ay) * 8 / 3; 1989 } else { 1990 k = (ay + by) * (r / d - 0.5) / (ax - bx) * 8 / 3; 1991 } 1992 1993 p2 = [1, p1[1] - k * ay, p1[2] + k * ax]; 1994 p3 = [1, p4[1] + k * by, p4[2] - k * bx]; 1995 1996 dataX = dataX.concat([p2[1], p3[1], p4[1]]); 1997 dataY = dataY.concat([p2[2], p3[2], p4[2]]); 1998 p1 = p4.slice(0); 1999 } 2000 2001 if (withLegs) { 2002 dataX = dataX.concat([ p4[1] + 0.333 * (x - p4[1]), p4[1] + 0.666 * (x - p4[1]), x]); 2003 dataY = dataY.concat([ p4[2] + 0.333 * (y - p4[2]), p4[2] + 0.666 * (y - p4[2]), y]); 2004 } 2005 2006 return [dataX, dataY]; 2007 }, 2008 2009 /****************************************/ 2010 /**** PROJECTIONS ****/ 2011 /****************************************/ 2012 2013 /** 2014 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 2015 * nearest one of the two intersection points of the line through the given point and the circles 2016 * center. 2017 * @param {JXG.Point,JXG.Coords} point Point to project or coords object to project. 2018 * @param {JXG.Circle} circle Circle on that the point is projected. 2019 * @param {JXG.Board} [board=point.board] Reference to the board 2020 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2021 */ 2022 projectPointToCircle: function (point, circle, board) { 2023 var dist, P, x, y, factor, 2024 M = circle.center.coords.usrCoords; 2025 2026 if (!Type.exists(board)) { 2027 board = point.board; 2028 } 2029 2030 // gave us a point 2031 if (Type.isPoint(point)) { 2032 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords); 2033 P = point.coords.usrCoords; 2034 // gave us coords 2035 } else { 2036 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords); 2037 P = point.usrCoords; 2038 } 2039 2040 if (Math.abs(dist) < Mat.eps) { 2041 dist = Mat.eps; 2042 } 2043 2044 factor = circle.Radius() / dist; 2045 x = M[1] + factor * (P[1] - M[1]); 2046 y = M[2] + factor * (P[2] - M[2]); 2047 2048 return new Coords(Const.COORDS_BY_USER, [x, y], board); 2049 }, 2050 2051 /** 2052 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 2053 * intersection point of the given line and its perpendicular through the given point. 2054 * @param {JXG.Point} point Point to project. 2055 * @param {JXG.Line} line Line on that the point is projected. 2056 * @param {JXG.Board} [board=point.board] Reference to a board. 2057 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 2058 */ 2059 projectPointToLine: function (point, line, board) { 2060 // Homogeneous version 2061 var v = [0, line.stdform[1], line.stdform[2]]; 2062 2063 if (!Type.exists(board)) { 2064 board = point.board; 2065 } 2066 2067 v = Mat.crossProduct(v, point.coords.usrCoords); 2068 //return this.meetLineLine(v, line.stdform, 0, board); 2069 return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(v, line.stdform), board); 2070 }, 2071 2072 /** 2073 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 2074 * segment defined by two coordinate arrays. 2075 * @param {Array} p Point to project. 2076 * @param {Array} q1 Start point of the line segment on that the point is projected. 2077 * @param {Array} q2 End point of the line segment on that the point is projected. 2078 * @returns {Array} The coordinates of the projection of the given point on the given segment 2079 * and the factor that determines the projected point as a convex combination of the 2080 * two endpoints q1 and q2 of the segment. 2081 */ 2082 projectCoordsToSegment: function (p, q1, q2) { 2083 var t, denom, c, 2084 s = [q2[1] - q1[1], q2[2] - q1[2]], 2085 v = [p[1] - q1[1], p[2] - q1[2]]; 2086 2087 /** 2088 * If the segment has length 0, i.e. is a point, 2089 * the projection is equal to that point. 2090 */ 2091 if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) { 2092 return [q1, 0]; 2093 } 2094 2095 t = Mat.innerProduct(v, s); 2096 denom = Mat.innerProduct(s, s); 2097 t /= denom; 2098 2099 return [ [1, t * s[0] + q1[1], t * s[1] + q1[2]], t]; 2100 }, 2101 2102 /** 2103 * Finds the coordinates of the closest point on a Bezier segment of a 2104 * {@link JXG.Curve} to a given coordinate array. 2105 * @param {Array} pos Point to project in homogeneous coordinates. 2106 * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3. 2107 * @param {Number} start Number of the Bezier segment of the curve. 2108 * @returns {Array} The coordinates of the projection of the given point 2109 * on the given Bezier segment and the preimage of the curve which 2110 * determines the closest point. 2111 */ 2112 projectCoordsToBeziersegment: function (pos, curve, start) { 2113 var t0, 2114 minfunc = function (t) { 2115 var z = [1, curve.X(start + t), curve.Y(start + t)]; 2116 2117 z[1] -= pos[1]; 2118 z[2] -= pos[2]; 2119 2120 return z[1] * z[1] + z[2] * z[2]; 2121 }; 2122 2123 t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]); 2124 2125 return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0]; 2126 }, 2127 2128 /** 2129 * Calculates the coordinates of the projection of a given point on a given curve. 2130 * Uses {@link #projectCoordsToCurve}. 2131 * @param {JXG.Point} point Point to project. 2132 * @param {JXG.Curve} curve Curve on that the point is projected. 2133 * @param {JXG.Board} [board=point.board] Reference to a board. 2134 * @see #projectCoordsToCurve 2135 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph. 2136 */ 2137 projectPointToCurve: function (point, curve, board) { 2138 if (!Type.exists(board)) { 2139 board = point.board; 2140 } 2141 2142 var x = point.X(), 2143 y = point.Y(), 2144 t = point.position || 0.0, 2145 result = this.projectCoordsToCurve(x, y, t, curve, board); 2146 2147 point.position = result[1]; 2148 2149 return result[0]; 2150 }, 2151 2152 /** 2153 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 2154 * function graphs this is the 2155 * intersection point of the curve and the parallel to y-axis through the given point. 2156 * @param {Number} x coordinate to project. 2157 * @param {Number} y coordinate to project. 2158 * @param {Number} t start value for newtons method 2159 * @param {JXG.Curve} curve Curve on that the point is projected. 2160 * @param {JXG.Board} [board=curve.board] Reference to a board. 2161 * @see #projectPointToCurve 2162 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and 2163 * the position on the curve. 2164 */ 2165 projectCoordsToCurve: function (x, y, t, curve, board) { 2166 var newCoords, newCoordsObj, i, j, 2167 x0, y0, x1, y1, mindist, dist, lbda, li, v, coords, d, 2168 p1, p2, q1, q2, res, 2169 minfunc, tnew, fnew, fold, delta, steps, 2170 infty = Number.POSITIVE_INFINITY; 2171 2172 if (!Type.exists(board)) { 2173 board = curve.board; 2174 } 2175 2176 if (curve.visProp.curvetype === 'plot') { 2177 t = 0; 2178 mindist = infty; 2179 2180 if (curve.numberPoints === 0) { 2181 newCoords = [0, 1, 1]; 2182 } else { 2183 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 2184 } 2185 2186 if (curve.numberPoints > 1) { 2187 2188 v = [1, x, y]; 2189 if (curve.bezierDegree === 3) { 2190 j = 0; 2191 } else { 2192 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 2193 } 2194 for (i = 0; i < curve.numberPoints - 1; i++) { 2195 if (curve.bezierDegree === 3) { 2196 res = this.projectCoordsToBeziersegment(v, curve, j); 2197 } else { 2198 p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)]; 2199 res = this.projectCoordsToSegment(v, p1, p2); 2200 } 2201 lbda = res[1]; 2202 coords = res[0]; 2203 2204 if (0.0 <= lbda && lbda <= 1.0) { 2205 dist = this.distance(coords, v); 2206 d = i + lbda; 2207 } else if (lbda < 0.0) { 2208 coords = p1; 2209 dist = this.distance(p1, v); 2210 d = i; 2211 } else if (lbda > 1.0 && i === curve.numberPoints - 2) { 2212 coords = p2; 2213 dist = this.distance(coords, v); 2214 d = curve.numberPoints - 1; 2215 } 2216 2217 if (dist < mindist) { 2218 mindist = dist; 2219 t = d; 2220 newCoords = coords; 2221 } 2222 2223 if (curve.bezierDegree === 3) { 2224 j++; 2225 i += 2; 2226 } else { 2227 p1 = p2; 2228 } 2229 } 2230 } 2231 2232 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board); 2233 } else { // 'parameter', 'polar', 'functiongraph' 2234 minfunc = function (t) { 2235 var dx = x - curve.X(t), 2236 dy = y - curve.Y(t); 2237 return dx * dx + dy * dy; 2238 }; 2239 2240 fold = minfunc(t); 2241 steps = 50; 2242 delta = (curve.maxX() - curve.minX()) / steps; 2243 tnew = curve.minX(); 2244 2245 for (i = 0; i < steps; i++) { 2246 fnew = minfunc(tnew); 2247 2248 if (fnew < fold) { 2249 t = tnew; 2250 fold = fnew; 2251 } 2252 2253 tnew += delta; 2254 } 2255 2256 //t = Numerics.root(Numerics.D(minfunc), t); 2257 t = Numerics.fminbr(minfunc, [t - delta, t + delta]); 2258 2259 if (t < curve.minX()) { 2260 t = curve.maxX() + t - curve.minX(); 2261 } 2262 2263 // Cyclically 2264 if (t > curve.maxX()) { 2265 t = curve.minX() + t - curve.maxX(); 2266 } 2267 2268 newCoordsObj = new Coords(Const.COORDS_BY_USER, [curve.X(t), curve.Y(t)], board); 2269 } 2270 2271 return [curve.updateTransform(newCoordsObj), t]; 2272 }, 2273 2274 /** 2275 * Calculates the coordinates of the closest orthogonal projection of a given coordinate array onto the 2276 * border of a polygon. 2277 * @param {Array} p Point to project. 2278 * @param {JXG.Polygon} pol Polygon element 2279 * @returns {Array} The coordinates of the closest projection of the given point to the border of the polygon. 2280 */ 2281 projectCoordsToPolygon: function (p, pol) { 2282 var i, 2283 len = pol.vertices.length, 2284 d_best = Infinity, 2285 d, 2286 projection, 2287 bestprojection; 2288 2289 for (i = 0; i < len; i++) { 2290 projection = JXG.Math.Geometry.projectCoordsToSegment( 2291 p, 2292 pol.vertices[i].coords.usrCoords, 2293 pol.vertices[(i + 1) % len].coords.usrCoords 2294 ); 2295 2296 d = JXG.Math.Geometry.distance(projection[0], p, 3); 2297 if (0 <= projection[1] && projection[1] <= 1 && d < d_best) { 2298 bestprojection = projection[0].slice(0); 2299 d_best = d; 2300 } 2301 } 2302 return bestprojection; 2303 }, 2304 2305 /** 2306 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 2307 * one or more curves of curveType 'plot'. Uses {@link #projectPointToCurve}. 2308 * @param {JXG.Point} point Point to project. 2309 * @param {JXG.Turtle} turtle on that the point is projected. 2310 * @param {JXG.Board} [board=point.board] Reference to a board. 2311 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle. 2312 */ 2313 projectPointToTurtle: function (point, turtle, board) { 2314 var newCoords, t, x, y, i, dist, el, minEl, 2315 np = 0, 2316 npmin = 0, 2317 mindist = Number.POSITIVE_INFINITY, 2318 len = turtle.objects.length; 2319 2320 if (!Type.exists(board)) { 2321 board = point.board; 2322 } 2323 2324 // run through all curves of this turtle 2325 for (i = 0; i < len; i++) { 2326 el = turtle.objects[i]; 2327 2328 if (el.elementClass === Const.OBJECT_CLASS_CURVE) { 2329 newCoords = this.projectPointToCurve(point, el); 2330 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 2331 2332 if (dist < mindist) { 2333 x = newCoords.usrCoords[1]; 2334 y = newCoords.usrCoords[2]; 2335 t = point.position; 2336 mindist = dist; 2337 minEl = el; 2338 npmin = np; 2339 } 2340 np += el.numberPoints; 2341 } 2342 } 2343 2344 newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board); 2345 point.position = t + npmin; 2346 2347 return minEl.updateTransform(newCoords); 2348 }, 2349 2350 /** 2351 * Trivial projection of a point to another point. 2352 * @param {JXG.Point} point Point to project (not used). 2353 * @param {JXG.Point} dest Point on that the point is projected. 2354 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2355 */ 2356 projectPointToPoint: function (point, dest) { 2357 return dest.coords; 2358 }, 2359 2360 /** 2361 * 2362 * @param {JXG.Point|JXG.Coords} point 2363 * @param {JXG.Board} [board] 2364 */ 2365 projectPointToBoard: function (point, board) { 2366 var i, l, c, 2367 brd = board || point.board, 2368 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx 2369 config = [ 2370 // left 2371 [1, 1, 0, 0, 3, 0, 1], 2372 // top 2373 [-1, 2, 1, 0, 1, 2, 1], 2374 // right 2375 [-1, 1, 2, 2, 1, 2, 3], 2376 // bottom 2377 [1, 2, 3, 0, 3, 2, 3] 2378 ], 2379 coords = point.coords || point, 2380 bbox = brd.getBoundingBox(); 2381 2382 for (i = 0; i < 4; i++) { 2383 c = config[i]; 2384 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) { 2385 // define border 2386 l = Mat.crossProduct([1, bbox[c[3]], bbox[c[4]]], [1, bbox[c[5]], bbox[c[6]]]); 2387 l[3] = 0; 2388 l = Mat.normalize(l); 2389 2390 // project point 2391 coords = this.projectPointToLine({coords: coords}, {stdform: l}, brd); 2392 } 2393 } 2394 2395 return coords; 2396 }, 2397 2398 /** 2399 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 2400 * coordinates. For lines this can be line.stdform. 2401 * @param {Array} point Homogeneous coordinates of a point. 2402 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 2403 * @returns {Number} Distance of the point to the line. 2404 */ 2405 distPointLine: function (point, line) { 2406 var a = line[1], 2407 b = line[2], 2408 c = line[0], 2409 nom; 2410 2411 if (Math.abs(a) + Math.abs(b) < Mat.eps) { 2412 return Number.POSITIVE_INFINITY; 2413 } 2414 2415 nom = a * point[1] + b * point[2] + c; 2416 a *= a; 2417 b *= b; 2418 2419 return Math.abs(nom) / Math.sqrt(a + b); 2420 }, 2421 2422 2423 /** 2424 * Helper function to create curve which displays a Reuleaux polygons. 2425 * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically, 2426 * these point list is the array vrtices of a regular polygon. 2427 * @param {Number} nr Number of vertices 2428 * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values 2429 * for the start and the end of the paramtric curve. array may be used as parent array of a {@link JXG.Curve}. 2430 * @example 2431 * var A = brd.create('point',[-2,-2]); 2432 * var B = brd.create('point',[0,1]); 2433 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2434 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2435 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2436 * 2437 * </pre><div id="2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div> 2438 * <script type="text/javascript"> 2439 * var brd = JXG.JSXGraph.initBoard('2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false}); 2440 * var A = brd.create('point',[-2,-2]); 2441 * var B = brd.create('point',[0,1]); 2442 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2443 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2444 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2445 * </script><pre> 2446 */ 2447 reuleauxPolygon: function (points, nr) { 2448 var beta, 2449 pi2 = Math.PI * 2, 2450 pi2_n = pi2 / nr, 2451 diag = (nr - 1) / 2, 2452 d = 0, 2453 makeFct = function (which, trig) { 2454 return function (t, suspendUpdate) { 2455 var t1 = (t % pi2 + pi2) % pi2, 2456 j = Math.floor(t1 / pi2_n) % nr; 2457 2458 if (!suspendUpdate) { 2459 d = points[0].Dist(points[diag]); 2460 beta = Mat.Geometry.rad([points[0].X() + 1, points[0].Y()], points[0], points[diag % nr]); 2461 } 2462 2463 if (isNaN(j)) { 2464 return j; 2465 } 2466 2467 t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta; 2468 2469 return points[j][which]() + d * Math[trig](t1); 2470 }; 2471 }; 2472 2473 return [makeFct('X', 'cos'), makeFct('Y', 'sin'), 0, pi2]; 2474 } 2475 }); 2476 2477 return Mat.Geometry; 2478 }); 2479