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