1 /*
  2     Copyright 2008-2021
  3         Matthias Ehmann,
  4         Michael Gerhaeuser,
  5         Carsten Miller,
  6         Bianca Valentin,
  7         Alfred Wassermann,
  8         Andreas Walter,
  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          * Sort vertices counter clockwise starting with the first point.
500          *
501          * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays.
502          *
503          * @returns {Array}
504          */
505         sortVertices: function (p) {
506             var ll,
507                 ps = Expect.each(p, Expect.coordsArray),
508                 N = ps.length,
509                 lastPoint = null;
510 
511             // If the last point equals the first point, we take the last point out of the array.
512             // It may be that the several points at the end of the array are equal to the first point.
513             // The polygonal chain is been closed by JSXGraph, but this may also have been done by the user.
514             // Therefore, we use a while lopp to pop the last points.
515             while (ps[0][0] === ps[N - 1][0] && ps[0][1] === ps[N - 1][1] && ps[0][2] === ps[N - 1][2]) {
516                 lastPoint = ps.pop();
517                 N--;
518             }
519             // Find the point with the lowest y value
520             // for (i = 1; i < N; i++) {
521             //     if ((ps[i][2] < ps[0][2]) ||
522             //         // if the current and the lowest point have the same y value, pick the one with
523             //         // the lowest x value.
524             //         (Math.abs(ps[i][2] - ps[0][2]) < Mat.eps && ps[i][1] < ps[0][1])) {
525             //         console.log(i, 0);
526             //         ps = Type.swap(ps, i, 0);
527             //     }
528             // }
529 
530             ll = ps[0];
531             // Sort ps in increasing order of the angle between a point and the first point ll.
532             // If a point is equal to the first point ll, the angle is defined to be -Infinity.
533             // Otherwise, atan2 would return zero, which is a value which also attained by points
534             // on the same horizontal line.
535             ps.sort(function (a, b) {
536                 var rad1 = (a[2] === ll[2] && a[1] === ll[1]) ? -Infinity : Math.atan2(a[2] - ll[2], a[1] - ll[1]),
537                     rad2 = (b[2] === ll[2] && b[1] === ll[1]) ? -Infinity : Math.atan2(b[2] - ll[2], b[1] - ll[1]);
538 
539                 return rad1 - rad2;
540             });
541 
542             // If the last point has been taken out of the array, we put it in again.
543             if (lastPoint !== null) {
544                 ps.push(lastPoint);
545             }
546 
547             return ps;
548         },
549 
550         /**
551          * Signed triangle area of the three points given.
552          *
553          * @param {JXG.Point|JXG.Coords|Array} p1
554          * @param {JXG.Point|JXG.Coords|Array} p2
555          * @param {JXG.Point|JXG.Coords|Array} p3
556          *
557          * @returns {Number}
558          */
559         signedTriangle: function (p1, p2, p3) {
560             var A = Expect.coordsArray(p1),
561                 B = Expect.coordsArray(p2),
562                 C = Expect.coordsArray(p3);
563 
564             return 0.5 * ((B[1] - A[1]) * (C[2] - A[2]) - (B[2] - A[2]) * (C[1] - A[1]));
565         },
566 
567         /**
568          * Determine the signed area of a non-selfintersecting polygon.
569          * Surveyor's Formula
570          *
571          * @param {Array} p An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays.
572          * @param {Boolean} [sort=true]
573          *
574          * @returns {Number}
575          */
576         signedPolygon: function (p, sort) {
577             var i, N,
578                 A = 0,
579                 ps = Expect.each(p, Expect.coordsArray);
580 
581             if (sort === undefined) {
582                 sort = true;
583             }
584 
585             if (!sort) {
586                 ps = this.sortVertices(ps);
587             } else {
588                 // Make sure the polygon is closed. If it is already closed this won't change the sum because the last
589                 // summand will be 0.
590                 ps.unshift(ps[ps.length - 1]);
591             }
592 
593             N = ps.length;
594 
595             for (i = 1; i < N; i++) {
596                 A += ps[i - 1][1] * ps[i][2] - ps[i][1] * ps[i - 1][2];
597             }
598 
599             return 0.5 * A;
600         },
601 
602         /**
603          * Calculate the complex hull of a point cloud.
604          *
605          * @param {Array} points An array containing {@link JXG.Point}, {@link JXG.Coords}, and/or arrays.
606          *
607          * @returns {Array}
608          */
609         GrahamScan: function (points) {
610             var i,
611                 M = 1,
612                 ps = Expect.each(points, Expect.coordsArray),
613                 N = ps.length;
614 
615             ps = this.sortVertices(ps);
616             N = ps.length;
617 
618             for (i = 2; i < N; i++) {
619                 while (this.signedTriangle(ps[M - 1], ps[M], ps[i]) <= 0) {
620                     if (M > 1) {
621                         M -= 1;
622                     } else if (i === N - 1) {
623                         break;
624                     }
625                     i += 1;
626                 }
627 
628                 M += 1;
629                 ps = Type.swap(ps, M, i);
630             }
631 
632             return ps.slice(0, M);
633         },
634 
635         /**
636          * A line can be a segment, a straight, or a ray. So it is not always delimited by point1 and point2
637          * calcStraight determines the visual start point and end point of the line. A segment is only drawn
638          * from start to end point, a straight line is drawn until it meets the boards boundaries.
639          * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point.
640          * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and
641          * set by this method.
642          * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set
643          * by this method.
644          * @param {Number} margin Optional margin, to avoid the display of the small sides of lines.
645          * @returns null
646          * @see Line
647          * @see JXG.Line
648          */
649         calcStraight: function (el, point1, point2, margin) {
650             var takePoint1, takePoint2, intersection, intersect1, intersect2, straightFirst, straightLast,
651                 c, p1, p2;
652 
653             if (!Type.exists(margin)) {
654                 // Enlarge the drawable region slightly. This hides the small sides
655                 // of thick lines in most cases.
656                 margin = 10;
657             }
658 
659             straightFirst = Type.evaluate(el.visProp.straightfirst);
660             straightLast = Type.evaluate(el.visProp.straightlast);
661 
662             // If one of the point is an ideal point in homogeneous coordinates
663             // drawing of line segments or rays are not possible.
664             if (Math.abs(point1.scrCoords[0]) < Mat.eps) {
665                 straightFirst = true;
666             }
667             if (Math.abs(point2.scrCoords[0]) < Mat.eps) {
668                 straightLast = true;
669             }
670 
671             // Do nothing in case of line segments (inside or outside of the board)
672             if (!straightFirst && !straightLast) {
673                 return;
674             }
675 
676             // Compute the stdform of the line in screen coordinates.
677             c = [];
678             c[0] = el.stdform[0] -
679                 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX +
680                 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY;
681             c[1] =  el.stdform[1] / el.board.unitX;
682             c[2] = -el.stdform[2] / el.board.unitY;
683 
684             // p1=p2
685             if (isNaN(c[0] + c[1] + c[2])) {
686                 return;
687             }
688 
689             takePoint1 = false;
690             takePoint2 = false;
691 
692             // Line starts at point1 and point1 is inside the board
693             takePoint1 = !straightFirst &&
694                 Math.abs(point1.usrCoords[0]) >= Mat.eps &&
695                 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth &&
696                 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight;
697 
698             // Line ends at point2 and point2 is inside the board
699             takePoint2 = !straightLast &&
700                 Math.abs(point2.usrCoords[0]) >= Mat.eps &&
701                 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth &&
702                 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight;
703 
704             // Intersect the line with the four borders of the board.
705             intersection = this.meetLineBoard(c, el.board, margin);
706             intersect1 = intersection[0];
707             intersect2 = intersection[1];
708 
709             /**
710              * At this point we have four points:
711              * point1 and point2 are the first and the second defining point on the line,
712              * intersect1, intersect2 are the intersections of the line with border around the board.
713              */
714 
715             /*
716              * Here we handle rays where both defining points are outside of the board.
717              */
718             // If both points are outside and the complete ray is outside we do nothing
719             if (!takePoint1 && !takePoint2) {
720                 // Ray starting at point 1
721                 if (!straightFirst && straightLast &&
722                         !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) {
723                     return;
724                 }
725 
726                 // Ray starting at point 2
727                 if (straightFirst && !straightLast &&
728                         !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) {
729                     return;
730                 }
731             }
732 
733             /*
734              * If at least one of the defining points is outside of the board
735              * we take intersect1 or intersect2 as one of the end points
736              * The order is also important for arrows of axes
737              */
738             if (!takePoint1) {
739                 if (!takePoint2) {
740                     // Two border intersection points are used
741                     if (this.isSameDir(point1, point2, intersect1, intersect2)) {
742                         p1 = intersect1;
743                         p2 = intersect2;
744                     } else {
745                         p2 = intersect1;
746                         p1 = intersect2;
747                     }
748                 } else {
749                     // One border intersection points is used
750                     if (this.isSameDir(point1, point2, intersect1, intersect2)) {
751                         p1 = intersect1;
752                     } else {
753                         p1 = intersect2;
754                     }
755                 }
756             } else {
757                 if (!takePoint2) {
758                     // One border intersection points is used
759                     if (this.isSameDir(point1, point2, intersect1, intersect2)) {
760                         p2 = intersect2;
761                     } else {
762                         p2 = intersect1;
763                     }
764                 }
765             }
766 
767             if (p1) {
768                 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1));
769                 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords);
770             }
771 
772             if (p2) {
773                 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1));
774                 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords);
775             }
776         },
777 
778         /**
779          * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2.
780          *
781          * This method adjusts the line's delimiting points taking into account its nature, the viewport defined
782          * by the board.
783          *
784          * A segment is delimited by start and end point, a straight line or ray is delimited until it meets the
785          * boards boundaries. However, if the line has infinite ticks, it will be delimited by the projection of
786          * the boards vertices onto itself.
787          *
788          * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point.
789          * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and
790          * set by this method.
791          * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set
792          * by this method.
793          * @see Line
794          * @see JXG.Line
795          */
796         calcLineDelimitingPoints: function (el, point1, point2) {
797             var distP1P2, boundingBox, lineSlope,
798                 intersect1, intersect2, straightFirst, straightLast,
799                 c, p1, p2,
800                 takePoint1 = false,
801                 takePoint2 = false;
802 
803             straightFirst = Type.evaluate(el.visProp.straightfirst);
804             straightLast = Type.evaluate(el.visProp.straightlast);
805 
806             // If one of the point is an ideal point in homogeneous coordinates
807             // drawing of line segments or rays are not possible.
808             if (Math.abs(point1.scrCoords[0]) < Mat.eps) {
809                 straightFirst = true;
810             }
811             if (Math.abs(point2.scrCoords[0]) < Mat.eps) {
812                 straightLast = true;
813             }
814 
815             // Compute the stdform of the line in screen coordinates.
816             c = [];
817             c[0] = el.stdform[0] -
818                 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX +
819                 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY;
820             c[1] =  el.stdform[1] / el.board.unitX;
821             c[2] = -el.stdform[2] / el.board.unitY;
822 
823             // p1=p2
824             if (isNaN(c[0] + c[1] + c[2])) {
825                 return;
826             }
827 
828             takePoint1 = !straightFirst;
829             takePoint2 = !straightLast;
830             // Intersect the board vertices on the line to establish the available visual space for the infinite ticks
831             // Based on the slope of the line we can optimise and only project the two outer vertices
832 
833             // boundingBox = [x1, y1, x2, y2] upper left, lower right vertices
834             boundingBox = el.board.getBoundingBox();
835             lineSlope = el.getSlope();
836             if (lineSlope >= 0) {
837                 // project vertices (x2,y1) (x1, y2)
838                 intersect1 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[2], boundingBox[1]] } }, el, el.board);
839                 intersect2 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[0], boundingBox[3]] } }, el, el.board);
840             } else {
841                 // project vertices (x1, y1) (x2, y2)
842                 intersect1 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[0], boundingBox[1]] } }, el, el.board);
843                 intersect2 = this.projectPointToLine({ coords: { usrCoords: [1, boundingBox[2], boundingBox[3]] } }, el, el.board);
844             }
845 
846             /**
847              * we have four points:
848              * point1 and point2 are the first and the second defining point on the line,
849              * intersect1, intersect2 are the intersections of the line with border around the board.
850              */
851 
852             /*
853              * Here we handle rays/segments where both defining points are outside of the board.
854              */
855             if (!takePoint1 && !takePoint2) {
856                 // Segment, if segment does not cross the board, do nothing
857                 if (!straightFirst && !straightLast) {
858                     distP1P2 = point1.distance(Const.COORDS_BY_USER, point2);
859                     // if  intersect1 not between point1 and point2
860                     if (Math.abs(point1.distance(Const.COORDS_BY_USER, intersect1) +
861                             intersect1.distance(Const.COORDS_BY_USER, point2) - distP1P2) > Mat.eps) {
862                         return;
863                     }
864                     // if insersect2 not between point1 and point2
865                     if (Math.abs(point1.distance(Const.COORDS_BY_USER, intersect2) +
866                             intersect2.distance(Const.COORDS_BY_USER, point2) - distP1P2) > Mat.eps) {
867                         return;
868                     }
869                 }
870 
871                 // If both points are outside and the complete ray is outside we do nothing
872                 // Ray starting at point 1
873                 if (!straightFirst && straightLast &&
874                         !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) {
875                     return;
876                 }
877 
878                 // Ray starting at point 2
879                 if (straightFirst && !straightLast &&
880                         !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) {
881                     return;
882                 }
883             }
884 
885             /*
886              * If at least one of the defining points is outside of the board
887              * we take intersect1 or intersect2 as one of the end points
888              * The order is also important for arrows of axes
889              */
890             if (!takePoint1) {
891                 if (!takePoint2) {
892                     // Two border intersection points are used
893                     if (this.isSameDir(point1, point2, intersect1, intersect2)) {
894                         p1 = intersect1;
895                         p2 = intersect2;
896                     } else {
897                         p2 = intersect1;
898                         p1 = intersect2;
899                     }
900                 } else {
901                     // One border intersection points is used
902                     if (this.isSameDir(point1, point2, intersect1, intersect2)) {
903                         p1 = intersect1;
904                     } else {
905                         p1 = intersect2;
906                     }
907                 }
908             } else {
909                 if (!takePoint2) {
910                     // One border intersection points is used
911                     if (this.isSameDir(point1, point2, intersect1, intersect2)) {
912                         p2 = intersect2;
913                     } else {
914                         p2 = intersect1;
915                     }
916                 }
917             }
918 
919             if (p1) {
920                 //point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords.slice(1));
921                 point1.setCoordinates(Const.COORDS_BY_USER, p1.usrCoords);
922             }
923 
924             if (p2) {
925                 //point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords.slice(1));
926                 point2.setCoordinates(Const.COORDS_BY_USER, p2.usrCoords);
927             }
928         },
929 
930         /**
931          * Calculates the visProp.position corresponding to a given angle.
932          * @param {number} angle angle in radians. Must be in range (-2pi,2pi).
933          */
934         calcLabelQuadrant: function(angle) {
935             var q;
936             if (angle < 0) {
937                 angle += 2*Math.PI;
938             }
939             q = Math.floor((angle+Math.PI/8)/(Math.PI/4))%8;
940             return ['rt','urt','top','ulft','lft','llft','lrt'][q];
941         },
942 
943         /**
944          * The vectors <tt>p2-p1</tt> and <tt>i2-i1</tt> are supposed to be collinear. If their cosine is positive
945          * they point into the same direction otherwise they point in opposite direction.
946          * @param {JXG.Coords} p1
947          * @param {JXG.Coords} p2
948          * @param {JXG.Coords} i1
949          * @param {JXG.Coords} i2
950          * @returns {Boolean} True, if <tt>p2-p1</tt> and <tt>i2-i1</tt> point into the same direction
951          */
952         isSameDir: function (p1, p2, i1, i2) {
953             var dpx = p2.usrCoords[1] - p1.usrCoords[1],
954                 dpy = p2.usrCoords[2] - p1.usrCoords[2],
955                 dix = i2.usrCoords[1] - i1.usrCoords[1],
956                 diy = i2.usrCoords[2] - i1.usrCoords[2];
957 
958             if (Math.abs(p2.usrCoords[0]) < Mat.eps) {
959                 dpx = p2.usrCoords[1];
960                 dpy = p2.usrCoords[2];
961             }
962 
963             if (Math.abs(p1.usrCoords[0]) < Mat.eps) {
964                 dpx = -p1.usrCoords[1];
965                 dpy = -p1.usrCoords[2];
966             }
967 
968             return dpx * dix + dpy * diy >= 0;
969         },
970 
971         /**
972          * If you're looking from point "start" towards point "s" and you can see the point "p", return true.
973          * Otherwise return false.
974          * @param {JXG.Coords} start The point you're standing on.
975          * @param {JXG.Coords} p The point in which direction you're looking.
976          * @param {JXG.Coords} s The point that should be visible.
977          * @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.
978          */
979         isSameDirection: function (start, p, s) {
980             var dx, dy, sx, sy, r = false;
981 
982             dx = p.usrCoords[1] - start.usrCoords[1];
983             dy = p.usrCoords[2] - start.usrCoords[2];
984 
985             sx = s.usrCoords[1] - start.usrCoords[1];
986             sy = s.usrCoords[2] - start.usrCoords[2];
987 
988             if (Math.abs(dx) < Mat.eps) {
989                 dx = 0;
990             }
991 
992             if (Math.abs(dy) < Mat.eps) {
993                 dy = 0;
994             }
995 
996             if (Math.abs(sx) < Mat.eps) {
997                 sx = 0;
998             }
999 
1000             if (Math.abs(sy) < Mat.eps) {
1001                 sy = 0;
1002             }
1003 
1004             if (dx >= 0 && sx >= 0) {
1005                 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0);
1006             } else if (dx <= 0 && sx <= 0) {
1007                 r = (dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0);
1008             }
1009 
1010             return r;
1011         },
1012 
1013         /****************************************/
1014         /****          INTERSECTIONS         ****/
1015         /****************************************/
1016 
1017         /**
1018          * Generate the function which computes the coordinates of the intersection point.
1019          * Primarily used in {@link JXG.Point#createIntersectionPoint}.
1020          * @param {JXG.Board} board object
1021          * @param {JXG.Line,JXG.Circle_JXG.Line,JXG.Circle_Number} el1,el2,i The result will be a intersection point on el1 and el2.
1022          * i determines the intersection point if two points are available: <ul>
1023          *   <li>i==0: use the positive square root,</li>
1024          *   <li>i==1: use the negative square root.</li></ul>
1025          * See further {@link JXG.Point#createIntersectionPoint}.
1026          * @param {Boolean} alwaysintersect. Flag that determines if segements and arc can have an outer intersection point
1027          * on their defining line or circle.
1028          * @returns {Function} Function returning a {@link JXG.Coords} object that determines
1029          * the intersection point.
1030          */
1031         intersectionFunction: function (board, el1, el2, i, j, alwaysintersect) {
1032             var func, that = this;
1033 
1034             if (el1.elementClass === Const.OBJECT_CLASS_CURVE &&
1035                     el2.elementClass === Const.OBJECT_CLASS_CURVE) {
1036                 // curve - curve
1037                 /** @ignore */
1038                 func = function () {
1039                     return that.meetCurveCurve(el1, el2, i, j, el1.board);
1040                 };
1041 
1042             } else if ((el1.elementClass === Const.OBJECT_CLASS_CURVE && el2.elementClass === Const.OBJECT_CLASS_LINE) ||
1043                     (el2.elementClass === Const.OBJECT_CLASS_CURVE && el1.elementClass === Const.OBJECT_CLASS_LINE)) {
1044                 // curve - line (this includes intersections between conic sections and lines
1045                 /** @ignore */
1046                 func = function () {
1047                     return that.meetCurveLine(el1, el2, i, el1.board, alwaysintersect);
1048                 };
1049 
1050             } else if (el1.elementClass === Const.OBJECT_CLASS_LINE && el2.elementClass === Const.OBJECT_CLASS_LINE) {
1051                 // line - line, lines may also be segments.
1052                 /** @ignore */
1053                 func = function () {
1054                     var res, c,
1055                         first1 = Type.evaluate(el1.visProp.straightfirst),
1056                         last1 = Type.evaluate(el1.visProp.straightlast),
1057                         first2 = Type.evaluate(el2.visProp.straightfirst),
1058                         last2 = Type.evaluate(el2.visProp.straightlast);
1059 
1060                     /**
1061                      * If one of the lines is a segment or ray and
1062                      * the the intersection point should disappear if outside
1063                      * of the segment or ray we call
1064                      * meetSegmentSegment
1065                      */
1066                     if (!Type.evaluate(alwaysintersect) && (!first1 || !last1 || !first2 || !last2)) {
1067                         res = that.meetSegmentSegment(
1068                             el1.point1.coords.usrCoords,
1069                             el1.point2.coords.usrCoords,
1070                             el2.point1.coords.usrCoords,
1071                             el2.point2.coords.usrCoords,
1072                             el1.board
1073                         );
1074 
1075                         if ((!first1 && res[1] < 0) || (!last1 && res[1] > 1) ||
1076                                 (!first2 && res[2] < 0) || (!last2 && res[2] > 1)) {
1077                             // Non-existent
1078                             c = [0, NaN, NaN];
1079                         } else {
1080                             c = res[0];
1081                         }
1082 
1083                         return (new Coords(Const.COORDS_BY_USER, c, el1.board));
1084                     }
1085 
1086                     return that.meet(el1.stdform, el2.stdform, i, el1.board);
1087                 };
1088             } else {
1089                 // All other combinations of circles and lines
1090                 /** @ignore */
1091                 func = function () {
1092                     return that.meet(el1.stdform, el2.stdform, i, el1.board);
1093                 };
1094             }
1095 
1096             return func;
1097         },
1098 
1099         /**
1100          * Computes the intersection of a pair of lines, circles or both.
1101          * It uses the internal data array stdform of these elements.
1102          * @param {Array} el1 stdform of the first element (line or circle)
1103          * @param {Array} el2 stdform of the second element (line or circle)
1104          * @param {Number} i Index of the intersection point that should be returned.
1105          * @param board Reference to the board.
1106          * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points.
1107          * Which point will be returned is determined by i.
1108          */
1109         meet: function (el1, el2, i, board) {
1110             var result,
1111                 eps = Mat.eps;
1112 
1113             // line line
1114             if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) {
1115                 result = this.meetLineLine(el1, el2, i, board);
1116             // circle line
1117             } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) {
1118                 result = this.meetLineCircle(el2, el1, i, board);
1119             // line circle
1120             } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) {
1121                 result = this.meetLineCircle(el1, el2, i, board);
1122             // circle circle
1123             } else {
1124                 result = this.meetCircleCircle(el1, el2, i, board);
1125             }
1126 
1127             return result;
1128         },
1129 
1130         /**
1131          * Intersection of the line with the board
1132          * @param  {Array}     line   stdform of the line in screen coordinates
1133          * @param  {JXG.Board} board  reference to a board.
1134          * @param  {Number}    margin optional margin, to avoid the display of the small sides of lines.
1135          * @returns {Array}            [intersection coords 1, intersection coords 2]
1136          */
1137         meetLineBoard: function (line, board, margin) {
1138              // Intersect the line with the four borders of the board.
1139             var s = [], intersect1, intersect2, i, j;
1140 
1141             if (!Type.exists(margin)) {
1142                 margin = 0;
1143             }
1144 
1145             // top
1146             s[0] = Mat.crossProduct(line, [margin, 0, 1]);
1147             // left
1148             s[1] = Mat.crossProduct(line, [margin, 1, 0]);
1149             // bottom
1150             s[2] = Mat.crossProduct(line, [-margin - board.canvasHeight, 0, 1]);
1151             // right
1152             s[3] = Mat.crossProduct(line, [-margin - board.canvasWidth, 1, 0]);
1153 
1154             // Normalize the intersections
1155             for (i = 0; i < 4; i++) {
1156                 if (Math.abs(s[i][0]) > Mat.eps) {
1157                     for (j = 2; j > 0; j--) {
1158                         s[i][j] /= s[i][0];
1159                     }
1160                     s[i][0] = 1.0;
1161                 }
1162             }
1163 
1164             // line is parallel to "left", take "top" and "bottom"
1165             if (Math.abs(s[1][0]) < Mat.eps) {
1166                 intersect1 = s[0];                          // top
1167                 intersect2 = s[2];                          // bottom
1168             // line is parallel to "top", take "left" and "right"
1169             } else if (Math.abs(s[0][0]) < Mat.eps) {
1170                 intersect1 = s[1];                          // left
1171                 intersect2 = s[3];                          // right
1172             // left intersection out of board (above)
1173             } else if (s[1][2] < 0) {
1174                 intersect1 = s[0];                          // top
1175 
1176                 // right intersection out of board (below)
1177                 if (s[3][2] > board.canvasHeight) {
1178                     intersect2 = s[2];                      // bottom
1179                 } else {
1180                     intersect2 = s[3];                      // right
1181                 }
1182             // left intersection out of board (below)
1183             } else if (s[1][2] > board.canvasHeight) {
1184                 intersect1 = s[2];                          // bottom
1185 
1186                 // right intersection out of board (above)
1187                 if (s[3][2] < 0) {
1188                     intersect2 = s[0];                      // top
1189                 } else {
1190                     intersect2 = s[3];                      // right
1191                 }
1192             } else {
1193                 intersect1 = s[1];                          // left
1194 
1195                 // right intersection out of board (above)
1196                 if (s[3][2] < 0) {
1197                     intersect2 = s[0];                      // top
1198                 // right intersection out of board (below)
1199                 } else if (s[3][2] > board.canvasHeight) {
1200                     intersect2 = s[2];                      // bottom
1201                 } else {
1202                     intersect2 = s[3];                      // right
1203                 }
1204             }
1205 
1206             intersect1 = new Coords(Const.COORDS_BY_SCREEN, intersect1.slice(1), board);
1207             intersect2 = new Coords(Const.COORDS_BY_SCREEN, intersect2.slice(1), board);
1208             return [intersect1, intersect2];
1209         },
1210 
1211         /**
1212          * Intersection of two lines.
1213          * @param {Array} l1 stdform of the first line
1214          * @param {Array} l2 stdform of the second line
1215          * @param {number} i unused
1216          * @param {JXG.Board} board Reference to the board.
1217          * @returns {JXG.Coords} Coordinates of the intersection point.
1218          */
1219         meetLineLine: function (l1, l2, i, board) {
1220             /*
1221             var s = Mat.crossProduct(l1, l2);
1222 
1223             if (Math.abs(s[0]) > Mat.eps) {
1224                 s[1] /= s[0];
1225                 s[2] /= s[0];
1226                 s[0] = 1.0;
1227             }
1228             */
1229             var s = isNaN(l1[5] + l2[5]) ? [0, 0, 0] : Mat.crossProduct(l1, l2);
1230             return new Coords(Const.COORDS_BY_USER, s, board);
1231         },
1232 
1233         /**
1234          * Intersection of line and circle.
1235          * @param {Array} lin stdform of the line
1236          * @param {Array} circ stdform of the circle
1237          * @param {number} i number of the returned intersection point.
1238          *   i==0: use the positive square root,
1239          *   i==1: use the negative square root.
1240          * @param {JXG.Board} board Reference to a board.
1241          * @returns {JXG.Coords} Coordinates of the intersection point
1242          */
1243         meetLineCircle: function (lin, circ, i, board) {
1244             var a, b, c, d, n,
1245                 A, B, C, k, t;
1246 
1247             // Radius is zero, return center of circle
1248             if (circ[4] < Mat.eps) {
1249                 if (Math.abs(Mat.innerProduct([1, circ[6], circ[7]], lin, 3)) < Mat.eps) {
1250                     return new Coords(Const.COORDS_BY_USER, circ.slice(6, 8), board);
1251                 }
1252 
1253                 return new Coords(Const.COORDS_BY_USER, [NaN, NaN], board);
1254             }
1255 
1256             c = circ[0];
1257             b = circ.slice(1, 3);
1258             a = circ[3];
1259             d = lin[0];
1260             n = lin.slice(1, 3);
1261 
1262             // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations:
1263             /*
1264              var nn = n[0]*n[0]+n[1]*n[1];
1265              A = a*nn;
1266              B = (b[0]*n[1]-b[1]*n[0])*nn;
1267              C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn;
1268              */
1269             A = a;
1270             B = (b[0] * n[1] - b[1] * n[0]);
1271             C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c;
1272 
1273             k = B * B - 4 * A * C;
1274             if (k > -Mat.eps * Mat.eps) {
1275                 k = Math.sqrt(Math.abs(k));
1276                 t = [(-B + k) / (2 * A), (-B - k) / (2 * A)];
1277 
1278                 return ((i === 0) ?
1279                         new Coords(Const.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0], -t[0] * n[0] - d * n[1]], board) :
1280                         new Coords(Const.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0], -t[1] * n[0] - d * n[1]], board)
1281                     );
1282             }
1283 
1284             return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board);
1285         },
1286 
1287         /**
1288          * Intersection of two circles.
1289          * @param {Array} circ1 stdform of the first circle
1290          * @param {Array} circ2 stdform of the second circle
1291          * @param {number} i number of the returned intersection point.
1292          *   i==0: use the positive square root,
1293          *   i==1: use the negative square root.
1294          * @param {JXG.Board} board Reference to the board.
1295          * @returns {JXG.Coords} Coordinates of the intersection point
1296          */
1297         meetCircleCircle: function (circ1, circ2, i, board) {
1298             var radicalAxis;
1299 
1300             // Radius is zero, return center of circle, if on other circle
1301             if (circ1[4] < Mat.eps) {
1302                 if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < Mat.eps) {
1303                     return new Coords(Const.COORDS_BY_USER, circ1.slice(6, 8), board);
1304                 }
1305 
1306                 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board);
1307             }
1308 
1309             // Radius is zero, return center of circle, if on other circle
1310             if (circ2[4] < Mat.eps) {
1311                 if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < Mat.eps) {
1312                     return new Coords(Const.COORDS_BY_USER, circ2.slice(6, 8), board);
1313                 }
1314 
1315                 return new Coords(Const.COORDS_BY_USER, [0, 0, 0], board);
1316             }
1317 
1318             radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0],
1319                 circ2[3] * circ1[1] - circ1[3] * circ2[1],
1320                 circ2[3] * circ1[2] - circ1[3] * circ2[2],
1321                 0, 1, Infinity, Infinity, Infinity];
1322             radicalAxis = Mat.normalize(radicalAxis);
1323 
1324             return this.meetLineCircle(radicalAxis, circ1, i, board);
1325         },
1326 
1327         /**
1328          * Compute an intersection of the curves c1 and c2.
1329          * We want to find values t1, t2 such that
1330          * c1(t1) = c2(t2), i.e. (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0).
1331          *
1332          * Methods: segment-wise intersections (default) or generalized Newton method.
1333          * @param {JXG.Curve} c1 Curve, Line or Circle
1334          * @param {JXG.Curve} c2 Curve, Line or Circle
1335          * @param {Number} nr the nr-th intersection point will be returned.
1336          * @param {Number} t2ini not longer used.
1337          * @param {JXG.Board} [board=c1.board] Reference to a board object.
1338          * @param {String} [method='segment'] Intersection method, possible values are 'newton' and 'segment'.
1339          * @returns {JXG.Coords} intersection point
1340          */
1341         meetCurveCurve: function (c1, c2, nr, t2ini, board, method) {
1342             var co;
1343 
1344             if (Type.exists(method) && method === 'newton') {
1345                 co = Numerics.generalizedNewton(c1, c2, nr, t2ini);
1346             } else {
1347                 if (c1.bezierDegree === 3 && c2.bezierDegree === 3) {
1348                     co = this.meetBezierCurveRedBlueSegments(c1, c2, nr);
1349                 } else {
1350                     co = this.meetCurveRedBlueSegments(c1, c2, nr);
1351                 }
1352             }
1353 
1354             return (new Coords(Const.COORDS_BY_USER, co, board));
1355         },
1356 
1357         /**
1358          * Intersection of curve with line,
1359          * Order of input does not matter for el1 and el2.
1360          * From version 0.99.7 on this method calls
1361          * {@link JXG.Math.Geometry.meetCurveLineDiscrete}.
1362          * If higher precision is needed, {@link JXG.Math.Geometry.meetCurveLineContinuous}
1363          * has to be used.
1364          *
1365          * @param {JXG.Curve,JXG.Line} el1 Curve or Line
1366          * @param {JXG.Curve,JXG.Line} el2 Curve or Line
1367          * @param {Number} nr the nr-th intersection point will be returned.
1368          * @param {JXG.Board} [board=el1.board] Reference to a board object.
1369          * @param {Boolean} alwaysIntersect If false just the segment between the two defining points are tested for intersection
1370          * @returns {JXG.Coords} Intersection point. In case no intersection point is detected,
1371          * the ideal point [0,1,0] is returned.
1372          */
1373         meetCurveLine: function (el1, el2, nr, board, alwaysIntersect) {
1374             var v = [0, NaN, NaN], cu, li;
1375 
1376             if (!Type.exists(board)) {
1377                 board = el1.board;
1378             }
1379 
1380             if (el1.elementClass === Const.OBJECT_CLASS_CURVE) {
1381                 cu = el1;
1382                 li = el2;
1383             } else {
1384                 cu = el2;
1385                 li = el1;
1386             }
1387 
1388             // if (Type.evaluate(cu.visProp.curvetype) === 'plot') {
1389                 v = this.meetCurveLineDiscrete(cu, li, nr, board, !alwaysIntersect);
1390             // } else {
1391             //     v = this.meetCurveLineContinuous(cu, li, nr, board);
1392             // }
1393 
1394             return v;
1395         },
1396 
1397         /**
1398          * Intersection of line and curve, continuous case.
1399          * Finds the nr-the intersection point
1400          * Uses {@link JXG.Math.Geometry.meetCurveLineDiscrete} as a first approximation.
1401          * A more exact solution is then found with {@link JXG.Math.Numerics.root}.
1402          *
1403          * @param {JXG.Curve} cu Curve
1404          * @param {JXG.Line} li Line
1405          * @param {Number} nr Will return the nr-th intersection point.
1406          * @param {JXG.Board} board
1407          * @returns {JXG.Coords} Coords object containing the intersection.
1408          */
1409         meetCurveLineContinuous: function (cu, li, nr, board, testSegment) {
1410             var t, func0, func1, v, x, y, z,
1411                 eps = Mat.eps,
1412                 epsLow = Mat.eps,
1413                 steps, delta, tnew, i,
1414                 tmin, fmin, ft;
1415 
1416             v = this.meetCurveLineDiscrete(cu, li, nr, board, testSegment);
1417             x = v.usrCoords[1];
1418             y = v.usrCoords[2];
1419 
1420             func0 = function (t) {
1421                 var c1, c2;
1422 
1423                 if (t > cu.maxX() || t < cu.minX()) {
1424                     return Infinity;
1425                 }
1426                 c1 = x - cu.X(t);
1427                 c2 = y - cu.Y(t);
1428                 return c1 * c1 + c2 * c2;
1429             };
1430 
1431             func1 = function (t) {
1432                 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t);
1433                 return v * v;
1434             };
1435 
1436             // Find t
1437             steps = 50;
1438             delta = (cu.maxX() - cu.minX()) / steps;
1439             tnew = cu.minX();
1440 
1441             fmin = 0.0001; //eps;
1442             tmin = NaN;
1443             for (i = 0; i < steps; i++) {
1444                 t = Numerics.root(func0, [Math.max(tnew, cu.minX()), Math.min(tnew + delta, cu.maxX())]);
1445                 ft = Math.abs(func0(t));
1446                 if (ft <= fmin) {
1447                     fmin = ft;
1448                     tmin = t;
1449                     if (fmin < eps) {
1450                         break;
1451                     }
1452                 }
1453 
1454                 tnew += delta;
1455             }
1456             t = tmin;
1457             // Compute "exact" t
1458             t = Numerics.root(func1, [Math.max(t - delta, cu.minX()), Math.min(t + delta, cu.maxX())]);
1459 
1460             ft = func1(t);
1461             // Is the point on the line?
1462             if (isNaN(ft) || Math.abs(ft) > epsLow) {
1463                 z = 0.0; //NaN;
1464             } else {
1465                 z = 1.0;
1466             }
1467 
1468             return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board));
1469         },
1470 
1471         /**
1472          * Intersection of line and curve, continuous case.
1473          * Segments are treated as lines. Finding the nr-the intersection point
1474          * works for nr=0,1 only.
1475          *
1476          * @private
1477          * @deprecated
1478          * @param {JXG.Curve} cu Curve
1479          * @param {JXG.Line} li Line
1480          * @param {Number} nr Will return the nr-th intersection point.
1481          * @param {JXG.Board} board
1482          *
1483          * BUG: does not respect cu.minX() and cu.maxX()
1484          */
1485         meetCurveLineContinuousOld: function (cu, li, nr, board) {
1486             var t, t2, i, func, z,
1487                 tnew, steps, delta, tstart, tend, cux, cuy,
1488                 eps = Mat.eps * 10;
1489 
1490             JXG.deprecated('Geometry.meetCurveLineContinuousOld()', 'Geometry.meetCurveLineContinuous()');
1491             func = function (t) {
1492                 var v = li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t);
1493                 return v * v;
1494             };
1495 
1496             // Find some intersection point
1497             if (this.meetCurveLineContinuous.t1memo) {
1498                 tstart = this.meetCurveLineContinuous.t1memo;
1499                 t = Numerics.root(func, tstart);
1500             } else {
1501                 tstart = cu.minX();
1502                 tend = cu.maxX();
1503                 t = Numerics.root(func, [tstart, tend]);
1504             }
1505 
1506             this.meetCurveLineContinuous.t1memo = t;
1507             cux = cu.X(t);
1508             cuy = cu.Y(t);
1509 
1510             // Find second intersection point
1511             if (nr === 1) {
1512                 if (this.meetCurveLineContinuous.t2memo) {
1513                     tstart = this.meetCurveLineContinuous.t2memo;
1514                 }
1515                 t2 = Numerics.root(func, tstart);
1516 
1517                 if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) {
1518                     steps = 20;
1519                     delta = (cu.maxX() - cu.minX()) / steps;
1520                     tnew = cu.minX();
1521 
1522                     for (i = 0; i < steps; i++) {
1523                         t2 = Numerics.root(func, [tnew, tnew + delta]);
1524 
1525                         if (Math.abs(func(t2)) <= eps && Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1) {
1526                             break;
1527                         }
1528 
1529                         tnew += delta;
1530                     }
1531                 }
1532                 t = t2;
1533                 this.meetCurveLineContinuous.t2memo = t;
1534             }
1535 
1536             // Is the point on the line?
1537             if (Math.abs(func(t)) > eps) {
1538                 z = NaN;
1539             } else {
1540                 z = 1.0;
1541             }
1542 
1543             return (new Coords(Const.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board));
1544         },
1545 
1546         /**
1547          * Intersection of line and curve, discrete case.
1548          * Segments are treated as lines.
1549          * Finding the nr-th intersection point should work for all nr.
1550          * @param {JXG.Curve} cu
1551          * @param {JXG.Line} li
1552          * @param {Number} nr
1553          * @param {JXG.Board} board
1554          * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the
1555          * line defined by the segment
1556          *
1557          * @returns {JXG.Coords} Intersection point. In case no intersection point is detected,
1558          * the ideal point [0,1,0] is returned.
1559          */
1560         meetCurveLineDiscrete: function (cu, li, nr, board, testSegment) {
1561             var i, j,
1562                 p1, p2, p, q,
1563                 lip1 = li.point1.coords.usrCoords,
1564                 lip2 = li.point2.coords.usrCoords,
1565                 d, res,
1566                 cnt = 0,
1567                 len = cu.numberPoints,
1568                 ev_sf = Type.evaluate(li.visProp.straightfirst),
1569                 ev_sl = Type.evaluate(li.visProp.straightlast);
1570 
1571             // In case, no intersection will be found we will take this
1572             q = new Coords(Const.COORDS_BY_USER, [0, NaN, NaN], board);
1573 
1574             if (lip1[0] === 0.0) {
1575                 lip1 = [1, lip2[1] + li.stdform[2], lip2[2] - li.stdform[1]];
1576             } else if (lip2[0] === 0.0) {
1577                 lip2 = [1, lip1[1] + li.stdform[2], lip1[2] - li.stdform[1]];
1578             }
1579 
1580             p2 = cu.points[0].usrCoords;
1581             for (i = 1; i < len; i++) {
1582                 p1 = p2.slice(0);
1583                 p2 = cu.points[i].usrCoords;
1584                 d = this.distance(p1, p2);
1585 
1586                 // The defining points are not identical
1587                 if (d > Mat.eps) {
1588                     if (cu.bezierDegree === 3) {
1589                         res = this.meetBeziersegmentBeziersegment([
1590                             cu.points[i - 1].usrCoords.slice(1),
1591                             cu.points[i].usrCoords.slice(1),
1592                             cu.points[i + 1].usrCoords.slice(1),
1593                             cu.points[i + 2].usrCoords.slice(1)
1594                         ], [
1595                             lip1.slice(1),
1596                             lip2.slice(1)
1597                         ], testSegment);
1598 
1599                         i += 2;
1600                     } else {
1601                         res = [this.meetSegmentSegment(p1, p2, lip1, lip2)];
1602                     }
1603 
1604                     for (j = 0; j < res.length; j++) {
1605                         p = res[j];
1606                         if (0 <= p[1] && p[1] <= 1) {
1607                             if (cnt === nr) {
1608                                 /**
1609                                 * If the intersection point is not part of the segment,
1610                                 * this intersection point is set to non-existent.
1611                                 * This prevents jumping of the intersection points.
1612                                 * But it may be discussed if it is the desired behavior.
1613                                 */
1614                                 if (testSegment &&
1615                                         ((!ev_sf && p[2] < 0) || (!ev_sl && p[2] > 1))) {
1616                                     return q;  // break;
1617                                 }
1618 
1619                                 q = new Coords(Const.COORDS_BY_USER, p[0], board);
1620                                 return q;      // break;
1621                             }
1622                             cnt += 1;
1623                         }
1624                     }
1625                 }
1626             }
1627 
1628             return q;
1629         },
1630 
1631         /**
1632          * Find the n-th intersection point of two curves named red (first parameter) and blue (second parameter).
1633          * We go through each segment of the red curve and search if there is an intersection with a segemnt of the blue curve.
1634          * This double loop, i.e. the outer loop runs along the red curve and the inner loop runs along the blue curve, defines
1635          * the n-th intersection point. The segments are either line segments or Bezier curves of degree 3. This depends on
1636          * the property bezierDegree of the curves.
1637          * <p>
1638          * This method works also for transformed curves, since only the already
1639          * transformed points are used.
1640          *
1641          * @param {JXG.Curve} red
1642          * @param {JXG.Curve} blue
1643          * @param {Number} nr
1644          */
1645         meetCurveRedBlueSegments: function (red, blue, nr) {
1646             var i, j,
1647                 red1, red2, blue1, blue2, m,
1648                 minX, maxX,
1649                 iFound = 0,
1650                 lenBlue = blue.numberPoints, //points.length,
1651                 lenRed = red.numberPoints; //points.length;
1652 
1653             if (lenBlue <= 1 || lenRed <= 1) {
1654                 return [0, NaN, NaN];
1655             }
1656 
1657             for (i = 1; i < lenRed; i++) {
1658                 red1 = red.points[i - 1].usrCoords;
1659                 red2 = red.points[i].usrCoords;
1660                 minX = Math.min(red1[1], red2[1]);
1661                 maxX = Math.max(red1[1], red2[1]);
1662 
1663                 blue2 = blue.points[0].usrCoords;
1664                 for (j = 1; j < lenBlue; j++) {
1665                     blue1 = blue2;
1666                     blue2 = blue.points[j].usrCoords;
1667 
1668                     if (Math.min(blue1[1], blue2[1]) < maxX && Math.max(blue1[1], blue2[1]) > minX) {
1669                         m = this.meetSegmentSegment(red1, red2, blue1, blue2);
1670                         if (m[1] >= 0.0 && m[2] >= 0.0 &&
1671                                 // The two segments meet in the interior or at the start points
1672                                 ((m[1] < 1.0 && m[2] < 1.0) ||
1673                                 // One of the curve is intersected in the very last point
1674                                 (i === lenRed - 1 && m[1] === 1.0) ||
1675                                 (j === lenBlue - 1 && m[2] === 1.0))) {
1676                             if (iFound === nr) {
1677                                 return m[0];
1678                             }
1679 
1680                             iFound++;
1681                         }
1682                     }
1683                 }
1684             }
1685 
1686             return [0, NaN, NaN];
1687         },
1688 
1689         /**
1690          * Intersection of two segments.
1691          * @param {Array} p1 First point of segment 1 using homogeneous coordinates [z,x,y]
1692          * @param {Array} p2 Second point of segment 1 using homogeneous coordinates [z,x,y]
1693          * @param {Array} q1 First point of segment 2 using homogeneous coordinates [z,x,y]
1694          * @param {Array} q2 Second point of segment 2 using homogeneous coordinates [z,x,y]
1695          * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates
1696          * of the intersection point. The second and third entry gives the position of the intersection between the
1697          * two defining points. For example, the second entry t is defined by: intersection point = t*p1 + (1-t)*p2.
1698          * If the two segments are collinear, [[0,0,0], Infinity, Infinity] is returned.
1699          **/
1700         meetSegmentSegment: function (p1, p2, q1, q2) {
1701             var t, u, diff,
1702                 li1 = Mat.crossProduct(p1, p2),
1703                 li2 = Mat.crossProduct(q1, q2),
1704                 c = Mat.crossProduct(li1, li2),
1705                 denom = c[0];
1706 
1707             if (Math.abs(denom) < Mat.eps) {
1708                 return [c, Infinity, Infinity];
1709             }
1710 
1711             diff = [q1[1] - p1[1], q1[2] - p1[2]];
1712 
1713             // Because of speed issues, evalute the determinants directly
1714             t = (diff[0] * (q2[2] - q1[2]) - diff[1] * (q2[1] - q1[1])) / denom;
1715             u = (diff[0] * (p2[2] - p1[2]) - diff[1] * (p2[1] - p1[1])) / denom;
1716 
1717             return [c, t, u];
1718         },
1719 
1720         /****************************************/
1721         /****   BEZIER CURVE ALGORITHMS      ****/
1722         /****************************************/
1723 
1724         /**
1725          * Splits a Bezier curve segment defined by four points into
1726          * two Bezier curve segments. Dissection point is t=1/2.
1727          * @param {Array} curve Array of four coordinate arrays of length 2 defining a
1728          * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]].
1729          * @returns {Array} Array consisting of two coordinate arrays for Bezier curves.
1730          */
1731         _bezierSplit: function (curve) {
1732             var p0, p1, p2, p00, p22, p000;
1733 
1734             p0 = [(curve[0][0] + curve[1][0]) * 0.5, (curve[0][1] + curve[1][1]) * 0.5];
1735             p1 = [(curve[1][0] + curve[2][0]) * 0.5, (curve[1][1] + curve[2][1]) * 0.5];
1736             p2 = [(curve[2][0] + curve[3][0]) * 0.5, (curve[2][1] + curve[3][1]) * 0.5];
1737 
1738             p00 = [(p0[0] + p1[0]) * 0.5, (p0[1] + p1[1]) * 0.5];
1739             p22 = [(p1[0] + p2[0]) * 0.5, (p1[1] + p2[1]) * 0.5];
1740 
1741             p000 = [(p00[0] + p22[0]) * 0.5, (p00[1] + p22[1]) * 0.5];
1742 
1743             return [[curve[0], p0, p00, p000], [p000, p22, p2, curve[3]]];
1744         },
1745 
1746         /**
1747          * Computes the bounding box [minX, maxY, maxX, minY] of a Bezier curve segment
1748          * from its control points.
1749          * @param {Array} curve Array of four coordinate arrays of length 2 defining a
1750          * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]].
1751          * @returns {Array} Bounding box [minX, maxY, maxX, minY]
1752          */
1753         _bezierBbox: function (curve) {
1754             var bb = [];
1755 
1756             if (curve.length === 4) {   // bezierDegree == 3
1757                 bb[0] = Math.min(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // minX
1758                 bb[1] = Math.max(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // maxY
1759                 bb[2] = Math.max(curve[0][0], curve[1][0], curve[2][0], curve[3][0]); // maxX
1760                 bb[3] = Math.min(curve[0][1], curve[1][1], curve[2][1], curve[3][1]); // minY
1761             } else {                   // bezierDegree == 1
1762                 bb[0] = Math.min(curve[0][0], curve[1][0]); // minX
1763                 bb[1] = Math.max(curve[0][1], curve[1][1]); // maxY
1764                 bb[2] = Math.max(curve[0][0], curve[1][0]); // maxX
1765                 bb[3] = Math.min(curve[0][1], curve[1][1]); // minY
1766             }
1767 
1768             return bb;
1769         },
1770 
1771         /**
1772          * Decide if two Bezier curve segments overlap by comparing their bounding boxes.
1773          * @param {Array} bb1 Bounding box of the first Bezier curve segment
1774          * @param {Array} bb2 Bounding box of the second Bezier curve segment
1775          * @returns {Boolean} true if the bounding boxes overlap, false otherwise.
1776          */
1777         _bezierOverlap: function (bb1, bb2) {
1778             return bb1[2] >= bb2[0] && bb1[0] <= bb2[2] && bb1[1] >= bb2[3] && bb1[3] <= bb2[1];
1779         },
1780 
1781         /**
1782          * Append list of intersection points to a list.
1783          * @private
1784          */
1785         _bezierListConcat: function (L, Lnew, t1, t2) {
1786             var i,
1787                 t2exists = Type.exists(t2),
1788                 start = 0,
1789                 len = Lnew.length,
1790                 le = L.length;
1791 
1792             if (le > 0 && len > 0 &&
1793                     ((L[le - 1][1] === 1 && Lnew[0][1] === 0) ||
1794                     (t2exists && L[le - 1][2] === 1 && Lnew[0][2] === 0))) {
1795                 start = 1;
1796             }
1797 
1798             for (i = start; i < len; i++) {
1799                 if (t2exists) {
1800                     Lnew[i][2] *= 0.5;
1801                     Lnew[i][2] += t2;
1802                 }
1803 
1804                 Lnew[i][1] *= 0.5;
1805                 Lnew[i][1] += t1;
1806 
1807                 L.push(Lnew[i]);
1808             }
1809         },
1810 
1811         /**
1812          * Find intersections of two Bezier curve segments by recursive subdivision.
1813          * Below maxlevel determine intersections by intersection line segments.
1814          * @param {Array} red Array of four coordinate arrays of length 2 defining the first
1815          * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]].
1816          * @param {Array} blue Array of four coordinate arrays of length 2 defining the second
1817          * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]].
1818          * @param {Number} level Recursion level
1819          * @returns {Array} List of intersection points (up to nine). Each intersection point is an
1820          * array of length three (homogeneous coordinates) plus preimages.
1821          */
1822         _bezierMeetSubdivision: function (red, blue, level) {
1823             var bbb, bbr,
1824                 ar, b0, b1, r0, r1, m,
1825                 p0, p1, q0, q1,
1826                 L = [],
1827                 maxLev = 5;      // Maximum recursion level
1828 
1829             bbr = this._bezierBbox(blue);
1830             bbb = this._bezierBbox(red);
1831 
1832             if (!this._bezierOverlap(bbr, bbb)) {
1833                 return [];
1834             }
1835 
1836             if (level < maxLev) {
1837                 ar = this._bezierSplit(red);
1838                 r0 = ar[0];
1839                 r1 = ar[1];
1840 
1841                 ar = this._bezierSplit(blue);
1842                 b0 = ar[0];
1843                 b1 = ar[1];
1844 
1845                 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b0, level + 1), 0.0, 0.0);
1846                 this._bezierListConcat(L, this._bezierMeetSubdivision(r0, b1, level + 1), 0, 0.5);
1847                 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b0, level + 1), 0.5, 0.0);
1848                 this._bezierListConcat(L, this._bezierMeetSubdivision(r1, b1, level + 1), 0.5, 0.5);
1849 
1850                 return L;
1851             }
1852 
1853             // Make homogeneous coordinates
1854             q0 = [1].concat(red[0]);
1855             q1 = [1].concat(red[3]);
1856             p0 = [1].concat(blue[0]);
1857             p1 = [1].concat(blue[3]);
1858 
1859             m = this.meetSegmentSegment(q0, q1, p0, p1);
1860 
1861             if (m[1] >= 0.0 && m[2] >= 0.0 && m[1] <= 1.0 && m[2] <= 1.0) {
1862                 return [m];
1863             }
1864 
1865             return [];
1866         },
1867 
1868         /**
1869          * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment
1870          */
1871         _bezierLineMeetSubdivision: function (red, blue, level, testSegment) {
1872             var bbb, bbr,
1873                 ar, r0, r1, m,
1874                 p0, p1, q0, q1,
1875                 L = [],
1876                 maxLev = 5;      // Maximum recursion level
1877 
1878             bbb = this._bezierBbox(blue);
1879             bbr = this._bezierBbox(red);
1880 
1881             if (testSegment && !this._bezierOverlap(bbr, bbb)) {
1882                 return [];
1883             }
1884 
1885             if (level < maxLev) {
1886                 ar = this._bezierSplit(red);
1887                 r0 = ar[0];
1888                 r1 = ar[1];
1889 
1890                 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r0, blue, level + 1), 0.0);
1891                 this._bezierListConcat(L, this._bezierLineMeetSubdivision(r1, blue, level + 1), 0.5);
1892 
1893                 return L;
1894             }
1895 
1896             // Make homogeneous coordinates
1897             q0 = [1].concat(red[0]);
1898             q1 = [1].concat(red[3]);
1899             p0 = [1].concat(blue[0]);
1900             p1 = [1].concat(blue[1]);
1901 
1902             m = this.meetSegmentSegment(q0, q1, p0, p1);
1903 
1904             if (m[1] >= 0.0 && m[1] <= 1.0) {
1905                 if (!testSegment || (m[2] >= 0.0 && m[2] <= 1.0)) {
1906                     return [m];
1907                 }
1908             }
1909 
1910             return [];
1911         },
1912 
1913         /**
1914          * Find the nr-th intersection point of two Bezier curve segments.
1915          * @param {Array} red Array of four coordinate arrays of length 2 defining the first
1916          * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]].
1917          * @param {Array} blue Array of four coordinate arrays of length 2 defining the second
1918          * Bezier curve segment, i.e. [[x0,y0], [x1,y1], [x2,y2], [x3,y3]].
1919          * @param {Boolean} testSegment Test if intersection has to be inside of the segment or somewhere on the line defined by the segment
1920          * @returns {Array} Array containing the list of all intersection points as homogeneous coordinate arrays plus
1921          * preimages [x,y], t_1, t_2] of the two Bezier curve segments.
1922          *
1923          */
1924         meetBeziersegmentBeziersegment: function (red, blue, testSegment) {
1925             var L, L2, i;
1926 
1927             if (red.length === 4 && blue.length === 4) {
1928                 L = this._bezierMeetSubdivision(red, blue, 0);
1929             } else {
1930                 L = this._bezierLineMeetSubdivision(red, blue, 0, testSegment);
1931             }
1932 
1933             L.sort(function (a, b) {
1934                 return (a[1] - b[1]) * 10000000.0 + (a[2] - b[2]);
1935             });
1936 
1937             L2 = [];
1938             for (i = 0; i < L.length; i++) {
1939                 // Only push entries different from their predecessor
1940                 if (i === 0 || (L[i][1] !== L[i - 1][1] || L[i][2] !== L[i - 1][2])) {
1941                     L2.push(L[i]);
1942                 }
1943             }
1944             return L2;
1945         },
1946 
1947         /**
1948          * Find the nr-th intersection point of two Bezier curves, i.e. curves with bezierDegree == 3.
1949          * @param {JXG.Curve} red Curve with bezierDegree == 3
1950          * @param {JXG.Curve} blue Curve with bezierDegree == 3
1951          * @param {Number} nr The number of the intersection point which should be returned.
1952          * @returns {Array} The homogeneous coordinates of the nr-th intersection point.
1953          */
1954         meetBezierCurveRedBlueSegments: function (red, blue, nr) {
1955             var p, i, j,
1956                 redArr, blueArr,
1957                 bbr, bbb,
1958                 lenBlue = blue.numberPoints, //points.length,
1959                 lenRed = red.numberPoints, // points.length,
1960                 L = [];
1961 
1962             if (lenBlue < 4 || lenRed < 4) {
1963                 return [0, NaN, NaN];
1964             }
1965 
1966             for (i = 0; i < lenRed - 3; i += 3) {
1967                 p = red.points;
1968                 redArr = [
1969                     [p[i].usrCoords[1], p[i].usrCoords[2]],
1970                     [p[i + 1].usrCoords[1], p[i + 1].usrCoords[2]],
1971                     [p[i + 2].usrCoords[1], p[i + 2].usrCoords[2]],
1972                     [p[i + 3].usrCoords[1], p[i + 3].usrCoords[2]]
1973                 ];
1974 
1975                 bbr = this._bezierBbox(redArr);
1976 
1977                 for (j = 0; j < lenBlue - 3; j += 3) {
1978                     p = blue.points;
1979                     blueArr = [
1980                         [p[j].usrCoords[1], p[j].usrCoords[2]],
1981                         [p[j + 1].usrCoords[1], p[j + 1].usrCoords[2]],
1982                         [p[j + 2].usrCoords[1], p[j + 2].usrCoords[2]],
1983                         [p[j + 3].usrCoords[1], p[j + 3].usrCoords[2]]
1984                     ];
1985 
1986                     bbb = this._bezierBbox(blueArr);
1987                     if (this._bezierOverlap(bbr, bbb)) {
1988                         L = L.concat(this.meetBeziersegmentBeziersegment(redArr, blueArr));
1989                         if (L.length > nr) {
1990                             return L[nr][0];
1991                         }
1992                     }
1993                 }
1994             }
1995             if (L.length > nr) {
1996                 return L[nr][0];
1997             }
1998 
1999             return [0, NaN, NaN];
2000         },
2001 
2002         bezierSegmentEval: function (t, curve) {
2003             var f, x, y,
2004                 t1 = 1.0 - t;
2005 
2006             x = 0;
2007             y = 0;
2008 
2009             f = t1 * t1 * t1;
2010             x += f * curve[0][0];
2011             y += f * curve[0][1];
2012 
2013             f = 3.0 * t * t1 * t1;
2014             x += f * curve[1][0];
2015             y += f * curve[1][1];
2016 
2017             f = 3.0 * t * t * t1;
2018             x += f * curve[2][0];
2019             y += f * curve[2][1];
2020 
2021             f = t * t * t;
2022             x += f * curve[3][0];
2023             y += f * curve[3][1];
2024 
2025             return [1.0, x, y];
2026         },
2027 
2028         /**
2029          * Generate the defining points of a 3rd degree bezier curve that approximates
2030          * a circle sector defined by three coordinate points A, B, C, each defined by an array of length three.
2031          * The coordinate arrays are given in homogeneous coordinates.
2032          * @param {Array} A First point
2033          * @param {Array} B Second point (intersection point)
2034          * @param {Array} C Third point
2035          * @param {Boolean} withLegs Flag. If true the legs to the intersection point are part of the curve.
2036          * @param {Number} sgn Wither 1 or -1. Needed for minor and major arcs. In case of doubt, use 1.
2037          */
2038         bezierArc: function (A, B, C, withLegs, sgn) {
2039             var p1, p2, p3, p4,
2040                 r, phi, beta,
2041                 PI2 = Math.PI * 0.5,
2042                 x = B[1],
2043                 y = B[2],
2044                 z = B[0],
2045                 dataX = [], dataY = [],
2046                 co, si, ax, ay, bx, by, k, v, d, matrix;
2047 
2048             r = this.distance(B, A);
2049 
2050             // x,y, z is intersection point. Normalize it.
2051             x /= z;
2052             y /= z;
2053 
2054             phi = this.rad(A.slice(1), B.slice(1), C.slice(1));
2055             if (sgn === -1) {
2056                 phi = 2 * Math.PI - phi;
2057             }
2058 
2059             p1 = A;
2060             p1[1] /= p1[0];
2061             p1[2] /= p1[0];
2062             p1[0] /= p1[0];
2063 
2064             p4 = p1.slice(0);
2065 
2066             if (withLegs) {
2067                 dataX = [x, x + 0.333 * (p1[1] - x), x + 0.666 * (p1[1] - x), p1[1]];
2068                 dataY = [y, y + 0.333 * (p1[2] - y), y + 0.666 * (p1[2] - y), p1[2]];
2069             } else {
2070                 dataX = [p1[1]];
2071                 dataY = [p1[2]];
2072             }
2073 
2074             while (phi > Mat.eps) {
2075                 if (phi > PI2) {
2076                     beta = PI2;
2077                     phi -= PI2;
2078                 } else {
2079                     beta = phi;
2080                     phi = 0;
2081                 }
2082 
2083                 co = Math.cos(sgn * beta);
2084                 si = Math.sin(sgn * beta);
2085 
2086                 matrix = [
2087                     [1, 0, 0],
2088                     [x * (1 - co) + y * si, co, -si],
2089                     [y * (1 - co) - x * si, si,  co]
2090                 ];
2091                 v = Mat.matVecMult(matrix, p1);
2092                 p4 = [v[0] / v[0], v[1] / v[0], v[2] / v[0]];
2093 
2094                 ax = p1[1] - x;
2095                 ay = p1[2] - y;
2096                 bx = p4[1] - x;
2097                 by = p4[2] - y;
2098 
2099                 d = Math.sqrt((ax + bx) * (ax + bx) + (ay + by) * (ay + by));
2100 
2101                 if (Math.abs(by - ay) > Mat.eps) {
2102                     k = (ax + bx) * (r / d - 0.5) / (by - ay) * 8 / 3;
2103                 } else {
2104                     k = (ay + by) * (r / d - 0.5) / (ax - bx) * 8 / 3;
2105                 }
2106 
2107                 p2 = [1, p1[1] - k * ay, p1[2] + k * ax];
2108                 p3 = [1, p4[1] + k * by, p4[2] - k * bx];
2109 
2110                 dataX = dataX.concat([p2[1], p3[1], p4[1]]);
2111                 dataY = dataY.concat([p2[2], p3[2], p4[2]]);
2112                 p1 = p4.slice(0);
2113             }
2114 
2115             if (withLegs) {
2116                 dataX = dataX.concat([ p4[1] + 0.333 * (x - p4[1]), p4[1] + 0.666 * (x - p4[1]), x]);
2117                 dataY = dataY.concat([ p4[2] + 0.333 * (y - p4[2]), p4[2] + 0.666 * (y - p4[2]), y]);
2118             }
2119 
2120             return [dataX, dataY];
2121         },
2122 
2123         /****************************************/
2124         /****           PROJECTIONS          ****/
2125         /****************************************/
2126 
2127         /**
2128          * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the
2129          * nearest one of the two intersection points of the line through the given point and the circles
2130          * center.
2131          * @param {JXG.Point,JXG.Coords} point Point to project or coords object to project.
2132          * @param {JXG.Circle} circle Circle on that the point is projected.
2133          * @param {JXG.Board} [board=point.board] Reference to the board
2134          * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
2135          */
2136         projectPointToCircle: function (point, circle, board) {
2137             var dist, P, x, y, factor,
2138                 M = circle.center.coords.usrCoords;
2139 
2140             if (!Type.exists(board)) {
2141                 board = point.board;
2142             }
2143 
2144             // gave us a point
2145             if (Type.isPoint(point)) {
2146                 dist = point.coords.distance(Const.COORDS_BY_USER, circle.center.coords);
2147                 P = point.coords.usrCoords;
2148             // gave us coords
2149             } else {
2150                 dist = point.distance(Const.COORDS_BY_USER, circle.center.coords);
2151                 P = point.usrCoords;
2152             }
2153 
2154             if (Math.abs(dist) < Mat.eps) {
2155                 dist = Mat.eps;
2156             }
2157 
2158             factor = circle.Radius() / dist;
2159             x = M[1] + factor * (P[1] - M[1]);
2160             y = M[2] + factor * (P[2] - M[2]);
2161 
2162             return new Coords(Const.COORDS_BY_USER, [x, y], board);
2163         },
2164 
2165         /**
2166          * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the
2167          * intersection point of the given line and its perpendicular through the given point.
2168          * @param {JXG.Point|JXG.Coords} point Point to project.
2169          * @param {JXG.Line} line Line on that the point is projected.
2170          * @param {JXG.Board} [board=point.board|board=line.board] Reference to a board.
2171          * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line.
2172          */
2173         projectPointToLine: function (point, line, board) {
2174             var v = [0, line.stdform[1], line.stdform[2]],
2175                 coords;
2176 
2177             if (!Type.exists(board)) {
2178                 if (Type.exists(point.coords)) {
2179                     board = point.board;
2180                 } else {
2181                     board = line.board;
2182                 }
2183             }
2184 
2185             if (Type.exists(point.coords)) {
2186                 coords = point.coords.usrCoords;
2187             } else {
2188                 coords = point.usrCoords;
2189             }
2190 
2191             v = Mat.crossProduct(v, coords);
2192             return new Coords(Const.COORDS_BY_USER, Mat.crossProduct(v, line.stdform), board);
2193         },
2194 
2195         /**
2196          * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line
2197          * segment defined by two coordinate arrays.
2198          * @param {Array} p Point to project.
2199          * @param {Array} q1 Start point of the line segment on that the point is projected.
2200          * @param {Array} q2 End point of the line segment on that the point is projected.
2201          * @returns {Array} The coordinates of the projection of the given point on the given segment
2202          * and the factor that determines the projected point as a convex combination of the
2203          * two endpoints q1 and q2 of the segment.
2204          */
2205         projectCoordsToSegment: function (p, q1, q2) {
2206             var t, denom,
2207                 s = [q2[1] - q1[1], q2[2] - q1[2]],
2208                 v = [p[1] - q1[1], p[2] - q1[2]];
2209 
2210             /**
2211              * If the segment has length 0, i.e. is a point,
2212              * the projection is equal to that point.
2213              */
2214             if (Math.abs(s[0]) < Mat.eps && Math.abs(s[1]) < Mat.eps) {
2215                 return [q1, 0];
2216             }
2217 
2218             t = Mat.innerProduct(v, s);
2219             denom = Mat.innerProduct(s, s);
2220             t /= denom;
2221 
2222             return [ [1, t * s[0] + q1[1], t * s[1] + q1[2]], t];
2223         },
2224 
2225         /**
2226          * Finds the coordinates of the closest point on a Bezier segment of a
2227          * {@link JXG.Curve} to a given coordinate array.
2228          * @param {Array} pos Point to project in homogeneous coordinates.
2229          * @param {JXG.Curve} curve Curve of type "plot" having Bezier degree 3.
2230          * @param {Number} start Number of the Bezier segment of the curve.
2231          * @returns {Array} The coordinates of the projection of the given point
2232          * on the given Bezier segment and the preimage of the curve which
2233          * determines the closest point.
2234          */
2235         projectCoordsToBeziersegment: function (pos, curve, start) {
2236             var t0,
2237                 /** @ignore */
2238                 minfunc = function (t) {
2239                     var z = [1, curve.X(start + t), curve.Y(start + t)];
2240 
2241                     z[1] -= pos[1];
2242                     z[2] -= pos[2];
2243 
2244                     return z[1] * z[1] + z[2] * z[2];
2245                 };
2246 
2247             t0 = JXG.Math.Numerics.fminbr(minfunc, [0.0, 1.0]);
2248 
2249             return [[1, curve.X(t0 + start), curve.Y(t0 + start)], t0];
2250         },
2251 
2252         /**
2253          * Calculates the coordinates of the projection of a given point on a given curve.
2254          * Uses {@link JXG.Math.Geometry.projectCoordsToCurve}.
2255          *
2256          * @param {JXG.Point} point Point to project.
2257          * @param {JXG.Curve} curve Curve on that the point is projected.
2258          * @param {JXG.Board} [board=point.board] Reference to a board.
2259          * @see #projectCoordsToCurve
2260          * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph.
2261          */
2262         projectPointToCurve: function (point, curve, board) {
2263             if (!Type.exists(board)) {
2264                 board = point.board;
2265             }
2266 
2267             var x = point.X(),
2268                 y = point.Y(),
2269                 t = point.position || 0.0,
2270                 result = this.projectCoordsToCurve(x, y, t, curve, board);
2271 
2272             point.position = result[1];
2273 
2274             return result[0];
2275         },
2276 
2277         /**
2278          * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of
2279          * function graphs this is the
2280          * intersection point of the curve and the parallel to y-axis through the given point.
2281          * @param {Number} x coordinate to project.
2282          * @param {Number} y coordinate to project.
2283          * @param {Number} t start value for newtons method
2284          * @param {JXG.Curve} curve Curve on that the point is projected.
2285          * @param {JXG.Board} [board=curve.board] Reference to a board.
2286          * @see #projectPointToCurve
2287          * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and
2288          * the position on the curve.
2289          */
2290         projectCoordsToCurve: function (x, y, t, curve, board) {
2291             var newCoords, newCoordsObj, i, j,
2292                 mindist, dist, lbda, v, coords, d,
2293                 p1, p2, res,
2294                 minfunc, tnew, fnew, fold, delta, steps,
2295                 minX, maxX,
2296                 infty = Number.POSITIVE_INFINITY;
2297 
2298             if (!Type.exists(board)) {
2299                 board = curve.board;
2300             }
2301 
2302 
2303             if (Type.evaluate(curve.visProp.curvetype) === 'plot') {
2304                 t = 0;
2305                 mindist = infty;
2306                 if (curve.numberPoints === 0) {
2307                     newCoords = [0, 1, 1];
2308                 } else {
2309                     newCoords = [curve.Z(0), curve.X(0), curve.Y(0)];
2310                 }
2311 
2312                 if (curve.numberPoints > 1) {
2313                     v = [1, x, y];
2314                     if (curve.bezierDegree === 3) {
2315                         j = 0;
2316                     } else {
2317                         p1 = [curve.Z(0), curve.X(0), curve.Y(0)];
2318                     }
2319                     for (i = 0; i < curve.numberPoints - 1; i++) {
2320                         if (curve.bezierDegree === 3) {
2321                             res = this.projectCoordsToBeziersegment(v, curve, j);
2322                         } else {
2323                             p2 = [curve.Z(i + 1), curve.X(i + 1), curve.Y(i + 1)];
2324                             res = this.projectCoordsToSegment(v, p1, p2);
2325                         }
2326                         lbda = res[1];
2327                         coords = res[0];
2328 
2329                         if (0.0 <= lbda && lbda <= 1.0) {
2330                             dist = this.distance(coords, v);
2331                             d = i + lbda;
2332                         } else if (lbda < 0.0) {
2333                             coords = p1;
2334                             dist = this.distance(p1, v);
2335                             d = i;
2336                         } else if (lbda > 1.0 && i === curve.numberPoints - 2) {
2337                             coords = p2;
2338                             dist = this.distance(coords, v);
2339                             d = curve.numberPoints - 1;
2340                         }
2341 
2342                         if (dist < mindist) {
2343                             mindist = dist;
2344                             t = d;
2345                             newCoords = coords;
2346                         }
2347 
2348                         if (curve.bezierDegree === 3) {
2349                             j++;
2350                             i += 2;
2351                         } else {
2352                             p1 = p2;
2353                         }
2354                     }
2355                 }
2356 
2357                 newCoordsObj = new Coords(Const.COORDS_BY_USER, newCoords, board);
2358             } else {   // 'parameter', 'polar', 'functiongraph'
2359                 /** @ignore */
2360                 minfunc = function (t) {
2361                     var dx, dy;
2362                     if (t < curve.minX() || t > curve.maxX()) {
2363                         return NaN;
2364                     }
2365                     dx = x - curve.X(t);
2366                     dy = y - curve.Y(t);
2367                     return dx * dx + dy * dy;
2368                 };
2369 
2370                 fold = minfunc(t);
2371                 steps = 50;
2372                 delta = (curve.maxX() - curve.minX()) / steps;
2373                 tnew = curve.minX();
2374 
2375                 for (i = 0; i < steps; i++) {
2376                     fnew = minfunc(tnew);
2377 
2378                     if (fnew < fold || isNaN(fold)) {
2379                         t = tnew;
2380                         fold = fnew;
2381                     }
2382 
2383                     tnew += delta;
2384                 }
2385 
2386                 //t = Numerics.root(Numerics.D(minfunc), t);
2387                 t = Numerics.fminbr(minfunc, [t - delta, t + delta]);
2388 
2389                 minX = curve.minX();
2390                 maxX = curve.maxX();
2391                 // Distinction between closed and open curves is not necessary.
2392                 // If closed, the cyclic projection shift will work anyhow
2393                 // if (Math.abs(curve.X(minX) - curve.X(maxX)) < Mat.eps &&
2394                 //     Math.abs(curve.Y(minX) - curve.Y(maxX)) < Mat.eps) {
2395                 //     // Cyclically
2396                 //     if (t < minX) {
2397                 //         t = maxX + t - minX;
2398                 //     }
2399                 //     if (t > maxX) {
2400                 //         t = minX + t - maxX;
2401                 //     }
2402                 // } else {
2403                     t = (t < minX) ? minX : t;
2404                     t = (t > maxX) ? maxX : t;
2405                 // }
2406 
2407                 newCoordsObj = new Coords(Const.COORDS_BY_USER, [curve.X(t), curve.Y(t)], board);
2408             }
2409 
2410             return [curve.updateTransform(newCoordsObj), t];
2411         },
2412 
2413         /**
2414          * Calculates the coordinates of the closest orthogonal projection of a given coordinate array onto the
2415          * border of a polygon.
2416          * @param {Array} p Point to project.
2417          * @param {JXG.Polygon} pol Polygon element
2418          * @returns {Array} The coordinates of the closest projection of the given point to the border of the polygon.
2419          */
2420         projectCoordsToPolygon: function (p, pol) {
2421             var i,
2422                 len = pol.vertices.length,
2423                 d_best = Infinity,
2424                 d,
2425                 projection,
2426                 bestprojection;
2427 
2428             for (i = 0; i < len; i++) {
2429                 projection = JXG.Math.Geometry.projectCoordsToSegment(
2430                     p,
2431                     pol.vertices[i].coords.usrCoords,
2432                     pol.vertices[(i + 1) % len].coords.usrCoords
2433                 );
2434 
2435                 d = JXG.Math.Geometry.distance(projection[0], p, 3);
2436                 if (0 <= projection[1] && projection[1] <= 1 && d < d_best) {
2437                     bestprojection = projection[0].slice(0);
2438                     d_best = d;
2439                 }
2440             }
2441             return bestprojection;
2442         },
2443 
2444         /**
2445          * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of
2446          * one or more curves of curveType 'plot'. Uses {@link JXG.Math.Geometry.projectPointToCurve}.
2447          * @param {JXG.Point} point Point to project.
2448          * @param {JXG.Turtle} turtle on that the point is projected.
2449          * @param {JXG.Board} [board=point.board] Reference to a board.
2450          * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle.
2451          */
2452         projectPointToTurtle: function (point, turtle, board) {
2453             var newCoords, t, x, y, i, dist, el, minEl,
2454                 np = 0,
2455                 npmin = 0,
2456                 mindist = Number.POSITIVE_INFINITY,
2457                 len = turtle.objects.length;
2458 
2459             if (!Type.exists(board)) {
2460                 board = point.board;
2461             }
2462 
2463             // run through all curves of this turtle
2464             for (i = 0; i < len; i++) {
2465                 el = turtle.objects[i];
2466 
2467                 if (el.elementClass === Const.OBJECT_CLASS_CURVE) {
2468                     newCoords = this.projectPointToCurve(point, el);
2469                     dist = this.distance(newCoords.usrCoords, point.coords.usrCoords);
2470 
2471                     if (dist < mindist) {
2472                         x = newCoords.usrCoords[1];
2473                         y = newCoords.usrCoords[2];
2474                         t = point.position;
2475                         mindist = dist;
2476                         minEl = el;
2477                         npmin = np;
2478                     }
2479                     np += el.numberPoints;
2480                 }
2481             }
2482 
2483             newCoords = new Coords(Const.COORDS_BY_USER, [x, y], board);
2484             point.position = t + npmin;
2485 
2486             return minEl.updateTransform(newCoords);
2487         },
2488 
2489         /**
2490          * Trivial projection of a point to another point.
2491          * @param {JXG.Point} point Point to project (not used).
2492          * @param {JXG.Point} dest Point on that the point is projected.
2493          * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
2494          */
2495         projectPointToPoint: function (point, dest) {
2496             return dest.coords;
2497         },
2498 
2499         /**
2500          *
2501          * @param {JXG.Point|JXG.Coords} point
2502          * @param {JXG.Board} [board]
2503          */
2504         projectPointToBoard: function (point, board) {
2505             var i, l, c,
2506                 brd = board || point.board,
2507                 // comparison factor, point coord idx, bbox idx, 1st bbox corner x & y idx, 2nd bbox corner x & y idx
2508                 config = [
2509                     // left
2510                     [1, 1, 0, 0, 3, 0, 1],
2511                     // top
2512                     [-1, 2, 1, 0, 1, 2, 1],
2513                     // right
2514                     [-1, 1, 2, 2, 1, 2, 3],
2515                     // bottom
2516                     [1, 2, 3, 0, 3, 2, 3]
2517                 ],
2518                 coords = point.coords || point,
2519                 bbox = brd.getBoundingBox();
2520 
2521             for (i = 0; i < 4; i++) {
2522                 c = config[i];
2523                 if (c[0] * coords.usrCoords[c[1]] < c[0] * bbox[c[2]]) {
2524                     // define border
2525                     l = Mat.crossProduct([1, bbox[c[3]], bbox[c[4]]], [1, bbox[c[5]], bbox[c[6]]]);
2526                     l[3] = 0;
2527                     l = Mat.normalize(l);
2528 
2529                     // project point
2530                     coords = this.projectPointToLine({coords: coords}, {stdform: l}, brd);
2531                 }
2532             }
2533 
2534             return coords;
2535         },
2536 
2537         /**
2538          * Calculates the distance of a point to a line. The point and the line are given by homogeneous
2539          * coordinates. For lines this can be line.stdform.
2540          * @param {Array} point Homogeneous coordinates of a point.
2541          * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0).
2542          * @returns {Number} Distance of the point to the line.
2543          */
2544         distPointLine: function (point, line) {
2545             var a = line[1],
2546                 b = line[2],
2547                 c = line[0],
2548                 nom;
2549 
2550             if (Math.abs(a) + Math.abs(b) < Mat.eps) {
2551                 return Number.POSITIVE_INFINITY;
2552             }
2553 
2554             nom = a * point[1] + b * point[2] + c;
2555             a *= a;
2556             b *= b;
2557 
2558             return Math.abs(nom) / Math.sqrt(a + b);
2559         },
2560 
2561         /**
2562          * Helper function to create curve which displays a Reuleaux polygons.
2563          * @param {Array} points Array of points which should be the vertices of the Reuleaux polygon. Typically,
2564          * these point list is the array vertices of a regular polygon.
2565          * @param {Number} nr Number of vertices
2566          * @returns {Array} An array containing the two functions defining the Reuleaux polygon and the two values
2567          * for the start and the end of the paramtric curve. array may be used as parent array of a
2568          * {@link JXG.Curve}.
2569          *
2570          * @example
2571          * var A = brd.create('point',[-2,-2]);
2572          * var B = brd.create('point',[0,1]);
2573          * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0});
2574          * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3),
2575          *                          {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'});
2576          *
2577          * </pre><div class="jxgbox" id="JXG2543a843-46a9-4372-abc1-94d9ad2db7ac" style="width: 300px; height: 300px;"></div>
2578          * <script type="text/javascript">
2579          * var brd = JXG.JSXGraph.initBoard('JXG2543a843-46a9-4372-abc1-94d9ad2db7ac', {boundingbox: [-5, 5, 5, -5], axis: true, showcopyright:false, shownavigation: false});
2580          * var A = brd.create('point',[-2,-2]);
2581          * var B = brd.create('point',[0,1]);
2582          * var pol = brd.create('regularpolygon',[A,B,3], {withLines:false, fillColor:'none', highlightFillColor:'none', fillOpacity:0.0});
2583          * var reuleauxTriangle = brd.create('curve', JXG.Math.Geometry.reuleauxPolygon(pol.vertices, 3),
2584          *                          {strokeWidth:6, strokeColor:'#d66d55', fillColor:'#ad5544', highlightFillColor:'#ad5544'});
2585          * </script><pre>
2586          */
2587         reuleauxPolygon: function (points, nr) {
2588             var beta,
2589                 pi2 = Math.PI * 2,
2590                 pi2_n = pi2 / nr,
2591                 diag = (nr - 1) / 2,
2592                 d = 0,
2593                 makeFct = function (which, trig) {
2594                     return function (t, suspendUpdate) {
2595                         var t1 = (t % pi2 + pi2) % pi2,
2596                             j = Math.floor(t1 / pi2_n) % nr;
2597 
2598                         if (!suspendUpdate) {
2599                             d = points[0].Dist(points[diag]);
2600                             beta = Mat.Geometry.rad([points[0].X() + 1, points[0].Y()], points[0], points[diag % nr]);
2601                         }
2602 
2603                         if (isNaN(j)) {
2604                             return j;
2605                         }
2606 
2607                         t1 = t1 * 0.5 + j * pi2_n * 0.5 + beta;
2608 
2609                         return points[j][which]() + d * Math[trig](t1);
2610                     };
2611                 };
2612 
2613             return [makeFct('X', 'cos'), makeFct('Y', 'sin'), 0, pi2];
2614         }
2615     });
2616 
2617     return Mat.Geometry;
2618 });
2619