1 /*
  2     Copyright 2008,2009
  3         Matthias Ehmann,
  4         Michael Gerhaeuser,
  5         Carsten Miller,
  6         Bianca Valentin,
  7         Alfred Wassermann,
  8         Peter Wilfahrt
  9 
 10     This file is part of JSXGraph.
 11 
 12     JSXGraph is free software: you can redistribute it and/or modify
 13     it under the terms of the GNU Lesser General Public License as published by
 14     the Free Software Foundation, either version 3 of the License, or
 15     (at your option) any later version.
 16 
 17     JSXGraph is distributed in the hope that it will be useful,
 18     but WITHOUT ANY WARRANTY; without even the implied warranty of
 19     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 20     GNU Lesser General Public License for more details.
 21 
 22     You should have received a copy of the GNU Lesser General Public License
 23     along with JSXGraph. If not, see <http://www.gnu.org/licenses/>.
 24 */
 25 
 26 /** 
 27  * @fileoverview This file contains the Math.Geometry namespace for calculating algebraic/geometric
 28  * stuff like intersection points, angles, midpoint, and so on.
 29  */
 30 
 31 
 32 /**
 33  * Math.Geometry namespace definition
 34  * @namespace
 35  */
 36 JXG.Math.Geometry = {};
 37 
 38 // the splitting is necessary due to the shortcut for the circumcircleMidpoint method to circumcenter.
 39 
 40 JXG.extend(JXG.Math.Geometry, {
 41 
 42     /****************************************/
 43     /**** GENERAL GEOMETRIC CALCULATIONS ****/
 44     /****************************************/
 45 
 46     /**
 47      * Calculates the angle defined by the points A, B, C.
 48      * @param {JXG.Point} A A point  or [x,y] array.
 49      * @param {JXG.Point} B Another point or [x,y] array.
 50      * @param {JXG.Point} C A circle - no, of course the third point or [x,y] array.
 51      * @deprecated Use {@link JXG.Math.Geometry#rad} instead.
 52      * @see #rad
 53      * @see #trueAngle
 54      * @returns {Number} The angle in radian measure.
 55      */
 56     angle: function(A, B, C) {
 57         var a = [],
 58             b = [],
 59             c = [],
 60             u, v, s, t;
 61 
 62         if (A.coords == null) {
 63             a[0] = A[0];
 64             a[1] = A[1];
 65         } else {
 66             a[0] = A.coords.usrCoords[1];
 67             a[1] = A.coords.usrCoords[2];
 68         }
 69         if (B.coords == null) {
 70             b[0] = B[0];
 71             b[1] = B[1];
 72         } else {
 73             b[0] = B.coords.usrCoords[1];
 74             b[1] = B.coords.usrCoords[2];
 75         }
 76         if (C.coords == null) {
 77             c[0] = C[0];
 78             c[1] = C[1];
 79         } else {
 80             c[0] = C.coords.usrCoords[1];
 81             c[1] = C.coords.usrCoords[2];
 82         }
 83         u = a[0] - b[0];
 84         v = a[1] - b[1];
 85         s = c[0] - b[0];
 86         t = c[1] - b[1];
 87         return Math.atan2(u * t - v * s, u * s + v * t);
 88     },
 89 
 90     /**
 91      * Calculates the angle defined by the three points A, B, C if you're going from A to C around B counterclockwise.
 92      * @param {JXG.Point} A Point or [x,y] array
 93      * @param {JXG.Point} B Point or [x,y] array
 94      * @param {JXG.Point} C Point or [x,y] array
 95      * @see #rad
 96      * @returns {Number} The angle in degrees.
 97      */
 98     trueAngle: function(A, B, C) {
 99         return this.rad(A, B, C) * 57.295779513082323; // *180.0/Math.PI;
100     },
101 
102     /**
103      * Calculates the internal angle defined by the three points A, B, C if you're going from A to C around B counterclockwise.
104      * @param {JXG.Point} A Point or [x,y] array
105      * @param {JXG.Point} B Point or [x,y] array
106      * @param {JXG.Point} C Point or [x,y] array
107      * @see #trueAngle
108      * @returns {Number} Angle in radians.
109      */
110     rad: function(A, B, C) {
111         var ax, ay, bx, by, cx, cy,
112             phi;
113 
114         if (A.coords == null) {
115             ax = A[0];
116             ay = A[1];
117         } else {
118             ax = A.coords.usrCoords[1];
119             ay = A.coords.usrCoords[2];
120         }
121         if (B.coords == null) {
122             bx = B[0];
123             by = B[1];
124         } else {
125             bx = B.coords.usrCoords[1];
126             by = B.coords.usrCoords[2];
127         }
128         if (C.coords == null) {
129             cx = C[0];
130             cy = C[1];
131         } else {
132             cx = C.coords.usrCoords[1];
133             cy = C.coords.usrCoords[2];
134         }
135 
136         phi = Math.atan2(cy - by, cx - bx) - Math.atan2(ay - by, ax - bx);
137         if (phi < 0) phi += 6.2831853071795862;
138         return phi;
139     },
140 
141     /**
142      * Calculates the bisection between the three points A, B, C. The bisection is defined by two points:
143      * Parameter B and a point with the coordinates calculated in this function.
144      * @param {JXG.Point} A Point
145      * @param {JXG.Point} B Point
146      * @param {JXG.Point} C Point
147      * @param [board=A.board] Reference to the board
148      * @returns {JXG.Coords} Coordinates of the second point defining the bisection.
149      */
150     angleBisector: function(A, B, C, board) {
151         /* First point */
152         var Ac = A.coords.usrCoords,
153             Bc = B.coords.usrCoords,
154             Cc = C.coords.usrCoords,
155             x = Ac[1] - Bc[1],
156             y = Ac[2] - Bc[2],
157             d = Math.sqrt(x * x + y * y),
158             phiA, phiC, phi;
159 
160         if (!JXG.exists(board))
161             board = A.board;
162 
163         x /= d;
164         y /= d;
165 
166         phiA = Math.acos(x);
167         if (y < 0) {
168             phiA *= -1;
169         }
170         if (phiA < 0) {
171             phiA += 2 * Math.PI;
172         }
173 
174         /* Second point */
175         x = Cc[1] - Bc[1];
176         y = Cc[2] - Bc[2];
177         d = Math.sqrt(x * x + y * y);
178         x /= d;
179         y /= d;
180 
181         phiC = Math.acos(x);
182         if (y < 0) {
183             phiC *= -1;
184         }
185         if (phiC < 0) {
186             phiC += 2 * Math.PI;
187         }
188 
189         phi = (phiA + phiC) * 0.5;
190         if (phiA > phiC) {
191             phi += Math.PI;
192         }
193 
194         x = Math.cos(phi) + Bc[1];
195         y = Math.sin(phi) + Bc[2];
196 
197         return new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
198     },
199 
200     /**
201      * Reflects the point along the line.
202      * @param {JXG.Line} line Axis of reflection.
203      * @param {JXG.Point} point Point to reflect.
204      * @param [board=point.board] Reference to the board
205      * @returns {JXG.Coords} Coordinates of the reflected point.
206      */
207     reflection: function(line, point, board) {
208         /* (v,w) defines the slope of the line */
209         var pc = point.coords.usrCoords,
210             p1c = line.point1.coords.usrCoords,
211             p2c = line.point2.coords.usrCoords,
212             x0, y0, x1, y1, v, w, mu;
213 
214         if (!JXG.exists(board))
215             board = point.board;
216 
217         v = p2c[1] - p1c[1];
218         w = p2c[2] - p1c[2];
219 
220         x0 = pc[1] - p1c[1];
221         y0 = pc[2] - p1c[2];
222 
223         mu = (v * y0 - w * x0) / (v * v + w * w);
224 
225         /* point + mu*(-y,x) waere Lotpunkt */
226         x1 = pc[1] + 2 * mu * w;
227         y1 = pc[2] - 2 * mu * v;
228 
229         return new JXG.Coords(JXG.COORDS_BY_USER, [x1,y1], board);
230     },
231 
232     /**
233      * Computes the new position of a point which is rotated
234      * around a second point (called rotpoint) by the angle phi.
235      * @param {JXG.Point} rotpoint Center of the rotation
236      * @param {JXG.Point} point point to be rotated
237      * @param {number} phi rotation angle in arc length
238      * @param {JXG.Board} [board=point.board] Reference to the board
239      * @returns {JXG.Coords} Coordinates of the new position.
240      */
241     rotation: function(rotpoint, point, phi, board) {
242         var pc = point.coords.usrCoords,
243             rotpc = rotpoint.coords.usrCoords,
244             x0, y0, c, s, x1, y1;
245 
246         if (!JXG.exists(board))
247             board = point.board;
248 
249         x0 = pc[1] - rotpc[1];
250         y0 = pc[2] - rotpc[2];
251 
252         c = Math.cos(phi);
253         s = Math.sin(phi);
254 
255         x1 = x0 * c - y0 * s + rotpc[1];
256         y1 = x0 * s + y0 * c + rotpc[2];
257 
258         return new JXG.Coords(JXG.COORDS_BY_USER, [x1,y1], board);
259     },
260 
261     /**
262      * Calculates the coordinates of a point on the perpendicular to the given line through
263      * the given point.
264      * @param {JXG.Line} line A line.
265      * @param {JXG.Point} point Intersection point of line to perpendicular.
266      * @param {JXG.Board} [board=point.board] Reference to the board
267      * @returns {JXG.Coords} Coordinates of a point on the perpendicular to the given line through the given point.
268      */
269     perpendicular: function(line, point, board) {
270         var A = line.point1.coords.usrCoords,
271             B = line.point2.coords.usrCoords,
272             C = point.coords.usrCoords,
273             x, y, change,
274             fmd, emc, d0, d1, den;
275 
276         if (!JXG.exists(board))
277             board = point.board;
278 
279         if (point == line.point1) { // Punkt ist erster Punkt der Linie
280             x = A[1] + B[2] - A[2];
281             y = A[2] - B[1] + A[1];
282             change = true;
283         } else if (point == line.point2) {  // Punkt ist zweiter Punkt der Linie
284             x = B[1] + A[2] - B[2];
285             y = B[2] - A[1] + B[1];
286             change = false;
287         } else if (((Math.abs(A[1] - B[1]) > JXG.Math.eps) &&
288             (Math.abs(C[2] - (A[2] - B[2]) * (C[1] - A[1]) / (A[1] - B[1]) - A[2]) < JXG.Math.eps)) ||
289             ((Math.abs(A[1] - B[1]) <= JXG.Math.eps) && (Math.abs(A[1] - C[1]) < JXG.Math.eps))) { // Punkt liegt auf der Linie
290             x = C[1] + B[2] - C[2];
291             y = C[2] - B[1] + C[1];
292             change = true;
293             if (Math.abs(x - C[1]) < JXG.Math.eps && Math.abs(y - C[2]) < JXG.Math.eps) {
294                 x = C[1] + A[2] - C[2];
295                 y = C[2] - A[1] + C[1];
296                 change = false;
297             }
298         } else { // Punkt liegt nicht auf der Linie -> als zweiter Punkt wird der Lotfusspunkt gewaehlt
299             fmd = A[2] - B[2];
300             emc = A[1] - B[1];
301             d0 = B[1] * fmd - B[2] * emc;
302             d1 = C[1] * emc + C[2] * fmd;
303             den = fmd * fmd + emc * emc;
304             if (Math.abs(den) < JXG.Math.eps) {
305                 den = JXG.Math.eps;
306             }
307             x = (d0 * fmd + d1 * emc) / den;
308             y = (d1 * fmd - d0 * emc) / den;
309             change = true;
310         }
311         return [new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board),change];
312     },
313 
314     /**
315      * @deprecated Please use {@link JXG.Math.Geometry#circumcenter} instead.
316      */
317     circumcenterMidpoint: JXG.shortcut(JXG.Math.Geometry, 'circumcenter'),
318 
319     /**
320      * Calculates the center of the circumcircle of the three given points.
321      * @param {JXG.Point} point1 Point
322      * @param {JXG.Point} point2 Point
323      * @param {JXG.Point} point3 Point
324      * @param {JXG.Board} [board=point1.board] Reference to the board
325      * @returns {JXG.Coords} Coordinates of the center of the circumcircle of the given points.
326      */
327     circumcenter: function(point1, point2, point3, board) {
328         var A = point1.coords.usrCoords,
329             B = point2.coords.usrCoords,
330             C = point3.coords.usrCoords,
331             u, v, den, x, y;
332 
333         if (!JXG.exists(board))
334             board = point1.board;
335 
336         u = ((A[1] - B[1]) * (A[1] + B[1]) + (A[2] - B[2]) * (A[2] + B[2])) * 0.5;
337         v = ((B[1] - C[1]) * (B[1] + C[1]) + (B[2] - C[2]) * (B[2] + C[2])) * 0.5;
338         den = (A[1] - B[1]) * (B[2] - C[2]) - (B[1] - C[1]) * (A[2] - B[2]);
339 
340         if (Math.abs(den) < JXG.Math.eps) {
341             den = JXG.Math.eps;
342         	return new JXG.Coords(JXG.COORDS_BY_USER, [Infinity, Infinity], board);
343         }
344 
345         x = (u * (B[2] - C[2]) - v * (A[2] - B[2])) / den;
346         y = (v * (A[1] - B[1]) - u * (B[1] - C[1])) / den;
347 
348         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
349     },
350 
351     /**
352      * Calculates euclidean norm for two given arrays of the same length.
353      * @param {Array} array1 Array of float or integer.
354      * @param {Array} array2 Array of float or integer.
355      * @returns {Number} Euclidean distance of the given vectors.
356      */
357     distance: function(array1, array2) {
358         var sum = 0,
359             i, len;
360 
361         if (array1.length != array2.length) {
362             return NaN;
363         }
364         len = array1.length;
365         for (i = 0; i < len; i++) {
366             sum += (array1[i] - array2[i]) * (array1[i] - array2[i]);
367         }
368         return Math.sqrt(sum);
369     },
370 
371     /**
372      * Calculates euclidean distance for two given arrays of the same length.
373      * If one of the arrays contains a zero in the first coordinate, and the euclidean distance
374      * is different from zero it is a point at infinity and we return Infinity.
375      * @param {Array} array1 Array containing elements of number.
376      * @param {Array} array2 Array containing elements of type number.
377      * @returns {Number} Euclidean (affine) distance of the given vectors.
378      */
379     affineDistance: function(array1, array2) {
380         var d;
381         if (array1.length != array2.length) {
382             return NaN;
383         }
384         d = this.distance(array1, array2);
385         if (d > JXG.Math.eps && (Math.abs(array1[0]) < JXG.Math.eps || Math.abs(array2[0]) < JXG.Math.eps)) {
386             return Infinity;
387         } else {
388             return d;
389         }
390     },
391 
392     /**
393      * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2
394      * calcStraight determines the visual start point and end point of the line. A segment is only drawn
395      * from start to end point, a straight line is drawn until it meets the boards boundaries.
396      * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point.
397      * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and set by this method.
398      * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set by this method.
399      * @see Line
400      * @see JXG.Line
401      */
402     calcStraight: function(el, point1, point2) {
403         var takePoint1, takePoint2, intersect1, intersect2, straightFirst, straightLast,
404             c, s, i, j, p1, p2;
405 
406         straightFirst = el.visProp.straightfirst;
407         straightLast = el.visProp.straightlast;
408 
409         // If one of the point is an ideal point in homogeneous coordinates
410         // drawing of line segments or rays are not possible.
411         if (Math.abs(point1.scrCoords[0]) < JXG.Math.eps) {
412             straightFirst = true;
413         }
414         if (Math.abs(point2.scrCoords[0]) < JXG.Math.eps) {
415             straightLast = true;
416         }
417 
418         if (!straightFirst && !straightLast) {  // Do nothing in case of line segments (inside or outside of the board)
419             return;
420         }
421 
422         // Compute the stdform of the line in screen coordinates.
423         c = [];
424         c[0] = el.stdform[0] -
425                 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX +
426                 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY;
427         c[1] = el.stdform[1] / el.board.unitX;
428         c[2] = el.stdform[2] / (-el.board.unitY);
429 
430         if (isNaN(c[0] + c[1] + c[2])) return; // p1=p2
431 
432         // Intersect the line with the four borders of the board.
433         s = [];
434         s[0] = JXG.Math.crossProduct(c, [0,0,1]);  // top
435         s[1] = JXG.Math.crossProduct(c, [0,1,0]);  // left
436         s[2] = JXG.Math.crossProduct(c, [-el.board.canvasHeight,0,1]);  // bottom
437         s[3] = JXG.Math.crossProduct(c, [-el.board.canvasWidth,1,0]);   // right
438 
439         // Normalize the intersections
440         for (i = 0; i < 4; i++) {
441             if (Math.abs(s[i][0]) > JXG.Math.eps) {
442                 for (j = 2; j > 0; j--) {
443                     s[i][j] /= s[i][0];
444                 }
445                 s[i][0] = 1.0;
446             }
447         }
448 
449         takePoint1 = false;
450         takePoint2 = false;
451         if (!straightFirst && // Line starts at point1 and point2 is inside the board
452                 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth &&
453                 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight) {
454             takePoint1 = true;
455         }
456         if (!straightLast && // Line ends at point2 and point2 is inside the board
457                 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth &&
458                 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight) {
459             takePoint2 = true;
460         }
461 
462         if (Math.abs(s[1][0]) < JXG.Math.eps) {           // line is parallel to "left", take "top" and "bottom"
463             intersect1 = s[0];                          // top
464             intersect2 = s[2];                          // bottom
465         } else if (Math.abs(s[0][0]) < JXG.Math.eps) {           // line is parallel to "top", take "left" and "right"
466             intersect1 = s[1];                          // left
467             intersect2 = s[3];                          // right
468         } else if (s[1][2] < 0) {                         // left intersection out of board (above)
469             intersect1 = s[0];                          // top
470             if (s[3][2] > el.board.canvasHeight) {        // right intersection out of board (below)
471                 intersect2 = s[2];                      // bottom
472             } else {
473                 intersect2 = s[3];                      // right
474             }
475         } else if (s[1][2] > el.board.canvasHeight) {     // left intersection out of board (below)
476             intersect1 = s[2];                          // bottom
477             if (s[3][2] < 0) {                            // right intersection out of board (above)
478                 intersect2 = s[0];                      // top
479             } else {
480                 intersect2 = s[3];                      // right
481             }
482         } else {
483             intersect1 = s[1];                          // left
484             if (s[3][2] < 0) {                            // right intersection out of board (above)
485                 intersect2 = s[0];                      // top
486             } else if (s[3][2] > el.board.canvasHeight) { // right intersection out of board (below)
487                 intersect2 = s[2];                      // bottom
488             } else {
489                 intersect2 = s[3];                      // right
490             }
491         }
492 
493         intersect1 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect1.slice(1), el.board);
494         intersect2 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect2.slice(1), el.board);
495 
496         /**
497          * At this point we have four points:
498          * point1 and point2 are the first and the second defining point on the line,
499          * intersect1, intersect2 are the intersections of the line with border around the board.
500          */
501         
502         /*
503          * Here we handle rays where both defining points are outside of the board.
504          */
505         if (!takePoint1 && !takePoint2) {              // If both points are outside and the complete ray is outside we do nothing
506             if (!straightFirst && straightLast && // Ray starting at point 1
507                     !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) {
508                 return;
509             } else if (straightFirst && !straightLast && // Ray starting at point 2
510                     !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) {
511                 return;
512             }
513         }
514 
515         /*
516          * If at least one of the definng points is outside of the board
517          * we take intersect1 or intersect2 as one of the end points
518          * The order is also important for arrows of axes
519          */
520         if (!takePoint1) {
521             if (!takePoint2) {                                   
522                 /*
523                  * Two border intersection points are used
524                  */
525                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
526                     p1 = intersect1;
527                     p2 = intersect2;
528                 } else {
529                     p2 = intersect1;
530                     p1 = intersect2;
531                 }
532                     
533                 /*
534                 if (this.isSameDirection(point1, point2, intersect1)) {
535                     if (!this.isSameDirection(point1, point2, intersect2)) {
536                         p2 = intersect1;
537                         p1 = intersect2;
538                     } else {
539                         if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) <= JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) {
540                             p1 = intersect1;
541                             p2 = intersect2;
542                         } else {
543                             p2 = intersect1;
544                             p1 = intersect2;
545                         }
546                     }
547                 } else {
548                     if (this.isSameDirection(point1, point2, intersect2)) {
549                         p1 = intersect1;
550                         p2 = intersect2;
551                     } else {
552                         if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) < JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) {
553                             p2 = intersect1;
554                             p1 = intersect2;
555                         } else {
556                             p1 = intersect1;
557                             p2 = intersect2;
558                         }
559                     }
560                 }
561                 */
562             } else {
563                 /*
564                 * One border intersection points is used 
565                 */
566                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
567                     p1 = intersect1;
568                 } else {
569                     p1 = intersect2;
570                 }
571                 /*
572                 if (this.isSameDirection(point2, point1, intersect1)) { // Instead of point1 the border intersection is taken
573                     p1 = intersect1;
574                 } else {
575                     p1 = intersect2;
576                 }
577                 */
578             }
579         } else {
580             if (!takePoint2) {
581                 /*
582                 * One border intersection points is used 
583                 */
584                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
585                     p2 = intersect2;
586                 } else {
587                     p2 = intersect1;
588                 } /*
589                 if (this.isSameDirection(point1, point2, intersect1)) { // Instead of point2 the border intersection is taken
590                     p2 = intersect1;
591                 } else {
592                     p2 = intersect2;
593                 }
594                 */
595             }
596         }
597 
598         if (p1) point1.setCoordinates(JXG.COORDS_BY_USER, p1.usrCoords.slice(1));
599         if (p2) point2.setCoordinates(JXG.COORDS_BY_USER, p2.usrCoords.slice(1));
600     },
601 
602     /**
603      * The vectors p2-p1 and i2-i1 are supposed collinear.
604      * If their cosine is positive they point into the same direction
605      * otherwise they point in opposite direction
606      * @param {JXG.Coords} p1 
607      * @param {JXG.Coords} p2 
608      * @param {JXG.Coords} i1 
609      * @param {JXG.Coords} i2 
610      * @returns {Boolean} True, if p2-p1 and i2-i1 point into the same direction
611      */
612     isSameDir: function(p1, p2, i1, i2) {
613         var dpx = p2.usrCoords[1] - p1.usrCoords[1],
614             dpy = p2.usrCoords[2] - p1.usrCoords[2],
615             dix = i2.usrCoords[1] - i1.usrCoords[1],
616             diy = i2.usrCoords[2] - i1.usrCoords[2];
617             
618         return dpx * dix + dpy * diy >= 0;
619     },
620     
621     /**
622      * If you're looking from point "start" towards point "s" and can see the point "p", true is returned. Otherwise false.
623      * @param {JXG.Coords} start The point you're standing on.
624      * @param {JXG.Coords} p The point in which direction you're looking.
625      * @param {JXG.Coords} s The point that should be visible.
626      * @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.
627      */
628     isSameDirection: function(start, p, s) {
629         var dx, dy, sx, sy, r = false;
630 
631         dx = p.usrCoords[1] - start.usrCoords[1];
632         dy = p.usrCoords[2] - start.usrCoords[2];
633 
634         sx = s.usrCoords[1] - start.usrCoords[1];
635         sy = s.usrCoords[2] - start.usrCoords[2];
636 
637         if (Math.abs(dx) < JXG.Math.eps) dx = 0;
638         if (Math.abs(dy) < JXG.Math.eps) dy = 0;
639         if (Math.abs(sx) < JXG.Math.eps) sx = 0;
640         if (Math.abs(sy) < JXG.Math.eps) sy = 0;
641 
642         if (dx >= 0 && sx >= 0) {
643             if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) {
644                 r = true;
645             }
646         } else if (dx <= 0 && sx <= 0) {
647             if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) {
648                 r = true;
649             }
650         }
651 
652         return r;
653     },
654 
655     /****************************************/
656     /****          INTERSECTIONS         ****/
657     /****************************************/
658 
659     /**
660      * Calculates the coordinates of the intersection of the given lines.
661      * @param {JXG.Line} line1 Line.
662      * @param {JXG.Line} line2 Line.
663      * @param {JXG.Board} [board=line1.board] Reference to the board
664      * @returns {JXG.Coords} Coordinates of the intersection point of the given lines.
665      */
666     intersectLineLine: function(line1, line2, board) {
667         var A = line1.point1.coords.usrCoords,
668             B = line1.point2.coords.usrCoords,
669             C = line2.point1.coords.usrCoords,
670             D = line2.point2.coords.usrCoords,
671             d0, d1, den, x, y;
672 
673         if (!JXG.exists(board))
674             board = line1.board;
675 
676         d0 = A[1] * B[2] - A[2] * B[1];
677         d1 = C[1] * D[2] - C[2] * D[1];
678         den = (B[2] - A[2]) * (C[1] - D[1]) - (A[1] - B[1]) * (D[2] - C[2]);
679 
680         if (Math.abs(den) < JXG.Math.eps) {
681             den = JXG.Math.eps;
682         }
683         x = (d0 * (C[1] - D[1]) - d1 * (A[1] - B[1])) / den;
684         y = (d1 * (B[2] - A[2]) - d0 * (D[2] - C[2])) / den;
685 
686         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
687     },
688 
689     /**
690      * Calculates the coordinates of the intersection of the given line and circle.
691      * @param {JXG.Circle} circle Circle.
692      * @param {JXG.Line} line Line.
693      * @param {JXG.Board} [board=line.board] Reference to the board
694      * @returns {Array} The coordinates of the intersection points of the given circle with the given line and
695      * the amount of intersection points in the first component of the array.
696      */
697     intersectCircleLine: function(circle, line, board) {
698         var eA = line.point1.coords.usrCoords,
699             eB = line.point2.coords.usrCoords,
700             fM = circle.center.coords.usrCoords,
701             s, d0, d1, b, w, h, r, n1, dx, dy, firstPointX, firstPointY, l, x, y, n1s, firstPoint, secondPoint, d;
702 
703         if (!JXG.exists(board))
704             board = line.board;
705 
706         s = line.point1.Dist(line.point2);
707         if (s > 0) {
708             d0 = circle.center.Dist(line.point1);
709             d1 = circle.center.Dist(line.point2);
710             b = ((d0 * d0) + (s * s) - (d1 * d1)) / (2 * s);
711             w = (d0 * d0) - (b * b);
712             w = (w < 0) ? 0 : w;
713             h = Math.sqrt(w);
714 
715             r = circle.Radius();
716             n1 = Math.sqrt((r * r) - h * h);
717             dx = eB[1] - eA[1];
718             dy = eB[2] - eA[2];
719             firstPointX = fM[1] + (h / s) * dy;
720             firstPointY = fM[2] - (h / s) * dx;
721             d0 = (eB[1] * dy) - (eB[2] * dx);
722             d1 = (firstPointX * dx) + (firstPointY * dy);
723             l = (dy * dy) + (dx * dx);
724             if (Math.abs(l) < JXG.Math.eps) {
725                 l = JXG.Math.eps;
726             }
727             x = ((d0 * dy) + (d1 * dx)) / l;
728             y = ((d1 * dy) - (d0 * dx)) / l;
729             n1s = n1 / s;
730             firstPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x + n1s * dx, y + n1s * dy], board);
731             secondPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x - n1s * dx, y - n1s * dy], board);
732             d = circle.center.coords.distance(JXG.COORDS_BY_USER, firstPoint);
733 
734             if ((r < (d - 1)) || isNaN(d)) {
735                 return [0];
736             } else {
737                 return [2,firstPoint,secondPoint];
738             }
739         }
740         return [0];
741     },
742 
743     /**
744      * Calculates the coordinates of the intersection of the given circles.
745      * @param {JXG.Circle} circle1 Circle.
746      * @param {JXG.Circle} circle2 Circle.
747      * @param {JXG.Board} [board=circle1.board] Reference to the board
748      * @returns {Array} Coordinates of the intersection points of the given circles and the
749      * amount of intersection points in the first component of the array.
750      */
751     intersectCircleCircle: function(circle1, circle2, board) {
752         var intersection = {},
753             r1 = circle1.Radius(),
754             r2 = circle2.Radius(),
755             M1 = circle1.center.coords.usrCoords,
756             M2 = circle2.center.coords.usrCoords,
757             rSum, rDiff, s,
758             dx, dy, a, h;
759 
760         if (!JXG.exists(board))
761             board = circle1.board;
762 
763         rSum = r1 + r2;
764         rDiff = Math.abs(r1 - r2);
765         // Abstand der Mittelpunkte der beiden Kreise
766         s = circle1.center.coords.distance(JXG.COORDS_BY_USER, circle2.center.coords);
767         if (s > rSum) {
768             return [0]; // Kreise schneiden sich nicht, liegen nebeneinander
769         } else if (s < rDiff) {
770             return [0]; // Kreise schneiden sich nicht, liegen ineinander
771         } else {
772             if (s != 0) {
773                 intersection[0] = 1; // es gibt einen Schnitt
774                 dx = M2[1] - M1[1];
775                 dy = M2[2] - M1[2];
776                 a = (s * s - r2 * r2 + r1 * r1) / (2 * s);
777                 h = Math.sqrt(r1 * r1 - a * a);
778                 intersection[1] = new JXG.Coords(JXG.COORDS_BY_USER,
779                     [M1[1] + (a / s) * dx + (h / s) * dy,
780                         M1[2] + (a / s) * dy - (h / s) * dx],
781                     board);
782                 intersection[2] = new JXG.Coords(JXG.COORDS_BY_USER,
783                     [M1[1] + (a / s) * dx - (h / s) * dy,
784                         M1[2] + (a / s) * dy + (h / s) * dx],
785                     board);
786             } else {
787                 return [0]; // vorsichtshalber...
788             }
789             return intersection;
790         }
791     },
792 
793     /**
794      * Computes the intersection of a pair of lines, circles or both.
795      * It uses the internal data array stdform of these elements.
796      * @param {Array} el1 stdform of the first element (line or circle)
797      * @param {Array} el2 stdform of the second element (line or circle)
798      * @param {Number} i Index of the intersection point that should be returned.
799      * @param board Reference to the board.
800      * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points.
801      * Which point will be returned is determined by i.
802      */
803     meet: function(el1, el2, i, board) {
804         var eps = JXG.Math.eps; //    var eps = 0.000001;
805         if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { // line line
806             return this.meetLineLine(el1, el2, i, board);
807         } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { // circle line
808             return this.meetLineCircle(el2, el1, i, board);
809         } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { // line circle
810             return this.meetLineCircle(el1, el2, i, board);
811         } else {  // circle circle
812             return this.meetCircleCircle(el1, el2, i, board);
813         }
814     },
815 
816     /**
817      * Intersection of two lines using the stdform.
818      * @param {Array} l1 stdform of the first line
819      * @param {Array} l2 stdform of the second line
820      * @param {number} i unused
821      * @param {JXG.Board} board Reference to the board.
822      * @returns {JXG.Coords} Coordinates of the intersection point.
823      */
824     meetLineLine: function(l1, l2, i, board) {
825         var s = JXG.Math.crossProduct(l1, l2);
826         if (Math.abs(s[0]) > JXG.Math.eps) {
827             s[1] /= s[0];
828             s[2] /= s[0];
829             s[0] = 1.0;
830         }
831         return new JXG.Coords(JXG.COORDS_BY_USER, s, board);
832     },
833 
834     /**
835      * Intersection of line and circle using the stdform.
836      * @param {Array} lin stdform of the line
837      * @param {Array} circ stdform of the circle
838      * @param {number} i number of the returned intersection point.
839      *   i==0: use the positive square root,
840      *   i==1: use the negative square root.
841      * @param {JXG.Board} board Reference to a board.
842      * @returns {JXG.Coords} Coordinates of the intersection point
843      */
844     meetLineCircle: function(lin, circ, i, board) {
845         var a,b,c,d,n, A,B,C, k,t;
846         if (circ[4] < JXG.Math.eps) { // Radius is zero, return center of circle
847             if (Math.abs( JXG.Math.innerProduct([1,circ[6],circ[7]], lin, 3)) < JXG.Math.eps) {
848                 return new JXG.Coords(JXG.COORDS_BY_USER, circ.slice(6, 8), board);
849             } else {
850                 return new JXG.Coords(JXG.COORDS_BY_USER, [NaN,NaN], board);
851             }
852         }
853         c = circ[0];
854         b = circ.slice(1, 3);
855         a = circ[3];
856         d = lin[0];
857         n = lin.slice(1, 3);
858 
859         // Line is normalized, therefore nn==1 and we can skip some operations:
860         /*
861          var nn = n[0]*n[0]+n[1]*n[1];
862          A = a*nn;
863          B = (b[0]*n[1]-b[1]*n[0])*nn;
864          C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn;
865          */
866         A = a;
867         B = (b[0] * n[1] - b[1] * n[0]);
868         C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c;
869 
870         k = B * B - 4 * A * C;
871         if (k >= 0) {
872             k = Math.sqrt(k);
873             t = [(-B + k) / (2 * A),(-B - k) / (2 * A)];
874             return ((i == 0)
875                 ? new JXG.Coords(JXG.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0],-t[0] * n[0] - d * n[1]], board)
876                 : new JXG.Coords(JXG.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0],-t[1] * n[0] - d * n[1]], board)
877                 );
878             /*
879              new JXG.Coords(JXG.COORDS_BY_USER, [-t[0]*(-n[1])-d*n[0]/nn,-t[0]*n[0]-d*n[1]/nn], this.board),
880              new JXG.Coords(JXG.COORDS_BY_USER, [-t[1]*(-n[1])-d*n[0]/nn,-t[1]*n[0]-d*n[1]/nn], this.board)
881              */
882         } else {
883             return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
884         }
885         // Returns do not work with homogeneous coordinates, yet
886     },
887 
888     /**
889      * Intersection of two circles using the stdform.
890      * @param {Array} circ1 stdform of the first circle
891      * @param {Array} circ2 stdform of the second circle
892      * @param {number} i number of the returned intersection point.
893      *   i==0: use the positive square root,
894      *   i==1: use the negative square root.
895      * @param {JXG.Board} board Reference to the board.
896      * @returns {JXG.Coords} Coordinates of the intersection point
897      */
898     meetCircleCircle: function(circ1, circ2, i, board) {
899         var radicalAxis;
900         if (circ1[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle
901             if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < JXG.Math.eps) {
902                 return new JXG.Coords(JXG.COORDS_BY_USER, circ1.slice(6, 8), board);
903             } else {
904                 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
905             }
906         }
907         if (circ2[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle
908             if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < JXG.Math.eps) {
909                 return new JXG.Coords(JXG.COORDS_BY_USER, circ2.slice(6, 8), board);
910             } else {
911                 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
912             }
913         }
914         radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0],
915             circ2[3] * circ1[1] - circ1[3] * circ2[1],
916             circ2[3] * circ1[2] - circ1[3] * circ2[2],
917             0,1,Infinity, Infinity, Infinity];
918         radicalAxis = JXG.Math.normalize(radicalAxis);
919         return this.meetLineCircle(radicalAxis, circ1, i, board);
920         // Returns do not work with homogeneous coordinates, yet
921     },
922 
923     /**
924      * Compute an intersection of the curves c1 and c2
925      * with a generalized Newton method.
926      * We want to find values t1, t2 such that
927      * c1(t1) = c2(t2), i.e.
928      * (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0).
929      * We set
930      * (e,f) := (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2))
931      *
932      * The Jacobian J is defined by
933      * J = (a, b)
934      *     (c, d)
935      * where
936      * a = c1_x'(t1)
937      * b = -c2_x'(t2)
938      * c = c1_y'(t1)
939      * d = -c2_y'(t2)
940      *
941      * The inverse J^(-1) of J is equal to
942      *  (d, -b)/
943      *  (-c, a) / (ad-bc)
944      *
945      * Then, (t1new, t2new) := (t1,t2) - J^(-1)*(e,f).
946      * If the function meetCurveCurve possesses the properties
947      * t1memo and t2memo then these are taken as start values
948      * for the Newton algorithm.
949      * After stopping of the Newton algorithm the values of t1 and t2 are stored in
950      * t1memo and t2memo.
951      *
952      * @param {JXG.Curve} c1 Curve, Line or Circle
953      * @param {JXG.Curve} c2 Curve, Line or Circle
954      * @param {Number} t1ini start value for t1
955      * @param {Number} t2ini start value for t2
956      * @param {JXG.Board} [board=c1.board] Reference to a board object.
957      * @returns {JXG.Coords} intersection point
958      */
959     meetCurveCurve: function(c1, c2, t1ini, t2ini, board) {
960         var count = 0,
961             t1, t2,
962             a, b, c, d, disc,
963             e, f, F,
964             D00, D01,
965             D10, D11;
966 
967         if (!JXG.exists(board))
968             board = c1.board;
969 
970         if (arguments.callee.t1memo) {
971             t1 = arguments.callee.t1memo;
972             t2 = arguments.callee.t2memo;
973         } else {
974             t1 = t1ini;
975             t2 = t2ini;
976         }
977         /*
978          if (t1>c1.maxX()) { t1 = c1.maxX(); }
979          if (t1<c1.minX()) { t1 = c1.minX(); }
980          if (t2>c2.maxX()) { t2 = c2.maxX(); }
981          if (t2<c2.minX()) { t2 = c2.minX(); }
982          */
983         e = c1.X(t1) - c2.X(t2);
984         f = c1.Y(t1) - c2.Y(t2);
985         F = e * e + f * f;
986 
987         D00 = c1.board.D(c1.X, c1);
988         D01 = c2.board.D(c2.X, c2);
989         D10 = c1.board.D(c1.Y, c1);
990         D11 = c2.board.D(c2.Y, c2);
991 
992         while (F > JXG.Math.eps && count < 10) {
993             a = D00(t1);
994             b = -D01(t2);
995             c = D10(t1);
996             d = -D11(t2);
997             disc = a * d - b * c;
998             t1 -= (d * e - b * f) / disc;
999             t2 -= (a * f - c * e) / disc;
1000             e = c1.X(t1) - c2.X(t2);
1001             f = c1.Y(t1) - c2.Y(t2);
1002             F = e * e + f * f;
1003             count++;
1004         }
1005         //console.log(t1+' '+t2);
1006 
1007         arguments.callee.t1memo = t1;
1008         arguments.callee.t2memo = t2;
1009 
1010         //return (new JXG.Coords(JXG.COORDS_BY_USER, [2,2], this.board));
1011         if (Math.abs(t1) < Math.abs(t2)) {
1012             return (new JXG.Coords(JXG.COORDS_BY_USER, [c1.X(t1),c1.Y(t1)], board));
1013         } else {
1014             return (new JXG.Coords(JXG.COORDS_BY_USER, [c2.X(t2),c2.Y(t2)], board));
1015         }
1016     },
1017 
1018     /**
1019      * order of input does not matter for el1 and el2.
1020      * @param {JXG.Curve,JXG.Line} el1 Curve or Line
1021      * @param {JXG.Curve,JXG.Line} el2 Curve or Line
1022      * @param {?} nr
1023      * @param {JXG.Board} [board=el1.board] Reference to a board object.
1024      * @returns {JXG.Coords} Intersection point
1025      */
1026     meetCurveLine: function(el1, el2, nr, board) {
1027         var t, t2, i, cu, li, func, z,
1028             tnew, steps, delta, tstart, tend, cux, cuy;
1029 
1030         if (!JXG.exists(board))
1031             board = el1.board;
1032 
1033         //for (i=0;i<arguments.length-1;i++) {
1034         for (i = 0; i <= 1; i++) {
1035             if (arguments[i].elementClass == JXG.OBJECT_CLASS_CURVE) {
1036                 cu = arguments[i];
1037             } else if (arguments[i].elementClass == JXG.OBJECT_CLASS_LINE) {
1038                 li = arguments[i];
1039             } else
1040                 throw new Error("JSXGraph: Can't call meetCurveLine with parent class " + (arguments[i].elementClass) + ".");
1041         }
1042 
1043         func = function(t) {
1044             return li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t);
1045         };
1046 
1047         if (arguments.callee.t1memo) {
1048             tstart = arguments.callee.t1memo;
1049             t = JXG.Math.Numerics.root(func, tstart);
1050         } else {
1051             tstart = cu.minX();
1052             tend = cu.maxX();
1053             t = JXG.Math.Numerics.root(func, [tstart,tend]);
1054         }
1055         arguments.callee.t1memo = t;
1056         cux = cu.X(t);
1057         cuy = cu.Y(t);
1058 
1059         if (nr == 1) {
1060             if (arguments.callee.t2memo) {
1061                 tstart = arguments.callee.t2memo;
1062                 t2 = JXG.Math.Numerics.root(func, tstart);
1063             }
1064             if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) {
1065                 steps = 20;
1066                 delta = (cu.maxX() - cu.minX()) / steps;
1067                 tnew = cu.minX();
1068                 for (i = 0; i < steps; i++) {
1069                     t2 = JXG.Math.Numerics.root(func, [tnew,tnew + delta]);
1070                     if (Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1) {
1071                         break;
1072                     }
1073                     tnew += delta;
1074                 }
1075             }
1076             t = t2;
1077             arguments.callee.t2memo = t;
1078         }
1079 
1080         if (Math.abs(func(t)) > JXG.Math.eps) {
1081             z = 0.0;
1082         } else {
1083             z = 1.0;
1084         }
1085 
1086         return (new JXG.Coords(JXG.COORDS_BY_USER, [z, cu.X(t),cu.Y(t)], board));
1087     },
1088 
1089 
1090 
1091     /****************************************/
1092     /****           PROJECTIONS          ****/
1093     /****************************************/
1094 
1095     /**
1096      * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the
1097      * nearest one of the two intersection points of the line through the given point and the circles
1098      * center.
1099      * @param {JXG.Point} point Point to project.
1100      * @param {JXG.Circle} circle Circle on that the point is projected.
1101      * @param {JXG.Board} [board=point.board] Reference to the board
1102      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
1103      */
1104     projectPointToCircle: function(point, circle, board) {
1105         var dist = point.coords.distance(JXG.COORDS_BY_USER, circle.center.coords),
1106             P = point.coords.usrCoords,
1107             M = circle.center.coords.usrCoords,
1108             x, y, factor;
1109 
1110         if (!JXG.exists(board))
1111             board = point.board;
1112 
1113         if (Math.abs(dist) < JXG.Math.eps) {
1114             dist = JXG.Math.eps;
1115         }
1116         factor = circle.Radius() / dist;
1117         x = M[1] + factor * (P[1] - M[1]);
1118         y = M[2] + factor * (P[2] - M[2]);
1119 
1120         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
1121     },
1122 
1123     /**
1124      * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the
1125      * intersection point of the given line and its perpendicular through the given point.
1126      * @param {JXG.Point} point Point to project.
1127      * @param {JXG.Line} line Line on that the point is projected.
1128      * @param {JXG.Board} [board=point.board] Reference to a board.
1129      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line.
1130      */
1131     projectPointToLine: function(point, line, board) {
1132         // Homogeneous version
1133         var v = [0,line.stdform[1],line.stdform[2]];
1134 
1135         if (!JXG.exists(board))
1136             board = point.board;
1137 
1138         v = JXG.Math.crossProduct(v, point.coords.usrCoords);
1139 
1140         return this.meetLineLine(v, line.stdform, 0, board);
1141     },
1142 
1143     /**
1144      * Calculates the coordinates of the projection of a given point on a given curve.
1145      * Uses {@link #projectCoordsToCurve}.
1146      * @param {JXG.Point} point Point to project.
1147      * @param {JXG.Curve} curve Curve on that the point is projected.
1148      * @param {JXG.Board} [board=point.board] Reference to a board.
1149      * @see #projectCoordsToCurve
1150      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph.
1151      */
1152     projectPointToCurve: function(point, curve, board) {
1153         if (!JXG.exists(board))
1154             board = point.board;
1155 
1156         var x = point.X(),
1157             y = point.Y(),
1158             t = point.position || 0.0, //(curve.minX()+curve.maxX())*0.5,
1159             result = this.projectCoordsToCurve(x, y, t, curve, board);
1160 
1161         point.position = result[1];      // side effect !
1162         return result[0];
1163     },
1164 
1165     /**
1166      * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of
1167      * function graphs this is the
1168      * intersection point of the curve and the parallel to y-axis through the given point.
1169      * @param {Number} x coordinate to project.
1170      * @param {Number} y coordinate to project.
1171      * @param {Number} t start value for newtons method
1172      * @param {JXG.Curve} curve Curve on that the point is projected.
1173      * @param {JXG.Board} [board=curve.board] Reference to a board.
1174      * @see #projectPointToCurve
1175      * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and
1176      * the position on the curve.
1177      */
1178     projectCoordsToCurve: function(x, y, t, curve, board) {
1179         var newCoords, x0, y0, x1, y1, den, i, mindist, dist, lbda, j,
1180             infty = 1000000.0, minfunc, tnew, fnew, fold, delta, steps;
1181 
1182         if (!JXG.exists(board))
1183             board = curve.board;
1184 
1185         if (curve.visProp.curvetype == 'parameter' || curve.visProp.curvetype == 'polar') {
1186             // Function to minimize
1187             minfunc = function(t) {
1188                 var dx = x - curve.X(t),
1189                     dy = y - curve.Y(t);
1190                 return dx * dx + dy * dy;
1191             };
1192 
1193             fold = minfunc(t);
1194             steps = 20;
1195             delta = (curve.maxX() - curve.minX()) / steps;
1196             tnew = curve.minX();
1197             for (j = 0; j < steps; j++) {
1198                 fnew = minfunc(tnew);
1199                 if (fnew < fold) {
1200                     t = tnew;
1201                     fold = fnew;
1202                 }
1203                 tnew += delta;
1204             }
1205             t = JXG.Math.Numerics.root(JXG.Math.Numerics.D(minfunc), t);
1206 
1207             if (t < curve.minX()) {
1208                 t = curve.maxX() + t - curve.minX();
1209             } // Cyclically
1210             if (t > curve.maxX()) {
1211                 t = curve.minX() + t - curve.maxX();
1212             }
1213             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [curve.X(t),curve.Y(t)], board);
1214         } else if (curve.visProp.curvetype == 'plot') {
1215             mindist = infty;
1216             for (i = 0; i < curve.numberPoints; i++) {
1217                 x0 = x - curve.X(i);
1218                 y0 = y - curve.Y(i);
1219                 dist = Math.sqrt(x0 * x0 + y0 * y0);
1220                 if (dist < mindist) {
1221                     mindist = dist;
1222                     t = i;
1223                 }
1224                 if (i == curve.numberPoints - 1) {
1225                     continue;
1226                 }
1227 
1228                 x1 = curve.X(i + 1) - curve.X(i);
1229                 y1 = curve.Y(i + 1) - curve.Y(i);
1230                 den = x1 * x1 + y1 * y1;
1231                 if (den >= JXG.Math.eps) {
1232                     lbda = (x0 * x1 + y0 * y1) / den;
1233                     dist = Math.sqrt(x0 * x0 + y0 * y0 - lbda * (x0 * x1 + y0 * y1));
1234                 } else {
1235                     lbda = 0.0;
1236                     dist = Math.sqrt(x0 * x0 + y0 * y0);
1237                 }
1238                 if (lbda >= 0.0 && lbda <= 1.0 && dist < mindist) {
1239                     t = i + lbda;
1240                     mindist = dist;
1241                 }
1242             }
1243             i = Math.floor(t);
1244             lbda = t - i;
1245             if (i < curve.numberPoints - 1) {
1246                 x = lbda * curve.X(i + 1) + (1.0 - lbda) * curve.X(i);
1247                 y = lbda * curve.Y(i + 1) + (1.0 - lbda) * curve.Y(i);
1248             } else {
1249                 x = curve.X(i);
1250                 y = curve.Y(i);
1251             }
1252             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
1253         } else {             // functiongraph
1254             t = x;
1255             x = t; //curve.X(t);
1256             y = curve.Y(t);
1257             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
1258         }
1259         return [curve.updateTransform(newCoords), t];
1260     },
1261 
1262     /**
1263      * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of
1264      * one or more curves of curveType 'plot'. Uses {@link #projectPointToCurve}.
1265      * @param {JXG.Point} point Point to project.
1266      * @param {JXG.Turtle} turtle on that the point is projected.
1267      * @param {JXG.Board} [board=point.board] Reference to a board.
1268      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle.
1269      */
1270     projectPointToTurtle: function(point, turtle, board) {
1271         var newCoords, t, x, y, i,
1272             np = 0,
1273             npmin = 0,
1274             mindist = 1000000.0,
1275             dist, el, minEl,
1276             len = turtle.objects.length;
1277 
1278         if (!JXG.exists(board))
1279             board = point.board;
1280 
1281         for (i = 0; i < len; i++) {  // run through all curves of this turtle
1282             el = turtle.objects[i];
1283             if (el.elementClass == JXG.OBJECT_CLASS_CURVE) {
1284                 newCoords = this.projectPointToCurve(point, el);
1285                 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords);
1286                 if (dist < mindist) {
1287                     x = newCoords.usrCoords[1];
1288                     y = newCoords.usrCoords[2];
1289                     t = point.position;
1290                     mindist = dist;
1291                     minEl = el;
1292                     npmin = np;
1293                 }
1294                 np += el.numberPoints;
1295             }
1296         }
1297         newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
1298         point.position = t + npmin;
1299         return minEl.updateTransform(newCoords);
1300     },
1301 
1302     /**
1303      * Trivial projection of a point to another point.
1304      * @param {JXG.Point} point Point to project (not used).
1305      * @param {JXG.Point} dest Point on that the point is projected.
1306      * @param {JXG.Board} [board=point.board] Reference to the board (not used).
1307      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
1308      */
1309     projectPointToPoint: function(point, dest, board) {
1310         return dest.coords;
1311     }
1312     
1313 });
1314