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