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