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