1 /*
  2     Copyright 2008-2021
  3         Matthias Ehmann,
  4         Michael Gerhaeuser,
  5         Carsten Miller,
  6         Alfred Wassermann
  7 console.log("P:", P.coords.usrCoords, P.data.type)
  8 
  9     This file is part of JSXGraph.
 10 
 11     JSXGraph is free software dual licensed under the GNU LGPL or MIT License.
 12 
 13     You can redistribute it and/or modify it under the terms of the
 14 
 15       * GNU Lesser General Public License as published by
 16         the Free Software Foundation, either version 3 of the License, or
 17         (at your option) any later version
 18       OR
 19       * MIT License: https://github.com/jsxgraph/jsxgraph/blob/master/LICENSE.MIT
 20 
 21     JSXGraph is distributed in the hope that it will be useful,
 22     but WITHOUT ANY WARRANTY; without even the implied warranty of
 23     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 24     GNU Lesser General Public License for more details.
 25 
 26     You should have received a copy of the GNU Lesser General Public License and
 27     the MIT License along with JSXGraph. If not, see <http://www.gnu.org/licenses/>
 28     and <http://opensource.org/licenses/MIT/>.
 29  */
 30 
 31 
 32 /*global JXG: true, define: true*/
 33 /*jslint nomen: true, plusplus: true*/
 34 
 35 /* depends:
 36  jxg
 37  base/constants
 38  base/coords
 39  math/math
 40  math/numerics
 41  math/geometry
 42  utils/type
 43  */
 44 
 45 /**
 46  * @fileoverview This file contains the Math.Clip namespace for clipping and computing boolean operations
 47  * on polygons and curves
 48  *
 49  * // TODO:
 50  * * Check if input polygons are closed. If not, handle this case.
 51  */
 52 
 53 define([
 54     'jxg', 'base/constants', 'base/coords', 'math/math', 'math/geometry', 'utils/type'
 55 ], function (JXG, Const, Coords, Mat, Geometry, Type) {
 56 
 57     "use strict";
 58 
 59     /**
 60      * Math.Clip namespace definition. This namespace contains algorithms for Boolean operations on paths, i.e.
 61      * intersection, union and difference of paths. Base is the Greiner-Hormann algorithm.
 62      * @name JXG.Math.Clip
 63      * @exports Mat.Clip as JXG.Math.Clip
 64      * @namespace
 65      */
 66     // Mat.Clip = function () {
 67     // };
 68 
 69     // JXG.extend(Mat.Clip.prototype, /** @lends JXG.Curve.prototype */ {
 70 
 71     Mat.Clip = {
 72 
 73         _isSeparator: function(node) {
 74             return isNaN(node.coords.usrCoords[1]) && isNaN(node.coords.usrCoords[2]);
 75         },
 76 
 77         /**
 78          * Add pointers to an array S such that it is a circular doubly-linked list.
 79          *
 80          * @private
 81          * @param  {Array} S Array
 82          * @return {Array} return containing the starter indices of each component.
 83          */
 84         makeDoublyLinkedList: function(S) {
 85             var i,
 86                 first = null,
 87                 components = [],
 88                 le = S.length;
 89 
 90             if (le > 0) {
 91                 for (i = 0; i < le; i++) {
 92                     // S[i]._next = S[(i + 1) % le];
 93                     // S[i]._prev = S[(le + i - 1) % le];
 94 
 95                     // If S[i] is component separator we proceed with the next node.
 96                     if (this._isSeparator(S[i])) {
 97                         S[i]._next = S[(i + 1) % le];
 98                         S[i]._prev = S[(le + i - 1) % le];
 99                         continue;
100                     }
101 
102                     // Now we know that S[i] is a path component
103                     if (first === null) {
104                         // Start the component if it is not yet started.
105                         first = i;
106                         components.push(first);
107                     }
108                     if (this._isSeparator(S[(i + 1) % le]) || i == le - 1) {
109                         // If the next node is a component separator or if the node is the last node,
110                         // then we close the loop
111 
112                         S[i]._next = S[first];
113                         S[first]._prev = S[i];
114                         S[i]._end = true;
115                         first = null;
116                     } else {
117                         // Here, we are not at the end of component
118                         S[i]._next = S[(i + 1) % le];
119                         S[first]._prev = S[i];
120                     }
121                     if (!this._isSeparator(S[(le + i - 1) % le])) {
122                         S[i]._prev = S[(le + i - 1) % le];
123                     }
124                 }
125             }
126             return components;
127         },
128 
129         /**
130          * Determinant of three points in the Euclidean plane.
131          * Zero, if the points are collinear. Used to determine of a point q is left or
132          * right to a segment defined by points p1 and p2.
133          * @private
134          * @param  {Array} p1 Coordinates of the first point of the segment. Array of length 3. First coordinate is equal to 1.
135          * @param  {Array} p2 Coordinates of the second point of the segment. Array of length 3. First coordinate is equal to 1.
136          * @param  {Array} q Coordinates of the point. Array of length 3. First coordinate is equal to 1.
137          * @return {Number} Signed area of the triangle formed by these three points.
138          */
139         det: function(p1, p2, q) {
140             return (p1[1] - q[1]) * (p2[2] - q[2]) - (p2[1] - q[1]) * (p1[2] - q[2]);
141         },
142 
143         /**
144          * Winding number of a point in respect to a polygon path.
145          *
146          * The point is regarded outside if the winding number is zero,
147          * inside otherwise. The algorithm tries to find degenerate cases, i.e.
148          * if the point is on the path. This is regarded as "outside".
149          * If the point is a vertex of the path, it is regarded as "inside".
150          *
151          * Implementation of algorithm 7 from "The point in polygon problem for
152          * arbitrary polygons" by Kai Hormann and Alexander Agathos, Computational Geometry,
153          * Volume 20, Issue 3, November 2001, Pages 131-144.
154          *
155          * @param  {Array} usrCoords Homogenous coordinates of the point
156          * @param  {Array} path      Array of points determining a path, i.e. the vertices of the polygon. The array elements
157          * do not have to be full points, but have to have a subobject "coords".
158          * @return {Number}          Winding number of the point. The point is
159          *                           regarded outside if the winding number is zero,
160          *                           inside otherwise.
161          */
162         windingNumber: function(usrCoords, path) {
163             var wn = 0,
164                 le = path.length,
165                 x = usrCoords[1],
166                 y = usrCoords[2],
167                 p1, p2, d, sign, i;
168 
169             if (le === 0) {
170                 return 0;
171             }
172 
173             // Infinite points are declared outside
174             if (isNaN(x) || isNaN(y)) {
175                 return 1;
176             }
177 
178             // Handle the case if the point is a vertex of the path
179             if (path[0].coords.usrCoords[1] === x &&
180                 path[0].coords.usrCoords[2] === y) {
181 
182                 // console.log('<<<<<<< Vertex 1');
183                 return 1;
184             }
185 
186             for (i = 0; i < le; i++) {
187                 // Consider the edge from p1 = path[i] to p2 = path[i+1]
188                 p1 = path[i].coords.usrCoords;
189                 p2 = path[(i + 1) % le].coords.usrCoords;
190                 if (p1[0] === 0 || p2[0] === 0 ||
191                     isNaN(p1[1]) || isNaN(p2[1]) ||
192                     isNaN(p1[2]) || isNaN(p2[2])) {
193 
194                     continue;
195                 }
196 
197                 if (p2[2] === y) {
198                     if (p2[1] === x) {
199                         // console.log('<<<<<<< Vertex 2');
200                         return 1;
201                     }
202                     if (p1[2] === y && ((p2[1] > x) === (p1[1] < x))) {
203                         // console.log('<<<<<<< Edge 1', p1, p2, [x, y]);
204                         return 0;
205                     }
206                 }
207 
208                 if ((p1[2] < y) !== (p2[2] < y)) {
209                     sign = 2 * ((p2[2] > p1[2]) ? 1 : 0) - 1;
210                     if (p1[1] >= x) {
211                         if (p2[1] > x) {
212                             wn += sign;
213                         } else {
214                             d = this.det(p1, p2, usrCoords);
215                             if (d === 0) {
216                                 // console.log('<<<<<<< Edge 2');
217                                 return 0;
218                             }
219                             if ((d > 0) === (p2[2] > p1[2])) {
220                                 wn += sign;
221                             }
222                         }
223                     } else {
224                         if (p2[1] > x) {
225                             d = this.det(p1, p2, usrCoords);
226                             if ((d > 0 + Mat.eps) === (p2[2] > p1[2])) {
227                                 wn += sign;
228                             }
229                         }
230                     }
231                 }
232             }
233 
234             return wn;
235         },
236 
237         /**
238          * JavaScript object containing the intersection of two paths. Every intersection point is on one path, but
239          * comes with a neighbour point having the same coordinates and being on the other path.
240          *
241          * The intersection point is inserted into the doubly linked list of the path.
242          *
243          * @private
244          * @param  {JXG.Coords} coords JSXGraph Coords object conatining the coordinates of the intersection
245          * @param  {Number} i        Number of the segment of the subject path (first path) containing the intersection.
246          * @param  {Number} alpha    The intersection is a p_1 + alpha*(p_2 - p_1), where p_1 and p_2 are the end points
247          *      of the i-th segment.
248          * @param  {Array} path      Pointer to the path containing the intersection point
249          * @param  {String} pathname Name of the path: 'S' or 'C'.
250          */
251         Vertex: function(coords, i, alpha, path, pathname, type) {
252             this.pos = i;
253             this.intersection = true;
254             this.coords = coords;
255             this.elementClass = Const.OBJECT_CLASS_POINT;
256 
257             this.data = {
258                 alpha: alpha,
259                 path: path,
260                 pathname: pathname,
261                 done: false,
262                 type: type,
263                 revtype: type,
264                 link: null,
265                 idx: 0
266             };
267 
268             // Set after initialisation
269             this.neighbour = null;
270             this.entry_exit = false;
271         },
272 
273         _addToList: function(list, coords, pos) {
274             var len = list.length,
275                 eps = Mat.eps * Mat.eps;
276 
277             if (len > 0 &&
278                 Math.abs(list[len - 1].coords.usrCoords[0] - coords.usrCoords[0]) < eps &&
279                 Math.abs(list[len - 1].coords.usrCoords[1] - coords.usrCoords[1]) < eps &&
280                 Math.abs(list[len - 1].coords.usrCoords[2] - coords.usrCoords[2]) < eps) {
281                 // Skip point
282                 return;
283             }
284             list.push({
285                 pos: pos,
286                 intersection: false,
287                 coords: coords,
288                 elementClass: Const.OBJECT_CLASS_POINT
289             });
290         },
291 
292         /**
293          * Sort the intersection points into their path.
294          * @private
295          * @param  {Array} P_crossings Array of arrays. Each array contains the intersections of the path
296          *      with one segment of the other path.
297          * @return {Array}  Array of intersection points ordered by first occurrence in the path.
298          */
299         sortIntersections: function(P_crossings) {
300             var i, j, P, Q,
301                 last,
302                 next_node,
303                 P_intersect = [],
304                 P_le = P_crossings.length;
305 
306             for (i = 0; i < P_le; i++) {
307                 P_crossings[i].sort(function(a, b) { return (a.data.alpha > b.data.alpha) ? 1 : -1; });
308 
309                 if (P_crossings[i].length > 0) {
310             // console.log("Crossings", P_crossings[i])
311                     last = P_crossings[i].length - 1;
312                     P = P_crossings[i][0];
313 //console.log("SORT", P.coords.usrCoords)
314                     Q =  P.data.path[P.pos];
315                     next_node = Q._next;  // Store the next "normal" node
316 
317                     if (i === P_le - 1) {
318                         Q._end = false;
319                     }
320 
321                     if (P.data.alpha === 0.0 && P.data.type === 'T') {
322 //            console.log("SKIP", P.coords.usrCoords, P.data.type, P.neighbour.data.type);
323                         Q.intersection = true;
324                         Q.data = P.data;
325                         Q.neighbour = P.neighbour;
326                         Q.neighbour.neighbour = Q;
327                         Q.entry_exit = false;
328                         P_crossings[i][0] = Q;
329                     } else {
330                         // Insert the first intersection point
331                         P._prev = Q;
332                         P._prev._next = P;
333                     }
334 
335                     // Insert the other intersection points, but the last
336                     for (j = 1; j <= last; j++) {
337                         P = P_crossings[i][j];
338                         P._prev = P_crossings[i][j - 1];
339                         P._prev._next = P;
340                     }
341 
342                     // Link last intersection point to the next node
343                     P = P_crossings[i][last];
344                     P._next = next_node;
345                     P._next._prev = P;
346 
347                     if (i === P_le - 1) {
348                         P._end = true;
349             //console.log("END", P._end, P.coords.usrCoords, P._prev.coords.usrCoords, P._next.coords.usrCoords);
350                     }
351 
352                     P_intersect = P_intersect.concat(P_crossings[i]);
353                 }
354             }
355             return P_intersect;
356         },
357 
358         _inbetween: function(q, p1, p2) {
359             var alpha,
360                 eps = Mat.eps * Mat.eps,
361                 px = p2[1] - p1[1],
362                 py = p2[2] - p1[2],
363                 qx = q[1]  - p1[1],
364                 qy = q[2]  - p1[2];
365 
366             if (px === 0 && py === 0 && qx === 0 && qy === 0) {
367                 // All three points are equal
368                 return true;
369             }
370             if (Math.abs(qx) < eps && Math.abs(px) < eps) {
371                 alpha = qy / py;
372             } else {
373                 alpha = qx / px;
374             }
375             if (Math.abs(alpha) < eps) {
376                 alpha = 0.0;
377             }
378             return alpha;
379         },
380 
381         _print_array: function(arr) {
382             var i, end;
383             for (i = 0; i < arr.length; i++) {
384                 //console.log(i, arr[i].coords.usrCoords,  arr[i].data.type);
385                 try {
386                     end = "";
387                     if (arr[i]._end) {
388                         end = " end";
389                     }
390                     console.log(i, arr[i].coords.usrCoords,
391                                 "prev", arr[i]._prev.coords.usrCoords,
392                                 "next", arr[i]._next.coords.usrCoords + end);
393                 } catch (e) {
394                     console.log(i, arr[i].coords.usrCoords);
395                 }
396             }
397         },
398 
399         _print_list: function(P) {
400             var cnt = 0, alpha;
401             while (cnt < 100) {
402                 if (P.data) {
403                     alpha = P.data.alpha;
404                 } else {
405                     alpha = '-';
406                 }
407                 console.log("\t", P.coords.usrCoords, "\n\t\tis:", P.intersection, "end:", P._end,
408                             alpha,
409                             "\n\t\t-:", P._prev.coords.usrCoords,
410                             "\n\t\t+:", P._next.coords.usrCoords,
411                             "\n\t\tn:", (P.intersection) ? P.neighbour.coords.usrCoords : '-'
412                             );
413                 if (P._end) {
414                     break;
415                 }
416                 P = P._next;
417                 cnt++;
418             }
419         },
420 
421         _noOverlap: function(p1, p2, q1, q2) {
422             var k,
423                 eps = Mat.eps * Mat.eps,
424                 minp, maxp, minq, maxq,
425                 no_overlap = false;
426 
427             for (k = 0; k < 3; k++) {
428                 minp = Math.min(p1[k], p2[k]);
429                 maxp = Math.max(p1[k], p2[k]);
430                 minq = Math.min(q1[k], q2[k]);
431                 maxq = Math.max(q1[k], q2[k]);
432                 if (maxp < minq - eps|| minp > maxq + eps) {
433                     no_overlap = true;
434                     break;
435                 }
436             }
437             return no_overlap;
438         },
439 
440         /**
441          * Find all intersections between two paths.
442          * @private
443          * @param  {Array} S     Subject path
444          * @param  {Array} C     Clip path
445          * @param  {JXG.Board} board JSXGraph board object. It is needed to convert between
446          * user coordinates and screen coordinates.
447          * @return {Array}  Array containing two arrays. The first array contains the intersection vertices
448          * of the subject path and the second array contains the intersection vertices of the clip path.
449          * @see JXG.Clip#Vertex
450          */
451         findIntersections: function(S, C, board) {
452             var res = [],
453                 eps = Mat.eps,
454                 i, j,
455                 crds,
456                 S_le = S.length,
457                 C_le = C.length,
458                 Si, Si1, Cj, Cj1,
459                 d1, d2,
460                 alpha,
461                 type,
462                 IS, IC,
463                 S_intersect = [],
464                 C_intersect = [],
465                 S_crossings = [],
466                 C_crossings = [],
467                 hasMultCompsS = false,
468                 hasMultCompsC = false;
469 
470             for (j = 0; j < C_le; j++) {
471                 C_crossings.push([]);
472             }
473 
474             // Run through the subject path.
475             for (i = 0; i < S_le; i++) {
476                 S_crossings.push([]);
477 
478                 // Test if S[i] or its successor is a path separator.
479                 // If yes, we know that the path consists of multiple components.
480                 // We immediately jump to the next segment.
481                 if (this._isSeparator(S[i]) || this._isSeparator(S[(i + 1) % S_le])) {
482                     hasMultCompsS = true;
483                     continue;
484                 }
485 
486                 // If the path consists of multiple components then there is
487                 // no path-closing segment between the last node and the first
488                 // node. In this case we can leave the loop now.
489                 if (hasMultCompsS && i === S_le - 1) {
490                     break;
491                 }
492 
493                 Si = S[i].coords.usrCoords;
494                 Si1 = S[(i + 1) % S_le].coords.usrCoords;
495 
496                 // Run through the clip path.
497                 for (j = 0; j < C_le; j++) {
498                     // Test if C[j] or its successor is a path separator.
499                     // If yes, we know that the path consists of multiple components.
500                     // We immediately jump to the next segment.
501                     if (this._isSeparator(C[j]) || this._isSeparator(C[(j + 1) % C_le])) {
502                         hasMultCompsC = true;
503                         continue;
504                     }
505 
506                     // If the path consists of multiple components then there is
507                     // no path-closing segment between the last node and the first
508                     // node. In this case we can leave the loop now.
509                     if (hasMultCompsC && j === C_le - 1) {
510                         break;
511                     }
512 
513                     // Test if bounding boxes of the two curve segments overlap
514                     // If not, the expensive intersection test can be skipped.
515                     Cj  = C[j].coords.usrCoords;
516                     Cj1 = C[(j + 1) % C_le].coords.usrCoords;
517 
518                     if (this._noOverlap(Si, Si1, Cj, Cj1)) {
519                         continue;
520                     }
521 
522                     // Intersection test
523                     res = Geometry.meetSegmentSegment(Si, Si1, Cj, Cj1);
524 // console.log(i, j, ":", eps, res[0][1] / res[0][0], res[0][2] / res[0][0], res[1], res[2]);
525 
526                     d1 = Geometry.distance(Si, Si1, 3);
527                     d2 = Geometry.distance(Cj, Cj1, 3);
528                     // Found an intersection point
529                     // isCollinear = false;
530                     if ((res[1] * d1 > -eps && res[1] < 1 - eps / d1 &&           // "regular" intersection
531                          res[2] * d2 > -eps && res[2] < 1 - eps / d2) ||
532                         (res[1] === Infinity &&
533                          res[2] === Infinity && Mat.norm(res[0], 3) < eps) // collinear
534                         ) {
535 
536                             crds = new Coords(Const.COORDS_BY_USER, res[0], board);
537                             type = 'X';
538 // console.log("IS", i, j, crds.usrCoords, res[1], d1, res[1] * d1);
539 // console.log(res[2], d2, res[2] * d2);
540 
541                             // Degenerate cases
542                             if (Math.abs(res[1]) * d1 < eps || Math.abs(res[2]) * d2 < eps) {
543                                 // Crossing / bouncing at vertex or
544                                 // end of delayed crossing / bouncing
545                                 type  = 'T';
546                                 if (Math.abs(res[1]) * d1 < eps) {
547                                     res[1] = 0;
548                                 }
549                                 if (Math.abs(res[2]) * d2 < eps) {
550                                     res[2] = 0;
551                                 }
552                                 if (res[1] === 0) {
553                                     crds = new Coords(Const.COORDS_BY_USER, Si, board);
554                                 } else {
555                                     crds = new Coords(Const.COORDS_BY_USER, Cj, board);
556                                 }
557                             } else if (res[1] === Infinity &&
558                                        res[2] === Infinity &&
559                                        Mat.norm(res[0], 3) < eps) {
560 
561                                 // In this case there might be two intersection points to be added
562                                 // Collinear segments
563                                 alpha = this._inbetween(Si, Cj, Cj1);
564     // console.log("alpha Si", alpha, Si);
565     // console.log(j, Cj)
566     // console.log((j + 1) % C_le, Cj1)
567                                 if (alpha >= 0 && alpha < 1) {
568                                     type = 'T';
569                                     crds = new Coords(Const.COORDS_BY_USER, Si, board);
570                                     res[1] = 0;
571                                     res[2] = alpha;
572                                     IS = new this.Vertex(crds, i, res[1], S, 'S', type);
573                                     IC = new this.Vertex(crds, j, res[2], C, 'C', type);
574                                     IS.neighbour = IC;
575                                     IC.neighbour = IS;
576 
577                                     S_crossings[i].push(IS);
578                                     C_crossings[j].push(IC);
579                                 }
580                                 alpha = this._inbetween(Cj, Si, Si1);
581     // console.log("alpha Cj", alpha, Si, Geometry.distance(Si, Cj, 3));
582                                 if (Geometry.distance(Si, Cj, 3) > eps &&
583                                     alpha >= 0 && alpha < 1) {
584                                         type = 'T';
585                                         crds = new Coords(Const.COORDS_BY_USER, Cj, board);
586                                         res[1] = alpha;
587                                         res[2] = 0;
588                                         IS = new this.Vertex(crds, i, res[1], S, 'S', type);
589                                         IC = new this.Vertex(crds, j, res[2], C, 'C', type);
590                                         IS.neighbour = IC;
591                                         IC.neighbour = IS;
592 
593                                         S_crossings[i].push(IS);
594                                         C_crossings[j].push(IC);
595                                 }
596                                 continue;
597                             }
598 
599                         IS = new this.Vertex(crds, i, res[1], S, 'S', type);
600                         IC = new this.Vertex(crds, j, res[2], C, 'C', type);
601                         IS.neighbour = IC;
602                         IC.neighbour = IS;
603 
604                         S_crossings[i].push(IS);
605                         C_crossings[j].push(IC);
606                     }
607                 }
608             }
609 
610             // For both paths, sort their intersection points
611             S_intersect = this.sortIntersections(S_crossings);
612 
613 // console.log('>>>>>> Intersections ')
614 // this._print_array(S_intersect);
615 // // console.log(S_intersect)
616 // console.log('----------')
617             for (i = 0; i < S_intersect.length; i++) {
618                 S_intersect[i].data.idx = i;
619                 S_intersect[i].neighbour.data.idx = i;
620             }
621             C_intersect = this.sortIntersections(C_crossings);
622 
623 // this._print_array(C_intersect);
624 // console.log(C_intersect)
625 // console.log('<<<<<< Phase 1 done')
626             return [S_intersect, C_intersect];
627         },
628 
629         _getPosition: function(q, p1, p2, p3) {
630             var s1 = this.det(q, p1, p2),
631                 s2 = this.det(q, p2, p3),
632                 s3 = this.det(p1, p2, p3);
633 
634             if (s3 >= 0) {   // Left turn or straight
635                 if (s1 > 0 && s2 > 0) {
636                     return 'left';
637                 }
638                 return 'right';
639             }
640             // Right turn
641             if (s1 < 0 && s2 < 0) {
642                 return 'right';
643             }
644             return 'left';
645         },
646 
647         _classifyDegenerateIntersections: function(P) {
648             var Pp, Pm, Qp, Qm, Q, side,
649                 cnt;
650 
651             cnt = 0;
652             P._start = 0;
653             while (true) {
654 // console.log("P:", P.coords.usrCoords, (P.data) ? P.data.type : " ")
655                 if (P.intersection && P.data.type === 'T') {
656 
657                     // Handle the degenerate cases
658                     // Decide if they are (delayed) bouncing or crossing intersections
659                     Pp = P._next.coords.usrCoords;  // P+
660                     Pm = P._prev.coords.usrCoords;  // P-
661 
662                     // If the intersection point is degenerated and
663                     // equal to the start and end of one component,
664                     // then there will be two adjacent points with
665                     // the same coordinate.
666                     // In that case, we proceed to the next node.
667                     if (Geometry.distance(P.coords.usrCoords, Pp, 3) < Mat.eps) {
668                         P._next = P._next._next;
669                         Pp = P._next.coords.usrCoords;
670                     }
671                     if (Geometry.distance(P.coords.usrCoords, Pm, 3) < Mat.eps) {
672                         P._prev = P._prev._prev;
673                         Pm = P._prev.coords.usrCoords;
674                     }
675 
676                     Q = P.neighbour;
677                     Qm = P.neighbour._prev.coords.usrCoords;  // Q-
678                     Qp = P.neighbour._next.coords.usrCoords;  // Q+
679 
680 // console.log("Chain 1:", Pm, P.coords.usrCoords, Pp)
681 // console.log("Chain 2:", Qm, P.neighbour.coords.usrCoords, Qp)
682 // console.log(P._next.neighbour, Q._prev)
683 // console.log(P._next.intersection, P._next.neighbour === Q._prev)
684                     if (P._next.intersection && P._next.neighbour === Q._next) {
685                         if (P._prev.intersection && P._prev.neighbour === Q._prev) {
686                             P.delayedStatus = ['on', 'on'];
687                         } else {
688                             side = this._getPosition(Qm,  Pm, P.coords.usrCoords, Pp);
689                             if (side === 'right') {
690                                 P.delayedStatus = ['left', 'on'];
691                             } else {
692                                 P.delayedStatus = ['right', 'on'];
693                             }
694                         }
695                     } else if (P._next.intersection && P._next.neighbour === Q._prev) {
696                         if (P._prev.intersection && P._prev.neighbour === Q._next) {
697                             P.delayedStatus = ['on', 'on'];
698                         } else {
699                             side = this._getPosition(Qp,  Pm, P.coords.usrCoords, Pp);
700                             if (side === 'right') {
701                                 P.delayedStatus = ['left', 'on'];
702                             } else {
703                                 P.delayedStatus = ['right', 'on'];
704                             }
705                         }
706                     }
707 
708                     if (P._prev.intersection && P._prev.neighbour === Q._prev) {
709                         if (!(P._next.intersection && P._next.neighbour === Q._next)) {
710                             side = this._getPosition(Qp,  Pm, P.coords.usrCoords, Pp);
711                             if (side === 'right') {
712                                 P.delayedStatus = ['on', 'left'];
713                             } else {
714                                 P.delayedStatus = ['on', 'right'];
715                             }
716                         }
717                     } else if (P._prev.intersection && P._prev.neighbour === Q._next) {
718                         if (!(P._next.intersection && P._next.neighbour === Q._prev)) {
719                             side = this._getPosition(Qm,  Pm, P.coords.usrCoords, Pp);
720                             if (side === 'right') {
721                                 P.delayedStatus = ['on', 'left'];
722                             } else {
723                                 P.delayedStatus = ['on', 'right'];
724                             }
725                         }
726                     }
727 
728                     if ((!P._next.intersection || (P._next.neighbour !== Q._prev && P._next.neighbour !== Q._next)) &&
729                         (!P._prev.intersection || (P._prev.neighbour !== Q._prev && P._prev.neighbour !== Q._next))
730                         ) {
731                         // Neither P- nor P+ are intersections
732 
733                         side = this._getPosition(Qm,   Pm, P.coords.usrCoords, Pp);
734                         if (side !== this._getPosition(Qp,  Pm, P.coords.usrCoords, Pp)) {
735                             P.data.type    = 'X';
736                             P.data.revtype = 'X';
737                         } else {
738                             P.data.type    = 'B';
739                             P.data.revtype = 'B';
740                         }
741                     }
742 // console.log(">P:", P.coords.usrCoords, (P.data) ? P.data.type : " ")
743 
744                 }
745 
746                 if (Type.exists(P._start)) {
747                     P._start++;
748                 }
749                 if (P._start > 3 || P._end || cnt > 1000) {
750                     if (cnt > 1000) {
751                         console.log("Clipping: _classifyDegenerateIntersections exit");
752                     }
753                     if (Type.exists(P._start)) {
754                         delete P._start;
755                     }
756                     break;
757                 }
758                 if (P.intersection) {
759                     cnt++;
760                 }
761                 P = P._next;
762             }
763 // console.log("------------------------")
764         },
765 
766         _handleIntersectionChains: function(P) {
767             var cnt = 0,
768                 start_status = 'Null',
769                 P_start,
770                 intersection_chain = false,
771                 wait_for_exit = false;
772 
773             while (true) {
774                 if (P.intersection === true) {
775     //console.log("Chain point", P.coords.usrCoords, P.data.type);
776                     if (P.data.type === 'T') {
777                         if (P.delayedStatus[0] !== 'on' && P.delayedStatus[1] === 'on') {
778                             intersection_chain = true;
779                             P_start = P;
780                             start_status = P.delayedStatus[0];
781                         } else if (P.delayedStatus[0] === 'on' && P.delayedStatus[1] === 'on') {
782                             P.data.type    = 'B';
783                             P.data.revtype = 'B';
784                         } else if (P.delayedStatus[0] === 'on' && P.delayedStatus[1] !== 'on' &&
785                                     intersection_chain) {
786                             intersection_chain = false;
787                             if (start_status === P.delayedStatus[1]) {
788                                 P.data.type          = 'B';
789                                 P.data.revtype       = 'B';
790                                 P_start.data.type    = 'B';
791                                 P_start.data.revtype = 'B';
792                             } else {
793                                 P.data.type          = 'X';
794                                 P.data.revtype       = 'B';
795                                 P_start.data.type    = 'B';
796                                 P_start.data.revtype = 'X';
797                             }
798                             P_start.data.link = P;
799                             P.data.link       = P_start;
800                         }
801                     }
802                     cnt++;
803                 }
804                 if (P._end) {
805                     wait_for_exit = true;
806                 }
807                 if (wait_for_exit && !intersection_chain) {
808                     break;
809                 }
810                 if (cnt > 1000) {
811                     console.log("Clipping: Intersection chain - exit");
812                     break;
813                 }
814                 P = P._next;
815             }
816         },
817 
818         /**
819          * Handle the case that all vertices of one path are contained
820          * in the other path. In this case we search for a midpoint of an edge
821          * which is not contained in the other path and add it to the path.
822          * It will be used as starting point for the entry/exit algorithm.
823          *
824          * @private
825          * @param {Array} S Subject path
826          * @param {Array} C Clip path
827          * @param {JXG.board} board JSXGraph board object. It is needed to convert between
828          * user coordinates and screen coordinates.
829          */
830         _handleFullyDegenerateCase: function(S, C, board) {
831             var P, Q, l, M, crds, q1, q2, node,
832                 i, j, le, le2, is_on_Q,
833                 is_fully_degenerated,
834                 arr = [S, C];
835 
836             for (l = 0; l < 2; l++) {
837                 P = arr[l];
838                 le = P.length;
839                 for (i = 0, is_fully_degenerated = true; i < le; i++) {
840                     if (!P[i].intersection) {
841                         is_fully_degenerated = false;
842                         break;
843                     }
844                 }
845 
846                 if (is_fully_degenerated) {
847                     // All nodes of P are also on the other path.
848                     Q = arr[(l + 1) % 2];
849                     le2 = Q.length;
850 
851                     // We search for a midpoint of one edge of P which is not the other path and
852                     // we add that midpoint to P.
853                     for (i = 0; i < le; i++) {
854                         q1 = P[i].coords.usrCoords;
855                         q2 = P[(i + 1) % le].coords.usrCoords;
856                         // M id the midpoint
857                         M = [(q1[0] +  q2[0]) * 0.5,
858                              (q1[1] +  q2[1]) * 0.5,
859                              (q1[2] +  q2[2]) * 0.5];
860 
861                         // Test if M is on path Q. If this is not the case,
862                         // we take M as additional point of P.
863                         for (j = 0, is_on_Q = false; j < le2; j++) {
864                             if (Math.abs(this.det(Q[j].coords.usrCoords, Q[(j + 1) % le2].coords.usrCoords, M)) < Mat.eps) {
865                                 is_on_Q = true;
866                                 break;
867                             }
868                         }
869                         if (!is_on_Q) {
870                             // The midpoint is added to the doubly-linked list.
871                             crds = new Coords(Const.COORDS_BY_USER, M, board);
872                             node = {
873                                     pos: i,
874                                     intersection: false,
875                                     coords: crds,
876                                     elementClass: Const.OBJECT_CLASS_POINT
877                                 };
878                             P[i]._next = node;
879                             node._prev = P[i];
880                             P[(i + 1) % le]._prev = node;
881                             node._next = P[(i + 1) % le];
882                             if (P[i]._end) {
883                                 P[i]._end = false;
884                                 node._end = true;
885                             }
886 
887                             break;
888                         }
889                     }
890                 }
891             }
892         },
893 
894         _getStatus: function(P, path) {
895             var status;
896             while (P.intersection) {
897                 if (P._end) {
898                     break;
899                 }
900                 P = P._next;
901             }
902             if (this.windingNumber(P.coords.usrCoords, path) % 2 === 0) {
903                 // Outside
904                 status = 'entry';
905             } else {
906                 // Inside
907                 status = 'exit';
908             }
909 //console.log("STATUS", P.coords.usrCoords, status)
910 
911             return [P, status];
912         },
913 
914         /**
915          * Mark the intersection vertices of path1 as entry points or as exit points
916          * in respect to path2.
917          *
918          * This is the simple algorithm as in
919          * Greiner, Günther; Kai Hormann (1998). "Efficient clipping of arbitrary polygons".
920          * ACM Transactions on Graphics. 17 (2): 71–83
921          *
922          * @private
923          * @param  {Array} path1 First path
924          * @param  {Array} path2 Second path
925          */
926         markEntryExit: function(path1, path2, starters) {
927             var status, P, cnt, res,
928                 i, len, start;
929 
930             len = starters.length;
931             for (i = 0; i < len; i++) {
932 // console.log(";;;;;;;;;;")
933                 start = starters[i];
934                 this._classifyDegenerateIntersections(path1[start]);
935                 this._handleIntersectionChains(path1[start]);
936 
937                 // Decide if the first point of the component is inside or outside
938                 // of the other path.
939                 res = this._getStatus(path1[start], path2);
940                 P = res[0];
941                 status = res[1];
942 // console.log("status", P.coords.usrCoords, status);
943 
944                 P._starter = true;
945                 // Greiner-Hormann entry/exit algorithm
946                 cnt = 0;
947                 while (true) {
948                     if (P.intersection === true && P.data.type === 'X') {
949                         P.entry_exit = status;
950                         status = (status === 'entry') ? 'exit' : 'entry';
951                         if (P.data.link !== null && !P.data.link.entry_exit) {
952                             P.data.link.entry_exit = P.entry_exit;
953                         }
954                     }
955                     if (P.intersection === true && P.data.type !== 'X') {
956                         if (!P.entry_exit && P.data.link !== null) {
957                             P.entry_exit = P.data.link.entry_exit;
958                         }
959                     }
960 // if (P.intersection) { console.log("s>>>", P.coords.usrCoords, P.entry_exit)}
961 
962                     P = P._next;
963                     if (Type.exists(P._starter) || cnt > 10000) {
964                             break;
965                     }
966 
967                     cnt++;
968                 }
969             }
970         },
971 
972         /**
973          *
974          * @private
975          * @param {Array} P
976          * @param {Boolean} isBackward
977          * @returns {Boolean} True, if the node is an intersection and is of type 'X'
978          */
979         _isCrossing: function(P, isBackward) {
980             isBackward = isBackward || false;
981             return P.intersection && ((isBackward ? P.data.revtype : P.data.type) === 'X');
982         },
983 
984         /**
985          * Tracing phase of the Greiner-Hormann algorithm, see
986          * Greiner, Günther; Kai Hormann (1998).
987          * "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83
988          *
989          * Boolean operations on polygons are distinguished: 'intersection', 'union', 'difference'.
990          *
991          * @private
992          * @param  {Array} S           Subject path
993          * @param  {Array} S_intersect Array containing the intersection vertices of the subject path
994          * @param  {String} clip_type  contains the Boolean operation: 'intersection', 'union', or 'difference'
995          * @return {Array}             Array consisting of two arrays containing the x-coordinates and the y-coordintaes of
996          *      the resulting path.
997          */
998         tracing: function(S, S_intersect, clip_type) {
999             var P, current, start,
1000                 cnt = 0,
1001                 reverse,
1002                 maxCnt = 10000,
1003                 S_idx = 0,
1004                 path = [];
1005 
1006 // console.log("------ Start Phase 3");
1007 
1008             reverse = (clip_type === 'difference' || clip_type === 'union') ? true : false;
1009             while (S_idx < S_intersect.length && cnt < maxCnt) {
1010                 // Take the first intersection node of the subject path
1011                 // which is not yet included as start point.
1012                 current = S_intersect[S_idx];
1013                 if (current.data.done || !this._isCrossing(current, reverse)) {
1014                     S_idx++;
1015                     continue;
1016                 }
1017 
1018 // console.log("\nStart", current.data.pathname, current.coords.usrCoords, current.data.type, current.data.revtype, current.entry_exit, S_idx);
1019                 if (path.length > 0) {    // Add a new path
1020                     path.push([NaN, NaN]);
1021                 }
1022 
1023                 // Start now the tracing with that node of the subject path
1024                 start = current.data.idx;
1025                 P = S;
1026                 do {
1027                     // Add the "current" intersection vertex.
1028                     path.push(current);
1029                     current.data.done = true;
1030 
1031 // console.log("Add intersection", current.coords.usrCoords);
1032 // console.log("AT", current.data.pathname, current.entry_exit, current.coords.usrCoords, current.data.type, current.data.revtype);
1033                     //
1034                     // Decide if we follow the current path forward or backward.
1035                     // for example, in case the clipping is of type "intersection"
1036                     // and the current intersection node is of type entry, we go forward.
1037                     //
1038                     if ((clip_type === 'intersection' && current.entry_exit === 'entry') ||
1039                         (clip_type === 'union' && current.entry_exit === 'exit') ||
1040                         (clip_type === 'difference' && (P === S) === (current.entry_exit === 'exit')) ) {
1041 
1042                         //
1043                         // Take the next nodes and add them to the path
1044                         // as long as they are not intersection nodes of type 'X'.
1045                         //
1046                         current = current._next;
1047                         do {
1048                             cnt++;
1049 
1050                             if (!this._isCrossing(current, reverse)) {
1051                                 if (!isNaN(current.coords.usrCoords[1]) && !isNaN(current.coords.usrCoords[2])) {
1052 // if (true ||current.intersection) console.log("Add fw", current.coords.usrCoords, "NEXT", current._next.coords.usrCoords);
1053                                     path.push(current);
1054                                 }
1055                                 current = current._next;
1056                             }
1057                         } while (!this._isCrossing(current, reverse) && cnt < maxCnt);
1058                     } else {
1059 
1060                         //
1061                         // Here, we go backward:
1062                         // Take the previous nodes and add them to the path
1063                         // as long as they are not intersection nodes of type 'X'.
1064                         //
1065                         current = current._prev;
1066                         do {
1067                             cnt++;
1068 
1069                             if (!this._isCrossing(current, true)) {
1070                                 if (!isNaN(current.coords.usrCoords[1]) && !isNaN(current.coords.usrCoords[2])) {
1071 // if (true ||current.intersection) console.log("Add fw", current.coords.usrCoords);
1072                                     path.push(current);
1073                                 }
1074                                 current = current._prev;
1075                             }
1076                         } while (!this._isCrossing(current, true) && cnt < maxCnt);
1077                     }
1078                     current.data.done = true;
1079 
1080                     if (!current.neighbour) {
1081                         console.log("BREAK!!!!!!!!!!!!!!!!!", cnt);
1082                         return [[0], [0]];
1083                     }
1084 
1085 // console.log("Switch", current.coords.usrCoords, current.data.pathname, "to", current.neighbour.data.pathname);
1086                     //
1087                     // We stopped the forwar or backward loop, because we've
1088                     // arrived at a crossing intersection node, i.e. we have to
1089                     // switch to the other path now.
1090                     current = current.neighbour;
1091                     if (current.data.done) {
1092                         // We arrived at an intersection node which is already
1093                         // added to the clipping path.
1094                         // We add it agian to close the clipping path and jump out of the
1095                         // loop.
1096                         path.push(current);
1097 // console.log("Push last", current.coords.usrCoords);
1098                         break;
1099                     }
1100                     P = current.data.path;
1101 
1102                 } while (!(current.data.pathname === 'S' && current.data.idx === start) && cnt < maxCnt);
1103 
1104                 S_idx++;
1105             }
1106 
1107             return this._getCoordsArrays(path, false);
1108         },
1109 
1110         /**
1111          * Handle path clipping if one of the two paths is empty.
1112          * @private
1113          * @param  {Array} S        First path, array of JXG.Coords
1114          * @param  {Array} C        Second path, array of JXG.Coords
1115          * @param  {String} clip_type Type of Boolean operation: 'intersection', 'union', 'differrence'.
1116          * @param  {Array} pathX     Array of x-coordinates of the resulting path
1117          * @param  {Array} pathY    Array of y-coordinates of the resulting path
1118          * @return {Boolean}        true, if one of the input paths is empty, false otherwise.
1119          */
1120         isEmptyCase: function(S, C, clip_type, pathX, pathY) {
1121             // var i;
1122 
1123             if (clip_type === 'intersection' && (S.length === 0 || C.length === 0)) {
1124                 return true; //[pathX, pathY];
1125             }
1126             if (clip_type === 'union' && (S.length === 0 || C.length === 0)) {
1127                 // if (S.length === 0) {
1128                 //     for (i = 0; i < C.length; ++i) {
1129                 //         pathX.push(C[i].coords.usrCoords[1]);
1130                 //         pathY.push(C[i].coords.usrCoords[2]);
1131                 //     }
1132                 //     if (C.length > 0) {
1133                 //         pathX.push(C[0].coords.usrCoords[1]);
1134                 //         pathY.push(C[0].coords.usrCoords[2]);
1135                 //     }
1136                 // } else {
1137                 //     for (i = 0; i < S.length; ++i) {
1138                 //         pathX.push(S[i].coords.usrCoords[1]);
1139                 //         pathY.push(S[i].coords.usrCoords[2]);
1140                 //     }
1141                 //     if (S.length > 0) {
1142                 //         pathX.push(S[0].coords.usrCoords[1]);
1143                 //         pathY.push(S[0].coords.usrCoords[2]);
1144                 //     }
1145                 // }
1146                 return true; //[pathX, pathY];
1147             }
1148             if (clip_type === 'difference' && (S.length === 0 || C.length === 0)) {
1149                 // if (C.length === 0) {
1150                 //     for (i = 0; i < S.length; ++i) {
1151                 //         pathX.push(S[i].coords.usrCoords[1]);
1152                 //         pathY.push(S[i].coords.usrCoords[2]);
1153                 //     }
1154                 //     if (S.length > 0) {
1155                 //         pathX.push(S[0].coords.usrCoords[1]);
1156                 //         pathY.push(S[0].coords.usrCoords[2]);
1157                 //     }
1158                 // }
1159                 return true; //[pathX, pathY];
1160             }
1161 
1162             return false;
1163         },
1164 
1165         _getCoordsArrays: function(path, doClose) {
1166             var pathX = [],
1167                 pathY = [],
1168                 i, le = path.length;
1169 
1170             for (i = 0; i < le; i++) {
1171                 if (path[i].coords) {
1172                     pathX.push(path[i].coords.usrCoords[1]);
1173                     pathY.push(path[i].coords.usrCoords[2]);
1174                 } else {
1175                     pathX.push(path[i][0]);
1176                     pathY.push(path[i][1]);
1177                 }
1178             }
1179             if (doClose && le > 0) {
1180                 if (path[0].coords) {
1181                     pathX.push(path[0].coords.usrCoords[1]);
1182                     pathY.push(path[0].coords.usrCoords[2]);
1183                 } else {
1184                     pathX.push(path[0][0]);
1185                     pathY.push(path[0][1]);
1186                 }
1187             }
1188 
1189             // le = pathX.length;
1190             // for (i = 0; i < le; i++) {
1191             //     console.log(pathX[i], pathY[i]);
1192             // }
1193 
1194             return [pathX, pathY];
1195         },
1196 
1197         /**
1198              * Handle cases when there are no intersection points of the two paths. This is the case if the
1199          * paths are disjoint or one is contained in the other.
1200          * @private
1201          * @param  {Array} S        First path, array of JXG.Coords
1202          * @param  {Array} C        Second path, array of JXG.Coords
1203          * @param  {String} clip_type Type of Boolean operation: 'intersection', 'union', 'differrence'.
1204          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1205          *      the resulting path.
1206          */
1207         handleEmptyIntersection: function(S, C, clip_type) {
1208             var P, Q,
1209                 doClose = false,
1210                 path = [];
1211 
1212             // Handle trivial cases
1213             if (S.length === 0) {
1214                 if (clip_type === 'union') {
1215                     // S cup C = C
1216                     path = C;
1217                 } else {
1218                     // S cap C = S \ C = {}
1219                     path = [];
1220                 }
1221                 return this._getCoordsArrays(path, true);
1222             }
1223             if (C.length === 0) {
1224                 if (clip_type === 'intersection') {
1225                     // S cap C = {}
1226                     path = [];
1227                 } else {
1228                     // S cup C = S \ C = S
1229                     path = S;
1230                 }
1231                 return this._getCoordsArrays(path, true);
1232             }
1233 
1234             // From now on, both paths have non-zero length
1235             //
1236             // Handle union
1237             if (clip_type === 'union') {
1238                 path = path.concat(S);
1239                 path.push(S[0]);
1240                 path.push([NaN, NaN]);
1241                 path = path.concat(C);
1242                 path.push(C[0]);
1243                 return this._getCoordsArrays(path, false);
1244             }
1245 
1246             // The two paths have no crossing intersections,
1247             // but there might be bouncing intersections.
1248 
1249             // First, we find - if possible - on each path a point which is not an intersection point.
1250             if (S.length > 0) {
1251                 P = S[0];
1252                 while (P.intersection) {
1253                     P = P._next;
1254                     if (P._end) {
1255                         break;
1256                     }
1257                 }
1258             }
1259             if (C.length > 0) {
1260                 Q = C[0];
1261                 while (Q.intersection) {
1262                     Q = Q._next;
1263                     if (Q._end) {
1264                         break;
1265                     }
1266                 }
1267             }
1268 
1269             // Test if one curve is contained by the other
1270             if (this.windingNumber(P.coords.usrCoords, C) === 0) {
1271                 // S is outside of C.
1272                 if (this.windingNumber(Q.coords.usrCoords, S) !== 0) {
1273                     // C is inside of S, i.e. C subset of S
1274 
1275                     if (clip_type === 'difference') {
1276 
1277                         path = path.concat(S);
1278                         path.push(S[0]);
1279                         if (Geometry.signedPolygon(S) * Geometry.signedPolygon(C) > 0) {
1280                             // Pathes have same orientation, we have to revert one.
1281                             path.reverse();
1282                         }
1283                         path.push([NaN, NaN]);
1284                     }
1285                     path = path.concat(C);
1286                     path.push(C[0]);
1287                     doClose = false;
1288                 } else {                                           // The curves are disjoint
1289                     if (clip_type === 'difference') {
1290                         path = path.concat(S);
1291                         doClose = true;
1292                     }
1293                 }
1294             } else {
1295                                                                     // S inside of C, i.e. S subset of C
1296                 if (clip_type === 'intersection') {
1297                     path = path.concat(S);
1298                     doClose = true;
1299                 }
1300                 // 'difference': path is empty
1301             }
1302 
1303             return this._getCoordsArrays(path, doClose);
1304         },
1305 
1306         _countCrossingIntersections: function(intersections) {
1307             var i,
1308                 le = intersections.length,
1309                 sum = 0;
1310 
1311             for (i = 0; i  < le; i++) {
1312                 if (intersections[i].data.type === 'X') {
1313                     sum++;
1314                 }
1315             }
1316             return sum;
1317         },
1318 
1319         /**
1320          * Create path from all sorts of input elements to greinerHormann().
1321          *
1322          * @private
1323          * @param {Object} obj Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
1324          * array of coordinate pairs.
1325          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1326          * user coordinates and screen coordinates.
1327          * @returns {Array} Array of JXG.Coords elements containing a path.
1328          * @see JXG.Math.Clip#greinerHormann
1329          */
1330         _getPath: function(obj, board) {
1331             var i, len, r, rad, angle, alpha,
1332                 steps,
1333                 S = [];
1334 
1335             // Collect all points into path array S
1336             if (obj.elementClass === Const.OBJECT_CLASS_CURVE &&
1337                 (obj.type === Const.OBJECT_TYPE_ARC || obj.type === Const.OBJECT_TYPE_SECTOR)) {
1338                 angle = Geometry.rad(obj.radiuspoint, obj.center, obj.anglepoint);
1339                 steps = Math.floor(angle * 180 / Math.PI);
1340                 r = obj.Radius();
1341                 rad = angle / steps;
1342                 alpha = Math.atan2(obj.radiuspoint.coords.usrCoords[2] - obj.center.coords.usrCoords[2],
1343                     obj.radiuspoint.coords.usrCoords[1] - obj.center.coords.usrCoords[1]);
1344 
1345                 if (obj.type === Const.OBJECT_TYPE_SECTOR) {
1346                     this._addToList(S, obj.center.coords, 0);
1347                 }
1348                 for (i = 0; i <= steps; i++) {
1349                     this._addToList(S, new Coords(Const.COORDS_BY_USER, [
1350                         obj.center.coords.usrCoords[0],
1351                         obj.center.coords.usrCoords[1] + Math.cos(i * rad + alpha) * r,
1352                         obj.center.coords.usrCoords[2] + Math.sin(i * rad + alpha) * r
1353                     ], board), i + 1);
1354                 }
1355                 if (obj.type === Const.OBJECT_TYPE_SECTOR) {
1356                     this._addToList(S, obj.center.coords, steps + 2);
1357                 }
1358 
1359             } else if (obj.elementClass === Const.OBJECT_CLASS_CURVE && Type.exists(obj.points)) {
1360                 len = obj.numberPoints;
1361                 for (i = 0; i < len; i++) {
1362                     this._addToList(S, obj.points[i], i);
1363                 }
1364             } else if (obj.type === Const.OBJECT_TYPE_POLYGON) {
1365                 for (i = 0; i < obj.vertices.length; i++) {
1366                     this._addToList(S, obj.vertices[i].coords, i);
1367                 }
1368             } else if (obj.elementClass === Const.OBJECT_CLASS_CIRCLE) {
1369                 steps = 359;
1370                 r = obj.Radius();
1371                 rad = 2 * Math.PI / steps;
1372                 for (i = 0; i <= steps; i++) {
1373                     this._addToList(S, new Coords(Const.COORDS_BY_USER, [
1374                         obj.center.coords.usrCoords[0],
1375                         obj.center.coords.usrCoords[1] + Math.cos(i * rad) * r,
1376                         obj.center.coords.usrCoords[2] + Math.sin(i * rad) * r
1377                     ], board), i);
1378                 }
1379             } else if (Type.isArray(obj)) {
1380                 len = obj.length;
1381                 for (i = 0; i < len; i++) {
1382                     if (Type.exists(obj[i].coords)) {
1383                         // Point type
1384                         this._addToList(S, obj[i].coords, i);
1385                     } else if (Type.isArray(obj[i])) {
1386                         // Coordinate pair
1387                         this._addToList(S, new Coords(Const.COORDS_BY_USER, obj[i], board), i);
1388                     } else if (Type.exists(obj[i].usrCoords)) {
1389                         // JXG.Coordinates
1390                         this._addToList(S, obj[i], i);
1391                     }
1392                 }
1393             }
1394 
1395             return S;
1396         },
1397 
1398         /**
1399          * Determine the intersection, union or difference of two closed paths.
1400          * <p>
1401          * This is an implementation of the Greiner-Hormann algorithm, see
1402          * Günther Greiner and Kai Hormann (1998).
1403          * "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83.
1404          * and
1405          * Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019),
1406          * "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2.
1407          * <p>
1408          * It is assumed that the pathes are closed, whereby it does not matter if the last point indeed
1409          * equals the first point. In contrast to the original Greiner-Hormann algorithm,
1410          * this algorithm can cope with many degenerate cases. A degenerate case is a vertext of one path
1411          * which is contained in the other path.
1412          * <p>
1413          *
1414          * <p>Problematic are:
1415          * <ul>
1416          *   <li>degenerate cases where one path additionally has self-intersections
1417          *   <li>differences with one path having self-intersections.
1418          * </ul>
1419          *
1420          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path, usually called 'subject'.
1421          * Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
1422          * array of coordinate pairs.
1423          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path, usually called 'clip'.
1424          * Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
1425          * array of coordinate pairs.
1426          * @param  {String} clip_type Determines the type of boolean operation on the two paths.
1427          *  Possible values are 'intersection', 'union', or 'difference'.
1428          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1429          * user coordinates and screen coordinates.
1430          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1431          *      the resulting path.
1432          *
1433          * @see JXG.Math.Clip#intersection
1434          * @see JXG.Math.Clip#union
1435          * @see JXG.Math.Clip#difference
1436          *
1437          * @example
1438          *     var curve1 = board.create('curve', [
1439          *             [-3, 3, 0, -3],
1440          *             [3, 3, 0, 3]
1441          *         ],
1442          *         {strokeColor: 'black'});
1443          *
1444          *     var curve2 = board.create('curve', [
1445          *             [-4, 4, 0, -4],
1446          *             [2, 2, 4, 2]
1447          *         ],
1448          *         {strokeColor: 'blue'});
1449          *
1450          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1451          *     clip_path.updateDataArray = function() {
1452          *         var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board);
1453          *
1454          *         this.dataX = a[0];
1455          *         this.dataY = a[1];
1456          *     };
1457          *
1458          *     board.update();
1459          *
1460          * </pre><div id="JXG9d2a6acf-a43b-4035-8f8a-9b1bee580210" class="jxgbox" style="width: 300px; height: 300px;"></div>
1461          * <script type="text/javascript">
1462          *     (function() {
1463          *         var board = JXG.JSXGraph.initBoard('JXG9d2a6acf-a43b-4035-8f8a-9b1bee580210',
1464          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1465          *
1466          *         var curve1 = board.create('curve', [
1467          *                 [-3, 3, 0, -3],
1468          *                 [3, 3, 0, 3]
1469          *             ],
1470          *             {strokeColor: 'black'});
1471          *
1472          *         var curve2 = board.create('curve', [
1473          *                 [-4, 4, 0, -4],
1474          *                 [2, 2, 4, 2]
1475          *             ],
1476          *             {strokeColor: 'blue'});
1477          *
1478          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1479          *         clip_path.updateDataArray = function() {
1480          *             var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board);
1481          *
1482          *             this.dataX = a[0];
1483          *             this.dataY = a[1];
1484          *         };
1485          *
1486          *         board.update();
1487          *
1488          *     })();
1489          *
1490          * </script><pre>
1491          *
1492          * @example
1493          *     var curve1 = board.create('curve', [
1494          *             [-3, 3, 0, -3],
1495          *             [3, 3, 0, 3]
1496          *         ],
1497          *         {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1498          *
1499          *     var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1500          *             {strokeColor: 'blue', fillColor: 'none'});
1501          *
1502          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1503          *     clip_path.updateDataArray = function() {
1504          *         var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board);
1505          *         this.dataX = a[0];
1506          *         this.dataY = a[1];
1507          *     };
1508          *
1509          *     board.update();
1510          *
1511          * </pre><div id="JXG6075c918-4d57-4b72-b600-6597a6a4f44e" class="jxgbox" style="width: 300px; height: 300px;"></div>
1512          * <script type="text/javascript">
1513          *     (function() {
1514          *         var board = JXG.JSXGraph.initBoard('JXG6075c918-4d57-4b72-b600-6597a6a4f44e',
1515          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1516          *         var curve1 = board.create('curve', [
1517          *                 [-3, 3, 0, -3],
1518          *                 [3, 3, 0, 3]
1519          *             ],
1520          *             {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1521          *
1522          *         var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1523          *                 {strokeColor: 'blue', fillColor: 'none'});
1524          *
1525          *
1526          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1527          *         clip_path.updateDataArray = function() {
1528          *             var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board);
1529          *             this.dataX = a[0];
1530          *             this.dataY = a[1];
1531          *         };
1532          *
1533          *         board.update();
1534          *
1535          *     })();
1536          *
1537          * </script><pre>
1538          *
1539          * @example
1540          *     var curve1 = board.create('curve', [
1541          *             [-4, 4, 0, -4],
1542          *             [4, 4, -2, 4]
1543          *         ],
1544          *         {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1545          *
1546          *     var curve2 = board.create('circle', [[0, 0], [0, -2]],
1547          *             {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3,
1548          *             center: {visible: true, size: 5}, point2: {size: 5}});
1549          *
1550          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1551          *     clip_path.updateDataArray = function() {
1552          *         var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board);
1553          *
1554          *         this.dataX = a[0];
1555          *         this.dataY = a[1];
1556          *     };
1557          *
1558          *     board.update();
1559          *
1560          * </pre><div id="JXG46b3316b-5ab9-4928-9473-ccb476ca4185" class="jxgbox" style="width: 300px; height: 300px;"></div>
1561          * <script type="text/javascript">
1562          *     (function() {
1563          *         var board = JXG.JSXGraph.initBoard('JXG46b3316b-5ab9-4928-9473-ccb476ca4185',
1564          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1565          *         var curve1 = board.create('curve', [
1566          *                 [-4, 4, 0, -4],
1567          *                 [4, 4, -2, 4]
1568          *             ],
1569          *             {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1570          *
1571          *         var curve2 = board.create('circle', [[0, 0], [0, -2]],
1572          *                 {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3,
1573          *                 center: {visible: true, size: 5}, point2: {size: 5}});
1574          *
1575          *
1576          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1577          *         clip_path.updateDataArray = function() {
1578          *             var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board);
1579          *
1580          *             this.dataX = a[0];
1581          *             this.dataY = a[1];
1582          *         };
1583          *
1584          *         board.update();
1585          *
1586          *     })();
1587          *
1588          * </script><pre>
1589          *
1590          * @example
1591          * var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6});
1592          * clip_path.updateDataArray = function() {
1593          *     var bbox = this.board.getBoundingBox(),
1594          *         canvas, triangle;
1595          *
1596          *     canvas = [[bbox[0], bbox[1]], // ul
1597          *          [bbox[0], bbox[3]], // ll
1598          *          [bbox[2], bbox[3]], // lr
1599          *          [bbox[2], bbox[1]], // ur
1600          *          [bbox[0], bbox[1]]] // ul
1601          *     triangle = [[-1,1], [1,1], [0,-1], [-1,1]];
1602          * 
1603          *     var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board);
1604          *     this.dataX = a[0];
1605          *     this.dataY = a[1];
1606          * };
1607          * 
1608          * </pre><div id="JXGe94da07a-2a01-4498-ad62-f71a327f8e25" class="jxgbox" style="width: 300px; height: 300px;"></div>
1609          * <script type="text/javascript">
1610          *     (function() {
1611          *         var board = JXG.JSXGraph.initBoard('JXGe94da07a-2a01-4498-ad62-f71a327f8e25',
1612          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1613          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6});
1614          *     clip_path.updateDataArray = function() {
1615          *         var bbox = this.board.getBoundingBox(),
1616          *             canvas, triangle;
1617          *
1618          *         canvas = [[bbox[0], bbox[1]], // ul
1619          *              [bbox[0], bbox[3]], // ll
1620          *              [bbox[2], bbox[3]], // lr
1621          *              [bbox[2], bbox[1]], // ur
1622          *              [bbox[0], bbox[1]]] // ul
1623          *         triangle = [[-1,1], [1,1], [0,-1], [-1,1]];
1624          *
1625          *         var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board);
1626          *         this.dataX = a[0];
1627          *         this.dataY = a[1];
1628          *     };
1629          *
1630          *     })();
1631          *
1632          * </script><pre>
1633          *
1634          */
1635         greinerHormann: function(subject, clip, clip_type, board) { //},
1636                 // subject_first_point_type, clip_first_point_type) {
1637 
1638             var len, S = [],
1639                 C = [],
1640                 S_intersect = [],
1641                 // C_intersect = [],
1642                 S_starters,
1643                 C_starters,
1644                 res = [],
1645                 pathX = [],
1646                 pathY = [];
1647 
1648             // Collect all subject points into subject array S
1649             S = this._getPath(subject, board);
1650             len = S.length;
1651             if (len > 0 && Geometry.distance(S[0].coords.usrCoords, S[len - 1].coords.usrCoords, 3) < Mat.eps) {
1652                 S.pop();
1653             }
1654 
1655             // Collect all points into clip array C
1656             C = this._getPath(clip, board);
1657 
1658             len = C.length;
1659             if (len > 0 && Geometry.distance(C[0].coords.usrCoords, C[len - 1].coords.usrCoords, 3) < Mat.eps * Mat.eps) {
1660                 C.pop();
1661             }
1662 
1663             // Handle cases where at least one of the paths is empty
1664             if (this.isEmptyCase(S, C, clip_type, pathX, pathY)) {
1665                 return [pathX, pathY];
1666             }
1667 
1668             // Add pointers for doubly linked lists
1669             S_starters = this.makeDoublyLinkedList(S);
1670             C_starters = this.makeDoublyLinkedList(C);
1671 
1672             // this._print_array(S);
1673             // console.log("Components:", S_starters);
1674             // this._print_array(C);
1675             // console.log("Components:", C_starters);
1676 
1677             res = this.findIntersections(S, C, board);
1678             S_intersect = res[0];
1679 
1680             // console.log("------- START ------------------")
1681             // let cnt = 0;
1682             // for (let start of S_starters) {
1683             //     console.log("----")
1684             //     let P = S[start];
1685             //     P._start = true;
1686             //     do {
1687             //         console.log(">", P.coords.usrCoords, "NEXT", P._next.coords.usrCoords, "NEXT^2", P._next._next.coords.usrCoords)
1688             //         P = P._next;
1689             //         cnt++;
1690             //     } while (!P._start && cnt < 15);
1691             //     P._start = null;
1692             // }
1693             // console.log("------- END ------------------")
1694 
1695             // C_intersect = res[1];
1696 
1697             // For non-closed paths
1698             // if (true && typeof subject_first_point_type === 'string') {
1699             //     S[0].neighbour = C[C.length - 1];
1700             //     S[0].first_point_type = subject_first_point_type;
1701             //     S[S.length - 1].neighbour = C[0];
1702             //     S[S.length - 1].first_point_type = subject_first_point_type;
1703             // }
1704             // if (true && typeof clip_first_point_type === 'string') {
1705             //     C[0].neighbour = S[S.length - 1];
1706             //     C[0].first_point_type = clip_first_point_type;
1707             //     C[C.length - 1].neighbour = S[0];
1708             //     C[C.length - 1].first_point_type = clip_first_point_type;
1709             // }
1710 
1711             this._handleFullyDegenerateCase(S, C, board);
1712 
1713             // Phase 2: mark intersection points as entry or exit points
1714             this.markEntryExit(S, C, S_starters);
1715 
1716             // if (S[0].coords.distance(Const.COORDS_BY_USER, C[0].coords) === 0) {
1717             //     // Randomly disturb the first point of the second path
1718             //     // if both paths start at the same point.
1719             //     C[0].usrCoords[1] *= 1 + Math.random() * 0.0001 - 0.00005;
1720             //     C[0].usrCoords[2] *= 1 + Math.random() * 0.0001 - 0.00005;
1721             // }
1722             this.markEntryExit(C, S, C_starters);
1723 
1724             // Handle cases without intersections
1725             if (this._countCrossingIntersections(S_intersect) === 0) {
1726                 return this.handleEmptyIntersection(S, C, clip_type);
1727             }
1728 
1729             // Phase 3: tracing
1730             return this.tracing(S, S_intersect, clip_type);
1731 
1732         },
1733 
1734         /**
1735          * Union of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon.
1736          * Computed by the Greiner-Hormann algorithm.
1737          *
1738          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path.
1739          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path.
1740          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1741          * user coordinates and screen coordinates.
1742          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1743          *      the resulting path.
1744          *
1745          * @see JXG.Math.Clip#greinerHormann
1746          * @see JXG.Math.Clip#intersection
1747          * @see JXG.Math.Clip#difference
1748          *
1749          * @example
1750          *     var curve1 = board.create('curve', [
1751          *             [-3, 3, 0, -3],
1752          *             [3, 3, 0, 3]
1753          *         ],
1754          *         {strokeColor: 'black'});
1755          *
1756          *     var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1757          *             {strokeColor: 'blue', fillColor: 'none'});
1758          *
1759          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1760          *     clip_path.updateDataArray = function() {
1761          *         var a = JXG.Math.Clip.union(curve1, curve2, this.board);
1762          *         this.dataX = a[0];
1763          *         this.dataY = a[1];
1764          *     };
1765          *
1766          *     board.update();
1767          *
1768          * </pre><div id="JXG7c5204aa-3824-4464-819c-80df7bf1d917" class="jxgbox" style="width: 300px; height: 300px;"></div>
1769          * <script type="text/javascript">
1770          *     (function() {
1771          *         var board = JXG.JSXGraph.initBoard('JXG7c5204aa-3824-4464-819c-80df7bf1d917',
1772          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1773          *         var curve1 = board.create('curve', [
1774          *                 [-3, 3, 0, -3],
1775          *                 [3, 3, 0, 3]
1776          *             ],
1777          *             {strokeColor: 'black'});
1778          *
1779          *         var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1780          *                 {strokeColor: 'blue', fillColor: 'none'});
1781          *
1782          *
1783          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1784          *         clip_path.updateDataArray = function() {
1785          *             var a = JXG.Math.Clip.union(curve1, curve2, this.board);
1786          *             this.dataX = a[0];
1787          *             this.dataY = a[1];
1788          *         };
1789          *
1790          *         board.update();
1791          *
1792          *     })();
1793          *
1794          * </script><pre>
1795          *
1796          */
1797         union: function(path1, path2, board) {
1798             return this.greinerHormann(path1, path2, 'union', board);
1799         },
1800 
1801         /**
1802          * Intersection of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon.
1803          * Computed by the Greiner-Hormann algorithm.
1804          *
1805          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path.
1806          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path.
1807          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1808          * user coordinates and screen coordinates.
1809          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1810          *      the resulting path.
1811          *
1812          * @see JXG.Math.Clip#greinerHormann
1813          * @see JXG.Math.Clip#union
1814          * @see JXG.Math.Clip#difference
1815          *
1816          * @example
1817          * var p = [];
1818          * p.push(board.create('point', [0, -5]));
1819          * p.push(board.create('point', [-5, 0]));
1820          * p.push(board.create('point', [-3, 3]));
1821          *
1822          * var curve1 = board.create('ellipse', p,
1823          *                 {strokeColor: 'black'});
1824          *
1825          * var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); },
1826          *                                     [0, 0],
1827          *                                     0, 2 * Math.PI],
1828          *                       {curveType:'polar', strokeColor: 'blue', strokewidth:1});
1829          *
1830          * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1831          * clip_path.updateDataArray = function() {
1832          *     var a = JXG.Math.Clip.intersection(curve2, curve1, this.board);
1833          *
1834          *     this.dataX = a[0];
1835          *     this.dataY = a[1];
1836          * };
1837          *
1838          * board.update();
1839          *
1840          * </pre><div id="JXG7ad547eb-7b6c-4a1a-a4d4-4ed298fc7998" class="jxgbox" style="width: 300px; height: 300px;"></div>
1841          * <script type="text/javascript">
1842          *     (function() {
1843          *         var board = JXG.JSXGraph.initBoard('JXG7ad547eb-7b6c-4a1a-a4d4-4ed298fc7998',
1844          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1845          *     var p = [];
1846          *     p.push(board.create('point', [0, -5]));
1847          *     p.push(board.create('point', [-5, 0]));
1848          *     p.push(board.create('point', [-3, 3]));
1849          *
1850          *     var curve1 = board.create('ellipse', p,
1851          *                     {strokeColor: 'black'});
1852          *
1853          *     var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); },
1854          *                                         [0, 0],
1855          *                                         0, 2 * Math.PI],
1856          *                           {curveType:'polar', strokeColor: 'blue', strokewidth:1});
1857          *
1858          *
1859          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1860          *     clip_path.updateDataArray = function() {
1861          *         var a = JXG.Math.Clip.intersection(curve2, curve1, this.board);
1862          *
1863          *         this.dataX = a[0];
1864          *         this.dataY = a[1];
1865          *     };
1866          *
1867          *     board.update();
1868          *
1869          *     })();
1870          *
1871          * </script><pre>
1872          *
1873          *
1874          */
1875         intersection: function(path1, path2, board) {
1876             return this.greinerHormann(path1, path2, 'intersection', board);
1877         },
1878 
1879         /**
1880          * Difference of two closed paths, i.e. path1 minus path2.
1881          * The paths could be JSXGraph elements circle, curve, or polygon.
1882          * Computed by the Greiner-Hormann algorithm.
1883          *
1884          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path.
1885          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path.
1886          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1887          * user coordinates and screen coordinates.
1888          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1889          *      the resulting path.
1890          *
1891          * @see JXG.Math.Clip#greinerHormann
1892          * @see JXG.Math.Clip#intersection
1893          * @see JXG.Math.Clip#union
1894          *
1895          * @example
1896          *     var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]],
1897          *             {strokeColor: 'blue', fillColor: 'none'});
1898          *
1899          *     var curve2 = board.create('curve', [
1900          *             [-1, 1, 0, -1],
1901          *             [1, 1, 3, 1]
1902          *         ],
1903          *         {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1904          *
1905          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1906          *     clip_path.updateDataArray = function() {
1907          *         var a = JXG.Math.Clip.difference(curve1, curve2, this.board);
1908          *         this.dataX = a[0];
1909          *         this.dataY = a[1];
1910          *     };
1911          *
1912          *     board.update();
1913          *
1914          * </pre><div id="JXGc5ce6bb3-146c-457f-a48b-6b9081fb68a3" class="jxgbox" style="width: 300px; height: 300px;"></div>
1915          * <script type="text/javascript">
1916          *     (function() {
1917          *         var board = JXG.JSXGraph.initBoard('JXGc5ce6bb3-146c-457f-a48b-6b9081fb68a3',
1918          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1919          *         var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]],
1920          *                 {strokeColor: 'blue', fillColor: 'none'});
1921          *
1922          *         var curve2 = board.create('curve', [
1923          *                 [-1, 1, 0, -1],
1924          *                 [1, 1, 3, 1]
1925          *             ],
1926          *             {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1927          *
1928          *
1929          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1930          *         clip_path.updateDataArray = function() {
1931          *             var a = JXG.Math.Clip.difference(curve1, curve2, this.board);
1932          *             this.dataX = a[0];
1933          *             this.dataY = a[1];
1934          *         };
1935          *
1936          *         board.update();
1937          *
1938          *     })();
1939          *
1940          * </script><pre>
1941          *
1942          */
1943         difference: function(path1, path2, board) {
1944             return this.greinerHormann(path1, path2, 'difference', board);
1945         }
1946     }; //);
1947 
1948     JXG.extend(Mat.Clip, /** @lends JXG.Math.Clip */ {
1949     });
1950 
1951     return Mat.Clip;
1952 });
1953