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