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