1 /* 2 Copyright 2008-2014 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(Type.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 * Computes the intersection of a pair of lines, circles or both. 934 * It uses the internal data array stdform of these elements. 935 * @param {Array} el1 stdform of the first element (line or circle) 936 * @param {Array} el2 stdform of the second element (line or circle) 937 * @param {Number} i Index of the intersection point that should be returned. 938 * @param board Reference to the board. 939 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 940 * Which point will be returned is determined by i. 941 */ 942 meet: function (el1, el2, i, board) { 943 var result, 944 eps = Mat.eps; 945 946 // line line 947 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { 948 result = this.meetLineLine(el1, el2, i, board); 949 // circle line 950 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { 951 result = this.meetLineCircle(el2, el1, i, board); 952 // line circle 953 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { 954 result = this.meetLineCircle(el1, el2, i, board); 955 // circle circle 956 } else { 957 result = this.meetCircleCircle(el1, el2, i, board); 958 } 959 960 return result; 961 }, 962 963 /** 964 * Intersection of the line with the board 965 * @param {Array} line stdform of the line 966 * @param {JXG.Board} board reference to a board. 967 * @param {Number} margin optional margin, to avoid the display of the small sides of lines. 968 * @return {Array} [intersection coords 1, intersection coords 2] 969 */ 970 meetLineBoard: function (line, board, margin) { 971 // Intersect the line with the four borders of the board. 972 var s = [], intersect1, intersect2, i, j; 973 974 if (!Type.exists(margin)) { 975 margin = 0; 976 } 977 978 // top 979 s[0] = Mat.crossProduct(line, [margin, 0, 1]); 980 // left 981 s[1] = Mat.crossProduct(line, [margin, 1, 0]); 982 // bottom 983 s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]); 984 // right 985 s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]); 986 987 // Normalize the intersections 988 for (i = 0; i < 4; i++) { 989 if (Math.abs(s[i][0]) > Mat.eps) { 990 for (j = 2; j > 0; j--) { 991 s[i][j] /= s[i][0]; 992 } 993 s[i][0] = 1.0; 994 } 995 } 996 997 // line is parallel to "left", take "top" and "bottom" 998 if (Math.abs(s[1][0]) < Mat.eps) { 999 intersect1 = s[0]; // top 1000 intersect2 = s[2]; // bottom 1001 // line is parallel to "top", take "left" and "right" 1002 } else if (Math.abs(s[0][0]) < Mat.eps) { 1003 intersect1 = s[1]; // left 1004 intersect2 = s[3]; // right 1005 // left intersection out of board (above) 1006 } else if (s[1][2] < 0) { 1007 intersect1 = s[0]; // top 1008 1009 // right intersection out of board (below) 1010 if (s[3][2] > board.canvasHeight) { 1011 intersect2 = s[2]; // bottom 1012 } else { 1013 intersect2 = s[3]; // right 1014 } 1015 // left intersection out of board (below) 1016 } else if (s[1][2] > board.canvasHeight) { 1017 intersect1 = s[2]; // bottom 1018 1019 // right intersection out of board (above) 1020 if (s[3][2] < 0) { 1021 intersect2 = s[0]; // top 1022 } else { 1023 intersect2 = s[3]; // right 1024 } 1025 } else { 1026 intersect1 = s[1]; // left 1027 1028 // right intersection out of board (above) 1029 if (s[3][2] < 0) { 1030 intersect2 = s[0]; // top 1031 // right intersection out of board (below) 1032 } else if (s[3][2] > board.canvasHeight) { 1033 intersect2 = s[2]; // bottom 1034 } else { 1035 intersect2 = s[3]; // right 1036 } 1037 } 1038 1039 intersect1 = new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board); 1040 intersect2 = new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board); 1041 return [intersect1, intersect2]; 1042 }, 1043 1044 /** 1045 * Intersection of two lines. 1046 * @param {Array} l1 stdform of the first line 1047 * @param {Array} l2 stdform of the second line 1048 * @param {number} i unused 1049 * @param {JXG.Board} board Reference to the board. 1050 * @returns {JXG.Coords} Coordinates of the intersection point. 1051 */ 1052 meetLineLine: function (l1, l2, i, board) { 1053 var s = Mat.crossProduct(l1, l2); 1054 1055 if (Math.abs(s[0]) > Mat.eps) { 1056 s[1] /= s[0]; 1057 s[2] /= s[0]; 1058 s[0] = 1.0; 1059 } 1060 return new Coords(Const.COORDS_BY_USER, s, board); 1061 }, 1062 1063 /** 1064 * Intersection of line and circle. 1065 * @param {Array} lin stdform of the line 1066 * @param {Array} circ stdform of the circle 1067 * @param {number} i number of the returned intersection point. 1068 * i==0: use the positive square root, 1069 * i==1: use the negative square root. 1070 * @param {JXG.Board} board Reference to a board. 1071 * @returns {JXG.Coords} Coordinates of the intersection point 1072 */ 1073 meetLineCircle: function (lin, circ, i, board) { 1074 var a, b, c, d, n, 1075 A, B, C, k, t; 1076 1077 // Radius is zero, return center of circle 1078 if (circ[4] < Mat.eps) { 1079 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) { 1080 return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board); 1081 } 1082 1083 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board); 1084 } 1085 1086 c = circ[0]; 1087 b = circ.slice(1, 3); 1088 a = circ[3]; 1089 d = lin[0]; 1090 n = lin.slice(1, 3); 1091 1092 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 1093 /* 1094 var nn = n[0]*n[0]+n[1]*n[1]; 1095 A = a*nn; 1096 B = (b[0]*n[1]-b[1]*n[0])*nn; 1097 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 1098 */ 1099 A = a; 1100 B = (b[0] * n[1] - b[1] * n[0]); 1101 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 1102 1103 k = B * B - 4 * A * C; 1104 if (k >= 0) { 1105 k = Math.sqrt(k); 1106 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)]; 1107 1108 return ((i === 0) ? 1109 new Coords(Const.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0], -t[0] * n[0] - d * n[1]], board) : 1110 new Coords(Const.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0], -t[1] * n[0] - d * n[1]], board) 1111 ); 1112 } 1113 1114 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1115 }, 1116 1117 /** 1118 * Intersection of two circles. 1119 * @param {Array} circ1 stdform of the first circle 1120 * @param {Array} circ2 stdform of the second circle 1121 * @param {number} i number of the returned intersection point. 1122 * i==0: use the positive square root, 1123 * i==1: use the negative square root. 1124 * @param {JXG.Board} board Reference to the board. 1125 * @returns {JXG.Coords} Coordinates of the intersection point 1126 */ 1127 meetCircleCircle: function (circ1, circ2, i, board) { 1128 var radicalAxis; 1129 1130 // Radius are zero, return center of circle, if on other circle 1131 if (circ1[4] < Mat.eps) { 1132 if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < Mat.eps) { 1133 return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board); 1134 } 1135 1136 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1137 } 1138 1139 // Radius are zero, return center of circle, if on other circle 1140 if (circ2[4] < Mat.eps) { 1141 if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < Mat.eps) { 1142 return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board); 1143 } 1144 1145 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board); 1146 } 1147 1148 radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0], 1149 circ2[3] * circ1[1] - circ1[3] * circ2[1], 1150 circ2[3] * circ1[2] - circ1[3] * circ2[2], 1151 0, 1, Infinity, Infinity, Infinity]; 1152 radicalAxis = Mat.normalize(radicalAxis); 1153 1154 return this.meetLineCircle(radicalAxis, circ1, i, board); 1155 }, 1156 1157 /** 1158 * Compute an intersection of the curves c1 and c2. 1159 * We want to find values t1, t2 such that 1160 * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 1161 * 1162 * Methods: segment-wise intersections (default) or generalized Newton method. 1163 * @param {JXG.Curve} c1 Curve, Line or Circle 1164 * @param {JXG.Curve} c2 Curve, Line or Circle 1165 * @param {Number} nr the nr-th intersection point will be returned. 1166 * @param {Number} t2ini not longer used. 1167 * @param {JXG.Board} [board=c1.board] Reference to a board object. 1168 * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'. 1169 * @returns {JXG.Coords} intersection point 1170 */ 1171 meetCurveCurve: function (c1, c2, nr, t2ini, board, method) { 1172 var co; 1173 1174 if (Type.exists(method) && method === 'newton') { 1175 co = Numerics.generalizedNewton(c1, c2, nr, t2ini); 1176 } else { 1177 if (c1.bezierDegree === 3 && c2.bezierDegree === 3) { 1178 co = this.meetBezierCurveRedBlueSegments(c1, c2, nr); 1179 } else { 1180 co = this.meetCurveRedBlueSegments(c1, c2, nr); 1181 } 1182 } 1183 1184 return (new Coords(Const.COORDS_BY_USER, co, board)); 1185 }, 1186 1187 /** 1188 * Intersection of curve with line, 1189 * Order of input does not matter for el1 and el2. 1190 * @param {JXG.Curve,JXG.Line} el1 Curve or Line 1191 * @param {JXG.Curve,JXG.Line} el2 Curve or Line 1192 * @param {Number} nr the nr-th intersection point will be returned. 1193 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1194 * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection 1195 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1196 * the ideal point [0,1,0] is returned. 1197 */ 1198 meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) { 1199 var v = [0, NaN, NaN], i, cu, li; 1200 1201 if (!Type.exists(board)) { 1202 board = el1.board; 1203 } 1204 1205 if (el1.elementClass === Const.OBJECT_CLASS_CURVE) { 1206 cu = el1; 1207 li = el2; 1208 } else { 1209 cu = el2; 1210 li = el1; 1211 } 1212 1213 if (cu.visProp.curvetype === 'plot') { 1214 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect); 1215 } else { 1216 v = this.meetCurveLineContinuous(cu, li, nr, board); 1217 } 1218 1219 return v; 1220 }, 1221 1222 /** 1223 * Intersection of line and curve, continuous case. 1224 * Finds the nr-the intersection point 1225 * Uses {@link JXG.Math.Geometry#meetCurveLineDiscrete} as a first approximation. 1226 * A more exact solution is then found with {@link JXG.Math.Numerics#meetCurveLineDiscrete}. 1227 * 1228 * @param {JXG.Curve} cu Curve 1229 * @param {JXG.Line} li Line 1230 * @param {Number} nr Will return the nr-th intersection point. 1231 * @param {JXG.Board} board 1232 * 1233 */ 1234 meetCurveLineContinuous: function (cu, li, nr, board, testSegment) { 1235 var t, func0, func1, v, x, y, z, 1236 eps = Mat.eps * 10; 1237 1238 v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment); 1239 x = v.usrCoords[1]; 1240 y = v.usrCoords[2]; 1241 1242 func0 = function (t) { 1243 var c1 = x - cu.X(t), 1244 c2 = y - cu.Y(t); 1245 1246 return Math.sqrt(c1 * c1 + c2 * c2); 1247 }; 1248 1249 func1 = function (t) { 1250 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1251 return v * v; 1252 }; 1253 1254 // Find t 1255 t = Numerics.root(func0, [cu.minX(), cu.maxX()]); 1256 // Compute "exect" t 1257 t = Numerics.root(func1, t); 1258 1259 // Is the point on the line? 1260 if (Math.abs(func1(t)) > eps) { 1261 z = NaN; 1262 } else { 1263 z = 1.0; 1264 } 1265 1266 return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1267 }, 1268 1269 /** 1270 * Intersection of line and curve, continuous case. 1271 * Segments are treated as lines. Finding the nr-the intersection point 1272 * works for nr=0,1 only. 1273 * 1274 * @private 1275 * @deprecated 1276 * @param {JXG.Curve} cu Curve 1277 * @param {JXG.Line} li Line 1278 * @param {Number} nr Will return the nr-th intersection point. 1279 * @param {JXG.Board} board 1280 * 1281 * BUG: does not respect cu.minX() and cu.maxX() 1282 */ 1283 meetCurveLineContinuousOld: function (cu, li, nr, board) { 1284 var t, t2, i, func, z, 1285 tnew, steps, delta, tstart, tend, cux, cuy, 1286 eps = Mat.eps * 10; 1287 1288 func = function (t) { 1289 // return li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1290 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1291 return v * v; 1292 }; 1293 1294 // Find some intersection point 1295 if (this.meetCurveLineContinuous.t1memo) { 1296 tstart = this.meetCurveLineContinuous.t1memo; 1297 t = Numerics.root(func, tstart); 1298 } else { 1299 tstart = cu.minX(); 1300 tend = cu.maxX(); 1301 t = Numerics.root(func, [tstart, tend]); 1302 } 1303 1304 this.meetCurveLineContinuous.t1memo = t; 1305 cux = cu.X(t); 1306 cuy = cu.Y(t); 1307 1308 // Find second intersection point 1309 if (nr === 1) { 1310 if (this.meetCurveLineContinuous.t2memo) { 1311 tstart = this.meetCurveLineContinuous.t2memo; 1312 } 1313 t2 = Numerics.root(func, tstart); 1314 1315 if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) { 1316 steps = 20; 1317 delta = (cu.maxX() - cu.minX()) / steps; 1318 tnew = cu.minX(); 1319 1320 for (i = 0; i < steps; i++) { 1321 t2 = Numerics.root(func, [tnew, tnew + delta]); 1322 1323 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) { 1324 break; 1325 } 1326 1327 tnew += delta; 1328 } 1329 } 1330 t = t2; 1331 this.meetCurveLineContinuous.t2memo = t; 1332 } 1333 1334 // Is the point on the line? 1335 if (Math.abs(func(t)) > eps) { 1336 z = NaN; 1337 } else { 1338 z = 1.0; 1339 } 1340 1341 return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1342 }, 1343 1344 /** 1345 * Intersection of line and curve, discrete case. 1346 * Segments are treated as lines. 1347 * Finding the nr-th intersection point should work for all nr. 1348 * @param {JXG.Curve} cu 1349 * @param {JXG.Line} li 1350 * @param {Number} nr 1351 * @param {JXG.Board} board 1352 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the 1353 * line defined by the segment 1354 * 1355 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1356 * the ideal point [0,1,0] is returned. 1357 */ 1358 meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) { 1359 var i, j, 1360 p1, p2, p, q, 1361 d, res, 1362 cnt = 0, 1363 len = cu.numberPoints; 1364 1365 // In case, no intersection will be found we will take this 1366 q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board); 1367 1368 p2 = cu.points[0].usrCoords; 1369 for (i = 1; i < len; i++) { 1370 p1 = p2.slice(0); 1371 p2 = cu.points[i].usrCoords; 1372 d = this.distance(p1, p2); 1373 1374 // The defining points are not identical 1375 if (d > Mat.eps) { 1376 if (cu.bezierDegree === 3) { 1377 res = this.meetBeziersegmentBeziersegment([ 1378 cu.points[i - 1].usrCoords.slice(1), 1379 cu.points[i].usrCoords.slice(1), 1380 cu.points[i + 1].usrCoords.slice(1), 1381 cu.points[i + 2].usrCoords.slice(1) 1382 ], [ 1383 li.point1.coords.usrCoords.slice(1), 1384 li.point2.coords.usrCoords.slice(1) 1385 ], testSegment); 1386 1387 i += 2; 1388 } else { 1389 res = [this.meetSegmentSegment(p1, p2, li.point1.coords.usrCoords, li.point2.coords.usrCoords)]; 1390 } 1391 1392 for (j = 0; j < res.length; j++) { 1393 p = res[j]; 1394 if (0 <= p[1] && p[1] <= 1) { 1395 if (cnt === nr) { 1396 /** 1397 * If the intersection point is not part of the segment, 1398 * this intersection point is set to non-existent. 1399 * This prevents jumping of the intersection points. 1400 * But it may be discussed if it is the desired behavior. 1401 */ 1402 if (testSegment && ((!li.visProp.straightfirst && p[2] < 0) || 1403 (!li.visProp.straightlast && p[2] > 1))) { 1404 return q; // break; 1405 } 1406 1407 q = new Coords(Const.COORDS_BY_USER, p[0], board); 1408 return q; // break; 1409 } 1410 cnt += 1; 1411 } 1412 } 1413 } 1414 } 1415 1416 return q; 1417 }, 1418 1419 /** 1420 * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter). 1421 * We go through each segment of the red curve and search if there is an intersection with a segemnt of the blue curve. 1422 * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines 1423 * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on 1424 * the property bezierDegree of the curves. 1425 * 1426 * @param {JXG.Curve} red 1427 * @param {JXG.Curve} blue 1428 * @param {Number} nr 1429 */ 1430 meetCurveRedBlueSegments: function (red, blue, nr) { 1431 var i, j, 1432 red1, red2, blue1, blue2, m, 1433 minX, maxX, 1434 iFound = 0, 1435 lenBlue = blue.points.length, 1436 lenRed = red.points.length; 1437 1438 if (lenBlue <= 1 || lenRed <= 1) { 1439 return [0, NaN, NaN]; 1440 } 1441 1442 for (i = 1; i < lenRed; i++) { 1443 red1 = red.points[i - 1].usrCoords; 1444 red2 = red.points[i].usrCoords; 1445 minX = Math.min(red1[1], red2[1]); 1446 maxX = Math.max(red1[1], red2[1]); 1447 1448 blue2 = blue.points[0].usrCoords; 1449 for (j = 1; j < lenBlue; j++) { 1450 blue1 = blue2; 1451 blue2 = blue.points[j].usrCoords; 1452 1453 if (Math.min(blue1[1], blue2[1]) < maxX && Math.max(blue1[1], blue2[1]) > minX) { 1454 m = this.meetSegmentSegment(red1, red2, blue1, blue2); 1455 if (m[1] >= 0.0 && m[2] >= 0.0 && 1456 // The two segments meet in the interior or at the start points 1457 ((m[1] < 1.0 && m[2] < 1.0) || 1458 // One of the curve is intersected in the very last point 1459 (i === lenRed - 1 && m[1] === 1.0) || 1460 (j === lenBlue - 1 && m[2] === 1.0))) { 1461 if (iFound === nr) { 1462 return m[0]; 1463 } 1464 1465 iFound++; 1466 } 1467 } 1468 } 1469 } 1470 1471 return [0, NaN, NaN]; 1472 }, 1473 1474 /** 1475 * Intersection of two segments. 1476 * @param {Array} p1 First point of segment 1 using homogeneous coordinates [z,x,y] 1477 * @param {Array} p2 Second point of segment 1 using homogeneous coordinates [z,x,y] 1478 * @param {Array} q1 First point of segment 2 using homogeneous coordinates [z,x,y] 1479 * @param {Array} q2 Second point of segment 2 using homogeneous coordinates [z,x,y] 1480 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 1481 * of the intersection point. The second and third entry gives the position of the intersection between the 1482 * two defining points. For example, the second entry t is defined by: intersection point = t*p1 + (1-t)*p2. 1483 **/ 1484 meetSegmentSegment: function (p1, p2, q1, q2) { 1485 var t, u, diff, 1486 li1 = Mat.crossProduct(p1, p2), 1487 li2 = Mat.crossProduct(q1, q2), 1488 c = Mat.crossProduct(li1, li2), 1489 denom = c[0]; 1490 1491 if (Math.abs(denom) < Mat.eps) { 1492 return [c, Infinity, Infinity]; 1493 } 1494 1495 diff = [q1[1] - p1[1], q1[2] - p1[2]]; 1496 1497 // Because of speed issues, evalute the determinants directly 1498 t = (diff[0] * (q2[2] - q1[2]) - diff[1] * (q2[1] - q1[1])) / denom; 1499 u = (diff[0] * (p2[2] - p1[2]) - diff[1] * (p2[1] - p1[1])) / denom; 1500 1501 return [c, t, u]; 1502 }, 1503 1504 /****************************************/ 1505 /**** BEZIER CURVE ALGORITHMS ****/ 1506 /****************************************/ 1507 1508 /** 1509 * Splits a Bezier curve segment defined by four points into 1510 * two Bezier curve segments. Dissection point is t=1/2. 1511 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1512 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1513 * @returns {Array} Array consisting of two coordinate arrays for Bezier curves. 1514 */ 1515 _bezierSplit: function (curve) { 1516 var a = [], b = [], 1517 p0, p1, p2, p00, p22, p000; 1518 1519 p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5]; 1520 p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5]; 1521 p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5]; 1522 1523 p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5]; 1524 p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5]; 1525 1526 p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5]; 1527 1528 return [[curve[0], p0, p00, p000], [p000, p22, p2, curve[3]]]; 1529 }, 1530 1531 /** 1532 * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment 1533 * from its control points. 1534 * @param {Array} curve Array of four coordinate arrays of length 2 defining a 1535 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1536 * @returns {Array} Bounding box [minX, maxY, maxX, minY] 1537 */ 1538 _bezierBbox: function (curve) { 1539 var bb = []; 1540 1541 if (curve.length === 4) { // bezierDegree == 3 1542 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX 1543 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY 1544 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX 1545 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY 1546 } else { // bezierDegree == 1 1547 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX 1548 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY 1549 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX 1550 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY 1551 } 1552 1553 return bb; 1554 }, 1555 1556 /** 1557 * Decide if two Bezier curve segments overlap by comparing their bounding boxes. 1558 * @param {Array} bb1 Bounding box of the first Bezier curve segment 1559 * @param {Array} bb2 Bounding box of the second Bezier curve segment 1560 * @returns {Boolean} true if the bounding boxes overlap, false otherwise. 1561 */ 1562 _bezierOverlap: function (bb1, bb2) { 1563 return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1]; 1564 }, 1565 1566 /** 1567 * Append list of intersection points to a list. 1568 * @private 1569 */ 1570 _bezierListConcat: function (L, Lnew, t1, t2) { 1571 var i, 1572 t2exists = Type.exists(t2), 1573 start = 0, 1574 len = Lnew.length, 1575 le = L.length; 1576 1577 if (le > 0 && 1578 ((L[le - 1][1] === 1 && Lnew[0][1] === 0) || 1579 (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0))) { 1580 start = 1; 1581 } 1582 1583 for (i = start; i < len; i++) { 1584 if (t2exists) { 1585 Lnew[i][2] *= 0.5; 1586 Lnew[i][2] += t2; 1587 } 1588 1589 Lnew[i][1] *= 0.5; 1590 Lnew[i][1] += t1; 1591 1592 L.push(Lnew[i]); 1593 } 1594 }, 1595 1596 /** 1597 * Find intersections of two Bezier curve segments by recursive subdivision. 1598 * Below maxlevel determine intersections by intersection line segments. 1599 * @param {Array} red Array of four coordinate arrays of length 2 defining the first 1600 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1601 * @param {Array} blue Array of four coordinate arrays of length 2 defining the second 1602 * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]]. 1603 * @param {Number} level Recursion level 1604 * @returns {Array} List of intersection points (up to nine). Each intersction point is an 1605 * array of length three (homogeneous coordinates) plus preimages. 1606 */ 1607 _bezierMeetSubdivision: function (red, blue, level) { 1608 var bbb, bbr, 1609 ar, b0, b1, r0, r1, m, 1610 p0, p1, q0, q1, 1611 L = [], 1612 maxLev = 5; // Maximum recursion level 1613 1614 bbr = this._bezierBbox(blue); 1615 bbb = this._bezierBbox(red); 1616 1617 if (!this._bezierOverlap(bbr, bbb)) { 1618 return []; 1619 } 1620 1621 if (level < maxLev) { 1622 ar = this._bezierSplit(red); 1623 r0 = ar[0]; 1624 r1 = ar[1]; 1625 1626 ar = this._bezierSplit(blue); 1627 b0 = ar[0]; 1628 b1 = ar[1]; 1629 1630 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b0, level + 1), 0.0, 0.0); 1631 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b1, level + 1), 0, 0.5); 1632 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b0, level + 1), 0.5, 0.0); 1633 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b1, level + 1), 0.5, 0.5); 1634 1635 return L; 1636 } 1637 1638 // Make homogeneous coordinates 1639 q0 = [1].concat(red[0]); 1640 q1 = [1].concat(red[3]); 1641 p0 = [1].concat(blue[0]); 1642 p1 = [1].concat(blue[3]); 1643 1644 m = this.meetSegmentSegment(q0, q1, p0, p1); 1645 1646 if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) { 1647 return [m]; 1648 } 1649 1650 return []; 1651 }, 1652 1653 /** 1654 * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 1655 */ 1656 _bezierLineMeetSubdivision: function (red, blue, level, testSegment) { 1657 var bbb, bbr, 1658 ar, r0, r1, m, 1659 p0, p1, q0, q1, 1660 L = [], 1661 maxLev = 5; // Maximum recursion level 1662 1663 bbb = this._bezierBbox(blue); 1664 bbr = this._bezierBbox(red); 1665 1666 if (testSegment && !this._bezierOverlap(bbr, bbb)) { 1667 return []; 1668 } 1669 1670 if (level < maxLev) { 1671 ar = this._bezierSplit(red); 1672 r0 = ar[0]; 1673 r1 = ar[1]; 1674 1675 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r0, blue, level + 1), 0.0); 1676 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r1, blue, level + 1), 0.5); 1677 1678 return L; 1679 } 1680 1681 // Make homogeneous coordinates 1682 q0 = [1].concat(red[0]); 1683 q1 = [1].concat(red[3]); 1684 p0 = [1].concat(blue[0]); 1685 p1 = [1].concat(blue[1]); 1686 1687 m = this.meetSegmentSegment(q0, q1, p0, p1); 1688 1689 if (m[1] >= 0.0 && m[1] <= 1.0) { 1690 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) { 1691 return [m]; 1692 } 1693 } 1694 1695 return []; 1696 }, 1697 1698 /** 1699 * Find the nr-th intersection point of two Bezier curve 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 {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment 1705 * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus 1706 * preimages [x,y], t_1, t_2] of the two Bezier curve segments. 1707 * 1708 */ 1709 meetBeziersegmentBeziersegment: function (red, blue, testSegment) { 1710 var L, n, L2, i; 1711 1712 if (red.length === 4 && blue.length === 4) { 1713 L = this._bezierMeetSubdivision(red, blue, 0); 1714 } else { 1715 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment); 1716 } 1717 1718 L.sort(function (a, b) { 1719 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]); 1720 }); 1721 1722 L2 = []; 1723 for (i = 0; i < L.length; i++) { 1724 // Only push entries different from their predecessor 1725 if (i === 0 || (L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2])) { 1726 L2.push(L[i]); 1727 } 1728 } 1729 return L2; 1730 }, 1731 1732 /** 1733 * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3. 1734 * @param {JXG.Curve} red Curve with bezierDegree == 3 1735 * @param {JXG.Curve} blue Curve with bezierDegree == 3 1736 * @param {Number} nr The number of the intersection point which should be returned. 1737 * @returns {Array} The homogeneous coordinates of the nr-th intersection point. 1738 */ 1739 meetBezierCurveRedBlueSegments: function (red, blue, nr) { 1740 var p, i, j, 1741 redArr, blueArr, 1742 bbr, bbb, 1743 lenBlue = blue.points.length, 1744 lenRed = red.points.length, 1745 L = []; 1746 1747 if (lenBlue < 4 || lenRed < 4) { 1748 return [0, NaN, NaN]; 1749 } 1750 1751 for (i = 0; i < lenRed - 3; i += 3) { 1752 p = red.points; 1753 redArr = [ 1754 [p[i].usrCoords[1], p[i].usrCoords[2]], 1755 [p[i + 1].usrCoords[1], p[i + 1].usrCoords[2]], 1756 [p[i + 2].usrCoords[1], p[i + 2].usrCoords[2]], 1757 [p[i + 3].usrCoords[1], p[i + 3].usrCoords[2]] 1758 ]; 1759 1760 bbr = this._bezierBbox(redArr); 1761 1762 for (j = 0; j < lenBlue - 3; j += 3) { 1763 p = blue.points; 1764 blueArr = [ 1765 [p[j].usrCoords[1], p[j].usrCoords[2]], 1766 [p[j + 1].usrCoords[1], p[j + 1].usrCoords[2]], 1767 [p[j + 2].usrCoords[1], p[j + 2].usrCoords[2]], 1768 [p[j + 3].usrCoords[1], p[j + 3].usrCoords[2]] 1769 ]; 1770 1771 bbb = this._bezierBbox(blueArr); 1772 if (this._bezierOverlap(bbr, bbb)) { 1773 L = L.concat(this.meetBeziersegmentBeziersegment(redArr, blueArr)); 1774 if (L.length > nr) { 1775 return L[nr][0]; 1776 } 1777 } 1778 } 1779 } 1780 if (L.length > nr) { 1781 return L[nr][0]; 1782 } 1783 1784 return [0, NaN, NaN]; 1785 }, 1786 1787 bezierSegmentEval: function (t, curve) { 1788 var f, x, y, 1789 t1 = 1.0 - t; 1790 1791 x = 0; 1792 y = 0; 1793 1794 f = t1 * t1 * t1; 1795 x += f * curve[0][0]; 1796 y += f * curve[0][1]; 1797 1798 f = 3.0 * t * t1 * t1; 1799 x += f * curve[1][0]; 1800 y += f * curve[1][1]; 1801 1802 f = 3.0 * t * t * t1; 1803 x += f * curve[2][0]; 1804 y += f * curve[2][1]; 1805 1806 f = t * t * t; 1807 x += f * curve[3][0]; 1808 y += f * curve[3][1]; 1809 1810 return [1.0, x, y]; 1811 }, 1812 1813 /** 1814 * Generate the defining points of a 3rd degree bezier curve that approximates 1815 * a cricle sector defined by three arrays A, B,C, each of length three. 1816 * The coordinate arrays are given in homogeneous coordinates. 1817 * @param {Array} A First point 1818 * @param {Array} B Second point (intersection point) 1819 * @param {Array} C Third point 1820 * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve. 1821 * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1. 1822 */ 1823 bezierArc: function (A, B, C, withLegs, sgn) { 1824 var p1, p2, p3, p4, 1825 r, phi, beta, 1826 PI2 = Math.PI * 0.5, 1827 x = B[1], 1828 y = B[2], 1829 z = B[0], 1830 dataX = [], dataY = [], 1831 co, si, ax, ay, bx, by, k, v, d, matrix; 1832 1833 r = this.distance(B, A); 1834 1835 // x,y, z is intersection point. Normalize it. 1836 x /= z; 1837 y /= z; 1838 1839 phi = this.rad(A.slice(1), B.slice(1), C.slice(1)); 1840 if (sgn === -1) { 1841 phi = 2 * Math.PI - phi; 1842 } 1843 1844 p1 = A; 1845 p1[1] /= p1[0]; 1846 p1[2] /= p1[0]; 1847 p1[0] /= p1[0]; 1848 1849 p4 = p1.slice(0); 1850 1851 if (withLegs) { 1852 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]]; 1853 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]]; 1854 } else { 1855 dataX = [p1[1]]; 1856 dataY = [p1[2]]; 1857 } 1858 1859 while (phi > Mat.eps) { 1860 if (phi > PI2) { 1861 beta = PI2; 1862 phi -= PI2; 1863 } else { 1864 beta = phi; 1865 phi = 0; 1866 } 1867 1868 co = Math.cos(sgn * beta); 1869 si = Math.sin(sgn * beta); 1870 1871 matrix = [ 1872 [1, 0, 0], 1873 [x * (1 - co) + y * si, co, -si], 1874 [y * (1 - co) - x * si, si, co] 1875 ]; 1876 v = Mat.matVecMult(matrix, p1); 1877 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]]; 1878 1879 ax = p1[1] - x; 1880 ay = p1[2] - y; 1881 bx = p4[1] - x; 1882 by = p4[2] - y; 1883 1884 d = Math.sqrt((ax + bx) * (ax + bx) + (ay + by) * (ay + by)); 1885 1886 if (Math.abs(by - ay) > Mat.eps) { 1887 k = (ax + bx) * (r / d - 0.5) / (by - ay) * 8 / 3; 1888 } else { 1889 k = (ay + by) * (r / d - 0.5) / (ax - bx) * 8 / 3; 1890 } 1891 1892 p2 = [1, p1[1] - k * ay, p1[2] + k * ax]; 1893 p3 = [1, p4[1] + k * by, p4[2] - k * bx]; 1894 1895 dataX = dataX.concat([p2[1], p3[1], p4[1]]); 1896 dataY = dataY.concat([p2[2], p3[2], p4[2]]); 1897 p1 = p4.slice(0); 1898 } 1899 1900 if (withLegs) { 1901 dataX = dataX.concat([ p4[1] + 0.333 * (x - p4[1]), p4[1] + 0.666 * (x - p4[1]), x]); 1902 dataY = dataY.concat([ p4[2] + 0.333 * (y - p4[2]), p4[2] + 0.666 * (y - p4[2]), y]); 1903 } 1904 1905 return [dataX, dataY]; 1906 }, 1907 1908 /****************************************/ 1909 /**** PROJECTIONS ****/ 1910 /****************************************/ 1911 1912 /** 1913 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 1914 * nearest one of the two intersection points of the line through the given point and the circles 1915 * center. 1916 * @param {JXG.Point,JXG.Coords} point Point to project or coords object to project. 1917 * @param {JXG.Circle} circle Circle on that the point is projected. 1918 * @param {JXG.Board} [board=point.board] Reference to the board 1919 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 1920 */ 1921 projectPointToCircle: function (point, circle, board) { 1922 var dist, P, x, y, factor, 1923 M = circle.center.coords.usrCoords; 1924 1925 if (!Type.exists(board)) { 1926 board = point.board; 1927 } 1928 1929 // gave us a point 1930 if (Type.isPoint(point)) { 1931 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords); 1932 P = point.coords.usrCoords; 1933 // gave us coords 1934 } else { 1935 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords); 1936 P = point.usrCoords; 1937 } 1938 1939 if (Math.abs(dist) < Mat.eps) { 1940 dist = Mat.eps; 1941 } 1942 1943 factor = circle.Radius() / dist; 1944 x = M[1] + factor * (P[1] - M[1]); 1945 y = M[2] + factor * (P[2] - M[2]); 1946 1947 return new Coords(Const.COORDS_BY_USER, [x, y], board); 1948 }, 1949 1950 /** 1951 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 1952 * intersection point of the given line and its perpendicular through the given point. 1953 * @param {JXG.Point} point Point to project. 1954 * @param {JXG.Line} line Line on that the point is projected. 1955 * @param {JXG.Board} [board=point.board] Reference to a board. 1956 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 1957 */ 1958 projectPointToLine: function (point, line, board) { 1959 // Homogeneous version 1960 var v = [0, line.stdform[1], line.stdform[2]]; 1961 1962 if (!Type.exists(board)) { 1963 board = point.board; 1964 } 1965 1966 v = Mat.crossProduct(v, point.coords.usrCoords); 1967 1968 return this.meetLineLine(v, line.stdform, 0, board); 1969 }, 1970 1971 /** 1972 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 1973 * segment defined by two coordinate arrays. 1974 * @param {Array} p Point to project. 1975 * @param {Array} q1 Start point of the line segment on that the point is projected. 1976 * @param {Array} q2 End point of the line segment on that the point is projected. 1977 * @returns {Array} The coordinates of the projection of the given point on the given segment 1978 * and the factor that determines the projected point as a convex combination of the 1979 * two endpoints q1 and q2 of the segment. 1980 */ 1981 projectCoordsToSegment: function (p, q1, q2) { 1982 var t, denom, c, 1983 s = [q2[1] - q1[1], q2[2] - q1[2]], 1984 v = [p[1] - q1[1], p[2] - q1[2]]; 1985 1986 /** 1987 * If the segment has length 0, i.e. is a point, 1988 * the projection is equal to that point. 1989 */ 1990 if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) { 1991 return [q1, 0]; 1992 } 1993 1994 t = Mat.innerProduct(v, s); 1995 denom = Mat.innerProduct(s, s); 1996 t /= denom; 1997 1998 return [ [1, t * s[0] + q1[1], t * s[1] + q1[2]], t]; 1999 }, 2000 2001 /** 2002 * Finds the coordinates of the closest point on a Bezier segment of a 2003 * {@link JXG.Curve} to a given coordinate array. 2004 * @param {Array} pos Point to project in homogeneous coordinates. 2005 * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3. 2006 * @param {Number} start Number of the Bezier segment of the curve. 2007 * @returns {Array} The coordinates of the projection of the given point 2008 * on the given Bezier segment and the preimage of the curve which 2009 * determines the closest point. 2010 */ 2011 projectCoordsToBeziersegment: function (pos, curve, start) { 2012 var t0, 2013 minfunc = function (t) { 2014 var z = [1, curve.X(start + t), curve.Y(start + t)]; 2015 2016 z[1] -= pos[1]; 2017 z[2] -= pos[2]; 2018 2019 return z[1] * z[1] + z[2] * z[2]; 2020 }; 2021 2022 t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]); 2023 2024 return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0]; 2025 }, 2026 2027 /** 2028 * Calculates the coordinates of the projection of a given point on a given curve. 2029 * Uses {@link #projectCoordsToCurve}. 2030 * @param {JXG.Point} point Point to project. 2031 * @param {JXG.Curve} curve Curve on that the point is projected. 2032 * @param {JXG.Board} [board=point.board] Reference to a board. 2033 * @see #projectCoordsToCurve 2034 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph. 2035 */ 2036 projectPointToCurve: function (point, curve, board) { 2037 if (!Type.exists(board)) { 2038 board = point.board; 2039 } 2040 2041 var x = point.X(), 2042 y = point.Y(), 2043 t = point.position || 0.0, 2044 result = this.projectCoordsToCurve(x, y, t, curve, board); 2045 2046 point.position = result[1]; 2047 2048 return result[0]; 2049 }, 2050 2051 /** 2052 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 2053 * function graphs this is the 2054 * intersection point of the curve and the parallel to y-axis through the given point. 2055 * @param {Number} x coordinate to project. 2056 * @param {Number} y coordinate to project. 2057 * @param {Number} t start value for newtons method 2058 * @param {JXG.Curve} curve Curve on that the point is projected. 2059 * @param {JXG.Board} [board=curve.board] Reference to a board. 2060 * @see #projectPointToCurve 2061 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and 2062 * the position on the curve. 2063 */ 2064 projectCoordsToCurve: function (x, y, t, curve, board) { 2065 var newCoords, newCoordsObj, i, j, 2066 x0, y0, x1, y1, mindist, dist, lbda, li, v, coords, d, 2067 p1, p2, q1, q2, res, 2068 minfunc, tnew, fnew, fold, delta, steps, 2069 infty = Number.POSITIVE_INFINITY; 2070 2071 if (!Type.exists(board)) { 2072 board = curve.board; 2073 } 2074 2075 if (curve.visProp.curvetype === 'plot') { 2076 t = 0; 2077 mindist = infty; 2078 2079 if (curve.numberPoints === 0) { 2080 newCoords = [0, 1, 1]; 2081 } else { 2082 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 2083 } 2084 2085 if (curve.numberPoints > 1) { 2086 2087 v = [1, x, y]; 2088 if (curve.bezierDegree === 3) { 2089 j = 0; 2090 } else { 2091 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 2092 } 2093 for (i = 0; i < curve.numberPoints - 1; i++) { 2094 if (curve.bezierDegree === 3) { 2095 res = this.projectCoordsToBeziersegment(v, curve, j); 2096 } else { 2097 p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)]; 2098 res = this.projectCoordsToSegment(v, p1, p2); 2099 } 2100 lbda = res[1]; 2101 coords = res[0]; 2102 2103 if (0.0 <= lbda && lbda <= 1.0) { 2104 dist = this.distance(coords, v); 2105 d = i + lbda; 2106 } else if (lbda < 0.0) { 2107 coords = p1; 2108 dist = this.distance(p1, v); 2109 d = i; 2110 } else if (lbda > 1.0 && i === curve.numberPoints - 2) { 2111 coords = p2; 2112 dist = this.distance(coords, v); 2113 d = curve.numberPoints - 1; 2114 } 2115 2116 if (dist < mindist) { 2117 mindist = dist; 2118 t = d; 2119 newCoords = coords; 2120 } 2121 2122 if (curve.bezierDegree === 3) { 2123 j++; 2124 i += 2; 2125 } else { 2126 p1 = p2; 2127 } 2128 } 2129 } 2130 2131 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board); 2132 } else { // 'parameter', 'polar', 'functiongraph' 2133 2134 // Function to minimize 2135 minfunc = function (t) { 2136 var dx = x - curve.X(t), 2137 dy = y - curve.Y(t); 2138 return dx * dx + dy * dy; 2139 }; 2140 2141 fold = minfunc(t); 2142 steps = 50; 2143 delta = (curve.maxX() - curve.minX()) / steps; 2144 tnew = curve.minX(); 2145 2146 for (i = 0; i < steps; i++) { 2147 fnew = minfunc(tnew); 2148 2149 if (fnew < fold) { 2150 t = tnew; 2151 fold = fnew; 2152 } 2153 2154 tnew += delta; 2155 } 2156 2157 //t = Numerics.root(Numerics.D(minfunc), t); 2158 t = Numerics.fminbr(minfunc, [t - delta, t + delta]); 2159 2160 if (t < curve.minX()) { 2161 t = curve.maxX() + t - curve.minX(); 2162 } 2163 2164 // Cyclically 2165 if (t > curve.maxX()) { 2166 t = curve.minX() + t - curve.maxX(); 2167 } 2168 2169 newCoordsObj = new Coords(Const.COORDS_BY_USER, [curve.X(t), curve.Y(t)], board); 2170 } 2171 2172 return [curve.updateTransform(newCoordsObj), t]; 2173 }, 2174 2175 /** 2176 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 2177 * one or more curves of curveType 'plot'. Uses {@link #projectPointToCurve}. 2178 * @param {JXG.Point} point Point to project. 2179 * @param {JXG.Turtle} turtle on that the point is projected. 2180 * @param {JXG.Board} [board=point.board] Reference to a board. 2181 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle. 2182 */ 2183 projectPointToTurtle: function (point, turtle, board) { 2184 var newCoords, t, x, y, i, dist, el, minEl, 2185 np = 0, 2186 npmin = 0, 2187 mindist = Number.POSITIVE_INFINITY, 2188 len = turtle.objects.length; 2189 2190 if (!Type.exists(board)) { 2191 board = point.board; 2192 } 2193 2194 // run through all curves of this turtle 2195 for (i = 0; i < len; i++) { 2196 el = turtle.objects[i]; 2197 2198 if (el.elementClass === Const.OBJECT_CLASS_CURVE) { 2199 newCoords = this.projectPointToCurve(point, el); 2200 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 2201 2202 if (dist < mindist) { 2203 x = newCoords.usrCoords[1]; 2204 y = newCoords.usrCoords[2]; 2205 t = point.position; 2206 mindist = dist; 2207 minEl = el; 2208 npmin = np; 2209 } 2210 np += el.numberPoints; 2211 } 2212 } 2213 2214 newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board); 2215 point.position = t + npmin; 2216 2217 return minEl.updateTransform(newCoords); 2218 }, 2219 2220 /** 2221 * Trivial projection of a point to another point. 2222 * @param {JXG.Point} point Point to project (not used). 2223 * @param {JXG.Point} dest Point on that the point is projected. 2224 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 2225 */ 2226 projectPointToPoint: function (point, dest) { 2227 return dest.coords; 2228 }, 2229 2230 /** 2231 * 2232 * @param {JXG.Point|JXG.Coords} point 2233 * @param {JXG.Board} [board] 2234 */ 2235 projectPointToBoard: function (point, board) { 2236 var i, l, c, 2237 brd = board || point.board, 2238 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx 2239 config = [ 2240 // left 2241 [1, 1, 0, 0, 3, 0, 1], 2242 // top 2243 [-1, 2, 1, 0, 1, 2, 1], 2244 // right 2245 [-1, 1, 2, 2, 1, 2, 3], 2246 // bottom 2247 [1, 2, 3, 0, 3, 2, 3] 2248 ], 2249 coords = point.coords || point, 2250 bbox = brd.getBoundingBox(); 2251 2252 for (i = 0; i < 4; i++) { 2253 c = config[i]; 2254 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) { 2255 // define border 2256 l = Mat.crossProduct([1, bbox[c[3]], bbox[c[4]]], [1, bbox[c[5]], bbox[c[6]]]); 2257 l[3] = 0; 2258 l = Mat.normalize(l); 2259 2260 // project point 2261 coords = this.projectPointToLine({coords: coords, board: brd}, {stdform: l}); 2262 } 2263 } 2264 2265 return coords; 2266 }, 2267 2268 /** 2269 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 2270 * coordinates. For lines this can be line.stdform. 2271 * @param {Array} point Homogeneous coordinates of a point. 2272 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 2273 * @returns {Number} Distance of the point to the line. 2274 */ 2275 distPointLine: function (point, line) { 2276 var a = line[1], 2277 b = line[2], 2278 c = line[0], 2279 nom; 2280 2281 if (Math.abs(a) + Math.abs(b) < Mat.eps) { 2282 return Number.POSITIVE_INFINITY; 2283 } 2284 2285 nom = a * point[1] + b * point[2] + c; 2286 a *= a; 2287 b *= b; 2288 2289 return Math.abs(nom) / Math.sqrt(a + b); 2290 }, 2291 2292 2293 /** 2294 * Helper function to create curve which displays a Reuleaux polygons. 2295 * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically, 2296 * these point list is the array vrtices of a regular polygon. 2297 * @param {Number} nr Number of vertices 2298 * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values 2299 * for the start and the end of the paramtric curve. array may be used as parent array of a {@link JXG.Curve}. 2300 * @example 2301 * var A = brd.create('point',[-2,-2]); 2302 * var B = brd.create('point',[0,1]); 2303 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2304 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2305 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2306 * 2307 * </pre><div id="2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div> 2308 * <script type="text/javascript"> 2309 * var brd = JXG.JSXGraph.initBoard('2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false}); 2310 * var A = brd.create('point',[-2,-2]); 2311 * var B = brd.create('point',[0,1]); 2312 * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0}); 2313 * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3), 2314 * {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'}); 2315 * </script><pre> 2316 */ 2317 reuleauxPolygon: function (points, nr) { 2318 var beta, 2319 pi2 = Math.PI * 2, 2320 pi2_n = pi2 / nr, 2321 diag = (nr - 1) / 2, 2322 d = 0, 2323 makeFct = function (which, trig) { 2324 return function (t, suspendUpdate) { 2325 var t1 = (t % pi2 + pi2) % pi2, 2326 j = Math.floor(t1 / pi2_n) % nr; 2327 2328 if (!suspendUpdate) { 2329 d = points[0].Dist(points[diag]); 2330 beta = Mat.Geometry.rad([points[0].X() + 1, points[0].Y()], points[0], points[diag % nr]); 2331 } 2332 2333 if (isNaN(j)) { 2334 return j; 2335 } 2336 2337 t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta; 2338 2339 return points[j][which]() + d * Math[trig](t1); 2340 }; 2341 }; 2342 2343 return [makeFct('X', 'cos'), makeFct('Y', 'sin'), 0, pi2]; 2344 } 2345 }); 2346 2347 return Mat.Geometry; 2348 }); 2349