      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, {
     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, den, x, y;
    332
    333         if (!JXG.exists(board))
    334             board = point1.board;
    335
    336         u = ((A[1] - B[1]) * (A[1] + B[1]) + (A[2] - B[2]) * (A[2] + B[2])) * 0.5;
    337         v = ((B[1] - C[1]) * (B[1] + C[1]) + (B[2] - C[2]) * (B[2] + C[2])) * 0.5;
    338         den = (A[1] - B[1]) * (B[2] - C[2]) - (B[1] - C[1]) * (A[2] - B[2]);
    339
    340         if (Math.abs(den) < JXG.Math.eps) {
    341             den = JXG.Math.eps;
    342         	return new JXG.Coords(JXG.COORDS_BY_USER, [Infinity, Infinity], board);
    343         }
    344
    345         x = (u * (B[2] - C[2]) - v * (A[2] - B[2])) / den;
    346         y = (v * (A[1] - B[1]) - u * (B[1] - C[1])) / den;
    347
    348         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
    349     },
    350
    351     /**
    352      * Calculates euclidean norm for two given arrays of the same length.
    353      * @param {Array} array1 Array of float or integer.
    354      * @param {Array} array2 Array of float or integer.
    355      * @returns {Number} Euclidean distance of the given vectors.
    356      */
    357     distance: function(array1, array2) {
    358         var sum = 0,
    359             i, len;
    360
    361         if (array1.length != array2.length) {
    362             return NaN;
    363         }
    364         len = array1.length;
    365         for (i = 0; i < len; i++) {
    366             sum += (array1[i] - array2[i]) * (array1[i] - array2[i]);
    367         }
    368         return Math.sqrt(sum);
    369     },
    370
    371     /**
    372      * Calculates euclidean distance for two given arrays of the same length.
    373      * If one of the arrays contains a zero in the first coordinate, and the euclidean distance
    374      * is different from zero it is a point at infinity and we return Infinity.
    375      * @param {Array} array1 Array containing elements of number.
    376      * @param {Array} array2 Array containing elements of type number.
    377      * @returns {Number} Euclidean (affine) distance of the given vectors.
    378      */
    379     affineDistance: function(array1, array2) {
    380         var d;
    381         if (array1.length != array2.length) {
    382             return NaN;
    383         }
    384         d = this.distance(array1, array2);
    385         if (d > JXG.Math.eps && (Math.abs(array1[0]) < JXG.Math.eps || Math.abs(array2[0]) < JXG.Math.eps)) {
    386             return Infinity;
    387         } else {
    388             return d;
    389         }
    390     },
    391
    392     /**
    393      * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2
    394      * calcStraight determines the visual start point and end point of the line. A segment is only drawn
    395      * from start to end point, a straight line is drawn until it meets the boards boundaries.
    396      * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point.
    397      * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and set by this method.
    398      * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set by this method.
    399      * @see Line
    400      * @see JXG.Line
    401      */
    402     calcStraight: function(el, point1, point2) {
    403         var takePoint1, takePoint2, intersect1, intersect2, straightFirst, straightLast,
    404             c, s, i, j, p1, p2;
    405
    406         straightFirst = el.visProp.straightfirst;
    407         straightLast = el.visProp.straightlast;
    408
    409         // If one of the point is an ideal point in homogeneous coordinates
    410         // drawing of line segments or rays are not possible.
    411         if (Math.abs(point1.scrCoords[0]) < JXG.Math.eps) {
    412             straightFirst = true;
    413         }
    414         if (Math.abs(point2.scrCoords[0]) < JXG.Math.eps) {
    415             straightLast = true;
    416         }
    417
    418         if (!straightFirst && !straightLast) {  // Do nothing in case of line segments (inside or outside of the board)
    419             return;
    420         }
    421
    422         // Compute the stdform of the line in screen coordinates.
    423         c = [];
    424         c[0] = el.stdform[0] -
    425                 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX +
    426                 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY;
    427         c[1] = el.stdform[1] / el.board.unitX;
    428         c[2] = el.stdform[2] / (-el.board.unitY);
    429
    430         if (isNaN(c[0] + c[1] + c[2])) return; // p1=p2
    431
    432         // Intersect the line with the four borders of the board.
    433         s = [];
    434         s[0] = JXG.Math.crossProduct(c, [0,0,1]);  // top
    435         s[1] = JXG.Math.crossProduct(c, [0,1,0]);  // left
    436         s[2] = JXG.Math.crossProduct(c, [-el.board.canvasHeight,0,1]);  // bottom
    437         s[3] = JXG.Math.crossProduct(c, [-el.board.canvasWidth,1,0]);   // right
    438
    439         // Normalize the intersections
    440         for (i = 0; i < 4; i++) {
    441             if (Math.abs(s[i][0]) > JXG.Math.eps) {
    442                 for (j = 2; j > 0; j--) {
    443                     s[i][j] /= s[i][0];
    444                 }
    445                 s[i][0] = 1.0;
    446             }
    447         }
    448
    449         takePoint1 = false;
    450         takePoint2 = false;
    451         if (!straightFirst && // Line starts at point1 and point2 is inside the board
    452                 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth &&
    453                 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight) {
    454             takePoint1 = true;
    455         }
    456         if (!straightLast && // Line ends at point2 and point2 is inside the board
    457                 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth &&
    458                 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight) {
    459             takePoint2 = true;
    460         }
    461
    462         if (Math.abs(s[1][0]) < JXG.Math.eps) {           // line is parallel to "left", take "top" and "bottom"
    463             intersect1 = s[0];                          // top
    464             intersect2 = s[2];                          // bottom
    465         } else if (Math.abs(s[0][0]) < JXG.Math.eps) {           // line is parallel to "top", take "left" and "right"
    466             intersect1 = s[1];                          // left
    467             intersect2 = s[3];                          // right
    468         } else if (s[1][2] < 0) {                         // left intersection out of board (above)
    469             intersect1 = s[0];                          // top
    470             if (s[3][2] > el.board.canvasHeight) {        // right intersection out of board (below)
    471                 intersect2 = s[2];                      // bottom
    472             } else {
    473                 intersect2 = s[3];                      // right
    474             }
    475         } else if (s[1][2] > el.board.canvasHeight) {     // left intersection out of board (below)
    476             intersect1 = s[2];                          // bottom
    477             if (s[3][2] < 0) {                            // right intersection out of board (above)
    478                 intersect2 = s[0];                      // top
    479             } else {
    480                 intersect2 = s[3];                      // right
    481             }
    482         } else {
    483             intersect1 = s[1];                          // left
    484             if (s[3][2] < 0) {                            // right intersection out of board (above)
    485                 intersect2 = s[0];                      // top
    486             } else if (s[3][2] > el.board.canvasHeight) { // right intersection out of board (below)
    487                 intersect2 = s[2];                      // bottom
    488             } else {
    489                 intersect2 = s[3];                      // right
    490             }
    491         }
    492
    493         intersect1 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect1.slice(1), el.board);
    494         intersect2 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect2.slice(1), el.board);
    495
    496         /**
    497          * At this point we have four points:
    498          * point1 and point2 are the first and the second defining point on the line,
    499          * intersect1, intersect2 are the intersections of the line with border around the board.
    500          */
    501
    502         /*
    503          * Here we handle rays where both defining points are outside of the board.
    504          */
    505         if (!takePoint1 && !takePoint2) {              // If both points are outside and the complete ray is outside we do nothing
    506             if (!straightFirst && straightLast && // Ray starting at point 1
    507                     !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) {
    508                 return;
    509             } else if (straightFirst && !straightLast && // Ray starting at point 2
    510                     !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) {
    511                 return;
    512             }
    513         }
    514
    515         /*
    516          * If at least one of the definng points is outside of the board
    517          * we take intersect1 or intersect2 as one of the end points
    518          * The order is also important for arrows of axes
    519          */
    520         if (!takePoint1) {
    521             if (!takePoint2) {
    522                 /*
    523                  * Two border intersection points are used
    524                  */
    525                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
    526                     p1 = intersect1;
    527                     p2 = intersect2;
    528                 } else {
    529                     p2 = intersect1;
    530                     p1 = intersect2;
    531                 }
    532
    533                 /*
    534                 if (this.isSameDirection(point1, point2, intersect1)) {
    535                     if (!this.isSameDirection(point1, point2, intersect2)) {
    536                         p2 = intersect1;
    537                         p1 = intersect2;
    538                     } else {
    539                         if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) <= JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) {
    540                             p1 = intersect1;
    541                             p2 = intersect2;
    542                         } else {
    543                             p2 = intersect1;
    544                             p1 = intersect2;
    545                         }
    546                     }
    547                 } else {
    548                     if (this.isSameDirection(point1, point2, intersect2)) {
    549                         p1 = intersect1;
    550                         p2 = intersect2;
    551                     } else {
    552                         if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) < JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) {
    553                             p2 = intersect1;
    554                             p1 = intersect2;
    555                         } else {
    556                             p1 = intersect1;
    557                             p2 = intersect2;
    558                         }
    559                     }
    560                 }
    561                 */
    562             } else {
    563                 /*
    564                 * One border intersection points is used
    565                 */
    566                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
    567                     p1 = intersect1;
    568                 } else {
    569                     p1 = intersect2;
    570                 }
    571                 /*
    572                 if (this.isSameDirection(point2, point1, intersect1)) { // Instead of point1 the border intersection is taken
    573                     p1 = intersect1;
    574                 } else {
    575                     p1 = intersect2;
    576                 }
    577                 */
    578             }
    579         } else {
    580             if (!takePoint2) {
    581                 /*
    582                 * One border intersection points is used
    583                 */
    584                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
    585                     p2 = intersect2;
    586                 } else {
    587                     p2 = intersect1;
    588                 } /*
    589                 if (this.isSameDirection(point1, point2, intersect1)) { // Instead of point2 the border intersection is taken
    590                     p2 = intersect1;
    591                 } else {
    592                     p2 = intersect2;
    593                 }
    594                 */
    595             }
    596         }
    597
    598         if (p1) point1.setCoordinates(JXG.COORDS_BY_USER, p1.usrCoords.slice(1));
    599         if (p2) point2.setCoordinates(JXG.COORDS_BY_USER, p2.usrCoords.slice(1));
    600     },
    601
    602     /**
    603      * The vectors p2-p1 and i2-i1 are supposed collinear.
    604      * If their cosine is positive they point into the same direction
    605      * otherwise they point in opposite direction
    606      * @param {JXG.Coords} p1
    607      * @param {JXG.Coords} p2
    608      * @param {JXG.Coords} i1
    609      * @param {JXG.Coords} i2
    610      * @returns {Boolean} True, if p2-p1 and i2-i1 point into the same direction
    611      */
    612     isSameDir: function(p1, p2, i1, i2) {
    613         var dpx = p2.usrCoords[1] - p1.usrCoords[1],
    614             dpy = p2.usrCoords[2] - p1.usrCoords[2],
    615             dix = i2.usrCoords[1] - i1.usrCoords[1],
    616             diy = i2.usrCoords[2] - i1.usrCoords[2];
    617
    618         return dpx * dix + dpy * diy >= 0;
    619     },
    620
    621     /**
    622      * If you're looking from point "start" towards point "s" and can see the point "p", true is returned. Otherwise false.
    623      * @param {JXG.Coords} start The point you're standing on.
    624      * @param {JXG.Coords} p The point in which direction you're looking.
    625      * @param {JXG.Coords} s The point that should be visible.
    626      * @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.
    627      */
    628     isSameDirection: function(start, p, s) {
    629         var dx, dy, sx, sy, r = false;
    630
    631         dx = p.usrCoords[1] - start.usrCoords[1];
    632         dy = p.usrCoords[2] - start.usrCoords[2];
    633
    634         sx = s.usrCoords[1] - start.usrCoords[1];
    635         sy = s.usrCoords[2] - start.usrCoords[2];
    636
    637         if (Math.abs(dx) < JXG.Math.eps) dx = 0;
    638         if (Math.abs(dy) < JXG.Math.eps) dy = 0;
    639         if (Math.abs(sx) < JXG.Math.eps) sx = 0;
    640         if (Math.abs(sy) < JXG.Math.eps) sy = 0;
    641
    642         if (dx >= 0 && sx >= 0) {
    643             if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) {
    644                 r = true;
    645             }
    646         } else if (dx <= 0 && sx <= 0) {
    647             if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) {
    648                 r = true;
    649             }
    650         }
    651
    652         return r;
    653     },
    654
    655     /****************************************/
    656     /****          INTERSECTIONS         ****/
    657     /****************************************/
    658
    659     /**
    660      * Calculates the coordinates of the intersection of the given lines.
    661      * @param {JXG.Line} line1 Line.
    662      * @param {JXG.Line} line2 Line.
    663      * @param {JXG.Board} [board=line1.board] Reference to the board
    664      * @returns {JXG.Coords} Coordinates of the intersection point of the given lines.
    665      */
    666     intersectLineLine: function(line1, line2, board) {
    667         var A = line1.point1.coords.usrCoords,
    668             B = line1.point2.coords.usrCoords,
    669             C = line2.point1.coords.usrCoords,
    670             D = line2.point2.coords.usrCoords,
    671             d0, d1, den, x, y;
    672
    673         if (!JXG.exists(board))
    674             board = line1.board;
    675
    676         d0 = A[1] * B[2] - A[2] * B[1];
    677         d1 = C[1] * D[2] - C[2] * D[1];
    678         den = (B[2] - A[2]) * (C[1] - D[1]) - (A[1] - B[1]) * (D[2] - C[2]);
    679
    680         if (Math.abs(den) < JXG.Math.eps) {
    681             den = JXG.Math.eps;
    682         }
    683         x = (d0 * (C[1] - D[1]) - d1 * (A[1] - B[1])) / den;
    684         y = (d1 * (B[2] - A[2]) - d0 * (D[2] - C[2])) / den;
    685
    686         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
    687     },
    688
    689     /**
    690      * Calculates the coordinates of the intersection of the given line and circle.
    691      * @param {JXG.Circle} circle Circle.
    692      * @param {JXG.Line} line Line.
    693      * @param {JXG.Board} [board=line.board] Reference to the board
    694      * @returns {Array} The coordinates of the intersection points of the given circle with the given line and
    695      * the amount of intersection points in the first component of the array.
    696      */
    697     intersectCircleLine: function(circle, line, board) {
    698         var eA = line.point1.coords.usrCoords,
    699             eB = line.point2.coords.usrCoords,
    700             fM = circle.center.coords.usrCoords,
    701             s, d0, d1, b, w, h, r, n1, dx, dy, firstPointX, firstPointY, l, x, y, n1s, firstPoint, secondPoint, d;
    702
    703         if (!JXG.exists(board))
    704             board = line.board;
    705
    706         s = line.point1.Dist(line.point2);
    707         if (s > 0) {
    708             d0 = circle.center.Dist(line.point1);
    709             d1 = circle.center.Dist(line.point2);
    710             b = ((d0 * d0) + (s * s) - (d1 * d1)) / (2 * s);
    711             w = (d0 * d0) - (b * b);
    712             w = (w < 0) ? 0 : w;
    713             h = Math.sqrt(w);
    714
    715             r = circle.Radius();
    716             n1 = Math.sqrt((r * r) - h * h);
    717             dx = eB[1] - eA[1];
    718             dy = eB[2] - eA[2];
    719             firstPointX = fM[1] + (h / s) * dy;
    720             firstPointY = fM[2] - (h / s) * dx;
    721             d0 = (eB[1] * dy) - (eB[2] * dx);
    722             d1 = (firstPointX * dx) + (firstPointY * dy);
    723             l = (dy * dy) + (dx * dx);
    724             if (Math.abs(l) < JXG.Math.eps) {
    725                 l = JXG.Math.eps;
    726             }
    727             x = ((d0 * dy) + (d1 * dx)) / l;
    728             y = ((d1 * dy) - (d0 * dx)) / l;
    729             n1s = n1 / s;
    730             firstPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x + n1s * dx, y + n1s * dy], board);
    731             secondPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x - n1s * dx, y - n1s * dy], board);
    732             d = circle.center.coords.distance(JXG.COORDS_BY_USER, firstPoint);
    733
    734             if ((r < (d - 1)) || isNaN(d)) {
    735                 return [0];
    736             } else {
    737                 return [2,firstPoint,secondPoint];
    738             }
    739         }
    740         return [0];
    741     },
    742
    743     /**
    744      * Calculates the coordinates of the intersection of the given circles.
    745      * @param {JXG.Circle} circle1 Circle.
    746      * @param {JXG.Circle} circle2 Circle.
    747      * @param {JXG.Board} [board=circle1.board] Reference to the board
    748      * @returns {Array} Coordinates of the intersection points of the given circles and the
    749      * amount of intersection points in the first component of the array.
    750      */
    751     intersectCircleCircle: function(circle1, circle2, board) {
    752         var intersection = {},
    753             r1 = circle1.Radius(),
    754             r2 = circle2.Radius(),
    755             M1 = circle1.center.coords.usrCoords,
    756             M2 = circle2.center.coords.usrCoords,
    757             rSum, rDiff, s,
    758             dx, dy, a, h;
    759
    760         if (!JXG.exists(board))
    761             board = circle1.board;
    762
    763         rSum = r1 + r2;
    764         rDiff = Math.abs(r1 - r2);
    765         // Abstand der Mittelpunkte der beiden Kreise
    766         s = circle1.center.coords.distance(JXG.COORDS_BY_USER, circle2.center.coords);
    767         if (s > rSum) {
    768             return [0]; // Kreise schneiden sich nicht, liegen nebeneinander
    769         } else if (s < rDiff) {
    770             return [0]; // Kreise schneiden sich nicht, liegen ineinander
    771         } else {
    772             if (s != 0) {
    773                 intersection[0] = 1; // es gibt einen Schnitt
    774                 dx = M2[1] - M1[1];
    775                 dy = M2[2] - M1[2];
    776                 a = (s * s - r2 * r2 + r1 * r1) / (2 * s);
    777                 h = Math.sqrt(r1 * r1 - a * a);
    778                 intersection[1] = new JXG.Coords(JXG.COORDS_BY_USER,
    779                     [M1[1] + (a / s) * dx + (h / s) * dy,
    780                         M1[2] + (a / s) * dy - (h / s) * dx],
    781                     board);
    782                 intersection[2] = new JXG.Coords(JXG.COORDS_BY_USER,
    783                     [M1[1] + (a / s) * dx - (h / s) * dy,
    784                         M1[2] + (a / s) * dy + (h / s) * dx],
    785                     board);
    786             } else {
    787                 return [0]; // vorsichtshalber...
    788             }
    789             return intersection;
    790         }
    791     },
    792
    793     /**
    794      * Computes the intersection of a pair of lines, circles or both.
    795      * It uses the internal data array stdform of these elements.
    796      * @param {Array} el1 stdform of the first element (line or circle)
    797      * @param {Array} el2 stdform of the second element (line or circle)
    798      * @param {Number} i Index of the intersection point that should be returned.
    799      * @param board Reference to the board.
    800      * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points.
    801      * Which point will be returned is determined by i.
    802      */
    803     meet: function(el1, el2, i, board) {
    804         var eps = JXG.Math.eps; //    var eps = 0.000001;
    805         if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { // line line
    806             return this.meetLineLine(el1, el2, i, board);
    807         } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { // circle line
    808             return this.meetLineCircle(el2, el1, i, board);
    809         } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { // line circle
    810             return this.meetLineCircle(el1, el2, i, board);
    811         } else {  // circle circle
    812             return this.meetCircleCircle(el1, el2, i, board);
    813         }
    814     },
    815
    816     /**
    817      * Intersection of two lines using the stdform.
    818      * @param {Array} l1 stdform of the first line
    819      * @param {Array} l2 stdform of the second line
    820      * @param {number} i unused
    821      * @param {JXG.Board} board Reference to the board.
    822      * @returns {JXG.Coords} Coordinates of the intersection point.
    823      */
    824     meetLineLine: function(l1, l2, i, board) {
    825         var s = JXG.Math.crossProduct(l1, l2);
    826         if (Math.abs(s[0]) > JXG.Math.eps) {
    827             s[1] /= s[0];
    828             s[2] /= s[0];
    829             s[0] = 1.0;
    830         }
    831         return new JXG.Coords(JXG.COORDS_BY_USER, s, board);
    832     },
    833
    834     /**
    835      * Intersection of line and circle using the stdform.
    836      * @param {Array} lin stdform of the line
    837      * @param {Array} circ stdform of the circle
    838      * @param {number} i number of the returned intersection point.
    839      *   i==0: use the positive square root,
    840      *   i==1: use the negative square root.
    841      * @param {JXG.Board} board Reference to a board.
    842      * @returns {JXG.Coords} Coordinates of the intersection point
    843      */
    844     meetLineCircle: function(lin, circ, i, board) {
    845         var a,b,c,d,n, A,B,C, k,t;
    846         if (circ[4] < JXG.Math.eps) { // Radius is zero, return center of circle
    847             if (Math.abs( JXG.Math.innerProduct([1,circ[6],circ[7]], lin, 3)) < JXG.Math.eps) {
    848                 return new JXG.Coords(JXG.COORDS_BY_USER, circ.slice(6, 8), board);
    849             } else {
    850                 return new JXG.Coords(JXG.COORDS_BY_USER, [NaN,NaN], board);
    851             }
    852         }
    853         c = circ[0];
    854         b = circ.slice(1, 3);
    855         a = circ[3];
    856         d = lin[0];
    857         n = lin.slice(1, 3);
    858
    859         // Line is normalized, therefore nn==1 and we can skip some operations:
    860         /*
    861          var nn = n[0]*n[0]+n[1]*n[1];
    862          A = a*nn;
    863          B = (b[0]*n[1]-b[1]*n[0])*nn;
    864          C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn;
    865          */
    866         A = a;
    867         B = (b[0] * n[1] - b[1] * n[0]);
    868         C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c;
    869
    870         k = B * B - 4 * A * C;
    871         if (k >= 0) {
    872             k = Math.sqrt(k);
    873             t = [(-B + k) / (2 * A),(-B - k) / (2 * A)];
    874             return ((i == 0)
    875                 ? new JXG.Coords(JXG.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0],-t[0] * n[0] - d * n[1]], board)
    876                 : new JXG.Coords(JXG.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0],-t[1] * n[0] - d * n[1]], board)
    877                 );
    878             /*
    879              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),
    880              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)
    881              */
    882         } else {
    883             return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
    884         }
    885         // Returns do not work with homogeneous coordinates, yet
    886     },
    887
    888     /**
    889      * Intersection of two circles using the stdform.
    890      * @param {Array} circ1 stdform of the first circle
    891      * @param {Array} circ2 stdform of the second circle
    892      * @param {number} i number of the returned intersection point.
    893      *   i==0: use the positive square root,
    894      *   i==1: use the negative square root.
    895      * @param {JXG.Board} board Reference to the board.
    896      * @returns {JXG.Coords} Coordinates of the intersection point
    897      */
    898     meetCircleCircle: function(circ1, circ2, i, board) {
    899         var radicalAxis;
    900         if (circ1[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle
    901             if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < JXG.Math.eps) {
    902                 return new JXG.Coords(JXG.COORDS_BY_USER, circ1.slice(6, 8), board);
    903             } else {
    904                 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
    905             }
    906         }
    907         if (circ2[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle
    908             if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < JXG.Math.eps) {
    909                 return new JXG.Coords(JXG.COORDS_BY_USER, circ2.slice(6, 8), board);
    910             } else {
    911                 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
    912             }
    913         }
    914         radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0],
    915             circ2[3] * circ1[1] - circ1[3] * circ2[1],
    916             circ2[3] * circ1[2] - circ1[3] * circ2[2],
    917             0,1,Infinity, Infinity, Infinity];
    918         radicalAxis = JXG.Math.normalize(radicalAxis);
    919         return this.meetLineCircle(radicalAxis, circ1, i, board);
    920         // Returns do not work with homogeneous coordinates, yet
    921     },
    922
    923     /**
    924      * Compute an intersection of the curves c1 and c2
    925      * with a generalized Newton method.
    926      * We want to find values t1, t2 such that
    927      * c1(t1) = c2(t2), i.e.
    928      * (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0).
    929      * We set
    930      * (e,f) := (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2))
    931      *
    932      * The Jacobian J is defined by
    933      * J = (a, b)
    934      *     (c, d)
    935      * where
    936      * a = c1_x'(t1)
    937      * b = -c2_x'(t2)
    938      * c = c1_y'(t1)
    939      * d = -c2_y'(t2)
    940      *
    941      * The inverse J^(-1) of J is equal to
    942      *  (d, -b)/
    943      *  (-c, a) / (ad-bc)
    944      *
    945      * Then, (t1new, t2new) := (t1,t2) - J^(-1)*(e,f).
    946      * If the function meetCurveCurve possesses the properties
    947      * t1memo and t2memo then these are taken as start values
    948      * for the Newton algorithm.
    949      * After stopping of the Newton algorithm the values of t1 and t2 are stored in
    950      * t1memo and t2memo.
    951      *
    952      * @param {JXG.Curve} c1 Curve, Line or Circle
    953      * @param {JXG.Curve} c2 Curve, Line or Circle
    954      * @param {Number} t1ini start value for t1
    955      * @param {Number} t2ini start value for t2
    956      * @param {JXG.Board} [board=c1.board] Reference to a board object.
    957      * @returns {JXG.Coords} intersection point
    958      */
    959     meetCurveCurve: function(c1, c2, t1ini, t2ini, board) {
    960         var count = 0,
    961             t1, t2,
    962             a, b, c, d, disc,
    963             e, f, F,
    964             D00, D01,
    965             D10, D11;
    966
    967         if (!JXG.exists(board))
    968             board = c1.board;
    969
    970         if (arguments.callee.t1memo) {
    971             t1 = arguments.callee.t1memo;
    972             t2 = arguments.callee.t2memo;
    973         } else {
    974             t1 = t1ini;
    975             t2 = t2ini;
    976         }
    977         /*
    978          if (t1>c1.maxX()) { t1 = c1.maxX(); }
    979          if (t1<c1.minX()) { t1 = c1.minX(); }
    980          if (t2>c2.maxX()) { t2 = c2.maxX(); }
    981          if (t2<c2.minX()) { t2 = c2.minX(); }
    982          */
    983         e = c1.X(t1) - c2.X(t2);
    984         f = c1.Y(t1) - c2.Y(t2);
    985         F = e * e + f * f;
    986
    987         D00 = c1.board.D(c1.X, c1);
    988         D01 = c2.board.D(c2.X, c2);
    989         D10 = c1.board.D(c1.Y, c1);
    990         D11 = c2.board.D(c2.Y, c2);
    991
    992         while (F > JXG.Math.eps && count < 10) {
    993             a = D00(t1);
    994             b = -D01(t2);
    995             c = D10(t1);
    996             d = -D11(t2);
    997             disc = a * d - b * c;
    998             t1 -= (d * e - b * f) / disc;
    999             t2 -= (a * f - c * e) / disc;
    1000             e = c1.X(t1) - c2.X(t2);
    1001             f = c1.Y(t1) - c2.Y(t2);
    1002             F = e * e + f * f;
    1003             count++;
    1004         }
    1005         //console.log(t1+' '+t2);
    1006
    1007         arguments.callee.t1memo = t1;
    1008         arguments.callee.t2memo = t2;
    1009
    1010         //return (new JXG.Coords(JXG.COORDS_BY_USER, [2,2], this.board));
    1011         if (Math.abs(t1) < Math.abs(t2)) {
    1012             return (new JXG.Coords(JXG.COORDS_BY_USER, [c1.X(t1),c1.Y(t1)], board));
    1013         } else {
    1014             return (new JXG.Coords(JXG.COORDS_BY_USER, [c2.X(t2),c2.Y(t2)], board));
    1015         }
    1016     },
    1017
    1018     /**
    1019      * order of input does not matter for el1 and el2.
    1020      * @param {JXG.Curve,JXG.Line} el1 Curve or Line
    1021      * @param {JXG.Curve,JXG.Line} el2 Curve or Line
    1022      * @param {?} nr
    1023      * @param {JXG.Board} [board=el1.board] Reference to a board object.
    1024      * @returns {JXG.Coords} Intersection point
    1025      */
    1026     meetCurveLine: function(el1, el2, nr, board) {
    1027         var t, t2, i, cu, li, func, z,
    1028             tnew, steps, delta, tstart, tend, cux, cuy;
    1029
    1030         if (!JXG.exists(board))
    1031             board = el1.board;
    1032
    1033         //for (i=0;i<arguments.length-1;i++) {
    1034         for (i = 0; i <= 1; i++) {
    1035             if (arguments[i].elementClass == JXG.OBJECT_CLASS_CURVE) {
    1036                 cu = arguments[i];
    1037             } else if (arguments[i].elementClass == JXG.OBJECT_CLASS_LINE) {
    1038                 li = arguments[i];
    1039             } else
    1040                 throw new Error("JSXGraph: Can't call meetCurveLine with parent class " + (arguments[i].elementClass) + ".");
    1041         }
    1042
    1043         func = function(t) {
    1044             return li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t);
    1045         };
    1046
    1047         if (arguments.callee.t1memo) {
    1048             tstart = arguments.callee.t1memo;
    1049             t = JXG.Math.Numerics.root(func, tstart);
    1050         } else {
    1051             tstart = cu.minX();
    1052             tend = cu.maxX();
    1053             t = JXG.Math.Numerics.root(func, [tstart,tend]);
    1054         }
    1055         arguments.callee.t1memo = t;
    1056         cux = cu.X(t);
    1057         cuy = cu.Y(t);
    1058
    1059         if (nr == 1) {
    1060             if (arguments.callee.t2memo) {
    1061                 tstart = arguments.callee.t2memo;
    1062                 t2 = JXG.Math.Numerics.root(func, tstart);
    1063             }
    1064             if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) {
    1065                 steps = 20;
    1066                 delta = (cu.maxX() - cu.minX()) / steps;
    1067                 tnew = cu.minX();
    1068                 for (i = 0; i < steps; i++) {
    1069                     t2 = JXG.Math.Numerics.root(func, [tnew,tnew + delta]);
    1070                     if (Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1) {
    1071                         break;
    1072                     }
    1073                     tnew += delta;
    1074                 }
    1075             }
    1076             t = t2;
    1077             arguments.callee.t2memo = t;
    1078         }
    1079
    1080         if (Math.abs(func(t)) > JXG.Math.eps) {
    1081             z = 0.0;
    1082         } else {
    1083             z = 1.0;
    1084         }
    1085
    1086         return (new JXG.Coords(JXG.COORDS_BY_USER, [z, cu.X(t),cu.Y(t)], board));
    1087     },
    1088
    1089
    1090
    1091     /****************************************/
    1092     /****           PROJECTIONS          ****/
    1093     /****************************************/
    1094
    1095     /**
    1096      * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the
    1097      * nearest one of the two intersection points of the line through the given point and the circles
    1098      * center.
    1099      * @param {JXG.Point} point Point to project.
    1100      * @param {JXG.Circle} circle Circle on that the point is projected.
    1101      * @param {JXG.Board} [board=point.board] Reference to the board
    1102      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
    1103      */
    1104     projectPointToCircle: function(point, circle, board) {
    1105         var dist = point.coords.distance(JXG.COORDS_BY_USER, circle.center.coords),
    1106             P = point.coords.usrCoords,
    1107             M = circle.center.coords.usrCoords,
    1108             x, y, factor;
    1109
    1110         if (!JXG.exists(board))
    1111             board = point.board;
    1112
    1113         if (Math.abs(dist) < JXG.Math.eps) {
    1114             dist = JXG.Math.eps;
    1115         }
    1116         factor = circle.Radius() / dist;
    1117         x = M[1] + factor * (P[1] - M[1]);
    1118         y = M[2] + factor * (P[2] - M[2]);
    1119
    1120         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
    1121     },
    1122
    1123     /**
    1124      * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the
    1125      * intersection point of the given line and its perpendicular through the given point.
    1126      * @param {JXG.Point} point Point to project.
    1127      * @param {JXG.Line} line Line on that the point is projected.
    1128      * @param {JXG.Board} [board=point.board] Reference to a board.
    1129      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line.
    1130      */
    1131     projectPointToLine: function(point, line, board) {
    1132         // Homogeneous version
    1133         var v = [0,line.stdform[1],line.stdform[2]];
    1134
    1135         if (!JXG.exists(board))
    1136             board = point.board;
    1137
    1138         v = JXG.Math.crossProduct(v, point.coords.usrCoords);
    1139
    1140         return this.meetLineLine(v, line.stdform, 0, board);
    1141     },
    1142
    1143     /**
    1144      * Calculates the coordinates of the projection of a given point on a given curve.
    1145      * Uses {@link #projectCoordsToCurve}.
    1146      * @param {JXG.Point} point Point to project.
    1147      * @param {JXG.Curve} curve Curve on that the point is projected.
    1148      * @param {JXG.Board} [board=point.board] Reference to a board.
    1149      * @see #projectCoordsToCurve
    1150      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph.
    1151      */
    1152     projectPointToCurve: function(point, curve, board) {
    1153         if (!JXG.exists(board))
    1154             board = point.board;
    1155
    1156         var x = point.X(),
    1157             y = point.Y(),
    1158             t = point.position || 0.0, //(curve.minX()+curve.maxX())*0.5,
    1159             result = this.projectCoordsToCurve(x, y, t, curve, board);
    1160
    1161         point.position = result[1];      // side effect !
    1162         return result[0];
    1163     },
    1164
    1165     /**
    1166      * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of
    1167      * function graphs this is the
    1168      * intersection point of the curve and the parallel to y-axis through the given point.
    1169      * @param {Number} x coordinate to project.
    1170      * @param {Number} y coordinate to project.
    1171      * @param {Number} t start value for newtons method
    1172      * @param {JXG.Curve} curve Curve on that the point is projected.
    1173      * @param {JXG.Board} [board=curve.board] Reference to a board.
    1174      * @see #projectPointToCurve
    1175      * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and
    1176      * the position on the curve.
    1177      */
    1178     projectCoordsToCurve: function(x, y, t, curve, board) {
    1179         var newCoords, x0, y0, x1, y1, den, i, mindist, dist, lbda, j,
    1180             infty = 1000000.0, minfunc, tnew, fnew, fold, delta, steps;
    1181
    1182         if (!JXG.exists(board))
    1183             board = curve.board;
    1184
    1185         if (curve.visProp.curvetype == 'parameter' || curve.visProp.curvetype == 'polar') {
    1186             // Function to minimize
    1187             minfunc = function(t) {
    1188                 var dx = x - curve.X(t),
    1189                     dy = y - curve.Y(t);
    1190                 return dx * dx + dy * dy;
    1191             };
    1192
    1193             fold = minfunc(t);
    1194             steps = 20;
    1195             delta = (curve.maxX() - curve.minX()) / steps;
    1196             tnew = curve.minX();
    1197             for (j = 0; j < steps; j++) {
    1198                 fnew = minfunc(tnew);
    1199                 if (fnew < fold) {
    1200                     t = tnew;
    1201                     fold = fnew;
    1202                 }
    1203                 tnew += delta;
    1204             }
    1205             t = JXG.Math.Numerics.root(JXG.Math.Numerics.D(minfunc), t);
    1206
    1207             if (t < curve.minX()) {
    1208                 t = curve.maxX() + t - curve.minX();
    1209             } // Cyclically
    1210             if (t > curve.maxX()) {
    1211                 t = curve.minX() + t - curve.maxX();
    1212             }
    1213             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [curve.X(t),curve.Y(t)], board);
    1214         } else if (curve.visProp.curvetype == 'plot') {
    1215             mindist = infty;
    1216             for (i = 0; i < curve.numberPoints; i++) {
    1217                 x0 = x - curve.X(i);
    1218                 y0 = y - curve.Y(i);
    1219                 dist = Math.sqrt(x0 * x0 + y0 * y0);
    1220                 if (dist < mindist) {
    1221                     mindist = dist;
    1222                     t = i;
    1223                 }
    1224                 if (i == curve.numberPoints - 1) {
    1225                     continue;
    1226                 }
    1227
    1228                 x1 = curve.X(i + 1) - curve.X(i);
    1229                 y1 = curve.Y(i + 1) - curve.Y(i);
    1230                 den = x1 * x1 + y1 * y1;
    1231                 if (den >= JXG.Math.eps) {
    1232                     lbda = (x0 * x1 + y0 * y1) / den;
    1233                     dist = Math.sqrt(x0 * x0 + y0 * y0 - lbda * (x0 * x1 + y0 * y1));
    1234                 } else {
    1235                     lbda = 0.0;
    1236                     dist = Math.sqrt(x0 * x0 + y0 * y0);
    1237                 }
    1238                 if (lbda >= 0.0 && lbda <= 1.0 && dist < mindist) {
    1239                     t = i + lbda;
    1240                     mindist = dist;
    1241                 }
    1242             }
    1243             i = Math.floor(t);
    1244             lbda = t - i;
    1245             if (i < curve.numberPoints - 1) {
    1246                 x = lbda * curve.X(i + 1) + (1.0 - lbda) * curve.X(i);
    1247                 y = lbda * curve.Y(i + 1) + (1.0 - lbda) * curve.Y(i);
    1248             } else {
    1249                 x = curve.X(i);
    1250                 y = curve.Y(i);
    1251             }
    1252             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
    1253         } else {             // functiongraph
    1254             t = x;
    1255             x = t; //curve.X(t);
    1256             y = curve.Y(t);
    1257             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
    1258         }
    1259         return [curve.updateTransform(newCoords), t];
    1260     },
    1261
    1262     /**
    1263      * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of
    1264      * one or more curves of curveType 'plot'. Uses {@link #projectPointToCurve}.
    1265      * @param {JXG.Point} point Point to project.
    1266      * @param {JXG.Turtle} turtle on that the point is projected.
    1267      * @param {JXG.Board} [board=point.board] Reference to a board.
    1268      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle.
    1269      */
    1270     projectPointToTurtle: function(point, turtle, board) {
    1271         var newCoords, t, x, y, i,
    1272             np = 0,
    1273             npmin = 0,
    1274             mindist = 1000000.0,
    1275             dist, el, minEl,
    1276             len = turtle.objects.length;
    1277
    1278         if (!JXG.exists(board))
    1279             board = point.board;
    1280
    1281         for (i = 0; i < len; i++) {  // run through all curves of this turtle
    1282             el = turtle.objects[i];
    1283             if (el.elementClass == JXG.OBJECT_CLASS_CURVE) {
    1284                 newCoords = this.projectPointToCurve(point, el);
    1285                 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords);
    1286                 if (dist < mindist) {
    1287                     x = newCoords.usrCoords[1];
    1288                     y = newCoords.usrCoords[2];
    1289                     t = point.position;
    1290                     mindist = dist;
    1291                     minEl = el;
    1292                     npmin = np;
    1293                 }
    1294                 np += el.numberPoints;
    1295             }
    1296         }
    1297         newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
    1298         point.position = t + npmin;
    1299         return minEl.updateTransform(newCoords);
    1300     },
    1301
    1302     /**
    1303      * Trivial projection of a point to another point.
    1304      * @param {JXG.Point} point Point to project (not used).
    1305      * @param {JXG.Point} dest Point on that the point is projected.
    1306      * @param {JXG.Board} [board=point.board] Reference to the board (not used).
    1307      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
    1308      */
    1309     projectPointToPoint: function(point, dest, board) {
    1310         return dest.coords;
    1311     }
    1312
    1313 });
    1314