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