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