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