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