1 /* 2 Copyright 2008,2009 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: you can redistribute it and/or modify 13 it under the terms of the GNU Lesser General Public License as published by 14 the Free Software Foundation, either version 3 of the License, or 15 (at your option) any later version. 16 17 JSXGraph is distributed in the hope that it will be useful, 18 but WITHOUT ANY WARRANTY; without even the implied warranty of 19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 20 GNU Lesser General Public License for more details. 21 22 You should have received a copy of the GNU Lesser General Public License 23 along with JSXGraph. If not, see <http://www.gnu.org/licenses/>. 24 */ 25 26 /** 27 * @fileoverview This file contains the Math.Geometry namespace for calculating algebraic/geometric 28 * stuff like intersection points, angles, midpoint, and so on. 29 */ 30 31 32 /** 33 * Math.Geometry namespace definition 34 * @namespace 35 */ 36 JXG.Math.Geometry = {}; 37 38 // the splitting is necessary due to the shortcut for the circumcircleMidpoint method to circumcenter. 39 40 JXG.extend(JXG.Math.Geometry, /** @lends JXG.Math.Geometry */ { 41 42 /****************************************/ 43 /**** GENERAL GEOMETRIC CALCULATIONS ****/ 44 /****************************************/ 45 46 /** 47 * Calculates the angle defined by the points A, B, C. 48 * @param {JXG.Point} A A point or [x,y] array. 49 * @param {JXG.Point} B Another point or [x,y] array. 50 * @param {JXG.Point} C A circle - no, of course the third point or [x,y] array. 51 * @deprecated Use {@link JXG.Math.Geometry#rad} instead. 52 * @see #rad 53 * @see #trueAngle 54 * @returns {Number} The angle in radian measure. 55 */ 56 angle: function(A, B, C) { 57 var a = [], 58 b = [], 59 c = [], 60 u, v, s, t; 61 62 if (A.coords == null) { 63 a[0] = A[0]; 64 a[1] = A[1]; 65 } else { 66 a[0] = A.coords.usrCoords[1]; 67 a[1] = A.coords.usrCoords[2]; 68 } 69 if (B.coords == null) { 70 b[0] = B[0]; 71 b[1] = B[1]; 72 } else { 73 b[0] = B.coords.usrCoords[1]; 74 b[1] = B.coords.usrCoords[2]; 75 } 76 if (C.coords == null) { 77 c[0] = C[0]; 78 c[1] = C[1]; 79 } else { 80 c[0] = C.coords.usrCoords[1]; 81 c[1] = C.coords.usrCoords[2]; 82 } 83 u = a[0] - b[0]; 84 v = a[1] - b[1]; 85 s = c[0] - b[0]; 86 t = c[1] - b[1]; 87 return Math.atan2(u * t - v * s, u * s + v * t); 88 }, 89 90 /** 91 * Calculates the angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 92 * @param {JXG.Point} A Point or [x,y] array 93 * @param {JXG.Point} B Point or [x,y] array 94 * @param {JXG.Point} C Point or [x,y] array 95 * @see #rad 96 * @returns {Number} The angle in degrees. 97 */ 98 trueAngle: function(A, B, C) { 99 return this.rad(A, B, C) * 57.295779513082323; // *180.0/Math.PI; 100 }, 101 102 /** 103 * Calculates the internal angle defined by the three points A, B, C if you're going from A to C around B counterclockwise. 104 * @param {JXG.Point} A Point or [x,y] array 105 * @param {JXG.Point} B Point or [x,y] array 106 * @param {JXG.Point} C Point or [x,y] array 107 * @see #trueAngle 108 * @returns {Number} Angle in radians. 109 */ 110 rad: function(A, B, C) { 111 var ax, ay, bx, by, cx, cy, 112 phi; 113 114 if (A.coords == null) { 115 ax = A[0]; 116 ay = A[1]; 117 } else { 118 ax = A.coords.usrCoords[1]; 119 ay = A.coords.usrCoords[2]; 120 } 121 if (B.coords == null) { 122 bx = B[0]; 123 by = B[1]; 124 } else { 125 bx = B.coords.usrCoords[1]; 126 by = B.coords.usrCoords[2]; 127 } 128 if (C.coords == null) { 129 cx = C[0]; 130 cy = C[1]; 131 } else { 132 cx = C.coords.usrCoords[1]; 133 cy = C.coords.usrCoords[2]; 134 } 135 136 phi = Math.atan2(cy - by, cx - bx) - Math.atan2(ay - by, ax - bx); 137 if (phi < 0) phi += 6.2831853071795862; 138 return phi; 139 }, 140 141 /** 142 * Calculates the bisection between the three points A, B, C. The bisection is defined by two points: 143 * Parameter B and a point with the coordinates calculated in this function. 144 * @param {JXG.Point} A Point 145 * @param {JXG.Point} B Point 146 * @param {JXG.Point} C Point 147 * @param [board=A.board] Reference to the board 148 * @returns {JXG.Coords} Coordinates of the second point defining the bisection. 149 */ 150 angleBisector: function(A, B, C, board) { 151 /* First point */ 152 var Ac = A.coords.usrCoords, 153 Bc = B.coords.usrCoords, 154 Cc = C.coords.usrCoords, 155 x = Ac[1] - Bc[1], 156 y = Ac[2] - Bc[2], 157 d = Math.sqrt(x * x + y * y), 158 phiA, phiC, phi; 159 160 if (!JXG.exists(board)) 161 board = A.board; 162 163 x /= d; 164 y /= d; 165 166 phiA = Math.acos(x); 167 if (y < 0) { 168 phiA *= -1; 169 } 170 if (phiA < 0) { 171 phiA += 2 * Math.PI; 172 } 173 174 /* Second point */ 175 x = Cc[1] - Bc[1]; 176 y = Cc[2] - Bc[2]; 177 d = Math.sqrt(x * x + y * y); 178 x /= d; 179 y /= d; 180 181 phiC = Math.acos(x); 182 if (y < 0) { 183 phiC *= -1; 184 } 185 if (phiC < 0) { 186 phiC += 2 * Math.PI; 187 } 188 189 phi = (phiA + phiC) * 0.5; 190 if (phiA > phiC) { 191 phi += Math.PI; 192 } 193 194 x = Math.cos(phi) + Bc[1]; 195 y = Math.sin(phi) + Bc[2]; 196 197 return new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board); 198 }, 199 200 /** 201 * Reflects the point along the line. 202 * @param {JXG.Line} line Axis of reflection. 203 * @param {JXG.Point} point Point to reflect. 204 * @param [board=point.board] Reference to the board 205 * @returns {JXG.Coords} Coordinates of the reflected point. 206 */ 207 reflection: function(line, point, board) { 208 // (v,w) defines the slope of the line 209 var pc = point.coords.usrCoords, 210 p1c = line.point1.coords.usrCoords, 211 p2c = line.point2.coords.usrCoords, 212 x0, y0, x1, y1, v, w, mu; 213 214 if (!JXG.exists(board)) 215 board = point.board; 216 217 v = p2c[1] - p1c[1]; 218 w = p2c[2] - p1c[2]; 219 220 x0 = pc[1] - p1c[1]; 221 y0 = pc[2] - p1c[2]; 222 223 mu = (v * y0 - w * x0) / (v * v + w * w); 224 225 // point + mu*(-y,x) waere Lotpunkt 226 x1 = pc[1] + 2 * mu * w; 227 y1 = pc[2] - 2 * mu * v; 228 229 return new JXG.Coords(JXG.COORDS_BY_USER, [x1,y1], board); 230 }, 231 232 /** 233 * Computes the new position of a point which is rotated 234 * around a second point (called rotpoint) by the angle phi. 235 * @param {JXG.Point} rotpoint Center of the rotation 236 * @param {JXG.Point} point point to be rotated 237 * @param {number} phi rotation angle in arc length 238 * @param {JXG.Board} [board=point.board] Reference to the board 239 * @returns {JXG.Coords} Coordinates of the new position. 240 */ 241 rotation: function(rotpoint, point, phi, board) { 242 var pc = point.coords.usrCoords, 243 rotpc = rotpoint.coords.usrCoords, 244 x0, y0, c, s, x1, y1; 245 246 if (!JXG.exists(board)) 247 board = point.board; 248 249 x0 = pc[1] - rotpc[1]; 250 y0 = pc[2] - rotpc[2]; 251 252 c = Math.cos(phi); 253 s = Math.sin(phi); 254 255 x1 = x0 * c - y0 * s + rotpc[1]; 256 y1 = x0 * s + y0 * c + rotpc[2]; 257 258 return new JXG.Coords(JXG.COORDS_BY_USER, [x1,y1], board); 259 }, 260 261 /** 262 * Calculates the coordinates of a point on the perpendicular to the given line through 263 * the given point. 264 * @param {JXG.Line} line A line. 265 * @param {JXG.Point} point Intersection point of line to perpendicular. 266 * @param {JXG.Board} [board=point.board] Reference to the board 267 * @returns {JXG.Coords} Coordinates of a point on the perpendicular to the given line through the given point. 268 */ 269 perpendicular: function(line, point, board) { 270 var A = line.point1.coords.usrCoords, 271 B = line.point2.coords.usrCoords, 272 C = point.coords.usrCoords, 273 x, y, change, 274 fmd, emc, d0, d1, den; 275 276 if (!JXG.exists(board)) 277 board = point.board; 278 279 if (point == line.point1) { // Punkt ist erster Punkt der Linie 280 x = A[1] + B[2] - A[2]; 281 y = A[2] - B[1] + A[1]; 282 change = true; 283 } else if (point == line.point2) { // Punkt ist zweiter Punkt der Linie 284 x = B[1] + A[2] - B[2]; 285 y = B[2] - A[1] + B[1]; 286 change = false; 287 } else if (((Math.abs(A[1] - B[1]) > JXG.Math.eps) && 288 (Math.abs(C[2] - (A[2] - B[2]) * (C[1] - A[1]) / (A[1] - B[1]) - A[2]) < JXG.Math.eps)) || 289 ((Math.abs(A[1] - B[1]) <= JXG.Math.eps) && (Math.abs(A[1] - C[1]) < JXG.Math.eps))) { // Punkt liegt auf der Linie 290 x = C[1] + B[2] - C[2]; 291 y = C[2] - B[1] + C[1]; 292 change = true; 293 if (Math.abs(x - C[1]) < JXG.Math.eps && Math.abs(y - C[2]) < JXG.Math.eps) { 294 x = C[1] + A[2] - C[2]; 295 y = C[2] - A[1] + C[1]; 296 change = false; 297 } 298 } else { // Punkt liegt nicht auf der Linie -> als zweiter Punkt wird der Lotfusspunkt gewaehlt 299 fmd = A[2] - B[2]; 300 emc = A[1] - B[1]; 301 d0 = B[1] * fmd - B[2] * emc; 302 d1 = C[1] * emc + C[2] * fmd; 303 den = fmd * fmd + emc * emc; 304 if (Math.abs(den) < JXG.Math.eps) { 305 den = JXG.Math.eps; 306 } 307 x = (d0 * fmd + d1 * emc) / den; 308 y = (d1 * fmd - d0 * emc) / den; 309 change = true; 310 } 311 return [new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board),change]; 312 }, 313 314 /** 315 * @deprecated Please use {@link JXG.Math.Geometry#circumcenter} instead. 316 */ 317 circumcenterMidpoint: JXG.shortcut(JXG.Math.Geometry, 'circumcenter'), 318 319 /** 320 * Calculates the center of the circumcircle of the three given points. 321 * @param {JXG.Point} point1 Point 322 * @param {JXG.Point} point2 Point 323 * @param {JXG.Point} point3 Point 324 * @param {JXG.Board} [board=point1.board] Reference to the board 325 * @returns {JXG.Coords} Coordinates of the center of the circumcircle of the given points. 326 */ 327 circumcenter: function(point1, point2, point3, board) { 328 var A = point1.coords.usrCoords, 329 B = point2.coords.usrCoords, 330 C = point3.coords.usrCoords, 331 u, v, m1, m2; 332 //u, v, den, m1, y, eps = JXG.Math.eps; 333 334 if (!JXG.exists(board)) 335 board = point1.board; 336 /* 337 u = ((A[1] - B[1]) * (A[1] + B[1]) + (A[2] - B[2]) * (A[2] + B[2])) * 0.5; 338 v = ((B[1] - C[1]) * (B[1] + C[1]) + (B[2] - C[2]) * (B[2] + C[2])) * 0.5; 339 den = (A[1] - B[1]) * (B[2] - C[2]) - (B[1] - C[1]) * (A[2] - B[2]); 340 341 if (Math.abs(den) < eps) { 342 den = eps; 343 return new JXG.Coords(JXG.COORDS_BY_USER, [Infinity, Infinity], board); 344 } 345 346 x = (u * (B[2] - C[2]) - v * (A[2] - B[2])) / den; 347 y = (v * (A[1] - B[1]) - u * (B[1] - C[1])) / den; 348 349 return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board); 350 */ 351 u = [B[0]-A[0], -B[2]+A[2], B[1]-A[1]]; 352 v = [(A[0]+B[0])*0.5, (A[1]+B[1])*0.5, (A[2]+B[2])*0.5]; 353 m1 = JXG.Math.crossProduct(u, v); 354 u = [C[0]-B[0], -C[2]+B[2], C[1]-B[1]]; 355 v = [(B[0]+C[0])*0.5, (B[1]+C[1])*0.5, (B[2]+C[2])*0.5]; 356 m2 = JXG.Math.crossProduct(u, v); 357 358 return new JXG.Coords(JXG.COORDS_BY_USER, JXG.Math.crossProduct(m1, m2), board); 359 }, 360 361 /** 362 * Calculates euclidean norm for two given arrays of the same length. 363 * @param {Array} array1 Array of float or integer. 364 * @param {Array} array2 Array of float or integer. 365 * @returns {Number} Euclidean distance of the given vectors. 366 */ 367 distance: function(array1, array2) { 368 var sum = 0, 369 i, len; 370 371 if (array1.length != array2.length) { 372 return NaN; 373 } 374 len = array1.length; 375 for (i = 0; i < len; i++) { 376 sum += (array1[i] - array2[i]) * (array1[i] - array2[i]); 377 } 378 return Math.sqrt(sum); 379 }, 380 381 /** 382 * Calculates euclidean distance for two given arrays of the same length. 383 * If one of the arrays contains a zero in the first coordinate, and the euclidean distance 384 * is different from zero it is a point at infinity and we return Infinity. 385 * @param {Array} array1 Array containing elements of number. 386 * @param {Array} array2 Array containing elements of type number. 387 * @returns {Number} Euclidean (affine) distance of the given vectors. 388 */ 389 affineDistance: function(array1, array2) { 390 var d; 391 if (array1.length != array2.length) { 392 return NaN; 393 } 394 d = this.distance(array1, array2); 395 if (d > JXG.Math.eps && (Math.abs(array1[0]) < JXG.Math.eps || Math.abs(array2[0]) < JXG.Math.eps)) { 396 return Infinity; 397 } else { 398 return d; 399 } 400 }, 401 402 /** 403 * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2 404 * calcStraight determines the visual start point and end point of the line. A segment is only drawn 405 * from start to end point, a straight line is drawn until it meets the boards boundaries. 406 * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point. 407 * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and set by this method. 408 * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set by this method. 409 * @param {Number} margin Optional margin, to avoid the display of the small sides 410 * of lines. 411 * @see Line 412 * @see JXG.Line 413 */ 414 calcStraight: function(el, point1, point2, margin) { 415 var takePoint1, takePoint2, intersect1, intersect2, straightFirst, straightLast, 416 c, s, i, j, p1, p2; 417 418 if (margin == null) { 419 margin = 10; // Enlarge the drawable region slightly. This hides the small sides 420 // of thick lines in most cases. 421 } 422 423 straightFirst = el.visProp.straightfirst; 424 straightLast = el.visProp.straightlast; 425 426 // If one of the point is an ideal point in homogeneous coordinates 427 // drawing of line segments or rays are not possible. 428 if (Math.abs(point1.scrCoords[0]) < JXG.Math.eps) { 429 straightFirst = true; 430 } 431 if (Math.abs(point2.scrCoords[0]) < JXG.Math.eps) { 432 straightLast = true; 433 } 434 435 if (!straightFirst && !straightLast) { // Do nothing in case of line segments (inside or outside of the board) 436 return; 437 } 438 439 // Compute the stdform of the line in screen coordinates. 440 c = []; 441 c[0] = el.stdform[0] - 442 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX + 443 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY; 444 c[1] = el.stdform[1] / el.board.unitX; 445 c[2] = el.stdform[2] / (-el.board.unitY); 446 447 if (isNaN(c[0] + c[1] + c[2])) return; // p1=p2 448 449 // Intersect the line with the four borders of the board. 450 s = []; 451 s[0] = JXG.Math.crossProduct(c, [margin,0,1]); // top 452 s[1] = JXG.Math.crossProduct(c, [margin,1,0]); // left 453 s[2] = JXG.Math.crossProduct(c, [-margin-el.board.canvasHeight,0,1]); // bottom 454 s[3] = JXG.Math.crossProduct(c, [-margin-el.board.canvasWidth,1,0]); // right 455 456 // Normalize the intersections 457 for (i = 0; i < 4; i++) { 458 if (Math.abs(s[i][0]) > JXG.Math.eps) { 459 for (j = 2; j > 0; j--) { 460 s[i][j] /= s[i][0]; 461 } 462 s[i][0] = 1.0; 463 } 464 } 465 466 takePoint1 = false; 467 takePoint2 = false; 468 if (!straightFirst && // Line starts at point1 and point1 is inside the board 469 Math.abs(point1.usrCoords[0]) >= JXG.Math.eps && 470 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth && 471 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight) { 472 takePoint1 = true; 473 } 474 if (!straightLast && // Line ends at point2 and point2 is inside the board 475 Math.abs(point2.usrCoords[0]) >= JXG.Math.eps && 476 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth && 477 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight) { 478 takePoint2 = true; 479 } 480 481 if (Math.abs(s[1][0]) < JXG.Math.eps) { // line is parallel to "left", take "top" and "bottom" 482 intersect1 = s[0]; // top 483 intersect2 = s[2]; // bottom 484 } else if (Math.abs(s[0][0]) < JXG.Math.eps) { // line is parallel to "top", take "left" and "right" 485 intersect1 = s[1]; // left 486 intersect2 = s[3]; // right 487 } else if (s[1][2] < 0) { // left intersection out of board (above) 488 intersect1 = s[0]; // top 489 if (s[3][2] > el.board.canvasHeight) { // right intersection out of board (below) 490 intersect2 = s[2]; // bottom 491 } else { 492 intersect2 = s[3]; // right 493 } 494 } else if (s[1][2] > el.board.canvasHeight) { // left intersection out of board (below) 495 intersect1 = s[2]; // bottom 496 if (s[3][2] < 0) { // right intersection out of board (above) 497 intersect2 = s[0]; // top 498 } else { 499 intersect2 = s[3]; // right 500 } 501 } else { 502 intersect1 = s[1]; // left 503 if (s[3][2] < 0) { // right intersection out of board (above) 504 intersect2 = s[0]; // top 505 } else if (s[3][2] > el.board.canvasHeight) { // right intersection out of board (below) 506 intersect2 = s[2]; // bottom 507 } else { 508 intersect2 = s[3]; // right 509 } 510 } 511 512 intersect1 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect1.slice(1), el.board); 513 intersect2 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect2.slice(1), el.board); 514 515 /** 516 * At this point we have four points: 517 * point1 and point2 are the first and the second defining point on the line, 518 * intersect1, intersect2 are the intersections of the line with border around the board. 519 */ 520 521 /* 522 * Here we handle rays where both defining points are outside of the board. 523 */ 524 if (!takePoint1 && !takePoint2) { // If both points are outside and the complete ray is outside we do nothing 525 if (!straightFirst && straightLast && // Ray starting at point 1 526 !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) { 527 return; 528 } else if (straightFirst && !straightLast && // Ray starting at point 2 529 !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) { 530 return; 531 } 532 } 533 534 /* 535 * If at least one of the defining points is outside of the board 536 * we take intersect1 or intersect2 as one of the end points 537 * The order is also important for arrows of axes 538 */ 539 if (!takePoint1) { 540 if (!takePoint2) { 541 /* 542 * Two border intersection points are used 543 */ 544 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 545 p1 = intersect1; 546 p2 = intersect2; 547 } else { 548 p2 = intersect1; 549 p1 = intersect2; 550 } 551 552 /* 553 if (this.isSameDirection(point1, point2, intersect1)) { 554 if (!this.isSameDirection(point1, point2, intersect2)) { 555 p2 = intersect1; 556 p1 = intersect2; 557 } else { 558 if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) <= JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) { 559 p1 = intersect1; 560 p2 = intersect2; 561 } else { 562 p2 = intersect1; 563 p1 = intersect2; 564 } 565 } 566 } else { 567 if (this.isSameDirection(point1, point2, intersect2)) { 568 p1 = intersect1; 569 p2 = intersect2; 570 } else { 571 if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) < JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) { 572 p2 = intersect1; 573 p1 = intersect2; 574 } else { 575 p1 = intersect1; 576 p2 = intersect2; 577 } 578 } 579 } 580 */ 581 } else { 582 /* 583 * One border intersection points is used 584 */ 585 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 586 p1 = intersect1; 587 } else { 588 p1 = intersect2; 589 } 590 /* 591 if (this.isSameDirection(point2, point1, intersect1)) { // Instead of point1 the border intersection is taken 592 p1 = intersect1; 593 } else { 594 p1 = intersect2; 595 } 596 */ 597 } 598 } else { 599 if (!takePoint2) { 600 /* 601 * One border intersection points is used 602 */ 603 if (this.isSameDir(point1, point2, intersect1, intersect2)) { 604 p2 = intersect2; 605 } else { 606 p2 = intersect1; 607 } /* 608 if (this.isSameDirection(point1, point2, intersect1)) { // Instead of point2 the border intersection is taken 609 p2 = intersect1; 610 } else { 611 p2 = intersect2; 612 } 613 */ 614 } 615 } 616 617 if (p1) point1.setCoordinates(JXG.COORDS_BY_USER, p1.usrCoords.slice(1)); 618 if (p2) point2.setCoordinates(JXG.COORDS_BY_USER, p2.usrCoords.slice(1)); 619 }, 620 621 /** 622 * The vectors p2-p1 and i2-i1 are supposed to be collinear. 623 * If their cosine is positive they point into the same direction 624 * otherwise they point in opposite direction 625 * @param {JXG.Coords} p1 626 * @param {JXG.Coords} p2 627 * @param {JXG.Coords} i1 628 * @param {JXG.Coords} i2 629 * @returns {Boolean} True, if p2-p1 and i2-i1 point into the same direction 630 */ 631 isSameDir: function(p1, p2, i1, i2) { 632 var dpx = p2.usrCoords[1] - p1.usrCoords[1], 633 dpy = p2.usrCoords[2] - p1.usrCoords[2], 634 dix = i2.usrCoords[1] - i1.usrCoords[1], 635 diy = i2.usrCoords[2] - i1.usrCoords[2]; 636 637 if (Math.abs(p2.usrCoords[0])<JXG.Math.eps) { 638 dpx = p2.usrCoords[1]; 639 dpy = p2.usrCoords[2]; 640 } 641 if (Math.abs(p1.usrCoords[0])<JXG.Math.eps) { 642 dpx = -p1.usrCoords[1]; 643 dpy = -p1.usrCoords[2]; 644 } 645 646 return dpx * dix + dpy * diy >= 0; 647 }, 648 649 /** 650 * If you're looking from point "start" towards point "s" and can see the point "p", true is returned. Otherwise false. 651 * @param {JXG.Coords} start The point you're standing on. 652 * @param {JXG.Coords} p The point in which direction you're looking. 653 * @param {JXG.Coords} s The point that should be visible. 654 * @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. 655 */ 656 isSameDirection: function(start, p, s) { 657 var dx, dy, sx, sy, r = false; 658 659 dx = p.usrCoords[1] - start.usrCoords[1]; 660 dy = p.usrCoords[2] - start.usrCoords[2]; 661 662 sx = s.usrCoords[1] - start.usrCoords[1]; 663 sy = s.usrCoords[2] - start.usrCoords[2]; 664 665 if (Math.abs(dx) < JXG.Math.eps) dx = 0; 666 if (Math.abs(dy) < JXG.Math.eps) dy = 0; 667 if (Math.abs(sx) < JXG.Math.eps) sx = 0; 668 if (Math.abs(sy) < JXG.Math.eps) sy = 0; 669 670 if (dx >= 0 && sx >= 0) { 671 if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) { 672 r = true; 673 } 674 } else if (dx <= 0 && sx <= 0) { 675 if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) { 676 r = true; 677 } 678 } 679 680 return r; 681 }, 682 683 /****************************************/ 684 /**** INTERSECTIONS ****/ 685 /****************************************/ 686 687 /** 688 * Calculates the coordinates of the intersection of the given lines. 689 * @deprecated 690 * @param {JXG.Line} line1 Line. 691 * @param {JXG.Line} line2 Line. 692 * @param {JXG.Board} [board=line1.board] Reference to the board 693 * @returns {JXG.Coords} Coordinates of the intersection point of the given lines. 694 */ 695 intersectLineLine: function(line1, line2, board) { 696 var A = line1.point1.coords.usrCoords, 697 B = line1.point2.coords.usrCoords, 698 C = line2.point1.coords.usrCoords, 699 D = line2.point2.coords.usrCoords, 700 d0, d1, den, x, y; 701 702 if (!JXG.exists(board)) 703 board = line1.board; 704 705 d0 = A[1] * B[2] - A[2] * B[1]; 706 d1 = C[1] * D[2] - C[2] * D[1]; 707 den = (B[2] - A[2]) * (C[1] - D[1]) - (A[1] - B[1]) * (D[2] - C[2]); 708 709 if (Math.abs(den) < JXG.Math.eps) { 710 den = JXG.Math.eps; 711 } 712 x = (d0 * (C[1] - D[1]) - d1 * (A[1] - B[1])) / den; 713 y = (d1 * (B[2] - A[2]) - d0 * (D[2] - C[2])) / den; 714 715 return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board); 716 }, 717 718 /** 719 * Calculates the coordinates of the intersection of the given line and circle. 720 * @deprecated 721 * @param {JXG.Circle} circle Circle. 722 * @param {JXG.Line} line Line. 723 * @param {JXG.Board} [board=line.board] Reference to the board 724 * @returns {Array} The coordinates of the intersection points of the given circle with the given line and 725 * the amount of intersection points in the first component of the array. 726 */ 727 intersectCircleLine: function(circle, line, board) { 728 var eA = line.point1.coords.usrCoords, 729 eB = line.point2.coords.usrCoords, 730 fM = circle.center.coords.usrCoords, 731 s, d0, d1, b, w, h, r, n1, dx, dy, firstPointX, firstPointY, l, x, y, n1s, firstPoint, secondPoint, d; 732 733 if (!JXG.exists(board)) 734 board = line.board; 735 736 s = line.point1.Dist(line.point2); 737 if (s > 0) { 738 d0 = circle.center.Dist(line.point1); 739 d1 = circle.center.Dist(line.point2); 740 b = ((d0 * d0) + (s * s) - (d1 * d1)) / (2 * s); 741 w = (d0 * d0) - (b * b); 742 w = (w < 0) ? 0 : w; 743 h = Math.sqrt(w); 744 745 r = circle.Radius(); 746 n1 = Math.sqrt((r * r) - h * h); 747 dx = eB[1] - eA[1]; 748 dy = eB[2] - eA[2]; 749 firstPointX = fM[1] + (h / s) * dy; 750 firstPointY = fM[2] - (h / s) * dx; 751 d0 = (eB[1] * dy) - (eB[2] * dx); 752 d1 = (firstPointX * dx) + (firstPointY * dy); 753 l = (dy * dy) + (dx * dx); 754 if (Math.abs(l) < JXG.Math.eps) { 755 l = JXG.Math.eps; 756 } 757 x = ((d0 * dy) + (d1 * dx)) / l; 758 y = ((d1 * dy) - (d0 * dx)) / l; 759 n1s = n1 / s; 760 firstPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x + n1s * dx, y + n1s * dy], board); 761 secondPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x - n1s * dx, y - n1s * dy], board); 762 d = circle.center.coords.distance(JXG.COORDS_BY_USER, firstPoint); 763 764 if ((r < (d - 1)) || isNaN(d)) { 765 return [0]; 766 } else { 767 return [2,firstPoint,secondPoint]; 768 } 769 } 770 return [0]; 771 }, 772 773 /** 774 * Calculates the coordinates of the intersection of the given circles. 775 * @deprecated 776 * @param {JXG.Circle} circle1 Circle. 777 * @param {JXG.Circle} circle2 Circle. 778 * @param {JXG.Board} [board=circle1.board] Reference to the board 779 * @returns {Array} Coordinates of the intersection points of the given circles and the 780 * amount of intersection points in the first component of the array. 781 */ 782 intersectCircleCircle: function(circle1, circle2, board) { 783 var intersection = {}, 784 r1 = circle1.Radius(), 785 r2 = circle2.Radius(), 786 M1 = circle1.center.coords.usrCoords, 787 M2 = circle2.center.coords.usrCoords, 788 rSum, rDiff, s, 789 dx, dy, a, h; 790 791 if (!JXG.exists(board)) 792 board = circle1.board; 793 794 rSum = r1 + r2; 795 rDiff = Math.abs(r1 - r2); 796 // Abstand der Mittelpunkte der beiden Kreise 797 s = circle1.center.coords.distance(JXG.COORDS_BY_USER, circle2.center.coords); 798 if (s > rSum) { 799 return [0]; // Kreise schneiden sich nicht, liegen nebeneinander 800 } else if (s < rDiff) { 801 return [0]; // Kreise schneiden sich nicht, liegen ineinander 802 } else { 803 if (s != 0) { 804 intersection[0] = 1; // es gibt einen Schnitt 805 dx = M2[1] - M1[1]; 806 dy = M2[2] - M1[2]; 807 a = (s * s - r2 * r2 + r1 * r1) / (2 * s); 808 h = Math.sqrt(r1 * r1 - a * a); 809 intersection[1] = new JXG.Coords(JXG.COORDS_BY_USER, 810 [M1[1] + (a / s) * dx + (h / s) * dy, 811 M1[2] + (a / s) * dy - (h / s) * dx], 812 board); 813 intersection[2] = new JXG.Coords(JXG.COORDS_BY_USER, 814 [M1[1] + (a / s) * dx - (h / s) * dy, 815 M1[2] + (a / s) * dy + (h / s) * dx], 816 board); 817 } else { 818 return [0]; // vorsichtshalber... 819 } 820 return intersection; 821 } 822 }, 823 824 /** 825 * Computes the intersection of a pair of lines, circles or both. 826 * It uses the internal data array stdform of these elements. 827 * @param {Array} el1 stdform of the first element (line or circle) 828 * @param {Array} el2 stdform of the second element (line or circle) 829 * @param {Number} i Index of the intersection point that should be returned. 830 * @param board Reference to the board. 831 * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points. 832 * Which point will be returned is determined by i. 833 */ 834 meet: function(el1, el2, i, board) { 835 var eps = JXG.Math.eps; // var eps = 0.000001; 836 if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { // line line 837 return this.meetLineLine(el1, el2, i, board); 838 } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { // circle line 839 return this.meetLineCircle(el2, el1, i, board); 840 } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { // line circle 841 return this.meetLineCircle(el1, el2, i, board); 842 } else { // circle circle 843 return this.meetCircleCircle(el1, el2, i, board); 844 } 845 }, 846 847 /** 848 * Intersection of two lines using the stdform. 849 * @param {Array} l1 stdform of the first line 850 * @param {Array} l2 stdform of the second line 851 * @param {number} i unused 852 * @param {JXG.Board} board Reference to the board. 853 * @returns {JXG.Coords} Coordinates of the intersection point. 854 */ 855 meetLineLine: function(l1, l2, i, board) { 856 var s = JXG.Math.crossProduct(l1, l2); 857 if (Math.abs(s[0]) > JXG.Math.eps) { 858 s[1] /= s[0]; 859 s[2] /= s[0]; 860 s[0] = 1.0; 861 } 862 return new JXG.Coords(JXG.COORDS_BY_USER, s, board); 863 }, 864 865 /** 866 * Intersection of line and circle using the stdform. 867 * @param {Array} lin stdform of the line 868 * @param {Array} circ stdform of the circle 869 * @param {number} i number of the returned intersection point. 870 * i==0: use the positive square root, 871 * i==1: use the negative square root. 872 * @param {JXG.Board} board Reference to a board. 873 * @returns {JXG.Coords} Coordinates of the intersection point 874 */ 875 meetLineCircle: function(lin, circ, i, board) { 876 var a,b,c,d,n, A,B,C, k,t; 877 if (circ[4] < JXG.Math.eps) { // Radius is zero, return center of circle 878 if (Math.abs( JXG.Math.innerProduct([1,circ[6],circ[7]], lin, 3)) < JXG.Math.eps) { 879 return new JXG.Coords(JXG.COORDS_BY_USER, circ.slice(6, 8), board); 880 } else { 881 return new JXG.Coords(JXG.COORDS_BY_USER, [NaN,NaN], board); 882 } 883 } 884 c = circ[0]; 885 b = circ.slice(1, 3); 886 a = circ[3]; 887 d = lin[0]; 888 n = lin.slice(1, 3); 889 890 // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations: 891 /* 892 var nn = n[0]*n[0]+n[1]*n[1]; 893 A = a*nn; 894 B = (b[0]*n[1]-b[1]*n[0])*nn; 895 C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn; 896 */ 897 A = a; 898 B = (b[0] * n[1] - b[1] * n[0]); 899 C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c; 900 901 k = B * B - 4 * A * C; 902 if (k >= 0) { 903 k = Math.sqrt(k); 904 t = [(-B + k) / (2 * A),(-B - k) / (2 * A)]; 905 return ((i == 0) 906 ? new JXG.Coords(JXG.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0],-t[0] * n[0] - d * n[1]], board) 907 : new JXG.Coords(JXG.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0],-t[1] * n[0] - d * n[1]], board) 908 ); 909 /* 910 new JXG.Coords(JXG.COORDS_BY_USER, [-t[0]*(-n[1])-d*n[0]/nn,-t[0]*n[0]-d*n[1]/nn], this.board), 911 new JXG.Coords(JXG.COORDS_BY_USER, [-t[1]*(-n[1])-d*n[0]/nn,-t[1]*n[0]-d*n[1]/nn], this.board) 912 */ 913 } else { 914 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board); 915 } 916 // Returns do not work with homogeneous coordinates, yet 917 }, 918 919 /** 920 * Intersection of two circles using the stdform. 921 * @param {Array} circ1 stdform of the first circle 922 * @param {Array} circ2 stdform of the second circle 923 * @param {number} i number of the returned intersection point. 924 * i==0: use the positive square root, 925 * i==1: use the negative square root. 926 * @param {JXG.Board} board Reference to the board. 927 * @returns {JXG.Coords} Coordinates of the intersection point 928 */ 929 meetCircleCircle: function(circ1, circ2, i, board) { 930 var radicalAxis; 931 if (circ1[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle 932 if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < JXG.Math.eps) { 933 return new JXG.Coords(JXG.COORDS_BY_USER, circ1.slice(6, 8), board); 934 } else { 935 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board); 936 } 937 } 938 if (circ2[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle 939 if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < JXG.Math.eps) { 940 return new JXG.Coords(JXG.COORDS_BY_USER, circ2.slice(6, 8), board); 941 } else { 942 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board); 943 } 944 } 945 radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0], 946 circ2[3] * circ1[1] - circ1[3] * circ2[1], 947 circ2[3] * circ1[2] - circ1[3] * circ2[2], 948 0,1,Infinity, Infinity, Infinity]; 949 radicalAxis = JXG.Math.normalize(radicalAxis); 950 return this.meetLineCircle(radicalAxis, circ1, i, board); 951 // Returns do not work with homogeneous coordinates, yet 952 }, 953 954 /** 955 * Compute an intersection of the curves c1 and c2 956 * with a generalized Newton method. 957 * We want to find values t1, t2 such that 958 * c1(t1) = c2(t2), i.e. 959 * (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0). 960 * We set 961 * (e,f) := (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) 962 * 963 * The Jacobian J is defined by 964 * J = (a, b) 965 * (c, d) 966 * where 967 * a = c1_x'(t1) 968 * b = -c2_x'(t2) 969 * c = c1_y'(t1) 970 * d = -c2_y'(t2) 971 * 972 * The inverse J^(-1) of J is equal to 973 * (d, -b)/ 974 * (-c, a) / (ad-bc) 975 * 976 * Then, (t1new, t2new) := (t1,t2) - J^(-1)*(e,f). 977 * If the function meetCurveCurve possesses the properties 978 * t1memo and t2memo then these are taken as start values 979 * for the Newton algorithm. 980 * After stopping of the Newton algorithm the values of t1 and t2 are stored in 981 * t1memo and t2memo. 982 * 983 * @param {JXG.Curve} c1 Curve, Line or Circle 984 * @param {JXG.Curve} c2 Curve, Line or Circle 985 * @param {Number} t1ini start value for t1 986 * @param {Number} t2ini start value for t2 987 * @param {JXG.Board} [board=c1.board] Reference to a board object. 988 * @returns {JXG.Coords} intersection point 989 */ 990 meetCurveCurve: function(c1, c2, t1ini, t2ini, board) { 991 var count = 0, 992 t1, t2, 993 a, b, c, d, disc, 994 e, f, F, 995 D00, D01, 996 D10, D11; 997 998 if (!JXG.exists(board)) 999 board = c1.board; 1000 1001 if (arguments.callee.t1memo) { 1002 t1 = arguments.callee.t1memo; 1003 t2 = arguments.callee.t2memo; 1004 } else { 1005 t1 = t1ini; 1006 t2 = t2ini; 1007 } 1008 1009 /* 1010 if (t1>c1.maxX()) { t1 = c1.maxX(); } 1011 if (t1<c1.minX()) { t1 = c1.minX(); } 1012 if (t2>c2.maxX()) { t2 = c2.maxX(); } 1013 if (t2<c2.minX()) { t2 = c2.minX(); } 1014 */ 1015 1016 c1X = function(t) { return c1.X.apply(c1, [t]); }; 1017 c1Y = function(t) { return c1.Y.apply(c1, [t]); }; 1018 c2X = function(t) { return c2.X.apply(c2, [t]); }; 1019 c2Y = function(t) { return c2.Y.apply(c2, [t]); }; 1020 1021 e = c1.X(t1) - c2.X(t2); 1022 f = c1.Y(t1) - c2.Y(t2); 1023 F = e * e + f * f; 1024 1025 D00 = board.D(c1.X, c1); 1026 D01 = board.D(c2.X, c2); 1027 D10 = board.D(c1.Y, c1); 1028 D11 = board.D(c2.Y, c2); 1029 1030 while (F > JXG.Math.eps && count < 10) { 1031 a = D00(t1); 1032 b = -D01(t2); 1033 c = D10(t1); 1034 d = -D11(t2); 1035 disc = a * d - b * c; 1036 t1 -= (d * e - b * f) / disc; 1037 t2 -= (a * f - c * e) / disc; 1038 e = c1.X(t1) - c2.X(t2); 1039 f = c1.Y(t1) - c2.Y(t2); 1040 F = e * e + f * f; 1041 count++; 1042 } 1043 //console.log(t1+' '+t2); 1044 1045 arguments.callee.t1memo = t1; 1046 arguments.callee.t2memo = t2; 1047 1048 //return (new JXG.Coords(JXG.COORDS_BY_USER, [2,2], this.board)); 1049 if (Math.abs(t1) < Math.abs(t2)) { 1050 return (new JXG.Coords(JXG.COORDS_BY_USER, [c1.X(t1),c1.Y(t1)], board)); 1051 } else { 1052 return (new JXG.Coords(JXG.COORDS_BY_USER, [c2.X(t2),c2.Y(t2)], board)); 1053 } 1054 }, 1055 1056 /** 1057 * Intersection of curve with line, 1058 * Order of input does not matter for el1 and el2. 1059 * @param {JXG.Curve,JXG.Line} el1 Curve or Line 1060 * @param {JXG.Curve,JXG.Line} el2 Curve or Line 1061 * @param {Number} nr the nr-th intersection point will be returned. 1062 * @param {JXG.Board} [board=el1.board] Reference to a board object. 1063 * @returns {JXG.Coords} Intersection point. In case no intersection point is detected, 1064 * the ideal point [0,1,0] is returned. 1065 */ 1066 meetCurveLine: function(el1, el2, nr, board, pointObj) { 1067 var v = [0, NaN, NaN], i, cu, li; 1068 1069 if (!JXG.exists(board)) { 1070 board = el1.board; 1071 } 1072 1073 for (i = 0; i <= 1; i++) { 1074 if (arguments[i].elementClass == JXG.OBJECT_CLASS_CURVE) { 1075 cu = arguments[i]; 1076 } else if (arguments[i].elementClass == JXG.OBJECT_CLASS_LINE) { 1077 li = arguments[i]; 1078 } else 1079 throw new Error("JSXGraph: Can't call meetCurveLine with parent class " + (arguments[i].elementClass) + "."); 1080 } 1081 1082 if (cu.visProp.curvetype==='plot') { 1083 v = this.meetCurveLineDiscrete(cu, li, nr, board, pointObj); 1084 } else { 1085 v = this.meetCurveLineContinuous(cu, li, nr, board); 1086 } 1087 1088 return v; 1089 }, 1090 1091 /** 1092 * Intersection of line and curve, continuous case. 1093 * Segments are treated as lines. Finding the nr-the intersection point 1094 * works for nr=0,1 only. 1095 * 1096 * BUG: does not respect cu.minX() and cu.maxX() 1097 */ 1098 meetCurveLineContinuous: function(cu, li, nr, board) { 1099 var t, t2, i, cu, li, func, z, 1100 tnew, steps, delta, tstart, tend, cux, cuy; 1101 1102 func = function(t) { 1103 return li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t); 1104 }; 1105 1106 /** 1107 * Find some intersection point 1108 */ 1109 if (arguments.callee.t1memo) { 1110 tstart = arguments.callee.t1memo; 1111 t = JXG.Math.Numerics.root(func, tstart); 1112 } else { 1113 tstart = cu.minX(); 1114 tend = cu.maxX(); 1115 t = JXG.Math.Numerics.root(func, [tstart,tend]); 1116 } 1117 arguments.callee.t1memo = t; 1118 cux = cu.X(t); 1119 cuy = cu.Y(t); 1120 1121 /** 1122 * Find second intersection point 1123 */ 1124 if (nr == 1) { 1125 if (arguments.callee.t2memo) { 1126 tstart = arguments.callee.t2memo; 1127 t2 = JXG.Math.Numerics.root(func, tstart); 1128 } 1129 if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) { 1130 steps = 20; 1131 delta = (cu.maxX() - cu.minX()) / steps; 1132 tnew = cu.minX(); 1133 for (i = 0; i < steps; i++) { 1134 t2 = JXG.Math.Numerics.root(func, [tnew,tnew + delta]); 1135 if (Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1) { 1136 break; 1137 } 1138 tnew += delta; 1139 } 1140 } 1141 t = t2; 1142 arguments.callee.t2memo = t; 1143 } 1144 1145 if (Math.abs(func(t)) > JXG.Math.eps) { 1146 z = NaN; 1147 } else { 1148 z = 1.0; 1149 } 1150 return (new JXG.Coords(JXG.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board)); 1151 }, 1152 1153 /** 1154 * Intersection of line and curve, continuous case. 1155 * Segments are treated as lines. 1156 * Finding the nr-the intersection point should work for all nr. 1157 */ 1158 meetCurveLineDiscrete: function(cu, li, nr, board, pointObj) { 1159 var len, i, p1, p2, q, 1160 d, cnt = 0, res, 1161 p, testSegment = false; 1162 1163 len = cu.numberPoints; 1164 if (pointObj!=null) { 1165 p = pointObj.point; 1166 if (JXG.exists(p) && !p.visProp.alwaysintersect) { 1167 testSegment = true; 1168 } 1169 1170 } 1171 1172 // In case, no intersection will be found we will take this 1173 q = new JXG.Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], board); 1174 1175 p2 = [1, cu.X(0), cu.Y(0)]; 1176 for (i=1;i<len;i++) { 1177 p1 = p2.slice(0); 1178 p2 = [1, cu.X(i), cu.Y(i)]; 1179 d = this.distance(p1, p2); 1180 if (d<JXG.Math.eps) { // The defining points are identical 1181 continue; 1182 } 1183 res = this.meetSegmentSegment(p1, p2, li.point1.coords.usrCoords, li.point2.coords.usrCoords, board); 1184 if (0<=res[1] && res[1]<=1) { 1185 if (cnt==nr) { 1186 1187 /** 1188 * If the intersection point is not part of the segment, 1189 * this intersection point is set to non-existent. 1190 * This prevents jumping of the intersection points. 1191 * But it may be discussed if it is the desired behavior. 1192 */ 1193 if (testSegment 1194 && ( li.visProp.straightfirst==false && res[2]<0 1195 || li.visProp.straightlast==false && res[2]>1 ) 1196 ) { 1197 break; 1198 } 1199 1200 q = new JXG.Coords(JXG.COORDS_BY_USER, res[0], board); 1201 break; 1202 } 1203 cnt++; 1204 } 1205 } 1206 1207 return q; 1208 }, 1209 1210 /** 1211 * Intersection of two segments. 1212 * @param {Array} p1 First point of segment 1 using homogeneous coordinates [z,x,y] 1213 * @param {Array} p2 Second point of segment 1 using homogeneous coordinates [z,x,y] 1214 * @param {Array} q1 First point of segment 2 using homogeneous coordinates [z,x,y] 1215 * @param {Array} q2 Second point of segment 2 using homogeneous coordinates [z,x,y] 1216 * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 1217 * of the intersection point. The second and third entry gives the position of the intersection between the two defining points. 1218 * For example, the second entry t is defined by: interestion point = t*p1 + (1-t)*p2. 1219 **/ 1220 meetSegmentSegment: function(p1, p2, q1, q2, board) { 1221 var li1 = JXG.Math.crossProduct(p1, p2), 1222 li2 = JXG.Math.crossProduct(q1, q2), 1223 c = JXG.Math.crossProduct(li1, li2), 1224 denom = c[0], 1225 t, u, diff; 1226 1227 if (Math.abs(denom)<Math.eps) { 1228 return [c, Number.Infinity, Number.Infinity]; 1229 } 1230 1231 diff = [q1[1]-p1[1], q1[2]-p1[2]]; 1232 // Because of speed issues, evalute the determinants directly 1233 //t = JXG.Math.Numerics.det([diff, [p2[1]-p1[1], p2[2]-p1[2]] ]) / denom; 1234 //u = JXG.Math.Numerics.det([diff, [q2[1]-q1[1], q2[2]-q1[2]] ]) / denom; 1235 t = (diff[0]*(q2[2]-q1[2]) - diff[1]*(q2[1]-q1[1])) / denom; 1236 u = (diff[0]*(p2[2]-p1[2]) - diff[1]*(p2[1]-p1[1])) / denom; 1237 1238 return [c, t, u]; 1239 }, 1240 1241 /****************************************/ 1242 /**** PROJECTIONS ****/ 1243 /****************************************/ 1244 1245 /** 1246 * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the 1247 * nearest one of the two intersection points of the line through the given point and the circles 1248 * center. 1249 * @param {JXG.Point_JXG.Coords} point Point to project or coords object to project. 1250 * @param {JXG.Circle} circle Circle on that the point is projected. 1251 * @param {JXG.Board} [board=point.board] Reference to the board 1252 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 1253 */ 1254 projectPointToCircle: function(point, circle, board) { 1255 var dist, P, 1256 M = circle.center.coords.usrCoords, 1257 x, y, factor; 1258 1259 if (!JXG.exists(board)) { 1260 board = point.board; 1261 } 1262 1263 if (JXG.isPoint(point)) { 1264 dist = point.coords.distance(JXG.COORDS_BY_USER, circle.center.coords); 1265 P = point.coords.usrCoords; 1266 } else { // coords 1267 dist = point.distance(JXG.COORDS_BY_USER, circle.center.coords); 1268 P = point.usrCoords; 1269 } 1270 1271 if (Math.abs(dist) < JXG.Math.eps) { 1272 dist = JXG.Math.eps; 1273 } 1274 factor = circle.Radius() / dist; 1275 x = M[1] + factor * (P[1] - M[1]); 1276 y = M[2] + factor * (P[2] - M[2]); 1277 1278 return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board); 1279 }, 1280 1281 /** 1282 * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the 1283 * intersection point of the given line and its perpendicular through the given point. 1284 * @param {JXG.Point} point Point to project. 1285 * @param {JXG.Line} line Line on that the point is projected. 1286 * @param {JXG.Board} [board=point.board] Reference to a board. 1287 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line. 1288 */ 1289 projectPointToLine: function(point, line, board) { 1290 // Homogeneous version 1291 var v = [0,line.stdform[1],line.stdform[2]]; 1292 1293 if (!JXG.exists(board)) 1294 board = point.board; 1295 1296 v = JXG.Math.crossProduct(v, point.coords.usrCoords); 1297 1298 return this.meetLineLine(v, line.stdform, 0, board); 1299 }, 1300 1301 /** 1302 * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line 1303 * segment defined by two coordinate arrays. 1304 * @param {Array} p1 Point to project. 1305 * @param {Array} q1 Start point of the line segment on that the point is projected. 1306 * @param {Array} q2 End point of the line segment on that the point is projected. 1307 * @returns {Array} The coordinates of the projection of the given point on the given segment 1308 * and the factor that determines the projected point as a convex combination of the 1309 * two endpoints q1 and q2 of the segment. 1310 */ 1311 projectCoordsToSegment: function(p, q1, q2) { 1312 var s = [q2[1]-q1[1], q2[2]-q1[2]], 1313 v = [p[1]-q1[1], p[2]-q1[2]], 1314 t, denom, c; 1315 1316 /** 1317 * If the segment has length 0, i.e. is a point, 1318 * the projection is equal to that point. 1319 */ 1320 if (Math.abs(s[0])<JXG.Math.eps && Math.abs(s[1])<JXG.Math.eps) { 1321 return q1; 1322 } 1323 t = JXG.Math.innerProduct(v,s); 1324 denom = JXG.Math.innerProduct(s,s); 1325 t /= denom; 1326 return [ [1, t*s[0]+q1[1], t*s[1]+q1[2]], t]; 1327 }, 1328 1329 /** 1330 * Calculates the coordinates of the projection of a given point on a given curve. 1331 * Uses {@link #projectCoordsToCurve}. 1332 * @param {JXG.Point} point Point to project. 1333 * @param {JXG.Curve} curve Curve on that the point is projected. 1334 * @param {JXG.Board} [board=point.board] Reference to a board. 1335 * @see #projectCoordsToCurve 1336 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph. 1337 */ 1338 projectPointToCurve: function(point, curve, board) { 1339 if (!JXG.exists(board)) 1340 board = point.board; 1341 1342 var x = point.X(), 1343 y = point.Y(), 1344 t = point.position || 0.0, //(curve.minX()+curve.maxX())*0.5, 1345 result = this.projectCoordsToCurve(x, y, t, curve, board); 1346 1347 point.position = result[1]; // side effect ! 1348 return result[0]; 1349 }, 1350 1351 /** 1352 * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of 1353 * function graphs this is the 1354 * intersection point of the curve and the parallel to y-axis through the given point. 1355 * @param {Number} x coordinate to project. 1356 * @param {Number} y coordinate to project. 1357 * @param {Number} t start value for newtons method 1358 * @param {JXG.Curve} curve Curve on that the point is projected. 1359 * @param {JXG.Board} [board=curve.board] Reference to a board. 1360 * @see #projectPointToCurve 1361 * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and 1362 * the position on the curve. 1363 */ 1364 projectCoordsToCurve: function(x, y, t, curve, board) { 1365 var newCoords, i, 1366 x0, y0, x1, y1, mindist, dist, lbda, li, v, coords, d, 1367 p1, p2, q1, q2, res, 1368 infty = Number.POSITIVE_INFINITY, 1369 minfunc, t, tnew, fnew, fold, delta, steps; 1370 1371 if (!JXG.exists(board)) { 1372 board = curve.board; 1373 } 1374 1375 if (curve.visProp.curvetype == 'parameter' || curve.visProp.curvetype == 'polar') { 1376 // Function to minimize 1377 minfunc = function(t) { 1378 var dx = x - curve.X(t), 1379 dy = y - curve.Y(t); 1380 return dx * dx + dy * dy; 1381 }; 1382 1383 fold = minfunc(t); 1384 steps = 20; 1385 delta = (curve.maxX() - curve.minX()) / steps; 1386 tnew = curve.minX(); 1387 for (i = 0; i < steps; i++) { 1388 fnew = minfunc(tnew); 1389 if (fnew < fold) { 1390 t = tnew; 1391 fold = fnew; 1392 } 1393 tnew += delta; 1394 } 1395 t = JXG.Math.Numerics.root(JXG.Math.Numerics.D(minfunc), t); 1396 1397 if (t < curve.minX()) { 1398 t = curve.maxX() + t - curve.minX(); 1399 } // Cyclically 1400 if (t > curve.maxX()) { 1401 t = curve.minX() + t - curve.maxX(); 1402 } 1403 newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [curve.X(t),curve.Y(t)], board); 1404 } else if (curve.visProp.curvetype == 'plot') { 1405 t = 0; 1406 mindist = infty; 1407 if (curve.numberPoints==0) { 1408 newCoords = [0,1,1]; 1409 } else { 1410 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 1411 } 1412 1413 if (curve.numberPoints>1) { 1414 p1 = [curve.Z(0), curve.X(0), curve.Y(0)]; 1415 for (i=0; i<curve.numberPoints-1; i++) { 1416 p2 = [curve.Z(i+1), curve.X(i+1), curve.Y(i+1)]; 1417 v = [1, x, y]; 1418 res = this.projectCoordsToSegment(v, p1, p2); 1419 lbda = res[1]; 1420 coords = res[0]; 1421 if (0.0<=lbda && lbda<=1.0) { 1422 dist = this.distance(coords, v); 1423 d = i + lbda; 1424 } else if (lbda<0.0) { 1425 coords = p1; 1426 dist = this.distance(p1, v); 1427 d = i; 1428 } else if (lbda>1.0 && i+1== curve.numberPoints-1) { 1429 coords = p2; 1430 dist = this.distance(coords, v); 1431 d = curve.numberPoints-1; 1432 } 1433 1434 if (dist < mindist) { 1435 mindist = dist; 1436 t = d; 1437 newCoords = coords; 1438 } 1439 p1 = p2; // Moving on. 1440 } 1441 } 1442 1443 newCoords = new JXG.Coords(JXG.COORDS_BY_USER, newCoords, board); 1444 } else { // functiongraph 1445 t = x; 1446 x = t; //curve.X(t); 1447 y = curve.Y(t); 1448 newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board); 1449 } 1450 return [curve.updateTransform(newCoords), t]; 1451 }, 1452 1453 /** 1454 * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of 1455 * one or more curves of curveType 'plot'. Uses {@link #projectPointToCurve}. 1456 * @param {JXG.Point} point Point to project. 1457 * @param {JXG.Turtle} turtle on that the point is projected. 1458 * @param {JXG.Board} [board=point.board] Reference to a board. 1459 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle. 1460 */ 1461 projectPointToTurtle: function(point, turtle, board) { 1462 var newCoords, t, x, y, i, 1463 np = 0, 1464 npmin = 0, 1465 mindist = Number.POSITIVE_INFINITY, 1466 dist, el, minEl, 1467 len = turtle.objects.length; 1468 1469 if (!JXG.exists(board)) 1470 board = point.board; 1471 1472 for (i = 0; i < len; i++) { // run through all curves of this turtle 1473 el = turtle.objects[i]; 1474 if (el.elementClass == JXG.OBJECT_CLASS_CURVE) { 1475 newCoords = this.projectPointToCurve(point, el); 1476 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords); 1477 if (dist < mindist) { 1478 x = newCoords.usrCoords[1]; 1479 y = newCoords.usrCoords[2]; 1480 t = point.position; 1481 mindist = dist; 1482 minEl = el; 1483 npmin = np; 1484 } 1485 np += el.numberPoints; 1486 } 1487 } 1488 newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board); 1489 point.position = t + npmin; 1490 return minEl.updateTransform(newCoords); 1491 }, 1492 1493 /** 1494 * Trivial projection of a point to another point. 1495 * @param {JXG.Point} point Point to project (not used). 1496 * @param {JXG.Point} dest Point on that the point is projected. 1497 * @param {JXG.Board} [board=point.board] Reference to the board (not used). 1498 * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle. 1499 */ 1500 projectPointToPoint: function(point, dest, board) { 1501 return dest.coords; 1502 }, 1503 1504 /** 1505 * Calculates the distance of a point to a line. The point and the line are given by homogeneous 1506 * coordinates. For lines this can be line.stdform. 1507 * @param {Array} point Homogeneous coordinates of a point. 1508 * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0). 1509 * @returns {Number} Distance of the point to the line. 1510 */ 1511 distPointLine: function(point, line) { 1512 var a = line[1], 1513 b = line[2], 1514 c = line[0], 1515 nom; 1516 1517 if (Math.abs(a)+Math.abs(b) < JXG.Math.eps) { 1518 return Number.POSITIVE_INFINITY; 1519 } 1520 1521 nom = a*point[1] + b*point[2] + c*1; 1522 a *= a; 1523 b *= b; 1524 return Math.abs(nom) / Math.sqrt(a+b); 1525 } 1526 1527 }); 1528