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