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