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