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