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, /** @lends 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, m1, m2;
332             //u, v, den, m1, y, eps = JXG.Math.eps;
333 
334         if (!JXG.exists(board))
335             board = point1.board;
336 /*
337         u = ((A[1] - B[1]) * (A[1] + B[1]) + (A[2] - B[2]) * (A[2] + B[2])) * 0.5;
338         v = ((B[1] - C[1]) * (B[1] + C[1]) + (B[2] - C[2]) * (B[2] + C[2])) * 0.5;
339         den = (A[1] - B[1]) * (B[2] - C[2]) - (B[1] - C[1]) * (A[2] - B[2]);
340 
341         if (Math.abs(den) < eps) {
342             den = eps;
343         	return new JXG.Coords(JXG.COORDS_BY_USER, [Infinity, Infinity], board);
344         }
345 
346         x = (u * (B[2] - C[2]) - v * (A[2] - B[2])) / den;
347         y = (v * (A[1] - B[1]) - u * (B[1] - C[1])) / den;
348 
349         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
350 */
351         u = [B[0]-A[0], -B[2]+A[2], B[1]-A[1]];
352         v = [(A[0]+B[0])*0.5, (A[1]+B[1])*0.5, (A[2]+B[2])*0.5];
353         m1 = JXG.Math.crossProduct(u, v);
354         u = [C[0]-B[0], -C[2]+B[2], C[1]-B[1]];
355         v = [(B[0]+C[0])*0.5, (B[1]+C[1])*0.5, (B[2]+C[2])*0.5];
356         m2 = JXG.Math.crossProduct(u, v);
357 
358         return new JXG.Coords(JXG.COORDS_BY_USER, JXG.Math.crossProduct(m1, m2), board);
359     },
360 
361     /**
362      * Calculates euclidean norm for two given arrays of the same length.
363      * @param {Array} array1 Array of float or integer.
364      * @param {Array} array2 Array of float or integer.
365      * @returns {Number} Euclidean distance of the given vectors.
366      */
367     distance: function(array1, array2) {
368         var sum = 0,
369             i, len;
370 
371         if (array1.length != array2.length) {
372             return NaN;
373         }
374         len = array1.length;
375         for (i = 0; i < len; i++) {
376             sum += (array1[i] - array2[i]) * (array1[i] - array2[i]);
377         }
378         return Math.sqrt(sum);
379     },
380 
381     /**
382      * Calculates euclidean distance for two given arrays of the same length.
383      * If one of the arrays contains a zero in the first coordinate, and the euclidean distance
384      * is different from zero it is a point at infinity and we return Infinity.
385      * @param {Array} array1 Array containing elements of number.
386      * @param {Array} array2 Array containing elements of type number.
387      * @returns {Number} Euclidean (affine) distance of the given vectors.
388      */
389     affineDistance: function(array1, array2) {
390         var d;
391         if (array1.length != array2.length) {
392             return NaN;
393         }
394         d = this.distance(array1, array2);
395         if (d > JXG.Math.eps && (Math.abs(array1[0]) < JXG.Math.eps || Math.abs(array2[0]) < JXG.Math.eps)) {
396             return Infinity;
397         } else {
398             return d;
399         }
400     },
401 
402     /**
403      * A line can be a segment, a straight, or a ray. so it is not always delimited by point1 and point2
404      * calcStraight determines the visual start point and end point of the line. A segment is only drawn
405      * from start to end point, a straight line is drawn until it meets the boards boundaries.
406      * @param {JXG.Line} el Reference to a line object, that needs calculation of start and end point.
407      * @param {JXG.Coords} point1 Coordinates of the point where line drawing begins. This value is calculated and set by this method.
408      * @param {JXG.Coords} point2 Coordinates of the point where line drawing ends. This value is calculated and set by this method.
409      * @param {Number} margin Optional margin, to avoid the display of the small sides
410      * of lines.
411      * @see Line
412      * @see JXG.Line
413      */
414     calcStraight: function(el, point1, point2, margin) {
415         var takePoint1, takePoint2, intersect1, intersect2, straightFirst, straightLast,
416             c, s, i, j, p1, p2;
417 
418         if (margin == null) { 
419             margin = 10;   // Enlarge the drawable region slightly. This hides the small sides
420                            // of thick lines in most cases.
421         }
422         
423         straightFirst = el.visProp.straightfirst;
424         straightLast = el.visProp.straightlast;
425 
426         // If one of the point is an ideal point in homogeneous coordinates
427         // drawing of line segments or rays are not possible.
428         if (Math.abs(point1.scrCoords[0]) < JXG.Math.eps) {
429             straightFirst = true;
430         }
431         if (Math.abs(point2.scrCoords[0]) < JXG.Math.eps) {
432             straightLast = true;
433         }
434 
435         if (!straightFirst && !straightLast) {  // Do nothing in case of line segments (inside or outside of the board)
436             return;
437         }
438 
439         // Compute the stdform of the line in screen coordinates.
440         c = [];
441         c[0] = el.stdform[0] -
442                 el.stdform[1] * el.board.origin.scrCoords[1] / el.board.unitX +
443                 el.stdform[2] * el.board.origin.scrCoords[2] / el.board.unitY;
444         c[1] = el.stdform[1] / el.board.unitX;
445         c[2] = el.stdform[2] / (-el.board.unitY);
446 
447         if (isNaN(c[0] + c[1] + c[2])) return; // p1=p2
448 
449         // Intersect the line with the four borders of the board.
450         s = [];
451         s[0] = JXG.Math.crossProduct(c, [margin,0,1]);  // top
452         s[1] = JXG.Math.crossProduct(c, [margin,1,0]);  // left
453         s[2] = JXG.Math.crossProduct(c, [-margin-el.board.canvasHeight,0,1]);  // bottom
454         s[3] = JXG.Math.crossProduct(c, [-margin-el.board.canvasWidth,1,0]);   // right
455         
456         // Normalize the intersections
457         for (i = 0; i < 4; i++) {
458             if (Math.abs(s[i][0]) > JXG.Math.eps) {
459                 for (j = 2; j > 0; j--) {
460                     s[i][j] /= s[i][0];
461                 }
462                 s[i][0] = 1.0;
463             }
464         }
465 
466         takePoint1 = false;
467         takePoint2 = false;
468         if (!straightFirst && // Line starts at point1 and point1 is inside the board
469                 Math.abs(point1.usrCoords[0]) >= JXG.Math.eps &&
470                 point1.scrCoords[1] >= 0.0 && point1.scrCoords[1] <= el.board.canvasWidth &&
471                 point1.scrCoords[2] >= 0.0 && point1.scrCoords[2] <= el.board.canvasHeight) {
472             takePoint1 = true;
473         }
474         if (!straightLast && // Line ends at point2 and point2 is inside the board
475                 Math.abs(point2.usrCoords[0]) >= JXG.Math.eps &&
476                 point2.scrCoords[1] >= 0.0 && point2.scrCoords[1] <= el.board.canvasWidth &&
477                 point2.scrCoords[2] >= 0.0 && point2.scrCoords[2] <= el.board.canvasHeight) {
478             takePoint2 = true;
479         }
480 
481         if (Math.abs(s[1][0]) < JXG.Math.eps) {           // line is parallel to "left", take "top" and "bottom"
482             intersect1 = s[0];                          // top
483             intersect2 = s[2];                          // bottom
484         } else if (Math.abs(s[0][0]) < JXG.Math.eps) {           // line is parallel to "top", take "left" and "right"
485             intersect1 = s[1];                          // left
486             intersect2 = s[3];                          // right
487         } else if (s[1][2] < 0) {                         // left intersection out of board (above)
488             intersect1 = s[0];                          // top
489             if (s[3][2] > el.board.canvasHeight) {        // right intersection out of board (below)
490                 intersect2 = s[2];                      // bottom
491             } else {
492                 intersect2 = s[3];                      // right
493             }
494         } else if (s[1][2] > el.board.canvasHeight) {     // left intersection out of board (below)
495             intersect1 = s[2];                          // bottom
496             if (s[3][2] < 0) {                            // right intersection out of board (above)
497                 intersect2 = s[0];                      // top
498             } else {
499                 intersect2 = s[3];                      // right
500             }
501         } else {
502             intersect1 = s[1];                          // left
503             if (s[3][2] < 0) {                            // right intersection out of board (above)
504                 intersect2 = s[0];                      // top
505             } else if (s[3][2] > el.board.canvasHeight) { // right intersection out of board (below)
506                 intersect2 = s[2];                      // bottom
507             } else {
508                 intersect2 = s[3];                      // right
509             }
510         }
511 
512         intersect1 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect1.slice(1), el.board);
513         intersect2 = new JXG.Coords(JXG.COORDS_BY_SCREEN, intersect2.slice(1), el.board);
514 
515         /**
516          * At this point we have four points:
517          * point1 and point2 are the first and the second defining point on the line,
518          * intersect1, intersect2 are the intersections of the line with border around the board.
519          */
520         
521         /*
522          * Here we handle rays where both defining points are outside of the board.
523          */
524         if (!takePoint1 && !takePoint2) {              // If both points are outside and the complete ray is outside we do nothing
525             if (!straightFirst && straightLast && // Ray starting at point 1
526                     !this.isSameDirection(point1, point2, intersect1) && !this.isSameDirection(point1, point2, intersect2)) {
527                 return;
528             } else if (straightFirst && !straightLast && // Ray starting at point 2
529                     !this.isSameDirection(point2, point1, intersect1) && !this.isSameDirection(point2, point1, intersect2)) {
530                 return;
531             }
532         }
533 
534         /*
535          * If at least one of the defining points is outside of the board
536          * we take intersect1 or intersect2 as one of the end points
537          * The order is also important for arrows of axes
538          */
539         if (!takePoint1) {
540             if (!takePoint2) {                                   
541                 /*
542                  * Two border intersection points are used
543                  */
544                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
545                     p1 = intersect1;
546                     p2 = intersect2;
547                 } else {
548                     p2 = intersect1;
549                     p1 = intersect2;
550                 }
551                     
552                 /*
553                 if (this.isSameDirection(point1, point2, intersect1)) {
554                     if (!this.isSameDirection(point1, point2, intersect2)) {
555                         p2 = intersect1;
556                         p1 = intersect2;
557                     } else {
558                         if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) <= JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) {
559                             p1 = intersect1;
560                             p2 = intersect2;
561                         } else {
562                             p2 = intersect1;
563                             p1 = intersect2;
564                         }
565                     }
566                 } else {
567                     if (this.isSameDirection(point1, point2, intersect2)) {
568                         p1 = intersect1;
569                         p2 = intersect2;
570                     } else {
571                         if (JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect1.usrCoords) < JXG.Math.Geometry.affineDistance(point2.usrCoords, intersect2.usrCoords)) {
572                             p2 = intersect1;
573                             p1 = intersect2;
574                         } else {
575                             p1 = intersect1;
576                             p2 = intersect2;
577                         }
578                     }
579                 }
580                 */
581             } else {
582                 /*
583                 * One border intersection points is used 
584                 */
585                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
586                     p1 = intersect1;
587                 } else {
588                     p1 = intersect2;
589                 }
590                 /*
591                 if (this.isSameDirection(point2, point1, intersect1)) { // Instead of point1 the border intersection is taken
592                     p1 = intersect1;
593                 } else {
594                     p1 = intersect2;
595                 }
596                 */
597             }
598         } else {
599             if (!takePoint2) {
600                 /*
601                 * One border intersection points is used 
602                 */
603                 if (this.isSameDir(point1, point2, intersect1, intersect2)) {
604                     p2 = intersect2;
605                 } else {
606                     p2 = intersect1;
607                 } /*
608                 if (this.isSameDirection(point1, point2, intersect1)) { // Instead of point2 the border intersection is taken
609                     p2 = intersect1;
610                 } else {
611                     p2 = intersect2;
612                 }
613                 */
614             }
615         }
616 
617         if (p1) point1.setCoordinates(JXG.COORDS_BY_USER, p1.usrCoords.slice(1));
618         if (p2) point2.setCoordinates(JXG.COORDS_BY_USER, p2.usrCoords.slice(1));
619     },
620 
621     /**
622      * The vectors p2-p1 and i2-i1 are supposed to be collinear.
623      * If their cosine is positive they point into the same direction
624      * otherwise they point in opposite direction
625      * @param {JXG.Coords} p1 
626      * @param {JXG.Coords} p2 
627      * @param {JXG.Coords} i1 
628      * @param {JXG.Coords} i2 
629      * @returns {Boolean} True, if p2-p1 and i2-i1 point into the same direction
630      */
631     isSameDir: function(p1, p2, i1, i2) {
632         var dpx = p2.usrCoords[1] - p1.usrCoords[1],
633             dpy = p2.usrCoords[2] - p1.usrCoords[2],
634             dix = i2.usrCoords[1] - i1.usrCoords[1],
635             diy = i2.usrCoords[2] - i1.usrCoords[2];
636             
637         if (Math.abs(p2.usrCoords[0])<JXG.Math.eps) {
638             dpx = p2.usrCoords[1];
639             dpy = p2.usrCoords[2];
640         }
641         if (Math.abs(p1.usrCoords[0])<JXG.Math.eps) {
642             dpx = -p1.usrCoords[1];
643             dpy = -p1.usrCoords[2];
644         }
645             
646         return dpx * dix + dpy * diy >= 0;
647     },
648     
649     /**
650      * If you're looking from point "start" towards point "s" and can see the point "p", true is returned. Otherwise false.
651      * @param {JXG.Coords} start The point you're standing on.
652      * @param {JXG.Coords} p The point in which direction you're looking.
653      * @param {JXG.Coords} s The point that should be visible.
654      * @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.
655      */
656     isSameDirection: function(start, p, s) {
657         var dx, dy, sx, sy, r = false;
658 
659         dx = p.usrCoords[1] - start.usrCoords[1];
660         dy = p.usrCoords[2] - start.usrCoords[2];
661 
662         sx = s.usrCoords[1] - start.usrCoords[1];
663         sy = s.usrCoords[2] - start.usrCoords[2];
664 
665         if (Math.abs(dx) < JXG.Math.eps) dx = 0;
666         if (Math.abs(dy) < JXG.Math.eps) dy = 0;
667         if (Math.abs(sx) < JXG.Math.eps) sx = 0;
668         if (Math.abs(sy) < JXG.Math.eps) sy = 0;
669 
670         if (dx >= 0 && sx >= 0) {
671             if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) {
672                 r = true;
673             }
674         } else if (dx <= 0 && sx <= 0) {
675             if ((dy >= 0 && sy >= 0) || (dy <= 0 && sy <= 0)) {
676                 r = true;
677             }
678         }
679 
680         return r;
681     },
682 
683     /****************************************/
684     /****          INTERSECTIONS         ****/
685     /****************************************/
686 
687     /**
688      * Calculates the coordinates of the intersection of the given lines.
689      * @deprecated 
690      * @param {JXG.Line} line1 Line.
691      * @param {JXG.Line} line2 Line.
692      * @param {JXG.Board} [board=line1.board] Reference to the board
693      * @returns {JXG.Coords} Coordinates of the intersection point of the given lines.
694      */
695     intersectLineLine: function(line1, line2, board) {
696         var A = line1.point1.coords.usrCoords,
697             B = line1.point2.coords.usrCoords,
698             C = line2.point1.coords.usrCoords,
699             D = line2.point2.coords.usrCoords,
700             d0, d1, den, x, y;
701 
702         if (!JXG.exists(board))
703             board = line1.board;
704 
705         d0 = A[1] * B[2] - A[2] * B[1];
706         d1 = C[1] * D[2] - C[2] * D[1];
707         den = (B[2] - A[2]) * (C[1] - D[1]) - (A[1] - B[1]) * (D[2] - C[2]);
708 
709         if (Math.abs(den) < JXG.Math.eps) {
710             den = JXG.Math.eps;
711         }
712         x = (d0 * (C[1] - D[1]) - d1 * (A[1] - B[1])) / den;
713         y = (d1 * (B[2] - A[2]) - d0 * (D[2] - C[2])) / den;
714 
715         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
716     },
717 
718     /**
719      * Calculates the coordinates of the intersection of the given line and circle.
720      * @deprecated 
721      * @param {JXG.Circle} circle Circle.
722      * @param {JXG.Line} line Line.
723      * @param {JXG.Board} [board=line.board] Reference to the board
724      * @returns {Array} The coordinates of the intersection points of the given circle with the given line and
725      * the amount of intersection points in the first component of the array.
726      */
727     intersectCircleLine: function(circle, line, board) {
728         var eA = line.point1.coords.usrCoords,
729             eB = line.point2.coords.usrCoords,
730             fM = circle.center.coords.usrCoords,
731             s, d0, d1, b, w, h, r, n1, dx, dy, firstPointX, firstPointY, l, x, y, n1s, firstPoint, secondPoint, d;
732 
733         if (!JXG.exists(board))
734             board = line.board;
735 
736         s = line.point1.Dist(line.point2);
737         if (s > 0) {
738             d0 = circle.center.Dist(line.point1);
739             d1 = circle.center.Dist(line.point2);
740             b = ((d0 * d0) + (s * s) - (d1 * d1)) / (2 * s);
741             w = (d0 * d0) - (b * b);
742             w = (w < 0) ? 0 : w;
743             h = Math.sqrt(w);
744 
745             r = circle.Radius();
746             n1 = Math.sqrt((r * r) - h * h);
747             dx = eB[1] - eA[1];
748             dy = eB[2] - eA[2];
749             firstPointX = fM[1] + (h / s) * dy;
750             firstPointY = fM[2] - (h / s) * dx;
751             d0 = (eB[1] * dy) - (eB[2] * dx);
752             d1 = (firstPointX * dx) + (firstPointY * dy);
753             l = (dy * dy) + (dx * dx);
754             if (Math.abs(l) < JXG.Math.eps) {
755                 l = JXG.Math.eps;
756             }
757             x = ((d0 * dy) + (d1 * dx)) / l;
758             y = ((d1 * dy) - (d0 * dx)) / l;
759             n1s = n1 / s;
760             firstPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x + n1s * dx, y + n1s * dy], board);
761             secondPoint = new JXG.Coords(JXG.COORDS_BY_USER, [x - n1s * dx, y - n1s * dy], board);
762             d = circle.center.coords.distance(JXG.COORDS_BY_USER, firstPoint);
763 
764             if ((r < (d - 1)) || isNaN(d)) {
765                 return [0];
766             } else {
767                 return [2,firstPoint,secondPoint];
768             }
769         }
770         return [0];
771     },
772 
773     /**
774      * Calculates the coordinates of the intersection of the given circles.
775      * @deprecated 
776      * @param {JXG.Circle} circle1 Circle.
777      * @param {JXG.Circle} circle2 Circle.
778      * @param {JXG.Board} [board=circle1.board] Reference to the board
779      * @returns {Array} Coordinates of the intersection points of the given circles and the
780      * amount of intersection points in the first component of the array.
781      */
782     intersectCircleCircle: function(circle1, circle2, board) {
783         var intersection = {},
784             r1 = circle1.Radius(),
785             r2 = circle2.Radius(),
786             M1 = circle1.center.coords.usrCoords,
787             M2 = circle2.center.coords.usrCoords,
788             rSum, rDiff, s,
789             dx, dy, a, h;
790 
791         if (!JXG.exists(board))
792             board = circle1.board;
793 
794         rSum = r1 + r2;
795         rDiff = Math.abs(r1 - r2);
796         // Abstand der Mittelpunkte der beiden Kreise
797         s = circle1.center.coords.distance(JXG.COORDS_BY_USER, circle2.center.coords);
798         if (s > rSum) {
799             return [0]; // Kreise schneiden sich nicht, liegen nebeneinander
800         } else if (s < rDiff) {
801             return [0]; // Kreise schneiden sich nicht, liegen ineinander
802         } else {
803             if (s != 0) {
804                 intersection[0] = 1; // es gibt einen Schnitt
805                 dx = M2[1] - M1[1];
806                 dy = M2[2] - M1[2];
807                 a = (s * s - r2 * r2 + r1 * r1) / (2 * s);
808                 h = Math.sqrt(r1 * r1 - a * a);
809                 intersection[1] = new JXG.Coords(JXG.COORDS_BY_USER,
810                     [M1[1] + (a / s) * dx + (h / s) * dy,
811                         M1[2] + (a / s) * dy - (h / s) * dx],
812                     board);
813                 intersection[2] = new JXG.Coords(JXG.COORDS_BY_USER,
814                     [M1[1] + (a / s) * dx - (h / s) * dy,
815                         M1[2] + (a / s) * dy + (h / s) * dx],
816                     board);
817             } else {
818                 return [0]; // vorsichtshalber...
819             }
820             return intersection;
821         }
822     },
823 
824     /**
825      * Computes the intersection of a pair of lines, circles or both.
826      * It uses the internal data array stdform of these elements.
827      * @param {Array} el1 stdform of the first element (line or circle)
828      * @param {Array} el2 stdform of the second element (line or circle)
829      * @param {Number} i Index of the intersection point that should be returned.
830      * @param board Reference to the board.
831      * @returns {JXG.Coords} Coordinates of one of the possible two or more intersection points.
832      * Which point will be returned is determined by i.
833      */
834     meet: function(el1, el2, i, board) {
835         var eps = JXG.Math.eps; //    var eps = 0.000001;
836         if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) < eps) { // line line
837             return this.meetLineLine(el1, el2, i, board);
838         } else if (Math.abs(el1[3]) >= eps && Math.abs(el2[3]) < eps) { // circle line
839             return this.meetLineCircle(el2, el1, i, board);
840         } else if (Math.abs(el1[3]) < eps && Math.abs(el2[3]) >= eps) { // line circle
841             return this.meetLineCircle(el1, el2, i, board);
842         } else {  // circle circle
843             return this.meetCircleCircle(el1, el2, i, board);
844         }
845     },
846 
847     /**
848      * Intersection of two lines using the stdform.
849      * @param {Array} l1 stdform of the first line
850      * @param {Array} l2 stdform of the second line
851      * @param {number} i unused
852      * @param {JXG.Board} board Reference to the board.
853      * @returns {JXG.Coords} Coordinates of the intersection point.
854      */
855     meetLineLine: function(l1, l2, i, board) {
856         var s = JXG.Math.crossProduct(l1, l2);
857         if (Math.abs(s[0]) > JXG.Math.eps) {
858             s[1] /= s[0];
859             s[2] /= s[0];
860             s[0] = 1.0;
861         }
862         return new JXG.Coords(JXG.COORDS_BY_USER, s, board);
863     },
864 
865     /**
866      * Intersection of line and circle using the stdform.
867      * @param {Array} lin stdform of the line
868      * @param {Array} circ stdform of the circle
869      * @param {number} i number of the returned intersection point.
870      *   i==0: use the positive square root,
871      *   i==1: use the negative square root.
872      * @param {JXG.Board} board Reference to a board.
873      * @returns {JXG.Coords} Coordinates of the intersection point
874      */
875     meetLineCircle: function(lin, circ, i, board) {
876         var a,b,c,d,n, A,B,C, k,t;
877         if (circ[4] < JXG.Math.eps) { // Radius is zero, return center of circle
878             if (Math.abs( JXG.Math.innerProduct([1,circ[6],circ[7]], lin, 3)) < JXG.Math.eps) {
879                 return new JXG.Coords(JXG.COORDS_BY_USER, circ.slice(6, 8), board);
880             } else {
881                 return new JXG.Coords(JXG.COORDS_BY_USER, [NaN,NaN], board);
882             }
883         }
884         c = circ[0];
885         b = circ.slice(1, 3);
886         a = circ[3];
887         d = lin[0];
888         n = lin.slice(1, 3);
889 
890         // Line is assumed to be normalized. Therefore, nn==1 and we can skip some operations:
891         /*
892          var nn = n[0]*n[0]+n[1]*n[1];
893          A = a*nn;
894          B = (b[0]*n[1]-b[1]*n[0])*nn;
895          C = a*d*d - (b[0]*n[0]+b[1]*n[1])*d + c*nn;
896          */
897         A = a;
898         B = (b[0] * n[1] - b[1] * n[0]);
899         C = a * d * d - (b[0] * n[0] + b[1] * n[1]) * d + c;
900 
901         k = B * B - 4 * A * C;
902         if (k >= 0) {
903             k = Math.sqrt(k);
904             t = [(-B + k) / (2 * A),(-B - k) / (2 * A)];
905             return ((i == 0)
906                 ? new JXG.Coords(JXG.COORDS_BY_USER, [-t[0] * (-n[1]) - d * n[0],-t[0] * n[0] - d * n[1]], board)
907                 : new JXG.Coords(JXG.COORDS_BY_USER, [-t[1] * (-n[1]) - d * n[0],-t[1] * n[0] - d * n[1]], board)
908                 );
909             /*
910              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),
911              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)
912              */
913         } else {
914             return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
915         }
916         // Returns do not work with homogeneous coordinates, yet
917     },
918 
919     /**
920      * Intersection of two circles using the stdform.
921      * @param {Array} circ1 stdform of the first circle
922      * @param {Array} circ2 stdform of the second circle
923      * @param {number} i number of the returned intersection point.
924      *   i==0: use the positive square root,
925      *   i==1: use the negative square root.
926      * @param {JXG.Board} board Reference to the board.
927      * @returns {JXG.Coords} Coordinates of the intersection point
928      */
929     meetCircleCircle: function(circ1, circ2, i, board) {
930         var radicalAxis;
931         if (circ1[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle
932             if (Math.abs(this.distance(circ1.slice(6, 2), circ2.slice(6, 8)) - circ2[4]) < JXG.Math.eps) {
933                 return new JXG.Coords(JXG.COORDS_BY_USER, circ1.slice(6, 8), board);
934             } else {
935                 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
936             }
937         }
938         if (circ2[4] < JXG.Math.eps) { // Radius are zero, return center of circle, if on other circle
939             if (Math.abs(this.distance(circ2.slice(6, 2), circ1.slice(6, 8)) - circ1[4]) < JXG.Math.eps) {
940                 return new JXG.Coords(JXG.COORDS_BY_USER, circ2.slice(6, 8), board);
941             } else {
942                 return new JXG.Coords(JXG.COORDS_BY_USER, [0,0,0], board);
943             }
944         }
945         radicalAxis = [circ2[3] * circ1[0] - circ1[3] * circ2[0],
946             circ2[3] * circ1[1] - circ1[3] * circ2[1],
947             circ2[3] * circ1[2] - circ1[3] * circ2[2],
948             0,1,Infinity, Infinity, Infinity];
949         radicalAxis = JXG.Math.normalize(radicalAxis);
950         return this.meetLineCircle(radicalAxis, circ1, i, board);
951         // Returns do not work with homogeneous coordinates, yet
952     },
953 
954     /**
955      * Compute an intersection of the curves c1 and c2
956      * with a generalized Newton method.
957      * We want to find values t1, t2 such that
958      * c1(t1) = c2(t2), i.e.
959      * (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2)) = (0,0).
960      * We set
961      * (e,f) := (c1_x(t1)-c2_x(t2),c1_y(t1)-c2_y(t2))
962      *
963      * The Jacobian J is defined by
964      * J = (a, b)
965      *     (c, d)
966      * where
967      * a = c1_x'(t1)
968      * b = -c2_x'(t2)
969      * c = c1_y'(t1)
970      * d = -c2_y'(t2)
971      *
972      * The inverse J^(-1) of J is equal to
973      *  (d, -b)/
974      *  (-c, a) / (ad-bc)
975      *
976      * Then, (t1new, t2new) := (t1,t2) - J^(-1)*(e,f).
977      * If the function meetCurveCurve possesses the properties
978      * t1memo and t2memo then these are taken as start values
979      * for the Newton algorithm.
980      * After stopping of the Newton algorithm the values of t1 and t2 are stored in
981      * t1memo and t2memo.
982      *
983      * @param {JXG.Curve} c1 Curve, Line or Circle
984      * @param {JXG.Curve} c2 Curve, Line or Circle
985      * @param {Number} t1ini start value for t1
986      * @param {Number} t2ini start value for t2
987      * @param {JXG.Board} [board=c1.board] Reference to a board object.
988      * @returns {JXG.Coords} intersection point
989      */
990     meetCurveCurve: function(c1, c2, t1ini, t2ini, board) {
991         var count = 0,
992             t1, t2,
993             a, b, c, d, disc,
994             e, f, F,
995             D00, D01,
996             D10, D11;
997 
998         if (!JXG.exists(board))
999             board = c1.board;
1000 
1001         if (arguments.callee.t1memo) {
1002             t1 = arguments.callee.t1memo;
1003             t2 = arguments.callee.t2memo;
1004         } else {
1005             t1 = t1ini;
1006             t2 = t2ini;
1007         }
1008 
1009         /*
1010          if (t1>c1.maxX()) { t1 = c1.maxX(); }
1011          if (t1<c1.minX()) { t1 = c1.minX(); }
1012          if (t2>c2.maxX()) { t2 = c2.maxX(); }
1013          if (t2<c2.minX()) { t2 = c2.minX(); }
1014          */
1015 
1016         c1X = function(t) { return c1.X.apply(c1, [t]); };
1017         c1Y = function(t) { return c1.Y.apply(c1, [t]); };
1018         c2X = function(t) { return c2.X.apply(c2, [t]); };
1019         c2Y = function(t) { return c2.Y.apply(c2, [t]); };
1020          
1021         e = c1.X(t1) - c2.X(t2);
1022         f = c1.Y(t1) - c2.Y(t2);
1023         F = e * e + f * f;
1024         
1025         D00 = board.D(c1.X, c1);
1026         D01 = board.D(c2.X, c2);
1027         D10 = board.D(c1.Y, c1);
1028         D11 = board.D(c2.Y, c2);
1029         
1030         while (F > JXG.Math.eps && count < 10) {
1031             a = D00(t1);
1032             b = -D01(t2);
1033             c = D10(t1);
1034             d = -D11(t2);
1035             disc = a * d - b * c;
1036             t1 -= (d * e - b * f) / disc;
1037             t2 -= (a * f - c * e) / disc;
1038             e = c1.X(t1) - c2.X(t2);
1039             f = c1.Y(t1) - c2.Y(t2);
1040             F = e * e + f * f;
1041             count++;
1042         }
1043         //console.log(t1+' '+t2);
1044 
1045         arguments.callee.t1memo = t1;
1046         arguments.callee.t2memo = t2;
1047 
1048         //return (new JXG.Coords(JXG.COORDS_BY_USER, [2,2], this.board));
1049         if (Math.abs(t1) < Math.abs(t2)) {
1050             return (new JXG.Coords(JXG.COORDS_BY_USER, [c1.X(t1),c1.Y(t1)], board));
1051         } else {
1052             return (new JXG.Coords(JXG.COORDS_BY_USER, [c2.X(t2),c2.Y(t2)], board));
1053         }
1054     },
1055 
1056     /**
1057      * Intersection of curve with line,
1058      * Order of input does not matter for el1 and el2.
1059      * @param {JXG.Curve,JXG.Line} el1 Curve or Line
1060      * @param {JXG.Curve,JXG.Line} el2 Curve or Line
1061      * @param {Number} nr the nr-th intersection point will be returned.
1062      * @param {JXG.Board} [board=el1.board] Reference to a board object.
1063      * @returns {JXG.Coords} Intersection point. In case no intersection point is detected,
1064      * the ideal point [0,1,0] is returned.
1065      */
1066     meetCurveLine: function(el1, el2, nr, board, pointObj) {
1067         var v = [0, NaN, NaN], i, cu, li;
1068 
1069         if (!JXG.exists(board)) {
1070             board = el1.board;
1071         }
1072 
1073         for (i = 0; i <= 1; i++) {
1074             if (arguments[i].elementClass == JXG.OBJECT_CLASS_CURVE) {
1075                 cu = arguments[i];
1076             } else if (arguments[i].elementClass == JXG.OBJECT_CLASS_LINE) {
1077                 li = arguments[i];
1078             } else
1079                 throw new Error("JSXGraph: Can't call meetCurveLine with parent class " + (arguments[i].elementClass) + ".");
1080         }
1081 
1082         if (cu.visProp.curvetype==='plot') {
1083             v = this.meetCurveLineDiscrete(cu, li, nr, board, pointObj);
1084         } else {
1085             v = this.meetCurveLineContinuous(cu, li, nr, board);
1086         }
1087 
1088         return v;
1089     },
1090     
1091     /**
1092      * Intersection of line and curve, continuous case.
1093      * Segments are treated as lines. Finding the nr-the intersection point
1094      * works for nr=0,1 only.
1095      * 
1096      * BUG: does not respect cu.minX() and cu.maxX() 
1097      */
1098     meetCurveLineContinuous: function(cu, li, nr, board) {
1099         var t, t2, i, cu, li, func, z,
1100             tnew, steps, delta, tstart, tend, cux, cuy;
1101 
1102         func = function(t) {
1103             return li.stdform[0] + li.stdform[1] * cu.X(t) + li.stdform[2] * cu.Y(t);
1104         };
1105         
1106         /**
1107          * Find some intersection point
1108          */
1109         if (arguments.callee.t1memo) {
1110             tstart = arguments.callee.t1memo;
1111             t = JXG.Math.Numerics.root(func, tstart);
1112         } else {
1113             tstart = cu.minX();
1114             tend = cu.maxX();
1115             t = JXG.Math.Numerics.root(func, [tstart,tend]);
1116         }
1117         arguments.callee.t1memo = t;
1118         cux = cu.X(t);
1119         cuy = cu.Y(t);
1120 
1121         /**
1122          * Find second intersection point
1123          */
1124         if (nr == 1) {
1125             if (arguments.callee.t2memo) {
1126                 tstart = arguments.callee.t2memo;
1127                 t2 = JXG.Math.Numerics.root(func, tstart);
1128             }
1129             if (!(Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1)) {
1130                 steps = 20;
1131                 delta = (cu.maxX() - cu.minX()) / steps;
1132                 tnew = cu.minX();
1133                 for (i = 0; i < steps; i++) {
1134                     t2 = JXG.Math.Numerics.root(func, [tnew,tnew + delta]);
1135                     if (Math.abs(t2 - t) > 0.1 && Math.abs(cux - cu.X(t2)) > 0.1 && Math.abs(cuy - cu.Y(t2)) > 0.1) {
1136                         break;
1137                     }
1138                     tnew += delta;
1139                 }
1140             }
1141             t = t2;
1142             arguments.callee.t2memo = t;
1143         }
1144 
1145         if (Math.abs(func(t)) > JXG.Math.eps) {
1146             z = NaN;
1147         } else {
1148             z = 1.0;
1149         }
1150         return (new JXG.Coords(JXG.COORDS_BY_USER, [z, cu.X(t), cu.Y(t)], board));
1151     },
1152 
1153     /**
1154      * Intersection of line and curve, continuous case.
1155      * Segments are treated as lines. 
1156      * Finding the nr-the intersection point should work for all nr.
1157      */
1158     meetCurveLineDiscrete: function(cu, li, nr, board, pointObj) {
1159         var len, i, p1, p2, q,
1160             d, cnt = 0, res, 
1161             p, testSegment = false;
1162 
1163         len = cu.numberPoints; 
1164         if (pointObj!=null) {
1165             p = pointObj.point;
1166             if (JXG.exists(p) && !p.visProp.alwaysintersect) {
1167                 testSegment = true;
1168             }
1169             
1170         }
1171     
1172         // In case, no intersection will be found we will take this
1173         q = new JXG.Coords(JXG.COORDS_BY_USER, [0, NaN, NaN], board);
1174         
1175         p2 = [1, cu.X(0), cu.Y(0)];
1176         for (i=1;i<len;i++) {
1177             p1 = p2.slice(0);
1178             p2 = [1, cu.X(i), cu.Y(i)];
1179             d = this.distance(p1, p2);
1180             if (d<JXG.Math.eps) {    // The defining points are identical
1181                 continue;
1182             }
1183             res = this.meetSegmentSegment(p1, p2, li.point1.coords.usrCoords, li.point2.coords.usrCoords, board);
1184             if (0<=res[1] && res[1]<=1) {
1185                 if (cnt==nr) {
1186                     
1187                     /**
1188                      * If the intersection point is not part of the segment, 
1189                      * this intersection point is set to non-existent.
1190                      * This prevents jumping of the intersection points.
1191                      * But it may be discussed if it is the desired behavior.
1192                      */
1193                     if (testSegment 
1194                         && ( li.visProp.straightfirst==false && res[2]<0 
1195                              || li.visProp.straightlast==false && res[2]>1 )
1196                         ) {
1197                         break;
1198                     }
1199                         
1200                     q = new JXG.Coords(JXG.COORDS_BY_USER, res[0], board);
1201                     break;
1202                 }
1203                 cnt++;
1204             }
1205         }
1206 
1207         return q;
1208     },
1209 
1210     /**
1211      * Intersection of two segments.
1212      * @param {Array} p1 First point of segment 1 using homogeneous coordinates [z,x,y]
1213      * @param {Array} p2 Second point of segment 1 using homogeneous coordinates [z,x,y]
1214      * @param {Array} q1 First point of segment 2 using homogeneous coordinates [z,x,y]
1215      * @param {Array} q2 Second point of segment 2 using homogeneous coordinates [z,x,y]
1216      * @returns {Array} [Intersection point, t, u] The first entry contains the homogeneous coordinates 
1217      * of the intersection point. The second and third entry gives the position of the intersection between the two defining points.
1218      * For example, the second entry t is defined by: interestion point = t*p1 + (1-t)*p2.
1219      **/
1220     meetSegmentSegment: function(p1, p2, q1, q2, board) {
1221         var li1 = JXG.Math.crossProduct(p1, p2),
1222             li2 = JXG.Math.crossProduct(q1, q2),
1223             c = JXG.Math.crossProduct(li1, li2),
1224             denom = c[0],
1225             t, u, diff;
1226         
1227         if (Math.abs(denom)<Math.eps) {
1228             return [c, Number.Infinity, Number.Infinity];
1229         }
1230 
1231         diff = [q1[1]-p1[1], q1[2]-p1[2]];
1232         // Because of speed issues, evalute the determinants directly
1233         //t = JXG.Math.Numerics.det([diff, [p2[1]-p1[1], p2[2]-p1[2]] ]) / denom;
1234         //u = JXG.Math.Numerics.det([diff, [q2[1]-q1[1], q2[2]-q1[2]] ]) / denom;
1235         t = (diff[0]*(q2[2]-q1[2]) - diff[1]*(q2[1]-q1[1])) / denom;
1236         u = (diff[0]*(p2[2]-p1[2]) - diff[1]*(p2[1]-p1[1])) / denom;
1237         
1238         return [c, t, u];
1239     },
1240     
1241     /****************************************/
1242     /****           PROJECTIONS          ****/
1243     /****************************************/
1244 
1245     /**
1246      * Calculates the coordinates of the projection of a given point on a given circle. I.o.w. the
1247      * nearest one of the two intersection points of the line through the given point and the circles
1248      * center.
1249      * @param {JXG.Point_JXG.Coords} point Point to project or coords object to project.
1250      * @param {JXG.Circle} circle Circle on that the point is projected.
1251      * @param {JXG.Board} [board=point.board] Reference to the board
1252      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
1253      */
1254     projectPointToCircle: function(point, circle, board) {
1255         var dist, P,
1256             M = circle.center.coords.usrCoords,
1257             x, y, factor;
1258 
1259         if (!JXG.exists(board)) {
1260             board = point.board;
1261         }
1262 
1263         if (JXG.isPoint(point))  {
1264             dist = point.coords.distance(JXG.COORDS_BY_USER, circle.center.coords);
1265             P = point.coords.usrCoords;
1266         } else {  // coords
1267             dist = point.distance(JXG.COORDS_BY_USER, circle.center.coords);
1268             P = point.usrCoords;
1269         }
1270 
1271         if (Math.abs(dist) < JXG.Math.eps) {
1272             dist = JXG.Math.eps;
1273         }
1274         factor = circle.Radius() / dist;
1275         x = M[1] + factor * (P[1] - M[1]);
1276         y = M[2] + factor * (P[2] - M[2]);
1277 
1278         return new JXG.Coords(JXG.COORDS_BY_USER, [x, y], board);
1279     },
1280 
1281     /**
1282      * Calculates the coordinates of the orthogonal projection of a given point on a given line. I.o.w. the
1283      * intersection point of the given line and its perpendicular through the given point.
1284      * @param {JXG.Point} point Point to project.
1285      * @param {JXG.Line} line Line on that the point is projected.
1286      * @param {JXG.Board} [board=point.board] Reference to a board.
1287      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given line.
1288      */
1289     projectPointToLine: function(point, line, board) {
1290         // Homogeneous version
1291         var v = [0,line.stdform[1],line.stdform[2]];
1292 
1293         if (!JXG.exists(board))
1294             board = point.board;
1295 
1296         v = JXG.Math.crossProduct(v, point.coords.usrCoords);
1297 
1298         return this.meetLineLine(v, line.stdform, 0, board);
1299     },
1300 
1301     /**
1302      * Calculates the coordinates of the orthogonal projection of a given coordinate array on a given line
1303      * segment defined by two coordinate arrays. 
1304      * @param {Array} p1 Point to project.
1305      * @param {Array} q1 Start point of the line segment on that the point is projected.
1306      * @param {Array} q2 End point of the line segment on that the point is projected.
1307      * @returns {Array} The coordinates of the projection of the given point on the given segment 
1308      * and the factor that determines the projected point as a convex combination of the 
1309      * two endpoints q1 and q2 of the segment.     
1310      */
1311     projectCoordsToSegment: function(p, q1, q2) {
1312         var s = [q2[1]-q1[1], q2[2]-q1[2]],
1313             v = [p[1]-q1[1], p[2]-q1[2]],
1314             t, denom, c;
1315             
1316         /**
1317          * If the segment has length 0, i.e. is a point,
1318          * the projection is equal to that point.
1319          */
1320         if (Math.abs(s[0])<JXG.Math.eps && Math.abs(s[1])<JXG.Math.eps) {
1321             return q1;
1322         }
1323         t = JXG.Math.innerProduct(v,s);
1324         denom = JXG.Math.innerProduct(s,s);
1325         t /= denom;
1326         return [ [1, t*s[0]+q1[1], t*s[1]+q1[2]], t];
1327     },
1328     
1329     /**
1330      * Calculates the coordinates of the projection of a given point on a given curve.
1331      * Uses {@link #projectCoordsToCurve}.
1332      * @param {JXG.Point} point Point to project.
1333      * @param {JXG.Curve} curve Curve on that the point is projected.
1334      * @param {JXG.Board} [board=point.board] Reference to a board.
1335      * @see #projectCoordsToCurve
1336      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given graph.
1337      */
1338     projectPointToCurve: function(point, curve, board) {
1339         if (!JXG.exists(board))
1340             board = point.board;
1341 
1342         var x = point.X(),
1343             y = point.Y(),
1344             t = point.position || 0.0, //(curve.minX()+curve.maxX())*0.5,
1345             result = this.projectCoordsToCurve(x, y, t, curve, board);
1346 
1347         point.position = result[1];      // side effect !
1348         return result[0];
1349     },
1350 
1351     /**
1352      * Calculates the coordinates of the projection of a coordinates pair on a given curve. In case of
1353      * function graphs this is the
1354      * intersection point of the curve and the parallel to y-axis through the given point.
1355      * @param {Number} x coordinate to project.
1356      * @param {Number} y coordinate to project.
1357      * @param {Number} t start value for newtons method
1358      * @param {JXG.Curve} curve Curve on that the point is projected.
1359      * @param {JXG.Board} [board=curve.board] Reference to a board.
1360      * @see #projectPointToCurve
1361      * @returns {JXG.Coords} Array containing the coordinates of the projection of the given point on the given graph and
1362      * the position on the curve.
1363      */
1364     projectCoordsToCurve: function(x, y, t, curve, board) {
1365         var newCoords, i, 
1366             x0, y0, x1, y1, mindist, dist, lbda, li, v, coords, d,
1367             p1, p2, q1, q2, res,
1368             infty = Number.POSITIVE_INFINITY, 
1369             minfunc, t, tnew, fnew, fold, delta, steps;
1370 
1371         if (!JXG.exists(board)) {
1372             board = curve.board;
1373         }
1374         
1375         if (curve.visProp.curvetype == 'parameter' || curve.visProp.curvetype == 'polar') {
1376             // Function to minimize
1377             minfunc = function(t) {
1378                 var dx = x - curve.X(t),
1379                     dy = y - curve.Y(t);
1380                 return dx * dx + dy * dy;
1381             };
1382 
1383             fold = minfunc(t);
1384             steps = 20;
1385             delta = (curve.maxX() - curve.minX()) / steps;
1386             tnew = curve.minX();
1387             for (i = 0; i < steps; i++) {
1388                 fnew = minfunc(tnew);
1389                 if (fnew < fold) {
1390                     t = tnew;
1391                     fold = fnew;
1392                 }
1393                 tnew += delta;
1394             }
1395             t = JXG.Math.Numerics.root(JXG.Math.Numerics.D(minfunc), t);
1396 
1397             if (t < curve.minX()) {
1398                 t = curve.maxX() + t - curve.minX();
1399             } // Cyclically
1400             if (t > curve.maxX()) {
1401                 t = curve.minX() + t - curve.maxX();
1402             }
1403             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [curve.X(t),curve.Y(t)], board);
1404         } else if (curve.visProp.curvetype == 'plot') {
1405             t = 0;
1406             mindist = infty;
1407             if (curve.numberPoints==0) {
1408                 newCoords = [0,1,1]; 
1409             } else {
1410                 newCoords = [curve.Z(0), curve.X(0), curve.Y(0)]; 
1411             } 
1412             
1413             if (curve.numberPoints>1) {
1414                 p1 = [curve.Z(0), curve.X(0), curve.Y(0)];
1415                 for (i=0; i<curve.numberPoints-1; i++) {
1416                     p2 = [curve.Z(i+1), curve.X(i+1), curve.Y(i+1)];
1417                     v = [1, x, y];
1418                     res = this.projectCoordsToSegment(v, p1, p2);
1419                     lbda = res[1];
1420                     coords = res[0];
1421                     if (0.0<=lbda && lbda<=1.0) {     
1422                         dist = this.distance(coords, v);
1423                         d = i + lbda;
1424                     } else if (lbda<0.0) {
1425                         coords = p1; 
1426                         dist = this.distance(p1, v);
1427                         d = i;
1428                     } else if (lbda>1.0 && i+1== curve.numberPoints-1) {
1429                         coords = p2;
1430                         dist = this.distance(coords, v);
1431                         d = curve.numberPoints-1;
1432                     }
1433                     
1434                     if (dist < mindist) {
1435                         mindist = dist;
1436                         t = d;
1437                         newCoords = coords;
1438                     }
1439                     p1 = p2;  // Moving on.
1440                 }
1441             }
1442            
1443             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, newCoords, board);
1444         } else {             // functiongraph
1445             t = x;
1446             x = t; //curve.X(t);
1447             y = curve.Y(t);
1448             newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
1449         }
1450         return [curve.updateTransform(newCoords), t];
1451     },
1452 
1453     /**
1454      * Calculates the coordinates of the projection of a given point on a given turtle. A turtle consists of
1455      * one or more curves of curveType 'plot'. Uses {@link #projectPointToCurve}.
1456      * @param {JXG.Point} point Point to project.
1457      * @param {JXG.Turtle} turtle on that the point is projected.
1458      * @param {JXG.Board} [board=point.board] Reference to a board.
1459      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given turtle.
1460      */
1461     projectPointToTurtle: function(point, turtle, board) {
1462         var newCoords, t, x, y, i,
1463             np = 0,
1464             npmin = 0,
1465             mindist = Number.POSITIVE_INFINITY,
1466             dist, el, minEl,
1467             len = turtle.objects.length;
1468 
1469         if (!JXG.exists(board))
1470             board = point.board;
1471 
1472         for (i = 0; i < len; i++) {  // run through all curves of this turtle
1473             el = turtle.objects[i];
1474             if (el.elementClass == JXG.OBJECT_CLASS_CURVE) {
1475                 newCoords = this.projectPointToCurve(point, el);
1476                 dist = this.distance(newCoords.usrCoords, point.coords.usrCoords);
1477                 if (dist < mindist) {
1478                     x = newCoords.usrCoords[1];
1479                     y = newCoords.usrCoords[2];
1480                     t = point.position;
1481                     mindist = dist;
1482                     minEl = el;
1483                     npmin = np;
1484                 }
1485                 np += el.numberPoints;
1486             }
1487         }
1488         newCoords = new JXG.Coords(JXG.COORDS_BY_USER, [x,y], board);
1489         point.position = t + npmin;
1490         return minEl.updateTransform(newCoords);
1491     },
1492 
1493     /**
1494      * Trivial projection of a point to another point.
1495      * @param {JXG.Point} point Point to project (not used).
1496      * @param {JXG.Point} dest Point on that the point is projected.
1497      * @param {JXG.Board} [board=point.board] Reference to the board (not used).
1498      * @returns {JXG.Coords} The coordinates of the projection of the given point on the given circle.
1499      */
1500     projectPointToPoint: function(point, dest, board) {
1501         return dest.coords;
1502     },
1503     
1504     /**
1505      * Calculates the distance of a point to a line. The point and the line are given by homogeneous 
1506      * coordinates. For lines this can be line.stdform.
1507      * @param {Array} point Homogeneous coordinates of a point.
1508      * @param {Array} line Homogeneous coordinates of a line ([C,A,B] where A*x+B*y+C*z=0).
1509      * @returns {Number} Distance of the point to the line.
1510      */
1511     distPointLine: function(point, line) {
1512         var a = line[1],
1513             b = line[2],
1514             c = line[0],
1515             nom;
1516         
1517         if (Math.abs(a)+Math.abs(b) < JXG.Math.eps) {
1518             return Number.POSITIVE_INFINITY;
1519         }
1520         
1521         nom = a*point[1] + b*point[2] + c*1;
1522         a *= a;
1523         b *= b;
1524         return Math.abs(nom) / Math.sqrt(a+b);
1525     }
1526     
1527 });
1528