1 /*
  2     Copyright 2008-2022
  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                 idx: 0
264             };
265 
266             // Set after initialisation
267             this.neighbour = null;
268             this.entry_exit = false;
269         },
270 
271         _addToList: function(list, coords, pos) {
272             var len = list.length,
273                 eps = Mat.eps * Mat.eps;
274 
275             if (len > 0 &&
276                 Math.abs(list[len - 1].coords.usrCoords[0] - coords.usrCoords[0]) < eps &&
277                 Math.abs(list[len - 1].coords.usrCoords[1] - coords.usrCoords[1]) < eps &&
278                 Math.abs(list[len - 1].coords.usrCoords[2] - coords.usrCoords[2]) < eps) {
279                 // Skip point
280                 return;
281             }
282             list.push({
283                 pos: pos,
284                 intersection: false,
285                 coords: coords,
286                 elementClass: Const.OBJECT_CLASS_POINT
287             });
288         },
289 
290         /**
291          * Sort the intersection points into their path.
292          * @private
293          * @param  {Array} P_crossings Array of arrays. Each array contains the intersections of the path
294          *      with one segment of the other path.
295          * @return {Array}  Array of intersection points ordered by first occurrence in the path.
296          */
297         sortIntersections: function(P_crossings) {
298             var i, j, P, Q,
299                 last,
300                 next_node,
301                 P_intersect = [],
302                 P_le = P_crossings.length;
303 
304             for (i = 0; i < P_le; i++) {
305                 P_crossings[i].sort(function(a, b) { return (a.data.alpha > b.data.alpha) ? 1 : -1; });
306 
307                 if (P_crossings[i].length > 0) {
308                     // console.log("Crossings", P_crossings[i])
309                     last = P_crossings[i].length - 1;
310                     P = P_crossings[i][0];
311 
312                     //console.log("SORT", P.coords.usrCoords)
313                     Q =  P.data.path[P.pos];
314                     next_node = Q._next;  // Store the next "normal" node
315 
316                     if (i === P_le - 1) {
317                         Q._end = false;
318                     }
319 
320                     if (P.data.alpha === 0.0 && P.data.type === 'T') {
321                         // console.log("SKIP", P.coords.usrCoords, P.data.type, P.neighbour.data.type);
322                         Q.intersection = true;
323                         Q.data = P.data;
324                         Q.neighbour = P.neighbour;
325                         Q.neighbour.neighbour = Q;
326                         Q.entry_exit = false;
327                         P_crossings[i][0] = Q;
328                     } else {
329                         // Insert the first intersection point
330                         P._prev = Q;
331                         P._prev._next = P;
332                     }
333 
334                     // Insert the other intersection points, but the last
335                     for (j = 1; j <= last; j++) {
336                         P = P_crossings[i][j];
337                         P._prev = P_crossings[i][j - 1];
338                         P._prev._next = P;
339                     }
340 
341                     // Link last intersection point to the next node
342                     P = P_crossings[i][last];
343                     P._next = next_node;
344                     P._next._prev = P;
345 
346                     if (i === P_le - 1) {
347                         P._end = true;
348                         //console.log("END", P._end, P.coords.usrCoords, P._prev.coords.usrCoords, P._next.coords.usrCoords);
349                     }
350 
351                     P_intersect = P_intersect.concat(P_crossings[i]);
352                 }
353             }
354             return P_intersect;
355         },
356 
357         _inbetween: function(q, p1, p2) {
358             var alpha,
359                 eps = Mat.eps * Mat.eps,
360                 px = p2[1] - p1[1],
361                 py = p2[2] - p1[2],
362                 qx = q[1]  - p1[1],
363                 qy = q[2]  - p1[2];
364 
365             if (px === 0 && py === 0 && qx === 0 && qy === 0) {
366                 // All three points are equal
367                 return true;
368             }
369             if (Math.abs(qx) < eps && Math.abs(px) < eps) {
370                 alpha = qy / py;
371             } else {
372                 alpha = qx / px;
373             }
374             if (Math.abs(alpha) < eps) {
375                 alpha = 0.0;
376             }
377             return alpha;
378         },
379 
380         _print_array: function(arr) {
381             var i, end;
382             for (i = 0; i < arr.length; i++) {
383                 //console.log(i, arr[i].coords.usrCoords,  arr[i].data.type);
384                 try {
385                     end = "";
386                     if (arr[i]._end) {
387                         end = " end";
388                     }
389                     console.log(i, arr[i].coords.usrCoords, arr[i].data.type, "\t",
390                                 "prev", arr[i]._prev.coords.usrCoords,
391                                 "next", arr[i]._next.coords.usrCoords + end);
392                 } catch (e) {
393                     console.log(i, arr[i].coords.usrCoords);
394                 }
395             }
396         },
397 
398         _print_list: function(P) {
399             var cnt = 0, alpha;
400             while (cnt < 100) {
401                 if (P.data) {
402                     alpha = P.data.alpha;
403                 } else {
404                     alpha = '-';
405                 }
406                 console.log("\t", P.coords.usrCoords, "\n\t\tis:", P.intersection, "end:", P._end,
407                             alpha,
408                             "\n\t\t-:", P._prev.coords.usrCoords,
409                             "\n\t\t+:", P._next.coords.usrCoords,
410                             "\n\t\tn:", (P.intersection) ? P.neighbour.coords.usrCoords : '-'
411                             );
412                 if (P._end) {
413                     break;
414                 }
415                 P = P._next;
416                 cnt++;
417             }
418         },
419 
420         _noOverlap: function(p1, p2, q1, q2) {
421             var k,
422                 eps = Math.sqrt(Mat.eps),
423                 minp, maxp, minq, maxq,
424                 no_overlap = false;
425 
426             for (k = 0; k < 3; k++) {
427                 minp = Math.min(p1[k], p2[k]);
428                 maxp = Math.max(p1[k], p2[k]);
429                 minq = Math.min(q1[k], q2[k]);
430                 maxq = Math.max(q1[k], q2[k]);
431                 if (maxp < minq - eps || minp > maxq + eps) {
432                     no_overlap = true;
433                     break;
434                 }
435             }
436             return no_overlap;
437         },
438 
439         /**
440          * Find all intersections between two paths.
441          * @private
442          * @param  {Array} S     Subject path
443          * @param  {Array} C     Clip path
444          * @param  {JXG.Board} board JSXGraph board object. It is needed to convert between
445          * user coordinates and screen coordinates.
446          * @return {Array}  Array containing two arrays. The first array contains the intersection vertices
447          * of the subject path and the second array contains the intersection vertices of the clip path.
448          * @see JXG.Clip#Vertex
449          */
450         findIntersections: function(S, C, board) {
451             var res = [],
452                 eps = Mat.eps,
453                 i, j,
454                 crds,
455                 S_le = S.length,
456                 C_le = C.length,
457                 Si, Si1, Cj, Cj1,
458                 d1, d2,
459                 alpha,
460                 type,
461                 IS, IC,
462                 S_intersect = [],
463                 C_intersect = [],
464                 S_crossings = [],
465                 C_crossings = [],
466                 hasMultCompsS = false,
467                 hasMultCompsC = false,
468                 DEBUG = 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                 // Run through the clip path.
496                 for (j = 0; j < C_le; j++) {
497                     // Test if C[j] or its successor is a path separator.
498                     // If yes, we know that the path consists of multiple components.
499                     // We immediately jump to the next segment.
500                     if (this._isSeparator(C[j]) || this._isSeparator(C[(j + 1) % C_le])) {
501                         hasMultCompsC = true;
502                         continue;
503                     }
504 
505                     // If the path consists of multiple components then there is
506                     // no path-closing segment between the last node and the first
507                     // node. In this case we can leave the loop now.
508                     if (hasMultCompsC && j === C_le - 1) {
509                         break;
510                     }
511 
512                     // Test if bounding boxes of the two curve segments overlap
513                     // If not, the expensive intersection test can be skipped.
514                     Cj  = C[j].coords.usrCoords;
515                     Cj1 = C[(j + 1) % C_le].coords.usrCoords;
516 
517                     if (this._noOverlap(Si, Si1, Cj, Cj1)) {
518                         continue;
519                     }
520 
521                     // Intersection test
522                     res = Geometry.meetSegmentSegment(Si, Si1, Cj, Cj1);
523 
524                     d1 = Geometry.distance(Si, Si1, 3);
525                     d2 = Geometry.distance(Cj, Cj1, 3);
526 
527                     // Found an intersection point
528                     if ( // "Regular" intersection
529                         (res[1] * d1 > -eps && res[1] < 1 - eps / d1 && res[2] * d2 > -eps && res[2] < 1 - eps / d2) ||
530                         // Collinear segments
531                         (res[1] === Infinity && res[2] === Infinity && Mat.norm(res[0], 3) < eps)
532                         ) {
533 
534                         crds = new Coords(Const.COORDS_BY_USER, res[0], board);
535                         type = 'X';
536 
537                         // Handle degenerated cases
538                         if (Math.abs(res[1]) * d1 < eps || Math.abs(res[2]) * d2 < eps) {
539                             // Crossing / bouncing at vertex or
540                             // end of delayed crossing / bouncing
541                             type  = 'T';
542                             if (Math.abs(res[1]) * d1 < eps) {
543                                 res[1] = 0;
544                             }
545                             if (Math.abs(res[2]) * d2 < eps) {
546                                 res[2] = 0;
547                             }
548                             if (res[1] === 0) {
549                                 crds = new Coords(Const.COORDS_BY_USER, Si, board);
550                             } else {
551                                 crds = new Coords(Const.COORDS_BY_USER, Cj, board);
552                             }
553 
554                             if (DEBUG) {
555                                 console.log("Degenerate case I", res[1], res[2], crds.usrCoords, "type", type);
556                             }
557                         } else if (res[1] === Infinity &&
558                                    res[2] === Infinity &&
559                                    Mat.norm(res[0], 3) < eps) {                // console.log(C_intersect);
560 
561 
562                             // Collinear segments
563                             // Here, there might be two intersection points to be added
564 
565                             alpha = this._inbetween(Si, Cj, Cj1);
566                             if (DEBUG) {
567                                 // console.log("alpha Si", alpha, Si);
568                                 // console.log(j, Cj)
569                                 // console.log((j + 1) % C_le, Cj1)
570                             }
571                             if (alpha >= 0 && alpha < 1) {
572                                 type = 'T';
573                                 crds = new Coords(Const.COORDS_BY_USER, Si, board);
574                                 res[1] = 0;
575                                 res[2] = alpha;
576                                 IS = new this.Vertex(crds, i, res[1], S, 'S', type);
577                                 IC = new this.Vertex(crds, j, res[2], C, 'C', type);
578                                 IS.neighbour = IC;
579                                 IC.neighbour = IS;
580                                 S_crossings[i].push(IS);
581                                 C_crossings[j].push(IC);
582                                 if (DEBUG) {
583                                     console.log("Degenerate case II", res[1], res[2], crds.usrCoords, "type T");
584                                 }
585                             }
586                             alpha = this._inbetween(Cj, Si, Si1);
587                             if (DEBUG) {
588                                 // console.log("alpha Cj", alpha, Si, Geometry.distance(Si, Cj, 3));
589                             }
590                             if (Geometry.distance(Si, Cj, 3) > eps &&
591                                 alpha >= 0 && alpha < 1) {
592 
593                                 type = 'T';
594                                 crds = new Coords(Const.COORDS_BY_USER, Cj, board);
595                                 res[1] = alpha;
596                                 res[2] = 0;
597                                 IS = new this.Vertex(crds, i, res[1], S, 'S', type);
598                                 IC = new this.Vertex(crds, j, res[2], C, 'C', type);
599                                 IS.neighbour = IC;
600                                 IC.neighbour = IS;
601                                 S_crossings[i].push(IS);
602                                 C_crossings[j].push(IC);
603                                 if (DEBUG) {
604                                     console.log("Degenerate case III", res[1], res[2], crds.usrCoords, "type T");
605                                 }
606                             }
607                             continue;
608                         }
609                         if (DEBUG) {
610                             console.log("IS", i, j, crds.usrCoords, type);
611                         }
612 
613                         IS = new this.Vertex(crds, i, res[1], S, 'S', type);
614                         IC = new this.Vertex(crds, j, res[2], C, 'C', type);
615                         IS.neighbour = IC;
616                         IC.neighbour = IS;
617 
618                         S_crossings[i].push(IS);
619                         C_crossings[j].push(IC);
620                     }
621                 }
622             }
623 
624             // For both paths, sort their intersection points
625             S_intersect = this.sortIntersections(S_crossings);
626 
627             if (DEBUG) {
628                 console.log('>>>>>> Intersections ');
629                 console.log("S_intersect");
630                 this._print_array(S_intersect);
631                 console.log('----------');
632             }
633             for (i = 0; i < S_intersect.length; i++) {
634                 S_intersect[i].data.idx = i;
635                 S_intersect[i].neighbour.data.idx = i;
636             }
637             C_intersect = this.sortIntersections(C_crossings);
638 
639             if (DEBUG) {
640                 console.log("C_intersect");
641                 this._print_array(C_intersect);
642                 console.log('<<<<<< Phase 1 done');
643             }
644             return [S_intersect, C_intersect];
645         },
646 
647         /**
648          * It is testedd if the point q lies to the left or right
649          * of the poylgonal chain [p1, p2, p3].
650          * @param {Array} q User coords array
651          * @param {Array} p1 User coords array
652          * @param {Array} p2 User coords array
653          * @param {Array} p3 User coords array
654          * @returns string 'left' or 'right'
655          * @private
656          */
657         _getPosition: function(q, p1, p2, p3) {
658             var s1 = this.det(q, p1, p2),
659                 s2 = this.det(q, p2, p3),
660                 s3 = this.det(p1, p2, p3);
661 
662             // Left turn
663             if (s3 >= 0) {
664                 if (s1 >= 0 && s2 >= 0) {
665                     return 'left';
666                 }
667                 return 'right';
668             }
669             // Right turn
670             if (s1 >= 0 || s2 >= 0) {
671                 return 'left';
672             }
673             return 'right';
674         },
675 
676         /**
677          * Determine the delayed status of degenerated intersection points.
678          * It is of the form
679          *   ['on|left|right', 'on|left|right']
680          * <p>
681          * If all four determinants are zero, we add random noise to the point.
682          *
683          * @param {JXG.Math.Clip.Vertex} P Start of path
684          * @private
685          * @see JXG.Math.Clip#markEntryExit
686          * @see JXG.Math.Clip#_handleIntersectionChains
687          */
688         _classifyDegenerateIntersections: function(P) {
689             var Pp, Pm, Qp, Qm, Q, side,
690                 cnt, tmp,
691                 oppositeDir,
692                 s1, s2, s3, s4,
693                 DEBUG = false;
694 
695             if (DEBUG) {
696                 console.log("\n-------------- _classifyDegenerateIntersections()", (Type.exists(P.data))?P.data.pathname:' ');
697             }
698             cnt = 0;
699             P._tours = 0;
700             while (true) {
701                 if (DEBUG) {
702                     console.log("Inspect P:", P.coords.usrCoords, (P.data) ? P.data.type : " ");
703                 }
704                 if (P.intersection && (P.data.type === 'T')) {
705 
706                     // Handle the degenerate cases
707                     // Decide if they are (delayed) bouncing or crossing intersections
708                     Pp = P._next.coords.usrCoords;  // P+
709                     Pm = P._prev.coords.usrCoords;  // P-
710 
711                     // If the intersection point is degenerated and
712                     // equal to the start and end of one component,
713                     // then there will be two adjacent points with
714                     // the same coordinate.
715                     // In that case, we proceed to the next node.
716                     if (Geometry.distance(P.coords.usrCoords, Pp, 3) < Mat.eps) {
717                         Pp = P._next._next.coords.usrCoords;
718                     }
719                     if (Geometry.distance(P.coords.usrCoords, Pm, 3) < Mat.eps) {
720                         Pm = P._prev._prev.coords.usrCoords;
721                     }
722 
723                     Q = P.neighbour;
724                     Qm = Q._prev.coords.usrCoords;  // Q-
725                     Qp = Q._next.coords.usrCoords;  // Q+
726                     if (Geometry.distance(Q.coords.usrCoords, Qp, 3) < Mat.eps) {
727                         Qp = Q._next._next.coords.usrCoords;
728                     }
729                     if (Geometry.distance(Q.coords.usrCoords, Qm, 3) < Mat.eps) {
730                         Qm = Q._prev._prev.coords.usrCoords;
731                     }
732 
733                     if (DEBUG) {
734                         console.log("P chain:", Pm, P.coords.usrCoords, Pp);
735                         console.log("Q chain:", Qm, P.neighbour.coords.usrCoords, Qp);
736                         console.log("Pm", this._getPosition(Pm,  Qm, Q.coords.usrCoords, Qp));
737                         console.log("Pp", this._getPosition(Pp,  Qm, Q.coords.usrCoords, Qp));
738                     }
739 
740                     s1 = this.det(P.coords.usrCoords, Pm, Qm);
741                     s2 = this.det(P.coords.usrCoords, Pp, Qp);
742                     s3 = this.det(P.coords.usrCoords, Pm, Qp);
743                     s4 = this.det(P.coords.usrCoords, Pp, Qm);
744 
745                     if (s1 === 0 && s2 === 0 && s3 === 0 && s4 === 0) {
746                         P.coords.usrCoords[1] *= 1 + Math.random() * Mat.eps;
747                         P.coords.usrCoords[2] *= 1 + Math.random() * Mat.eps;
748                         Q.coords.usrCoords[1] = P.coords.usrCoords[1];
749                         Q.coords.usrCoords[2] = P.coords.usrCoords[2];
750                         s1 = this.det(P.coords.usrCoords, Pm, Qm);
751                         s2 = this.det(P.coords.usrCoords, Pp, Qp);
752                         s3 = this.det(P.coords.usrCoords, Pm, Qp);
753                         s4 = this.det(P.coords.usrCoords, Pp, Qm);
754                         if (DEBUG) {
755                             console.log("Random shift", P.coords.usrCoords);
756                             console.log(s1, s2, s3, s4, s2 === 0);
757                             console.log(this._getPosition(Pm,  Qm, Q.coords.usrCoords, Qp),
758                                 this._getPosition(Pp,  Qm, Q.coords.usrCoords, Qp));
759                         }
760                     }
761                     oppositeDir = false;
762                     if (s1 === 0) {
763                         // Q-, Q=P, P- on straight line
764                         if (Geometry.affineRatio(P.coords.usrCoords, Pm, Qm) < 0) {
765                             oppositeDir = true;
766                         }
767                     } else if (s2 === 0) {
768                         if (Geometry.affineRatio(P.coords.usrCoords, Pp, Qp) < 0) {
769                             oppositeDir = true;
770                         }
771                     } else if (s3 === 0) {
772                         if (Geometry.affineRatio(P.coords.usrCoords, Pm, Qp) > 0) {
773                             oppositeDir = true;
774                         }
775                     } else if (s4 === 0) {
776                         if (Geometry.affineRatio(P.coords.usrCoords, Pp, Qm) > 0) {
777                             oppositeDir = true;
778                         }
779                     }
780                     if (oppositeDir) {
781                         // Swap Qm and Qp
782                         // Then Qm Q Qp has the same direction as Pm P Pp
783                         tmp = Qm; Qm = Qp; Qp = tmp;
784                         tmp = s1; s1 = s3; s3 = tmp;
785                         tmp = s2; s2 = s4; s4 = tmp;
786                     }
787 
788                     if (DEBUG) {
789                         console.log(s1, s2, s3, s4, oppositeDir);
790                     }
791 
792                     if (!Type.exists(P.delayedStatus)) {
793                         P.delayedStatus = [];
794                     }
795 
796                     if (s1 === 0 && s2 === 0) {
797                         // Line [P-,P] equals [Q-,Q] and line [P,P+] equals [Q,Q+]
798                         // Interior of delayed crossing / bouncing
799                         P.delayedStatus = ['on', 'on'];
800 
801                     } else if (s1 === 0) {
802                         // P- on line [Q-,Q], P+ not on line [Q,Q+]
803                         // Begin / end of delayed crossing / bouncing
804                         side = this._getPosition(Pp,  Qm, Q.coords.usrCoords, Qp);
805                         P.delayedStatus = ['on', side];
806 
807                     } else if (s2 === 0) {
808                         // P+ on line [Q,Q+], P- not on line [Q-,Q]
809                         // Begin / end of delayed crossing / bouncing
810                         side = this._getPosition(Pm,  Qm, Q.coords.usrCoords, Qp);
811                         P.delayedStatus = [side, 'on'];
812 
813                     } else {
814                         // Neither P+ on line [Q,Q+], nor P- on line [Q-,Q]
815                         // No delayed crossing / bouncing
816                         if (P.delayedStatus.length === 0) {
817                             if (this._getPosition(Pm,  Qm, Q.coords.usrCoords, Qp) !== this._getPosition(Pp,  Qm, Q.coords.usrCoords, Qp)) {
818                                 P.data.type = 'X';
819                             } else {
820                                 P.data.type = 'B';
821                             }
822                         }
823                     }
824 
825                     if (DEBUG) {
826                         console.log(">>>> P:", P.coords.usrCoords, "delayedStatus:", P.delayedStatus.toString(), (P.data) ? P.data.type : " ", "\n---");
827                     }
828 
829                 }
830 
831                 if (Type.exists(P._tours)) {
832                     P._tours++;
833                 }
834 
835                 if (P._tours > 3 || P._end || cnt > 1000) {
836                     // Jump out if either
837                     // - we reached the end
838                     // - there are more than 1000 intersection points
839                     // - P._tours > 3: We went already 4 times through this path.
840                     if (cnt > 1000) {
841                         console.log("Clipping: _classifyDegenerateIntersections exit");
842                     }
843                     if (Type.exists(P._tours)) {
844                         delete P._tours;
845                     }
846                     break;
847                 }
848                 if (P.intersection) {
849                     cnt++;
850                 }
851                 P = P._next;
852             }
853             if (DEBUG) {
854                 console.log("------------------------");
855             }
856         },
857 
858         /**
859          * At this point the degenerated intersections have been classified.
860          * Now we decide if the intersection chains of the given path
861          * ultimatively cross the other path or bounce.
862          *
863          * @param {JXG.Math.Clip.Vertex} P Start of path
864          *
865          * @see JXG.Math.Clip#markEntryExit
866          * @see JXG.Math.Clip#_classifyDegenerateIntersections
867          * @private
868          */
869         _handleIntersectionChains: function(P) {
870             var cnt = 0,
871                 start_status = 'Null',
872                 P_start,
873                 intersection_chain = false,
874                 wait_for_exit = false,
875                 DEBUG = false;
876 
877             if (DEBUG) {
878                 console.log("\n-------------- _handleIntersectionChains()",
879                     (Type.exists(P.data))?P.data.pathname:' ');
880             }
881             while (true) {
882                 if (P.intersection === true) {
883                     if (DEBUG) {
884                         if (P.data.type === 'T') {
885                             console.log("Degenerate point", P.coords.usrCoords, P.data.type, (P.data.type === 'T')?P.delayedStatus:' ');
886                         } else {
887                             console.log("Intersection point", P.coords.usrCoords, P.data.type);
888                         }
889                     }
890                     if (P.data.type === 'T') {
891                         if (P.delayedStatus[0] !== 'on' && P.delayedStatus[1] === 'on') {
892                             // First point of intersection chain
893                             intersection_chain = true;
894                             P_start = P;
895                             start_status = P.delayedStatus[0];
896 
897                         } else if (intersection_chain &&
898                                     P.delayedStatus[0] === 'on' && P.delayedStatus[1] === 'on') {
899                             // Interior of intersection chain
900                             P.data.type    = 'B';
901                             if (DEBUG) {
902                                 console.log("Interior", P.coords.usrCoords);
903                             }
904                         } else if (intersection_chain &&
905                                     P.delayedStatus[0] === 'on' && P.delayedStatus[1] !== 'on') {
906                             // Last point of intersection chain
907                             intersection_chain = false;
908                             if (start_status === P.delayedStatus[1]) {
909                                 // Intersection chain is delayed bouncing
910                                 P_start.data.type    = 'DB';
911                                 P.data.type          = 'DB';
912                                 if (DEBUG) {
913                                     console.log("Chain: delayed bouncing", P_start.coords.usrCoords, '...', P.coords.usrCoords);
914                                 }
915                             } else {
916                                 // Intersection chain is delayed crossing
917                                 P_start.data.type    = 'DX';
918                                 P.data.type          = 'DX';
919                                 if (DEBUG) {
920                                     console.log("Chain: delayed crossing", P_start.coords.usrCoords, '...', P.coords.usrCoords);
921                                 }
922                             }
923                         }
924                     }
925                     cnt++;
926                 }
927                 if (P._end) {
928                     wait_for_exit = true;
929                 }
930                 if (wait_for_exit && !intersection_chain) {
931                     break;
932                 }
933                 if (cnt > 1000) {
934                     console.log("Warning: _handleIntersectionChains: intersection chain reached maximum numbers of iterations");
935                     break;
936                 }
937                 P = P._next;
938             }
939         },
940 
941         /**
942          * Handle the case that all vertices of one path are contained
943          * in the other path. In this case we search for a midpoint of an edge
944          * which is not contained in the other path and add it to the path.
945          * It will be used as starting point for the entry/exit algorithm.
946          *
947          * @private
948          * @param {Array} S Subject path
949          * @param {Array} C Clip path
950          * @param {JXG.board} board JSXGraph board object. It is needed to convert between
951          * user coordinates and screen coordinates.
952          */
953         _handleFullyDegenerateCase: function(S, C, board) {
954             var P, Q, l, M, crds, q1, q2, node,
955                 i, j, le, le2, is_on_Q,
956                 is_fully_degenerated,
957                 arr = [S, C];
958 
959             for (l = 0; l < 2; l++) {
960                 P = arr[l];
961                 le = P.length;
962                 for (i = 0, is_fully_degenerated = true; i < le; i++) {
963                     if (!P[i].intersection) {
964                         is_fully_degenerated = false;
965                         break;
966                     }
967                 }
968 
969                 if (is_fully_degenerated) {
970                     // All nodes of P are also on the other path.
971                     Q = arr[(l + 1) % 2];
972                     le2 = Q.length;
973 
974                     // We search for a midpoint of one edge of P which is not the other path and
975                     // we add that midpoint to P.
976                     for (i = 0; i < le; i++) {
977                         q1 = P[i].coords.usrCoords;
978                         q2 = P[(i + 1) % le].coords.usrCoords;
979                         // M id the midpoint
980                         M = [(q1[0] +  q2[0]) * 0.5,
981                              (q1[1] +  q2[1]) * 0.5,
982                              (q1[2] +  q2[2]) * 0.5];
983 
984                         // Test if M is on path Q. If this is not the case,
985                         // we take M as additional point of P.
986                         for (j = 0, is_on_Q = false; j < le2; j++) {
987                             if (Math.abs(this.det(Q[j].coords.usrCoords, Q[(j + 1) % le2].coords.usrCoords, M)) < Mat.eps) {
988                                 is_on_Q = true;
989                                 break;
990                             }
991                         }
992                         if (!is_on_Q) {
993                             // The midpoint is added to the doubly-linked list.
994                             crds = new Coords(Const.COORDS_BY_USER, M, board);
995                             node = {
996                                     pos: i,
997                                     intersection: false,
998                                     coords: crds,
999                                     elementClass: Const.OBJECT_CLASS_POINT
1000                                 };
1001                             P[i]._next = node;
1002                             node._prev = P[i];
1003                             P[(i + 1) % le]._prev = node;
1004                             node._next = P[(i + 1) % le];
1005                             if (P[i]._end) {
1006                                 P[i]._end = false;
1007                                 node._end = true;
1008                             }
1009 
1010                             break;
1011                         }
1012                     }
1013                 }
1014             }
1015         },
1016 
1017         _getStatus: function(P, path) {
1018             var status;
1019             while (P.intersection) {
1020                 if (P._end) {
1021                     break;
1022                 }
1023                 P = P._next;
1024             }
1025             if (this.windingNumber(P.coords.usrCoords, path) % 2 === 0) {
1026                 // Outside
1027                 status = 'entry';
1028             } else {
1029                 // Inside
1030                 status = 'exit';
1031             }
1032 
1033             return [P, status];
1034         },
1035 
1036         /**
1037          * Mark the intersection vertices of path1 as entry points or as exit points
1038          * in respect to path2.
1039          * <p>
1040          * This is the simple algorithm as in
1041          * Greiner, Günther; Kai Hormann (1998). "Efficient clipping of arbitrary polygons".
1042          * ACM Transactions on Graphics. 17 (2): 71–83
1043          * <p>
1044          * The algorithm handles also "delayed crossings" from
1045          * Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019),
1046          * "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2.
1047          * and - as an additional improvement -
1048          * handles self intersections of delayed crossings (A.W. 2021).
1049          *
1050          * @private
1051          * @param  {Array} path1 First path
1052          * @param  {Array} path2 Second path
1053          */
1054         markEntryExit: function(path1, path2, starters) {
1055             var status, P, cnt, res,
1056                 i, len, start,
1057                 chain_start = null,
1058                 intersection_chain = 0,
1059                 DEBUG = false;
1060 
1061             len = starters.length;
1062             for (i = 0; i < len; i++) {
1063                 start = starters[i];
1064                 if (DEBUG) {
1065                     console.log("\n;;;;;;;;;; Labelling phase",
1066                         (Type.exists(path1[start].data))?path1[start].data.pathname:' ',
1067                         path1[start].coords.usrCoords);
1068                 }
1069                 this._classifyDegenerateIntersections(path1[start]);
1070                 this._handleIntersectionChains(path1[start]);
1071                 if (DEBUG) {
1072                     console.log("\n---- back to markEntryExit");
1073                 }
1074 
1075                 // Decide if the first point of the component is inside or outside
1076                 // of the other path.
1077                 res = this._getStatus(path1[start], path2);
1078                 P = res[0];
1079                 status = res[1];
1080                 if (DEBUG) {
1081                     console.log("Start node:", P.coords.usrCoords, status);
1082                 }
1083 
1084                 P._starter = true;
1085 
1086                 // Greiner-Hormann entry/exit algorithm
1087                 // with additional handling of delayed crossing / bouncing
1088                 cnt = 0;
1089                 chain_start = null;
1090                 intersection_chain = 0;
1091 
1092                 while (true) {
1093                     if (P.intersection === true) {
1094                         if (P.data.type === 'X' && intersection_chain === 1) {
1095                             // While we are in an intersection chain, i.e. a delayed crossing,
1096                             // we stumble on a crossing intersection.
1097                             // Probably, the other path is self intersecting.
1098                             // We end the intersection chain here and
1099                             // mark this event by setting intersection_chain = 2.
1100                             chain_start.entry_exit = status;
1101                             if (status === 'exit') {
1102                                 chain_start.data.type = 'X';
1103                             }
1104                             intersection_chain = 2;
1105                         }
1106 
1107                         if (P.data.type === 'X' || P.data.type === 'DB') {
1108                             P.entry_exit = status;
1109                             status = (status === 'entry') ? 'exit' : 'entry';
1110                             if (DEBUG) {
1111                                 console.log("mark:", P.coords.usrCoords, P.data.type, P.entry_exit);
1112                             }
1113                         }
1114 
1115                         if (P.data.type === 'DX') {
1116                             if (intersection_chain === 0) {
1117                                 // Start of intersection chain.
1118                                 // No active intersection chain yet,
1119                                 // i.e. we did not pass a the first node of a delayed crossing.
1120                                 chain_start = P;
1121                                 intersection_chain = 1;
1122                                 if (DEBUG) {
1123                                     console.log("Start intersection chain:", P.coords.usrCoords, P.data.type, status);
1124                                 }
1125 
1126                             } else if (intersection_chain === 1) {
1127                                 // Active intersection chain (intersection_chain===1)!
1128                                 // End of delayed crossing chain reached
1129                                 P.entry_exit = status;
1130                                 chain_start.entry_exit = status;
1131                                 if (status === 'exit') {
1132                                     chain_start.data.type = 'X';
1133                                 } else {
1134                                     P.data.type = 'X';
1135                                 }
1136                                 status = (status === 'entry') ? 'exit' : 'entry';
1137 
1138                                 if (DEBUG) {
1139                                     console.log("mark':", chain_start.coords.usrCoords, chain_start.data.type, chain_start.entry_exit);
1140                                     console.log("mark:", P.coords.usrCoords, P.data.type, P.entry_exit);
1141                                 }
1142                                 chain_start = null;
1143                                 intersection_chain = 0;
1144 
1145                             } else if (intersection_chain === 2) {
1146                                 // The delayed crossing had been interrupted by a crossing intersection.
1147                                 // Now we treat the end of the delayed crossing as regular crossing.
1148                                 P.entry_exit = status;
1149                                 P.data.type = 'X';
1150                                 status = (status === 'entry') ? 'exit' : 'entry';
1151                                 chain_start = null;
1152                                 intersection_chain = 0;
1153                             }
1154                         }
1155                     }
1156 
1157                     P = P._next;
1158                     if (Type.exists(P._starter) || cnt > 10000) {
1159                             break;
1160                     }
1161 
1162                     cnt++;
1163                 }
1164             }
1165         },
1166 
1167         /**
1168          *
1169          * @private
1170          * @param {Array} P
1171          * @param {Boolean} isBackward
1172          * @returns {Boolean} True, if the node is an intersection and is of type 'X'
1173          */
1174         _stayOnPath: function(P, status) {
1175             var stay = true;
1176 
1177             if (P.intersection && P.data.type !== 'B') {
1178                 stay = (status === P.entry_exit);
1179             }
1180             return stay;
1181         },
1182 
1183         /**
1184          * Add a point to the clipping path and returns if the algorithms
1185          * arrived at an intersection point which has already been visited.
1186          * In this case, true is returned.
1187          *
1188          * @param {Array} path Resulting path
1189          * @param {JXG.Math.Clip.Vertex} vertex Point to be added
1190          * @param {Boolean} DEBUG debug output to console.log
1191          * @returns {Boolean} true: point has been visited before, false otherwise
1192          * @private
1193          */
1194         _addVertex: function(path, vertex, DEBUG) {
1195             if (!isNaN(vertex.coords.usrCoords[1]) && !isNaN(vertex.coords.usrCoords[2])) {
1196                 path.push(vertex);
1197             }
1198             if (vertex.intersection && vertex.data.done) {
1199                 if (DEBUG) {
1200                     console.log("Add last intersection point", vertex.coords.usrCoords,
1201                         "on", vertex.data.pathname, vertex.entry_exit,
1202                         vertex.data.type);
1203                 }
1204                 return true;
1205             }
1206             if (vertex.intersection) {
1207                 vertex.data.done = true;
1208 
1209                 if (DEBUG) {
1210                     console.log("Add intersection point", vertex.coords.usrCoords,
1211                         "on", vertex.data.pathname, vertex.entry_exit,
1212                         vertex.data.type);
1213                 }
1214             }
1215             return false;
1216         },
1217 
1218         /**
1219          * Tracing phase of the Greiner-Hormann algorithm, see
1220          * Greiner, Günther; Kai Hormann (1998).
1221          * "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83
1222          *
1223          * Boolean operations on polygons are distinguished: 'intersection', 'union', 'difference'.
1224          *
1225          * @private
1226          * @param  {Array} S           Subject path
1227          * @param  {Array} S_intersect Array containing the intersection vertices of the subject path
1228          * @param  {String} clip_type  contains the Boolean operation: 'intersection', 'union', or 'difference'
1229          * @return {Array}             Array consisting of two arrays containing the x-coordinates and the y-coordintaes of
1230          *      the resulting path.
1231          */
1232         tracing: function(S, S_intersect, clip_type) {
1233             var P, current, start,
1234                 cnt = 0,
1235                 status,
1236                 maxCnt = 10000,
1237                 S_idx = 0,
1238                 path = [],
1239                 done = false,
1240                 DEBUG = false;
1241 
1242             if (DEBUG) {
1243                 console.log("\n------ Start Phase 3");
1244             }
1245 
1246             // reverse = (clip_type === 'difference' || clip_type === 'union') ? true : false;
1247             while (S_idx < S_intersect.length && cnt < maxCnt) {
1248                 // Take the first intersection node of the subject path
1249                 // which is not yet included as start point.
1250                 current = S_intersect[S_idx];
1251                 if (current.data.done || current.data.type !== 'X' /*|| !this._isCrossing(current, reverse)*/) {
1252                     S_idx++;
1253                     continue;
1254                 }
1255 
1256                 if (DEBUG) {
1257                     console.log("\nStart", current.data.pathname, current.coords.usrCoords, current.data.type, current.entry_exit, S_idx);
1258                 }
1259                 if (path.length > 0) {    // Add a new path
1260                     path.push([NaN, NaN]);
1261                 }
1262 
1263                 // Start now the tracing with that node of the subject path
1264                 start = current.data.idx;
1265                 P = S;
1266 
1267                 done = this._addVertex(path, current, DEBUG);
1268                 status = current.entry_exit;
1269                 do {
1270                     if (done) {
1271                         break;
1272                     }
1273                     //
1274                     // Decide if we follow the current path forward or backward.
1275                     // for example, in case the clipping is of type "intersection"
1276                     // and the current intersection node is of type entry, we go forward.
1277                     //
1278                     if ((clip_type === 'intersection' && current.entry_exit === 'entry') ||
1279                         (clip_type === 'union' && current.entry_exit === 'exit') ||
1280                         (clip_type === 'difference' && (P === S) === (current.entry_exit === 'exit')) ) {
1281 
1282                         if (DEBUG) {
1283                             console.log("Go forward on", current.data.pathname, current.entry_exit);
1284                         }
1285 
1286                         //
1287                         // Take the next nodes and add them to the path
1288                         // as long as they are not intersection nodes of type 'X'.
1289                         //
1290                         do {
1291                             current = current._next;
1292                             done = this._addVertex(path, current, DEBUG);
1293                             if (done) {
1294                                 break;
1295                             }
1296                         } while (this._stayOnPath(current, status));
1297                         cnt++;
1298                     } else {
1299                         if (DEBUG) {
1300                             console.log("Go backward on", current.data.pathname);
1301                         }
1302                         //
1303                         // Here, we go backward:
1304                         // Take the previous nodes and add them to the path
1305                         // as long as they are not intersection nodes of type 'X'.
1306                         //
1307                         do {
1308                             current = current._prev;
1309                             done = this._addVertex(path, current, DEBUG);
1310                             if (done) {
1311                                 break;
1312                             }
1313                         } while (this._stayOnPath(current, status));
1314                         cnt++;
1315                     }
1316 
1317                     if (done) {
1318                         break;
1319                     }
1320 
1321                     if (!current.neighbour) {
1322                         console.log("Tracing: emergency break - no neighbour!!!!!!!!!!!!!!!!!", cnt);
1323                         return [[0], [0]];
1324                     }
1325                     //
1326                     // We stopped the forward or backward loop, because we've
1327                     // arrived at a crossing intersection node, i.e. we have to
1328                     // switch to the other path now.
1329                     if (DEBUG) {
1330                         console.log("Switch from", current.coords.usrCoords, current.data.pathname, "to",
1331                         current.neighbour.coords.usrCoords, "on", current.neighbour.data.pathname);
1332                     }
1333                     current = current.neighbour;
1334                     if (current.data.done) {
1335                         break;
1336                     }
1337                     current.data.done = true;
1338                     status = current.entry_exit;
1339 
1340                     // if (current.data.done) {
1341                     //     // We arrived at an intersection node which is already
1342                     //     // added to the clipping path.
1343                     //     // We add it again to close the clipping path and jump out of the
1344                     //     // loop.
1345                     //     path.push(current);
1346                     //     if (DEBUG) {
1347                     //         console.log("Push last", current.coords.usrCoords);
1348                     //     }
1349                     //     break;
1350                     // }
1351                     P = current.data.path;
1352 
1353                     // Polygon closed:
1354                     // if (DEBUG) {
1355                     //     console.log("End of loop:", "start=", start, "idx=", current.data.idx);
1356                     // }
1357                 // } while (!(current.data.pathname === 'S' && current.data.idx === start) && cnt < maxCnt);
1358                 } while (current.data.idx !== start && cnt < maxCnt);
1359 
1360                 if (cnt >= maxCnt) {
1361                     console.log("Tracing: stopping an infinite loop!", cnt);
1362                 }
1363 
1364                 S_idx++;
1365             }
1366             return this._getCoordsArrays(path, false);
1367         },
1368 
1369         /**
1370          * Handle path clipping if one of the two paths is empty.
1371          * @private
1372          * @param  {Array} S        First path, array of JXG.Coords
1373          * @param  {Array} C        Second path, array of JXG.Coords
1374          * @param  {String} clip_type Type of Boolean operation: 'intersection', 'union', 'differrence'.
1375          * @return {Boolean}        true, if one of the input paths is empty, false otherwise.
1376          */
1377         isEmptyCase: function(S, C, clip_type) {
1378             if (clip_type === 'intersection' && (S.length === 0 || C.length === 0)) {
1379                 return true;
1380             }
1381             if (clip_type === 'union' && (S.length === 0 && C.length === 0)) {
1382                 return true;
1383             }
1384             if (clip_type === 'difference' && S.length === 0) {
1385                 return true;
1386             }
1387 
1388             return false;
1389         },
1390 
1391         _getCoordsArrays: function(path, doClose) {
1392             var pathX = [],
1393                 pathY = [],
1394                 i, le = path.length;
1395 
1396             for (i = 0; i < le; i++) {
1397                 if (path[i].coords) {
1398                     pathX.push(path[i].coords.usrCoords[1]);
1399                     pathY.push(path[i].coords.usrCoords[2]);
1400                 } else {
1401                     pathX.push(path[i][0]);
1402                     pathY.push(path[i][1]);
1403                 }
1404             }
1405             if (doClose && le > 0) {
1406                 if (path[0].coords) {
1407                     pathX.push(path[0].coords.usrCoords[1]);
1408                     pathY.push(path[0].coords.usrCoords[2]);
1409                 } else {
1410                     pathX.push(path[0][0]);
1411                     pathY.push(path[0][1]);
1412                 }
1413             }
1414 
1415             return [pathX, pathY];
1416         },
1417 
1418         /**
1419          * Handle cases when there are no intersection points of the two paths. This is the case if the
1420          * paths are disjoint or one is contained in the other.
1421          * @private
1422          * @param  {Array} S        First path, array of JXG.Coords
1423          * @param  {Array} C        Second path, array of JXG.Coords
1424          * @param  {String} clip_type Type of Boolean operation: 'intersection', 'union', 'differrence'.
1425          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1426          *      the resulting path.
1427          */
1428         handleEmptyIntersection: function(S, C, clip_type) {
1429             var P, Q,
1430                 doClose = false,
1431                 path = [];
1432 
1433             // Handle trivial cases
1434             if (S.length === 0) {
1435                 if (clip_type === 'union') {
1436                     // S cup C = C
1437                     path = C;
1438                 } else {
1439                     // S cap C = S \ C = {}
1440                     path = [];
1441                 }
1442                 return this._getCoordsArrays(path, true);
1443             }
1444             if (C.length === 0) {
1445                 if (clip_type === 'intersection') {
1446                     // S cap C = {}
1447                     path = [];
1448                 } else {
1449                     // S cup C = S \ C = S
1450                     path = S;
1451                 }
1452                 return this._getCoordsArrays(path, true);
1453             }
1454 
1455             // From now on, both paths have non-zero length.
1456             // The two paths have no crossing intersections,
1457             // but there might be bouncing intersections.
1458 
1459             // First, we find -- if possible -- on each path a point which is not an intersection point.
1460             if (S.length > 0) {
1461                 P = S[0];
1462                 while (P.intersection) {
1463                     P = P._next;
1464                     if (P._end) {
1465                         break;
1466                     }
1467                 }
1468             }
1469             if (C.length > 0) {
1470                 Q = C[0];
1471                 while (Q.intersection) {
1472                     Q = Q._next;
1473                     if (Q._end) {
1474                         break;
1475                     }
1476                 }
1477             }
1478 
1479             // Test if one curve is contained by the other
1480             if (this.windingNumber(P.coords.usrCoords, C) === 0) {
1481                 // P is outside of C:
1482                 // Either S is disjoint from C or C is inside of S
1483                 if (this.windingNumber(Q.coords.usrCoords, S) !== 0) {
1484                     // C is inside of S, i.e. C subset of S
1485 
1486                     if (clip_type === 'union') {
1487                         path = path.concat(S);
1488                         path.push(S[0]);
1489                     } else if (clip_type === 'difference') {
1490                         path = path.concat(S);
1491                         path.push(S[0]);
1492                         if (Geometry.signedPolygon(S) * Geometry.signedPolygon(C) > 0) {
1493                             // Pathes have same orientation, we have to revert one.
1494                             path.reverse();
1495                         }
1496                         path.push([NaN, NaN]);
1497                     }
1498                     if (clip_type === 'difference' || clip_type === 'intersection') {
1499                         path = path.concat(C);
1500                         path.push(C[0]);
1501                         doClose = false;
1502                     }
1503                 } else {                                           // The curves are disjoint
1504                     if (clip_type === 'difference') {
1505                         path = path.concat(S);
1506                         doClose = true;
1507                     } else if (clip_type === 'union') {
1508                         path = path.concat(S);
1509                         path.push(S[0]);
1510                         path.push([NaN, NaN]);
1511                         path = path.concat(C);
1512                         path.push(C[0]);
1513                     }
1514                 }
1515             } else {
1516                                                                     // S inside of C, i.e. S subset of C
1517                 if (clip_type === 'intersection') {
1518                     path = path.concat(S);
1519                     doClose = true;
1520                 } else if (clip_type === 'union') {
1521                     path = path.concat(C);
1522                     path.push(C[0]);
1523                 }
1524 
1525                 // 'difference': path is empty
1526             }
1527 
1528             return this._getCoordsArrays(path, doClose);
1529         },
1530 
1531         /**
1532          * Count intersection points of type 'X'.
1533          * @param {JXG.Mat.Clip.Vertex} intersections
1534          * @returns Number
1535          * @private
1536          */
1537         _countCrossingIntersections: function(intersections) {
1538             var i,
1539                 le = intersections.length,
1540                 sum = 0;
1541 
1542             for (i = 0; i  < le; i++) {
1543                 if (intersections[i].data.type === 'X') {
1544                     sum++;
1545                 }
1546             }
1547             return sum;
1548         },
1549 
1550         /**
1551          * Create path from all sorts of input elements and convert it
1552          * to a suitable input path for greinerHormann().
1553          *
1554          * @private
1555          * @param {Object} obj Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
1556          * array of coordinate pairs.
1557          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1558          * user coordinates and screen coordinates.
1559          * @returns {Array} Array of JXG.Coords elements containing a path.
1560          * @see JXG.Math.Clip#greinerHormann
1561          */
1562         _getPath: function(obj, board) {
1563             var i, len, r, rad, angle, alpha,
1564                 steps,
1565                 S = [];
1566 
1567             // Collect all points into path array S
1568             if (obj.elementClass === Const.OBJECT_CLASS_CURVE &&
1569                 (obj.type === Const.OBJECT_TYPE_ARC || obj.type === Const.OBJECT_TYPE_SECTOR)) {
1570                 angle = Geometry.rad(obj.radiuspoint, obj.center, obj.anglepoint);
1571                 steps = Math.floor(angle * 180 / Math.PI);
1572                 r = obj.Radius();
1573                 rad = angle / steps;
1574                 alpha = Math.atan2(obj.radiuspoint.coords.usrCoords[2] - obj.center.coords.usrCoords[2],
1575                     obj.radiuspoint.coords.usrCoords[1] - obj.center.coords.usrCoords[1]);
1576 
1577                 if (obj.type === Const.OBJECT_TYPE_SECTOR) {
1578                     this._addToList(S, obj.center.coords, 0);
1579                 }
1580                 for (i = 0; i <= steps; i++) {
1581                     this._addToList(S, new Coords(Const.COORDS_BY_USER, [
1582                         obj.center.coords.usrCoords[0],
1583                         obj.center.coords.usrCoords[1] + Math.cos(i * rad + alpha) * r,
1584                         obj.center.coords.usrCoords[2] + Math.sin(i * rad + alpha) * r
1585                     ], board), i + 1);
1586                 }
1587                 if (obj.type === Const.OBJECT_TYPE_SECTOR) {
1588                     this._addToList(S, obj.center.coords, steps + 2);
1589                 }
1590 
1591             } else if (obj.elementClass === Const.OBJECT_CLASS_CURVE && Type.exists(obj.points)) {
1592                 len = obj.numberPoints;
1593                 for (i = 0; i < len; i++) {
1594                     this._addToList(S, obj.points[i], i);
1595                 }
1596             } else if (obj.type === Const.OBJECT_TYPE_POLYGON) {
1597                 for (i = 0; i < obj.vertices.length; i++) {
1598                     this._addToList(S, obj.vertices[i].coords, i);
1599                 }
1600             } else if (obj.elementClass === Const.OBJECT_CLASS_CIRCLE) {
1601                 steps = 359;
1602                 r = obj.Radius();
1603                 rad = 2 * Math.PI / steps;
1604                 for (i = 0; i <= steps; i++) {
1605                     this._addToList(S, new Coords(Const.COORDS_BY_USER, [
1606                         obj.center.coords.usrCoords[0],
1607                         obj.center.coords.usrCoords[1] + Math.cos(i * rad) * r,
1608                         obj.center.coords.usrCoords[2] + Math.sin(i * rad) * r
1609                     ], board), i);
1610                 }
1611             } else if (Type.isArray(obj)) {
1612                 len = obj.length;
1613                 for (i = 0; i < len; i++) {
1614                     if (Type.exists(obj[i].coords)) {
1615                         // Point type
1616                         this._addToList(S, obj[i].coords, i);
1617                     } else if (Type.isArray(obj[i])) {
1618                         // Coordinate pair
1619                         this._addToList(S, new Coords(Const.COORDS_BY_USER, obj[i], board), i);
1620                     } else if (Type.exists(obj[i].usrCoords)) {
1621                         // JXG.Coordinates
1622                         this._addToList(S, obj[i], i);
1623                     }
1624                 }
1625             }
1626 
1627             return S;
1628         },
1629 
1630         /**
1631          * Determine the intersection, union or difference of two closed paths.
1632          * <p>
1633          * This is an implementation of the Greiner-Hormann algorithm, see
1634          * Günther Greiner and Kai Hormann (1998).
1635          * "Efficient clipping of arbitrary polygons". ACM Transactions on Graphics. 17 (2): 71–83.
1636          * and
1637          * Erich, L. Foster, and Kai Hormann, Kai, and Romeo Traaian Popa (2019),
1638          * "Clipping simple polygons with degenerate intersections", Computers & Graphics:X, 2.
1639          * <p>
1640          * It is assumed that the pathes are closed, whereby it does not matter if the last point indeed
1641          * equals the first point. In contrast to the original Greiner-Hormann algorithm,
1642          * this algorithm can cope with many degenerate cases. A degenerate case is a vertext of one path
1643          * which is contained in the other path.
1644          * <p>
1645          *
1646          * <p>Problematic are:
1647          * <ul>
1648          *   <li>degenerate cases where one path additionally has self-intersections
1649          *   <li>differences with one path having self-intersections.
1650          * </ul>
1651          *
1652          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path, usually called 'subject'.
1653          * Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
1654          * array of coordinate pairs.
1655          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path, usually called 'clip'.
1656          * Maybe curve, arc, sector, circle, polygon, array of points, array of JXG.Coords,
1657          * array of coordinate pairs.
1658          * @param  {String} clip_type Determines the type of boolean operation on the two paths.
1659          *  Possible values are 'intersection', 'union', or 'difference'.
1660          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1661          * user coordinates and screen coordinates.
1662          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1663          *      the resulting path.
1664          *
1665          * @see JXG.Math.Clip#intersection
1666          * @see JXG.Math.Clip#union
1667          * @see JXG.Math.Clip#difference
1668          *
1669          * @example
1670          *     var curve1 = board.create('curve', [
1671          *             [-3, 3, 0, -3],
1672          *             [3, 3, 0, 3]
1673          *         ],
1674          *         {strokeColor: 'black'});
1675          *
1676          *     var curve2 = board.create('curve', [
1677          *             [-4, 4, 0, -4],
1678          *             [2, 2, 4, 2]
1679          *         ],
1680          *         {strokeColor: 'blue'});
1681          *
1682          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1683          *     clip_path.updateDataArray = function() {
1684          *         var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board);
1685          *
1686          *         this.dataX = a[0];
1687          *         this.dataY = a[1];
1688          *     };
1689          *
1690          *     board.update();
1691          *
1692          * </pre><div id="JXG9d2a6acf-a43b-4035-8f8a-9b1bee580210" class="jxgbox" style="width: 300px; height: 300px;"></div>
1693          * <script type="text/javascript">
1694          *     (function() {
1695          *         var board = JXG.JSXGraph.initBoard('JXG9d2a6acf-a43b-4035-8f8a-9b1bee580210',
1696          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1697          *
1698          *         var curve1 = board.create('curve', [
1699          *                 [-3, 3, 0, -3],
1700          *                 [3, 3, 0, 3]
1701          *             ],
1702          *             {strokeColor: 'black'});
1703          *
1704          *         var curve2 = board.create('curve', [
1705          *                 [-4, 4, 0, -4],
1706          *                 [2, 2, 4, 2]
1707          *             ],
1708          *             {strokeColor: 'blue'});
1709          *
1710          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1711          *         clip_path.updateDataArray = function() {
1712          *             var a = JXG.Math.Clip.greinerHormann(curve2, curve1, 'intersection', this.board);
1713          *
1714          *             this.dataX = a[0];
1715          *             this.dataY = a[1];
1716          *         };
1717          *
1718          *         board.update();
1719          *
1720          *     })();
1721          *
1722          * </script><pre>
1723          *
1724          * @example
1725          *     var curve1 = board.create('curve', [
1726          *             [-3, 3, 0, -3],
1727          *             [3, 3, 0, 3]
1728          *         ],
1729          *         {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1730          *
1731          *     var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1732          *             {strokeColor: 'blue', fillColor: 'none'});
1733          *
1734          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1735          *     clip_path.updateDataArray = function() {
1736          *         var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board);
1737          *         this.dataX = a[0];
1738          *         this.dataY = a[1];
1739          *     };
1740          *
1741          *     board.update();
1742          *
1743          * </pre><div id="JXG6075c918-4d57-4b72-b600-6597a6a4f44e" class="jxgbox" style="width: 300px; height: 300px;"></div>
1744          * <script type="text/javascript">
1745          *     (function() {
1746          *         var board = JXG.JSXGraph.initBoard('JXG6075c918-4d57-4b72-b600-6597a6a4f44e',
1747          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1748          *         var curve1 = board.create('curve', [
1749          *                 [-3, 3, 0, -3],
1750          *                 [3, 3, 0, 3]
1751          *             ],
1752          *             {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1753          *
1754          *         var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1755          *                 {strokeColor: 'blue', fillColor: 'none'});
1756          *
1757          *
1758          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1759          *         clip_path.updateDataArray = function() {
1760          *             var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'union', this.board);
1761          *             this.dataX = a[0];
1762          *             this.dataY = a[1];
1763          *         };
1764          *
1765          *         board.update();
1766          *
1767          *     })();
1768          *
1769          * </script><pre>
1770          *
1771          * @example
1772          *     var curve1 = board.create('curve', [
1773          *             [-4, 4, 0, -4],
1774          *             [4, 4, -2, 4]
1775          *         ],
1776          *         {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1777          *
1778          *     var curve2 = board.create('circle', [[0, 0], [0, -2]],
1779          *             {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3,
1780          *             center: {visible: true, size: 5}, point2: {size: 5}});
1781          *
1782          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1783          *     clip_path.updateDataArray = function() {
1784          *         var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board);
1785          *
1786          *         this.dataX = a[0];
1787          *         this.dataY = a[1];
1788          *     };
1789          *
1790          *     board.update();
1791          *
1792          * </pre><div id="JXG46b3316b-5ab9-4928-9473-ccb476ca4185" class="jxgbox" style="width: 300px; height: 300px;"></div>
1793          * <script type="text/javascript">
1794          *     (function() {
1795          *         var board = JXG.JSXGraph.initBoard('JXG46b3316b-5ab9-4928-9473-ccb476ca4185',
1796          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1797          *         var curve1 = board.create('curve', [
1798          *                 [-4, 4, 0, -4],
1799          *                 [4, 4, -2, 4]
1800          *             ],
1801          *             {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
1802          *
1803          *         var curve2 = board.create('circle', [[0, 0], [0, -2]],
1804          *                 {strokeColor: 'blue', strokeWidth: 1, fillColor: 'red', fixed: true, fillOpacity: 0.3,
1805          *                 center: {visible: true, size: 5}, point2: {size: 5}});
1806          *
1807          *
1808          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.6});
1809          *         clip_path.updateDataArray = function() {
1810          *             var a = JXG.Math.Clip.greinerHormann(curve1, curve2, 'difference', this.board);
1811          *
1812          *             this.dataX = a[0];
1813          *             this.dataY = a[1];
1814          *         };
1815          *
1816          *         board.update();
1817          *
1818          *     })();
1819          *
1820          * </script><pre>
1821          *
1822          * @example
1823          * var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6});
1824          * clip_path.updateDataArray = function() {
1825          *     var bbox = this.board.getBoundingBox(),
1826          *         canvas, triangle;
1827          *
1828          *     canvas = [[bbox[0], bbox[1]], // ul
1829          *          [bbox[0], bbox[3]], // ll
1830          *          [bbox[2], bbox[3]], // lr
1831          *          [bbox[2], bbox[1]], // ur
1832          *          [bbox[0], bbox[1]]] // ul
1833          *     triangle = [[-1,1], [1,1], [0,-1], [-1,1]];
1834          *
1835          *     var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board);
1836          *     this.dataX = a[0];
1837          *     this.dataY = a[1];
1838          * };
1839          *
1840          * </pre><div id="JXGe94da07a-2a01-4498-ad62-f71a327f8e25" class="jxgbox" style="width: 300px; height: 300px;"></div>
1841          * <script type="text/javascript">
1842          *     (function() {
1843          *         var board = JXG.JSXGraph.initBoard('JXGe94da07a-2a01-4498-ad62-f71a327f8e25',
1844          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1845          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 1, fillColor: 'yellow', fillOpacity: 0.6});
1846          *     clip_path.updateDataArray = function() {
1847          *         var bbox = this.board.getBoundingBox(),
1848          *             canvas, triangle;
1849          *
1850          *         canvas = [[bbox[0], bbox[1]], // ul
1851          *              [bbox[0], bbox[3]], // ll
1852          *              [bbox[2], bbox[3]], // lr
1853          *              [bbox[2], bbox[1]], // ur
1854          *              [bbox[0], bbox[1]]] // ul
1855          *         triangle = [[-1,1], [1,1], [0,-1], [-1,1]];
1856          *
1857          *         var a = JXG.Math.Clip.greinerHormann(canvas, triangle, 'difference', this.board);
1858          *         this.dataX = a[0];
1859          *         this.dataY = a[1];
1860          *     };
1861          *
1862          *     })();
1863          *
1864          * </script><pre>
1865          *
1866          */
1867         greinerHormann: function(subject, clip, clip_type, board) { //},
1868                 // subject_first_point_type, clip_first_point_type) {
1869 
1870             var len, S = [],
1871                 C = [],
1872                 S_intersect = [],
1873                 // C_intersect = [],
1874                 S_starters,
1875                 C_starters,
1876                 res = [],
1877                 DEBUG = false;
1878 
1879             if (DEBUG) {
1880                 console.log("\n------------ GREINER-HORMANN --------------");
1881             }
1882             // Collect all subject points into subject array S
1883             S = this._getPath(subject, board);
1884             len = S.length;
1885             if (len > 0 && Geometry.distance(S[0].coords.usrCoords, S[len - 1].coords.usrCoords, 3) < Mat.eps) {
1886                 S.pop();
1887             }
1888 
1889             // Collect all points into clip array C
1890             C = this._getPath(clip, board);
1891             len = C.length;
1892             if (len > 0 && Geometry.distance(C[0].coords.usrCoords, C[len - 1].coords.usrCoords, 3) < Mat.eps * Mat.eps) {
1893                 C.pop();
1894             }
1895 
1896             // Handle cases where at least one of the paths is empty
1897             if (this.isEmptyCase(S, C, clip_type)) {
1898                 return [[], []];
1899             }
1900 
1901             // Add pointers for doubly linked lists
1902             S_starters = this.makeDoublyLinkedList(S);
1903             C_starters = this.makeDoublyLinkedList(C);
1904 
1905             if (DEBUG) {
1906                 this._print_array(S);
1907                 console.log("Components:", S_starters);
1908                 this._print_array(C);
1909                 console.log("Components:", C_starters);
1910             }
1911 
1912             res = this.findIntersections(S, C, board);
1913             S_intersect = res[0];
1914 
1915             this._handleFullyDegenerateCase(S, C, board);
1916 
1917             // Phase 2: mark intersection points as entry or exit points
1918             this.markEntryExit(S, C, S_starters);
1919 
1920             // if (S[0].coords.distance(Const.COORDS_BY_USER, C[0].coords) === 0) {
1921             //     // Randomly disturb the first point of the second path
1922             //     // if both paths start at the same point.
1923             //     C[0].usrCoords[1] *= 1 + Math.random() * 0.0001 - 0.00005;
1924             //     C[0].usrCoords[2] *= 1 + Math.random() * 0.0001 - 0.00005;
1925             // }
1926             this.markEntryExit(C, S, C_starters);
1927 
1928             // Handle cases without intersections
1929             if (this._countCrossingIntersections(S_intersect) === 0) {
1930                 return this.handleEmptyIntersection(S, C, clip_type);
1931             }
1932 
1933             // Phase 3: tracing
1934             return this.tracing(S, S_intersect, clip_type);
1935         },
1936 
1937         /**
1938          * Union of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon.
1939          * Computed by the Greiner-Hormann algorithm.
1940          *
1941          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path.
1942          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path.
1943          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
1944          * user coordinates and screen coordinates.
1945          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
1946          *      the resulting path.
1947          *
1948          * @see JXG.Math.Clip#greinerHormann
1949          * @see JXG.Math.Clip#intersection
1950          * @see JXG.Math.Clip#difference
1951          *
1952          * @example
1953          *     var curve1 = board.create('curve', [
1954          *             [-3, 3, 0, -3],
1955          *             [3, 3, 0, 3]
1956          *         ],
1957          *         {strokeColor: 'black'});
1958          *
1959          *     var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1960          *             {strokeColor: 'blue', fillColor: 'none'});
1961          *
1962          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1963          *     clip_path.updateDataArray = function() {
1964          *         var a = JXG.Math.Clip.union(curve1, curve2, this.board);
1965          *         this.dataX = a[0];
1966          *         this.dataY = a[1];
1967          *     };
1968          *
1969          *     board.update();
1970          *
1971          * </pre><div id="JXG7c5204aa-3824-4464-819c-80df7bf1d917" class="jxgbox" style="width: 300px; height: 300px;"></div>
1972          * <script type="text/javascript">
1973          *     (function() {
1974          *         var board = JXG.JSXGraph.initBoard('JXG7c5204aa-3824-4464-819c-80df7bf1d917',
1975          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
1976          *         var curve1 = board.create('curve', [
1977          *                 [-3, 3, 0, -3],
1978          *                 [3, 3, 0, 3]
1979          *             ],
1980          *             {strokeColor: 'black'});
1981          *
1982          *         var curve2 = board.create('polygon', [[3, 4], [-4, 0], [-4, 4]],
1983          *                 {strokeColor: 'blue', fillColor: 'none'});
1984          *
1985          *
1986          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
1987          *         clip_path.updateDataArray = function() {
1988          *             var a = JXG.Math.Clip.union(curve1, curve2, this.board);
1989          *             this.dataX = a[0];
1990          *             this.dataY = a[1];
1991          *         };
1992          *
1993          *         board.update();
1994          *
1995          *     })();
1996          *
1997          * </script><pre>
1998          *
1999          */
2000         union: function(path1, path2, board) {
2001             return this.greinerHormann(path1, path2, 'union', board);
2002         },
2003 
2004         /**
2005          * Intersection of two closed paths. The paths could be JSXGraph elements circle, curve, or polygon.
2006          * Computed by the Greiner-Hormann algorithm.
2007          *
2008          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path.
2009          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path.
2010          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
2011          * user coordinates and screen coordinates.
2012          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
2013          *      the resulting path.
2014          *
2015          * @see JXG.Math.Clip#greinerHormann
2016          * @see JXG.Math.Clip#union
2017          * @see JXG.Math.Clip#difference
2018          *
2019          * @example
2020          * var p = [];
2021          * p.push(board.create('point', [0, -5]));
2022          * p.push(board.create('point', [-5, 0]));
2023          * p.push(board.create('point', [-3, 3]));
2024          *
2025          * var curve1 = board.create('ellipse', p,
2026          *                 {strokeColor: 'black'});
2027          *
2028          * var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); },
2029          *                                     [0, 0],
2030          *                                     0, 2 * Math.PI],
2031          *                       {curveType:'polar', strokeColor: 'blue', strokewidth:1});
2032          *
2033          * var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
2034          * clip_path.updateDataArray = function() {
2035          *     var a = JXG.Math.Clip.intersection(curve2, curve1, this.board);
2036          *
2037          *     this.dataX = a[0];
2038          *     this.dataY = a[1];
2039          * };
2040          *
2041          * board.update();
2042          *
2043          * </pre><div id="JXG7ad547eb-7b6c-4a1a-a4d4-4ed298fc7998" class="jxgbox" style="width: 300px; height: 300px;"></div>
2044          * <script type="text/javascript">
2045          *     (function() {
2046          *         var board = JXG.JSXGraph.initBoard('JXG7ad547eb-7b6c-4a1a-a4d4-4ed298fc7998',
2047          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
2048          *     var p = [];
2049          *     p.push(board.create('point', [0, -5]));
2050          *     p.push(board.create('point', [-5, 0]));
2051          *     p.push(board.create('point', [-3, 3]));
2052          *
2053          *     var curve1 = board.create('ellipse', p,
2054          *                     {strokeColor: 'black'});
2055          *
2056          *     var curve2 = board.create('curve', [function(phi){return 4 * Math.cos(2*phi); },
2057          *                                         [0, 0],
2058          *                                         0, 2 * Math.PI],
2059          *                           {curveType:'polar', strokeColor: 'blue', strokewidth:1});
2060          *
2061          *
2062          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
2063          *     clip_path.updateDataArray = function() {
2064          *         var a = JXG.Math.Clip.intersection(curve2, curve1, this.board);
2065          *
2066          *         this.dataX = a[0];
2067          *         this.dataY = a[1];
2068          *     };
2069          *
2070          *     board.update();
2071          *
2072          *     })();
2073          *
2074          * </script><pre>
2075          *
2076          *
2077          */
2078         intersection: function(path1, path2, board) {
2079             return this.greinerHormann(path1, path2, 'intersection', board);
2080         },
2081 
2082         /**
2083          * Difference of two closed paths, i.e. path1 minus path2.
2084          * The paths could be JSXGraph elements circle, curve, or polygon.
2085          * Computed by the Greiner-Hormann algorithm.
2086          *
2087          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} subject   First closed path.
2088          * @param  {JXG.Circle|JXG.Curve|JXG.Polygon} clip      Second closed path.
2089          * @param  {JXG.Board} board   JSXGraph board object. It is needed to convert between
2090          * user coordinates and screen coordinates.
2091          * @return {Array}          Array consisting of two arrays containing the x-coordinates and the y-coordinates of
2092          *      the resulting path.
2093          *
2094          * @see JXG.Math.Clip#greinerHormann
2095          * @see JXG.Math.Clip#intersection
2096          * @see JXG.Math.Clip#union
2097          *
2098          * @example
2099          *     var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]],
2100          *             {strokeColor: 'blue', fillColor: 'none'});
2101          *
2102          *     var curve2 = board.create('curve', [
2103          *             [-1, 1, 0, -1],
2104          *             [1, 1, 3, 1]
2105          *         ],
2106          *         {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
2107          *
2108          *     var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
2109          *     clip_path.updateDataArray = function() {
2110          *         var a = JXG.Math.Clip.difference(curve1, curve2, this.board);
2111          *         this.dataX = a[0];
2112          *         this.dataY = a[1];
2113          *     };
2114          *
2115          *     board.update();
2116          *
2117          * </pre><div id="JXGc5ce6bb3-146c-457f-a48b-6b9081fb68a3" class="jxgbox" style="width: 300px; height: 300px;"></div>
2118          * <script type="text/javascript">
2119          *     (function() {
2120          *         var board = JXG.JSXGraph.initBoard('JXGc5ce6bb3-146c-457f-a48b-6b9081fb68a3',
2121          *             {boundingbox: [-8, 8, 8,-8], axis: true, showcopyright: false, shownavigation: false});
2122          *         var curve1 = board.create('polygon', [[-4, 4], [4, 4], [0, -1]],
2123          *                 {strokeColor: 'blue', fillColor: 'none'});
2124          *
2125          *         var curve2 = board.create('curve', [
2126          *                 [-1, 1, 0, -1],
2127          *                 [1, 1, 3, 1]
2128          *             ],
2129          *             {strokeColor: 'black', fillColor: 'none', fillOpacity: 0.8});
2130          *
2131          *
2132          *         var clip_path = board.create('curve', [[], []], {strokeWidth: 3, fillColor: 'yellow', fillOpacity: 0.3});
2133          *         clip_path.updateDataArray = function() {
2134          *             var a = JXG.Math.Clip.difference(curve1, curve2, this.board);
2135          *             this.dataX = a[0];
2136          *             this.dataY = a[1];
2137          *         };
2138          *
2139          *         board.update();
2140          *
2141          *     })();
2142          *
2143          * </script><pre>
2144          *
2145          */
2146         difference: function(path1, path2, board) {
2147             return this.greinerHormann(path1, path2, 'difference', board);
2148         }
2149     }; //);
2150 
2151     JXG.extend(Mat.Clip, /** @lends JXG.Math.Clip */ {
2152     });
2153 
2154     return Mat.Clip;
2155 });
2156