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