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