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